Two Definitions, One Use: Building SSA in a Haskell Compiler

2026-07-27 • 14 min read

Last updated: 2026-07-27 • Commit 3e3e430

I have been writing a compiler in Haskell for a small statically typed language. It parses, it type checks, it builds SSA form, it optimises, and it emits LLVM IR that clang turns into a native binary. This post is about the SSA part, because it is the piece that made everything after it cheap, and the piece that felt like real compiler engineering rather than bookkeeping.

The short version: I lowered && to branches, which quietly created a variable with two definitions reaching one use, and fixing that properly is the entire reason SSA exists.

The problem, concretely

My language has short-circuit &&. That means f() && g() must not call g() when f() returns false. You cannot express that as a single instruction, so the lowering turns it into control flow. Here is what my compiler emits for return side(a) && side(b); before SSA:

fn both(a: int, b: int) -> bool {
  b0:
    %1 = call side(a)
    %0 = %1
    br %1 ? b1 : b2
  b1:
    %2 = call side(b)
    %0 = %2
    jmp b2
  b2:
    ret %0
}

This is correct. side(b) only runs when the left side was true, which is what short-circuiting means. But look at %0. It is assigned in b0 and assigned again in b1, and then read in b2. Two definitions reach one use.

That single fact is what makes optimization hard. Suppose I want to know whether %0 is a constant. I cannot answer by looking at the instruction that defines it, because there is no such instruction — there are two, and which one applies depends on a branch taken at runtime. Every analysis has to carry around "the set of definitions that might reach here," and that set has to be computed with a dataflow fixpoint, and it has to be recomputed every time a pass changes anything.

Static Single Assignment form removes the problem by fiat: every name is assigned exactly once. Then "the definition of %0" is a well formed phrase, and def-use chains are just pointers.

The catch

If every name is assigned once, what do you do at b2, where control arrives from two blocks carrying two different values?

You invent an instruction. A $\phi$ function takes one argument per incoming edge and evaluates to whichever argument corresponds to the edge actually taken:

  b2:
    %0.2 = phi [b0: %0.0, b1: %0.1]
    ret %0.2

That is the same program, in SSA. %0.0 and %0.1 are each assigned once, %0.2 is assigned once, and every use has exactly one definition.

$\phi$ is not a real machine instruction. It is a notation for "the value depends on how you got here," and the backend eventually destroys it by inserting copies on the incoming edges. But between construction and codegen, it lets every pass pretend the program is a simple dataflow graph.

The interesting question is where to put them. Naively you could put a $\phi$ for every variable at every join point, which is correct and produces a staggering amount of garbage. The right answer is a graph property called the dominance frontier.

Dominance

Fix a control flow graph with entry node $r$.

A node $d$ dominates node $n$, written $d \mathbin{\mathrm{dom}} n$, if every path from $r$ to $n$ passes through $d$. Every node dominates itself. $d$ strictly dominates $n$ if $d \mathbin{\mathrm{dom}} n$ and $d \neq n$.

Dominance matters here because of one observation: if $d$ dominates $n$, then a value computed in $d$ is guaranteed to be available at $n$. There is no way to reach $n$ without having executed $d$. So a definition in $d$ needs no $\phi$ at $n$ — there is nothing to merge with.

The dominance relation forms a tree. Every node except the entry has a unique immediate dominator $\mathrm{idom}(n)$: the strict dominator of $n$ that is dominated by every other strict dominator of $n$. Equivalently, the closest one.

Dominance frontiers

The frontier is where dominance stops:

$$ DF(n) = {\, m \;\mid\; \exists\, p \in \mathrm{pred}(m),\; n \mathbin{\mathrm{dom}} p \;\wedge\; n \not\mathbin{\mathrm{sdom}} m \,} $$

In words: $m$ is in the frontier of $n$ if $n$ dominates some predecessor of $m$, but does not strictly dominate $m$ itself. These are exactly the nodes where control flow originating in $n$ merges with control flow that avoided $n$ — the first places where a value defined in $n$ stops being guaranteed.

Which is precisely where you need a $\phi$.

Two examples from my compiler. A diamond:

  b0  idom=-   df={}
  b1  idom=b0  df={b3}
  b2  idom=b0  df={b3}
  b3  idom=b0  df={}

Both arms have the join b3 in their frontier, and b3 has an empty frontier because b0 dominates everything downstream. A loop:

  b0  idom=-   df={}
  b1  idom=b0  df={b1}
  b2  idom=b1  df={b1}
  b3  idom=b1  df={}

b1 is the loop header and it is in its own dominance frontier. That looks wrong the first time you see it. It is not: b1 dominates b2, b2 is a predecessor of b1 via the back edge, and b1 does not strictly dominate itself. So $b1 \in DF(b1)$, and a variable assigned anywhere in the loop body needs a $\phi$ at the header. That is the loop-carried dependence falling out of the definition.

Placing the nodes

