In an SSA intermediate form where every name is assigned exactly once, what does a phi node at a control-flow merge do?

## The invariant SSA buys **Static single assignment (SSA)** is a discipline on an intermediate representation: **every name is the destination of exactly one instruction in the whole procedure**. It is achieved by renaming. Each time the source assigns to a variable, the renamer produces a fresh version — `x1`, `x2`, `x3` — and each read is rewritten to the version that reaches it. The payoff is stated in one line: **for any operand, the instruction that produced it is found by looking up the name, with no dataflow analysis to reconstruct it.** On a representation where names are reassigned, "what value does this read see?" depends on which paths reach this point and what each of them last wrote; it is an analysis. Under SSA it is a lookup. Every rewrite that has to know where a value came from — and most do — starts from cheaper ground. The word **static** matters. The rule is about the *program text*: one assignment per name in the code. It is not a claim about runtime. A loop body executes its instructions many times, and the storage behind a name is written on each iteration. ## Why merges need something extra Renaming works effortlessly along a straight line. It breaks at a **merge**: a block with more than one predecessor. ``` if cond: x = 1 else: x = 2 y = x + 1 ``` After renaming the branches, one holds `x1 = 1` and the other `x2 = 2`. The read in `y = x + 1` must see one of them, and which one is not known until the program runs. Three non-solutions: - name `x1` — wrong on the else path; - assign both branches into one name — breaks single assignment, which is the entire value of the form; - leave the read referring to "either" — then a name has no single definition and the lookup property is gone. ## The phi node The answer is a pseudo-instruction at the **head of the merge block**: ``` x3 = phi(x1 from L_then, x2 from L_else) ``` It defines exactly one new name, `x3`, and its operands are paired with the predecessor edges. Its meaning: *the value is the operand associated with the edge along which control actually arrived.* The single-assignment rule survives, and every use after the merge refers to `x3`. Properties worth knowing: - Phi nodes sit **at the top of a block**, before any ordinary instruction. - A block's phis are understood to take effect **together, on entry**, not one after another. Ordering them against each other would be meaningless, since they all read values from the predecessor. - A phi has **one operand per predecessor edge** — three predecessors, three operands. - Phis are needed only where two different definitions genuinely converge. Compilers place them by computing, for each definition, the blocks where its influence first meets another's, and repeating until the set stops growing. Inserting phis everywhere would be correct but wasteful. ## Leaving SSA No machine has a phi instruction. On the way down, the compiler **destroys SSA**: each phi is replaced by ordinary copies placed **on the incoming edges** — at the end of the then-block, copy `x1` into the location for `x3`; at the end of the else-block, copy `x2`. Every path then writes the merged location before reaching the merge, and no selection is needed at runtime. Many of those copies disappear when the versions end up sharing storage anyway. ## Limits — where the tidy story stops | Holds for | Not automatic for | |---|---| | Values held in SSA names | Locations reachable through more than one path, such as aliased memory | | Scalar quantities the compiler can rename freely | Storage whose identity is not known statically | This is the caveat a strong candidate volunteers. SSA's lookup property covers **the values that were renamed**. A store into a location that some other name might also reach cannot be renamed away by the same trick; compilers either keep such locations out of SSA or model memory itself with a parallel scheme. "SSA means you never have to do a dataflow analysis again" is too strong. ## What interviewers listen for The answer that lands states the invariant, shows why a merge forces the issue, gives a phi with edge-paired operands, and closes with the fact that phis are removed as copies rather than executed. A candidate who describes phi as a runtime test on which branch was taken has the mechanism backwards — that would cost a check the compiler has gone out of its way to avoid.