Skip to content

References — Chapter 16 · Static Single Assignment Form

Every source this chapter cites, grouped by kind. Lessons cite entries inline as [KEY]; each entry says why and when to read it. Core reading marks the entries the chapter assumes you will open.

Foundational and research papers

  • [AH00] John Aycock and Nigel Horspool. Simple Generation of Static Single-Assignment Form. Compiler Construction (CC 2000), LNCS 1781, 2000. doi:10.1007/3-540-46423-9_8
    Why and when: Build "maximal" SSA (a phi for every variable at every join), then delete redundant phis with two rewrite rules until none applies; minimal for reducible CFGs. The second technique of Lesson 16.3 and the optional lab algorithm.
    Cited in: 03-construction-without-frontiers

  • [App98] Andrew W. Appel. SSA is Functional Programming. ACM SIGPLAN Notices 33(4), 1998.
    Why and when: Four pages arguing that an SSA procedure is a set of mutually recursive functions whose parameters are the phis; the shortest motivation for block arguments in Lesson 16.5.
    Note: Look it up by title in the ACM Digital Library (DOI not re-checked from the course container).
    Cited in: 05-phi-block-arguments-upsilon

  • [AWZ88] Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting Equality of Variables in Programs. Proc. 15th ACM POPL, pp. 1-11, 1988. doi:10.1145/73560.73561
    Why and when: The companion 1988 paper: SSA as the basis of partition-based value equality. Its notion of "values" returns in Boissinot et al.'s value-based interference (Lesson 16.7).
    Cited in: 01-ssa-properties-and-flavors, 07-parallel-copies-and-coalescing

  • [BBH+13] Matthias Braun, Sebastian Buchwald, Sebastian Hack, Roland Leißa, Christoph Mallon, and Andreas Zwinkau. Simple and Efficient Construction of Static Single Assignment Form. Compiler Construction (CC 2013), LNCS 7791, pp. 102-122, 2013. doi:10.1007/978-3-642-37051-9_6
    Why and when: Core reading. On-the-fly construction without dominance frontiers: local and global value numbering, sealed blocks, trivial-phi removal, minimality for reducible CFGs and SCC-based removal of redundant phi sets for irreducible ones, and measurements against LLVM's mem2reg. The algorithm of Lesson 16.3 and of lab L1's Braun part; read all of it.
    Cited in: overview, 01-ssa-properties-and-flavors, 03-construction-without-frontiers

  • [BCH+02] Zoran Budimlić, Keith D. Cooper, Timothy J. Harvey, Ken Kennedy, Timothy S. Oberg, and Steven W. Reeves. Fast Copy Coalescing and Live-Range Identification. Proc. ACM SIGPLAN PLDI 2002, 2002. doi:10.1145/512529.512534
    Why and when: The dominance-forest interference test that Boissinot et al. build on: in strict SSA two names interfere iff one is live at the definition of the other (Lemma 16.7.1).
    Cited in: 07-parallel-copies-and-coalescing

  • [BCHS98] Preston Briggs, Keith D. Cooper, Timothy J. Harvey, and L. Taylor Simpson. Practical Improvements to the Construction and Destruction of Static Single Assignment Form. Software: Practice and Experience 28(8), 1998. doi:10.1002/(SICI)1097-024X(19980710)28:8<859::AID-SPE188>3.0.CO;2-8
    Why and when: Core reading. Two contributions in one paper: semi-pruned SSA (phis only for names live across a block boundary, Definition 16.1.7) and the lost-copy and swap problems of naive destruction with their fixes (Lesson 16.6). Read the construction half with Lesson 16.1, the destruction half with Lesson 16.6; its phi-count tables back the comparison in Lesson 16.1 §5.
    Cited in: 01-ssa-properties-and-flavors, 06-ssa-destruction

  • [BDR+09] Benoit Boissinot, Alain Darte, Fabrice Rastello, Benoît Dupont de Dinechin, and Christophe Guillon. Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency. Proc. 7th IEEE/ACM International Symposium on Code Generation and Optimization (CGO 2009), 2009. doi:10.1109/CGO.2009.19
    Why and when: Core reading. The modern recipe of Lesson 16.7: isolate phis with parallel copies (Sreedhar's Method I made parallel), coalesce aggressively with value-based interference, check interference without an interference graph using dominance order and fast liveness, and sequentialize parallel copies with the minimum number of moves. Read it after Lesson 16.7.
    Cited in: overview, 06-ssa-destruction, 07-parallel-copies-and-coalescing

  • [BGS00] Rastislav Bodík, Rajiv Gupta, and Vivek Sarkar. ABCD: Eliminating Array Bounds Checks on Demand. Proc. ACM SIGPLAN PLDI 2000, 2000.
    Why and when: e-SSA (extended SSA): pi assignments after conditional branches, used to prove array bounds checks redundant on demand. LLVM's PredicateInfo implements the same idea.
    Note: Look it up by title in the ACM Digital Library (DOI not re-checked from the course container).
    Cited in: overview, 08-ssa-extensions

  • [BHG+08] Benoit Boissinot, Sebastian Hack, Daniel Grund, Benoît Dupont de Dinechin, and Fabrice Rastello. Fast Liveness Checking for SSA-Form Programs. Proc. 6th IEEE/ACM International Symposium on Code Generation and Optimization (CGO 2008), pp. 35-44, 2008. doi:10.1145/1356058.1356064
    Why and when: Liveness queries answered from the dominator tree and a precomputed reduced reachability, without liveness sets; the live-in check of Algorithm 16.7.4 cites it. Read it after Lesson 16.7.
    Cited in: 01-ssa-properties-and-flavors, 07-parallel-copies-and-coalescing

  • [BMO90] Robert A. Ballance, Arthur B. Maccabe, and Karl J. Ottenstein. The Program Dependence Web: A Representation Supporting Control-, Data-, and Demand-Driven Interpretation of Imperative Languages. Proc. ACM SIGPLAN PLDI 1990, 1990.
    Why and when: The origin of gated SSA: gamma, mu and eta gating functions that make the controlling predicate of a merge explicit. Lesson 16.8's gated-SSA section follows its definitions.
    Note: Look it up by title in the ACM Digital Library (DOI not re-checked from the course container).
    Cited in: 08-ssa-extensions

  • [CCF91] Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante. Automatic Construction of Sparse Data Flow Evaluation Graphs. Proc. 18th ACM POPL, pp. 55-66, 1991. doi:10.1145/99583.99594
    Why and when: Core reading. The origin of pruned SSA: place a phi only where the variable is live. Definition 16.1.7 and the LLVM setLiveInBlocks call are this idea.
    Cited in: 01-ssa-properties-and-flavors

  • [CCL+96] Fred Chow, Sun Chan, Shin-Ming Liu, Raymond Lo, and Mark Streich. Effective Representation of Aliases and Indirect Memory Operations in SSA Form. Compiler Construction (CC 1996), LNCS 1060, 1996. doi:10.1007/3-540-61053-7_66
    Why and when: Hashed SSA (HSSA): virtual variables, mu and chi operators for may-uses and may-defs, and hashing of expressions into a global value table; developed at SGI.
    Cited in: overview, 08-ssa-extensions

  • [CFRWZ91] Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM TOPLAS 13(4), pp. 451-490, 1991. doi:10.1145/115372.115320
    Why and when: Core reading. The construction every other method is measured against: minimal SSA defined, phi placement at iterated dominance frontiers (§5.1), renaming with one stack per variable (§5.2), the correctness argument (§5.3-5.4), the naive translation out of SSA (§7) and measurements of frontier sizes (§8). Read §2 and §5 with Lesson 16.2; §7 with Lesson 16.6.
    Cited in: overview, 01-ssa-properties-and-flavors, 02-frontier-based-construction, 05-phi-block-arguments-upsilon, 06-ssa-destruction

  • [FKS00] Stephen J. Fink, Kathleen Knobe, and Vivek Sarkar. Unified Analysis of Array and Object References in Strongly Typed Languages. Static Analysis Symposium (SAS 2000), LNCS 1824, 2000.
    Why and when: Heap Array SSA in the Jikes RVM optimizing compiler: one heap array per field or array type, used for redundant load elimination. The production use in Lesson 16.8's real-world box.
    Note: Look it up by title in the SpringerLink (DOI not re-checked from the course container).
    Cited in: 08-ssa-extensions

  • [Kel95] Richard A. Kelsey. A Correspondence between Continuation Passing Style and Static Single Assignment Form. ACM SIGPLAN Workshop on Intermediate Representations (IR '95), SIGPLAN Notices 30(3), 1995.
    Why and when: Phi functions as parameters of local continuations: the formal basis of block arguments (Lesson 16.5). Chapter 8 teaches the translation; reread it for the representation comparison.
    Note: Look it up by title in the ACM Digital Library (DOI not re-checked from the course container).
    Cited in: 05-phi-block-arguments-upsilon

  • [KS98] Kathleen Knobe and Vivek Sarkar. Array SSA Form and Its Use in Parallelization. Proc. 25th ACM POPL, 1998. doi:10.1145/268946.268956
    Why and when: Array SSA: element-level def-use through @ timestamps, definition phis after every array store and control phis at joins. Lesson 16.8's Array SSA section.
    Cited in: 08-ssa-extensions

  • [May89] Cathy May. The Parallel Assignment Problem Redefined. IEEE Transactions on Software Engineering 15(6), 1989.
    Why and when: The parallel assignment problem and its solution with a minimum number of moves, earlier than the SSA literature; background for Theorem 16.7.6.
    Note: Look it up by title in the IEEE Xplore (DOI not re-checked from the course container).
    Cited in: 07-parallel-copies-and-coalescing

  • [Nov07] Diego Novillo. Memory SSA — A Unified Approach for Sparsely Representing Memory Operations. Proceedings of the GCC Developers' Summit 2007, 2007.
    Why and when: Memory SSA as implemented in GCC: virtual operands (VDEF/VUSE) that version memory, with memory partitions. LLVM's MemorySSA documentation points to this paper and notes that GCC later moved to a single memory name, as LLVM uses. Read it with Lesson 16.8.
    Note: In the printed GCC Developers' Summit 2007 proceedings; the GCC wiki (MemorySSA page) links the paper.
    Cited in: 08-ssa-extensions

  • [RSL08] Laurence Rideau, Bernard Paul Serpette, and Xavier Leroy. Tilting at Windmills with Coq: Formal Verification of a Compilation Algorithm for Parallel Moves. Journal of Automated Reasoning 40(4), 2008.
    Why and when: A mechanically verified parallel-move sequentializer (the one CompCert uses) and the "windmill" picture of copy graphs behind Lesson 16.7's algorithm; read it for the algorithm and its invariant.
    Note: Look it up by title in the SpringerLink (DOI not re-checked from the course container).
    Cited in: 07-parallel-copies-and-coalescing

  • [RWZ88] Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Global Value Numbers and Redundant Computations. Proc. 15th ACM POPL, pp. 12-27, 1988. doi:10.1145/73560.73562
    Why and when: One of the two 1988 papers that introduced SSA names and phi functions, here as the substrate of global redundancy elimination. Historical background for Lesson 16.1 §1.
    Cited in: 01-ssa-properties-and-flavors

  • [SG95] Vugranam C. Sreedhar and Guang R. Gao. A Linear Time Algorithm for Placing φ-Nodes. Proc. 22nd ACM Symposium on Principles of Programming Languages (POPL), pp. 62-73, 1995. doi:10.1145/199448.199464
    Why and when: Core reading. DJ graphs and the level-ordered DF+ computation behind LLVM's IDFCalculator and Go's large-function phi placement (Lesson 16.2, Algorithm 16.2.4). Read the DJ-graph construction and the linear-time argument.
    Cited in: 02-frontier-based-construction

  • [SJGS99] Vugranam C. Sreedhar, Roy Dz-Ching Ju, David M. Gillies, and Vatsa Santhanam. Translating Out of Static Single Assignment Form. Static Analysis Symposium (SAS 1999), LNCS 1694, 1999. doi:10.1007/3-540-48294-6_13
    Why and when: Core reading. Conventional SSA, phi congruence classes, and three methods to reach CSSA before dropping the phis: I (copy everything), II (copy where interference graphs say so), III (copy only where live ranges really interfere). Lesson 16.6 §2-4 follows its definitions.
    Cited in: 01-ssa-properties-and-flavors, 05-phi-block-arguments-upsilon, 06-ssa-destruction

  • [TP95] Peng Tu and David Padua. Efficient Building and Placing of Gating Functions. Proc. ACM SIGPLAN PLDI 1995, 1995.
    Why and when: Builds gating functions for arbitrary reducible CFGs with gating path expressions; Lesson 16.8's Algorithm 16.8.6 is the structured special case. Read it for the general construction.
    Note: Look it up by title in the ACM Digital Library (DOI not re-checked from the course container).
    Cited in: 08-ssa-extensions

Textbooks and monographs

  • [Appel] Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998. Read: §19.1 Converting to SSA form; §19.6 Converting back from SSA form; §19.7 A functional intermediate form.
    Why and when: Cytron's algorithm with complete code and the functional (block-argument) view of SSA; read §19.1 with Lesson 16.2 and §19.7 with Lesson 16.5. The C and Java editions share the numbering.
    Cited in: 02-frontier-based-construction

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: §9.3 Static Single-Assignment Form (placing phi-functions, renaming, translation out of SSA, the lost-copy and swap problems).
    Why and when: The gentlest complete treatment of semi-pruned construction and of destruction, by two of the Briggs et al. authors. Read §9.3 before Lesson 16.2 if the proofs feel compressed.

  • [SSAB] Fabrice Rastello and Florent Bouchez Tichadou. SSA-based Compiler Design. Springer, 2022. Read: Ch. 2 Properties and Flavors; Ch. 3 Standard Construction and Destruction Algorithms; Ch. 4 Advanced Construction Algorithms for SSA; Ch. 5 SSA Reconstruction; Ch. 13 Static Single Information Form; Ch. 14 Graphs and Gating Functions; Ch. 16 Hashed SSA Form: HSSA; Ch. 17 Array SSA Form; Ch. 21 SSA Destruction for Machine Code; Ch. 22 Register Allocation. doi:10.1007/978-3-030-80515-9
    Why and when: Core reading. The reference on everything in this chapter, by the researchers who wrote most of the destruction and extension papers. Read Ch. 2-3 alongside Lessons 16.1-16.2, Ch. 4-5 with Lessons 16.2-16.4, Ch. 21 with Lessons 16.6-16.7 (it has the parallel-copy algorithm in full) and Ch. 13-17 with Lesson 16.8.
    Cited in: overview, 01-ssa-properties-and-flavors, 02-frontier-based-construction, 04-llvm-mem2reg-sroa-ssaupdater, 06-ssa-destruction, 07-parallel-copies-and-coalescing

Theses and technical reports

  • [Ana99] C. Scott Ananian. The Static Single Information Form. Master's thesis, Massachusetts Institute of Technology (MIT-LCS-TR-801), 1999.
    Why and when: SSI: sigma functions at branches as the dual of phis at joins, so every use sees facts about the path it is on. The definition behind Lesson 16.8's SSI section.
    Note: MIT Laboratory for Computer Science technical report MIT-LCS-TR-801.
    Cited in: 08-ssa-extensions

  • [Hack07] Sebastian Hack. Register Allocation for Programs in SSA Form. PhD thesis, Universität Karlsruhe (TH), 2007.
    Why and when: SSA interference graphs are chordal, so SSA programs can be register-allocated before leaving SSA; spilling and coalescing on SSA. The preview in Lesson 16.7 §6 and the SSA-based allocator of Ch 22 start here.
    Note: Published by Universitätsverlag Karlsruhe; the KIT library repository hosts the PDF.
    Cited in: 07-parallel-copies-and-coalescing

Source code (pinned versions)

  • [CL-IR] Cranelift IR reference (block parameters) — cranelift/docs/ir.md in bytecodealliance/wasmtime at v37.0.2. Symbols: Basic blocks.
    Why and when: Cranelift's definition of block parameters and of branch arguments; read with the Cranelift box of Lessons 16.3 and 16.5.
    Cited in: 05-phi-block-arguments-upsilon

  • [CL-SSA] Cranelift's SSA construction (Braun et al.) behind FunctionBuilder variables — cranelift/frontend/src/ssa.rs in bytecodealliance/wasmtime at v37.0.2. Symbols: SSABuilder, SSABuilder::use_var, SSABuilder::seal_block.
    Why and when: Braun's algorithm producing block parameters instead of phis; the Wasm translator declares one variable per Wasm local. Lessons 16.3 and 16.5.
    Cited in: 03-construction-without-frontiers

  • [GCC-Coalesce] GCC's SSA-name coalescing into partitions — gcc/tree-ssa-coalesce.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: build_ssa_conflict_graph, coalesce_partitions, live_track_process_def.
    Why and when: Conflict graph with Chaitin's copy exception and a cost-sorted coalesce list; the partitions are Sreedhar's phi congruence classes after coalescing (Lesson 16.6-16.7 boxes).
    Cited in: 07-parallel-copies-and-coalescing

  • [GCC-IntoSSA] GCC's SSA construction (Cytron et al. with dead-phi pruning) — gcc/tree-into-ssa.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: insert_phi_nodes, insert_phi_nodes_for, prune_unused_phi_nodes, rewrite_stmt.
    Why and when: IDF-based phi placement followed by prune_unused_phi_nodes, which keeps only phis that reach a use: pruned SSA computed as "minimal minus dead phis" (Theorem 16.1.10).
    Cited in: 01-ssa-properties-and-flavors, 02-frontier-based-construction

  • [GCC-OutOfSSA] GCC's translation out of SSA (per-edge elimination graphs) — gcc/tree-outof-ssa.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: eliminate_phi, elim_create, insert_partition_copy_on_edge, insert_backedge_copies.
    Why and when: Copies on edges between coalesced partitions, ordered by an elimination graph with a temporary for cycles: GCC's parallel-copy sequentializer (Lesson 16.7).
    Cited in: 07-parallel-copies-and-coalescing

  • [Go-Regalloc] The Go register allocator's edge shuffles (parallel copies on edges) — src/cmd/compile/internal/ssa/regalloc.go in golang/go at go1.24.7. Symbols: edgeState.shuffle, edgeState.processDest, edgeState.findRegFor.
    Why and when: Phi arguments become register-to-register moves on each edge, resolved as a parallel copy with a free register for cycles; the parallel-copy real-world box of Lesson 16.7.
    Cited in: 07-parallel-copies-and-coalescing

  • [Go-SSAGen] The Go compiler's phi placement (Braun below 500 blocks, Sreedhar-Gao above) — src/cmd/compile/internal/ssagen/phi.go in golang/go at go1.24.7. Symbols: state.insertPhis, phiState.insertPhis, phiState.insertVarPhis, simplePhiState.insertPhis, smallBlocks.
    Why and when: Two construction algorithms in one file, chosen by function size; the large-function path considers only variables read before written in some block (semi-pruned SSA). Lessons 16.1 and 16.3 real-world boxes use the Go 1.24.7 toolchain.
    Cited in: 01-ssa-properties-and-flavors, 02-frontier-based-construction, 03-construction-without-frontiers

  • [Jikes-ArraySSA] Heap Array SSA in the Jikes RVM optimizing compiler — rvm/src/org/jikesrvm/compilers/opt/ssa/SSADictionary.java in JikesRVM/JikesRVM at 3.1.4. Symbols: SSADictionary, HeapVariable, HeapOperand.
    Why and when: The production implementation of [FKS00]: heap variables per type, with phi and definition operands kept in a lookaside dictionary. Lesson 16.8.
    Cited in: 08-ssa-extensions

  • [LLVM-IDF] LLVM's Sreedhar-Gao iterated dominance frontier (IDFCalculator) — llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: IDFCalculatorBase::calculate, IDFCalculatorBase::setLiveInBlocks.
    Why and when: The DJ-graph walk of Algorithm 16.2.4 with the live-in filter that makes the result pruned SSA; the "find it in LLVM" task of Lesson 16.2 starts here.
    Cited in: 02-frontier-based-construction

  • [LLVM-InstSimplify] InstSimplify's phi folding (all incoming values equal, undef, self references) — llvm/lib/Analysis/InstructionSimplify.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: simplifyPHINode.
    Why and when: The rules mem2reg applies to its new phis at the end, and Aycock-Horspool's two reduction rules in production form (Lesson 16.3 §7).
    Cited in: 03-construction-without-frontiers

  • [LLVM-Mem2Reg] LLVM's mem2reg (promote allocas to SSA registers) — llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: isAllocaPromotable, PromoteMem2Reg::run, rewriteSingleStoreAlloca, promoteSingleBlockAlloca, PromoteMem2Reg::ComputeLiveInBlocks, PromoteMem2Reg::RenamePass.
    Why and when: Core reading. The production version of exercise E1: the promotability test, the single-store and single-block fast paths, live-in blocks for pruned SSA, IDFCalculator, the renaming worklist and the final simplifyInstruction loop over the new phis. Read with Lesson 16.4.
    Cited in: overview, 01-ssa-properties-and-flavors, 04-llvm-mem2reg-sroa-ssaupdater

  • [LLVM-Mem2RegPass] The mem2reg pass wrapper (which allocas are collected, the repeat loop) — llvm/lib/Transforms/Utils/Mem2Reg.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: promoteMemoryToRegister, PromotePass::run.
    Why and when: Collects promotable allocas of the entry block and repeats until none is left; the "rounds" of Algorithm 16.4.3.
    Cited in: 04-llvm-mem2reg-sroa-ssaupdater

  • [LLVM-MSSA] LLVM's MemorySSA (one memory variable, MemoryDef/MemoryUse/MemoryPhi) — llvm/lib/Analysis/MemorySSA.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MemorySSA::buildMemorySSA, MemorySSA::placePHINodes, MemorySSA::renamePass, ClobberWalker.
    Why and when: Memory SSA built with IDFCalculator and renaming exactly as in Lesson 16.2, plus the clobber walker that makes uses precise lazily. Read with Lesson 16.8.
    Cited in: 08-ssa-extensions

  • [LLVM-PHIElim] LLVM's machine-level phi elimination (copies in predecessors, critical-edge splitting) — llvm/lib/CodeGen/PHIElimination.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PHIEliminationImpl::LowerPHINode, PHIEliminationImpl::SplitPHIEdges.
    Why and when: Destruction in LLVM's back end: a fresh virtual register per phi, a COPY at the end of each predecessor and one at the block start (Sreedhar's Method I), and edge splitting when the incoming value is live past the phi. Lessons 16.6-16.7.
    Cited in: 06-ssa-destruction

  • [LLVM-PredicateInfo] LLVM's PredicateInfo (e-SSA copies after branches and assumes) — llvm/lib/Transforms/Utils/PredicateInfo.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PredicateInfoBuilder::buildPredicateInfo, PredicateInfoBuilder::renameUses.
    Why and when: e-SSA in LLVM: bitcast copies (formerly ssa.copy intrinsics) on the edges of conditional branches, consumed by SCCP and NewGVN. Lesson 16.8's SSI/e-SSA box.
    Cited in: 08-ssa-extensions

  • [LLVM-RegCoalescer] LLVM's register coalescer (value-numbered live intervals) — llvm/lib/CodeGen/RegisterCoalescer.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: JoinVals::analyzeValue, JoinVals::valuesIdentical, RegisterCoalescer::joinCopy.
    Why and when: The coalescing phase after PHIElimination; JoinVals compares value numbers, not just live ranges, so copies of one value do not interfere (Lesson 16.7).
    Cited in: 07-parallel-copies-and-coalescing

  • [LLVM-SROA] Scalar replacement of aggregates (SROA), which ends by calling PromoteMemToReg — llvm/lib/Transforms/Scalar/SROA.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SROA::runOnAlloca, AllocaSlices, SROA::promoteAllocas.
    Why and when: Splits aggregate allocas into per-field slices and promotes the slices; Lesson 16.4 §2 and the SROA real-world box.
    Cited in: 04-llvm-mem2reg-sroa-ssaupdater

  • [LLVM-SSAUpdater] LLVM's SSAUpdater (repair SSA after a value is duplicated) — llvm/lib/Transforms/Utils/SSAUpdater.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SSAUpdater::AddAvailableValue, SSAUpdater::GetValueInMiddleOfBlock, SSAUpdater::RewriteUse.
    Why and when: The on-demand, Braun-like SSA repair used by loop rotation, jump threading and LCSSA; the search itself is in llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h (SSAUpdaterImpl::GetValue, FindDominators, FindExistingPHI). Lesson 16.4 §2.
    Cited in: 04-llvm-mem2reg-sroa-ssaupdater

  • [LLVM-SSAUpdaterBulk] SSAUpdaterBulk (many variables at once, via IDFCalculator) — llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SSAUpdaterBulk::RewriteAllUses, ComputeLiveInBlocks.
    Why and when: The frontier-based alternative to SSAUpdater for many rewritten values: live-in blocks plus IDFCalculator, exactly Cytron-style pruned placement. Lesson 16.4 §6.
    Cited in: 04-llvm-mem2reg-sroa-ssaupdater

  • [SIL-Docs] Swift Intermediate Language reference (basic blocks take arguments) — docs/SIL.rst in swiftlang/swift at swift-6.1-RELEASE. Symbols: Basic Blocks.
    Why and when: SIL's block arguments ("instead of phi nodes, SIL uses basic block arguments") and the rule that branch operands match them; Lesson 16.5.
    Cited in: 05-phi-block-arguments-upsilon

  • [WebKit-B3] B3's Phi and Upsilon opcodes (JavaScriptCore's back-end IR) — Source/JavaScriptCore/b3/B3Opcode.h in WebKit/WebKit at WebKit-7622.2.11.14.6. Symbols: Upsilon, Phi, UpsilonValue (b3/B3UpsilonValue.h), validatePhisAreDominatedByUpsilons (b3/B3Validate.cpp).
    Why and when: Upsilon/phi SSA in a production JIT: Upsilons store to a phi's shadow variable in the predecessors; the validator checks that every path to a Phi passes an Upsilon. Lesson 16.5.
    Cited in: 05-phi-block-arguments-upsilon