A $\phi$ is itself a definition, so it can force more $\phi$s downstream. The placement set is the least fixpoint, the iterated dominance frontier:

$$ DF^{+}(S) = \lim_{i \to \infty} DF_i, \qquad DF_1 = DF(S), \qquad DF_{i+1} = DF!\left(S \cup DF_i\right) $$

For each variable $v$ with definition sites $S_v$, $\phi$ nodes for $v$ go exactly at $DF^{+}(S_v)$. That is Cytron et al.'s result, and it gives minimal SSA: no $\phi$ that could be omitted, and none missing.

The worklist version is short. Seed the list with the definition sites, and for each node popped, add the target to every frontier member that does not have one yet, pushing that member back on the list if it was not already a definition site:

spread :: DomInfo -> Set BlockId -> Set BlockId -> [BlockId] -> Set BlockId
spread info originals placed queue = case queue of
    [] -> placed
    (bid : rest) ->
        let frontier = Set.toList (frontierOf info bid)
            fresh = filter (isUnplaced placed) frontier
            nextPlaced = Set.union placed (Set.fromList fresh)
            added = filter (isNewDefSite originals) fresh
        in spread info originals nextPlaced (added ++ rest)

Computing the tree without computing dominator sets

The definition of dominance suggests a direct algorithm: $Dom(n)$ is the intersection of $Dom(p)$ over predecessors, plus $n$ itself, iterated to a fixpoint. It is obviously correct and it materializes a set per node.

I use Cooper, Harvey and Kennedy's algorithm instead, from A Simple, Fast Dominance Algorithm. It never builds the sets. Instead it keeps only the immediate dominator array and refines it in reverse postorder until nothing changes:

refineIdom index preds idoms bid =
    let candidates = filter (isProcessed idoms) (Map.findWithDefault [] bid preds)
    in case candidates of
        [] -> idoms
        (first : rest) ->
            let chosen = foldl (intersectNodes index idoms) first rest
            in Map.insert bid chosen idoms

The trick is intersectNodes. To intersect two nodes in the dominator tree, you walk both up toward the root and stop when they meet — and you know which one to advance by comparing reverse postorder numbers, because a node's idom always has a smaller RPO number than the node itself:

intersectNodes index idoms first second =
    if first == second
        then first
        else
            let a = climb index idoms first second
                b = climb index idoms second a
            in if a == b then a else intersectNodes index idoms a b

climb index idoms node target =
    if rankOf index node > rankOf index target
        then climb index idoms (Map.findWithDefault node node idoms) target
        else node

Two integer comparisons and a pointer chase, instead of a set intersection.

Renaming

Placement gives you $\phi$ nodes with no arguments. Renaming fills them in and versions everything else.

The algorithm is a depth-first walk of the dominator tree, not the CFG, carrying a stack of current versions per variable. At each block: version the $\phi$ destinations, rewrite each instruction's uses to the top of stack and give its destination a fresh version, then visit successors in the CFG to fill in their $\phi$ arguments with whatever is on top of the stack right now. Then recurse into dominator tree children, and pop everything the block pushed.

Walking the dominator tree is the part that makes it work. When you enter a block, the stack holds exactly the definitions that are guaranteed to be live there, because those are the definitions from blocks that dominate it. In Haskell the pop is free — save the stacks before recursing and restore after:

renameFrom :: DomInfo -> Renamer -> BlockId -> Renamer
renameFrom info renamer bid =
    let saved = renameStacks renamer
        afterBlock = renameBlock renamer bid
        children = dominatorChildren info bid
        afterChildren = foldl (renameFrom info) afterBlock children
    in afterChildren { renameStacks = saved }

Counters keep going up; only the stacks roll back. That one line is the whole scoping discipline of the renaming pass.

Semi-pruned placement

Minimal SSA is minimal in a specific sense — no removable $\phi$ given the definition sites — but it still inserts $\phi$s for values nobody reads. My three-address lowering generates a temporary per subexpression, and those are almost always dead one instruction later. Placing $\phi$s for them at every join their frontier reaches produces noise proportional to expression complexity.

Fully pruned SSA fixes this with a liveness analysis. I used the cheaper approximation: only place $\phi$s for names that are live-in to some block — that is, used in a block before being defined in it.

liveInOf :: Block -> Set Name
liveInOf block =
    let (needed, defined) = foldl scanInstr (Set.empty, Set.empty) (blockInstrs block)
        terminatorUses = Set.fromList (usedByTerminator (blockTerm block))
    in Set.union needed (Set.difference terminatorUses defined)

One linear scan per block, no fixpoint. A block-local temporary is never live-in anywhere, so it never gets a $\phi$. The %0 from the short-circuit example is live-in to b2, so it does.

The result

