8.1 Basic Blocks, Flow Graphs & Control Flow Analysis

Back to DBMS Notes

📚Module 01Basic Blocks, Flow Graphs & Control Flow Analysis⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Train Stations and Railway Track Network

Imagine a high-speed railway transit network:

• Instruction Stream: A single continuous stretch of track.
• Basic Block (The Non-Stop Express Run): A straight segment of railway track between two stations with zero switches, zero junctions, and zero siding tracks. If a train passes the entry signal, it is physically impossible for it to derail or turn off until it reaches the final station. It executes strictly all-or-nothing.
• Leader (The Station Platform): The very first point where a train can enter the straight track.
• Control Flow Graph (CFG): The global schematic map of the entire railway network, showing every junction, switch, loop, and bypass connecting these straight express segments.

💻 Bridging to Computer Science: Leader Identification and Control Flow Graph Topology

In code optimization and target code generation:

• A flat linear stream of Three-Address Code is partitioned into maximal straight-line sequences called Basic Blocks.
• Within a basic block, execution is strictly sequential: if the first instruction executes, all subsequent instructions are guaranteed to execute in order.
• By abstracting instructions into basic blocks and representing jumps as directed edges, the compiler constructs a Control Flow Graph (CFG).
• Analyzing the CFG allows the compiler to detect loops, compute dominators, and trace live variable ranges for register allocation.

📑Table of Contents

• 🏗️ Architectural Foundations: Linear Stream vs Control Flow Graph
• 📐 Formal Foundations: Basic Blocks & Leader Identification
  • 🎯 The 3 Leader Identification Rules
• 🏗️ Architecture & Execution Mechanics: Constructing the Control Flow Graph
  • 🚦 Conditions for a Directed Edge Between Basic Blocks
• 👑 Dominators, Dominator Trees & Natural Loops
  • 1️⃣ The Dominator Relation (dom)
  • 2️⃣ Immediate Dominator (idom)
  • 3️⃣ Back Edges & Natural Loops
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Rigorous Leader Identification & Block Partitioning
  • Example 2: Dominator Analysis on a Multi-Path Flow Graph
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: Linear Stream vs Control Flow Graph

Linear Instruction Stream vs Control Flow Graph (CFG)

Transforming flat assembly into a structured mathematical graph

Flat Stream

Linear Instruction Stream

📜

Dominant Architecture / DomainRaw Three-Address Code, Assembly Files

• •Unstructured sequential array of instructions with arbitrary goto jumps.
• •Difficult to reason about variable lifetimes and loop boundaries.
• •High risk of instruction reordering bugs due to hidden jump targets.
• •Poor platform for automated global optimizations.

"Linear text conceals the topological structure of program execution."

CFG

Control Flow Graph (CFG)

🕸️

Dominant Architecture / DomainModern Optimizers, LLVM, GCC, HotSpot JIT

• •Nodes are atomic basic blocks; edges represent permissible branch transitions.
• •Clear demarcation of loop headers, preheaders, and exit blocks.
• •Enables rigorous dataflow analysis (liveness, reaching definitions).
• •Directly supports dominator tree construction and SSA form.

"Exposing control topology unlocks mathematical optimization algorithms."

---

📐 Formal Foundations: Basic Blocks & Leader Identification

A Basic Block is a maximal sequence of consecutive three-address instructions satisfying two strict properties:

1. Single Entry: Control enters the sequence only through the first instruction. There is no instruction inside the block (other than the first) that can be the target of a jump from anywhere in the program.
2. Single Exit: Control leaves the sequence without halting or branching except possibly at the very last instruction of the block.

🎯 The 3 Leader Identification Rules

To partition any three-address instruction stream into basic blocks, the compiler first identifies all Leaders (the initial instruction of each basic block):

Architecture Flow

The 3 Canonical Leader Identification Rules

Determining the entry points of all atomic basic blocks

🏁Rule 1

Program Origin

The very first instruction of the three-address program is ALWAYS a leader.

→

Scan Code

🎯Rule 2

Branch Targets

Any instruction that is the TARGET of a conditional or unconditional jump is a leader.

→

Scan Jumps

⚡Rule 3

Post-Branch Fallthrough

Any instruction immediately FOLLOWING a conditional or unconditional jump is a leader.

Formal Algorithm: Partitioning into Basic Blocks

