Optimization of Basic Blocks:

Optimization process can be applied on a basic block. While optimization, we don't need to change the set of expressions computed by the block.

There are two type of basic block optimization. These are as follows:

1. Structure-Preserving Transformations
2. Algebraic Transformations

1. Structure preserving transformations:

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

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

(a) Common sub-expression elimination:

In the common sub-expression, you don't need to be computed it over and over again. Instead of this you can compute it once and kept in store from where it's referenced when encountered again.

1. a : = b + c  
2. b : = a - d   
3. c : = b + c                          
4. d : = a - d  

In the above expression, the second and forth expression computed the same expression. So the block can be transformed as follows:

1. a : = b + c   
2. b : = a - d                                                         
3. c : = b + c  
4. d : = b  

(b) Dead-code elimination

• It is possible that a program contains a large amount of dead code.
• This can be caused when once declared and defined once and forget to remove them in this case they serve no purpose.
• Suppose the statement x:= y + z appears in a block and x is dead symbol that means it will never subsequently used. Then without changing the value of the basic block you can safely remove this statement.

(c) Renaming temporary variables

A statement t:= b + c can be changed to u:= b + c where t is a temporary variable and u is a new temporary variable. All the instance of t can be replaced with the u without changing the basic block value.

(d) Interchange of statement

Suppose a block has the following two adjacent statements:

1. t1 : = b + c   
2. t2 : = x + y  

These two statements can be interchanged without affecting the value of block when value of t1 does not affect the value of t2.

2. Algebraic transformations:

• In the algebraic transformation, we can change the set of expression into an algebraically equivalent set. Thus the expression x:= x + 0 or x:= x *1 can be eliminated from a basic block without changing the set of expression.
• Constant folding is a class of related optimization. Here at compile time, we evaluate constant expressions and replace the constant expression by their values. Thus the expression 5*2.7 would be replaced by13.5.
• Sometimes the unexpected common sub expression is generated by the relational operators like <=, >=, <, >, +, = etc.
• Sometimes associative expression is applied to expose common sub expression without changing the basic block value. if the source code has the assignments

1. a:= b + c  
2.                 e:= c +d +b  

The following intermediate code may be generated:

1. a:= b + c  
2.  t:= c +d  
3.  e:= t + b