SSA Form

The core of SSA is that each value name has only one static definition, with uses explicitly associated with that definition. "Static" is important: the same instruction in a loop can be executed dynamically many times, producing different results each time, and still conform to SSA.

SSA improves the representation of data dependencies; it does not automatically eliminate all loop analysis requirements, nor does it require infinite physical registers or that memory can only be written once.

How to represent reassignment in branches at merge points

In a normal program, x is set to 1, then possibly set to 2 depending on a condition, and finally x is used. After converting to SSA, the two assignments use different names, and a φ definition is added at the merge point to select the input based on the incoming predecessor edge.

define i32 @choose(i1 %cond) {
entry:
  br i1 %cond, label %left, label %right
left:
  br label %merge
right:
  br label %merge
merge:
  %x = phi i32 [ 2, %left ], [ 1, %right ]
  %y = add i32 %x, 1
  ret i32 %y
}

φ does not evaluate both inputs simultaneously and then check the condition; rather, it is a value selection associated with the actual control flow edge. In this example, it returns 3 or 2. It can exist as an IR instruction, but the target ISA does not need to have a machine instruction with the same name.

Dominance: Is a definition necessarily visible to its uses?

Block A dominates B if every path from the entry to B passes through A. For standard SSA usage, a definition should dominate its uses; within the same block, definitions must precede uses. φ inputs are checked against uses on their corresponding predecessor edges.

The immediate dominance relationship forms a tree on entry-reachable blocks, where each non-entry node has exactly one immediate dominator. A merge node in the CFG can have multiple predecessors, but it will not have two parent nodes in the dominator tree. Labeling a diamond-shaped CFG directly as a dominator tree confuses these two structures.

φ in loops: Connecting initial values with back-edge values

define i32 @count_to(i32 %n) {
entry:
  br label %header
header:
  %i = phi i32 [ 0, %entry ], [ %next, %body ]
  %more = icmp slt i32 %i, %n
  br i1 %more, label %body, label %exit
body:
  %next = add i32 %i, 1
  br label %header
exit:
  ret i32 %i
}

On the first entry to header, it selects 0; subsequently, returning from body, it selects next from the previous iteration. Definitions and uses may form cycles in the text or dependency graph; this does not violate SSA. Therefore, fixed-point analyses do not necessarily become single-pass just because SSA is used.

How the same static name produces multiple dynamic results when n=2

In the text, %i has only one φ definition, and %next has only one add definition; the table records three dynamic arrivals of the same program, introducing no conflicting static definitions. If n=0 or negative, the first comparison exits and returns 0, with no body → header back-edge executions.

Putting the two IR snippets from choose and count_to into the same file ssa.ll, you can first run opt -passes=verify -disable-output ssa.ll. Then, use the following C driver to observe the two branches and zero/multiple loop iterations:

/* ssa-main.c: clang ssa.ll ssa-main.c -o ssa-demo */
extern int choose(_Bool);
extern int count_to(int);
int main(void) {
    return choose(1) != 3 || choose(0) != 2 ||
           count_to(-1) != 0 || count_to(0) != 0 || count_to(2) != 2;
}

If you keep the CFG body → header back-edge but remove [ %next, %body ] from the φ for %i, the verifier should reject it: φ inputs must correspond to the predecessor structure. If %next is used directly as a normal value in entry, its definition does not dominate that use, which should also be rejected. The verifier proves that the IR structure satisfies the rules, not that the frontend has correctly expressed the source program's intent. LLVM φ Rules

How does one phi receive the initial and back-edge values?

Separate static instruction identity from dynamic visit number. There is always one definition of %i; the selected header visit determines whether phi takes the entry value or the preceding iteration’s result. At i=n the run compares and exits without computing another next.

Dominance Frontier: Where merge points need selection for a definition's influence

DF(X) = {Y | X dominates some predecessor of Y, but X does not strictly dominate Y}.

"Non-strict dominance" allows cases where Y=X in certain loops, so the dominance frontier cannot always be interpreted as the first node completely outside X's dominance region.

The classic construction starts from the definition block of a variable, inserts φs iteratively on the dominance frontier, and the new φ blocks act as definitions for further propagation. Pruned SSA further avoids inserting useless φs by leveraging variable liveness at entry points. This does not mean inserting a φ at every merge point for all variables.

Renaming: Maintaining current versions along the dominator tree

