|
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. A diagram of the operation of an ideal compiler. ...
Compiler optimization techniques are optimization techniques that have been programmed into a compiler. ...
Sparse conditional constant propagation is an optimization frequently utilized in compilers after conversion to static single assignment form (SSA). ...
In computer programming, dead code typically consists of blocks of programming instructions or entire routines that will never be accessed because all calls to them have been removed, or code that cannot be reached because it is guarded by a control structure that must always transfer control somewhere else. ...
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: In mathematics and the mathematical sciences, a constant is a fixed, but possibly unspecified, value. ...
In computer science, compile time, as opposed to runtime, is the time when a compiler compiles code written in a programming language into an executable form. ...
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. The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a standardized imperative computer programming language developed in the early 1970s by Ken Thompson and Dennis Ritchie for use on the...
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. In their most general meanings, the terms front end and back end refer to the initial and the end stages of a process flow. ...
In computer science, three address code is a form of representing intermediate code used by compilers to aid in the implementation of code-improving transformations. ...
In their most general meanings, the terms front end and back end refer to the initial and the end stages of a process flow. ...
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: In compiler theory, an intrinsic function is a function available in a given language whose implementation is handled specially by the compiler. ...
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: Dead code elimination is a technique used in computer science to reduce program size by removing code which can never be executed. ...
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: In formal logic, mathematics and computer science, Boolean algebras, or Boolean lattices, are algebraic structures which capture the essence of the logical operations AND, OR and NOT as well as the corresponding set-theoretic operations intersection, union and complement. ...
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 -32 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 | 
Feeds |
Contact