Basic Blocks, Control Flow Graphs, DAGs & Loop Optimizations
“Leader identification algorithm, CFG construction, DAG value numbering, and loop-invariant hoisting.”
1.The Control Flow & Optimization Engine
§ 5.1.Machine-independent optimization operates on Intermediate Representations before physical hardware instructions are selected.
Basic Blocks: A Basic Block is a sequence of consecutive three-address instructions in which flow of control enters exclusively at the first instruction and leaves exclusively at the last instruction without possibility of branching except at the end.
Control Flow Graphs (CFG): Directed graph G = (V, E) where vertices V are basic blocks and directed edges E represent potential control transfers. An edge exists from B_1 to B_2 if B_2 can execute immediately after B_1.
DAG Representation of a Basic Block:
- Nodes are labeled with operators or variable names.
- Constructed by scanning instructions in order: before creating an operator node, the compiler checks if a node with the same operator and children already exists. If so, the existing node is reused (Common Subexpression Elimination).
- Dead code elimination: Nodes with no outgoing edges and no associated active variables at block exit are discarded.
Loop Optimizations:
A Natural Loop has a single entry point (the header) which dominates all nodes in the loop, and at least one back-edge returning to the header.
- Loop-Invariant Code Motion: Computes expressions outside the loop if all operands are defined outside or invariant.
- Strength Reduction: Replaces multiplication with repeated addition.
- Loop Unrolling: Replicates the loop body to decrease branch penalty cycles and instruction test overhead.
2. Worked Analysis: Leader Identification & CFG Partitioning
Every instruction immediately following a conditional or unconditional branch is a leader.
Problem Statement (Modeled on GATE Pattern):
Consider the following intermediate code snippet:
(1) i = 1
(2) s = 0
(3) t1 = i * 4
(4) t2 = A[t1]
(5) s = s + t2
(6) i = i + 1
(7) if i <= 100 goto (3)
(8) t3 = s * 2
(9) if t3 > 500 goto (12)
(10) print "Normal"
(11) goto (13)
(12) print "High"
(13) halt
Identify all leaders, partition the code into basic blocks, and determine the number of basic blocks.
Step 1: Apply Leader Identification Rules:
- Rule 1 (First instruction): Instruction (1) is a leader.
- Rule 2 (Targets of jumps):
- Target of jump at (7) is (3) -> (3) is a leader.
- Target of jump at (9) is (12) -> (12) is a leader.
- Target of jump at (11) is (13) -> (13) is a leader.
- Rule 3 (Instructions immediately following jumps):
- Follows jump at (7) -> (8) is a leader.
- Follows jump at (9) -> (10) is a leader.
- Follows jump at (11) -> (12) is a leader (already identified).
Set of Leaders = {1, 3, 8, 10, 12, 13}.
Step 2: Partition into Basic Blocks:
- Block B1: Instructions (1) to (2) [from leader 1 up to next leader 3]
- Block B2: Instructions (3) to (7) [from leader 3 up to next leader 8]
- Block B3: Instructions (8) to (9) [from leader 8 up to next leader 10]
- Block B4: Instructions (10) to (11) [from leader 10 up to next leader 12]
- Block B5: Instruction (12) [from leader 12 up to next leader 13]
- Block B6: Instruction (13) [from leader 13 to end]
Conclusion: There are exactly 6 Basic Blocks in this program.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused with worked FIRST/FOLLOW and LR parsing table numericals.
Exam-oriented explanations of ambiguous grammars and parser conflicts.
University-depth treatment of the full compiler pipeline — build a real compiler.