display | more...

"Constant folding" is one of the easiest ways to make a compiler generate more efficient code. There's not much to it: If the result of an expression can be known to the compiler, it's a "constant expression". The compiler evaluates it and puts the result in the generated code as a literal value, rather than generating code to evaluate the whole expression at run time (how many times does a given program need to reassure itself that 1+1=2?). If the compiler can figure it out, the programmer could have figured it out too, of course, but there are cases where programmers do things the long way for the sake of clarity, or just because they feel like it:

#define	WEEK_SECONDS   ( 60 * 60 * 24 * 7 )
#define TWOPI          ( PI * 2 )

Neither of those expressions should ever be evaluated at run-time, and programmers have a reasonable expectation that they won't be.

There are various ways to go about doing this. The most obvious way is to walk your parse tree in post-order and annotate all the literal-value nodes as constant, and all operator nodes with no non-constant operands as constant, and so on. Once the walker backs up out of a constant expression onto something non-constant, it can evaluate the constant expression, remove that branch, and bung in the value to replace it. The problem is ensuring that the compile-time evaluation of the expression is identical to what the run-time evaluation would have been.

There's fun way to ensure identicality of evaluation, which the Dragon Book attributes to Ken Thompson: Generate the code for the constant expression, keeping track of where it starts. Execute that code right there using whatever means will be used at run-time (e.g., if it's native code, move the program counter and let it do its thing), and replace the constant expression's code with its result.

There are some expressions whose results can in fact be known in advance by the compiler, but which have putatively variable operands. Those are discussed in data flow analysis.

Log in or register to write something here or to contact authors.