Constant folding

Constant folding and constant propagation are related compiler optimizations used by many modern compilers. ^[1] An advanced form of constant propagation known as sparse conditional constant propagation can more accurately propagate constants and simultaneously remove dead code.

Constant folding

Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, but they may also be variables whose values are known at compile time. Consider the statement:

i=320*200*32;

Most 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, 2,048,000).

Constant folding can make use of arithmetic identities. If x is numeric, the value of 0 * x is zero even if the compiler does not know the value of x (note that this is not valid for IEEE floats since x could be Infinity or NaN. Still, some environments that favor performance such as GLSL shaders allow this for constants, which can occasionally cause bugs).

Constant folding may apply to more than just numbers. Concatenation of string literals and constant strings can be constant folded. Code such as "abc" + "def" may be replaced with "abcdef".

Constant folding and cross compilation

In implementing a cross compiler, care must be taken to ensure that the behaviour of the arithmetic operations on the host architecture matches that on the target architecture, as otherwise enabling constant folding will change the behaviour of the program. This is of particular importance in the case of floating point operations, whose precise implementation may vary widely.

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:

intx=14;inty=7-x/2;returny*(28/x+2);

Propagating x yields:

intx=14;inty=7-14/2;returny*(28/14+2);

Continuing to propagate yields the following (which would likely be further optimized by dead-code elimination of both x and y.)

intx=14;inty=0;return0;

Constant propagation is implemented in compilers using reaching definition analysis results. If all a variable's reaching definitions are the same assignment - which assigns a same constant to the variable - then the variable will always have the same value, and can be replaced with the constant.

Constant propagation can also cause conditional branches to simplify to one or more unconditional statements, if 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, and their interleaved, iterative application continues until those effects cease.

Consider this unoptimized pseudocode returning a number unknown pending analysis:

inta=30;intb=9-(a/5);intc=b*4;if(c>10){c=c-10;}returnc*(60/a);

Applying constant propagation once, followed by constant folding, yields:

inta=30;intb=3;intc=b*4;if(c>10){c=c-10;}returnc*2;

Repeating both steps twice produces:

inta=30;intb=3;intc=12;if(true){c=2;}returnc*2;

Having replaced all uses of variables a and b with constants, the compiler's dead-code elimination applies to those variables, leaving:

intc=12;if(true){c=2;}returnc*2;

(Boolean constructs vary among languages and compilers, but their details—such as the status, origin, and representation of true—do not affect these optimization principles.)

Traditional constant propagation produces no further optimization; it does not restructure programs.

However, a similar optimization, sparse conditional constant propagation, goes further by selecting the appropriate conditional branch, ^[2] and removing the always-true conditional test. Thus, variable c becomes redundant, and only an operation on a constant remains:

return4;

If that pseudocode constitutes a function body, the compiler knows the function evaluates to integer constant 4, allowing replacement of calls to the function with 4, and further increasing program efficiency.

See also

• Control-flow graph
• Use-define chain and SSA form
• Copy propagation
• Common subexpression elimination
• Partial evaluation

References

1. Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation . Morgan Kaufmann. ISBN   978-1-55860-320-2. constant propagation OR constant folding.
2. Wegman, Mark N; Zadeck, F. Kenneth (April 1991), "Constant Propagation with Conditional Branches", ACM Transactions on Programming Languages and Systems, 13 (2): 181–210, CiteSeerX   10.1.1.130.3532 , doi:10.1145/103135.103136, S2CID   52813828

Further reading

• Muchnick, Steven S. (1997), Advanced Compiler Design and Implementation , Morgan Kaufmann, ISBN   9781558603202