Skip to content

References — Chapter 12 · Passes, Pass Managers & Testing Compilers

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

  • [ACK81] Frances E. Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. In S. S. Muchnick and N. D. Jones (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, pp. 79–101, 1981.
    Why and when: Classic strength reduction of induction-variable multiplications in loops; the global ancestor of Lesson 12.3's local rewrites and the topic of Chapter 18.
    Note: Book chapter; no DOI.
    Cited in: overview, 03-writing-passes

  • [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, its optimality, and edge profiling vs tracing. Read §2–3 after Lesson 12.3 §2 (Theorem 12.3.12).
    Cited in: overview, 03-writing-passes

  • [BMC20] Marcel Böhme, Valentin J. M. Manès, and Sang Kil Cha. Boosting Fuzzer Efficiency: An Information Theoretic Perspective. ESEC/FSE 2020, pp. 678–689, 2020. doi:10.1145/3368089.3409748
    Why and when: Entropic, the power schedule libFuzzer uses by default (its start-up log says "Running with entropic power schedule"; Lesson 12.6's box filters that line out). Read §3 after Lesson 12.6.
    Cited in: 06-fuzzing-and-metamorphic-testing

  • [BPR16] Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. Coverage-based Greybox Fuzzing as Markov Chain. CCS 2016, pp. 1032–1043, 2016. doi:10.1145/2976749.2978428
    Why and when: AFLFast: power schedules that spend more mutations on inputs exercising rare paths. Read after Lesson 12.6 §6 for the theory behind choosing which corpus input to mutate.
    Cited in: 06-fuzzing-and-metamorphic-testing

  • [CSS99] Keith D. Cooper, Philip J. Schielke, and Devika Subramanian. Optimizing for Reduced Code Space using Genetic Algorithms. LCTES 1999, pp. 1–9, 1999. doi:10.1145/314403.314414
    Why and when: Genetic search over optimization sequences for code size, beating the fixed sequence. Read after Lesson 12.2 §6.
    Cited in: overview, 02-pipelines-and-extension-points

  • [GM94] Torbjörn Granlund and Peter L. Montgomery. Division by Invariant Integers using Multiplication. PLDI 1994, pp. 61–72, 1994. doi:10.1145/178243.178249
    Why and when: Division by any constant with a multiply-high and shifts, including the signed rounding correction — the general case of Lesson 12.3's power-of-two sequence. Read §4–5 after Lesson 12.3.
    Cited in: overview, 03-writing-passes

  • [Han70] Kenneth V. Hanford. Automatic Generation of Test Cases. IBM Systems Journal 9(4), pp. 242–257, 1970. doi:10.1147/sj.94.0242
    Why and when: The "syntax machine": random programs from a grammar to test PL/I compilers — grammar-based fuzzing forty years before the word. Skim it for history after Lesson 12.6 §1.
    Cited in: overview, 06-fuzzing-and-metamorphic-testing

  • [HHZ12] Christian Holler, Kim Herzig, and Andreas Zeller. Fuzzing with Code Fragments. USENIX Security 2012, pp. 445–458, 2012. link
    Why and when: LangFuzz: grammar-based fuzzing of JavaScript engines that recombines fragments of existing test programs. Read after Lesson 12.6 as the practical refinement of random derivation.
    Cited in: 06-fuzzing-and-metamorphic-testing

  • [KWTD06] Prasad A. Kulkarni, David B. Whalley, Gary S. Tyson, and Jack W. Davidson. Exhaustive Optimization Phase Order Space Exploration. CGO 2006, pp. 306–318, 2006. link · pdf
    Why and when: Enumerating all distinct function instances reachable by phase orders, made feasible by detecting identical instances. Read after Lesson 12.2 §2 (Algorithm 12.2.7).
    Cited in: overview, 02-pipelines-and-extension-points

  • [LAS14] Vu Le, Mehrdad Afshari, and Zhendong Su. Compiler Validation via Equivalence Modulo Inputs. PLDI 2014, pp. 216–226, 2014. doi:10.1145/2594291.2594334
    Why and when: EMI and the Orion tool: prune statements that did not execute on an input and compare; 147 confirmed bugs in GCC and LLVM in eleven months. Read §2–3 after Lesson 12.6 §2.
    Cited in: overview, 06-fuzzing-and-metamorphic-testing

  • [LBR20] Vsevolod Livinskii, Dmitry Babokin, and John Regehr. Random Testing for C and C++ Compilers with YARPGen. Proc. ACM Program. Lang. 4 (OOPSLA), Article 196, 2020. doi:10.1145/3428264
    Why and when: YARPGen: UB avoidance by evaluating every expression during generation, and generation policies that steer programs toward optimization-triggering patterns. Read §3 after Lesson 12.5; compare its design choices with Csmith's.
    Cited in: overview, 05-snapshot-and-differential-testing

  • [LLH+21] Nuno P. Lopes, Juneyoung Lee, Chung-Kil Hur, Zhengyang Liu, and John Regehr. Alive2: Bounded Translation Validation for LLVM. PLDI 2021, pp. 65–79, 2021. doi:10.1145/3453483.3454030
    Why and when: Core reading. Refinement for whole LLVM functions with undef, poison, memory and bounded loops, and the experience of running it over LLVM's test suite. Read §2–4 after Lesson 12.8.
    Cited in: overview, 08-translation-validation

  • [LMNR15] Nuno P. Lopes, David Menendez, Santosh Nagarakatte, and John Regehr. Provably Correct Peephole Optimizations with Alive. PLDI 2015, pp. 22–32, 2015. doi:10.1145/2737924.2737965
    Why and when: Alive's DSL, its SMT encoding of undef and poison, and the inference of nsw/nuw/exact flags — the question of Theorem 12.3.10. Read §3–4 after Lesson 12.8.
    Cited in: overview, 08-translation-validation

  • [McK98] William M. McKeeman. Differential Testing for Software. Digital Technical Journal 10(1), pp. 100–107, 1998. link
    Why and when: Core reading. The origin of differential testing for compilers: run the same program through several C compilers and treat disagreement as a bug report, with a hierarchy of generated-test "quality levels" from random bytes to well-defined programs. Read it before Lesson 12.5 §2; its discussion of undefined behavior is the problem Csmith later solved.
    Note: No DOI. The URL is HP Labs' archive of the Digital Technical Journal (vol. 10, no. 1, article 9); if it moves, the Internet Archive keeps copies of that path.
    Cited in: overview, 05-snapshot-and-differential-testing

  • [Nec00] George C. Necula. Translation Validation for an Optimizing Compiler. PLDI 2000, pp. 83–94, 2000. doi:10.1145/349299.349314
    Why and when: Translation validation for GCC's optimizer by symbolic evaluation and inferred simulation relations between source and target. Read after Lesson 12.8 §2 (Algorithm 12.8.6 follows its structure).
    Cited in: overview, 08-translation-validation

  • [PSS98] Amir Pnueli, Michael Siegel, and Eli Singerman. Translation Validation. TACAS 1998, LNCS 1384, pp. 151–166, 1998. doi:10.1007/BFb0054170
    Why and when: Core reading. The idea of validating each compiler run instead of verifying the compiler, applied to the SIGNAL-to-C translator. Read §1–3 before Lesson 12.8 §2.
    Cited in: overview, 08-translation-validation

  • [Pur72] Paul Purdom. A Sentence Generator for Testing Parsers. BIT Numerical Mathematics 12(3), pp. 366–375, 1972. doi:10.1007/BF01932308
    Why and when: Generating a small set of sentences that together use every production of a grammar; the systematic counterpart of random derivation (Lesson 12.6 §6).
    Cited in: overview, 06-fuzzing-and-metamorphic-testing

  • [RCC+12] John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang. Test-Case Reduction for C Compiler Bugs. PLDI 2012, pp. 335–346, 2012. doi:10.1145/2254064.2254104
    Why and when: C-Reduce: domain-specific transformation passes iterated to a fixpoint, compared with delta debugging, and the problem of reductions that introduce undefined behavior. Read after Lesson 12.7 §2.
    Cited in: overview, 07-reduction-and-bisection

  • [Ser16] Kostya Serebryany. Continuous Fuzzing with libFuzzer and AddressSanitizer. IEEE Cybersecurity Development (SecDev) 2016, p. 157, 2016. doi:10.1109/SecDev.2016.043
    Why and when: libFuzzer's author on in-process, coverage-guided fuzzing combined with sanitizers as a continuous service. Short; read with Lesson 12.6 §7.
    Cited in: overview, 06-fuzzing-and-metamorphic-testing

  • [YCER11] Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. Finding and Understanding Bugs in C Compilers. PLDI 2011, pp. 283–294, 2011. doi:10.1145/1993498.1993532
    Why and when: Core reading. Csmith: generating C programs free of undefined behavior (safe math, points-to and effect analysis during generation) and running them differentially; more than 325 bugs reported in GCC and LLVM. Read §2 (generation) after Lesson 12.5 §2 and §3 for the bug statistics.
    Cited in: overview, 05-snapshot-and-differential-testing

  • [ZH02] Andreas Zeller and Ralf Hildebrandt. Simplifying and Isolating Failure-Inducing Input. IEEE Transactions on Software Engineering 28(2), pp. 183–200, 2002. doi:10.1109/32.988498
    Why and when: Core reading. The ddmin algorithm, 1-minimality and its complexity analysis, and the isolation variant dd. Read §3–4 alongside Lesson 12.7 §2 and §4 before implementing Part B of the lab.
    Cited in: overview, 07-reduction-and-bisection

Textbooks and monographs

  • [FB-Grammar] Andreas Zeller, Rahul Gopinath, Marcel Böhme, Gordon Fraser, and Christian Holler. The Fuzzing Book. CISPA Helmholtz Center for Information Security (online book; Python package fuzzingbook 1.2.2), 2024. Read: Chapters "Fuzzing with Grammars" and "Efficient Grammar Fuzzing" (GrammarFuzzer), "Coverage", "Reducing Failure-Inducing Inputs". link
    Why and when: Executable chapters on grammar fuzzing (the three-phase GrammarFuzzer of Algorithm 12.6.2), greybox fuzzing and delta debugging. Run the notebooks alongside Lessons 12.6–12.7.
    Cited in: overview, 06-fuzzing-and-metamorphic-testing

  • [HD2] Henry S. Warren Jr.. Hacker's Delight, 2nd ed.. Addison-Wesley, 2012. Read: Ch. 10 (Integer Division by Constants), §10-1 (Signed Division by a Known Power of 2).
    Why and when: The bias trick of Theorem 12.3.9 and its variants for every width, then division by arbitrary constants. Read §10-1 with Lesson 12.3 §2.
    Cited in: overview, 03-writing-passes

  • [WPF] Andreas Zeller. Why Programs Fail: A Guide to Systematic Debugging, 2nd ed.. Morgan Kaufmann, 2009. Read: Ch. 5 (Simplifying Problems: ddmin), Ch. 14 (Isolating Failure Causes).
    Why and when: The textbook presentation of delta debugging with worked examples and code; easier than the paper. Read Ch. 5 before Lesson 12.7 if the proofs feel dense.
    Cited in: 07-reduction-and-bisection

Surveys and tutorials

  • [CPS+20] Junjie Chen, Jibesh Patra, Michael Pradel, Yingfei Xiong, Hongyu Zhang, Dan Hao, and Lu Zhang. A Survey of Compiler Testing. ACM Computing Surveys 53(1), Article 4, 2020. doi:10.1145/3363562
    Why and when: The map of the field: program generation, test oracles (differential, metamorphic/EMI), reduction, prioritization, and the empirical record. Read it after Lesson 12.5 to place every technique of Lessons 12.5–12.8.
    Cited in: 05-snapshot-and-differential-testing, 06-fuzzing-and-metamorphic-testing

Source code (pinned versions)

  • [Alive2] Alive2's standalone validator, opt/clang plugin and Alive DSL tool — tools/alive-tv.cpp in AliveToolkit/alive2 at 01a5ec45c8152995755f7331827407a9de19f262. Symbols: TransformVerify, tv/tv.cpp, tools/alive.cpp.
    Why and when: The commit built for Lesson 12.8's boxes (the last one compatible with LLVM 23.1.2's TargetLibraryInfo API). The README explains building against LLVM with RTTI.
    Cited in: 08-translation-validation

  • [CReduce] C-Reduce's driver and pass modules (Ubuntu 24.04 packages 2.11.0) — creduce/creduce.in in csmith-project/creduce at master. Symbols: pass_lines, pass_clex, clang_delta.
    Why and when: Algorithm 12.7.4's fixpoint loop over passes; read pass_lines.pm to see ddmin-style line deletion inside it.
    Note: The repository has no 2.11.0 release tag; the pass modules are creduce/pass_.pm and the C++-aware transformations are in clang_delta/.
    Cited in:* 07-reduction-and-bisection

  • [Csmith] Csmith's random statement generation (see also src/FactPointTo.cpp, runtime/safe_math.m4) — src/Statement.cpp in csmith-project/csmith at csmith-2.3.0. Symbols: Statement::make_random.
    Why and when: Where Algorithm 12.5.6's random choices and safety checks live; safe_math.m4 generates the wrappers.
    Cited in: 05-snapshot-and-differential-testing

  • [GCC-Expmed] GCC's expansion of signed division by a power of two — gcc/expmed.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: expand_sdiv_pow2.
    Why and when: The same bias sequence as Theorem 12.3.9, chosen per target cost.
    Cited in: 03-writing-passes

  • [GCC-Opts] Which -f options each -O level enables in GCC — gcc/opts.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: default_options_table.
    Why and when: GCC's counterpart of LLVM's pipeline builders: levels are sets of flags that gate passes.
    Cited in: 02-pipelines-and-extension-points

  • [GCC-Passes] GCC's pass manager — gcc/passes.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: execute_one_pass, execute_todo, execute_pass_list.
    Why and when: Algorithm 12.1.13: gates, property checks and TODOs around every pass.
    Cited in: 01-pass-manager-architectures

  • [GCC-PassesDef] GCC's pass tree — gcc/passes.def in gcc-mirror/gcc at releases/gcc-15. Symbols: INSERT_PASSES_AFTER, PUSH_INSERT_PASSES_WITHIN, NEXT_PASS.
    Why and when: The whole optimization pipeline in one file; count the instances of pass_ccp and pass_fre (Lesson 12.2).
    Cited in: 01-pass-manager-architectures

  • [GCC-TreePass] GCC pass metadata, properties and TODO flags — gcc/tree-pass.h in gcc-mirror/gcc at releases/gcc-15. Symbols: pass_data, opt_pass, PROP_ssa, TODO_update_ssa.
    Why and when: Definition 12.1.12 comes straight from this header.
    Cited in: 01-pass-manager-architectures

  • [LLVM-BasicAA] BasicAA's stateless invalidation — llvm/lib/Analysis/BasicAliasAnalysis.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: BasicAAResult::invalidate.
    Why and when: Ignores its own preservation and checks only its dependencies (Definition 12.1.4).
    Cited in: 01-pass-manager-architectures

  • [LLVM-CFGMST] The spanning-tree builder used by PGO instrumentation — llvm/include/llvm/Transforms/Instrumentation/CFGMST.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: CFGMST::buildEdges, CFGMST::computeMinimumSpanningTree.
    Why and when: Kruskal with union-find over weighted CFG edges: Algorithm 12.3.7's Place.
    Cited in: 03-writing-passes

  • [LLVM-CGSCC] The CGSCC pass manager and its adaptors — llvm/include/llvm/Analysis/CGSCCPassManager.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: ModuleToPostOrderCGSCCPassAdaptor, CGSCCToFunctionPassAdaptor, DevirtSCCRepeatedPass, CGSCCUpdateResult.
    Why and when: Definition 12.1.11: the post-order SCC walk, graph updates, devirt. Read after Lesson 12.1's CGSCC box.
    Cited in: 01-pass-manager-architectures

  • [LLVM-DAGCombiner] Lowering sdiv by a power of two in the code generator — llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DAGCombiner::visitSDIV, DAGCombiner::BuildSDIVPow2.
    Why and when: The biased sequence of Theorem 12.3.9 in the back end (with target hooks such as select-based forms).
    Cited in: 03-writing-passes

  • [LLVM-DeltaSrc] llvm-reduce's chunked delta loop — llvm/tools/llvm-reduce/deltas/Delta.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: runDeltaPass, increaseGranularity.
    Why and when: Algorithm 12.7.5's inner loop; the individual reductions are the Reduce*.cpp files next to it.
    Cited in: 07-reduction-and-bisection

  • [LLVM-Dominators] DominatorTree's invalidation predicate — llvm/lib/IR/Dominators.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DominatorTree::invalidate.
    Why and when: Preserved by name, by all, or by the CFGAnalyses set — the rule the pm-invalidation drill uses.
    Cited in: 01-pass-manager-architectures

  • [LLVM-FileCheckSrc] FileCheck's matcher — llvm/lib/FileCheck/FileCheck.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: FileCheck::checkInput, FileCheckString::Check, FileCheckString::CheckDag, FileCheckString::CheckNot, FileCheckString::CheckNext, Pattern::match.
    Why and when: The operational semantics of Algorithm 12.4.4, line for line; tools/course/lib/filecheck.py follows it.
    Cited in: 04-filecheck-and-lit

  • [LLVM-FuzzerLoop] libFuzzer's main loop — compiler-rt/lib/fuzzer/FuzzerLoop.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Fuzzer::Loop, Fuzzer::MutateAndTestOne, Fuzzer::RunOne.
    Why and when: Algorithm 12.6.4 in production: corpus selection, mutation, and the NEW/REDUCE logic.
    Cited in: 06-fuzzing-and-metamorphic-testing

  • [LLVM-InstCombineMulDiv] InstCombine's multiplication and division rewrites — llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InstCombinerImpl::visitMul, InstCombinerImpl::visitUDiv, InstCombinerImpl::visitSDiv.
    Why and when: The IR-level strength reductions LLVM performs, and why sdiv by 2^k stays sdiv (Lesson 12.3 §7).
    Cited in: 03-writing-passes

  • [LLVM-LegacyPM] The legacy pass manager's scheduler — llvm/lib/IR/LegacyPassManager.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PMTopLevelManager::schedulePass, FPPassManager::runOnFunction, PMDataManager::removeNotPreservedAnalysis.
    Why and when: Algorithm 12.1.6 in production; still used by the code generator.
    Cited in: 01-pass-manager-architectures

  • [LLVM-litSrc] lit's shell-test runner — llvm/utils/lit/lit/TestRunner.py in llvm/llvm-project at llvmorg-23.1.2. Symbols: executeShTest, parseIntegratedTestScript.
    Why and when: RUN-line parsing, substitutions and the internal shell behind Algorithm 12.4.7.
    Cited in: 04-filecheck-and-lit

  • [LLVM-LPM] The loop pass manager — llvm/include/llvm/Transforms/Scalar/LoopPassManager.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: FunctionToLoopPassAdaptor, LPMUpdater.
    Why and when: Loop pipelines that may add and delete loops while running (Lesson 12.1 §6).
    Cited in: 01-pass-manager-architectures

  • [LLVM-MSSA] MemorySSA's invalidation predicate — llvm/lib/Analysis/MemorySSA.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MemorySSAAnalysis::Result::invalidate.
    Why and when: Invalidated when not preserved, or when AA or the dominator tree is (Lesson 12.1's cascade box).
    Cited in: 01-pass-manager-architectures

  • [LLVM-NewPMDriver] opt's pipeline driver — llvm/tools/opt/NewPMDriver.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: registerEPCallbacks, runPassPipeline.
    Why and when: Why -passes-ep-* cannot name plugin passes: the flags are parsed before plugins register (Lesson 12.2 §7).
    Cited in: 02-pipelines-and-extension-points

  • [LLVM-PassPlugin] The pass-plugin ABI (LLVM 22+ header location) — llvm/include/llvm/Plugins/PassPlugin.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: PassPluginLibraryInfo, LLVM_PLUGIN_API_VERSION, llvmGetPassPluginInfo.
    Why and when: What PebblePasses.so exports; the course's pebble/lib/Passes/Plugin.cpp implements it.
    Cited in: overview, 02-pipelines-and-extension-points

  • [LLVM-PassRegistry] The table of built-in pass names — llvm/lib/Passes/PassRegistry.def in llvm/llvm-project at llvmorg-23.1.2. Symbols: FUNCTION_PASS, FUNCTION_ANALYSIS.
    Why and when: Every name opt accepts, including the print<...> printers of Lesson 12.3.
    Cited in: 03-writing-passes

  • [LLVM-PB] PassBuilder's parsing and extension-point callbacks — llvm/include/llvm/Passes/PassBuilder.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: PassBuilder::registerPipelineParsingCallback, PassBuilder::registerPeepholeEPCallback, PassBuilder::registerOptimizerLastEPCallback.
    Why and when: Every extension point a plugin can use (Definition 12.2.2).
    Cited in: overview, 02-pipelines-and-extension-points

  • [LLVM-PBP] How -O1/-O2/-O3 pipelines are built — llvm/lib/Passes/PassBuilderPipelines.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PassBuilder::buildPerModuleDefaultPipeline, PassBuilder::buildModuleSimplificationPipeline, PassBuilder::buildFunctionSimplificationPipeline, PassBuilder::buildO1FunctionSimplificationPipeline, PassBuilder::invokePeepholeEPCallbacks.
    Why and when: Algorithm 12.2.5 in code: read buildPerModuleDefaultPipeline, then follow the simplification pipeline.
    Cited in: overview, 01-pass-manager-architectures, 02-pipelines-and-extension-points

  • [LLVM-PGOInstr] IR-level PGO instrumentation (pgo-instr-gen) — llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: FuncPGOInstrumentation, SplitCriticalEdge.
    Why and when: Spanning-tree counter placement in production (Theorem 12.3.12), with critical-edge splitting.
    Cited in: 03-writing-passes

  • [LLVM-PI] Pass instrumentation callbacks — llvm/include/llvm/IR/PassInstrumentation.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: PassInstrumentationCallbacks.
    Why and when: shouldRunOptionalPass, beforeSkippedPass, beforeNonSkippedPass, afterPass: the hooks of Algorithm 12.1.8.
    Cited in: 01-pass-manager-architectures

  • [LLVM-PMH] The new pass manager's core templates — llvm/include/llvm/IR/PassManager.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: AnalysisManager, InnerAnalysisManagerProxy, OuterAnalysisManagerProxy, ModuleToFunctionPassAdaptor, RequiredPassInfoMixin, OptionalPassInfoMixin.
    Why and when: The data structures of Algorithms 12.1.7–12.1.10. Read after Lesson 12.1 §2; PreservedAnalyses itself is in llvm/include/llvm/IR/Analysis.h.
    Cited in: 01-pass-manager-architectures

  • [LLVM-SCEV] ScalarEvolution's invalidation predicate with dependencies — llvm/lib/Analysis/ScalarEvolution.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ScalarEvolution::invalidate.
    Why and when: The textbook example of an analysis that must consult its dependencies (AC, DT, LI) when invalidated.
    Cited in: 01-pass-manager-architectures

  • [LLVM-SI] The standard instrumentations (optnone, opt-bisect, print-changed, ...) — llvm/lib/Passes/StandardInstrumentations.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: OptNoneInstrumentation::shouldRun, OptPassGateInstrumentation::shouldRun, IRChangedPrinter.
    Why and when: How optnone and -opt-bisect-limit skip optional passes and how -print-changed diffs IR. Read with Lessons 12.1 and 12.7.
    Cited in: 01-pass-manager-architectures, 07-reduction-and-bisection

  • [LLVM-StressSrc] llvm-stress's random IR generator — llvm/tools/llvm-stress/llvm-stress.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Modifier, FillFunction, IntroduceControlFlow.
    Why and when: Algorithm 12.5.8 in about 800 lines; a good model for a random Pebble generator in Chapter 24.
    Cited in: 05-snapshot-and-differential-testing

  • [LLVM-UTC] The IR check generator — llvm/utils/update_test_checks.py in llvm/llvm-project at llvmorg-23.1.2. Symbols: main, UpdateTestChecks.common.generalize_check_lines, UpdateTestChecks.common.FunctionTestBuilder.
    Why and when: Algorithm 12.4.8; the naming and generalization logic is in llvm/utils/UpdateTestChecks/common.py.
    Cited in: overview, 04-filecheck-and-lit

  • [MLIR-Pass] MLIR's nested pass adaptor — mlir/lib/Pass/Pass.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: OpToOpPassAdaptor::runOnOperation, OpToOpPassAdaptor::runPipeline.
    Why and when: Algorithm 12.1.15: how nested pipelines are scheduled, in parallel when threading is enabled.
    Cited in: 01-pass-manager-architectures

  • [YARPGen] YARPGen's expression evaluation and UB-removing rebuild (policies in src/gen_policy.cpp) — src/expr.cpp in intel/yarpgen at e2a051221b835869d3efad3f4a2554050f65845c. Symbols: evaluate, rebuild.
    Why and when: Algorithm 12.5.7: each expression node's evaluate() detects UB and rebuild() rewrites it away.
    Cited in: 05-snapshot-and-differential-testing

Official documentation and specifications

  • [GCC-Int] GNU Compiler Collection Internals: Passes and Files of the Compiler. GCC 15. link
    Why and when: Sections "Pass manager" and "Inter-procedural optimization passes": what passes.def, properties and the IPA stages are for. Read with Lesson 12.1's GCC subsections.
    Cited in: overview, 01-pass-manager-architectures

  • [GCC-Plugins] GNU Compiler Collection Internals: Plugins. GCC 15. link
    Why and when: PLUGIN_PASS_MANAGER_SETUP and struct register_pass_info: inserting a pass relative to a named reference pass — GCC's extension points (Lesson 12.2 §1).
    Cited in: 02-pipelines-and-extension-points

  • [GitBisect] git-bisect — Use binary search to find the commit that introduced a bug. Git 2.43. link
    Why and when: bisect start/good/bad, bisect run and its exit-code convention (125 = skip). Read with Lesson 12.7's bisection section.
    Cited in: overview, 07-reduction-and-bisection

  • [Insta] insta: snapshot testing for Rust. link
    Why and when: Snapshot testing with review (cargo insta review), inline snapshots and redactions. Read for the variants in Lesson 12.5 §6.
    Cited in: overview, 05-snapshot-and-differential-testing

  • [LLVM-BugpointRedesign] Bugpoint Redesign. LLVM 23.1.2. link
    Why and when: Why bugpoint was replaced: confusing, slow, low-quality reductions; the plan that became llvm-reduce. Read with Lesson 12.7 §1.
    Cited in: overview, 07-reduction-and-bisection

  • [LLVM-FileCheck] FileCheck — Flexible pattern matching file verifier. LLVM 23.1.2. link
    Why and when: Core reading. The reference for every directive, variables and numeric expressions. Read alongside Lesson 12.4 §2; Algorithm 12.4.4 makes its prose precise.
    Cited in: overview, 04-filecheck-and-lit

  • [LLVM-LibFuzzer] libFuzzer — a library for coverage-guided fuzz testing. LLVM 23.1.2. link
    Why and when: The fuzz-target contract, flags (-seed, -runs, -minimize_crash, -dict), the output format of Lesson 12.6's log, and advice on harnesses. Read before Lesson 12.6 §7.
    Cited in: overview, 06-fuzzing-and-metamorphic-testing

  • [LLVM-lit] lit — LLVM Integrated Tester. LLVM 23.1.2. link
    Why and when: Test discovery, configuration files, substitutions, features and result codes (Definition 12.4.6).
    Cited in: overview, 04-filecheck-and-lit

  • [LLVM-NPM] Using the New Pass Manager. LLVM 23.1.2. link
    Why and when: Core reading. Analysis managers, proxies, adaptors, PreservedAnalyses and invalidation, from the user's side. Read after Lesson 12.1 §2; it is the prose version of Algorithms 12.1.7–12.1.10.
    Cited in: overview, 01-pass-manager-architectures

  • [LLVM-OptBisect] Using -opt-bisect-limit to debug optimization errors. LLVM 23.1.2. link
    Why and when: Which passes are counted, how to bisect, and how to combine it with -print-after. Read with Lesson 12.7 §2.
    Cited in: overview, 07-reduction-and-bisection

  • [LLVM-Reduce] llvm-reduce — LLVM automatic testcase reducer. LLVM 23.1.2. link
    Why and when: Interestingness tests, delta passes and options. Read before running Lesson 12.7's box.
    Cited in: overview, 07-reduction-and-bisection

  • [LLVM-RN23] LLVM 23 Release Notes. LLVM 23.1.2. link
    Why and when: Records the removal of bugpoint in favor of llvm-reduce and reduce_pipeline.py (Lesson 12.7 §1).
    Cited in: 07-reduction-and-bisection

  • [LLVM-Stress] llvm-stress — generate random .ll files. LLVM 23.1.2. link
    Why and when: The two options (-seed, -size) and the intended use: crash testing of passes and code generators.
    Cited in: overview, 05-snapshot-and-differential-testing

  • [LLVM-TestingGuide] LLVM Testing Infrastructure Guide. LLVM 23.1.2. link
    Why and when: Core reading. How LLVM's regression tests are organized and written with lit and FileCheck, and when to use update_test_checks.py. Read before Lesson 12.4.
    Cited in: overview, 04-filecheck-and-lit

  • [LLVM-WLP] Writing an LLVM Pass (legacy PM version). LLVM 23.1.2. link
    Why and when: The legacy pass classes (ModulePass, CallGraphSCCPass, FunctionPass, LoopPass) and getAnalysisUsage; read its sections on pass classes and analysis usage for Lesson 12.1's comparison, not to write passes.
    Cited in: overview, 01-pass-manager-architectures

  • [LLVM-WNPM] Writing an LLVM Pass (new pass manager). LLVM 23.1.2. link
    Why and when: Core reading. The mechanics of a pass: run(), PreservedAnalyses, required passes, and registering a plugin. Read before exercise E1.
    Cited in: overview, 01-pass-manager-architectures, 02-pipelines-and-extension-points, 03-writing-passes

  • [MLIR-PM] MLIR Pass Infrastructure. LLVM 23.1.2. link
    Why and when: Core reading. Operation passes, OpPassManager nesting, analysis management, dynamic pipelines, instrumentation and crash reproducers. Read after Lesson 12.1 §2 (Definition 12.1.14).
    Cited in: overview, 01-pass-manager-architectures

  • [Turnt] Turnt: a simple expect-style testing tool. Turnt 1.12.0. link
    Why and when: Cornell's snapshot tester (turnt.toml, --save, --diff), used by the Bril course infrastructure; the tool of Lesson 12.5's first box.
    Cited in: overview, 05-snapshot-and-differential-testing