SSA form

Deep dive

How it works

In: a CFG with reassigned variables · Out: one definition per name, phis at joins · State: version stacks or current_def[v][block], during construction · Cost: near-linear in practice; phi count drives it

Cytron et al. (classic).

1. Compute immediate dominators (see dominator tree); block D dominates B if every entry-to-B path passes D.
2. Dominance frontier DF(D) = blocks J where D dominates a predecessor of J but does not strictly dominate J: where D's dominance ends.
3. For each variable v with definition blocks Defs(v), put a phi for v at every block in DF+(Defs(v)); a phi is itself a definition, so iterate to a fixed point (a worklist).
4. Rename: walk the dominator tree depth first with a stack of current versions per variable; push at each definition, fill phi operands for each successor, pop on exit.

Computing DF (Cooper-Harvey-Kennedy): for each join J, walk from every predecessor up the idom chain to idom(J), adding J to the DF of each block visited.

 edges: 0>1  1>2  1>5  2>3  2>4  3>4  4>1      idom: 1<-0 2<-1 3<-2 4<-2 5<-1
 DF(3)={4}  DF(2)=DF(4)=DF(1)={1}              x defined in 0,3: phi at 4, then at 1

Flavours of placement.

• Minimal: Cytron as above; no phi where only one definition reaches.
• Semi-pruned: only variables read in a block before being written there ("non-local" names); block-local temporaries never get phis (Briggs et al.).
• Pruned: also require v live-in at the join; costs a liveness pass (dataflow analysis).

Braun et al. (on the fly). Keep current_def[v][block]. write(v,b,val) sets it. read(v,b): if set, return it; if b has one predecessor, recurse into it; if b is sealed (all predecessors known), create a phi, record it, fill operands by reading v in each predecessor, and remove it if trivial (all operands equal each other or itself; replace by that value and re-check phis that used it). If b is unsealed (a loop header whose body is still being built), create an operand-less phi, remember it as incomplete, and fill it in seal(b). No trivial phis remain: minimal SSA for reducible CFGs.

Out of SSA. Replace each phi by copies at the end of each predecessor, executed as one parallel copy per edge. Two classic traps:

• Lost copy: x2 = phi(x1, x3) in a loop header, and x3 = x2 + 1 in the loop, x2 used after the exit. The copy x2 = x3 placed at the end of the header also runs on the exit path and clobbers x2. Fix: split the critical edge or copy to a fresh temp.
• Swap: a2 = phi(a1, b2); b2 = phi(b1, a2) at one header; sequential copies a2 = b2; b2 = a2 read the clobbered value. Fix: sequentialise the parallel copy (order by dependency, break cycles with one temporary).

Then coalesce copies so most vanish (Sreedhar et al.; Boissinot et al.).

Block arguments vs phis. MLIR and Cranelift write block1(v0, v1) and jump with jump block1(a, b). Same expressive power as phis (MLIR Rationale); values travel with the edge, so no "phis come first" rule, and function parameters are the entry block's arguments. Out-of-SSA is "emit the edge's parallel copy".

What SSA makes cheap. A use-def edge is the fact. Constant propagation is sparse: one lattice value per name, worklist over def-use edges (SCCP). GVN keys on (opcode, operand value numbers) with no kill sets. Dead code is a name with no uses.

Code

Dominators (Cooper-Harvey-Kennedy), dominance frontiers and phi placement in all three flavours, asserted on the CFG above (x: defs 0,3; y: defs 0,4; z: def 2, read in 3; w: block-local). Compiled and run; renaming is left out.

