Constant Folding and Constant Propagation in Compiler Design

In this article, we discuss two compiler optimizations (Constant Folding and Constant Propagation) which enable the compiler to produce high performance and efficient assembly code.

Table of contents:

1. Constant Folding
2. Constant propagation
3. Need for optimization

Pre-requisites:

• Different phases of Compiler
• Different Code Optimizations in Compiler Design

Constant Folding

This is an optimization technique which eliminates expressions that calculate a value that can be determined before code execution.

If operands are known at compile time, then the compiler performs the operations statically.

An Example,

1. int x = (2 + 3) * y → int x = 5 * y
2. int z = 300 * 78 * 6 → int z = 140400

Compilers will not go ahead and generate two symbols addition and multiplication in the first case or two multiplication symbols in the second case but instead will identify such constructs and substitute the computed values as shown.

Optimizations are commonly applied at the intermediate representation phase (4th phase in the compiler).

Constant folding is applicable for boolean values, integers with the exception of a division by zero and floating points.

Constant propagation

This is the substitution of values of known constants and expressions.
That is, if the value of a variable is known to be a constant, then the compiler will replace its use by that constant.

The value of the variable is propagated forward from the point of assignment.

An example,
int x = 5;
int y = x * 2;
int z = a[y];

optimize...
int y = 5 * 2;
int z = a[y];

optimize...
int y = 10;
int z = a[y];

optimize...
int z = a[10];

This will enable the code to assign static values which is faster than a lookup and copying of a variable value.

It saves time by eliminating the need for an assignment of a value that it itself will be subsequently only used to propagate that value through out the code.

For more efficiency constant folding is interleaved with constant propagation.

An example,
Consider the pseudocode.

int func(){
    int a = 30;
    int b = 9 - a / 5;
    int c;

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

Apply constant propagation once followed by constant folding and the result is,

int funct(){
    int a = 30;
    int b = 3;
    int c;

    c = b * 4;
    if (c > 10) {
        c = c - 10;
    }
    return c * 2;
}

a and b have been simplified to constants and their values substituted on all occurrences.

Dead code elimination is applied to discard them thus optimizing the code further.

int func(){
    int c;
    c = 12;
    if (12 > 10) {
        c = 2;
    }
    return c * 2;
}

If the statement is always true, the compiler will eliminate c thus shrinking the code even further.

int func(){
    return 4;
}

This could be further optimized by taking advantage of knowing that it evaluates to the constant integer 4, thus unnecessary calls to the function are eliminated.

Need for optimization

• Code written by programmers is not optimal.
• Architectural independence.
• Improves execution speed.
• Reduced memory need.
• Low power consumption.
• Code locality.
• Avoid redundancy in computations.
• Fewer lines of code means less resources required

Other compiler optimization techniques include

• Dead code elimination - elimination of unused expressions or statements.
• Copy propagation - After assignment of one variable to another, a reference to one variable is replaced with the value of another variable.
• Tail call elimination - If a function ends by calling another function, the compiler will reuse the caller stack frame for the function being called.
• Algebraic simplification - constant folding that takes advantage of mathematical simplification rules.
• Inlining - Replacing the call to a function with the function body.

Criteria for code optimization

• The optimizations should be simple enough to have good effect.
• Algorithms implemented should not be modified.
• Both optimized and unoptimized versions of a program should maintain semantic equivalence.
• The optimizations should end up speeding up execution.

With this article, you must have the complete idea of Constant Folding and Constant Propagation in Compiler Design.