Skip to content

References — Chapter 17 · SSA-Based Scalar Optimizations

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

  • [AWZ88] Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting Equality of Variables in Programs. POPL 1988, pp. 1–11, 1988. doi:10.1145/73560.73561
    Why and when: Core reading. Congruence partitioning on the SSA value graph: start optimistic, split with Hopcroft's algorithm, get the coarsest stable partition. Lesson 17.5 §2–4 is §3–5 of the paper; the lab implements it.
    Cited in: overview, 05-partition-and-optimistic-gvn

  • [BC94] Preston Briggs and Keith D. Cooper. Effective Partial Redundancy Elimination. PLDI 1994, pp. 159–170, 1994.
    Why and when: Why lexical PRE misses redundancies and how global reassociation plus value-based naming recovers them; motivation for GVN-PRE (Lesson 17.6 §6).
    Note: ACM Digital Library; DOI not re-checked from the course container (look it up by title).
    Cited in: 06-partial-redundancy-elimination

  • [BCS97] Preston Briggs, Keith D. Cooper, and L. Taylor Simpson. Value Numbering. Software: Practice and Experience 27(6), pp. 701–724, 1997.
    Why and when: Core reading. Hash-based value numbering from local to superlocal to dominator-based (DVNT), and SCC-based value numbering, compared on real code. Lesson 17.4's DVNT is their Figure for DVNT; the measurements back Lesson 17.5 §5.
    Note: Wiley Online Library.
    Cited in: 04-dominator-scoped-redundancy, 05-partition-and-optimistic-gvn

  • [CC95] Cliff Click and Keith D. Cooper. Combining Analyses, Combining Optimizations. ACM TOPLAS 17(2), pp. 181–196, 1995.
    Why and when: Why solving constant propagation, unreachable code and value numbering together beats any fixed order of the separate passes: the theory behind Lessons 17.1 §4 and 17.8. Read §2–4 after Lesson 17.8 §1.
    Note: ACM Digital Library; DOI not re-checked from the course container (look it up by title).
    Cited in: overview, 01-constant-propagation, 05-partition-and-optimistic-gvn, 08-phase-ordering-and-equality-saturation

  • [CCK+97] Fred Chow, Sun Chan, Robert Kennedy, Shin-Ming Liu, Raymond Lo, and Peng Tu. A New Algorithm for Partial Redundancy Elimination based on SSA Form. PLDI 1997, pp. 273–286, 1997.
    Why and when: SSAPRE: PRE on SSA form expression by expression, via Φ-insertion, renaming, DownSafety, WillBeAvail, Finalize and CodeMotion. Lesson 17.6 §2 (SSAPRE) follows its six steps.
    Note: ACM Digital Library; DOI not re-checked from the course container (look it up by title).
    Cited in: 06-partial-redundancy-elimination

  • [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. Besides SSA and control dependence, §7.1 is the aggressive dead-code elimination of Lesson 17.3: mark from the roots through data and control dependences, then rewrite dead branches to the nearest marked post-dominator.
    Cited in: 03-dead-code-elimination

  • [Cli95] Cliff Click. Global Code Motion / Global Value Numbering. PLDI 1995, pp. 246–257, 1995. doi:10.1145/207110.207154
    Why and when: Hash-based GVN on the sea of nodes plus global code motion: why a hash table suffices when scheduling is done afterwards. Read §3 with Lesson 17.5 §6.

  • [DS88] Karl-Heinz Drechsler and Manfred P. Stadel. A Solution to a Problem with Morel and Renvoise's "Global Optimization by Suppression of Partial Redundancies". ACM TOPLAS 10(4), pp. 635–640, 1988.
    Why and when: Morel–Renvoise can miss insertions that need a new block on a critical edge; inserting on edges fixes it. Read after Lesson 17.6 §6.
    Note: ACM Digital Library; DOI not re-checked from the course container (look it up by title).
    Cited in: 06-partial-redundancy-elimination

  • [DS93] Karl-Heinz Drechsler and Manfred P. Stadel. A Variation of Knoop, Rüthing, and Steffen's Lazy Code Motion. ACM SIGPLAN Notices 28(5), pp. 29–38, 1993.
    Why and when: LCM on basic blocks with insertions on edges (EARLIEST, LATER, LATERIN, INSERT, DELETE): the formulation of Algorithm 17.6.6, the drill lcm-sets and the ★ lab.
    Note: ACM Digital Library; DOI not re-checked from the course container (look it up by title).
    Cited in: 06-partial-redundancy-elimination

  • [FOW87] Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The Program Dependence Graph and Its Use in Optimization. ACM TOPLAS 9(3), pp. 319–349, 1987. doi:10.1145/24039.24041
    Why and when: Control dependence from post-dominance, the relation ADCE marks through (Lesson 17.3 §2); read §2–3 if Ch 15's Lesson 15.4 is not fresh.

  • [Gar02] Karthik Gargi. A Sparse Algorithm for Predicated Global Value Numbering. PLDI 2002, pp. 45–56, 2002.
    Why and when: Complete optimistic GVN with value inference and predicates, touching only instructions whose inputs changed: the design LLVM's NewGVN implements (Lesson 17.5 §2). Read §3–5.
    Note: ACM Digital Library; DOI not re-checked from the course container (look it up by title).
    Cited in: 05-partition-and-optimistic-gvn

  • [GN04] Sumit Gulwani and George C. Necula. A Polynomial-Time Algorithm for Global Value Numbering. SAS 2004, LNCS 3148, pp. 212–227, 2004.
    Why and when: What "complete" GVN means (Herbrand equivalence over all paths) and how to reach it in polynomial time; Lesson 17.5 §4 uses their definition to place AWZ and hash-based GVN.
    Note: SpringerLink; DOI not re-checked from the course container (look it up by title).
    Cited in: 05-partition-and-optimistic-gvn

  • [KCL+99] Robert Kennedy, Sun Chan, Shin-Ming Liu, Raymond Lo, Peng Tu, and Fred Chow. Partial Redundancy Elimination in SSA Form. ACM TOPLAS 21(3), pp. 627–676, 1999.
    Why and when: The journal version of [CCK+97] with the correctness and optimality proofs and the extensions (speculation, strength reduction). Theorem 17.6.16 points here for the full proof.
    Note: ACM Digital Library; DOI not re-checked from the course container (look it up by title).
    Cited in: 06-partial-redundancy-elimination

  • [Kil73] Gary A. Kildall. A unified approach to global program optimization. POPL 1973, 194–206, 1973. doi:10.1145/512927.512945
    Why and when: The dense iterative algorithm and constant propagation as its first instance: the "simple constant" baseline of Lesson 17.1. Read §3–4 after Lesson 17.1 §2 to see the per-point environments that sparse methods get rid of.
    Cited in: 01-constant-propagation

  • [KRS92] Jens Knoop, Oliver Rüthing, and Bernhard Steffen. Lazy Code Motion. PLDI 1992, pp. 224-234, 1992. doi:10.1145/143095.143136
    Why and when: Core reading. PRE decomposed into unidirectional problems (down-safety, earliest, delay/latest, isolated) with computational and lifetime optimality. Lesson 17.6 §2–4 follows it.
    Cited in: 06-partial-redundancy-elimination

  • [KRS94] Jens Knoop, Oliver Rüthing, and Bernhard Steffen. Optimal Code Motion: Theory and Practice. ACM TOPLAS 16(4), pp. 1117–1155, 1994.
    Why and when: The journal version of [KRS92] with full proofs of computational and lifetime optimality; Lemma 17.6.12 and Theorems 17.6.13–17.6.14 cite it for the complete arguments.
    Note: ACM Digital Library; DOI not re-checked from the course container (look it up by title).
    Cited in: overview, 06-partial-redundancy-elimination

  • [MR79] Etienne Morel and Claude Renvoise. Global optimization by suppression of partial redundancies. Communications of the ACM 22(2), pp. 96-103, 1979. doi:10.1145/359060.359069
    Why and when: Core reading. Partial-redundancy elimination as one bidirectional bit-vector system (PPIN/PPOUT, INSERT, DELETE). Lesson 17.6 §2 states it in full; read the paper for its examples and for why the bidirectional system is hard to solve fast.
    Cited in: 06-partial-redundancy-elimination

  • [NO80] Greg Nelson and Derek C. Oppen. Fast Decision Procedures Based on Congruence Closure. Journal of the ACM 27(2), pp. 356–364, 1980. doi:10.1145/322186.322198
    Why and when: Congruence closure with union-find: the invariant an e-graph maintains (Definition 17.8.2) and the same "congruence" AWZ partitions compute from the other side.
    Cited in: 08-phase-ordering-and-equality-saturation

  • [RL77] John H. Reif and Harry R. Lewis. Symbolic Evaluation and the Global Value Graph. POPL 1977, pp. 104–118, 1977.
    Why and when: Sparse constant propagation over def-use ("global value graph") edges instead of program points: the "sparse simple constant" algorithm of Lesson 17.1 §2. Read §2 for the graph, skip the symbolic-evaluation generalization on a first pass.
    Note: ACM Digital Library; DOI not re-checked from the course container (look it up by title).
    Cited in: 01-constant-propagation

  • [RL86] John H. Reif and Harry R. Lewis. Efficient Symbolic Analysis of Programs. Journal of Computer and System Sciences 32(3), pp. 280–314, 1986.
    Why and when: The journal version of [RL77] with the complexity analysis quoted in Lesson 17.1 §5; optional reading.
    Note: ScienceDirect; DOI not re-checked from the course container (look it up by title).
    Cited in: 01-constant-propagation

  • [RWZ88] Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Global Value Numbers and Redundant Computations. POPL 1988, pp. 12–27, 1988. doi:10.1145/73560.73562
    Why and when: The companion paper: using value numbers to move and delete redundant computations, a precursor of GVN-PRE (Lesson 17.6 §6). Optional.

  • [TSTL09] Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. Equality Saturation: A New Approach to Optimization. POPL 2009, pp. 264–276, 2009. doi:10.1145/1480881.1480915
    Why and when: Equality saturation as a cure for phase ordering: apply every rewrite non-destructively, then extract. Lesson 17.8 §1–2 starts here.
    Cited in: 08-phase-ordering-and-equality-saturation

  • [VH04] Thomas VanDrunen and Antony L. Hosking. Value-Based Partial Redundancy Elimination. Compiler Construction (CC 2004), LNCS 2985, pp. 167–184, 2004.
    Why and when: GVN-PRE: anticipation and availability over value numbers, with phi-translation, so PRE also removes redundancies that are not lexically identical. GCC's tree PRE is built on it (Lesson 17.6 §7).
    Note: SpringerLink; DOI not re-checked from the course container (look it up by title).
    Cited in: 06-partial-redundancy-elimination

  • [Weg75] Ben Wegbreit. Property Extraction in Well-Founded Property Sets. IEEE Transactions on Software Engineering SE-1(3), pp. 270–285, 1975.
    Why and when: The origin of conditional constant propagation on dense dataflow: only edges whose branch condition allows them contribute (the CC algorithm of [WZ91]). Read after Lesson 17.1 §6 for the dense ancestor of SCCP.
    Note: IEEE Xplore; DOI not re-checked from the course container (look it up by title).
    Cited in: 01-constant-propagation

  • [WNW+21] Max Willsey, Chandrakana Nandi, Yisu Remy Wang, Oliver Flatt, Zachary Tatlock, and Pavel Panchekha. egg: Fast and Extensible Equality Saturation. Proc. ACM on Programming Languages 5 (POPL), Article 23, 2021. doi:10.1145/3434304
    Why and when: Core reading. Rebuilding (§3) and e-class analyses (§4): Algorithm 17.8.4 and the ★ e-graph lab follow it, and the lab's class and node counts match egg 0.11's on the lab inputs.
    Cited in: overview, 08-phase-ordering-and-equality-saturation

  • [WZ91] Mark N. Wegman and F. Kenneth Zadeck. Constant Propagation with Conditional Branches. ACM TOPLAS 13(2), pp. 181-210, 1991. doi:10.1145/103135.103136
    Why and when: Core reading. SCCP and its three siblings (SC, SSC, CC) in one framework, with the proof that SCCP is at least as strong as constant propagation and unreachable-code elimination iterated. Lesson 17.1 follows §2–5; Theorem 17.1.12 is their §4 restated for SSA.
    Cited in: overview, 01-constant-propagation

Textbooks and monographs

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: Ch. 8 (Introduction to optimization: superlocal and dominator-based value numbering), Ch. 10 (Scalar optimization: useless and unreachable code, lazy code motion, sparse conditional constant propagation).
    Why and when: The textbook formulations Lessons 17.3, 17.4 and 17.6 use (DVNT, the Dead/Clean algorithms, LCM with EARLIEST/LATER/INSERT/DELETE); read Ch. 10 after Lesson 17.3.
    Cited in: overview, 03-dead-code-elimination, 04-dominator-scoped-redundancy, 06-partial-redundancy-elimination, 07-cfg-simplification

  • [Muchnick] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. Read: Ch. 12 (Early optimizations: value numbering, constant propagation, SCCP), Ch. 13 (Redundancy elimination: common-subexpression elimination, code hoisting, partial-redundancy elimination), §18.10 (dead-code elimination).
    Why and when: Complete ICAN pseudo-code for SCCP, global CSE, Morel–Renvoise and Knoop–Rüthing–Steffen; the reference GCC's gcse.cc cites. Read Ch. 13 with Lesson 17.6.

  • [SSAB] Fabrice Rastello and Florent Bouchez Tichadou. SSA-based Compiler Design. Springer, 2022. Read: Ch. 8 (Propagating information using SSA: SCCP), Ch. 11 (Redundancy elimination: SSAPRE, speculative PRE, value-based redundancy elimination). doi:10.1007/978-3-030-80515-9
    Why and when: The SSA-centric treatment of Lessons 17.1 and 17.6: read Ch. 8 alongside Lesson 17.1 and Ch. 11 alongside Lesson 17.6 §2 (SSAPRE) and §6 (GVN-PRE).
    Cited in: overview, 06-partial-redundancy-elimination

Theses and technical reports

  • [Cli95t] Clifford Noel Click Jr.. Combining Analyses, Combining Optimizations. PhD thesis, Rice University, 1995.
    Why and when: Optimistic combined constant propagation and value numbering by SCCs, with the proofs that [CC95] only sketches (Lesson 17.5 §2 and Lesson 17.8 §4).
    Note: Rice University Ph.D. thesis (also a Rice CS technical report); available from Rice's repository.
    Cited in: 01-constant-propagation, 05-partition-and-optimistic-gvn, 08-phase-ordering-and-equality-saturation

  • [Sim96] L. Taylor Simpson. Value-Driven Redundancy Elimination. PhD thesis, Rice University, 1996.
    Why and when: SCC-based value numbering (the optimistic RPO algorithm NewGVN's header cites) and value-based code motion. Read Ch. 3–4 after Lesson 17.5 §6.
    Note: Rice University Ph.D. thesis (also a Rice CS technical report).
    Cited in: 04-dominator-scoped-redundancy, 05-partition-and-optimistic-gvn

Source code (pinned versions)

  • [CL-Arith] Cranelift's arithmetic rewrite rules (ISLE) — cranelift/codegen/src/opts/arithmetic.isle in bytecodealliance/wasmtime at v37.0.2. Symbols: simplify.
    Why and when: What an aegraph rule looks like in production; compare with the lab's rules files (Lesson 17.8 §7).
    Cited in: 08-phase-ordering-and-equality-saturation

  • [CL-Egraph] Cranelift's aegraph mid-end — cranelift/codegen/src/egraph.rs in bytecodealliance/wasmtime at v37.0.2. Symbols: EgraphPass, EgraphPass::run.
    Why and when: A production acyclic e-graph with elaboration back into a CFG (Lesson 17.8 §7); its rewrite rules are ISLE files under cranelift/codegen/src/opts/.
    Cited in: 08-phase-ordering-and-equality-saturation

  • [GCC-CCP] GCC's conditional constant propagation on SSA — gcc/tree-ssa-ccp.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: ccp_lattice_t, likely_value.
    Why and when: Wegman–Zadeck CCP with a four-level lattice; compare likely_value with Algorithm 17.1.8's operand rule.
    Cited in: 01-constant-propagation

  • [GCC-CPROP] GCC's global constant/copy propagation on RTL (dense, available sets) — gcc/cprop.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: one_cprop_pass.
    Why and when: Kildall-style dense propagation over available assignments, still in GCC's RTL pipeline (Lesson 17.1's Kildall box).
    Cited in: 01-constant-propagation

  • [GCC-DCE] GCC's DCE and control-dependence DCE (cddce) — gcc/tree-ssa-dce.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: find_obviously_necessary_stmts, mark_control_dependent_edges_necessary, perform_tree_ssa_dce.
    Why and when: Mark-sweep DCE and its aggressive variant in one file; its finite-loop test is the GCC answer to "may not terminate" (Lesson 17.3 §7).
    Cited in: 03-dead-code-elimination

  • [GCC-GCSE] GCC's RTL global CSE and PRE — gcc/gcse.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: one_pre_gcse_pass.
    Why and when: Its header lists the literature from Morel–Renvoise to lazy code motion; RTL PRE on top of lcm.cc (Lesson 17.6 §7).
    Cited in: 06-partial-redundancy-elimination

  • [GCC-LCM] GCC's generic lazy code motion on edges — gcc/lcm.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: pre_edge_lcm, compute_antinout_edge, compute_earliest, compute_laterin.
    Why and when: Algorithm 17.6.6 as a reusable library: ANTIN/ANTOUT, EARLIEST, LATERIN, INSERT and DELETE over bitmaps, shared by PRE and other placement problems.
    Cited in: 06-partial-redundancy-elimination

  • [GCC-PRE] GCC's tree PRE (GVN-PRE), FRE and code hoisting — gcc/tree-ssa-pre.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: compute_antic, do_pre_regular_insertion.
    Why and when: ANTIC_IN/ANTIC_OUT over value expressions with phi-translation, insertion, and the hoisting pass that shares its sets (Lesson 17.6 §7's box prints them).
    Cited in: 06-partial-redundancy-elimination

  • [GCC-SCCVN] GCC's value numbering over SSA, in RPO — gcc/tree-ssa-sccvn.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: do_rpo_vn, run_rpo_vn.
    Why and when: Optimistic RPO value numbering iterated over loop SCCs (Simpson's descendant), used by FRE and PRE (Lesson 17.5 §7).
    Cited in: 04-dominator-scoped-redundancy, 05-partition-and-optimistic-gvn, 08-phase-ordering-and-equality-saturation

  • [LLVM-ADCE] Aggressive dead code elimination via post-dominance frontiers — llvm/lib/Transforms/Scalar/ADCE.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences, AggressiveDeadCodeElimination::updateDeadRegions.
    Why and when: Cytron's marking with a ReverseIDFCalculator, the adce-remove-loops switch for loops that might not terminate, and dead-branch rewriting to the successor nearest the exit (Lesson 17.3 §7).
    Cited in: 03-dead-code-elimination

  • [LLVM-BDCE] Bit-tracking dead code elimination — llvm/lib/Transforms/Scalar/BDCE.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: bitTrackingDCE.
    Why and when: Deletes instructions none of whose bits are demanded, and clears assumptions (flags) that no longer hold (Lesson 17.2 §7, Lesson 17.3 §6).
    Cited in: 02-range-and-bit-analyses

  • [LLVM-ConstantRange] ConstantRange, the wrapped-interval domain — llvm/lib/IR/ConstantRange.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ConstantRange::add, ConstantRange::multiply, ConstantRange::unionWith.
    Why and when: The abstract transformers of Lesson 17.2 §2 (add, multiply, union of wrapped intervals); compare add with the proof of Lemma 17.2.5.
    Cited in: 02-range-and-bit-analyses

  • [LLVM-CVP] Correlated value propagation (LVI-driven rewrites) — llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: narrowSDivOrSRem, processUDivOrURem.
    Why and when: What LVI's facts buy: signed-to-unsigned division, narrowing, nuw/nsw inference, folded compares (Lesson 17.2 §7).
    Cited in: 02-range-and-bit-analyses

  • [LLVM-DCE] LLVM's worklist dead-code elimination (and ADCE.cpp for the aggressive variant) — llvm/lib/Transforms/Scalar/DCE.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: eliminateDeadCode, DCEInstruction.
    Why and when: The trivially-dead worklist of Ch 13 that Lesson 17.3 improves on; compare with ADCE.cpp.
    Cited in: 03-dead-code-elimination

  • [LLVM-DemandedBits] Backward demanded-bits analysis — llvm/lib/Analysis/DemandedBits.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DemandedBits::determineLiveOperandBits.
    Why and when: Which bits of each value can reach an observable use; print<demanded-bits> in Lesson 17.2 prints it. BDCE.cpp (bitTrackingDCE) is its client.
    Cited in: 02-range-and-bit-analyses

  • [LLVM-DSE] Dead store elimination on MemorySSA — llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: eliminateDeadStores.
    Why and when: Where "dead" means an overwritten or never-read store: the memory side of Lesson 17.3 §6, taught in full in Ch 19.
    Cited in: 03-dead-code-elimination

  • [LLVM-EarlyCSE] LLVM's EarlyCSE (dominator-scoped value numbering) — llvm/lib/Transforms/Scalar/EarlyCSE.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SimpleValue, DenseMapInfo<SimpleValue>::getHashValue, EarlyCSEPass::run.
    Why and when: Scoped hash tables walked in dominator order, memory generations, and the MemorySSA mode; Lesson 17.4 §2 and §7.
    Cited in: 04-dominator-scoped-redundancy

  • [LLVM-GVN] LLVM's GVN (hash-based value numbers, load elimination and PRE) — llvm/lib/Transforms/Scalar/GVN.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: GVNPass::ValueTable::lookupOrAdd, GVNPass::propagateEquality, GVNPass::PerformLoadPRE, GVNPass::performScalarPRE.
    Why and when: Hash-based value numbering in RPO with a leader table, equality propagation from branches, load PRE and a simple scalar PRE (Lessons 17.4 and 17.6).
    Cited in: 04-dominator-scoped-redundancy, 06-partial-redundancy-elimination

  • [LLVM-GVNHoist] GVN-based hoisting of very busy expressions — llvm/lib/Transforms/Scalar/GVNHoist.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: GVNHoist::hoistExpressions.
    Why and when: Hoists equal-valued computations from all successors to a common dominator (Lesson 17.5 §6).
    Cited in: 05-partition-and-optimistic-gvn

  • [LLVM-GVNSink] GVN-based sinking into a common successor — llvm/lib/Transforms/Scalar/GVNSink.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: GVNSink::sinkBB.
    Why and when: The mirror image of GVN-hoist, merging "almost equal" instructions with phis of their differing operands (Lesson 17.5 §6).
    Cited in: 05-partition-and-optimistic-gvn

  • [LLVM-IPSCCP] Interprocedural SCCP (arguments, returns and globals) — llvm/lib/Transforms/IPO/SCCP.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: runIPSCCP.
    Why and when: The same solver across calls of internal functions: the preview of Lesson 17.1 §6, continued in Ch 20.
    Cited in: 01-constant-propagation

  • [LLVM-JumpThreading] Jump threading with a lazy DomTreeUpdater — llvm/lib/Transforms/Scalar/JumpThreading.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: JumpThreadingPass::runImpl, JumpThreadingPass::threadEdge, JumpThreadingPass::processThreadableEdges.
    Why and when: Threads edges whose branch outcome LVI knows per predecessor, duplicating the block in between (Lesson 17.7 §2, §5 for the duplication cost).
    Cited in: 07-cfg-simplification

  • [LLVM-KnownBits] The known-bits domain and its transfer functions — llvm/lib/Support/KnownBits.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: KnownBits::computeForAddSub.
    Why and when: Zero/one masks per bit and the carry-aware addition of Lemma 17.2.9; read after Lesson 17.2 §2.
    Cited in: 02-range-and-bit-analyses

  • [LLVM-LVI] On-demand interval analysis per (value, block) — llvm/lib/Analysis/LazyValueInfo.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LazyValueInfoImpl::solve, LazyValueInfoImpl::solveBlockValue, LazyValueInfoImpl::getEdgeValue.
    Why and when: Demand-driven ranges with branch refinement on edges; Lesson 17.2's LVI box prints its cache.
    Cited in: 02-range-and-bit-analyses

  • [LLVM-NewGVN] NewGVN, LLVM's optimistic sparse GVN after Gargi — llvm/lib/Transforms/Scalar/NewGVN.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: NewGVN::iterateTouchedInstructions, NewGVN::performCongruenceFinding, CongruenceClass.
    Why and when: Its header cites [Gar02] and Simpson's SCC-based VN; congruence classes that start optimistic, touched-instruction iteration, PredicateInfo (Lesson 17.5 §7).
    Cited in: 05-partition-and-optimistic-gvn, 08-phase-ordering-and-equality-saturation

  • [LLVM-Pipelines] The -O0/-O1/-O2/-O3 pass pipelines of LLVM's new pass manager — llvm/lib/Passes/PassBuilderPipelines.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PassBuilder::buildPerModuleDefaultPipeline, PassBuilder::buildO0DefaultPipeline.
    Why and when: Where the phase order of Lesson 17.8 lives: count how often instcombine, simplifycfg and early-cse appear in buildFunctionSimplificationPipeline.
    Cited in: 01-constant-propagation, 03-dead-code-elimination, 04-dominator-scoped-redundancy, 08-phase-ordering-and-equality-saturation

  • [LLVM-SCCP] LLVM's sparse conditional constant (and range) propagation solver — llvm/lib/Transforms/Utils/SCCPSolver.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SCCPInstVisitor::solve, SCCPInstVisitor::markEdgeExecutable, SCCPInstVisitor::visitPHINode, MaxNumRangeExtensions.
    Why and when: Wegman–Zadeck SCCP over ValueLatticeElement (constants and ConstantRanges), shared by the sccp and ipsccp passes. Lesson 17.1 §7's reading task starts at solve.
    Cited in: 01-constant-propagation, 02-range-and-bit-analyses

  • [LLVM-SCCPPass] The intraprocedural sccp pass (solver driver and rewriting) — llvm/lib/Transforms/Scalar/SCCP.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: runSCCP, SCCPPass::run.
    Why and when: Where the solver's results become IR: constants replaced, dead blocks removed, flags and range attributes added (Lesson 17.1 §7 and Lesson 17.2's range box).
    Cited in: 01-constant-propagation

  • [LLVM-SimplifyCFG] SimplifyCFG, LLVM's CFG canonicalizer — llvm/lib/Transforms/Utils/SimplifyCFG.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SimplifyCFGOpt::simplifyOnce, simplifySwitchLookup, foldBranchToCommonDest.
    Why and when: Block merging, constant-branch folding, speculation into selects and switch-to-lookup-table (Lesson 17.7 §2 and §7).
    Cited in: 07-cfg-simplification

  • [LLVM-ValueTracking] Demand-driven known-bits queries on IR — llvm/lib/Analysis/ValueTracking.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: computeKnownBits.
    Why and when: computeKnownBits walks operands recursively up to a depth limit instead of solving a fixed point: the "local, bounded" variant of Lesson 17.2 §6.
    Cited in: 02-range-and-bit-analyses

  • [Open64-SSAPRE] Open64's SSAPRE (down-safety step; see also opt_eavail.cxx and opt_efinalize.cxx) — osprey/be/opt/opt_eant.cxx in open64-compiler/open64 at 590bdf3d58944cb93aafd89480a5590a863ded60. Symbols: EXP_WORKLST::Compute_du_info.
    Why and when: The production SSAPRE of [CCK+97], by the same group: one file per step (opt_eant.cxx: anticipation / down-safety, opt_eavail.cxx: WillBeAvail, opt_efinalize.cxx: Finalize). The repository has no release tags; the pointer is pinned to a commit.
    Cited in: 06-partial-redundancy-elimination

Official documentation and specifications

  • [CL-EgraphRFC] Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations (RFC). link
    Why and when: The design document of Cranelift's aegraphs by its author, Chris Fallin: phase ordering, acyclic e-graphs, elaboration and rule priority. Read with Lesson 17.8 §6–7.
    Cited in: 08-phase-ordering-and-equality-saturation

  • [GCC-TreeSSAPasses] GCC Internals, "Tree SSA passes". GCC 15. link
    Why and when: The list of GIMPLE passes with the names used by -fdump-tree-* (ccp, cddce, fre, pre, dom/threading); keep it open when reading the GCC boxes of this chapter.
    Cited in: 01-constant-propagation, 07-cfg-simplification, 08-phase-ordering-and-equality-saturation

  • [LLVM-Passes] LLVM's Analysis and Transform Passes. LLVM 23.1.2. link
    Why and when: One paragraph per pass; at llvmorg-23.1.2 it has entries for adce, gvn, sccp, ipsccp, simplifycfg and jump-threading (not for bdce, early-cse, newgvn or correlated-propagation, whose file headers are the documentation). A map of Lessons 17.1–17.7 in LLVM's words.