1. Find Leaders: Apply Rules 1, 2, and 3 across all instructions in the program.
2. Form Blocks: For each leader instruction $L_i$:
   • Its basic block consists of $L_i$ and all subsequent instructions up to, but not including, the next leader $L_{i+1}$ (or the end of the program).

---

🏗️ Architecture & Execution Mechanics: Constructing the Control Flow Graph

Once basic blocks are identified, the compiler constructs a directed graph $G = (V, E)$, called the Control Flow Graph (CFG):

• Vertices ($V$): The set of basic blocks $B_1, B_2, \dots, B_k$, augmented with two virtual nodes: ENTRY and EXIT.
• Directed Edges ($E$): A directed edge $B_i \to B_j$ exists if and only if control can pass from the last instruction of $B_i$ to the first instruction of $B_j$.

🚦 Conditions for a Directed Edge Between Basic Blocks

An edge $B_i \to B_j$ exists if either of the following holds:

1. Explicit Branch: The last instruction of $B_i$ is a conditional or unconditional jump targeting the first instruction (the leader) of $B_j$.
2. Fallthrough: $B_j$ immediately follows $B_i$ in physical program order, and $B_i$ does NOT end in an unconditional jump (goto).

---

👑 Dominators, Dominator Trees & Natural Loops

Control flow optimization requires identifying loops mechanically from arbitrary flow graphs.

1️⃣ The Dominator Relation (dom)

A node $d$ dominates a node $n$ (written $d \text{ dom } n$) if every path from the ENTRY node to $n$ in the CFG must pass through $d$.

Mathematical Properties:

• Reflexive: Every node dominates itself ($n \text{ dom } n$).
• Transitive: If $a \text{ dom } b$ and $b \text{ dom } c$, then $a \text{ dom } c$.
• Antisymmetric: If $a \text{ dom } b$ and $b \text{ dom } a$, then $a = b$.

2️⃣ Immediate Dominator (idom)

The Immediate Dominator of node $n$ (denoted $idom(n)$) is the unique strict dominator of $n$ that is dominated by all other strict dominators of $n$. The tree formed by edges $idom(n) \to n$ is the Dominator Tree.

3️⃣ Back Edges & Natural Loops

📖Formal Definition: Back Edges & Natural Loopsdefinition

$$\text{Back Edge}(A \to B) \iff B \text{ dom } A \quad \text{($B$ is the Loop Header)}$$$$\text{Natural Loop}(A \to B) = \{ n \mid B \text{ dom } n \land \exists \text{ path } n \rightsquigarrow A \text{ avoiding } B \}$$

• The node $B$ is the Loop Header (the single entry point to the loop).
• Identifying back edges is the formal mechanism compilers use to find all reducible loops for loop-invariant code motion and loop unrolling.

---

🏭 Real-World Production Context: How Industry Builds This

In modern industrial production compilers (such as LLVM and GCC):

In the LLVM Compiler Infrastructure:

• A function (llvm::Function) is physically stored as an ilist of llvm::BasicBlock objects.
• Every BasicBlock must end with a mandatory Terminator Instruction (BranchInst, ReturnInst, or SwitchInst).
• Fallthroughs are explicitly represented as unconditional branches (br label %next_bb).
• This guarantees that basic blocks cannot be malformed during optimization passes.

Engineers can inspect compiler control flow by generating Graphviz diagrams directly:

opt -dot-cfg input.ll
dot -Tpng cfg.func.dot -o cfg.png

This renders basic blocks, branch conditions, and loop headers as interactive SVG/PNG graphs.

---

📐 Numerical Applications & Worked Examples

Example 1: Rigorous Leader Identification & Block Partitioning

Consider the following three-address code representing dot-product calculation:

(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)
(13) return prod

Identify:

1. All leader instructions with explicit rule justifications.
2. The complete set of basic blocks.
3. The transition adjacency list for the Control Flow Graph.

Step-by-Step Analytical Solution:

Step 1: Leader Identification

• Instruction (1): Leader by Rule 1 (first instruction of the program).
• Instruction (3): Leader by Rule 2 (target of conditional jump at instruction 12: goto (3)).
• Instruction (13): Leader by Rule 3 (instruction immediately following conditional jump at instruction 12).

No other jump statements exist in the program. Therefore, the leaders are:

$$\text{Leaders} = \{ 1, 3, 13 \}$$

Step 2: Basic Block Partitioning

• Block $B_1$ (Leader 1 up to before Leader 3):
  • Instructions (1) to (2):

    (1) prod = 0
    (2) i = 1

