Basic blocks and control flow graphs

Why it exists

Most optimisation and code generation work on straight-line code: sequences of instructions that are always executed from the first to the last. A long program is first cut into such pieces, the basic blocks, and the possible transfers of control between them are drawn as a graph, the control flow graph (CFG). Local optimisation works inside one block; global optimisation and data flow analysis work on the whole graph (data flow framework).

Prerequisites

You need three-address code with jumps (three-address code), as produced by control-flow translation.

Precise definitions

Basic block. A maximal sequence of consecutive three-address instructions such that (1) control can enter only at the first instruction (there is no jump into the middle), and (2) control leaves only at the last instruction, without halting or branching in the middle, except possibly at the last. If the first instruction of a block is executed, all the others are executed in order.

Leaders. The first instruction of each basic block. They are found by three rules:

1. The first instruction of the program is a leader.
2. Any instruction that is the target of a conditional or unconditional jump is a leader.
3. Any instruction that immediately follows a conditional or unconditional jump is a leader.

Each leader starts a block that extends up to, but not including, the next leader (or to the end of the program). A leader found by two rules is a leader once, so the number of blocks equals the number of distinct leaders.

Control flow graph. The nodes are the basic blocks. There is a directed edge from block B to block C if C can immediately follow B in some execution, that is:

• the last instruction of B is a conditional or unconditional jump to the first instruction of C; or
• C immediately follows B in the program text and B does not end in an unconditional jump (goto).

A block that ends in a conditional jump has two successors (the target and the next block); a block that ends in goto has one; a block that ends in neither has one (the next block). Textbooks often add an entry node (with an edge to the first block) and an exit node (reached from blocks that end the program); the count of edges in a question may or may not include them, so read the statement.

Loops. A node $d$ dominates a node $n$ if every path from the entry to $n$ passes through $d$ (every node dominates itself). An edge $n \to h$ is a back edge if $h$ dominates $n$. The natural loop of a back edge $n \to h$ is $h$ together with all nodes that can reach $n$ without passing through $h$; $h$ is the header. A loop is where the program spends most of its time, so optimisations such as loop-invariant code motion concentrate on loops.

How it works

The animation finds the leaders of a program with two nested loops (a typical double loop that fills a matrix) rule by rule, then the blocks, then the edges. Watch which rule makes each instruction a leader: instruction 2 is the target of the jump in instruction 11 (the end of the outer loop), instruction 3 the target of the jump in 9 (the inner loop), 10 and 12 follow jumps, and 13 is the target of the jump in 17. Instruction 1 is a leader by rule 1. That gives six blocks and eight edges. The inner loop is the block B3 with an edge to itself, and the outer loop is B2, B3, B4.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The jump instructions and labels come from control-flow translation; the instructions inside a block are rewritten by local optimisation and described by a DAG; the graph is the framework of data flow analysis. The notion of a basic block also underlies pipelining and branch hazards at the hardware level.

PYQs

Consider the following grammar:
            stmt    → if expr then expr else expr; stmt|O`
            expr    →  term relop term | term
            term    →  id | number
             id        →  a | b |  c
           number  → [0-9]

where relop is a relational operator (e.g., <, >, ...),
O ` refers to the empty statement, and if, then, else
are terminals.

Consider a program P following the above
grammar containing ten if terminals. The number
of control flow paths in P is ________. For
example, the program

 if e1 then e2 else e3

has 2 control flow paths, e1  → e2 and e1  → e3

Refer to the given 3-address code sequence. This
code sequence is split into basic blocks. The
number of basic blocks is _________.

1001: i = 1

1002: j = 1

1003: t1 = 10*i

1004: t2 = t1+j

1005: t3 = 8*t2

1006: t4 = t3-88

1007: a[t4] = 0.0

1008: j = j+1

1009: if j <= 10 goto 1003

1010: i = i+1

1011: if i <= 10 goto 1002

1012: i = 1

1013: t5 = i-1

1014: t6 = 88*t5

1015: a[t6] = 1.0

1016: i = i+1

1017: if i <= 10 goto 1013

Consider the following pseudo-code.

L1 : t1 = -1

L2 : t2 = 0

L3 : t3 = 0

L4 : t4 = 4 * t3

L5 : t5 = 4 * t2

L6 : t6 = t5 * M

L7 : t7 = t4 + t6

L8 : t8 = a[t7]

L9 : if t8 <= max goto L11

L10 : t1 = t8

L11 : t3 = t3 + 1

L12 : if t3 < M goto L4

L13 : t2 = t2 + 1

L14 : if t2 < N goto L3

L15 : max = t1
Which of the following options CORRECTLY
specifies the number of basic blocks and the number
of
instructions
in
the
largest
basic
block,
respectively?

COMPILER DESIGN

In the context of abstract-syntax-tree (AST) and
control-flow-graph (CFG), which one of the
following is TRUE?

COMPILER DESIGN

Consider the intermediate code given below.

(1) i = 1

(2) j = 1

(3) t1 = 5 * i

(4) t2 = t1 + j

(5) t3 = 4 * t2

(6) t4 = t3

(7) a[t4] = –1

(8) j = j + 1

(9) if j < = 5 goto (3)

(10) i = i + 1

(11) if i < 5 goto (2)

The number of nodes and edges in the control-flow-
graph constructed for the above code, respectively,
are:-

Self-check

Revision card

References