Why does constant propagation become dramatically simpler when the IR is in SSA form?
ASSA restricts programs to integer types, so all values are known statically at compile time
BEach use has exactly one reaching definition, so if x₃ = 5, every use of x₃ can immediately be replaced with 5 without any iterative dataflow analysis
CPhi functions pre-compute all possible values at control flow joins, making constants visible in a single pass
DSSA eliminates all conditional branches, so values are always statically determined
In conventional IR, determining which definition reaches a given use requires reaching-definitions dataflow analysis — an iterative algorithm that propagates sets of definitions through the control flow graph. In SSA, this is unnecessary: each variable name uniquely identifies its one and only definition. If x₃ = 5, every use of x₃ is definitively reached by that one assignment. Constant propagation reduces to a single lookup rather than a fixpoint computation. This is the core payoff of the SSA invariant — use-def chains are free.
Question 2 Multiple Choice
A program contains: if (cond) { x = 1; } else { x = 2; } followed by: y = x + 3. After converting to SSA form, what appears at the join point after the if-else?
ATwo separate assignments x = 1 and x = 2 are duplicated at the join point and resolved by runtime branching
BA phi function x₃ = φ(x₁, x₂) is placed at the join point, which resolves to x₁ or x₂ depending on which branch was taken
CA merged assignment x₃ = (x₁ + x₂) / 2 representing the average of both branches
DThe variable x is left undefined at the join point; SSA requires the programmer to initialize it before use
Control flow joins are exactly where SSA's phi functions are needed. After the if-branch assigns x₁ = 1 and the else-branch assigns x₂ = 2, subsequent code needs a way to refer to 'the value of x, whichever branch was taken.' The phi function x₃ = φ(x₁, x₂) is SSA's solution: it is a definitional device that takes the value of whichever argument corresponds to the actual execution path. The subsequent use y = x₃ + 3 then has exactly one reaching definition. Phi functions are not runtime instructions — they encode the join semantics in the IR structure.
Question 3 True / False
Phi functions in SSA form are real instructions that execute at runtime to select between multiple possible values.
TTrue
FFalse
Answer: False
Phi functions are a conceptual device in the IR — they exist only during compilation, not at runtime. During final code generation, SSA destruction replaces each phi function with copy instructions inserted at the ends of predecessor blocks: x₃ = φ(x₁, x₂) becomes 'copy x₁ into x₃' at the end of the left predecessor and 'copy x₂ into x₃' at the end of the right predecessor. Register allocation then coalesces these copies where possible. Treating phi functions as runtime instructions is a misconception; they are analysis artifacts that make the dataflow structure explicit.
Question 4 True / False
In SSA form, any given variable name may appear on the left-hand side of at most one assignment anywhere in the entire function.
TTrue
FFalse
Answer: True
This is the defining invariant of SSA — 'static single assignment.' Each original variable x is renamed into a family of versioned names x₁, x₂, x₃, ... where each version is assigned exactly once. A definition site for x₃ appears exactly once in the program; every use of x₃ refers to that one definition. This unique-definition property is what makes use-def chains trivially available (follow the name back to its one assignment site) and what enables the optimization benefits.
Question 5 Short Answer
Explain why phi functions are necessary in SSA form and how the dominance frontier determines where they are placed.
Think about your answer, then reveal below.
Model answer: Phi functions are needed wherever two control flow paths merge and bring different versions of the same variable. Without them, a join point would have ambiguous reaching definitions — violating SSA's invariant. A phi function x₃ = φ(x₁, x₂) resolves the ambiguity by explicitly merging the two versions. Phi functions are placed at dominance frontiers: a block B is in the dominance frontier of block D if D dominates a predecessor of B but does not strictly dominate B itself. Intuitively, the dominance frontier of a definition site is the set of blocks where that definition first 'competes' with other reaching definitions — precisely where merging is needed.
The dominance frontier placement ensures phi functions are inserted neither too early (wasting memory and computation) nor too late (leaving ambiguous uses). A definition at block D dominates all blocks it reaches exclusively; the moment another path brings a different definition to the same block, a phi function is required there. Algorithms like Cytron's efficient SSA construction algorithm use the dominance tree and iterated dominance frontiers to insert exactly the right phi functions — no more, no less.