Basic Blocks, Flow

Graphs
Flow Graphs
• A flow graph is a graphical depiction of a sequence of instructions
• A flow graph can be defined at the intermediate code level or target
code level
Example

MOV 0,R0
MOV 1,R0 MOV n,R1
MOV n,R1 JMP L2
JMP L2 L1: MUL 2,R0
L1: MUL 2,R0 SUB 1,R1
SUB 1,R1 L2: JMPNZ R1,L1
L2: JMPNZ R1,L1
Basic Blocks
• A basic block is a sequence of consecutive statements in which flow of
control enters at the beginning and leaves at the end without halt or
possibility of branching except at the end (with natural flow or a
branch instruction)
• The basic blocks become the nodes of a flow graph, whose edges
indicate which blocks can follow which other blocks.

4
Basic blocks and flow graphs
• Graph representation of 3-address statement – flow graph
• Nodes in the graph – Computations
• Edges in the graph – Flow of control
• Useful for optimization, register allocation
Basic Blocks & Control Flow Graph
• A control flow graph (CFG) is a directed graph with basic blocks Bi as
vertices and with edges BiBj iff Bj can be executed immediately after
Bi

6
Partition Algorithm for Basic Blocks
Input: A sequence of three-address statements
Output: A list of the basic blocks for that sequence in which each instruction is
assigned to exactly one basic block.

1. Determine the set of leaders, the first statements if basic blocks

a) The first statement is the leader
b) Any statement that is the target of a conditional or unconditional jump
is a leader
c) Any statement that immediately follows a conditional or unconditional
jump is a leader
2. For each leader, its basic block consist of the leader and all statements up to
but not including the next leader or the end of the program
7
Example
MOV 1,R0
MOV 1,R0 MOV n,R1
MOV n,R1 JMP L2
JMP L2
L1: MUL 2,R0 L1: MUL 2,R0
SUB 1,R1 SUB 1,R1
L2: JMPNZ R1,L1 L2: JMPNZ R1,L1
Successor and Predecessor Blocks
• Suppose the flow graph has an edge B1B2
• B1 is a predecessor of B2 and B2 is a successor of B1

MOV 1,R0
MOV n,R1
JMP L2
L1: MUL 2,R0
SUB 1,R1
L2: JMPNZ R1,L1
10
 Example
Begin 1. prod := 0
prod := 0 2. i := 1
3. t1 := 4 * i
i := 1;
4. t2 := a[t1]
do begin 5. t3 := 4 * i
prod : = prod + a[i] * b[i]; 6. t4 := b [t3]
i = i +1; 7. t5 := t2 *t4
end 8. t6 := prod + t5
while i < = 20 9. prod := t6
10. t7 := i+1
end
11. i := t7
12. If i <= 20 goto (3)
Identifying leaders
• (1) is the beginning – hence leader
• (3) is the target of a jump – hence leader
• Lines (1) and (2) is a basic block
• Statement following (12) is a leader
• Statements (3) to (12) is another basic block
 Control flow graph
B1 1. prod := 0
2. i := 1

B2 3. t1 := 4 * I
B1 is the
4. t2 := a[t1]
predecessor of
5. t3 := 4 * I
B2 and B2 is
6. t4 := b [t3]
the successor
7. t5 := t2 *t4
of B1
8. t6 := prod + t5
9. prod := t6
10. t7 := i+1
11. i := t7
12. If i <= 20 goto (3)
Loops
• A loop is a collection of basic blocks, such that
• All blocks in the collection are strongly connected – any node to any other
there is a path of length one or more within the loop
• The collection has a unique entry, and the only way to reach a block in the
loop is through the entry

17
Outer & Inner loops
• Loops not containing any other loop is Inner loop
• Loops that has one or more inner loops is outer loop
Loops (Example)

B1: MOV 1,R0 Strongly connected

MOV n,R1 components:
JMP L2
B2: L1: MUL 2,R0 SCC={{B2,B3}, {B4} }
SUB 1,R1
B3: L2: JMPNZ R1,L1 Entries:
B3, B4
B4: L3: ADD 2,R2
SUB 1,R0
JMPNZ R0,L3
19
Transformations on Basic blocks
• Basic block computes set of expressions
• Values of the variables outside the block is decided by the
computation inside the block
• Two basic blocks are equivalent if they compute the same set of
expressions
Equivalence of Basic Blocks
• Two basic blocks are equivalent if they compute the same set of
expressions

b := 0
t1 := a + b
t2 := c * t1 a := c * a
a := t2 b := 0

a := c*a a := c*a
b := 0 b := 0
21
Transformation on Basic Blocks
• A code-improving transformation is a code optimization to improve
speed or reduce code size
• Global transformations are performed across basic blocks
• Local transformations are only performed on single basic blocks
• Transformations must be safe and preserve the meaning of the code
• A local transformation is safe if the transformed basic block is guaranteed to
be equivalent to its original form
Transformations on Basic blocks
• Structure-Preserving Transformation
• Syntactic structure of the statements in the basic blocks are not altered
• Algebraic Transformation
• Mathematical identity based transformation and thus altering the syntactic
structure
Transformations on Basic blocks
• Structure-Preserving Transformation
• Common Sub-expression Elimination
• Dead-code elimination
• Renaming of temporary variables
• Interchange of two independent adjacent statements
Common-Subexpression Elimination
• Remove redundant computations

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

t1 := b * c t1 := b * c
t2 := a - t1 t2 := a - t1
t3 := b * c t4 := t2 + t1
t4 := t2 + t3
Dead Code Elimination
• Remove unused statements

b := a + 1 b := a + 1
a := b + c …
… Assuming a is dead (not used)

if true goto L2

b := x + y Remove unreachable code

…
Renaming Temporary Variables
• Temporary variables that are dead at the end of a block can be safely
renamed

t1 := b + c t1 := b + c
t2 := a - t1 t2 := a - t1
t1 := t1 * d t3 := t1 * d
d := t2 + t1 d := t2 + t3
Interchange of Statements
• Independent statements can be reordered
• In this example, neither t1 or d is t2, nor a or t1 is t3

t1 := b + c t1 := b + c
t2 := a - t1 t3 := t1 * d
t3 := t1 * d t2 := a - t1
d := t2 + t3 d := t2 + t3
Algebraic Transformations
• Change arithmetic operations to transform blocks to algebraic
equivalent forms

t1 := a - a t1 := 0
t2 := b + t1 t2 := b
t3 := 2 * t2 t3 := t2 << 1
x := y ** 2 x := y * y

29
Summary
• Converting code to Basic blocks
• Possible transformations in basic blocks