7
$\begingroup$

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?

$\endgroup$
1
7
$\begingroup$

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;)

$\endgroup$
2
  • 1
    $\begingroup$ Other than there's no reason stacks and machine code need to be involved (you can do these as source-to-source translations for example), yes, this is the distinction. Constant propagation just replaces a bound variable with the constant expression it's bound to, while constant folding evaluates a (side-effect free) expression where all inputs are compile-time constants. $\endgroup$ – Derek Elkins left SE Aug 7 '17 at 22:44
  • $\begingroup$ @DerekElkins yeah, the no side effects part is an importnat note $\endgroup$ – nikolaevra Aug 9 '17 at 1:06
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

In constant folding you only submit the result. For example, in constant folding you turn y=3+4 into y=7.

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:

for(i=0;i<6;i++)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.