Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edges

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Convert to SSA: x = a; x = x + 1. from Lesson 4.3
• Translate while (B) S into labels and jumps. from Lesson 4.2.3
• What is a cycle in a directed graph, and what is a DAG? from Lesson 0.2.4

1 · The Story

📖

Chapters and a chapter map

Ishaan wants to improve the draft piece by piece. Dev cuts the long stack of cards into chapters: a chapter is read straight through from its first card to its last, with no way to jump into its middle and no way to leave from its middle.

So a new chapter starts at the very first card, at every card that some detour jumps to, and at the card right after every detour (because a reader may continue there). Then Dev draws a chapter map: an arrow from chapter X to chapter Y if, after finishing X, a reader can go to Y, by a detour or simply by continuing.

Mrs. Desai frowns at the label “CFG” on the map. “At Kabir’s desk, CFG means his rulebook. Call this the flow map, so nobody mixes them up.”

2 · Predict First

🤔

A program has instructions 1–9 with jumps “3: if a < b goto 6”, “5: goto 7” and “8: if d > 10 goto 1”. Which instructions start a block? Write your guess down. The answer is in the vault.

3 · Core Concept

Basic blocks

A basic block is a maximal sequence of consecutive three-address instructions such that control enters only at the first instruction and leaves only after the last, with no jumps in between except possibly at the end.

Leader rules

The first instruction of each block is a leader:

• the first instruction of the program is a leader;
• any instruction that is the target of a conditional or unconditional jump is a leader;
• any instruction that immediately follows a conditional or unconditional jump is a leader.

Each block runs from a leader up to (not including) the next leader or the end of the program. (Edge cases: an instruction after a return or halt is also a leader; a call is normally treated as an ordinary instruction inside a block.)

Flow graphs

The flow graph (control flow graph) has the basic blocks as nodes and an edge B → C if C can immediately follow B in execution:

• the last instruction of B jumps (conditionally or not) to the leader of C; or
• C immediately follows B in program order and B does not end in an unconditional jump.

Often two extra nodes, entry and exit, are added. Unless a question says otherwise, count only edges between basic blocks.

The two meanings of “CFG”

Careful: CFG already means context-free grammar (Phase 2). In optimization texts, CFG also abbreviates control flow graph. These notes write “flow graph” for the second meaning; in a question, the context (blocks and edges vs productions) tells you which is meant.

Loops

An edge from a block to a block that appears earlier (one that every path to it passes through, the loop header) forms a loop. Inner loops and loop headers are where optimization pays off most (Phase 6).

Story → compiler term

4 · Visual

( 1) i = 1
( 2) j = 1
( 3) t1 = 10 * i
( 4) t2 = t1 + j
( 5) t3 = 8 * t2
( 6) t4 = t3 - 88
( 7) a[t4] = 0.0
( 8) j = j + 1
( 9) if j <= 10 goto (3)
(10) i = i + 1
(11) if i <= 10 goto (2)
(12) i = 1
(13) t5 = i - 1
(14) t6 = 88 * t5
(15) a[t6] = 1.0
(16) i = i + 1
(17) if i <= 10 goto (13)

6 basic blocks, 8 edges (computed from the leader rules).

5 · Worked Examples

Example 1 Easy

Find the leaders and basic blocks of the instructions 1–9 in the Predict question: 1 a = 1; 2 b = 2; 3 if a < b goto 6; 4 c = a + b; 5 goto 7; 6 c = a − b; 7 d = c * 2; 8 if d > 10 goto 1; 9 e = d.

Solution

5 basic blocks, 6 edges (computed from the leader rules).

Leaders 1, 4, 6, 7, 9; blocks B1 = 1–3, B2 = 4–5, B3 = 6, B4 = 7–8, B5 = 9. Edges: B1 → B2 (fall through), B1 → B3 (jump), B2 → B4 (goto 7), B3 → B4, B4 → B1 (back edge), B4 → B5. Dev’s chapters and chapter map.

