What is the difference between constant folding and constant propogation? They both seem to do the same thing, instead of saving constants into stack or evaluating a full arithmetic expression, they simply replace it with the result which can be obtained at compile time. What is the difference between two?
Based on these two websites: http://www.compileroptimizations.com/category/constant_folding.htm and http://www.compileroptimizations.com/category/constant_propagation.htm
The difference is that constant propogation is not saving a variable to the stack, because we know its a constant (like
x = 10;) and can simply plug it in everywhere (say if you had an expression
y = x + x + x =>
y = 10 + 10 + 10) it is used in machine code. Whereas, constant folding is simply evaluating expressions that use constants and substituting the result into the machine code (like
y = 10 + 10 + 10; =>
y = 30;)
Constant propagation is entirely different.
What it does is gather information about the values of variables and propagates it to different locations in a program. For example, if you assign x = 5, then y = x, then z = y * 3, then a = x + y + z, and there are no assignments interfering with this, then constant propagation tells as that y = 5, z = 5 * 3 (which turns into z = 15 after constant folding), and a = 25.
Instead of just constant values, other values can be propagated. For example, after x = 5, y = x, z = y * 3, if (condition) z += y, we know that 15 <= z <= 20. Knowledge about ranges can remove overflow checks, can allow using faster instructions that can handle only smaller numbers, can remove comparisons like if (x <= 25) which will be true, can give hints whether loop unrolling should be done or should not be done etc.
In constant folding you only submit the result.
For example, in constant folding you turn
In contrast, in constant propagation, the constant replaces a variable. For example, given
int x=6; for(i=0;i<x;i++)
you simple replace the value of
x by the constant: