References — Chapter 20 · Interprocedural & Whole-Program Optimization

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

• [AGS97] Andrew Ayers, Richard Schooler, and Robert Gottlieb. Aggressive Inlining. PLDI 1997, pp. 134–145, 1997. doi:10.1145/258915.258928
  Why and when: HP's profile-driven inliner and cloner for large programs: benefit/cost priorities and a global budget. Read §3–4 after Lesson 20.3's classic heuristics.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 03-inlining

• [Ban79] John P. Banning. An Efficient Way to Find the Side Effects of Procedure Calls and the Aliases of Variables. POPL 1979, pp. 29–41, 1979. doi:10.1145/567752.567756
  Why and when: Side-effect (MOD/REF) summaries of procedures, the ancestor of memory-effect inference. Read after Lesson 20.6 §2 (the effect equations of Definition 20.6.3).
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 06-attributes-and-signatures

• [BD77] R. M. Burstall and John Darlington. A Transformation System for Developing Recursive Programs. Journal of the ACM 24(1), pp. 44–67, 1977. doi:10.1145/321992.321996
  Why and when: Fold/unfold transformations, including generalization with accumulating parameters — the program-transformation view of TRE with accumulators (Lesson 20.8, Theorem 20.8.5).
  Note: DOI recorded from the journal; not re-resolved from the course container.
  Cited in: 08-tail-calls

• [BL94] Thomas Ball and James R. Larus. Optimally Profiling and Tracing Programs. ACM TOPLAS 16(4), pp. 1319–1360, 1994. doi:10.1145/183432.183527
  Why and when: Counter placement on the complement of a maximum-weight spanning tree, and edge profiling versus tracing. Read §2–3 before Lesson 20.10 if Lesson 12.3 is not fresh.
  Cited in: 10-profile-guided-optimization

• [BS96] David F. Bacon and Peter F. Sweeney. Fast Static Analysis of C++ Virtual Function Calls. OOPSLA 1996, pp. 324–341, 1996. doi:10.1145/236337.236371
  Why and when: Rapid type analysis: CHA restricted to classes instantiated in reachable code, and its evaluation on C++ programs. Read §3–5 after Lesson 20.1's RTA and compare with the lab's measurement table.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 01-call-graph-construction

• [CCKT86] David Callahan, Keith D. Cooper, Ken Kennedy, and Linda Torczon. Interprocedural Constant Propagation. SIGPLAN '86 Symposium on Compiler Construction, pp. 152–161, 1986. doi:10.1145/12276.13327
  Why and when: Jump functions and return functions for interprocedural constants, the design GCC's ipa-cp still follows. Read §2–3 with Lesson 20.5's IPSCCP section.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 05-interprocedural-analysis

• [CHK93] Keith D. Cooper, Mary W. Hall, and Ken Kennedy. A Methodology for Procedure Cloning. Computer Languages 19(2), pp. 105–117, 1993. doi:10.1016/0096-0551(93)90005-L
  Why and when: Procedure cloning driven by interprocedural facts (constants reaching each call site), with a partitioning algorithm that bounds the number of clones. Read after Lesson 20.4 §2.
  Note: DOI recorded from the journal; not re-resolved from the course container.
  Cited in: 04-specialization-and-outlining

• [CK88] Keith D. Cooper and Ken Kennedy. Interprocedural Side-Effect Analysis in Linear Time. PLDI 1988, pp. 57–66, 1988. doi:10.1145/53990.53996
  Why and when: Side effects in linear time by solving on the call graph's SCCs — the same bottom-up SCC structure as Algorithm 20.6.5. Read after Lesson 20.6 §4.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 06-attributes-and-signatures

• [CLM16] Dehao Chen, David Xinliang Li, and Tipp Moseley. AutoFDO: Automatic Feedback-Directed Optimization for Warehouse-Scale Applications. CGO 2016, pp. 12–23, 2016. doi:10.1145/2854038.2854044
  Why and when: Sampling-based FDO from production perf profiles mapped to source lines, and its deployment at Google. Read §3–4 with Lesson 20.10's sampling PGO.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 10-profile-guided-optimization

• [DGC95] Jeffrey Dean, David Grove, and Craig Chambers. Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis. ECOOP 1995, LNCS 952, pp. 77–101, 1995. doi:10.1007/3-540-49538-X_5
  Why and when: The origin of class hierarchy analysis: resolve a message send to the overrides below the receiver's static class. Read §2–3 with Lesson 20.1's CHA (Algorithm 20.1.5).
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 01-call-graph-construction

• [DH92] Jack W. Davidson and Anne M. Holler. Subprogram Inlining: A Study of Its Effects on Program Execution Time. IEEE Transactions on Software Engineering 18(2), pp. 89–102, 1992. doi:10.1109/32.121752
  Why and when: A measurement study of when inlining helps and when it hurts (register pressure, cache effects). Read after Lesson 20.3 §5 for why a cost model needs a size term.
  Note: DOI recorded from the journal; not re-resolved from the course container.
  Cited in: 03-inlining

• [FMW84] Christopher W. Fraser, Eugene W. Myers, and Alan L. Wendt. Analyzing and Compressing Assembly Code. SIGPLAN '84 Symposium on Compiler Construction, pp. 117–121, 1984. doi:10.1145/502874.502886
  Why and when: Procedural abstraction with suffix trees: find repeated instruction sequences and replace them by calls — the idea behind LLVM's MachineOutliner. Read with Lesson 20.4's outlining.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 04-specialization-and-outlining

• [GC01] David Grove and Craig Chambers. A Framework for Call Graph Construction Algorithms. ACM TOPLAS 23(6), pp. 685–746, 2001. doi:10.1145/506315.506316
  Why and when: Core reading. One lattice-based framework in which CHA, RTA, XTA-style propagation, 0-CFA and k-CFA are instances, with a large experimental comparison. Read §2–4 after Lesson 20.1 §2 to see the precision chain of Theorem 20.1.14 as an ordering of framework instances.
  Note: DOI recorded from the journal; not re-resolved from the course container (doi.org is blocked there).
  Cited in: overview, 01-call-graph-construction

• [HU94] Urs Hölzle and David Ungar. Optimizing Dynamically-Dispatched Calls with Run-Time Type Feedback. PLDI 1994, 1994. doi:10.1145/178243.178478
  Why and when: Type feedback: guard the observed receiver type and inline its method — the idea behind speculative devirtualization and indirect-call promotion (Lesson 20.7).
  Cited in: 07-devirtualization

• [JAL17] Teresa Johnson, Mehdi Amini, and Xinliang David Li. ThinLTO: Scalable and Incremental LTO. CGO 2017, pp. 111–121, 2017. doi:10.1109/CGO.2017.7863733
  Why and when: Core reading. Summaries, the thin link, importing and the parallel backends, with measurements against full LTO. Read §3–4 with Lesson 20.9 and §5 for the numbers its "At scale" paragraph cites.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: overview, 09-lto-and-thinlto

• [KS73] Donald E. Knuth and Francis R. Stevenson. Optimal Measurement Points for Program Frequency Counts. BIT Numerical Mathematics 13(3), pp. 313–322, 1973. doi:10.1007/BF01951942
  Why and when: Counting only the edges outside a spanning tree and recovering the rest by flow conservation — the counter placement of LLVM's IR PGO (Lesson 20.10, Ch 12).
  Note: DOI recorded from the journal; not re-resolved from the course container. Cited in the header of LLVM's PGOInstrumentation.cpp.
  Cited in: 10-profile-guided-optimization

• [LA04] Chris Lattner and Vikram Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. CGO 2004, pp. 75–86, 2004. doi:10.1109/CGO.2004.1281665
  Why and when: LLVM's original design goal: keep IR in object files so that the linker can optimize the whole program. Read §3.3–3.4 with Lesson 20.9's monolithic LTO.
  Cited in: 09-lto-and-thinlto

• [LH03] Ondřej Lhoták and Laurie Hendren. Scaling Java Points-to Analysis Using Spark. CC 2003, LNCS 2622, pp. 153–169, 2003. doi:10.1007/3-540-36579-6_12
  Why and when: Soot's Spark: points-to analysis with on-the-fly call-graph construction, and the options (rta, vta, on-fly-cg) the Lesson 20.1 boxes use. Read §2–3 after Lesson 20.1's points-to-based call graphs.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 01-call-graph-construction

• [NS94] Esko Nuutila and Eljas Soisalon-Soininen. On finding the strongly connected components in a directed graph. Information Processing Letters 49(1), pp. 9–14, 1994. doi:10.1016/0020-0190(94)90047-7
  Why and when: A Tarjan variant that does not push single-node SCCs, which dominate call graphs. Short; read after Lesson 20.2 §6.
  Note: DOI recorded from the journal; not re-resolved from the course container.
  Cited in: 02-scc-traversal

• [PAN+19] Maksim Panchenko, Rafael Auler, Bill Nell, and Guilherme Ottoni. BOLT: A Practical Binary Optimizer for Data Centers and Beyond. CGO 2019, 2019. doi:10.1109/CGO.2019.8661201 · pdf
  Why and when: Post-link optimization of the linked binary from sampled profiles: CFG reconstruction, block reordering, function splitting and ordering. Read §3–5 after Lesson 20.10.
  Cited in: 10-profile-guided-optimization

• [Pea16] David J. Pearce. A space-efficient algorithm for finding strongly connected components. Information Processing Letters 116(1), pp. 47–52, 2016. doi:10.1016/j.ipl.2015.08.010
  Why and when: Tarjan's algorithm with one integer per node instead of index, lowlink and an on-stack flag, in the same visiting order. Read after Lesson 20.2 §6.
  Note: DOI recorded from the journal; not re-resolved from the course container.
  Cited in: 02-scc-traversal

• [PH90] Karl Pettis and Robert C. Hansen. Profile Guided Code Positioning. PLDI 1990, 1990. doi:10.1145/93542.93550
  Why and when: Profile-driven procedure ordering ("closest is best") and basic-block positioning and splitting. Read §3 with Algorithm 20.10.6 and Lesson 20.4's hot/cold splitting.
  Cited in: 04-specialization-and-outlining, 10-profile-guided-optimization

• [RHS95] Thomas Reps, Susan Horwitz, and Mooly Sagiv. Precise Interprocedural Dataflow Analysis via Graph Reachability. POPL 1995, pp. 49-61, 1995. doi:10.1145/199448.199462
  Why and when: Core reading. IFDS: distributive problems over finite domains as realizable-path reachability in the exploded supergraph, and the tabulation algorithm with its O(ED³) bound. Read §3–5 with Lesson 20.5 and the drill ifds-tabulation.
  Cited in: overview, 05-interprocedural-analysis

• [Sch77] Robert W. Scheifler. An Analysis of Inline Substitution for a Structured Programming Language. Communications of the ACM 20(9), pp. 647–654, 1977. doi:10.1145/359810.359830
  Why and when: Inlining under a size budget as a knapsack-like optimization problem, with a greedy heuristic. Read §2–3 after Lesson 20.3 §2 (Definition 20.3.3 and Theorem 20.3.4).
  Note: DOI recorded from the journal; not re-resolved from the course container.
  Cited in: 03-inlining

• [Sha81] Micha Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications 7(1), pp. 67–72, 1981. doi:10.1016/0898-1221(81)90008-0
  Why and when: The two-pass (Kosaraju–Sharir) SCC algorithm, which emits SCCs in topological order. Read after Lesson 20.2 §6 for the contrast with Tarjan's bottom-up order.
  Note: DOI recorded from the journal; not re-resolved from the course container.
  Cited in: 02-scc-traversal

• [SHR+00] Vijay Sundaresan, Laurie Hendren, Chrislain Razafimahefa, Raja Vallée-Rai, Patrick Lam, Étienne Gagnon, and Charles Godin. Practical Virtual Method Call Resolution for Java. OOPSLA 2000, pp. 264–280, 2000. doi:10.1145/353171.353189
  Why and when: Variable type analysis (VTA) and declared type analysis in Soot: a type propagation graph over variables. Read §3 with Lesson 20.1's VTA and the Soot box of §7.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 01-call-graph-construction

