Constant folding
Type of compiler optimization
- 7 min read
- 4 chapters
Related on Lably
Through Compiler and Constant (computer programming)
It is often used together with constant propagation, which substitutes variables whose values are known to be constant. 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:
<span id="mwGg"></span><span class="n" id="mwGw">i</span><span class="w" id="mwHA"> </span><span class="o" id="mwHQ">=</span><span class="w" id="mwHg"> </span><span class="mi" id="mwHw">320</span><span class="w" id="mwIA"> </span><span class="o" id="mwIQ">*</span><span class="w" id="mwIg"> </span><span class="mi" id="mwIw">200</span><span class="w" id="mwJA"> </span><span class="o" id="mwJQ">*</span><span class="w" id="mwJg"> </span><span class="mi" id="mwJw">32</span><span class="p" id="mwKA">;</span>
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.)
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".
Sign in to keep reading
3 more chapters are free with a Lably account.
Constant folding and cross compilation
Cross compilers have 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:
<span id="mwPw"></span><span class="kt" id="mwQA">int</span><span class="w" id="mwQQ"> </span><span class="n" id="mwQg">x</span><span class="w" id="mwQw"> </span><span class="o" id="mwRA">=</span><span class="w" id="mwRQ"> </span><span class="mi" id="mwRg">14</span><span class="p" id="mwRw">;</span> <span class="kt" id="mwSA">int</span><span class="w" id="mwSQ"> </span><span class="n" id="mwSg">y</span><span class="w" id="mwSw"> </span><span class="o" id="mwTA">=</span><span class="w" id="mwTQ"> </span><span class="mi" id="mwTg">7</span><span class="w" id="mwTw"> </span><span class="o" id="mwUA">-</span><span class="w" id="mwUQ"> </span><span class="n" id="mwUg">x</span><span class="w" id="mwUw"> </span><span class="o" id="mwVA">/</span><span class="w" id="mwVQ"> </span><span class="mi" id="mwVg">2</span><span class="p" id="mwVw">;</span> <span class="k" id="mwWA">return</span><span class="w" id="mwWQ"> </span><span class="n" id="mwWg">y</span><span class="w" id="mwWw"> </span><span class="o" id="mwXA">*</span><span class="w" id="mwXQ"> </span><span class="p" id="mwXg">(</span><span class="mi" id="mwXw">28</span><span class="w" id="mwYA"> </span><span class="o" id="mwYQ">/</span><span class="w" id="mwYg"> </span><span class="n" id="mwYw">x</span><span class="w" id="mwZA"> </span><span class="o" id="mwZQ">+</span><span class="w" id="mwZg"> </span><span class="mi" id="mwZw">2</span><span class="p" id="mwaA">);</span>
Propagating x yields:
<span id="mwbA"></span><span class="kt" id="mwbQ">int</span><span class="w" id="mwbg"> </span><span class="n" id="mwbw">x</span><span class="w" id="mwcA"> </span><span class="o" id="mwcQ">=</span><span class="w" id="mwcg"> </span><span class="mi" id="mwcw">14</span><span class="p" id="mwdA">;</span> <span class="kt" id="mwdQ">int</span><span class="w" id="mwdg"> </span><span class="n" id="mwdw">y</span><span class="w" id="mweA"> </span><span class="o" id="mweQ">=</span><span class="w" id="mweg"> </span><span class="mi" id="mwew">7</span><span class="w" id="mwfA"> </span><span class="o" id="mwfQ">-</span><span class="w" id="mwfg"> </span><span class="mi" id="mwfw">14</span><span class="w" id="mwgA"> </span><span class="o" id="mwgQ">/</span><span class="w" id="mwgg"> </span><span class="mi" id="mwgw">2</span><span class="p" id="mwhA">;</span> <span class="k" id="mwhQ">return</span><span class="w" id="mwhg"> </span><span class="n" id="mwhw">y</span><span class="w" id="mwiA"> </span><span class="o" id="mwiQ">*</span><span class="w" id="mwig"> </span><span class="p" id="mwiw">(</span><span class="mi" id="mwjA">28</span><span class="w" id="mwjQ"> </span><span class="o" id="mwjg">/</span><span class="w" id="mwjw"> </span><span class="mi" id="mwkA">14</span><span class="w" id="mwkQ"> </span><span class="o" id="mwkg">+</span><span class="w" id="mwkw"> </span><span class="mi" id="mwlA">2</span><span class="p" id="mwlQ">);</span>
Continuing to propagate yields the following (which would likely be further optimized by dead-code elimination of both x and y.)
<span id="mwmg"></span><span class="kt" id="mwmw">int</span><span class="w" id="mwnA"> </span><span class="n" id="mwnQ">x</span><span class="w" id="mwng"> </span><span class="o" id="mwnw">=</span><span class="w" id="mwoA"> </span><span class="mi" id="mwoQ">14</span><span class="p" id="mwog">;</span> <span class="kt" id="mwow">int</span><span class="w" id="mwpA"> </span><span class="n" id="mwpQ">y</span><span class="w" id="mwpg"> </span><span class="o" id="mwpw">=</span><span class="w" id="mwqA"> </span><span class="mi" id="mwqQ">0</span><span class="p" id="mwqg">;</span> <span class="k" id="mwqw">return</span><span class="w" id="mwrA"> </span><span class="mi" id="mwrQ">0</span><span class="p" id="mwrg">;</span>
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:
<span id="mwtw"></span><span class="kt" id="mwuA">int</span><span class="w" id="mwuQ"> </span><span class="n" id="mwug">a</span><span class="w" id="mwuw"> </span><span class="o" id="mwvA">=</span><span class="w" id="mwvQ"> </span><span class="mi" id="mwvg">30</span><span class="p" id="mwvw">;</span> <span class="kt" id="mwwA">int</span><span class="w" id="mwwQ"> </span><span class="n" id="mwwg">b</span><span class="w" id="mwww"> </span><span class="o" id="mwxA">=</span><span class="w" id="mwxQ"> </span><span class="mi" id="mwxg">9</span><span class="w" id="mwxw"> </span><span class="o" id="mwyA">-</span><span class="w" id="mwyQ"> </span><span class="p" id="mwyg">(</span><span class="n" id="mwyw">a</span><span class="w" id="mwzA"> </span><span class="o" id="mwzQ">/</span><span class="w" id="mwzg"> </span><span class="mi" id="mwzw">5</span><span class="p" id="mw0A">);</span> <span class="kt" id="mw0Q">int</span><span class="w" id="mw0g"> </span><span class="n" id="mw0w">c</span><span class="w" id="mw1A"> </span><span class="o" id="mw1Q">=</span><span class="w" id="mw1g"> </span><span class="n" id="mw1w">b</span><span class="w" id="mw2A"> </span><span class="o" id="mw2Q">*</span><span class="w" id="mw2g"> </span><span class="mi" id="mw2w">4</span><span class="p" id="mw3A">;</span> <span class="k" id="mw3Q">if</span><span class="w" id="mw3g"> </span><span class="p" id="mw3w">(</span><span class="n" id="mw4A">c</span><span class="w" id="mw4Q"> </span><span class="o" id="mw4g">></span><span class="w" id="mw4w"> </span><span class="mi" id="mw5A">10</span><span class="p" id="mw5Q">)</span><span class="w" id="mw5g"> </span><span class="p" id="mw5w">{</span> <span class="w" id="mw6A"> </span><span class="n" id="mw6Q">c</span><span class="w" id="mw6g"> </span><span class="o" id="mw6w">=</span><span class="w" id="mw7A"> </span><span class="n" id="mw7Q">c</span><span class="w" id="mw7g"> </span><span class="o" id="mw7w">-</span><span class="w" id="mw8A"> </span><span class="mi" id="mw8Q">10</span><span class="p" id="mw8g">;</span> <span class="p" id="mw8w">}</span> <span class="k" id="mw9A">return</span><span class="w" id="mw9Q"> </span><span class="n" id="mw9g">c</span><span class="w" id="mw9w"> </span><span class="o" id="mw-A">*</span><span class="w" id="mw-Q"> </span><span class="p" id="mw-g">(</span><span class="mi" id="mw-w">60</span><span class="w" id="mw_A"> </span><span class="o" id="mw_Q">/</span><span class="w" id="mw_g"> </span><span class="n" id="mw_w">a</span><span class="p" id="mwAQA">);</span>Applying constant propagation once, followed by constant folding, yields:
<span id="mwAQQ"></span><span class="kt" id="mwAQU">int</span><span class="w" id="mwAQY"> </span><span class="n" id="mwAQc">a</span><span class="w" id="mwAQg"> </span><span class="o" id="mwAQk">=</span><span class="w" id="mwAQo"> </span><span class="mi" id="mwAQs">30</span><span class="p" id="mwAQw">;</span> <span class="kt" id="mwAQ0">int</span><span class="w" id="mwAQ4"> </span><span class="n" id="mwAQ8">b</span><span class="w" id="mwARA"> </span><span class="o" id="mwARE">=</span><span class="w" id="mwARI"> </span><span class="mi" id="mwARM">3</span><span class="p" id="mwARQ">;</span> <span class="kt" id="mwARU">int</span><span class="w" id="mwARY"> </span><span class="n" id="mwARc">c</span><span class="w" id="mwARg"> </span><span class="o" id="mwARk">=</span><span class="w" id="mwARo"> </span><span class="n" id="mwARs">b</span><span class="w" id="mwARw"> </span><span class="o" id="mwAR0">*</span><span class="w" id="mwAR4"> </span><span class="mi" id="mwAR8">4</span><span class="p" id="mwASA">;</span> <span class="k" id="mwASE">if</span><span class="w" id="mwASI"> </span><span class="p" id="mwASM">(</span><span class="n" id="mwASQ">c</span><span class="w" id="mwASU"> </span><span class="o" id="mwASY">></span><span class="w" id="mwASc"> </span><span class="mi" id="mwASg">10</span><span class="p" id="mwASk">)</span><span class="w" id="mwASo"> </span><span class="p" id="mwASs">{</span> <span class="w" id="mwASw"> </span><span class="n" id="mwAS0">c</span><span class="w" id="mwAS4"> </span><span class="o" id="mwAS8">=</span><span class="w" id="mwATA"> </span><span class="n" id="mwATE">c</span><span class="w" id="mwATI"> </span><span class="o" id="mwATM">-</span><span class="w" id="mwATQ"> </span><span class="mi" id="mwATU">10</span><span class="p" id="mwATY">;</span> <span class="p" id="mwATc">}</span> <span class="k" id="mwATg">return</span><span class="w" id="mwATk"> </span><span class="n" id="mwATo">c</span><span class="w" id="mwATs"> </span><span class="o" id="mwATw">*</span><span class="w" id="mwAT0"> </span><span class="mi" id="mwAT4">2</span><span class="p" id="mwAT8">;</span>Repeating both steps twice produces:
<span id="mwAUM"></span><span class="kt" id="mwAUQ">int</span><span class="w" id="mwAUU"> </span><span class="n" id="mwAUY">a</span><span class="w" id="mwAUc"> </span><span class="o" id="mwAUg">=</span><span class="w" id="mwAUk"> </span><span class="mi" id="mwAUo">30</span><span class="p" id="mwAUs">;</span> <span class="kt" id="mwAUw">int</span><span class="w" id="mwAU0"> </span><span class="n" id="mwAU4">b</span><span class="w" id="mwAU8"> </span><span class="o" id="mwAVA">=</span><span class="w" id="mwAVE"> </span><span class="mi" id="mwAVI">3</span><span class="p" id="mwAVM">;</span> <span class="kt" id="mwAVQ">int</span><span class="w" id="mwAVU"> </span><span class="n" id="mwAVY">c</span><span class="w" id="mwAVc"> </span><span class="o" id="mwAVg">=</span><span class="w" id="mwAVk"> </span><span class="mi" id="mwAVo">12</span><span class="p" id="mwAVs">;</span> <span class="k" id="mwAVw">if</span><span class="w" id="mwAV0"> </span><span class="p" id="mwAV4">(</span><span class="nb" id="mwAV8">true</span><span class="p" id="mwAWA">)</span><span class="w" id="mwAWE"> </span><span class="p" id="mwAWI">{</span> <span class="w" id="mwAWM"> </span><span class="n" id="mwAWQ">c</span><span class="w" id="mwAWU"> </span><span class="o" id="mwAWY">=</span><span class="w" id="mwAWc"> </span><span class="mi" id="mwAWg">2</span><span class="p" id="mwAWk">;</span> <span class="p" id="mwAWo">}</span> <span class="k" id="mwAWs">return</span><span class="w" id="mwAWw"> </span><span class="n" id="mwAW0">c</span><span class="w" id="mwAW4"> </span><span class="o" id="mwAW8">*</span><span class="w" id="mwAXA"> </span><span class="mi" id="mwAXE">2</span><span class="p" id="mwAXI">;</span>Having replaced all uses of variables a and b with constants, the compiler's dead-code elimination applies to those variables, leaving:
<span id="mwAXk"></span><span class="kt" id="mwAXo">int</span><span class="w" id="mwAXs"> </span><span class="n" id="mwAXw">c</span><span class="w" id="mwAX0"> </span><span class="o" id="mwAX4">=</span><span class="w" id="mwAX8"> </span><span class="mi" id="mwAYA">12</span><span class="p" id="mwAYE">;</span> <span class="n" id="mwAYI">c</span><span class="w" id="mwAYM"> </span><span class="o" id="mwAYQ">=</span><span class="w" id="mwAYU"> </span><span class="mi" id="mwAYY">2</span><span class="p" id="mwAYc">;</span> <span class="k" id="mwAYg">return</span><span class="w" id="mwAYk"> </span><span class="n" id="mwAYo">c</span><span class="w" id="mwAYs"> </span><span class="o" id="mwAYw">*</span><span class="w" id="mwAY0"> </span><span class="mi" id="mwAY4">2</span><span class="p" id="mwAY8">;</span>
(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, and removing the always-true conditional test. Thus, variable c becomes redundant, and only an operation on a constant remains:
<span id="mwAZw"></span><span class="k" id="mwAZ0">return</span><span class="w" id="mwAZ4"> </span><span class="mi" id="mwAZ8">4</span><span class="p" id="mwAaA">;</span>
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.