Chapter 16 · Static Single Assignment Form¶

Part 3 · Analysis Foundations & SSA · about 3 weeks · Previous: Ch 15 · Next: Ch 17

The problem¶

You are given a function as a control-flow graph whose instructions assign and read variables any number of times: TAC listings from Ch 8, or LLVM IR in which every local lives in an alloca. You want an equivalent program in static single assignment (SSA) form, where every name has exactly one definition, that definition dominates every use, and merges of values are explicit (phi nodes, block arguments or upsilon/phi). You want it small (minimal, semi-pruned or pruned: no phis that are not needed) and fast to build (with dominance frontiers, a DJ-graph walk, or on the fly without any dominance information). At the end of the pipeline you want to leave SSA again: produce a phi-free program with as few copies as possible and without the lost-copy and swap bugs. And for memory, branch facts and merge predicates, which scalar SSA does not cover, you want its extensions. In pebblec your SSA construction is pebble-mem2reg (E1), which you run right after lowering to LLVM IR with pebblec --passes=pebble-mem2reg,…; it uses the dominator tree of Ch 15. The default -O pipelines use LLVM's own mem2reg and sroa. Every optimization of Ch 17–Ch 19 assumes SSA, and the register allocators of Ch 22 leave it.

What you will be able to do¶

Compute minimal, semi-pruned and pruned phi placements by hand (\(\mathrm{DF}^+\), upward-exposed uses, liveness), rename with Cytron's stacks, and prove that pruned = minimal minus dead phis.
Build SSA on the fly with Braun et al.'s algorithm (sealing, trivial-phi removal, redundant-SCC removal) and with Aycock–Horspool, and say when each is minimal.
Read LLVM's PromoteMemoryToRegister.cpp, SROA.cpp and SSAUpdater, and implement pebble-mem2reg (pruned SSA from allocas) that matches LLVM's phi counts.
Convert between phi nodes, block arguments and upsilon/phi, and explain what each costs for CFG edits and for SSA destruction.
Leave SSA correctly: detect lost-copy and swap situations, split critical edges, apply Sreedhar's Methods I–III and Boissinot et al.'s value-based coalescing, and sequentialize a parallel copy with the proven minimum number of moves.
Explain e-SSA/SSI, gated SSA, Memory SSA, Array SSA and HSSA, and read LLVM's print<predicate-info> and print<memoryssa> and GCC's virtual operands.
Choose a construction and a destruction algorithm for a given compiler, with measured phi and copy counts from the comparison labs.

Prerequisites: Ch 8 (TAC, CFGs, critical edges, and the phi ↔ block-argument translation of Lesson 8.4), Ch 14 (liveness) and Ch 15 (dominator trees, dominance frontiers, iterated frontiers, DJ graphs, reducibility).

Notation¶

Shared notation follows the house notation: §1 (sets, functions, logic), §3 (graphs and CFGs) and §4 (dominance and loops). Dominance, \(\mathrm{DF}\) and \(\mathrm{DF}^+\) are as in Ch 15. In this chapter:

Symbol	Meaning
\(G = (N, E, r)\), \(n\), \(m\)	the CFG, entry \(r\); \(n = \lvert N \rvert\), \(m = \lvert E \rvert\)
\(V\)	the variables of the input program (Definition 16.1.1)
\(\mathrm{defs}(v)\)	the blocks that assign \(v\), including \(r\) for the implicit initial definition
\(\mathrm{UE}(B)\)	variables used in \(B\) before any assignment in \(B\) (upward-exposed)
\(\mathrm{LiveIn}(B)\), \(\mathrm{LiveOut}(B)\)	liveness of variables (Definition 16.1.6)
\(\Phi_{\min}(v)\), \(\Phi_{\mathrm{semi}}(v)\), \(\Phi_{\mathrm{pruned}}(v)\)	the phi blocks of the three flavors (Definition 16.1.7)
\(x = \phi(x_1, \dots, x_k)\)	a phi; operand \(x_j\) comes from the \(j\)-th predecessor, all phis of a block execute in parallel (Definition 16.1.2)
\(x_i\), `x.i`	the \(i\)-th SSA version of variable \(x\) (\(x_0\) = the initial value)
\(\mathrm{def}(x)\), \(\mathrm{LR}(x)\)	the definition point and the live range of an SSA name (Lemma 16.7.1)
CSSA, TSSA	conventional and transformed SSA (Definition 16.1.8)
\((d_1, \dots, d_k) \gets (s_1, \dots, s_k)\)	a parallel copy: all sources read before any destination is written (Algorithm 16.7.5)
\(V(x)\)	the value of an SSA name for value-based interference (Definition 16.7.2); not to be confused with the variable set \(V\)
\(\pi\), \(\sigma\)	π-assignment of e-SSA, σ-function of SSI (Definitions 16.8.1, 16.8.2)
\(\gamma, \mu, \eta\)	gating functions of gated SSA (Definition 16.8.5)
\(\mathsf{M}_i\)	the \(i\)-th version of memory in Memory SSA, \(\mathsf{M}_0\) = `liveOnEntry` (Definition 16.8.7)
\(d\phi\), \(@A\)	definition φ and timestamp array of Array SSA (Definition 16.8.9)
\(\chi\), \(\mu\) (HSSA)	may-definition and may-use of Hashed SSA (Definition 16.8.11); context distinguishes this \(\mu\) from the gating μ