use std::collections::BTreeSet;
pub struct Cfg { pub succs: Vec<Vec<usize>> } // block 0 = entry
impl Cfg {
    fn preds(&self) -> Vec<Vec<usize>> {
        let mut p = vec![vec![]; self.succs.len()];
        for (b, ss) in self.succs.iter().enumerate() { for &s in ss { p[s].push(b); } }
        p
    }
    fn rpo(&self) -> Vec<usize> { // reverse postorder, iterative DFS
        let (mut post, mut seen) = (vec![], vec![false; self.succs.len()]);
        let mut st = vec![(0usize, 0usize)];
        seen[0] = true;
        while let Some(&mut (b, ref mut i)) = st.last_mut() {
            if let Some(&s) = self.succs[b].get(*i) {
                *i += 1;
                if !seen[s] { seen[s] = true; st.push((s, 0)); }
            } else { post.push(b); st.pop(); }
        }
        post.reverse();
        post
    }
    pub fn idoms(&self) -> Vec<usize> { // idom[0] = 0, unreachable = MAX
        let (order, preds) = (self.rpo(), self.preds());
        let mut num = vec![usize::MAX; self.succs.len()];
        for (i, &b) in order.iter().enumerate() { num[b] = i; }
        let mut idom = vec![usize::MAX; self.succs.len()];
        idom[0] = 0;
        let mut changed = true;
        while changed {
            changed = false;
            for &b in &order[1..] {
                let mut new = usize::MAX;
                for &p in &preds[b] {
                    if idom[p] == usize::MAX { continue; }
                    new = if new == usize::MAX { p } else {
                        let (mut x, mut y) = (p, new); // intersect along idom chains
                        while x != y {
                            while num[x] > num[y] { x = idom[x]; }
                            while num[y] > num[x] { y = idom[y]; }
                        }
                        x
                    };
                }
                if idom[b] != new { idom[b] = new; changed = true; }
            }
        }
        idom
    }
    pub fn frontiers(&self) -> Vec<BTreeSet<usize>> { // walk up from each join predecessor
        let (idom, preds) = (self.idoms(), self.preds());
        let mut df = vec![BTreeSet::new(); self.succs.len()];
        for b in 0..self.succs.len() {
            if preds[b].len() < 2 || idom[b] == usize::MAX { continue; }
            for &p in &preds[b] {
                if idom[p] == usize::MAX { continue; }
                let mut r = p;
                while r != idom[b] { df[r].insert(b); r = idom[r]; }
            }
        }
        df
    }
}
#[derive(Clone, Copy, PartialEq)]
pub enum Mode { Minimal, SemiPruned, Pruned }
// defs[b]: variables written in b; uses[b]: read before written in b
pub fn place_phis(cfg: &Cfg, defs: &[Vec<usize>], uses: &[Vec<usize>], nvars: usize, mode: Mode) -> Vec<BTreeSet<usize>> {
    let (n, df) = (cfg.succs.len(), cfg.frontiers());
    let mut live_in = vec![vec![false; nvars]; n]; // used by Pruned
    let mut global = vec![false; nvars];            // used by SemiPruned
    for b in 0..n { for &v in &uses[b] { global[v] = true; } }
    let mut changed = true;
    while changed {
        changed = false;
        for b in (0..n).rev() {
            for v in 0..nvars {
                let live_out = cfg.succs[b].iter().any(|&s| live_in[s][v]);
                let li = uses[b].contains(&v) || (live_out && !defs[b].contains(&v));
                if li && !live_in[b][v] { live_in[b][v] = true; changed = true; }
            }
        }
    }
    let mut phis = vec![BTreeSet::new(); n]; // phis[b] = variables with a phi at b
    for v in 0..nvars {
        if mode == Mode::SemiPruned && !global[v] { continue; }
        let mut work: Vec<usize> = (0..n).filter(|&b| defs[b].contains(&v)).collect();
        while let Some(b) = work.pop() {
            for &d in &df[b] {
                if mode == Mode::Pruned && !live_in[d][v] { continue; }
                if phis[d].insert(v) && !defs[d].contains(&v) { work.push(d); } // a phi is a def
            }
        }
    }
    phis
}
fn main() {
    // 0->1; 1->2,5; 2->3,4; 3->4; 4->1; 5 = exit
    let cfg = Cfg { succs: vec![vec![1], vec![2, 5], vec![3, 4], vec![4], vec![1], vec![]] };
    assert_eq!(cfg.idoms(), vec![0, 0, 1, 2, 2, 1]);
    let df = cfg.frontiers();
    let want: [&[usize]; 6] = [&[], &[1], &[1], &[4], &[1], &[]];
    for b in 0..6 { assert_eq!(df[b], want[b].iter().copied().collect::<BTreeSet<_>>()); }
    // variables x=0 y=1 z=2 w=3
    let defs = vec![vec![0, 1], vec![], vec![2, 3], vec![0, 3], vec![1], vec![]];
    let uses = vec![vec![], vec![0, 1], vec![], vec![2], vec![0, 1], vec![1]];
    let at = |m| {
        let p = place_phis(&cfg, &defs, &uses, 4, m);
        (0..4).map(|v| (0..6).filter(|&b| p[b].contains(&v)).collect::<Vec<_>>()).collect::<Vec<_>>()
    };
    assert_eq!(at(Mode::Minimal), vec![vec![1, 4], vec![1], vec![1], vec![1, 4]]);
    assert_eq!(at(Mode::SemiPruned), vec![vec![1, 4], vec![1], vec![1], vec![]]);
    assert_eq!(at(Mode::Pruned), vec![vec![1, 4], vec![1], vec![], vec![]]);
}