fn main() -> void {
  b0:
    %0.0 = array [1, 2, 3, 4, 5]
    numbers.0 = %0.0
    total.0 = 0
    i.0 = 0
    jmp b1
  b1:
    i.1 = phi [b0: i.0, b2: i.2]
    total.1 = phi [b0: total.0, b2: total.2]
    %1.0 = len numbers.0
    %2.0 = i.1 < %1.0
    br %2.0 ? b2 : b3
  b2:
    %3.0 = numbers.0[i.1]
    %4.0 = total.1 + %3.0
    total.2 = %4.0
    %5.0 = i.1 + 1
    i.2 = %5.0
    jmp b1
  b3:
    print total.1
    ret
}

Two $\phi$s, both at the loop header, for exactly the two variables the loop carries. numbers.0 gets none because it is never reassigned. The temporaries get none because they never cross a block boundary. The exit block reads total.1, the $\phi$ result, which is the correct value on every iteration count including zero.

Testing something you are not sure you understand

This is the part I would most want to read in someone else's post, so here it is in mine.

The dominance algorithm above is clever, and clever code is where I get things wrong. Worse, a unit test I write is a test of what I believe the answer is — if I misunderstood dominance frontiers, my implementation and my test will agree, both be wrong, and the suite will be green.

So the test suite contains a second implementation of everything, written straight from the definitions with no attempt at efficiency. Dominators by set intersection to a fixpoint. Frontiers by literally checking, for every pair $(n, m)$, whether $n$ dominates a predecessor of $m$ without strictly dominating $m$:

inFrontierOf :: DomInfo -> BlockId -> BlockId -> Bool
inFrontierOf info m n =
    let sources = Map.findWithDefault [] n (domPreds info)
    in any (dominates info m) sources && not (strictlyDominates info m n)

Then QuickCheck generates random programs, compiles them to CFGs, and asserts the fast and slow versions agree. The fast one ships; the slow one exists only to disagree if the fast one is wrong.

On top of that, three properties that state what SSA is, checked over about 1,200 generated programs:

• every name is defined exactly once
• every use is dominated by its definition — and for a $\phi$ argument, by the predecessor block it is labelled with, not by the block holding the $\phi$
• every $\phi$ has one argument per predecessor, labelled with the actual predecessors

The second is the one that matters. It is the definition of well formed SSA, and it fails loudly if placement or renaming is wrong in any way I did not think to write a unit test for.

The first time I ran these, the single-assignment property failed. The counterexample turned out to be a generated function with two parameters of the same name — something my type checker rejects, so it can never reach SSA in the real pipeline. The bug was in my generator, not my compiler. Worth saying plainly, because "the property found a bug" is a more interesting claim than it usually deserves to be, and this time the bug was mine and in the test.

A bug it found for real

Before writing any of this I checked the CFG for shadowed variables:

let x: int = 1;
if true { let x: str = "inner"; print(x); }
print(x);

Both xes lowered to the same name. The final print(x) would have printed "inner". Scope information was being discarded during lowering, and SSA built on that CFG would have been consistently, invisibly wrong — the $\phi$s would have been correct for a program nobody wrote.

The fix is alpha-renaming during lowering: the shadowing declaration becomes x$1, and the outer x survives. Fully qualified, a name in my IR now reads x$1.0 — source name, shadow index, SSA version. Neither $ nor . is legal in a source identifier, so generated names can never collide with yours.

I would not have caught it if I had gone straight to SSA. Checking the output of each stage by eye, on purpose, before building the next one, is worth the hour.

What it bought

Everything after this got cheaper, which is the whole argument for doing it.

The optimiser is four passes — constant folding, copy propagation, trivial $\phi$ elimination, dead code elimination — run to a fixpoint. Together they are about 300 lines, and none of them needs a dataflow framework. Dead code elimination is the clearest case: collect every name that appears as an operand anywhere, then delete any instruction whose destination is not in that set and which has no side effect. Two passes over the blocks. Without SSA that is a liveness analysis with a fixpoint over sets.

On my examples it removes 30 to 65 percent of instructions, mostly by folding constant expressions and then deleting what became unreachable:

Type recovery was cheap for the same reason. My SSA carries no types, and LLVM needs one for every value, so there is a pass that propagates them forward to a fixpoint: constants and parameters are known, every instruction derives its result from its operands, and a $\phi$ takes the type of its first known argument. It needs a fixpoint only because a $\phi$ in a loop header can precede the definition it merges. About a hundred lines.

Then LLVM IR, where $\phi$ maps onto LLVM's own phi instruction, so the structural work was already done.

$ haskompile --compile examples/factorial.hk
wrote examples/factorial.exe
$ ./examples/factorial.exe
15
720

Which is the thing I actually wanted: source text in, a program out.

The last test layer is the one that decides whether any of this is real. Every example program is compiled to a native binary twice, once with optimisation and once without, run, and both outputs diffed against a committed expected file. If a pass ever changes what a program does, that goes red. The sharpest case is the one this post opened with — a program where noisy(0) && noisy(3) must print 0 and must not print 3. If short circuiting broke anywhere between the parser and the machine code, that single test catches it.