Editing Constant folding

{{Short description|Type of compiler optimization}}
'''Constant folding''' and '''constant propagation''' are related [[Optimizing compiler|compiler optimizations]] used by many modern [[compiler]]s.<ref name="MuchnickAssociates1997">{{cite book|author1=Steven Muchnick|author2=Muchnick and Associates|title=Advanced Compiler Design Implementation|url=https://archive.org/details/advancedcompiler00much|url-access=registration|quote=constant propagation OR constant folding.|date=15 August 1997|publisher=Morgan Kaufmann|isbn=978-1-55860-320-2}}</ref>  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 (programming)|constant]] expressions at [[compile time]] rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the [[integer literal]] <code>2</code>, but they may also be variables whose values are known at compile time. Consider the statement:

<syntaxhighlight lang="c">
i = 320 * 200 * 32;
</syntaxhighlight>

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

Constant folding can make use of arithmetic identities. If <code>x</code> is numeric, the value of <code>0 * x</code> is zero even if the compiler does not know the value of <code>x</code>. (Note that this is not valid for [[IEEE_754|IEEE floats]], since <code>x</code> could be Infinity or [[NaN]].)

Constant folding may apply to more than just numbers. Concatenation of [[string literal]]s and constant strings can be constant folded.  Code such as <code>"abc" + "def"</code> may be replaced with <code>"abcdef"</code>.

== 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 function]]s applied to constant values. Consider the following pseudocode:

<syntaxhighlight lang="c">
int x = 14;
int y = 7 - x / 2;
return y * (28 / x + 2);
</syntaxhighlight>

Propagating x yields:

<syntaxhighlight lang="c">
int x = 14;
int y = 7 - 14 / 2;
return y * (28 / 14 + 2);
</syntaxhighlight>

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

<syntaxhighlight lang="c">
int x = 14;
int y = 0;
return 0;
</syntaxhighlight>

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:

<syntaxhighlight lang="c">
int a = 30;
int b = 9 - (a / 5);
int c = b * 4;

if (c > 10) {
   c = c - 10;
}
return c * (60 / a);
</syntaxhighlight>

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

<syntaxhighlight lang="c">
int a = 30;
int b = 3;
int c = b * 4;

if (c > 10) {
   c = c - 10;
}
return c * 2;
</syntaxhighlight>

Repeating both steps twice produces:

<syntaxhighlight lang="c">
int a = 30;
int b = 3;
int c = 12;

if (true) {
   c = 2;
}
return c * 2;
</syntaxhighlight>

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

<syntaxhighlight lang="c">
int c = 12;

if (true) {
   c = 2;
}
return c * 2;
</syntaxhighlight>

(Boolean constructs vary among languages and compilers, but their details—such as the status, origin, and representation of [[Boolean data type|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,<ref>{{Citation |last1=Wegman |first1=Mark N |last2=Zadeck |first2=F. Kenneth |title=Constant Propagation with Conditional Branches |journal=ACM Transactions on Programming Languages and Systems |volume=13 |issue=2 |date=April 1991 |pages=181–210 |doi= 10.1145/103135.103136|citeseerx=10.1.1.130.3532 |s2cid=52813828 }}</ref> and removing the always-true conditional test. Thus, variable <code>c</code> becomes redundant, and only an operation on a constant remains:

<syntaxhighlight lang="c">
return 4;
</syntaxhighlight>

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

== See also ==
* [[Control-flow graph]]
* [[Use-define chain]] and [[SSA form]]
* [[Copy propagation]]
* [[Common subexpression elimination]]
* [[Partial evaluation]]

== References ==
{{Reflist}}

== Further reading ==
* {{Citation |last=Muchnick |first=Steven S. |title=Advanced Compiler Design and Implementation |year=1997 |publisher=Morgan Kaufmann |isbn=9781558603202 |url-access=registration |url=https://archive.org/details/advancedcompiler00much }}

{{Compiler optimizations}}

[[Category:Compiler optimizations]]