Transformations on Basic Block
Again Freestudy9 comes with new post related to Transformations on Basic Block.
- A number of transformations can be applied to a basic block without changing the set of expressions computed by the block.
- Many of these transformations are useful for improving the quality of the code.
- There are two important classes of local transformations that can be applied to the basic block. These are,
1. Structure preserving transformation.
2. Algebraic transformation.
Structure Preserving Transformation Structure
The primary structure-preserving transformations on basic blocks are, transformations
Common sub-expression elimination.expression
- Consider the basic block,
- The second and fourth statements compute the same expression, hence this basic block may transform into the equivalent block.
- Although the 1st and 3rd statements in both cases appear to have the same expression on the right, the second statement redefines b.
- Therefore, the value of b in the 3rd statement is different from the value of b in the 1st, and the 1st and 3rd statements do not compute the same expression.
- Suppose x is dead, that is, never subsequently used, at the point where the statement x:=y+z appears in a basic block. Then this statement may be safely removed without changing the value of the basic block.
Renaming of Temporary Variables
- Suppose we have a statement t:=b+c, where t is temporary. If we change this statement to u:= b+c, where u is a new temporary variable, and change all uses of this instance of t to u, then the value of the basic block is not changed.
- In fact, we can always transform a basic block into an equivalent block in which each statement that defines a temporary defines a new temporary. We call such a basic block a normal-form block.
Interchange of Two Independent Adjacent Statements
- Suppose we have a block with the two adjacent statements,
- t1:= b+c
- Then we can interchange the two statements without affecting the value of the block if and only if neither x nor y is t1 and neither b nor c is t2. A normal -form basic block permits all statement interchanges that are possible.
Algebraic Transformation: Transformations on Basic Block
- Countless algebraic transformation can use to change the set of expression algebraic computed by the basic block into an algebraically equivalent set.
- The useful ones are those that simplify expressions or replace expensive operation with a cheaper one.
- Example: x=x+0 or x=x+1 can be eliminated.
Flow Graph (Transformations on Basic Block)
- A graph representation of three-address statements called a flow graph is useful graphs, for understanding code-generation algorithms.
- Nodes in the flow graph represent computations, and the edges represent the flow of control.
- Example of flow graph for following three address code,
(1) prod=0 (2) i=1 (3) t1 := 4*i (4) t2 := a [ t1 ] (5) t3 := 4*i (6) t4 :=b [ t3 ] (7) t5 := t2*t4 (8) t6 := prod +t5 (9) prod := t6 (10) t7 := i+1 (11) i := t7 (12) if i<=20 goto (3)