Technique map¶

Family	Techniques (origin)	Lesson
SSA properties and flavors	phi semantics; minimal SSA (Cytron, Ferrante, Rosen, Wegman, Zadeck 1991), semi-pruned SSA (Briggs, Cooper, Harvey, Simpson 1998), pruned SSA (Choi, Cytron, Ferrante 1991)	16.1
Construction with frontiers	Cytron et al. placement + renaming (1991); Sreedhar–Gao DJ-graph placement (1995)	16.2
Construction without frontiers	Braun, Buchwald, Hack, Leißa, Mallon, Zwinkau (2013) with SCC removal; Aycock–Horspool (2000)	16.3
LLVM case study	mem2reg (`PromoteMemToReg`), SROA, `SSAUpdater`/`SSAUpdaterBulk`	16.4
Representations	phi nodes (Cytron et al. 1991), block arguments (Kelsey 1995; Swift SIL, MLIR), upsilon/phi (Pizlo, WebKit B3)	16.5
Destruction	Cytron's naive copies (1991); critical-edge splitting and the lost-copy and swap problems (Briggs, Cooper, Harvey, Simpson 1998); CSSA with Methods I–III (Sreedhar, Ju, Gillies, Santhanam 1999)	16.6
Destruction done well	Boissinot, Darte, Rastello, Dupont de Dinechin, Guillon (2009); parallel-copy sequentialization (May 1989; Boissinot et al. 2009); coalescing (Budimlić et al. 2002); preview of SSA-based register allocation (Hack 2007)	16.7
Extensions	SSI (Ananian 1999) and e-SSA (Bodík, Gupta, Sarkar 2000); gated SSA (Ballance, Maccabe, Ottenstein 1990; Tu–Padua 1995); Memory SSA (Novillo 2007; LLVM MemorySSA); Array SSA (Knobe–Sarkar 1998; Fink, Knobe, Sarkar 2000); Hashed SSA (Chow, Chan, Liu, Lo, Streich 1996)	16.8

flowchart LR
  MIN["Minimal SSA<br/>Cytron et al. 1991"] -->|filter by liveness| PR["Pruned SSA<br/>Choi et al. 1991"]
  MIN -->|filter by global names| SP["Semi-pruned<br/>Briggs et al. 1998"]
  CY["Cytron placement + renaming"] -->|linear DF+ on DJ graph| SG["Sreedhar–Gao 1995"]
  SG -->|IDFCalculator + live-in filter| M2R["LLVM mem2reg"]
  M2R -->|aggregates first| SROA["SROA"]
  AH["Aycock–Horspool 2000<br/>maximal then minimize"] -->|on the fly, no dominance| BR["Braun et al. 2013"]
  BR -->|same lookup| SU["SSAUpdater"]
  PHI["phi nodes"] <-->|Kelsey 1995| BA["block arguments"]
  PHI -->|split into write + read| UP["upsilon/phi<br/>Pizlo"]
  NAIVE["naive copies<br/>Cytron 1991"] -->|lost copy, swap| BRIGGS["edge splitting<br/>Briggs et al. 1998"]
  NAIVE -->|make CSSA first| SREE["Sreedhar I–III 1999"]
  SREE -->|isolate + value-based coalescing| BOI["Boissinot et al. 2009"]
  BOI --> PC["optimal parallel-copy sequentialization"]
  MIN -->|memory as one variable| MSSA["Memory SSA"]
  MSSA -->|virtual variables, χ/μ, hashing| HSSA["HSSA 1996"]
  MSSA -->|element level| ASSA["Array SSA 1998"]
  MIN -->|σ at branches| SSI["SSI / e-SSA"]
  MIN -->|predicates on merges| GSA["gated SSA"]

