Constant Folding - The Optimizations in Action

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;

Repeating both steps twice results in:

int a = 30; int b = 3; int c; c = 12; if (true) { c = 2; } 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:

int c; if (true) { c = 2; } return c * 2;

In above code, instead of True it could be 1 or any other Boolean construct depending on compiler framework. With traditional constant propagation we will get only this much optimization. It can't change structure of the program.

There is another similar optimization, called sparse conditional constant propagation, which selects the appropriate branch on the basis of if-condition. The compiler can now detect that the if statement will always evaluate to true, c itself can be eliminated, shrinking the code even further:

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 4 to eliminate unnecessary calls to the function, producing further performance gains.