• Block $B_2$ (Leader 3 up to before Leader 13):
  • Instructions (3) to (12):

    (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)

• Block $B_3$ (Leader 13 to end of program):
  • Instruction (13):

    (13) return prod

Step 3: CFG Adjacency Transitions

• From $B_1$: Control falls through unconditionally to $B_2$.
  • Edge: $B_1 \to B_2$.
• From $B_2$:
  • If condition $i \le 20$ is true: jumps to instruction (3) (head of $B_2$).
  • If condition is false: falls through to instruction (13) (head of $B_3$).
  • Edges: $B_2 \to B_2$ (self-loop) and $B_2 \to B_3$.
• From $B_3$: Program terminates.
  • Edge: $B_3 \to \text{EXIT}$.

---

Example 2: Dominator Analysis on a Multi-Path Flow Graph

Consider a CFG with nodes $\{1, 2, 3, 4, 5, 6, 7, 8\}$ and initial entry node $1$:

• Edges:
  • $1 \to 2, 1 \to 3$
  • $2 \to 4$
  • $3 \to 4, 3 \to 5$
  • $4 \to 6$
  • $5 \to 6$
  • $6 \to 7$
  • $7 \to 8, 7 \to 3$

Determine:

1. The dominator set $\text{Dom}(n)$ for each node.
2. The Immediate Dominator $idom(n)$ for each node.
3. Identify whether edge $7 \to 3$ is a back edge.

Step-by-Step Analytical Trace:

Step 1: Compute Dominator Sets

Node $n$	Paths from Entry ($1$) to $n$	Dominator Set $\text{Dom}(n)$
1	$[1]$	$\{1\}$
2	$[1, 2]$	$\{1, 2\}$
3	$[1, 3]$, $[1, 2, 4, 6, 7, 3]$	$\{1, 3\}$
4	$[1, 2, 4]$, $[1, 3, 4]$	$\{1, 4\}$
5	$[1, 3, 5]$	$\{1, 3, 5\}$
6	$[1, 2, 4, 6]$, $[1, 3, 5, 6]$	$\{1, 6\}$
7	All paths pass through 6	$\{1, 6, 7\}$
8	All paths pass through 7	$\{1, 6, 7, 8\}$

Notice that node 4 can be reached via 2 or 3. Hence neither 2 nor 3 dominates 4. Only 1 and 4 dominate node 4.

Step 2: Immediate Dominators

• $idom(2) = 1$
• $idom(3) = 1$
• $idom(4) = 1$
• $idom(5) = 3$
• $idom(6) = 1$
• $idom(7) = 6$
• $idom(8) = 7$

Step 3: Back Edge Evaluation

• Consider edge $7 \to 3$:
  • By definition, $7 \to 3$ is a back edge if and only if $3 \text{ dom } 7$.
  • However, $\text{Dom}(7) = \{1, 6, 7\}$. Node 3 is NOT in $\text{Dom}(7)$!
  • Why? Because path $1 \to 2 \to 4 \to 6 \to 7$ bypasses node 3 completely!
  • Therefore, $7 \to 3$ is NOT a back edge, and the cycle is an irreducible cycle.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why is the instruction immediately following a conditional or unconditional jump guaranteed to be a leader?"
Key Focus Points:

• Rule 3 Logic: A basic block has a single exit. Since a jump instruction represents an exit from the current block, the next instruction cannot be executed as part of that same straight-line sequence.
• It represents the fallthrough target (for conditional jumps) or the start of a new block reached by another jump, and must therefore begin a new basic block.

Question 2: "What is the exact definition of a natural loop in terms of dominators?"
Key Focus Points:

• A natural loop is defined by a back edge $A \to B$ where $B \text{ dom } A$.
• The natural loop consists of $B$ (the loop header) plus all nodes that can reach $A$ through a path that does not pass through $B$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Forgetting Rule 3 and merging post-jump instructions.
Answer: Critical partitioning error. Failing to apply Rule 3 erroneously combines the instruction following a jump into the preceding basic block, giving the block multiple exits or internal jump targets and corrupting subsequent optimization passes.

Trap 2: Assuming every cycle in a CFG is a natural loop.
Answer: False. A cycle is only a natural loop if it has a unique entry point (a single loop header that dominates all nodes in the cycle). Cycles with multiple entry points are irreducible flow graphs and do not possess a single back edge.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic7.3 Control Flow Translation, Boolean Expressions & BackpatchingNext Topic →8.2 Principal Sources of Code Optimization: Local, Global & Loop