Who uses what¶

System	Technique	Notes
LLVM 23	pruned SSA by Sreedhar–Gao placement (mem2reg, `IDFCalculator` with live-in blocks), SROA, SSAUpdater (Braun-style lookup); phi nodes; PHIElimination (Method I) + register coalescer (value numbers); PredicateInfo (e-SSA); MemorySSA (minimal, one memory variable)	Lessons 16.2, 16.4, 16.6–16.8
GCC 14	Cytron placement with dominance frontiers (`tree-into-ssa.cc`), pruned by liveness; out-of-SSA with partitions and a coalesce list (`tree-outof-ssa.cc`, `tree-ssa-coalesce.cc`); virtual operands `.MEM` (Memory SSA)	Lessons 16.2, 16.7, 16.8
Go 1.24	Braun-style lookup for small functions, semi-pruned Sreedhar–Gao placement above 500 blocks; edge "shuffle" sequentialization in the register allocator	Lessons 16.1, 16.3, 16.7
Cranelift (wasmtime 37)	Braun et al. in `cranelift-frontend`; block parameters; regalloc2 leaves SSA	Lessons 16.3, 16.5
MLIR / Swift SIL	block arguments	Lesson 16.5
WebKit B3 / DFG	upsilon/phi	Lesson 16.5
Jikes RVM 3.1.4	Heap Array SSA for redundant load elimination	Lesson 16.8
`pebblec`	`pebble-mem2reg` (pruned, Sreedhar–Gao placement, dominator-tree renaming)	Exercises E1

Comparison¶