Example 2 Medium

Partition the 17-instruction program above (it sets a 10 × 10 matrix to the identity) into basic blocks and count the edges.

Solution

Leaders: 1 (first), 2 and 3 and 13 (jump targets), 10 and 12 (after jumps). Blocks: B1 = 1–1, B2 = 2–2, B3 = 3–9, B4 = 10–11, B5 = 12–12, B6 = 13–17. Edges: 8, including the self-loops on B3 and B6 (each jumps back to its own leader).

Example 3 GATE

Generate code for i = 1; while (i <= n) { if (a[i] > m) m = a[i]; i = i + 1; } x = m; and count its basic blocks and edges.

Solution

( 1) i = 1
( 2) if i <= n goto (4)
( 3) goto (10)
( 4) t1 = a[i]
( 5) if t1 > m goto (7)
( 6) goto (8)
( 7) m = a[i]
( 8) i = i + 1
( 9) goto (2)
(10) x = m

8 basic blocks, 9 edges (computed from the leader rules).

8 blocks and 9 edges for this unoptimised jumping code. Questions usually give the code; apply the three leader rules mechanically.

6 · Shortcuts

⚡

Leaders in three sweeps: (1) mark instruction 1; (2) mark every jump target; (3) mark every instruction right after a jump. Blocks = number of leaders. Valid when: any partitioning question.

⚡

Edges: each block ending in a conditional jump has 2 successors (target and next); unconditional jump 1; no jump 1 (next); the last block 0 (unless it jumps). Valid when: counting flow-graph edges (no entry/exit nodes).

7 · GATE Traps

⚠️

• The instruction after a conditional jump is a leader, even though control may fall into it.
• The target of a jump is a leader, even if it is in the middle of an otherwise straight sequence.
• A block ending in an unconditional goto has no fall-through edge.
• A jump to its own block’s leader is a self-loop edge.
• CFG (context-free grammar) and CFG (control flow graph) are different things; read the context.
• Check whether entry/exit nodes and their edges are counted.

8 · Memory Hook

🧠

Leaders: First, Targets, After-jumps. “FTA” cuts the draft into chapters.

9 · Connect the Dots

Phase 4 is complete: the program is now three-address code in basic blocks connected by a flow graph. Before optimizing it, Phase 5 asks how the program’s data lives in memory while it runs: storage areas, function calls, visible names and parameters.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markBlocks

How many basic blocks does the code 1 a = 1; 2 b = 2; 3 if a < b goto 6; 4 c = a + b; 5 goto 7; 6 c = a − b; 7 d = c * 2; 8 if d > 10 goto 1; 9 e = d have?

Numerical answer: ________

Q2NAT2 marksEdges

How many flow-graph edges does the same code have (no entry/exit nodes)?

Numerical answer: ________

Q3MCQ1 markLeaders

Which is not a leader rule?

• (A) the first instruction
• (B) the target of a jump
• (C) the instruction after a jump
• (D) every assignment to a temporary

Q4NAT2 marksBlocks

The 17-instruction identity-matrix program of this lesson has how many basic blocks?

Numerical answer: ________

Q5MCQ1 markName clash

In the sentence “the optimizer builds the CFG of each function from its basic blocks”, CFG means:

• (A) context-free grammar
• (B) control flow graph
• (C) canonical finite grammar
• (D) compiler front end

11 · Rule Card

• Basic block: enter only at the first instruction, leave only after the last.
• Leaders: first instruction; jump targets; instructions after jumps (and after return/halt).
• Block = leader … before next leader.
• Flow graph edges: jump target, and fall-through unless the block ends in an unconditional jump.
• CFG = context-free grammar (parsing) vs control flow graph (optimization): read the context.

12 · Concept Ledger

basic blockleaderflow graph (control flow graph)successor / predecessor blockentry / exit nodeback edge (loop)

13 · Answer Vault