Skip to content

References — Chapter 19 · Memory: Alias Analysis & Memory 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

  • [BS09] Martin Bravenboer and Yannis Smaragdakis. Strictly Declarative Specification of Sophisticated Points-to Analyses. OOPSLA 2009, pp. 243–262, 2009. doi:10.1145/1640089.1640108
    Why and when: Doop: a complete, context-sensitive Java points-to analysis written in Datalog. Read §2–3 after Lesson 19.8 §2 for how call-graph discovery and context constructors become rules.
    Cited in: overview, 07-context-sensitivity, 08-declarative-and-demand-driven

  • [CDOY09] Cristiano Calcagno, Dino Distefano, Peter O'Hearn, and Hongseok Yang. Compositional Shape Analysis by Means of Bi-Abduction. POPL 2009, pp. 289–300, 2009. doi:10.1145/1480881.1480917
    Why and when: Per-procedure separation-logic summaries inferred bottom-up; the analysis inside Facebook Infer's biabduction checker (Lesson 19.9 §7).
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 09-escape-and-shape

  • [Cho99] Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, and Sam Midkiff. Escape Analysis for Java. OOPSLA 1999, pp. 1–19, 1999. doi:10.1145/320384.320386
    Why and when: Connection graphs with escape states (NoEscape, ArgEscape, GlobalEscape), used for stack allocation and lock elision; HotSpot's C2 escape analysis follows it. Read §3–4 after Lesson 19.9 §2.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 09-escape-and-shape

  • [Das00] Manuvir Das. Unification-based Pointer Analysis with Directional Assignments. PLDI 2000, pp. 35–46, 2000. doi:10.1145/349299.349309
    Why and when: One-level flow: inclusion only at the top level of each assignment, unification below, with the empirical claim that this recovers most of Andersen's precision at nearly Steensgaard's cost. Read §3–4 after Lesson 19.5 §2.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: overview, 05-unification

  • [DMM98] Amer Diwan, Kathryn S. McKinley, and J. Eliot B. Moss. Type-Based Alias Analysis. PLDI 1998, pp. 106–117, 1998. doi:10.1145/277650.277670
    Why and when: Core reading. Type compatibility, field-name disambiguation and SMFieldTypeRefs for Modula-3, with the finding that simple type-based rules capture most of the benefit. The origin of Lesson 19.3's TBAA; read §2–3.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: overview, 02-local-alias-rules, 03-type-and-scope-rules

  • [HL07] Ben Hardekopf and Calvin Lin. The Ant and the Grasshopper: Fast and Accurate Pointer Analysis for Millions of Lines of Code. PLDI 2007, pp. 290–299, 2007. doi:10.1145/1250734.1250767
    Why and when: Core reading. Lazy cycle detection (LCD) and hybrid cycle detection (HCD), and an experimental comparison of every cycle-detection scheme then known. The ★ part of the lab implements LCD; read §3–5 after Lesson 19.4 §6 and compare Table 3 with the lab's stress numbers.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: overview, 04-andersen

  • [HL07b] Ben Hardekopf and Calvin Lin. Exploiting Pointer and Location Equivalence to Optimize Pointer Analysis. SAS 2007, LNCS 4634, pp. 265–280, 2007. doi:10.1007/978-3-540-74061-2_17
    Why and when: Offline variable substitution (HVN, HRU) that shrinks the constraint graph before solving; GCC's "Detecting pointer and location equivalences" phase in Lesson 19.4's real-world box is this. Read after Lesson 19.4 §6.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 04-andersen

  • [HL11] Ben Hardekopf and Calvin Lin. Flow-Sensitive Pointer Analysis for Millions of Lines of Code. CGO 2011, pp. 289–298, 2011. doi:10.1109/CGO.2011.5764696
    Why and when: Staged flow-sensitive analysis (SFS): an auxiliary flow-insensitive analysis builds def-use chains for memory, and the flow-sensitive analysis runs sparsely on them. Read §3–4 after Lesson 19.6 §2.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: overview, 06-flow-and-field-sensitivity

  • [HM97] Nevin Heintze and David McAllester. On the Cubic Bottleneck in Subtyping and Flow Analysis. LICS 1997, pp. 342–351, 1997.
    Why and when: Shows that a family of inclusion-based analyses is as hard as a problem for which no subcubic algorithm is known — why Proposition 19.4.16's bound is not just an artefact of the worklist. Read the introduction after Lesson 19.4 §5.
    Note: Look it up by title in the LICS 1997 proceedings (IEEE); no DOI was checked from the course container.
    Cited in: 04-andersen

  • [HT01] Nevin Heintze and Olivier Tardieu. Demand-Driven Pointer Analysis. PLDI 2001, pp. 24–34, 2001. doi:10.1145/378795.378802
    Why and when: Answer one query "what may p point to?" by exploring only the constraints that can matter, with caching. Read §3 after Lesson 19.8 §2.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 04-andersen, 08-declarative-and-demand-driven

  • [JSS16] Herbert Jordan, Bernhard Scholz, and Pavle Subotić. Soufflé: On Synthesis of Program Analyzers. CAV 2016, LNCS 9780, pp. 422–430, 2016. doi:10.1007/978-3-319-41540-6_23
    Why and when: The engine Lesson 19.8's boxes run: Datalog compiled to parallel C++ with specialized indexes; eqrel relations are union-find. A short tool paper; read it all.
    Cited in: overview, 08-declarative-and-demand-driven

  • [LH06] Ondřej Lhoták and Laurie Hendren. Context-Sensitive Points-to Analysis: Is It Worth It?. CC 2006, LNCS 3923, pp. 47–64, 2006. doi:10.1007/11688839_5
    Why and when: A measured comparison of call-site, object and ZCWL cloning sensitivity on Java: object sensitivity wins for OO clients. Read §5 for the numbers quoted in Lesson 19.7 §8.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 07-context-sensitivity

  • [MRR05] Ana Milanova, Atanas Rountev, and Barbara G. Ryder. Parameterized Object Sensitivity for Points-to Analysis for Java. ACM TOSEM 14(1), pp. 1–41, 2005. doi:10.1145/1044834.1044835
    Why and when: Object sensitivity: a method is analysed separately per receiver object (allocation site), not per call site. Read §3 after Lesson 19.7 §2.
    Note: DOI recorded from the journal; not re-resolved from the course container.
    Cited in: 07-context-sensitivity

  • [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 in GCC (virtual operands, memory partitions); LLVM's MemorySSA cites it and uses one memory variable. Read with Lesson 19.10 §1.
    Note: In the printed GCC Developers' Summit 2007 proceedings; the GCC wiki (MemorySSA page) links the paper.
    Cited in: 10-memory-ssa

  • [PB09] Fernando Magno Quintão Pereira and Daniel Berlin. Wave Propagation and Deep Propagation for Pointer Analysis. CGO 2009, pp. 126–135, 2009. doi:10.1109/CGO.2009.9
    Why and when: Replaces the worklist by rounds of "collapse cycles, propagate once in topological order, add complex edges" (wave) or by a depth-first push from each changed node (deep). Algorithm 19.4.9 is wave propagation; read §3–4 after Lesson 19.4 §2.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 04-andersen

  • [PKH03] David J. Pearce, Paul H. J. Kelly, and Chris Hankin. Online Cycle Detection and Difference Propagation for Pointer Analysis. SCAM 2003 (Third IEEE International Workshop on Source Code Analysis and Manipulation), pp. 3–12, 2003. doi:10.1109/SCAM.2003.1238030
    Why and when: Cycle detection during solving by maintaining a topological order of the constraint graph (the Marchetti-Spaccamela / Pearce-Kelly dynamic ordering), plus difference propagation. The source of Lesson 19.4's "online" cycle detection; read §3–4 after Lesson 19.4 §6.
    Note: DOI recorded from the proceedings; not re-resolved from the course container (doi.org is blocked there).
    Cited in: 04-andersen

  • [PKH07] David J. Pearce, Paul H. J. Kelly, and Chris Hankin. Efficient Field-Sensitive Pointer Analysis of C. ACM TOPLAS 30(1), article 4, 2007. doi:10.1145/1290520.1290524
    Why and when: Field sensitivity for C with pointer arithmetic, modelled as constraints with offsets ("Pearce's model", Lesson 19.6), and the cycle and positive-weight-cycle problems it creates. Read §3–5 after Lesson 19.6 §2.
    Note: DOI recorded from the journal; not re-resolved from the course container.
    Cited in: overview, 06-flow-and-field-sensitivity

  • [RC00] Atanas Rountev and Satish Chandra. Off-line Variable Substitution for Scaling Points-to Analysis. PLDI 2000, pp. 47–56, 2000. doi:10.1145/349299.349310
    Why and when: The first offline pre-pass that merges pointer-equivalent variables before solving (Lesson 19.4 §6); [HL07b] generalizes it.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 04-andersen

  • [Rey02] John C. Reynolds. Separation Logic: A Logic for Shared Mutable Data Structures. LICS 2002, pp. 55–74, 2002. doi:10.1109/LICS.2002.1029817
    Why and when: The separating conjunction and list-segment predicates behind separation-logic shape analyses (Infer). Read §1–3 after Lesson 19.9 §6.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 09-escape-and-shape

  • [SB06] Manu Sridharan and Rastislav Bodík. Refinement-Based Context-Sensitive Points-to Analysis for Java. PLDI 2006, pp. 387–400, 2006. doi:10.1145/1133981.1134027
    Why and when: Points-to as CFL reachability (matched field and call parentheses), answered on demand and refined only where the client needs more precision, under a budget. Read §3–4 after Lesson 19.8 §2.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 08-declarative-and-demand-driven

  • [SBL11] Yannis Smaragdakis, Martin Bravenboer, and Ondřej Lhoták. Pick Your Contexts Well: Understanding Object-Sensitivity. POPL 2011, pp. 17–30, 2011. doi:10.1145/1926385.1926390
    Why and when: A uniform model of context sensitivity that explains object sensitivity and introduces type sensitivity (contexts are the classes enclosing allocation sites). Read §3–5 after Lesson 19.7.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 07-context-sensitivity, 08-declarative-and-demand-driven

  • [Shi88] Olin Shivers. Control-Flow Analysis in Scheme. PLDI 1988, pp. 164–174, 1988. doi:10.1145/53990.54007
    Why and when: k-CFA: contexts as the last k call sites. The name and the parameter k of Lesson 19.7's call-string sensitivity come from here.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 07-context-sensitivity

  • [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 call-string and functional (summary) approaches to interprocedural analysis, the two poles of Lesson 19.7. Read §3 (call strings) and §4 (functional approach).
    Note: A book chapter; no DOI. Available in university libraries.
    Cited in: 07-context-sensitivity

  • [SRW02] Mooly Sagiv, Thomas Reps, and Reinhard Wilhelm. Parametric Shape Analysis via 3-Valued Logic. ACM TOPLAS 24(3), pp. 217–298, 2002. doi:10.1145/514188.514190
    Why and when: Shape analysis with three-valued logical structures, summary nodes and focus/blur (TVLA). Read §2–4 after Lesson 19.9 §2; the rest is for specialists.
    Note: DOI recorded from the journal; not re-resolved from the course container.
    Cited in: 09-escape-and-shape

  • [Ste96] Bjarne Steensgaard. Points-to Analysis in Almost Linear Time. POPL 1996, pp. 32–41, 1996. doi:10.1145/237721.237727
    Why and when: Core reading. The origin of unification-based points-to analysis: a type system whose inference is union-find, with conditional joins for non-pointers and λ types for functions. Read §3–5 after Lesson 19.5 §2; the lab's signatures for indirect calls are its λ types.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: overview, 05-unification

  • [SX16] Yulei Sui and Jingling Xue. SVF: Interprocedural Static Value-Flow Analysis in LLVM. CC 2016, pp. 265–266, 2016. doi:10.1145/2892208.2892235
    Why and when: The SVF framework whose Andersen (wave, diff), flow-sensitive and demand-driven solvers Lessons 19.4, 19.6 and 19.8 quote. A two-page tool paper; the SVF wiki has the details.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 04-andersen, 05-unification, 06-flow-and-field-sensitivity

  • [Tar75] Robert Endre Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM 22(2), pp. 215–225, 1975. doi:10.1145/321879.321884
    Why and when: The inverse-Ackermann bound for union by rank with path compression that Definition 19.5.1 and Theorem 19.5.8 cites. Read the statement of the main theorem; the proof is optional.
    Note: DOI recorded from the journal; not re-resolved from the course container.
    Cited in: 05-unification

  • [WACL05] John Whaley, Dzintars Avots, Michael Carbin, and Monica S. Lam. Using Datalog with Binary Decision Diagrams for Program Analysis. APLAS 2005, LNCS 3780, pp. 97–118, 2005. doi:10.1007/11575467_8
    Why and when: bddbddb: Datalog compiled to BDD operations, with variable-ordering search. Read §2–3 after Lesson 19.8 §6.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: 07-context-sensitivity, 08-declarative-and-demand-driven

  • [WL04] John Whaley and Monica S. Lam. Cloning-Based Context-Sensitive Pointer Alias Analysis Using Binary Decision Diagrams. PLDI 2004, pp. 131–144, 2004. doi:10.1145/996841.996859
    Why and when: Context sensitivity by cloning every acyclic call path (10^14 contexts) and representing the relations with BDDs in bddbddb. Read §2–4 after Lesson 19.7 §2 and Lesson 19.8.
    Cited in: 07-context-sensitivity, 08-declarative-and-demand-driven

Textbooks and monographs

  • [Dragon2] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed.. Addison-Wesley, 2006. Read: §12.3 (Datalog), §12.4 (a simple pointer-analysis algorithm), §12.5–12.6 (context-insensitive and context-sensitive pointer analysis), §12.7 (Datalog with BDDs).
    Why and when: The textbook treatment of flow-insensitive Andersen-style analysis in Datalog, cloning for context sensitivity and BDDs. Read §12.4 with Lesson 19.4 and §12.6–12.7 with Lessons 19.7–19.8.
    Cited in: overview, 08-declarative-and-demand-driven

  • [SPA] Anders Møller and Michael I. Schwartzbach. Static Program Analysis. Aarhus University (online lecture notes), 2024. Read: the chapter "Pointer Analysis" (allocation-site abstraction, Andersen's analysis, Steensgaard's analysis, interprocedural and null-pointer analysis) and the interprocedural-analysis chapter's context-sensitivity sections; cited by title because chapter numbers differ between editions. link
    Why and when: Short, precise chapters on Andersen and Steensgaard with cubic-algorithm framing and exercises; the best first textbook reading for Lessons 19.4–19.5.
    Note: Chapter numbers deliberately omitted: they changed between revisions of the notes and could not be checked against the current PDF (cs.au.dk is unreachable from the course container).
    Cited in: overview

  • [SSAB] Fabrice Rastello and Florent Bouchez Tichadou. SSA-based Compiler Design. Springer, 2022. Read: Ch. 16 (Hashed SSA form: HSSA — virtual variables for memory, μ and χ) and Ch. 17 (Array SSA form). doi:10.1007/978-3-030-80515-9
    Why and when: The SSA-book treatment of SSA for memory, from which LLVM's single-memory-variable design is the extreme case. Read Ch. 16 with Lesson 19.10 §6.
    Cited in: 10-memory-ssa

Surveys and tutorials

  • [Hin01] Michael Hind. Pointer Analysis: Haven't We Solved This Problem Yet?. PASTE 2001, pp. 54–61, 2001. doi:10.1145/379605.379665
    Why and when: Core reading. The map of the design space (flow, context, field sensitivity; heap naming; aggregate modelling) and a sober look at what precision buys clients. Read it first, before the lessons, and again after Lesson 19.7.
    Note: DOI recorded from the proceedings; not re-resolved from the course container.
    Cited in: overview, 01-memory-and-alias-queries, 06-flow-and-field-sensitivity

Theses and technical reports

  • [And94] Lars Ole Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen (DIKU report 94/19), 1994. link
    Why and when: Core reading. The origin of inclusion-based ("Andersen-style") points-to analysis: Ch. 4 states the subset constraints for C and solves them. Read Ch. 4 after Lesson 19.4 §2; the lesson's four constraint forms are a simplification of Andersen's type-directed rules.
    Note: The Cornell course copy of the thesis; not re-fetched from the course container.
    Cited in: overview, 04-andersen

Source code (pinned versions)

  • [CIL-PTA] CIL's points-to analyses (olf.ml one-level flow, steensgaard.ml, golf.ml) — src/ext/pta/olf.ml in cil-project/cil at cil-1.7.3. Symbols: leq_int, unify_int, add_toplev_constraint.
    Why and when: Lesson 19.5's production implementations of Steensgaard and Das's one-level flow, in OCaml; steensgaard.ml in the same directory is the unification analysis.
    Cited in: 05-unification

  • [GCC-StructAlias] GCC's points-to analysis (field-sensitive Andersen with HVN, HCD and LCD-style cycle collapsing) — gcc/tree-ssa-structalias.cc in gcc-mirror/gcc at releases/gcc-14.2.0. Symbols: solve_constraints, perform_var_substitution, find_indirect_cycles, solve_graph, get_constraint_for_component_ref.
    Why and when: The production inclusion-based solver of Lessons 19.4 and 19.6; the phases printed by -fdump-tree-ealias-details are these functions. Its comments cite Pearce–Kelly–Hankin, Heintze–Tardieu, Nuutila's SCC algorithm and Hardekopf–Lin (lazy cycle detection, and pointer/location equivalence). GCC 14.2 is the version installed in the course container.
    Cited in: 04-andersen, 06-flow-and-field-sensitivity, 07-context-sensitivity

  • [GCC-TreeAlias] GCC's alias oracle (the query layer over points-to sets and type-based rules) — gcc/tree-ssa-alias.cc in gcc-mirror/gcc at releases/gcc-14.2.0. Symbols: refs_may_alias_p_1, ptr_derefs_may_alias_p, call_may_clobber_ref_p, ref_maybe_used_by_call_p, aliasing_component_refs_p, same_type_for_tbaa.
    Why and when: GCC's counterpart of LLVM's AAResults: reference-reference and call-reference queries that combine points-to sets (tree-ssa-structalias.cc), access-path rules and TBAA alias sets. Read after Lesson 19.1 §7.
    Cited in: 01-memory-and-alias-queries, 02-local-alias-rules, 03-type-and-scope-rules, 04-andersen

  • [Go-Escape] The Go compiler's escape analysis — src/cmd/compile/internal/escape/escape.go in golang/go at go1.24.7. Symbols: Batch, escape.go header comment (the "data-flow graph" of locations).
    Why and when: Lesson 19.9's Go example: a weighted data-flow graph of locations, whose header comment states the two invariants (no pointer to a stack object is stored in the heap or outlives the object).
    Cited in: 07-context-sensitivity, 09-escape-and-shape

  • [HotSpot-EA] HotSpot C2 escape analysis (connection graph after Choi et al.) — src/hotspot/share/opto/escape.cpp in openjdk/jdk21u at jdk-21.0.10+7. Symbols: ConnectionGraph::compute_escape, ConnectionGraph::find_non_escaped_objects.
    Why and when: Lesson 19.9 §7: C2's connection graph, scalar replacement and lock elimination.
    Cited in: 09-escape-and-shape

  • [Infer-Biabduction] Infer's separation-logic heap predicates (points-to, list segments) — infer/src/biabduction/Predicates.mli in facebook/infer at v1.2.0. Symbols: hpred0, lseg_kind.
    Why and when: Lesson 19.9's shape-analysis box: the symbolic heaps of bi-abduction [CDOY09].
    Cited in: 09-escape-and-shape

  • [LLVM-AA] The AAResults aggregation (ask each AA in turn, stop at a definite answer) — llvm/lib/Analysis/AliasAnalysis.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: AAResults::alias, AAResults::getModRefInfo, AAResults::callCapturesBefore.
    Why and when: Lesson 19.1 §7: how the chain of AAs is queried and how call mod/ref combines memory effects with alias queries.
    Cited in: 01-memory-and-alias-queries

  • [LLVM-BasicAA] BasicAA, LLVM's local alias rules — llvm/lib/Analysis/BasicAliasAnalysis.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: BasicAAResult::aliasCheck, BasicAAResult::aliasGEP, BasicAAResult::aliasPHI, BasicAAResult::aliasSelect, BasicAAResult::DecomposeGEPExpression, EarliestEscapeAnalysis.
    Why and when: Lesson 19.2's algorithm in production: underlying objects, GEP decomposition into a constant offset plus scaled variable indices, phi/select recursion.
    Cited in: 01-memory-and-alias-queries, 02-local-alias-rules

  • [LLVM-CaptureTracking] Capture tracking (does a pointer escape?) — llvm/lib/Analysis/CaptureTracking.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: llvm::PointerMayBeCaptured, llvm::PointerMayBeCapturedBefore, llvm::DetermineUseCaptureKind.
    Why and when: The use-walk of Algorithm 19.2.7, with the use-count cap; read after Lesson 19.2 §4.
    Cited in: 02-local-alias-rules

  • [LLVM-DSE] MemorySSA-based dead store elimination — llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DSEState::getDomMemoryDef, DSEState::isCompleteOverwrite, DSEState::isGuaranteedLoopInvariant, tryToShorten, DSEState::eliminateRedundantStoresOfExistingValues, eliminateDeadStores.
    Why and when: Lesson 19.11's DSE in production: the walk from a dead candidate to a killing def, the partial-overwrite intervals and tryToShorten; compare with exercise E1.
    Cited in: 11-memory-optimizations

  • [LLVM-FunctionAttrs] Bottom-up memory and capture summaries over call-graph SCCs — llvm/lib/Transforms/IPO/FunctionAttrs.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: addMemoryAttrs, addArgumentAttrs.
    Why and when: Lesson 19.7's summary-based context sensitivity in LLVM: memory(...) and captures(none) inferred per function and reused at every call site.
    Cited in: 07-context-sensitivity

  • [LLVM-GlobalsAA] GlobalsAA (mod/ref of non-address-taken internal globals per function) — llvm/lib/Analysis/GlobalsModRef.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: GlobalsAAResult::AnalyzeGlobals, GlobalsAAResult::AnalyzeCallGraph, GlobalsAAResult::getModRefInfo.
    Why and when: Lesson 19.2's GlobalsAA: which globals escape, and bottom-up mod/ref over call-graph SCCs; note the nosync/nocallback conditions for declarations.
    Cited in: 02-local-alias-rules

  • [LLVM-GVN] GVN's load elimination and load PRE — llvm/lib/Transforms/Scalar/GVN.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: GVNPass::processLoad, GVNPass::PerformLoadPRE, GVNPass::AnalyzeLoadAvailability.
    Why and when: Lesson 19.11's store-to-load forwarding and load PRE (via MemoryDependenceAnalysis); compare AnalyzeLoadAvailability with exercise E2.
    Cited in: 11-memory-optimizations

  • [LLVM-Inliner-noalias] How the inliner turns noalias parameters into scoped metadata — llvm/lib/Transforms/Utils/InlineFunction.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: AddAliasScopeMetadata.
    Why and when: Lesson 19.3 §7: the translation that keeps restrict alive after inlining.
    Cited in: 03-type-and-scope-rules

  • [LLVM-LICM] LICM scalar promotion (must-alias sets, load-only promotion) — llvm/lib/Transforms/Scalar/LICM.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: collectPromotionCandidates, llvm::promoteLoopAccessesToScalars.
    Why and when: Lesson 19.11 §7: the candidate sets, "reads outside the set" and why the store may stay in the loop.
    Cited in: 11-memory-optimizations

  • [LLVM-MemCpyOpt] MemCpyOpt (store merging, memcpy forwarding, memset formation, call-slot optimization) — llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MemCpyOptPass::tryMergingIntoMemset, MemCpyOptPass::processMemCpyMemCpyDependence, MemCpyOptPass::performMemCpyToMemSetOptzn, MemCpyOptPass::performCallSlotOptzn.
    Why and when: Lesson 19.11's memcpyopt; read the four named transforms after its box.
    Cited in: 11-memory-optimizations

  • [LLVM-MSSA] MemorySSA construction, renaming, use optimization and the clobber walker — llvm/lib/Analysis/MemorySSA.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MemorySSA::buildMemorySSA, MemorySSA::placePHINodes, MemorySSA::renamePass, ClobberWalker::findClobber, MemorySSA::OptimizeUses::optimizeUsesInBlock, MaxCheckLimit.
    Why and when: Lesson 19.10 §7 reads placePHINodes (IDF), renamePass and the walker with its memssa-check-limit of 100.
    Cited in: 10-memory-ssa

  • [LLVM-ScopedNoAlias] Scoped noalias AA (alias.scope / noalias metadata) — llvm/lib/Analysis/ScopedNoAliasAA.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ScopedNoAliasAAResult::alias, ScopedNoAliasAAResult::mayAliasInScopes.
    Why and when: Algorithm 19.3.6's subset test in about 30 lines; read after Lesson 19.3 §2.
    Cited in: 03-type-and-scope-rules

  • [LLVM-SROA] Scalar replacement of aggregates — llvm/lib/Transforms/Scalar/SROA.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: AllocaSlices, SROA::runOnAlloca, SROA::splitAlloca, SROA::promoteAllocas.
    Why and when: Lesson 19.11's SROA: slices, partitions, rewriting and the final PromoteMemToReg.
    Cited in: 11-memory-optimizations

  • [LLVM-TBAA] Struct-path TBAA — llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: matchAccessTags, mayBeAccessToSubobjectOf, getLeastCommonType, TBAAStructTypeNode::getField.
    Why and when: Algorithm 19.3.4 is a transcription of matchAccessTags; the header comment explains the type DAG. The drill tbaa-query uses the same logic.
    Cited in: 03-type-and-scope-rules

  • [SVF-DDA] SVF's demand-driven, context-sensitive points-to queries with budgets — svf/lib/DDA/ContextDDA.cpp in SVF-tools/SVF at SVF-3.3. Symbols: ContextDDA::computeDDAPts, ContextDDA::handleOutOfBudgetDpm.
    Why and when: Lesson 19.8's demand-driven analysis with refinement budgets.
    Cited in: 08-declarative-and-demand-driven

  • [SVF-FS] SVF's staged, sparse flow-sensitive points-to analysis — svf/lib/WPA/FlowSensitive.cpp in SVF-tools/SVF at SVF-3.3. Symbols: FlowSensitive::initialize, FlowSensitive::processSVFGNode.
    Why and when: Lesson 19.6's SFS: an auxiliary Andersen builds the SVFG (sparse value-flow graph), and the flow-sensitive solver runs on it.
    Cited in: 06-flow-and-field-sensitivity

  • [SVF-Wave] SVF's wave-propagation Andersen with difference propagation — svf/lib/WPA/AndersenWaveDiff.cpp in SVF-tools/SVF at SVF-3.3. Symbols: AndersenWaveDiff::solveWorklist, AndersenWaveDiff::postProcessNode.
    Why and when: Lesson 19.4's wave propagation in a maintained research framework.
    Cited in: 04-andersen

Official documentation and specifications

  • [C11] ISO/IEC 9899:2011 (C11), committee draft N1570: §6.5 ¶6–7 (effective type and the aliasing rule), §6.7.3.1 (formal definition of restrict). N1570 (2011-04-12). link
    Why and when: Core reading. The rules TBAA and restrict rely on. Read §6.5 ¶6–7 with Lesson 19.3 §2 (which lvalue types may access an object) and §6.7.3.1 with Lesson 19.3's restrict section.
    Cited in: overview, 03-type-and-scope-rules

  • [CPP-basiclval] C++ working draft, [basic.lval] ¶11 (the type-access rule) and [cstddef.syn] (std::byte). C++ working draft (eel.is/c++draft). link
    Why and when: C++'s version of the aliasing rule: an object may be accessed through its dynamic type, a signed/unsigned variant, or char, unsigned char or std::byte. Read with Lesson 19.3 §2.
    Cited in: 03-type-and-scope-rules

  • [GCC-StrictAliasing] GCC manual: -fstrict-aliasing (Optimize Options). GCC 14. link
    Why and when: GCC's statement of when type-based aliasing is assumed, with the union-punning exception GCC documents. Read with Lesson 19.3 §4.
    Cited in: 03-type-and-scope-rules

  • [LLVM-AADoc] LLVM Alias Analysis Infrastructure. LLVM 23.1.2. link
    Why and when: Core reading. The AliasAnalysis interface (MemoryLocation, AliasResult, ModRefInfo), how AA implementations are chained, and aa-eval. Read with Lesson 19.1.
    Cited in: overview, 01-memory-and-alias-queries

  • [LLVM-LangRef] LLVM Language Reference Manual. LLVM 23.1.2. link
    Why and when: Read the sections "tbaa Metadata", "'noalias' and 'alias.scope' Metadata", the noalias parameter attribute and "Pointer Aliasing Rules" with Lessons 19.1–19.3.
    Cited in: 03-type-and-scope-rules

  • [LLVM-MemorySSADoc] LLVM MemorySSA documentation. LLVM 23.1.2. link
    Why and when: Core reading. MemoryDef, MemoryUse, MemoryPhi, liveOnEntry, walkers and use optimization, in LLVM's words. Read with Lesson 19.10 §2 and before exercise E1.
    Cited in: overview, 10-memory-ssa

  • [SOUFFLE-DOC] Soufflé: project README and language documentation. Soufflé 2.5. link
    Why and when: The Datalog dialect of the Lesson 19.7–19.8 boxes, including eqrel. Read before running the Soufflé boxes.
    Cited in: 08-declarative-and-demand-driven