Optimization of Basic Blocks in Compiler Design

Optimization of Basic Blocks

We can apply the optimization process on a basic block. While optimization, there is no need to change the set of expressions computed by the block.

The basic block optimization can be done in two ways:

• Structure-Preserving Transformations
• Algebraic Transformations

Structure-Preserving Transformations

The primary Structure-Preserving Transformation on basic blocks are as follows:

• Common sub-expression elimination
• Dead code elimination
• Renaming of temporary variables
• Interchange of two adjacent independent statements.

Common sub-expression elimination:

Suppose we have two expressions that compute the same values. In that case, we need to eliminate one of the expressions. This method is known as the common sub-expression elimination method.

Example:

 p = a + b
 q = c – d
 r = x+ y
 s = c - d 

This example shows that the second and fourth statements compute the same expression: c - d. So the basic block can be transformed as follows:

 p = a + b
 q = c - d
 r = x + y
 s = q 

Dead code elimination:

Whenever a programmer writes a program, there is a possibility that the program may have some dead code. These dead codes are the result of some expression in the program. Generally, a programmer doesn't introduce dead code intentionally. The dead code may be a variable or the result of some expression computed by the programmer that may not have any further uses. By eliminating these useless things from a code, the code will get optimized.

Example:

A statement p = q + r appears in a block, and p is a dead symbol. It means that it will never be used subsequently so that we can eliminate this statement. This elimination does not have any impact on the values of the basic block.

Renaming of temporary variables:

Consider the statement x = a + b

The given statement's value is stored in the temporary variable x that can be changed to another temporary variable y and changes all uses of x to y.

This kind of transformation is also known as a normal-form block.

Interchange of two independent adjacent statements:

Suppose we have two statements as follows:

                          p = a + b
                          q = x + y                 

The given statement can be interchanged without affecting the value of the block when the value of p does not affect the value of q.

Algebraic Transformations:

We can also optimized the basic blocks using algebraic identities. For example, we may apply arithmetic identities, such as

 x + 0 = 0 + x = x                  x , 0= x
  x * 1=1 * x = x                    x= 1 = x                     

Local reduction in strength is also another kind of algebraic transformation. In this optimization, a more expensive operator is replaced by a cheaper one.

EXPENSIVE                  CHEAPER

x^2                                        x * x

2 * x                                       x + x  

x/2                                           x * 0.5

The third class of optimizations is constant folding. In constant folding, the value of the constant expression is evaluated at compile-time, and their values replace constant expression. So, the expression 3 * 3 will be replaced by 9.

Sometimes unexpected common subexpression arose due to some relational operators like <, >, and =.           

The relational operators such as < and = sometimes generate unexpected common subexpressions.

Sometimes associative rule may be applied to expose common sub expression. If the source code has the assignments:

a = b + c;

e = c + d+ b;

Then, the intermediate code may be generated as the following:

a = b + c

t = c + d

e = t + b