Complexity and constants

• Dominators by CHK iteration: near-linear on real CFGs, worst case quadratic; DF sets can also blow up on pathological graphs.
• Phi count is the cost driver: on the example minimal places 6 phis, semi-pruned 4, pruned 3 (measured by the code). Each phi has one operand per predecessor, so wide joins times many live variables multiply.
• Braun: each read walks single-predecessor chains and memoizes per block; total work about proportional to reads plus phis.

Efficiency

• Cost: compile time is memory traffic over instruction and phi operand lists: dominators touch each edge a few times, renaming each instruction once. Phis: 6 minimal, 4 semi-pruned, 3 pruned on the example (measured by the code). Run-time cost is the copies left after out-of-SSA coalescing.
• Levers:
  • pruned or semi-pruned placement — fewer phis to rename and coalesce (Briggs et al.) — most variables are block-local
  • Braun on-the-fly construction — no dominator, frontier or rename pass — frontends that walk the code once
  • sparse analyses on def-use edges — each name visited about once (dataflow analysis) — value properties
• Naive → standard → state of the art:
  • per-variable dataflow to find merge points · fixed point per variable
  • Cytron: dominators, frontiers, renaming · near-linear in practice, three passes
  • Braun: one pass with trivial-phi cleanup · no dominator tree needed

Implementation notes

• Store phis as block parameters and edge arguments on the terminator; this removes "skip the phi prefix" bugs.
• Phi operands follow predecessor order; index by edge id, or edge splitting scrambles operands.
• u32 value ids; use lists as intrusive lists or CSR so replace-all-uses (trivial-phi removal) is cheap.
• Compare reverse-postorder numbers, not sets; seal blocks as soon as the last predecessor edge exists.
• Split critical edges (control-flow graph) before out-of-SSA so an edge copy never lands in a block other edges also run through.

Pitfalls

• Dead phis in minimal SSA keep dead values alive; build pruned or run DCE.
• Unreachable blocks in preds give phis operands from nowhere; remove them first.
• Irreducible loops: Braun's result may keep extra phis.
• Lost copy and swap when lowering phis one at a time.
• Address-taken locals are not SSA names; LLVM's mem2reg promotes only allocas used by loads and stores.
• Reads with no definition need an explicit undef, else construction recurses to the entry.

Variants and alternatives

In production

• Compilers: LLVM promotes allocas to SSA registers in mem2reg using iterated dominance frontiers (LangRef); Cranelift's cranelift-frontend builds SSA on the fly (Braun et al.) with block parameters; MLIR uses block arguments instead of phis (Rationale).
• JITs: JavaScriptCore's B3 IR uses SSA (WebKit blog).
• GPU shaders: SPIR-V keeps intermediate results in SSA form, with variables for load/store (spec).
• Static analysis and security: CodeQL provides an SSA library for Java/Kotlin analyses (docs).

Implementations

Sources

• Cytron, Ferrante, Rosen, Wegman, Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM TOPLAS 13(4), 1991. paper
• Braun, Buchwald, Hack, Leißa, Mallon, Zwinkau, Simple and Efficient Construction of Static Single Assignment Form, CC 2013. paper · code
• Briggs, Cooper, Harvey, Simpson, Practical improvements to the construction and destruction of static single assignment form, Software: Practice and Experience 28(8), 1998.
• Cooper, Harvey, Kennedy, A Simple, Fast Dominance Algorithm, Rice University technical report, 2001.
• Sreedhar, Ju, Gillies, Santhanam, Translating Out of Static Single Assignment Form, SAS 1999.
• Boissinot, Darte, Rastello, Dupont de Dinechin, Guillon, Revisiting Out-of-SSA Translation for Correctness, Code Quality and Efficiency, CGO 2009.
• Appel, SSA is functional programming, ACM SIGPLAN Notices 33(4), 1998.
• Rosen, Wegman, Zadeck, Global Value Numbers and Redundant Computations, POPL 1988. paper
• MLIR Rationale, "Block Arguments vs PHI nodes". docs