Control-Flow Analysis
1. Purpose
Control-flow analysis (CFA) builds the control-flow graph (CFG): nodes = basic blocks (straight-line code, one entry/exit), edges = jumps/fall-through. All later optimizations walk the CFG.
2. Building CFG
1. find leaders (first stmt, jump targets, after-jump stmts)
2. blocks = leader..before-next-leader
3. edge B1→B2 if B1 ends with goto B2, ifFalse→B2 + fall-through, or falls into B2
Example:
L1: t1=a<b | ifFalse t1→L2 | t2=x+1 | x=t2 | goto L1 | L2: ...
→ B1(L1 test), B2(body), B3(L2 exit); edges B1→B2,B3; B2→B1
3. Uses
- Loops: back edge (target dominates source) → natural loop body.
- Dominators: A dominates B if all paths to B pass A (for motion/safety).
- Unreachable elim: blocks with no predecessor (except entry) deleted.
4. CFGs in SSA/Loop Opt
Loop headers, preheaders inserted here; data-flow equations iterate over CFG till fixpoint.
5. Exam Points
- Define basic block + build CFG from TAC — 7 marks, very frequent.
- Leaders algorithm steps — 5 marks, frequent.
- Dominators / back edges / loops — 3-5 marks, frequent.