Official documentation and specifications

  • [LLVM-LangRefPhi] LLVM Language Reference Manual — 'phi' instruction. LLVM 23.1.2. link
    Why and when: The normative phi rules: at the top of the block, one incoming value per predecessor, and at run time the phi "logically takes on the value specified by the pair corresponding to the predecessor basic block that executed just prior to the current block". Lesson 16.1 §2.
    Cited in: 05-phi-block-arguments-upsilon

  • [LLVM-MemorySSADoc] LLVM MemorySSA documentation. LLVM 23.1.2. link
    Why and when: MemoryDef, MemoryUse, MemoryPhi, liveOnEntry, the walker API and the "use optimization" invariant; read with Lesson 16.8 before using MemorySSA in Ch 19.
    Cited in: 08-ssa-extensions

  • [MLIR-Rationale] MLIR Rationale — "Block Arguments vs PHI nodes". LLVM 23.1.2. link
    Why and when: Why MLIR chose block arguments ("representationally identical" to phis): no phis to skip at block tops, entry-block arguments replace function arguments, no atomically executing phi groups (it names the lost-copy problem), no long unordered predecessor lists. Lesson 16.5.
    Cited in: 05-phi-block-arguments-upsilon

Blog posts and articles

  • [Piz25] Filip Pizlo. Pizlo SSA Form (short version). 2025. link
    Why and when: The author of B3 explains Phi/Upsilon form: every phi has a shadow variable that Upsilons assign, so blocks know nothing about SSA. Extra reading for Lesson 16.5 (the design itself dates from B3, 2015; see [WebKit-B3]).
    Cited in: 05-phi-block-arguments-upsilon