Chapter 19 · Memory: Alias Analysis & Memory Optimizations¶
Part 4 · Optimization · about 3 weeks · Previous: Ch 18 · Next: Ch 20
The problem¶
After mem2reg (Ch 16) everything whose address is taken — arrays, structs, heap objects, globals, locals passed by pointer — stays in memory, reached through load, store, getelementptr and calls. The input of this chapter is such a program (LLVM IR, or the small pointer language of Lessons 19.4–19.8); the output is twofold. First, alias information: for two memory accesses, can they touch the same bytes (NoAlias, MayAlias, PartialAlias, MustAlias)? For an instruction and a location, may it read or write it (mod/ref)? For a pointer, which allocation sites may it point to (points-to sets)? Second, memory optimizations that use it: scalar replacement of aggregates, dead-store elimination, store-to-load forwarding and load PRE, MemCpyOpt and scalar promotion, organised around Memory SSA's def-use chains for memory. Exact aliasing is undecidable (Theorem 19.1.8), so every analysis approximates, always towards "may alias". In LLVM 23 the analyses are basic-aa, tbaa, scoped-noalias-aa, globals-aa and MemorySSA, and the transformations sroa, dse, gvn, memcpyopt and licm; in pebblec your pebble-dse and pebble-loadfwd run on them, and your comparison lab implements the whole-program points-to analyses LLVM does not ship.
What you will be able to do¶
- Answer alias and mod/ref queries on concrete IR by BasicAA's rules (objects, offsets, sizes, capture), TBAA's struct paths and scoped
noaliastags, and predict what an AA pipeline returns. - Solve Andersen's inclusion constraints by hand (worklist, every step), identify the cycles a detector collapses, and prove the cubic bound and the soundness theorem.
- Run Steensgaard's unification and Das's one-level flow by hand, and prove Andersen ⊆ Das ⊆ Steensgaard.
- Explain what flow, field and context sensitivity (call strings, cloning, summaries, object and type sensitivity) buy and cost, and read a Datalog formulation of each.
- Build Memory SSA for a function by hand — numbering, phis at the iterated dominance frontier, renaming, optimized uses — and check it against
opt -passes='print<memoryssa>'. - Implement
pebble-dseandpebble-loadfwdon LLVM'sAAResultsandMemorySSA, and Andersen and Steensgaard over LLVM IR; check soundness at run time and measure precision and speed. - Find where LLVM 23, GCC 14, Go and HotSpot implement each technique, and read the relevant code.
Prerequisites: Ch 9 (the memory model, GEP, noalias, TBAA metadata), Ch 14 (lattices and least fixed points, worklists, Datalog in Lesson 14.8), Ch 15 (dominators, iterated dominance frontiers, SCCs), Ch 16 (SSA construction, mem2reg, Memory SSA in Lesson 16.8), Ch 17 (GVN, PRE, DSE in Lesson 17.3). Ch 18's LICM is referenced for scalar promotion.
Notation¶
Shared notation follows the house notation: §1 (sets, functions, logic), §2 (orders and lattices), §3 (graphs), §4 (dominance, \(\mathrm{DF}^{+}\)), §7 (dataflow, SSA). Orientation: points-to sets grow up the lattice (\(\subseteq\)), and \(\mathrm{pts}^*\) is a least solution; the precision order of alias answers puts MayAlias at the bottom. In this chapter:
| Symbol | Meaning |
|---|---|
| \(L = (p, s)\), \(\llbracket L \rrbracket\) | a memory location (pointer, size); the byte interval it denotes (Definition 19.1.1) |
| \(\mathsf{No}\), \(\mathsf{May}\), \(\mathsf{Partial}\), \(\mathsf{Must}\) | the four alias answers (Definition 19.1.2) |
| \(\mathit{MR}(I, L)\) | mod/ref information: a subset of \(\{\mathsf{ref}, \mathsf{mod}\}\) (Definition 19.1.4) |
| \(\mathrm{obj}(p)\) | the underlying object of a pointer (Definition 19.2.1) |
| \((B, A, o)\) | a TBAA access tag: base type, access type, offset (Definition 19.3.2) |
| \(\mathrm{AS}(I)\), \(\mathrm{NA}(I)\) | !alias.scope and !noalias scope lists (Definition 19.3.5) |
| \(V\), \(\mathit{Obj}\) | variables of a pointer program; address-taken variables (objects) (Definition 19.4.1) |
| \(\mathrm{pts}(v)\), \(\mathrm{pts}^*\) | a points-to set; the least solution of the inclusion constraints (Definition 19.4.2) |
| \(p = \&a\), \(p = q\), \(p = {*}q\), \({*}p = q\) | the four statement forms (Definition 19.4.1) |
| \(\mathrm{find}(x)\), \(\mathrm{ptr}(C)\) | union-find representative; the class that class \(C\) points to (Definitions 19.5.1–19.5.2) |
| \(\mathrm{val}(v)\), \(D(n)\) | Das's value node and dereference node (Definition 19.5.4) |
| \(\alpha(m, n)\) | the inverse Ackermann function (Definition 19.5.1) |
| \(G^{\mathrm{in}}_\ell\), \(G^{\mathrm{out}}_\ell\) | flow-sensitive points-to graphs at a program point (Definition 19.6.1) |
| \(o.k\) | field (offset) \(k\) of object \(o\) (Definition 19.6.4) |
| \(\mathit{Ctx}\), \(\mathrm{push}\), \(\pi\) | contexts, the context of a callee, projection (Definition 19.7.1) |
| \(\mathsf{NoEscape} \sqsubset \mathsf{ArgEscape} \sqsubset \mathsf{GlobalEscape}\) | escape states (Definition 19.9.1) |
| \(x \mapsto y\), \(\mathrm{lseg}(x, y)\), \(\ast\) | separation-logic points-to, list segment, separating conjunction (Definition 19.9.4) |
| MemoryDef, MemoryUse, MemoryPhi, liveOnEntry | Memory SSA accesses; phi@B is the MemoryPhi of block B (Definition 19.10.1) |
| \(n\), \(m\), \(k\), \(a\) | numbers of variables (or blocks), statements, objects, memory accesses — each complexity section restates its variables |
Numbered statements are N.k.m (chapter, lesson, counter), as in NOTATION.md §9.
Technique map¶
| Family | Techniques (origin) | Lesson |
|---|---|---|
| Alias queries and the AA interface | may/must/partial/no alias queries over memory locations and mod/ref queries (the vocabulary surveyed by Hind 2001; LLVM AAResults); chaining analyses into a pipeline (LLVM AAManager, GCC's alias oracle) |
19.1 |
| Local alias rules | BasicAA-style reasoning: distinct allocations, GEP decomposition and offset arithmetic, object sizes, phi/select (LLVM); capture/escape tracking (LLVM CaptureTracking); GlobalsAA (mod/ref of non-address-taken globals) |
19.2 |
| Language rules | Type-based alias analysis (Diwan, McKinley & Moss 1998; C/C++ strict aliasing with the char/std::byte exemption; LLVM struct-path TBAA); scoped noalias (C99/C11 restrict, LLVM noalias and scoped metadata created by the inliner) |
19.3 |
| Inclusion-based points-to | Andersen's analysis (Andersen 1994); online cycle detection (Pearce, Kelly & Hankin 2003), lazy and hybrid cycle detection (Hardekopf & Lin 2007), offline variable substitution (Rountev & Chandra 2000; Hardekopf & Lin 2007); wave and deep propagation (Pereira & Berlin 2009) | 19.4 |
| Unification-based points-to | Steensgaard's analysis (Steensgaard 1996; union-find by Tarjan 1975); Das's one-level flow (Das 2000) | 19.5 |
| Flow and field sensitivity | Dense and staged sparse flow-sensitive analysis, SFS (Hardekopf & Lin 2011); field-insensitive, field-based and field-sensitive models, Pearce's offset constraints (Pearce, Kelly & Hankin 2007) | 19.6 |
| Context sensitivity | Call strings and k-CFA (Sharir & Pnueli 1981; Shivers 1988); cloning (Whaley & Lam 2004) and summaries (Sharir & Pnueli's functional approach; LLVM function attributes); object sensitivity (Milanova, Rountev & Ryder 2005) and type sensitivity (Smaragdakis, Bravenboer & Lhoták 2011) | 19.7 |
| Declarative and demand-driven analysis | Points-to in Datalog (Doop: Bravenboer & Smaragdakis 2009; Soufflé: Jordan, Scholz & Subotić 2016; BDDs in bddbddb: Whaley & Lam 2004, Whaley et al. 2005); demand-driven analysis (Heintze & Tardieu 2001; refinement-based CFL reachability, Sridharan & Bodík 2006) | 19.8 |
| Escape and shape analysis | Escape analysis (Choi et al. 1999; Go, HotSpot C2); shape analysis overview (three-valued logic and TVLA: Sagiv, Reps & Wilhelm 2002; separation logic: Reynolds 2002; bi-abduction in Infer: Calcagno et al. 2009) | 19.9 |
| Memory SSA | MemoryDef/Use/Phi, clobber walkers, optimized uses, cost limits (Novillo 2007; LLVM MemorySSA) |
19.10 |
| Memory optimizations | SROA (LLVM); MemorySSA-based dead-store elimination (LLVM dse); store-to-load forwarding and load PRE (LLVM GVN); MemCpyOpt (LLVM); LICM scalar promotion (LLVM LICM, Ch 18) |
19.11 |
flowchart LR
Q[Alias and mod/ref queries] --> BA[BasicAA + capture]
Q --> TB[TBAA / scoped noalias]
Q --> GA[GlobalsAA]
A94[Andersen 1994<br/>inclusion] -->|cycle collapse| CD[Online / lazy / hybrid<br/>cycle detection]
A94 -->|rounds in topological order| WV[Wave / deep propagation]
A94 -->|equalities instead of inclusions| ST[Steensgaard 1996<br/>unification]
ST -->|inclusion at the top level| DAS[Das 2000<br/>one-level flow]
A94 -->|per program point, staged| SFS[SFS 2011]
A94 -->|per field / offset| FS[Field sensitivity]
A94 -->|per context| CS[Call strings / cloning /<br/>object and type sensitivity]
A94 -->|rules| DL[Datalog: Doop, Soufflé, bddbddb]
A94 -->|per query| DD[Demand-driven]
A94 -->|reachability from roots| EA[Escape analysis]
EA -->|heap structure| SH[Shape analysis]
BA --> MSSA[Memory SSA + walker]
TB --> MSSA
MSSA --> OPT[SROA · DSE · forwarding/PRE ·<br/>MemCpyOpt · LICM promotion]Who uses what¶
| System | Technique | Notes |
|---|---|---|
| LLVM 23 | BasicAA, scoped-noalias, TBAA, GlobalsAA in the AA pipeline; capture tracking; function-attrs summaries; MemorySSA; SROA, DSE, GVN (forwarding, load PRE), MemCpyOpt, LICM promotion; no whole-program points-to (CFL-Steens/Anders removed after LLVM 15) | lessons 19.1–19.3, 19.7, 19.10–19.11 |
| GCC 14 | Andersen-style, field-sensitive points-to (tree-ssa-structalias.cc: offline variable substitution, HCD, LCD) under an alias oracle (tree-ssa-alias.cc) with TBAA alias sets; .MEM virtual operands; SRA, DSE, FRE/PRE |
19.4, 19.6 |
| Go 1.24 | escape analysis deciding stack vs heap for every allocation, with per-parameter summaries | 19.9 |
| HotSpot (JDK 21) | C2 escape analysis on connection graphs: scalar replacement, lock elimination | 19.9 |
| SVF 3.3 | Andersen (wave + difference propagation), Steensgaard, staged flow-sensitive, demand-driven context-sensitive analyses over LLVM IR | 19.4, 19.6, 19.8 |
| Doop / Soufflé | Java points-to in Datalog with call-site, object and type sensitivity | 19.7, 19.8 |
| CIL | Steensgaard, one-level flow and Golf points-to analyses for C | 19.5 |
| Facebook Infer | separation-logic shape analysis with bi-abduction | 19.9 |
| Pebble | pebble-dse, pebble-loadfwd; the lab's Andersen (+★ cycle elimination) and Steensgaard with run-time soundness checks |
exercises, lab |
Comparison¶
The fixed columns follow docs/authoring/DEPTH_CONTRACT.md §3 item 8; each lesson repeats its own rows and defines its variables.
Memory and alias queries: may, must, partial and no alias; mod/ref; AA pipelines (lesson 19.1)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Alias queries | Four answers; PartialAlias/MustAlias need offsets and sizes; soundness only in the "may" direction | per query \(O(d \cdot g)\) for local AAs · microseconds, cached per pass | aa-eval prints every pair; answers explain nothing about why |
Low for the interface, high for good members | every memory transform (DSE, GVN, LICM, vectorizer) |
| Mod/ref queries | Four-point lattice per instruction; calls limited by memory effects and escape facts | \(O(r \cdot q)\) per call query | aa-eval -print-all-alias-modref-info |
Medium (memory-effect attributes, capture tracking) | MemorySSA construction, DSE, LICM around calls |
| AA pipelines | At least as precise as each member (Proposition 19.1.9); inherits any member's unsoundness | \(\le k\) member queries, early exit | the answer, not the member that gave it | Low (a list); ordering matters for speed | LLVM AAManager, -aa-pipeline; GCC's single oracle |
Local alias rules: BasicAA, capture tracking, GlobalsAA (lesson 19.2)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| BasicAA | Local facts only: distinct allocations, offsets, sizes, phi/select; nothing about what arguments or loaded pointers point to | \(O(D \cdot g)\) per query, cached · the cheapest AA | Four answers with offsets (PartialAlias) | Medium (many rules, many corner cases) | First member of every LLVM AA pipeline |
| Capture tracking | Decides "private local" exactly for the use patterns it knows; conservative on any other use | \(O(\min(u, 100))\) per pointer | yes/no (plus capture components) | Low–medium | BasicAA escape sources, DSE at function exit, call mod/ref, captures(none) inference |
| GlobalsAA | Mod/ref of calls for internal non-address-taken globals; gives up on indirect calls and callbacks | \(O(I + C)\) once per module | per-function mod/ref summaries | Medium (call graph, SCC order) | LLVM -O2 module pass; GCC ipa-reference |
Language rules as alias facts: type-based alias analysis and scoped noalias (lesson 19.3)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| TBAA | Separates accesses of unrelated types and different struct paths; nothing for same-type accesses through different pointers; unsound for programs that type-pun | \(O(h + w)\) per query · very cheap | May/No per pair of tags; tags are readable in the IR | Front end: map the language's types to a DAG; back end: ~700 lines | C/C++ at -O1+; disabled by -fno-strict-aliasing (Linux kernel, many embedded code bases) |
| Scoped noalias | Separates accesses based on different restrict/noalias pointers, also after inlining; exactly as good as the programmer's promises |
\(O(\lvert \mathrm{AS} \rvert + \lvert \mathrm{NA} \rvert)\) per query | No/May; scopes are named after the parameter | Inliner translation plus a ~200-line AA | Numerical kernels (restrict), Rust &mut, Fortran dummy arguments |
Inclusion-based points-to analysis: Andersen, cycle detection, wave and deep propagation (lesson 19.4)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Andersen's analysis | The most precise flow- and context-insensitive analysis for the model (least solution); on the lab corpus 45 of 224 alias pairs MayAlias, vs 51 for Steensgaard | \(O(n^3)\) with difference propagation · 75 s on the lab's 4000-variable stress input without cycle detection | One set per pointer; exact least solution, easy to inspect | Low for the basic solver (~200 lines), medium with all optimizations | GCC's points-to; SVF; static analyzers; the lab |
| Cycle detection (online, lazy, hybrid) | Same sets (Theorem 19.4.14) | same bound · 40× faster than plain on the lab's stress run (1.8 s vs 75 s) | Same sets; collapsed-node counts | Medium (union-find, Tarjan, triggered edges) | GCC (HCD + LCD), SVF, research solvers |
| Wave / deep propagation | Same sets (Theorem 19.4.15) | few rounds of linear work on typical graphs; worst case as above | Same sets | Medium (SCCs and topological order per round) | SVF (AndersenWaveDiff), research |
Unification-based points-to analysis: Steensgaard and Das's one-level flow (lesson 19.5)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Steensgaard's analysis | Coarsest of the three: ⊇ Andersen (Corollary 19.5.7); 51 vs 45 MayAlias pairs of 224 on the lab corpus, 28 vs 15 of 36 on the running example | \(O((n + m)\,\alpha)\) · 0.3 s on the 4000-variable stress input (Andersen: 75 s, 1.8 s with cycles) | One class per pointee: a storage-shape graph; sets are shared, so large | Low (union-find, ~150 lines) | Very large code bases, first pass of demand-driven or staged analyses, CIL, historic LLVM CFL-AA |
| Das's one-level flow | Between the two (Theorem 19.5.9); equal to Andersen on the running example's top-level u |
near-linear · close to Steensgaard [Das00] | Flow graph + classes | Medium (flow edges plus unification) | Large C programs where Steensgaard is too coarse (Das's MSR tools), CIL's olf |
Flow sensitivity and field sensitivity (lesson 19.6)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Flow-sensitive points-to (SFS) | Per-point facts with strong updates; ⊆ Andersen (Theorem 19.6.6); SFS = dense (Theorem 19.6.7) | dense: infeasible at scale · SFS: auxiliary + sparse, millions of lines [HL11] | Sets per SSA variable and per memory version | High (memory SSA per object, strong-update rules) | SVF, bug finders (null dereference, use-after-free), security analyses |
| Field sensitivity | field-sensitive ⊆ field-insensitive (Theorem 19.6.8); field-based incomparable, unsound for C | locations × fields · slower than field-insensitive [PKH07] | Sets per field (s.0+64) |
Medium (offsets, PWC collapse) | GCC's points-to, SVF, Java analyses (field-based or field-sensitive) |
Context sensitivity: call strings, cloning and summaries, object and type sensitivity (lesson 19.7)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Call-string sensitivity (k-CFA) | Separates calls by the last \(k\) call sites; wrappers deeper than \(k\) merge | \(S^k\) contexts · 1–2-CFA feasible | Facts per (context, variable) | Low on top of a solver (a push function) | Functional-language CFA, C analyzers, Doop's call-site variants |
| Cloning and summaries | Cloning: exact for non-recursive programs; summaries: the same with one analysis per function (Theorem 19.7.9) | cloning exponential (BDDs); summaries linear to exponential in summary size | Per-path facts, or per-function summaries | High (BDDs, or symbolic summaries) | bddbddb; LLVM function-attrs and Go parameter tags (coarse summaries) |
| Object and type sensitivity | Object: the most useful for OO code; type: coarser (Theorem 19.7.10) | \(H^k\) / \(T^k\) contexts · 2-object+1-heap practical; type much cheaper | Facts per receiver object or class | Medium (heap contexts) | Java analyses (Doop, WALA, Soot) |
Points-to analysis as Datalog, and on demand (lesson 19.8)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Datalog points-to | Whatever the rules say: Andersen (Theorem 19.8.5) or context/field-sensitive variants | \(O(n^3)\) derivations · Soufflé is competitive with hand-written solvers [BS09, JSS16] | Relations you can query; every fact has a derivation (provenance) | Very low for the analysis (a page of rules), high for the engine | Doop, CodeQL, research; the Lab 14 engine |
| Demand-driven points-to | Exact per query (Theorem 19.8.6), or budget-limited | proportional to the relevant part · fast for few queries | Answers per query; "out of budget" fallback | Medium–high (caching, budgets) | IDE analyses, bug finders, SVF DDA, JIT-time queries |
Escape analysis and shape analysis (lesson 19.9)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Escape analysis | Three states per allocation site; flow-insensitive per method (partial EA adds path sensitivity) | near-linear per method · runs on every Go build and every C2 compilation | Per-site decisions ("moved to heap: q"); explains allocations | Medium | Go (stack vs heap), HotSpot C2 and Graal (scalar replacement, lock elision) |
| Shape analysis | Proves list/tree shapes, acyclicity, disjointness; far beyond points-to | exponential · seconds to minutes per procedure | Symbolic heaps or 3-valued structures; can prove memory safety | High | Verifiers and bug finders (Infer, TVLA-based research tools) |
Memory SSA in depth: accesses, clobber walkers, optimized uses and cost limits (lesson 19.10)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| MemorySSA | Def-use chains for all memory; precision comes from the walker's alias queries (one variable, refined on demand); bounded by \(K\) | construction linear · queries capped at 100 steps | print<memoryssa>, print<memoryssa-walker>; readable versions |
High (~2,700 lines plus the updater); for clients, low | LLVM DSE, LICM, EarlyCSE, NewGVN; GCC's .MEM virtual operands |
Memory optimizations: SROA, dead-store elimination, forwarding and load PRE, MemCpyOpt, LICM promotion (lesson 19.11)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| SROA | Removes whole aggregates with constant-offset uses; blocked by escaping or variable-offset uses | \(O(s \log s)\) per alloca · runs several times per pipeline | Promoted SSA values; readable IR | High (~6,400 lines in SROA.cpp: slicing, rewriting, types) |
LLVM SROA, GCC SRA; essential for C++ abstraction removal |
| Dead-store elimination | Complete and partial overwrites, stores dead at exit; limited by mod/ref of calls | per store \(O(\min(K, a))\) · capped scans | Deleted or shortened stores | High in LLVM, medium for E1 | LLVM dse (function simplification pipeline), GCC dse |
| Store-to-load forwarding and load PRE | Forwarding needs a dominating available value; PRE handles one missing predecessor | per load one clobber query (+ PRE per predecessor) | Replaced loads, inserted .pre loads and phis |
Medium (E2), high (GVN) | LLVM GVN and EarlyCSE; GCC FRE/PRE |
| MemCpyOpt | Pattern-based: memset formation, copy forwarding, call-slot | linear with MemorySSA queries | Fewer, larger intrinsics | Medium–high | LLVM memcpyopt (after SROA and before DSE) |
| LICM scalar promotion | Whole loops' accesses to one must-alias location; full or load-only | alias sets per loop, capped | Preheader load, exit stores, header phis | Medium (SSA updater, safety) | LLVM LICM, GCC tree-ssa-loop-im.cc |
Comparison-lab results (reproduce with build/<preset>/bin/ch19-pointsto --table labs/ch19-points-to/corpus/*.ll and --stress N on a solution build): on the five corpus programs (59 query pointers, 224 pairs), Andersen answers MayAlias for 45 pairs and Steensgaard for 51; Andersen with lazy cycle detection gives identical sets and collapses 13 nodes. On random programs with 4000 variables and 12 000 statements, Andersen takes about 75 s, Andersen with lazy cycle detection 1.8 s (10 269 nodes collapsed) and Steensgaard 0.3 s.
Route through this chapter¶
| Step | What | Techniques | How it is exercised |
|---|---|---|---|
| 1 | Lesson 19.1 | alias and mod/ref queries, AA pipelines | quiz; flashcards |
| 2 | Lesson 19.2 | BasicAA, capture tracking, GlobalsAA | quiz; gep-offset drill (Ch 9) |
| 3 | Lesson 19.3 | TBAA, scoped noalias / restrict | drill tbaa-query |
| 4 | Lesson 19.4 | Andersen, cycle detection, wave propagation | drill points-to-andersen; lab |
| 5 | Lesson 19.5 | Steensgaard, Das | drill points-to-steensgaard; lab |
| 6 | Lesson 19.6 | SFS, field sensitivity | quiz; lab ★ |
| 7 | Lesson 19.7 | call strings, cloning and summaries, object/type sensitivity | quiz; Soufflé boxes |
| 8 | Lesson 19.8 | Datalog, demand-driven | quiz; your Lab 14 Datalog engine |
| 9 | Lesson 19.9 | escape analysis, shape analysis | quiz; flashcards |
| 10 | Lesson 19.10 | Memory SSA | drill memoryssa-build |
| 11 | Lesson 19.11 | SROA, DSE, forwarding/PRE, MemCpyOpt, LICM promotion | quiz; exercises E1–E2 |
| 12 | Exercises E1–E2 | Pebble implements pebble-dse and pebble-loadfwd on MemorySSA |
./course test 19 |
| 13 | Comparison lab labs/ch19-points-to/ |
Andersen (+★ cycle elimination) vs Steensgaard over LLVM IR | ch19.lab, ch19.PointsTo.*; ch19-pointsto --table |
| 14 | Theory test | all | ./course quiz 19 (≥ 80 % to finish) |
Practice and check¶
./course drill points-to-andersen --difficulty easy # warm up; --solution shows every worklist step
./course drill points-to-steensgaard # joins, classes, what unification loses
./course drill memoryssa-build # defs, phis, defining accesses, clobbers
./course drill tbaa-query # struct-path TBAA on C accesses
./course flash 19 # daily, a few minutes
./course quiz 19 # after the lessons
./course test 19 # after the exercises and the lab
./course status # done = quiz ≥ 80 % and tests pass
References¶
The chapter's annotated bibliography (papers, textbook sections, standards, pinned source files and documentation) is in references.md. Start with: [Hin01] (the map of the design space), [And94] and [Ste96] (the two classic analyses), [HL07] (making Andersen fast), [DMM98] and [C11] (type-based rules and restrict), [LLVM-AADoc] and [LLVM-MemorySSADoc] (the interfaces your passes use). [Dragon2] and [SPA] are the textbook companions.