# 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,

a:= b+c

b:= a-d

c:= b+c

d:= a-d - The second and fourth statements compute the same expression, hence this basic block may transformed into the equivalent block

a:= b+c

b:= a-d

c:= b+c

d:= b - 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.

**Dead-code elimination**

- 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 a 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

t2:= x+y - 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.statement

**Algebraic transformation: Transformations on Basic Block**

- Countless algebraic transformation can used 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 by 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)

**Related Search**

Compiler Design, basic Blocks, Data Flow Properties, Free Study.

## Leave a Reply