Constant folding

(See below for a dissenting article)

Constant folding is the optimization done by compilers in early stage of the compilation of a program. In C it is the optimization that makes it possible to have constant expressions in array-declarations, like:

#define WIDTH 320
#define HEIGHT 240
char buffer[WIDTH*HEIGHT];

Constant folding is similar to constant propagation, however constant folding must be done before the high-level language is translated to three-address-code to make code like above work. Constant propagation is done on the three-address-code (preferably on SSA form)

I would argue that the above is not quite correct. Although the above is an example of constant folding, the difference between constant folding and constant propagation is not the stage of the compiler during which they occur (both can occur at several stages), but actually what they do.

Constant folding is the process of simplifying expressions at compile-time which consist only of constants, which are usually simple literals like 2. An example is this:

 i = 320*200*32;

Most modern compilers would not generate two multiply instructions for this statement. Instead, they identify constructs like these, and compute their values at compile time, substituting them in, usually in the IR (intermediate representation) tree.

Constant folding and constant propagation can work together to effect many reductions of expressions by interleaving them repeatedly until no more changes are possible. Take this pseudocode for example:

 int x = 14;
 int y = 7 - x/2;
 return y*(28/x+2);

If we execute constant propagation on this, we obtain

 int x = 14;
 int y = 7 - 14/2;
 return y*(28/x+2);

If we execute constant folding on this, we get:

 int x = 14;
 int y = 0;
 return y*(28/x+2);

If we execute constant propagation on this, we get:

 int x = 14;
 int y = 0;
 return 0;

As noted by the previous author, sometimes constant folding must be done early so that expressions which can only contain constants, and not expressions, such as array initializers in C, can accept simple arithmetic expressions. However, this doesn't preclude doing it later again after constant propagation.