Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 61 ยท Intermediate Code and Optimization

Static Single Assignment

Understand SSA form: phi functions, dominators, dominance frontiers and renaming, with a runnable Python SSA construction for a loop.

In ordinary code a variable such as x can be assigned many times, so the question "which assignment gave x its value here?" needs a data-flow analysis to answer. Static single assignment (SSA) form removes the question. In SSA every variable is assigned exactly once in the program text. If the source assigns x three times, the compiler creates three names, such as x1, x2 and x3. Each use of a name then points to exactly one definition.

SSA is the main intermediate form inside LLVM, GCC, the JVM's HotSpot compilers, V8 and many others. This lesson explains how code is converted to SSA, why joins need a special phi function, and how dominators and dominance frontiers decide where the phi functions go. The code at the end builds SSA for a loop from scratch.

Renaming straight-line code

In a single basic block there is nothing difficult. Give every assignment a fresh name, and rewrite each later use to the latest name:

TEXT
x = 1            x1 = 1
y = x + 2        y1 = x1 + 2
x = y * 3   ->   x2 = y1 * 3
z = x + y        z1 = x2 + y1

The old x and the new x were really two different values that happened to share a name. After renaming they are distinct, and the optimizer sees that x1 is dead after y1 is computed.

Python Renaming a basic block into SSA

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last lines show a benefit. To find constants in non-SSA code you track which assignment is current and forget facts when a variable changes. In SSA the dictionary known is only ever extended, never invalidated, so one pass over the code finds all constants of a straight-line block. Real compilers use the same property for sparse constant propagation across whole functions.

The problem at a join: phi functions

Branches break the simple renaming scheme. Look at this diamond:

flowchart TD
    A["entry<br/>if c"] --> B["then<br/>x = 1"]
    A --> C["else<br/>x = 2"]
    B --> D["join<br/>print x"]
    C --> D

Two definitions of x meet at the join. Which name should print use?

If the branches become x1 = 1 and x2 = 2, the print in the join block cannot name just one of them, because the right one depends on the path taken at run time. SSA solves this with a pseudo-instruction called a phi function at the start of the join block:

TEXT
join:
    x3 = phi(x1, x2)     # x1 if we came from "then", x2 if from "else"
    print x3

phi does not exist in machine code. It is notation that says "this value is whichever argument belongs to the predecessor we arrived from". Each argument is tied to one incoming edge. When the compiler leaves SSA before code generation, it replaces a phi with copy instructions at the end of the predecessors, and a register allocator often removes most of those copies again.

Where do phi functions go?

You could put a phi for every variable at every join, but that bloats the code. The goal is a minimal set: a phi for x only where two different definitions of x can actually meet. Two graph concepts find those places.

Dominators. A block D dominates block N if every path from the entry to N goes through D. Every block dominates itself. Among the strict dominators of N, the closest one is its immediate dominator (idom), and the idoms form the dominator tree. The entry is the root. If you have not seen them yet, they are introduced with control flow graphs.

Dominance frontier. The dominance frontier DF(D) is the set of blocks N where D's dominance just stops: D dominates a predecessor of N but does not strictly dominate N itself. Intuitively, it is the first place where a path that went through D can merge with a path that did not. A definition in D is the only definition in force inside the region D dominates, but at DF(D) it may meet another one. So a definition of x in block D requires a phi for x at every block in DF(D).

A phi is itself a definition, so it may require more phis at its own frontier. The construction repeats until nothing new is added, like a worklist. In the diamond, DF(then) = DF(else) = {join}, and that is exactly where the phi appears.

flowchart TD
    E["entry<br/>i = 0; s = 0"] --> H["head<br/>t = i #lt; 10"]
    H --> BD["body<br/>s = s + i; i = i + 1"]
    BD --> H
    H --> X["exit<br/>print s"]

A loop. The body dominates nothing past itself, and its frontier is the loop head, so i and s need phi functions there.

Renaming with the dominator tree

After the phi functions are placed (with no arguments yet), a second pass renames everything. Walk the dominator tree from the entry, keeping a stack of current names for each original variable:

  1. On entering a block, give each of its phi functions a fresh name and push it.
  2. For each ordinary instruction, replace the uses with the top of the stack for each variable, then give the assigned variable a fresh name and push it.
  3. For every CFG successor, fill in the phi argument that belongs to this block with the current top-of-stack name.
  4. Recurse into the children in the dominator tree.
  5. On leaving, pop every name that this block pushed.

The stacks work because dominance matches scoping: inside a block's region of the dominator tree, the latest definition seen on the way down is the one that reaches. When the walk returns, the definitions of that region go out of scope.

Building SSA for a loop

The program below implements all the steps: iterative dominators, immediate dominators and the dominator tree, dominance frontiers, phi placement with a worklist, and renaming. It uses semi-pruned SSA: it only considers variables that are read in a block before being assigned there. The temporary t, which is created and used in one block, never needs a phi.

Python SSA construction: dominance frontiers, phis and renaming

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The dominance frontier of head is head itself, because the loop's back edge makes the head a join point that head does not strictly dominate. body also has the frontier . Hence i and s get a phi at head, and nowhere else. In the printed result, i2 = phi(i1, i3) means: on entry from entry the value is i1 (zero), and when we come around the loop from body it is i3, the incremented value. The exit block reads s2, the loop head's version, because the loop condition is evaluated before the exit is taken.

Note how the data-flow facts of the previous lesson are now visible in the names. A reader sees at once that body reads s2 and i2, which are the loop-carried values, and writes s3 and i3.

Why optimizers like SSA

  • Use-def chains are free. Each name has one definition, so "who defined this?" is a lookup, and "who uses this?" is a list kept with the definition.
  • Sparse analyses. Constant propagation, dead-code elimination and value numbering work along the def-use edges instead of recomputing sets for every block. They are faster and often more precise.
  • Dead code is easy to spot. A definition with no uses (and no side effects) can be deleted, and deleting it may make its operands unused, which cascades.
  • Cleaner transformations. Code motion, loop optimizations and register assignment do not have to worry that moving an instruction changes which x a later use reads.

SSA also costs something: converting to and from it takes time, the number of names grows, and phi functions must be eliminated before code generation. Production compilers also place phis more carefully than the minimal rule: pruned SSA adds a phi only if the variable is live there. Our program used the cheaper semi-pruned variation.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a phi function do?

    A phi merges the definitions that arrive on different incoming edges. Its i-th argument is the value to use when control arrives along the i-th edge.
  2. 2. Where must a definition of x in block D cause a phi function for x to be placed?

    The dominance frontier of D is where D's dominance ends: the first points where a path through D can merge with a path that did not pass D.
  3. 3. Which statement about SSA form is true?

    SSA is about the static program text: a loop body still executes its single assignment many times. Phi functions are removed before machine code is produced.
  4. 4. In the loop example, why does i get a phi function at head but t does not?

    Both entry and body supply a different definition of i at the loop head. t never carries a value across blocks, so no merge is needed.

Summary

  • SSA gives every definition its own name, so each use refers to exactly one definition.
  • Where two definitions meet at a join, a phi function chooses by incoming edge; phis are removed before code generation.
  • Phi functions go into the dominance frontier of each block that assigns the variable, repeated until no new phis appear.
  • Renaming walks the dominator tree with a stack of current names for each variable.
  • SSA makes constant propagation, dead-code elimination and value numbering simple and fast.

Next: Loop and Global Optimizations