The rows are those of the lessons' §8 tables.

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Minimal SSA	every phi merges two definitions, but dead phis remain	DF⁺ per variable · fastest placement	19 106 phis on the lab corpus	DF⁺ only	textbooks; the basis of the other two
Semi-pruned SSA	no phis for block-local names; dead phis of global names remain	+ one linear scan · as fast as minimal	8 620 phis on the lab corpus	+ UE scan (~15 lines)	Go (≥ 500 blocks), EaC's construction
Pruned SSA	no dead phis (Theorem 16.1.14)	+ liveness per variable · cheap for allocas	4 477 phis on the lab corpus	+ liveness (~30 lines)	LLVM mem2reg, GCC into-SSA, Pebble E1
Cytron et al.	any flavor (filter at placement); renaming handles any CFG	\(O(\lvert V \rvert \cdot \lvert \mathrm{DF} \rvert + S)\), quadratic frontiers on nested repeat-until loops · fast on real code; lab: 130 ms for all three flavors on 306 listings	deterministic names from the dominator-tree walk	~120 lines (placement + renaming)	GCC into-SSA, textbooks, the lab's Cytron flavors
Sreedhar–Gao	same placement, pruned via a live-in filter; renaming as Cytron	\(O(n + m)\) per variable, no frontiers · immune to the quadratic case	deterministic order via (level, DFS) keys	~50 lines for placement	LLVM IDFCalculator (mem2reg, SSAUpdaterBulk, MemorySSA), Go (≥ 500 blocks)
Braun et al.	pruned and copy-folded; minimal for reducible CFGs; needs the SCC pass for irreducible ones	about linear, no dominance information · lab: 227 ms on 306 listings (vs 130 ms for Cytron)	TSSA (copies folded); 4 352 phis on the lab corpus	~150 lines + ~60 for SCCs	Cranelift, Go (≤ 500 blocks), libFirm, LLVM's SSAUpdater
Aycock–Horspool	minimal (Cytron) on reducible CFGs; dead phis stay; redundant SCCs stay on irreducible CFGs	\(O(n_{\mathrm{join}} \lvert V \rvert)\) phis first, then sweeps · lab: 216 ms	18 990 phis on the lab corpus	~80 lines	teaching, quick prototypes; its rules are LLVM's phi simplification
mem2reg	scalar allocas with only loads and stores; pruned phis, then simplified	linear per alloca after the dominator tree · fast paths for one store or one block	TSSA (loads folded into stored values)	`PromoteMemoryToRegister.cpp` is ~1 200 lines; Pebble's E1 ~250	every LLVM `-O0`-to-SSA step; `pebblec` after lowering
SROA	aggregates with constant-offset accesses; then mem2reg	\(O(u \log u)\) per alloca · the most expensive of the three	scalar phis per field, splits `memcpy`	`SROA.cpp` is ~6 400 lines	the first scalar pass of `-O1`+ pipelines
SSAUpdater	one value, arbitrary set of definitions, any CFG	proportional to the explored subgraph · cheap per query	reuses matching phis	`SSAUpdaterImpl.h` ~500 lines	loop rotation, jump threading, LCSSA, LICM promotion
Phi nodes	full SSA; entries keyed by predecessor	edge edits \(O(m)\) per target block · fine in practice	self-describing; the verifier checks placement and arity	predecessor bookkeeping in every CFG pass	LLVM, GCC, Go, V8 TurboFan
Block arguments	full SSA; equivalent to phis (Theorem 8.4.10)	edge edits local to the branch; parameter deletion touches every predecessor	the parallel copy of an edge is one instruction	branch operand lists; natural for CPS/functional front ends	MLIR, Swift SIL, Cranelift
Upsilon/phi	full SSA with SSU shadow variables	CFG edits \(O(1)\) for SSA · validation needs a dataflow pass	Phis are plain instructions; destruction is trivially correct	the simplest CFG passes; effect analysis must know shadows	WebKit B3 and DFG
Naive copies	correct only without lost copies and swaps (CSSA with named operands)	\(O(A)\) · trivial	wrong answers on TSSA: 158 of the 564 lab L2 inputs (0 of the 153 conventional ones)	~10 lines	Cytron's paper; never alone in production
Critical-edge splitting (Briggs et al.)	always correct	\(O(A + E)\) · adds blocks and jumps	copies = operands + cycles; extra blocks	~60 lines + an edge splitter	GCC edge insertion, LLVM `SplitPHIEdges`, lab `split`
Sreedhar's CSSA (Methods I–III)	always correct; Method III close to minimal	I: \(O(A)\); III: pairwise tests per phi	I: \(A + \Phi\) copies before coalescing; III: far fewer	I: ~20 lines; III: ~150 with liveness	LLVM PHIElimination (Method I at machine level), research compilers
Boissinot et al.	always correct; handles TSSA and critical edges; value-aware	linear-time class checks, no interference graph · fastest known	fewest copies among the lesson's methods: lab 2 195 vs 4 595 (split) on Braun outputs	~200 lines with liveness	out-of-SSA passes that avoid interference graphs; LLVM's coalescer uses its value idea
Parallel-copy sequentialization	exact: \(n + c\) moves, proven optimal	\(O(k)\) per edge	minimal moves; one spare location	~40 lines	every out-of-SSA pass and register allocator (Go, GCC, Cranelift, CompCert)
Coalescing	removes copies between non-interfering names; not optimal (NP-complete)	graph: \(O(N^2)\); SSA dominance tests: linear	depends on visiting order and interference notion	~60 lines (union-find + tests)	GCC partitions, LLVM register coalescer, Ch 22 allocators
SSI / e-SSA	one name per (value, path fact): sparse range and predicate analyses	\(O(n + m + u \log u)\) · cheap, built on demand	at most 4 copies per branch, only where live	~900 lines (LLVM `PredicateInfo.cpp`)	LLVM SCCP, IPSCCP and NewGVN; ABCD bounds-check elimination [BGS00]
Gated SSA	φs become executable γ/μ/η with explicit predicates	\(O(\lvert R \rvert)\) per merge with sharing · exponential without	exact gates for structured code; thinned gates otherwise	~200 lines structured, more with path expressions	symbolic and dependence analysis; `select` after if-conversion
Memory SSA	def-use chains for all memory, one version stream	linear construction · clobber walks capped	minimal MemoryPhis; uses optimized lazily	~2,700 lines (`MemorySSA.cpp`, with the walker) plus the updater	LLVM LICM, DSE, EarlyCSE, NewGVN; GCC's `.MEM` web
Array SSA	element-level def-use through dφ and timestamps	Cytron per array · fast	exact for known indices; needs index analysis otherwise	~1,600 lines (Jikes `SSADictionary.java`, heap arrays)	redundant load elimination, parallelization of array code
Hashed SSA	per-variable μ/χ precision plus global hash-consing	\(O(\#\chi)\) can be \(s \cdot V\) · zero versions keep it small	exact versions for real occurrences	large: alias classes, virtual variables, hashing	SGI's optimizer [CCL+96]; the per-variable virtual operands GCC's manual describes

Comparison-lab results.

Construction (lab L1): on the 303 corpus listings of tests/ch16/Inputs/construct-goldens.txt the phi counts are minimal 19 106, semi-pruned 8 620, pruned 4 477, Braun 4 352, Aycock–Horspool 18 990. ch16-ssa-compare times all of them plus three generated ladders (306 listings): 130 ms for minimal, 119 ms for semi-pruned, 131 ms for pruned, 227 ms for Braun and 216 ms for Aycock–Horspool (best of several runs in this container).
Destruction (lab L2, ch16-out-of-ssa --stats, summed over the 564 test functions):
On pruned (conventional) inputs: naive = split = 7 176 copies, coalesce 2 615 (Method I would insert 9 110).
On Braun (transformed) inputs: split 4 595, coalesce 2 195.
Naive destruction gives wrong results on 158 of the 564 functions.

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 16.1	phi semantics; minimal, semi-pruned, pruned	drill `phi-placement`; quiz; flashcards
2	Lesson 16.2	Cytron et al., Sreedhar–Gao	drills `ssa-renaming`, `idf`, `phi-placement`
3	Lesson 16.3	Braun et al. (with SCCs), Aycock–Horspool	lab L1 `braun` and ★ `ah`
4	Lesson 16.4 + Exercises E1	Pebble uses pruned SSA via mem2reg (full implementation)	`pebble-mem2reg`, `./course test 16`
5	Lesson 16.5	phi nodes, block arguments, upsilon/phi	quiz; flashcards (conversions: Ch 8 lab)
6	Lesson 16.6	naive copies, Briggs et al., Sreedhar I–III	drill `lost-copy-swap`; lab L2 `naive`, `split`
7	Lesson 16.7	Boissinot et al., sequentialization, coalescing	drill `parallel-copy`; lab L2 `coalesce`
8	Lesson 16.8	SSI/e-SSA, gated SSA, Memory SSA, Array SSA, HSSA	theory + LLVM/GCC dumps; quiz
9	Comparison lab L1 `labs/ch16-ssa-construct/SPEC.md`	minimal vs semi-pruned vs pruned (Cytron) vs Braun (vs ★ Aycock–Horspool)	`ch16_construct_test`, `ch16.lab.compare-smoke`, `ch16-ssa-compare`
10	Comparison lab L2 `labs/ch16-out-of-ssa/SPEC.md`	naive vs split vs coalesce	`ch16_destruct_test`, lit `lab-destruct.test`
11	Theory test	all	`./course quiz 16` (≥ 80 % to finish)

Practice and check¶

./course drill phi-placement --difficulty easy     # warm up; --solution shows every step
./course drill ssa-renaming
./course drill parallel-copy --difficulty hard
./course drill lost-copy-swap
./course flash 16                                  # daily, a few minutes
./course quiz 16                                   # after the lessons
./course test 16                                   # after E1 and the labs
./course status                                    # done = quiz ≥ 80 % and tests pass

References¶

The chapter's annotated bibliography (papers, textbook sections, pinned LLVM, GCC, Go, Cranelift and WebKit sources, and docs) is in references.md. Start with:

[CFRWZ91], the SSA paper: placement, renaming and the first translation out of SSA.
[BBH+13], construction without dominance, as used in Cranelift and Go.
[BDR+09], leaving SSA correctly and cheaply.
[SSAB], the SSA book, which covers every lesson of this chapter.
[LLVM-Mem2Reg], the production construction you reimplement in E1.