Basic Blocks and Flow
Graphs (Unit IV)
What are Basic Blocks?
A basic block is like a straight road with no turns or stops—it’s a sequence of consecutive instructions in a program
where control enters only at the beginning and leaves only at the end, with no jumps or branches inside the block. Basic
blocks are used to simplify code analysis and optimization by breaking the program into manageable chunks.
Characteristics of a Basic Block:
Single Entry, Single Exit: Control enters at the first instruction and exits at the last.
No Internal Jumps: There are no jump instructions (e.g., goto, if) within the block, except possibly at the end.
Ends When:
A jump instruction is encountered (e.g., goto, if).
A label is encountered (since another part of the program might jump to it).
The program ends.
How to Identify Basic Blocks:
1. Leaders: The first instruction of a basic block is called a leader. Leaders are identified as:
The first instruction of the program.
Any instruction that is the target of a jump (e.g., a label).
Any instruction immediately following a jump or branch.
2. Block Construction: A basic block starts at a leader and includes all instructions until the next leader (exclusive).
Example:
Intermediate Code:
1: t1 = a + b
2: t2 = t1 * c
3: if t2 > 0 goto L1
4: x = 0
5: goto L2
L1:
6: x = 1
L2:
7: t3 = x + t2
Identify Leaders:
Instruction 1: First instruction (leader).
Instruction 3: Has a jump (goto L1), so the next instruction (4) is a leader.
Instruction 5: Has a jump (goto L2), so the next instruction (6) is a leader.
Instruction 6: Labeled L1 (target of a jump).
Instruction 7: Labeled L2 (target of a jump).
Basic Blocks:
B1: Instructions 1–3 (ends at goto L1).
t1 = a + b
t2 = t1 * c
if t2 > 0 goto L1
B2: Instructions 4–5 (starts after jump, ends at goto L2).
x = 0
goto L2
B3: Instruction 6 (starts at L1, ends before L2).
x = 1
B4: Instruction 7 (starts at L2).
t3 = x + t2
What is a Flow Graph?
A flow graph (or control flow graph, CFG) is like a map of a city showing how roads connect—it’s a directed graph where
each node represents a basic block, and each edge represents the flow of control between blocks. Flow graphs are used
to analyze the program’s control flow for optimizations like dead code elimination or loop optimization.
Constructing a Flow Graph:
Nodes: Each basic block is a node.
Edges: An edge from block B1 to block B2 exists if control can flow from B1 to B2:
B1 ends with a jump to a label in B2.
B2 immediately follows B1 and B1 does not end with an unconditional jump (e.g., goto).
Example (Using the Basic Blocks Above):
Basic Blocks:
B1: t1 = a + b; t2 = t1 * c; if t2 > 0 goto L1
B2: x = 0; goto L2
B3: x = 1 (at L1)
B4: t3 = x + t2 (at L2)
Flow Graph:
B1 → B2: If t2 <= 0, control flows to the next instruction (B2).
B1 → B3: If t2 > 0, jumps to L1 (B3).
B2 → B4: Unconditional jump to L2 (B4).
B3 → B4: B3 ends, control flows to the next block (B4).
Diagram:
[B1]
/ \
/ \
[B2] [B3]
\ /
\ /
[B4]
Applications of Basic Blocks and Flow
Graphs:
1. Optimization:
Within Basic Blocks: Apply local optimizations like constant folding (e.g., x = 2 + 3 → x = 5).
Across Blocks (Using Flow Graph): Perform global optimizations like common subexpression
elimination.
2. Data-Flow Analysis:
Analyze how data flows through the program (e.g., which variables are live at each point).
Example: In B1, t2 is live until the end; in B2, x is live.
3. Code Scheduling:
Reorder instructions within a basic block to improve parallelism.
4. Dead Code Elimination:
Use the flow graph to identify unreachable blocks (e.g., a block with no incoming edges).
Data-Flow Analysis Using Flow Graphs
Data-flow analysis examines how variables are defined and used across basic blocks to optimize code. For example:
Live Variable Analysis: Determine which variables are live (may be used later) at each point.
In B1, after t2 = t1 * c, t2 is live because it’s used in if t2 > 0.
In B2, x is live because it’s used in B4 (t3 = x + t2).
Reaching Definitions: Determine which definitions (assignments) reach a point.
The definition x = 0 in B2 reaches B4, as does x = 1 in B3.
Flowchart: Constructing Basic Blocks and
Flow Graphs
[Intermediate Code] → [Identify Leaders] → [Form Basic Blocks] →
[Create Nodes (Blocks)] → [Add Edges (Control Flow)] → [Flow Graph]
Quick Revision Box
Quick Revision: Basic Blocks & Flow Graphs
1. Basic Block: Single entry/exit (e.g., t1 = a + b; t2 = t1 * c).
2. Leaders: First instr, jump targets, after jumps.
3. Flow Graph: Nodes = blocks, edges = control flow.
4. Example: B1 → B2 (if false), B1 → B3 (if true).
5. Use: Optimization, data-flow analysis.
Sticky Note-Style Visual
Sticky Note: Basic Blocks & Flow Graphs
Block: t1 = a + b; t2 = t1 * c.
Leader: First instr or label (L1).
Flow: B1 → B2, B1 → B3.
Use: Optimize within/across blocks.
Summary
Basic blocks are sequences of instructions with a single entry and exit, identified by leaders (first instruction, jump
targets, or instructions after jumps). A flow graph represents these blocks as nodes, with edges showing control flow
(e.g., B1 → B2 if control flows naturally). They’re used for optimizations like constant folding within blocks and data-flow
analysis across blocks, helping improve code efficiency.
