Loading page…
Master the fundamental concepts of intermediate representation through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksBlock 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.
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.
cLoading…
Entry dominates A, B, C. A does not dominate B.
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.
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.
Compute dominators, immediate dominators, dominance frontiers and natural loops for a control-flow graph. Dominance frontiers are exactly where the next task will place φ-nodes; back edges are how compilers find loops.
One edge per line: FROM TO (block names are words). The entry is the first name in the input. Blocks are ordered by first appearance; every listing below uses that order.
A dominates B if every path from the entry to B passes through A (every block dominates itself).idom(B) is the dominator of B closest to it (other than B); the entry has none.DF(A) is the set of blocks B such that A dominates a predecessor of B but does not strictly dominate B.T → H where H dominates T. Its natural loop is H plus every block that can reach T without going through H.For each reachable block:
cLoading…
(idom=- for the entry). Then back edges: T->H ... in input order (or back edges: none), one line loop H <- T: {…} per back edge, and finally unreachable: … (or unreachable: none).
Input:
cLoading…
Output:
cLoading…
Dom(entry) = {entry}, every other Dom(n) starts as all blocks, then repeat Dom(n) = {n} ∪ ⋂ Dom(p) over the predecessors p until nothing changes. Bit sets make this cheap.idom from the sets, and the frontiers by walking up from each predecessor of a join block to its idom.Hidden tests cover nested loops, a loop with two back edges to one header, and an unreachable block.