Constant folding

related topics
{math, number, function}
{math, energy, light}

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

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

[edit] 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.

[edit] 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);

Propagating x yields:

 int x = 14;
 int y = 7 - 14 / 2;
 return y * (28 / 14 + 2);

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

 int x = 14;
 int y = 0;
 return 0;

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

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.

[edit] 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:

Full article ▸

related documents
Hilbert's Nullstellensatz
Linearity of integration
Rectangle
Euler's theorem
Z notation
List of Fourier-related transforms
Sigmoid function
Group object
Product of group subsets
Discrete mathematics
Surjective function
Derivative of a constant
Essential singularity
Online algorithm
Direct sum of groups
The Third Manifesto
De Bruijn-Newman constant
Greibach normal form
Hurwitz polynomial
Precondition
Distinct
Context-free language
Dense set
Conjugate closure
CycL
RC5
Recursive language
Location parameter
Persistence
Lazy initialization