Constant folding
Encyclopedia
Constant folding and constant propagation are related compiler optimization
s used by many modern compiler
s. An advanced form of constant propagation known as sparse conditional constant propagation
can more accurately propagate constants and simultaneously remove dead code
.
expressions at compile time
. Terms in constant expressions are typically simple literals, such as the integer
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.
, 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.
s 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.
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 = 3 * 4;
if (c > 10) {
c = c - 10;
}
return c * 2;
As
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
,
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
Compiler optimization
Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
s used by many modern compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
s. An advanced form of constant propagation known as sparse conditional constant propagation
Sparse conditional constant propagation
In computer science, sparse conditional constant propagation is an optimization frequently applied in compilers after conversion to static single assignment form . It simultaneously removes some kinds of dead code and propagates constants throughout a program...
can more accurately propagate constants and simultaneously remove dead code
Dead code
Dead code is a computer programming term for code in the source code of a program which is executed but whose result is never used in any other computation...
.
Constant folding
Constant folding is the process of simplifying constantConstant (programming)
In computer programming, a constant is an identifier whose associated value cannot typically be altered by the program during its execution...
expressions at compile time
Compile time
In computer science, compile time refers to either the operations performed by a compiler , programming language requirements that must be met by source code for it to be successfully compiled , or properties of the program that can be reasoned about at compile time.The operations performed at...
. 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
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
'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 folding and cross compilation
In implementing a cross compilerCross compiler
A cross compiler is a compiler capable of creating executable code for a platform other than the one on which the compiler is run. Cross compiler tools are used to generate executables for embedded system or multiple platforms. It is used to compile for a platform upon which it is not feasible to...
, 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
Floating point
In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent. The base for the scaling is normally 2, 10 or 16...
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 functionIntrinsic function
In compiler theory, an intrinsic function is a function available for use in a given language whose implementation is handled specially by the compiler. Typically, it substitutes a sequence of automatically generated instructions for the original function call, similar to an inline function...
s 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
Dead code elimination
In compiler theory, dead code elimination is a compiler optimization to remove code which does not affect the program results. Removing such code has two benefits: it shrinks program size, an important...
of both x and y.)
int x = 14;
int y = 0;
return 0;
Constant propagation is implemented in compilers using reaching definition
Reaching definition
In compiler theory, a reaching definition for a given instruction is another instruction, the target variable of which may reach the given instruction without an intervening assignment. For example, in the following code: d1 : y := 3 d2 : x := y...
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.
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 = 3 * 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 eliminationDead code elimination
In compiler theory, dead code elimination is a compiler optimization to remove code which does not affect the program results. Removing such code has two benefits: it shrinks program size, an important...
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 trueBoolean datatype
In computer science, the Boolean or logical data type is a data type, having two values , intended to represent the truth values of logic and Boolean algebra...
,
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.
See also
- Control flow graphControl flow graphA control flow graph in computer science is a representation, using graph notation, of all paths that might be traversed through a program during its execution.- Overview :...
- SSA form
- Copy propagationCopy propagationIn compiler theory, copy propagation is the process of replacing the occurrences of targets of direct assignments with their values. A direct assignment is an instruction of the form x = y, which simply assigns the value of y to x.From the following code:...
- Common subexpression eliminationCommon subexpression eliminationIn computer science, common subexpression elimination is a compiler optimization that searches for instances of identical expressions , and analyses whether it is worthwhile replacing them with a single variable holding the computed value.- Example :In the following code: a = b * c + g; d = b * c...
- Partial evaluationPartial evaluationIn computing, partial evaluation is a technique for several different types of program optimization by specialization. The most straightforward application is to produce new programs which run faster than the originals while being guaranteed to behave in the same way...