• [SP81] Micha Sharir and Amir Pnueli. Two Approaches to Interprocedural Data Flow Analysis. In S. Muchnick and N. Jones (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, pp. 189–234, 1981.
  Why and when: The functional (summary) approach and the call-string approach, and when each computes the meet over valid paths. Read after Lesson 20.5 §2 (Theorem 20.5.7) and Lesson 20.2's bottom-up summaries.
  Note: A book chapter; no DOI. Available in university libraries.
  Cited in: 02-scc-traversal, 05-interprocedural-analysis

• [SPL+23] Han Shen, Krzysztof Pszeniczny, Rahman Lavaee, Snehasish Kumar, Sriraman Tallam, and Xinliang David Li. Propeller: A Profile Guided, Relinking Optimizer for Warehouse-Scale Applications. ASPLOS 2023, pp. 617–631, 2023. doi:10.1145/3575693.3575727
  Why and when: Post-link layout moved into the compiler and linker with basic-block sections, designed for distributed builds. Read §3–4 with Lesson 20.10's basic-block-sections box.
  Cited in: 10-profile-guided-optimization

• [SRH96] Mooly Sagiv, Thomas Reps, and Susan Horwitz. Precise Interprocedural Dataflow Analysis with Applications to Constant Propagation. Theoretical Computer Science 167(1-2), pp. 131-170, 1996. doi:10.1016/0304-3975(96)00072-2
  Why and when: IDE: environment transformers and micro-functions, with linear constant propagation as the example. Read §2–4 after Lesson 20.5's IDE section.
  Cited in: 05-interprocedural-analysis

• [Ste77] Guy Lewis Steele Jr.. Debunking the "Expensive Procedure Call" Myth, or, Procedure Call Implementations Considered Harmful, or, LAMBDA: The Ultimate GOTO. Proceedings of the 1977 ACM Annual Conference, pp. 153–162, 1977. doi:10.1145/800179.810196
  Why and when: Tail calls as jumps that pass arguments, and why a compiler should compile them so. Read §1–3 with Lesson 20.8's tail-call elimination.
  Note: DOI recorded from the proceedings; not re-resolved from the course container. Also MIT AI Memo 443.
  Cited in: 08-tail-calls

• [Tar72] Robert E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1(2), 146–160, 1972. doi:10.1137/0201010
  Why and when: The linear-time SCC algorithm that LLVM's scc_iterator runs on the call graph. Read the strong-connectivity part after Lesson 20.2 §2 and compare its lowlink with Lemma 20.2.8.
  Cited in: 02-scc-traversal

• [TP00] Frank Tip and Jens Palsberg. Scalable Propagation-Based Call Graph Construction Algorithms. OOPSLA 2000, pp. 281–293, 2000. doi:10.1145/353171.353190
  Why and when: The family CTA, MTA, FTA and XTA between RTA and 0-CFA: one type set per method, field or class. Read §3 with Lesson 20.1's XTA (Algorithm 20.1.8), the lab's ★ milestone.
  Note: DOI recorded from the proceedings; not re-resolved from the course container.
  Cited in: 01-call-graph-construction

• [TQY+21] Mircea Trofin, Yundi Qian, Eugene Brevdo, Zinan Lin, Krzysztof Choromanski, and David Li. MLGO: a Machine Learning Guided Compiler Optimizations Framework. arXiv preprint 2101.04808, 2021. link
  Why and when: The design of LLVM's learned inlining-for-size policy: features, the reward (native size), evolution strategies and reinforcement learning, and deployment in LLVM. Read §3–5 after Lesson 20.3's MLGO section.
  Cited in: 03-inlining

• [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: Sparse conditional constant propagation, which LLVM's IPSCCP runs over all functions at once. Review §3 before Lesson 20.5's IPSCCP.
  Cited in: 05-interprocedural-analysis

Textbooks and monographs

• [GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Read: Appendix A1.3 (vertex ordering, including optimal linear arrangement), Appendix A6 (mathematical programming, including knapsack).
  Why and when: The NP-hardness facts behind Proposition 20.10.8 (weighted linear arrangement) and the knapsack view of inlining (Theorem 20.3.4). Use as a lookup, not a read.
  Cited in: 10-profile-guided-optimization

• [Gus97] Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997. Read: Ch. 5 (suffix trees), Ch. 6 (Ukkonen's linear-time construction), Ch. 7 (first applications: repeated substrings).
  Why and when: The full proofs behind the outliner's repeated-sequence search (Lesson 20.4 §4 cites Ch. 7). Read Ch. 5–6 only if you want to implement suffix trees yourself.
  Cited in: 04-specialization-and-outlining

• [Muchnick] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. Read: Ch. 15 (Procedure Optimizations: tail calls, procedure integration, in-line expansion), Ch. 19 (Interprocedural Analysis and Optimization).
  Why and when: A textbook treatment of inlining, tail-call optimization, interprocedural side effects, constants and cloning. Read Ch. 19 alongside Lessons 20.5–20.6 for a second presentation.

Source code (pinned versions)

• [GCC-Devirt] GCC's type inheritance graph, polymorphic call targets and speculative devirtualization — gcc/ipa-devirt.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: possible_polymorphic_call_targets, type_possibly_instantiated_p, ipa_devirt.
  Why and when: CHA with an RTA-like instantiation filter and speculative devirtualization. Read possible_polymorphic_call_targets after Lesson 20.1 §7 and ipa_devirt with Lesson 20.7.
  Cited in: 01-call-graph-construction, 07-devirtualization

• [GCC-Inline] GCC's inliner (priority queue by badness, unit-growth limits) — gcc/ipa-inline.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: inline_small_functions, edge_badness, want_inline_small_function_p.
  Why and when: The greedy benefit/cost inliner of Algorithm 20.3.5. Read edge_badness after Lesson 20.3 §2 and the GCC box of §7.
  Cited in: 03-inlining

• [GCC-IPACP] GCC's interprocedural constant propagation and cloning — gcc/ipa-cp.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: decide_about_value, create_specialized_node.
  Why and when: Jump functions, lattices per parameter and .constprop clones (Lessons 20.4 and 20.5).
  Cited in: 04-specialization-and-outlining, 05-interprocedural-analysis

• [GCC-Modref] GCC's mod/ref summaries (ipa-modref) — gcc/ipa-modref.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: modref_summary, analyze_function, modref_propagate_in_scc.
  Why and when: Bottom-up per-function memory summaries propagated over SCCs — Lessons 20.2, 20.5 and 20.6 in one production pass.
  Cited in: 02-scc-traversal, 05-interprocedural-analysis, 06-attributes-and-signatures

• [GCC-PolyCall] GCC's polymorphic call contexts (dynamic-type tracking) — gcc/ipa-polymorphic-call.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: ipa_polymorphic_call_context.
  Why and when: Flow-sensitive tracking of an object's dynamic type before target lookup — GCC's closest relative of XTA/VTA (Lesson 20.1 §7).
  Cited in: 01-call-graph-construction

• [GCC-Split] GCC's function splitting for partial inlining (fnsplit) — gcc/ipa-split.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: find_split_points, split_function.
  Why and when: Chooses a split point by estimated size and time and creates .part functions. Read after Lesson 20.4's partial inlining.
  Cited in: 04-specialization-and-outlining

• [GCC-Tail] GCC's tail-call marking and tail-recursion elimination — gcc/tree-tailcall.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: find_tail_calls, process_assignment, eliminate_tail_call.
  Why and when: Accumulator recognition (add and mult accumulators) and the loop construction — compare with LLVM's TRE after Lesson 20.8.
  Cited in: 08-tail-calls

• [LLVM-ArgPromotion] LLVM's argument promotion — llvm/lib/Transforms/IPO/ArgumentPromotion.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: promoteArguments, findArgParts, doPromotion.
  Why and when: The legality checks and the signature rewrite of Algorithm 20.6.9 (by-pointer to by-value). Read findArgParts after Lesson 20.6.
  Cited in: 06-attributes-and-signatures

• [LLVM-BBSections] LLVM's basic-block sections (Propeller's compiler side) — llvm/lib/CodeGen/BasicBlockSections.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: BasicBlockSections::runOnMachineFunction, assignSections, BasicBlockSections::handleBBSections.
  Why and when: Places blocks into sections from a cluster profile and emits the block address map. Read the file header after Lesson 20.10's basic-block-sections box.
  Cited in: 10-profile-guided-optimization

• [LLVM-CG] LLVM's legacy call graph (external calling and calls-external nodes) — llvm/lib/Analysis/CallGraph.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: CallGraph::addToCallGraph, CallGraph::populateCallGraphNode.
  Why and when: How LLVM builds the direct call graph whose SCC order E1 must reproduce (Definition 20.2.4): read addToCallGraph for the roots and populateCallGraphNode for the edges.
  Cited in: 01-call-graph-construction, 02-scc-traversal

• [LLVM-CGSCC] LLVM's CGSCC pass manager and its call-graph update protocol — llvm/lib/Analysis/CGSCCPassManager.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ModuleToPostOrderCGSCCPassAdaptor::run, updateCGAndAnalysisManagerForCGSCCPass, updateCGAndAnalysisManagerForFunctionPass.
  Why and when: The worklists and the update functions behind Algorithm 20.2.7 and Proposition 20.2.11. Read after Lesson 20.2 §2; the comments in run explain every invariant.
  Cited in: 02-scc-traversal

• [LLVM-CodeLayout] LLVM's ext-TSP block layout and cache-directed function sort — llvm/lib/Transforms/Utils/CodeLayout.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: codelayout::computeExtTspLayout, codelayout::computeCacheDirectedLayout, ExtTSPImpl.
  Why and when: The chain-merging layout algorithms used by block placement and by BOLT; the header contrasts them with Pettis–Hansen. Read after Algorithm 20.10.6.
  Cited in: 10-profile-guided-optimization

• [LLVM-DAE] LLVM's dead-argument and dead-return-value elimination — llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DeadArgumentEliminationPass::surveyFunction, DeadArgumentEliminationPass::markLive, DeadArgumentEliminationPass::removeDeadStuffFromFunction.
  Why and when: The liveness propagation of Algorithm 20.6.8 over arguments and return values. Read after Lesson 20.6's dead-argument elimination.
  Cited in: 06-attributes-and-signatures

• [LLVM-FuncSpec] LLVM's function specialization (inside IPSCCP) — llvm/lib/Transforms/IPO/FunctionSpecialization.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: FunctionSpecializer::run, FunctionSpecializer::findSpecializations, InstCostVisitor.
  Why and when: Cloning for constant and function-pointer arguments with a bonus-based cost model. Read findSpecializations after Lesson 20.4 §2.
  Cited in: 01-call-graph-construction, 04-specialization-and-outlining

• [LLVM-FunctionAttrs] LLVM's function-attribute inference — llvm/lib/Transforms/IPO/FunctionAttrs.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: deriveAttrsInPostOrder, checkFunctionMemoryAccess, addNoRecurseAttrs, addArgumentAttrs.
  Why and when: The production version of E3: memory effects, norecurse, argument captures and more, per SCC in post order. Read deriveAttrsInPostOrder after Lesson 20.6 §2.
  Cited in: 02-scc-traversal, 06-attributes-and-signatures

• [LLVM-FunctionImport] LLVM's ThinLTO import decisions and importer — llvm/lib/Transforms/IPO/FunctionImport.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ModuleImportsManager::computeImportForModule, computeImportForFunction, selectCallee, FunctionImporter::importFunctions.
  Why and when: Algorithm 20.9.5 in production: thresholds, the evolution factor, hot and cold multipliers. The "find where LLVM does it" question of Lesson 20.9 is in this file.
  Cited in: 09-lto-and-thinlto

• [LLVM-GlobalOpt] LLVM's global optimizer — llvm/lib/Transforms/IPO/GlobalOpt.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: optimizeGlobalsInModule, processGlobal, processInternalGlobal, SRAGlobal.
  Why and when: Constant globals, stored-once globals, scalar replacement of aggregate globals and dead globals (Algorithm 20.6.10). Read processInternalGlobal after Lesson 20.6.
  Cited in: 06-attributes-and-signatures

• [LLVM-HotCold] LLVM's hot/cold splitting — llvm/lib/Transforms/IPO/HotColdSplitting.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: HotColdSplitting::run, HotColdSplitting::outlineColdRegions.
  Why and when: Finds cold single-entry regions (profile or unreachable/noreturn heuristics) and outlines them into .cold functions. Read after Lesson 20.4's hot/cold splitting.
  Cited in: 04-specialization-and-outlining

• [LLVM-ICP] LLVM's profile-guided indirect-call promotion — llvm/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: IndirectCallPromoter::processFunction, IndirectCallPromoter::getPromotionCandidatesForCallSite, promoteIndirectCalls.
  Why and when: Reads value profiles and promotes hot targets behind a guard (Lessons 20.7 and 20.10); the thresholds are the cl::opts in IndirectCallPromotionAnalysis.cpp.
  Cited in: 07-devirtualization, 10-profile-guided-optimization

• [LLVM-InlineAdvisor] LLVM's inline advisor interface and default advisor — llvm/lib/Analysis/InlineAdvisor.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DefaultInlineAdvisor::getAdviceImpl, llvm::shouldInline.
  Why and when: Where the inliner asks "should I inline this call?" and where a learned advisor plugs in (Definition 20.3.10).
  Cited in: 03-inlining

• [LLVM-InlineCost] LLVM's inline cost analysis — llvm/lib/Analysis/InlineCost.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: CallAnalyzer::analyze, InlineCostCallAnalyzer, LastCallToStaticBonus, llvm::getInlineCost.
  Why and when: Core reading. The production version of the course cost model: simplification during analysis, bonuses, thresholds. Read CallAnalyzer::analyze and InlineCostCallAnalyzer after Lesson 20.3 §2.
  Cited in: overview, 03-inlining

• [LLVM-Inliner] LLVM's CGSCC inliner pass — llvm/lib/Transforms/IPO/Inliner.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InlinerPass::run, ModuleInlinerWrapperPass.
  Why and when: The bottom-up inliner loop: call sites per SCC, inline history against recursion through inlining, deletion of dead callees. Compare with pebble-inline (Algorithm 20.3.9).
  Cited in: 03-inlining

• [LLVM-IPSCCP] LLVM's interprocedural SCCP driver — llvm/lib/Transforms/IPO/SCCP.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: runIPSCCP, IPSCCPPass::run.
  Why and when: Which functions IPSCCP tracks (internal, all uses known), how arguments and returns are merged, and where function specialization runs. Read with Lesson 20.5 §2.
  Cited in: 04-specialization-and-outlining, 05-interprocedural-analysis

• [LLVM-IROutliner] LLVM's IR-level outliner — llvm/lib/Transforms/IPO/IROutliner.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: IROutliner::run, IROutliner::doOutline.
  Why and when: Outlining of similar IR regions (with different constants as parameters); compare with the machine outliner in Lesson 20.4 §6.
  Cited in: 04-specialization-and-outlining

• [LLVM-LCG] LLVM's LazyCallGraph (call and ref edges, RefSCCs, incremental updates) — llvm/lib/Analysis/LazyCallGraph.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LazyCallGraph::buildRefSCCs, LazyCallGraph::RefSCC::switchInternalEdgeToRef, LazyCallGraph::RefSCC::switchInternalEdgeToCall.
  Why and when: The graph the new pass manager's CGSCC walk runs on. Read the file header and buildRefSCCs after Lesson 20.2's Definition 20.2.6.
  Cited in: 01-call-graph-construction, 02-scc-traversal

• [LLVM-LTOSrc] LLVM's LTO driver (regular and thin) — llvm/lib/LTO/LTO.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LTO::run, LTO::runRegularLTO, LTO::runThinLTO.
  Why and when: The implementation behind llvm-lto2 and the linker plugins: symbol resolutions, internalization, the regular and thin paths. Read after Lesson 20.9 §2.
  Cited in: 09-lto-and-thinlto

• [LLVM-MachineOutliner] LLVM's machine outliner (suffix-tree based) — llvm/lib/CodeGen/MachineOutliner.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InstructionMapper, MachineOutliner::findCandidates, MachineOutliner::outline.
  Why and when: Maps machine instructions to integers, finds repeats with a suffix tree and asks the target for the cost of each outlining strategy. Read after Lesson 20.4's outlining.
  Cited in: 04-specialization-and-outlining

• [LLVM-MLAdvisor] LLVM's ML inline advisor (MLGO) — llvm/lib/Analysis/MLInlineAdvisor.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MLInlineAdvisor::getAdviceImpl, MLInlineAdvisor::onPassEntry.
  Why and when: The features MLGO feeds its model and how the model's decision becomes advice; read with Lesson 20.3's MLGO section.
  Cited in: 03-inlining

• [LLVM-PartialInliner] LLVM's partial inliner — llvm/lib/Transforms/IPO/PartialInlining.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PartialInlinerImpl::tryPartialInline, PartialInlinerImpl::computeOutliningInfo.
  Why and when: Recognizes an early-return guard, outlines the rest and inlines the guard. Read after Lesson 20.4's partial inlining.
  Cited in: 04-specialization-and-outlining

• [LLVM-PGOSrc] LLVM's IR PGO instrumentation and profile use — llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PGOInstrumentationGen::run, instrumentOneFunc, PGOUseFunc::populateCounters, PGOUseFunc::setBranchWeights.
  Why and when: Spanning-tree counter placement (via CFGMST.h), value-profiling sites, count reconstruction and branch weights. Read the file header first (Lesson 20.10's quiz asks about it).
  Cited in: 10-profile-guided-optimization

• [LLVM-Pipelines] Where LLVM's -O2, LTO, ThinLTO and PGO pipelines schedule the interprocedural passes — llvm/lib/Passes/PassBuilderPipelines.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PassBuilder::buildInlinerPipeline, PassBuilder::buildModuleSimplificationPipeline, PassBuilder::buildLTODefaultPipeline, PassBuilder::buildThinLTODefaultPipeline, PassBuilder::addPGOInstrPasses.
  Why and when: Find the CGSCC inliner group, IPSCCP, GlobalOpt, DeadArgElim, WholeProgramDevirt and the PGO passes in order. Keep it open while reading Lessons 20.2, 20.9 and 20.10.
  Cited in: 02-scc-traversal, 09-lto-and-thinlto, 10-profile-guided-optimization

• [LLVM-SampleSrc] LLVM's sample-profile loader (AutoFDO) — llvm/lib/Transforms/IPO/SampleProfile.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SampleProfileLoader::getInstWeight, SampleProfileLoader::inlineHotFunctions, SampleProfileLoader::emitAnnotations.
  Why and when: How line-offset samples become block weights, how the profiled binary's inlining is replayed, and where the annotations are written. Read after Lesson 20.10's sampling box.
  Cited in: 10-profile-guided-optimization

• [LLVM-SCCIt] LLVM's generic iterative Tarjan SCC iterator — llvm/include/llvm/ADT/SCCIterator.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: scc_iterator::DFSVisitOne, scc_iterator::DFSVisitChildren, scc_iterator::GetNextSCC.
  Why and when: The exact algorithm and visiting order of Algorithm 20.2.3; read it before E1 and compare its lowlink updates with yours.
  Cited in: 02-scc-traversal

• [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.
  Why and when: The solver IPSCCP shares with SCCP; the interprocedural part is how call and return values are tracked. Read after Lesson 20.5's IPSCCP section.
  Cited in: 05-interprocedural-analysis

• [LLVM-Summary] LLVM's ThinLTO module summary builder — llvm/lib/Analysis/ModuleSummaryAnalysis.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: computeFunctionSummary, buildModuleSummaryIndex.
  Why and when: What a function summary records (Definition 20.9.4): instruction count, calls with hotness, references, flags. Read after the Lesson 20.9 summary box.
  Cited in: 09-lto-and-thinlto

• [LLVM-TRE] LLVM's tail-call marking and tail-recursion elimination — llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: markTails, canTransformAccumulatorRecursion, TailRecursionEliminator::eliminateCall, TailRecursionEliminator::processBlock.
  Why and when: markTails (Definition 20.8.2) and TRE with accumulators (Algorithm 20.8.4). Compare eliminateCall with your E4 after you pass the tests.
  Cited in: 08-tail-calls

• [LLVM-WPD] LLVM's whole-program devirtualization — llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DevirtModule::run, DevirtModule::trySingleImplDevirt, DevirtModule::tryVirtualConstProp, DevirtModule::tryUniformRetValOpt.
  Why and when: Single-implementation devirtualization, virtual constant propagation and branch funnels over type metadata. Read the file header and DevirtModule::run after Lesson 20.7 §2.
  Cited in: 07-devirtualization

• [Soot] Soot's call-graph builders (CHATransformer; Spark with rta/vta/on-fly-cg) — src/main/java/soot/jimple/spark/SparkTransformer.java in soot-oss/soot at 4.6.0. Symbols: SparkTransformer.internalTransform.
  Why and when: The Java framework whose CHA, RTA and VTA the Lesson 20.1 boxes run; CHATransformer is in soot/jimple/toolkits/callgraph/. Read the option handling in SparkTransformer to see how rta and vta change Spark.
  Cited in: 01-call-graph-construction

Official documentation and specifications

• [LLVM-BOLT] BOLT README (input requirements, perf profiling, perf2bolt, llvm-bolt options). LLVM 23.1.2. link
  Why and when: The documented BOLT workflow quoted in Lesson 20.10 (the course image has no llvm-bolt or perf). Read Steps 1–3 if you want to run BOLT on your own machine.
  Cited in: 10-profile-guided-optimization

• [LLVM-LangRef-Call] LLVM Language Reference, the call instruction (tail, musttail, notail). LLVM 23.1.2. link
  Why and when: The exact guarantees of the tail markers that Lesson 20.8's TCE relies on; search for "musttail" in the call instruction's section.
  Cited in: 08-tail-calls

• [LLVM-LTO] LLVM Link Time Optimization — Design and Implementation. LLVM 23.1.2. link
  Why and when: The linker–LTO interface (symbol resolution, visibility) that Lesson 20.9's internalization depends on.
  Cited in: 09-lto-and-thinlto

• [LLVM-MLGO] Machine Learning - Guided Optimization (MLGO). LLVM 23.1.2. link
  Why and when: How LLVM builds with a model (AOT or development mode), the training corpus tools and the interfaces. Read after Lesson 20.3's MLGO section.
  Cited in: 03-inlining

• [LLVM-NPM] Using the New Pass Manager. LLVM 23.1.2. link
  Why and when: The pass-manager layers (module, CGSCC, function) and how analyses are invalidated; read the CGSCC parts before Lesson 20.2's CGSCC section.
  Cited in: 02-scc-traversal

• [LLVM-PGO] Clang Users Manual, Profile Guided Optimization (instrumentation, CSPGO, sampling profilers, sample profile formats). LLVM 23.1.2. link
  Why and when: The flags of Lesson 20.10's boxes (-fprofile-generate, -fcs-profile-generate, -fprofile-sample-use), the text sample format and create_llvm_prof. Read the "Profile Guided Optimization" section before running the boxes yourself.
  Cited in: 10-profile-guided-optimization

• [LLVM-ThinLTO] Clang ThinLTO documentation. LLVM 23.1.2. link
  Why and when: Using ThinLTO with Clang and the linkers: caches, parallelism, distributed builds. Read after Lesson 20.9 §6.
  Cited in: 09-lto-and-thinlto

• [LLVM-TypeMetadata] Type Metadata (!type, llvm.type.test, vtable layout for CFI and devirtualization). LLVM 23.1.2. link
  Why and when: How Clang describes class hierarchies to LLVM; the input of whole-program devirtualization. Read before Lesson 20.7 §2.
  Cited in: 01-call-graph-construction, 07-devirtualization