Add Phi-Nodes to Your SSA IR

Topic Overview

Phi-Nodes Merge Values at Joins

In SSA, each variable has one definition, but control flow merges multiple paths. Phi-nodes select the right value based on which predecessor block executed. LLVM's phi instruction and GCC's PHI_EXPR are everywhere in optimized IR.

Placement and Semantics

Insert phi at join blocks where different paths assign the same variable. x3 = phi(x1 from B1, x2 from B2) means x3 takes x1 if control came from B1, else x2 from B2.

cCopy
Loading…

• One phi operand per CFG predecessor
• Operands pair (value, label) in LLVM text form
• Place at dominance frontier of definitions
• Later passes copy-propagate through phi chains

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 add phi-nodes to your SSA IR at control-flow merge points. This exercise requires inserting phi instructions and wiring predecessor values so SSA form correctly represents variables across branches.

Your Task

Build full SSA form for code with branches and loops: place φ-nodes where values from different paths meet, then rename every definition and use. This is the algorithm of Cytron et al. that GCC and LLVM descend from, and it puts the previous three tasks together: basic blocks, dominance frontiers, and renaming.

Input

TAC with control flow, exactly as in Build a Control Flow Graph (CFG) from Your IR (copies, binary operations, labels, goto, if/ifFalse … goto, print a, return a). Build basic blocks and edges with that task's rules; ignore blocks unreachable from B0.

Algorithm (follow it exactly)

1. Dominators and frontiers of the reachable blocks, as in Implement Dominance Analysis on the CFG.
2. φ placement (minimal SSA). For each variable v, let Defs(v) be the blocks that assign v. Place a φ for v at every block in the iterated dominance frontier of Defs(v) (a block that receives a φ counts as a new definition site). This is minimal, not pruned, SSA: a φ can be dead.
3. Renaming. Every variable has a counter starting at 0; a definition takes the next number (v_1, v_2, …) and a use reads the current top of v's stack, with v_0 for a value that enters the program undefined. Visit blocks in dominator-tree preorder, children in block order. In each block: first give its φ's new versions, then rename the instructions in order (uses before the target, as in the SSA task), then fill in this block's argument in each successor's φs, then recurse into the dominator-tree children, and finally pop what the block pushed.

Output

For each reachable block:

cCopy
Loading…

• φs come first, ordered by the variable's first appearance in the program (reading each instruction's operands before its target). Arguments follow the block's predecessors in ascending block order.
• Labels are shown only in the block header; jump targets keep their label names.

Finish with phis=N.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Reuse your CFG and dominance code; add φ placement with a work list, and a recursive rename over the dominator tree with a stack of versions per variable.
2. Keep φ arguments indexed by predecessor so each edge fills exactly one slot.

Hidden tests cover a counting loop (with a dead φ for the loop condition's temporary), nested loops, a variable redefined on only one branch, and an unreachable block.