Implement Dominance Analysis on the CFG

Dominators Structure the CFG

Block A dominates B if every path from entry to B passes through A. Dominance is foundational for SSA phi placement, loop detection, and LICM. Lengauer-Tarjan computes dominators efficiently; LLVM's DominanceInfo wraps this for every pass.

Computing Dominators

Entry dominates all blocks. Iteratively refine: dom(B) = {B} ∪ ∩ dom(P) for predecessors P of B. The immediate dominator (idom) forms a tree. A dominates B but not strictly if A equals B.

cCopy
Loading…

Entry dominates A, B, C. A does not dominate B.

• Strict dominators exclude the block itself
• idom(B) is the closest strict dominator of B
• Dominance frontiers guide phi insertion
• Back edges in the CFG often indicate loops

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement dominance analysis on your CFG. This exercise asks you to compute dominator sets or the immediate dominator tree for each basic block, enabling SSA construction and loop analyses.