Optimization of Basic Blocks

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:
Structure-Preserving Transformations
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.

a : = b + c
b : = a - d
c : = b + c
d : = a - d a : = b + c b : = a - d c : = b + c d : = a - d

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

a : = b + c
b : = a - d
c : = b + c
d : = b a : = b + c b : = a - d c : = b + c 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:

t1 : = b + c
t2 : = x + y t1 : = b + c 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

a:= b + c
e:= c +d +b a:= b + c e:= c +d +b

The following intermediate code may be generated:

a:= b + c
t:= c +d
e:= t + b a:= b + c t:= c +d e:= t + b