Chapter 17 · SSA-Based Scalar Optimizations¶
Part 4 · Optimization · about 3 weeks · Previous: Ch 16 · Next: Ch 18
The problem¶
You are given a function in SSA form: LLVM IR after mem2reg, or the chapter's compact SSA notation. You want an equivalent function that computes less, obtained with scalar optimizations, the ones that look at individual values rather than loops or memory layouts. Five questions organize the chapter. Which values are constants, and which ranges or bits of a value are known (constant propagation, LVI, known bits)? Which computations and branches cannot affect the output (dead-code elimination)? Which computations recompute a value that is already available on some or all paths (value numbering, partial-redundancy elimination)? Which branches and blocks are left over after the others have run (CFG simplification, jump threading)? And how should all of these be ordered, when each can enable the others (phase ordering, combined analyses, equality saturation)? The inputs come from Ch 16 (SSA), Ch 15 (dominator and post-dominator trees, control dependence) and Ch 14 (lattices and fixed points). In LLVM 23 these are the passes sccp/ipsccp, correlated-propagation, bdce, adce, dse, early-cse, gvn, newgvn, gvn-hoist, simplifycfg and jump-threading, which make up much of the function simplification pipeline of default<O2>. In pebblec your four passes run on the LLVM IR that Pebble emits, before the loop optimizations of Ch 18.
What you will be able to do¶
- Trace SCCP by hand (both worklists, every lattice change and executable edge) and prove that it finds every constant that constant propagation and dead-code elimination find together, in any order.
- Compute known bits, demanded bits and constant ranges for small functions, and say what LazyValueInfo and CorrelatedValuePropagation do with them.
- Mark live instructions for aggressive DCE using control dependence, and explain why ADCE may delete an empty loop only when the function must make progress.
- Compute the congruence partition of Alpern, Wegman and Zadeck by hand, and compare it with dominator-based hashing on functions where the optimistic and pessimistic answers differ.
- Solve the four lazy code motion bit-vector systems (anticipability, availability, later, insert/delete) and apply them to a TAC program.
- Implement
pebble-sccp,pebble-adce,pebble-gvnandpebble-simplifycfgasoptplugin passes, check them against LLVM, and measure simple CP vs SCCP and hash-based vs partition value numbering in the comparison lab. - Explain the phase-ordering problem with a measured example. Prove that a combined analysis is at least as precise as any interleaving of separate ones. Build a small equality-saturation engine (★).
- Find where LLVM 23, GCC 15 and Cranelift implement each technique, and read the relevant code.
Prerequisites: Ch 14 (lattices, monotone frameworks, available expressions and very busy expressions, sparse analysis), Ch 15 (dominator trees, post-dominance with a virtual exit, control dependence), Ch 16 (SSA and mem2reg), Ch 9 (LLVM IR), and Lesson 8.3 (DAGs and hash-consing, the idea behind value numbering). Ch 13 (local value numbering) is referenced but not required.
Notation¶
Shared notation follows the house notation: §1 (sets, functions, logic), §2 (orders and lattices), §3 (graphs and CFGs), §4 (dominance) and §7 (dataflow, SSA, IR). Orientation: as in Ch 14, lattice values rise: \(\bot\) means "no evidence yet" (optimistic: unreachable, undefined, congruent to everything), \(\top\) means "overdefined". So SCCP starts every value at \(\bot\) and every edge non-executable, and the AWZ partition starts with one class and only splits. In this chapter:
| Symbol | Meaning |
|---|---|
| \(F\) | an SSA function; \(N\), \(E\) its blocks and CFG edges, \(n = \lvert N \rvert\), \(e = \lvert E \rvert\) |
| \(I\), \(U\) | number of instructions, number of SSA uses (def-use edges) |
| \(\bot\), \(c\), \(\top\) | the constant lattice of Lesson 17.1: no evidence, the constant \(c\), overdefined |
| \(X\) | the set of executable edges; a block is executable if an edge of \(X\) enters it (Definition 17.1.7) |
| \(V(v)\) | the lattice value of SSA value \(v\) (Definition 17.1.7) |
| \([a, b)\), \(\mathrm{CR}(v)\) | a wrapped half-open interval; LLVM's ConstantRange of \(v\) (Lesson 17.2) |
| \(\mathrm{KB}(v) = (Z, O)\) | known-zero and known-one bit masks (Definition 17.2.4) |
| \(\mathrm{DB}(v)\) | demanded bits of \(v\) (Definition 17.2.6) |
| \(\mathrm{CD}(Y)\), \(\mathrm{ipdom}(Y)\) | control dependences, immediate post-dominator (Ch 15, Lesson 15.4) |
| \(\mathit{Live}\) | the instructions ADCE marks useful (Algorithm 17.3.5) |
| \(\mathrm{VN}(v)\) | the value number of \(v\) |
| \(v \equiv w\) | \(v\) and \(w\) are congruent (Definition 17.5.1) |
| \(P = \{C_1, \dots, C_k\}\) | a partition of the SSA values into classes |
| \(\mathrm{ANTIN}\), \(\mathrm{ANTOUT}\), \(\mathrm{AVIN}\), \(\mathrm{AVOUT}\) | anticipability and availability per block (Lesson 17.6) |
| \(\mathrm{EARLIEST}(i, j)\), \(\mathrm{LATER}(i, j)\), \(\mathrm{LATERIN}(j)\) | lazy code motion's edge and entry sets (Definition 17.6.5) |
| \(\mathrm{INSERT}(i, j)\), \(\mathrm{DELETE}(j)\) | where LCM inserts and deletes computations |
| \(\mathrm{DEEXPR}\), \(\mathrm{UEEXPR}\), \(\mathrm{EXPRKILL}\) | downward exposed, upward exposed and killed expressions of a block (EaC3's names) |
| \(\mathrm{lfp}\, G\) | least fixed point of a monotone \(G\) |
| \(\mathrm{find}(c)\), \(\mathrm{terms}(c)\) | union-find root of an e-class; the terms it represents (Definition 17.8.2) |
| \(\ell \to r\), \(\sigma\) | a rewrite rule; a substitution from pattern variables to e-classes (Definition 17.8.3) |
Numbered statements are N.k.m (chapter, lesson, counter), as in NOTATION.md §9.
Technique map¶
| Family | Techniques (origin) | Lesson |
|---|---|---|
| Constant propagation | Kildall's dense CP (Kildall 1973), sparse simple CP on SSA (Reif & Lewis 1977; Wegman & Zadeck 1991), dense conditional CP (Wegbreit 1975), SCCP (Wegman & Zadeck 1991), interprocedural SCCP (preview of Ch 20) | 17.1 |
| Range and bit analyses | LazyValueInfo and CorrelatedValuePropagation (LLVM), ConstantRange (wrapped intervals), known bits (ValueTracking), demanded bits and BDCE (LLVM), GCC's Ranger/VRP | 17.2 |
| Dead-code elimination | Mark–sweep DCE, aggressive DCE with control dependence (Cytron, Ferrante, Rosen, Wegman & Zadeck 1991), dead-store elimination (MemorySSA-based DSE in LLVM) | 17.3 |
| Dominator-scoped redundancy | EarlyCSE (LLVM), dominator-based value numbering DVNT (Briggs, Cooper & Simpson 1997), LLVM's GVN with equality propagation | 17.4 |
| Partition and optimistic GVN | Congruence partitioning (Alpern, Wegman & Zadeck 1988) with Hopcroft splitting, optimistic RPO/SCC value numbering (Simpson 1996; Cooper & Simpson), NewGVN (Gargi 2002; LLVM), predicated VN, GVN-hoist and GVN-sink | 17.5 |
| Partial-redundancy elimination | Morel–Renvoise (1979), lazy code motion (Knoop, Rüthing & Steffen 1992; Drechsler & Stadel 1993 edge form), SSAPRE (Chow, Chan, Kennedy, Liu, Lo & Tu 1997; Kennedy et al. 1999), GVN-PRE (VanDrunen & Hosking 2004), LLVM load PRE | 17.6 |
| CFG simplification | SimplifyCFG and Cooper–Torczon's Clean, switch-to-lookup-table, jump threading (Mueller & Whalley 1995; LLVM with LVI; GCC's backward threader) | 17.7 |
| Phase ordering and equality saturation | Fixed pipelines, combined analyses (Click & Cooper 1995), equality saturation (Tate, Stepp, Tatlock & Lerner 2009) with rebuilding (egg, Willsey et al. 2021), acyclic e-graphs (Cranelift) | 17.8 |
flowchart LR
K[Kildall CP 1973] -->|SSA def-use chains| SSC[Sparse simple CP]
W75[Wegbreit 1975<br/>conditional CP] -->|sparse| SCCP[SCCP 1991]
SSC -->|executable edges| SCCP
SCCP -->|ranges per edge| LVI[LVI / CVP, Ranger]
SCCP -->|bit lattice| KB[Known / demanded bits]
MS[Mark-sweep DCE] -->|control dependence| ADCE[ADCE 1991]
LVN[Local VN, Ch 13] -->|dominator scopes| DVNT[DVNT / EarlyCSE / GVN]
DVNT -->|optimistic partition| AWZ[AWZ 1988]
AWZ -->|hashing + folding| RPO[RPO / SCC VN]
RPO -->|constants + reachability| NGVN[NewGVN]
MR[Morel-Renvoise 1979] -->|edge placement, optimal| LCM[Lazy code motion 1992]
LCM -->|on SSA| SSAPRE[SSAPRE 1997]
LCM -->|value numbers| GVNPRE[GVN-PRE 2004]
SCCP -.->|leaves constant branches| SCFG[SimplifyCFG]
LVI -->|edge facts| JT[Jump threading]
SCCP -->|combined with VN| CC[Click-Cooper 1995]
AWZ --> CC
CC -->|non-destructive rewriting| EQS[Equality saturation 2009]
EQS -->|rebuilding| EGG[egg 2021]
EQS -->|acyclic, eager| AEG[Cranelift aegraph]Who uses what¶
| System | Technique | Notes |
|---|---|---|
| LLVM 23 | SCCP and IPSCCP (ValueLatticeElement with ranges), LVI + CVP, known bits / demanded bits + BDCE, ADCE, MemorySSA DSE, EarlyCSE, GVN (DVNT-style + load PRE), NewGVN (optional), GVN-hoist/sink (optional), SimplifyCFG (8× at -O2), jump threading |
lessons 17.1–17.7; llvm/lib/Transforms/Scalar/ and llvm/lib/Transforms/Utils/SimplifyCFG.cpp |
| GCC 15 | CCP (5× in the pipeline), Ranger-based VRP and threading, dce/cddce (control-dependence DCE), dse, FRE and PRE on RPO value numbering (tree-ssa-sccvn.cc, tree-ssa-pre.cc), RTL lazy code motion (lcm.cc, gcse.cc) |
17.1, 17.3, 17.5, 17.6 |
| Open64 | SSAPRE (osprey/be/opt/opt_ssa*, opt_eant.cxx, opt_efinalize.cxx) |
17.6 |
| Cranelift (Wasmtime 37) | aegraph mid-end: eager ISLE rewriting, GVN by hashconsing, LICM and rematerialization during elaboration | 17.8 |
| egg 0.11 | equality saturation with rebuilding, e-class analyses, extraction | 17.8 |
| MLIR | -sccp (sparse dataflow framework), -cse (dominator-scoped), canonicalization patterns |
17.1 |
| Pebble | pebble-sccp, pebble-adce, pebble-gvn (DVNT), pebble-simplifycfg |
exercises |
Comparison¶
The fixed columns follow docs/authoring/DEPTH_CONTRACT.md §3 item 8; every lesson repeats its own rows. \(n\) blocks, \(e\) edges, \(I\) instructions, \(U\) uses, \(E\) def-use edges (Lesson 17.5), \(N\) values, \(h\) the lattice height.
Constant propagation (lesson 17.1)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Kildall dense CP | Constants valid on all paths, every edge assumed executable; equals SSC on SSA | \(O(\lvert\mathit{Vars}\rvert^2 n e)\) · slow on large functions | A map per program point; works without SSA | Low (one generic solver) | Non-SSA IRs (GCC RTL cprop), teaching |
| Sparse simple CP (SSC) | Same constants as Kildall (Theorem 17.1.11); optimistic at phis | \(O(U + I)\) · linear | One lattice value per SSA value | Low | Folding along def-use chains; the base of SCCP |
| SCCP | Strictly more than CP + DCE iterated (Theorem 17.1.12); proves blocks unreachable | \(O(U + e + I)\) · linear, ~2–3 visits per instruction | Constants plus executable edges; drives branch folding | Medium (two worklists, edge bookkeeping) | LLVM sccp/ipsccp, GCC CCP, MLIR -sccp |
Range and bit analyses (lesson 17.2)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| LazyValueInfo + CVP | Per-block, per-edge ranges (branch facts); pessimistic on cycles | demand-driven, cached per (value, block); capped at 500 steps | Ranges on request; rewrites divisions, flags, compares | High (cache invalidation, edge constraints) | CVP, jump threading (LLVM); Ranger/VRP (GCC) |
| ConstantRange arithmetic | Wrapped intervals; sound transformers; one interval per value (union loses) | \(O(1)\) per operation | Ranges printed as range(...), !range |
Medium (every opcode, signed/unsigned views) | SCCP's lattice, LVI, InstCombine, attributes |
| Known bits | Per-bit facts; incomparable with ranges; best transformer for add | query \(O(2^d)\) with depth cap \(d\) | Zero/one masks | Low per rule, many rules | InstCombine, alignment, SelectionDAG |
| Demanded bits + BDCE | Backward; removes computations of undemanded bits | \(O(w \cdot U)\) | Masks per value | Low | BDCE, InstCombine's SimplifyDemandedBits, vectorizer width |
Dead-code elimination (lesson 17.3)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Mark–sweep DCE | Removes dead cycles; keeps every branch | \(O(I + U)\) · linear | CFG unchanged | Low | Cheap cleanup; LLVM adce without control flow, GCC dce |
| Aggressive DCE | Also removes dead branches and dead loops (Theorem 17.3.11) | \(O(I + U + \lvert\mathrm{CD}\rvert)\) · near-linear with IDF | Rewrites branches to post-dominators | Medium (post-dominators, control dependence, termination policy) | LLVM adce, GCC cddce, pebble-adce |
| Dead-store elimination | Removes overwritten / never-read stores; enables ADCE | \(O(I \cdot s)\) with MemorySSA scan limits | Deletes memory operations | High (alias analysis, partial overwrites) | LLVM dse, GCC dse |
Dominator-scoped redundancy (lesson 17.4)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| EarlyCSE | Dominated redundancies of pure ops, loads (generations or MemorySSA), calls; simplification | \(O(I + U)\) · the cheapest global CSE | Replaces with dominating values | Low–medium | Cleanup between LLVM passes (2× in default<O2>) |
| Dominator-based VN (DVNT) | Dominated redundancies + meaningless/redundant phis; pessimistic at back edges; misses siblings | \(O(I + U)\) · one walk | Value numbers + replacements | Low | pebble-gvn; GCC dom; teaching |
| LLVM GVN | DVNT-like numbering + equality propagation + load elimination + PRE | \(O(I + U)\) per iteration + memdep · the most expensive of the three | Replacements, PRE insertions | High | LLVM gvn at -O2 |
Partition and optimistic GVN (lesson 17.5)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| AWZ partitioning | Maximal congruence (Theorem 17.5.10); ⊇ hash-based (17.5.12); no algebra, no constants | \(O(E \log N)\) Hopcroft; rounds × \(O(E)\) with signatures | Classes, not replacements (needs a leader choice) | Medium (partition refinement) | Theory, the lab; basis of optimistic VN |
| Optimistic RPO / SCC VN | Same partition, plus folding and identities during hashing | 2–3 linear iterations · fast | Value numbers usable directly | Medium | GCC FRE/PRE (do_rpo_vn) |
| NewGVN (Gargi) | Optimistic congruence + constants + unreachable code + predicates + memory | sparse, touched instructions · slower than GVN | Replacements; unreachable blocks marked | High | LLVM newgvn (not default) |
| GVN-hoist / GVN-sink | Moves equal computations to a common dominator / successor; code size | per value number · cheap with limits | Fewer copies, same number of evaluations | Medium | LLVM gvn-hoist, gvn-sink; GCC code hoisting |
Partial-redundancy elimination (lesson 17.6)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Morel–Renvoise | Correct and safe; misses critical-edge cases; not optimal (Proposition 17.6.15) | bidirectional bit vectors · slow to converge | Block-end insertions | Medium | Historical; the problem statement |
| Lazy code motion | Computationally and lifetime optimal among safe placements (Theorems 17.6.13–17.6.14); lexical | 4 rapid bit-vector problems · fast | Edge insertions, deletions, temporaries | Medium | GCC RTL PRE (lcm.cc), textbooks, the ★ lab |
| SSAPRE | Same optimality per expression, on SSA; sparse | per expression, near-linear | Φ-based placement, SSA temporaries | High (six steps) | SGI/Open64; the SSA book |
| GVN-PRE | Value-based: finds redundancies with different names, via phi-translation | set operations per block over value numbers | Insertions of new expressions (e.g. x_6 * 2) |
High | GCC tree PRE |
| LLVM load PRE | Loads only; single missing predecessor; safety checks | per load, memdep-bound | Hoisted loads + phis | Medium (inside GVN) | LLVM gvn |
CFG simplification (lesson 17.7)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| CFG simplification | Canonical CFG: no constant branches, no unreachable blocks, no mergeable chains | rounds × linear · cheap, run often | Fewer blocks and edges; selects |
Low for the core rules, high for LLVM's full set | After every CFG-changing pass (LLVM 8× at -O2) |
| Switch-to-lookup-table | Dense constant switches only | \(O(k \log k + \mathit{size})\) | A constant table + range check | Medium (profitability, holes, types) | Late SimplifyCFG in LLVM |
| Jump threading | Removes branches whose outcome is known per edge (with LVI: ranges, predicates) | LVI queries + bounded duplication | Duplicated blocks | Medium–high (SSA repair, loop headers) | LLVM jump-threading 2× at -O2; GCC threaders |
Phase ordering and equality saturation (lesson 17.8)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Phase ordering (fixed pipeline) | Limited by the order: misses facts that need two analyses at once (Proposition 17.8.7) | sum of the passes · predictable | Each pass's output is inspectable (-print-changed) |
Low per pass, high to tune the pipeline | LLVM default<O2>, GCC passes.def |
| Combined analyses | At least every phase ordering of the combined analyses (Theorem 17.8.6), sometimes strictly more | \(O(I \cdot h)\) · comparable to one GVN | One fixed point; hard to debug when it does not converge | High (one transfer function that knows every fact) | LLVM NewGVN, GCC RPO VN / FRE |
| Equality saturation | Every rewrite order at once, if saturated (Theorem 17.8.9) | unbounded; needs limits · slow on AC rules | Extraction chooses by a cost model; equivalences can be explained (egg's proofs) | Medium (e-graph, e-matching, extraction); rules are declarative | Research, rewrite-heavy domains (tensor graphs, floating-point accuracy with Herbie), superoptimizers |
| Acyclic e-graphs (aegraph) | Eager single application of each rule; no saturation guarantee | near one pass · production JIT speed | Rules in ISLE, verifiable one by one | Medium–high (elaboration, bounds) | Cranelift's mid-end in Wasmtime |
Comparison-lab results (reproduce with build/<preset>/bin/ch17-compare --table labs/ch17-scalar/corpus/*.ll on a solution build): on the 12 corpus functions (48 blocks, 114 candidate instructions), simple CP finds 7 constants and SCCP 12, and SCCP proves 5 blocks unreachable. Hash-based (dominator-scoped) value numbering finds 15 redundant instructions and the AWZ partition finds 26. The running example run alone gives 0 vs 3 constants and 0 vs 3 congruences. The ★ LCM lab reduces the running TAC program from 24 to 17 dynamic evaluations (labs/ch17-lcm/inputs/running.tac).
Route through this chapter¶
| Step | What | Techniques | How it is exercised |
|---|---|---|---|
| 1 | Lesson 17.1 | Kildall CP, sparse CP, SCCP | drill sccp-trace; quiz; flashcards |
| 2 | Lesson 17.2 | LVI, CVP, ConstantRange, known bits, demanded bits | quiz; flashcards |
| 3 | Lesson 17.3 | mark–sweep DCE, ADCE, DSE | drill adce-marking; quiz |
| 4 | Lesson 17.4 | EarlyCSE, DVNT, LLVM GVN | quiz; flashcards |
| 5 | Lesson 17.5 | AWZ, optimistic RPO VN, NewGVN, GVN-hoist/sink | drill vn-partition; quiz |
| 6 | Lesson 17.6 | Morel–Renvoise, LCM, SSAPRE, GVN-PRE, load PRE | drill lcm-sets; quiz |
| 7 | Lesson 17.7 | SimplifyCFG, switch tables, jump threading | quiz; flashcards |
| 8 | Lesson 17.8 | phase ordering, combined analyses, equality saturation, aegraphs | quiz; flashcards |
| 9 | Exercises E1–E4 | Pebble implements SCCP, ADCE, DVNT and SimplifyCFG-lite | ./course test 17 |
| 10 | Comparison lab labs/ch17-scalar/ |
simple CP vs SCCP; hash VN vs AWZ partition | lab tests + ch17-compare --table |
| 11 | ★ labs labs/ch17-lcm/, labs/ch17-egraph/ |
lazy code motion on TAC; equality saturation | ch17.lab tests |
| 12 | Theory test | all | ./course quiz 17 (≥ 80 % to finish) |
Practice and check¶
./course drill sccp-trace --difficulty easy # warm up; --solution shows every step
./course drill vn-partition # AWZ rounds and the final partition
./course drill lcm-sets # the LCM sets of a small CFG
./course drill adce-marking # which instructions and branches ADCE keeps
./course flash 17 # daily, a few minutes
./course quiz 17 # after the lessons
./course test 17 # after the exercises and the lab
./course status # done = quiz ≥ 80 % and tests pass
References¶
The chapter's annotated bibliography (papers, textbook sections, pinned source files and documentation) is in references.md. Start with: [WZ91] (SCCP, and the dense/sparse × conditional/unconditional map of Lesson 17.1), [AWZ88] (congruence partitioning), [KRS94] (lazy code motion, with its optimality proofs), [CC95] (why analyses should be combined), and [WNW+21] (egg and equality saturation). [SSAB] and [EaC3] are the textbook companions.