Maintain a version stack for each source variable; create a version for φ results upon entering a block; when scanning normal instructions, first replace uses with the current version, then create a version for the new definition; when leaving the block to process successor edges, fill in the corresponding φ inputs; after recursively processing dominator tree children, pop the versions pushed by the current block.

Uninitialized uses must be determined by source language semantics or frontend error handling; you cannot arbitrarily fill 0 just to make SSA pass. Unreachable blocks also need cleanup or independent handling according to algorithm conventions.

General CFGs, including irreducible control flow, can also have SSA constructed; it is not required to first convert all loops into single-entry natural loops. Some subsequent loop optimizations may require a reduced form, but that is a separate issue.

Which incoming path creates a dominance frontier?

“Does not strictly dominate” is weaker than “does not dominate.” With M’s self-loop, M dominates predecessor M but not strictly itself, so M∈DF(M). In the diamond, selecting L or R shows how the other branch prevents domination of M. Colors come from computed dominator sets; the CFG is not a dominator tree.

$$\mathrm{DF}(X)=\{Y\mid \exists P\in \mathrm{pred}(Y):X\mathrm{dom}P\wedge \neg (X\mathrm{sdom}Y)\}$$

Destruction: φ produces parallel copies on edges

When there are multiple φ inputs on a predecessor edge, they can be understood as simultaneous assignments to the result locations. For example, after location allocation, if a←b and b←a are needed, sequential execution would lose one old value; a temporary location or a proper swap sequence must be used.

For critical edges where a predecessor has multiple successors and a successor has multiple predecessors, copies cannot be unconditionally placed at the end of the predecessor or the beginning of the successor; this is often handled by splitting edges to create execution locations specific to that path.

φ inputs coming from different predecessors do not prove that they are never simultaneously active throughout the program. The source values may still be used elsewhere, so sharing physical locations requires interference and copy coalescing checks; you cannot unconditionally merge all values of a φ into a single register.

A set of swap copies must read the same old state

The old values of locations a and b are 10 and 20, respectively, and the target parallel copy is a←b, b←a. After the first sequential copy, a has become 20; if the second copy reads a again, it will get the new value, resulting in both being 20. The role of the temporary location is to preserve the old value that was overwritten early.

old = {"a": 10, "b": 20}
expected = {"a": old["b"], "b": old["a"]}
wrong = old.copy()
wrong["a"] = wrong["b"]
wrong["b"] = wrong["a"]
assert wrong == {"a": 20, "b": 20} and wrong != expected

actual = old.copy()
temporary = actual["a"]
actual["a"] = actual["b"]
actual["b"] = temporary
assert actual == expected

This problem occurs after mapping SSA values to reusable physical locations; it is not saying that SSA itself allows reassigning the same name. General parallel copies may have acyclic chains and multiple cycles: arrange copies that do not destroy other old inputs first, and introduce temporary locations when encountering cycles; only when swapping two items can you directly use this three-step template.

Copies cannot simply be moved to the end of P, otherwise P→X would also execute them; nor can they be placed at the entry of M, otherwise Q→M would also execute the copy from P. After splitting the edge, the φ predecessor for M must be updated from P to the new block, not just changing the jump target.

Can a later copy still read an overwritten old value?

The overwritten entities are reusable locations, not SSA names. All target RHS operands refer to one old state. Actions preserve visible current values and recent writes. Try two direct copies, reset, then use a temporary to locate the loss precisely. Saving too late merely preserves an already overwritten value.

SSA values coexisting with mutable memory

LLVM's %p = alloca i32 defines the pointer value only once, after which memory can be stored to multiple times; each load produces a new SSA value. SSA constrains named values, not turning the entire heap into immutable data.

mem2reg converts suitable local slots to SSA values and φs; aliasing, address escaping, and unsupported accesses affect promotion. The frontend can first use alloca to express mutable local variables and then hand them over to the promotion process, avoiding the need to immediately implement full SSA construction. LLVM Mutable Variables Tutorial

Verification Checklist

Check for unique definitions, types, dominance relationships, correspondence between φs and predecessor edges, terminator instructions, and handling of unreachable blocks. When modifying the CFG, also update φ inputs; deleting an edge while keeping the corresponding input breaks the IR.

Related chapters: LLVM IR in Practice, Data Flow Analysis, Register Allocation.

References

• LLVM Language Reference.
• LLVM: Mutable Variables.

Keywords: SSA, phi, dominator, dominance frontier, renaming, parallel copy, critical edge, mem2reg