Constant folding
|
|
In compiler theory, constant folding and constant propagation are related optimization techniques used by many modern compilers. A more advanced form of constant propagation known as sparse conditional constant propagation may be utilized to simultaneously remove dead code and more accurately propagate constants.
| Contents |
Constant folding
Constant folding is the process of simplifying constant expressions at compile time. Terms in constant expressions are typically simple literals, such as the integer 2, but can also be variables whose values are never modified, or variables explicitly marked as constant. Consider the statement:
i = 320 * 200 * 32;
Most modern compilers would not actually generate two multiply instructions and a store for this statement. Instead, they identify constructs such as these, and substitute the computed values at compile time (in this case, 1,024,000), usually in the intermediate representation (IR) tree.
In some compilers, constant folding is done early so that statements such as C's array initializers can accept simple arithmetic expressions. However, it is also common to include further constant folding rounds in later stages in the compiler, as well.
Constant folding can be done in a compiler's front end on the IR tree that represents the high-level source language, before it is translated into three-address code, or in the back end, as an adjunct to constant propagation.
Constant propagation
Constant propagation is the process of substituting the values of known constants in expressions at compile time. Such constants include those defined above, as well as intrinsic functions applied to constant values. Consider the following pseudocode:
int x = 14; int y = 7 - x / 2; return y * (28 / x + 2);
Applying constant propagation once yields:
int x = 14; int y = 7 - 14 / 2; return y * (28 / 14 + 2);
A typical compiler might apply constant folding now, to simplify the resulting expressions, before attempting further propagation.
Constant propagation can also cause conditional branches to simplify to one or more unconditional statements, when the conditional expression can be evaluated to true or false at compile time to determine the only possible outcome.
The optimizations in action
Constant folding and propagation are typically used together to achieve many simplifications and reductions, by interleaving them iteratively until no more changes occur. Consider this pseudocode, for example:
int a = 30;
int b = 9 - a / 5;
int c;
c = b * 4;
if (c > 10) {
c = c - 10;
}
return c * (60 / a);
Applying constant propagation once, followed by constant folding, yields:
int a = 30;
int b = 3;
int c;
c = b * 4;
if (c > 10) {
c = c - 10;
}
return c * 2;
As a and b have been simplified to constants and their values substituted everywhere they occurred, the compiler now applies dead code elimination to discard them, reducing the code further:
int c;
c = 12;
if (12 > 10) {
c = 2;
}
return c * 2;
The compiler can now detect that the if statement will always evaluate to true, c itself can be eliminated, shrinking the code even further:
return 4;
If this pseudocode constituted the body of a function, the compiler could further take advantage of the knowledge that it evaluates to the constant integer 4 to eliminate unnecessary calls to the function, producing further performance gains.
Further reading
- Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997.