Flashcards — Chapter 12¶
98 cards. Review them with spaced repetition in the terminal (./course flash 12) or export them to Anki (./course flash export 12). Here, click a card to reveal its back.
legacy-pm¶
How does LLVM's legacy pass manager learn what a pass preserves?
From getAnalysisUsage, declared before the pass runs (addRequired, addPreserved, setPreservesCFG, setPreservesAll); the same declaration holds for every run (Definition 12.1.5).
Where is the legacy pass manager still used in LLVM 23?
In the code generator (llc's pipeline; -debug-pass=Structure prints its schedule). opt 23.1.2 rejects -enable-new-pm=0.
Main cost of static AnalysisUsage declarations?
A pass that sometimes changes the CFG must declare that it never preserves it, so CFG analyses are recomputed after it on every function, changed or not.
Which function schedules passes in the legacy PM?
PMTopLevelManager::schedulePass in llvm/lib/IR/LegacyPassManager.cpp (Algorithm 12.1.6); removeNotPreservedAnalysis frees analyses.
new-pm¶
New pass manager: when is an analysis computed?
Lazily, when a pass calls getResult; the result is cached per IR unit until a pass's PreservedAnalyses invalidates it (Algorithm 12.1.7).
What must a new-PM pass return?
A PreservedAnalyses describing what this run preserved: all() if nothing changed; e.g. preserveSet<CFGAnalyses>() if only instructions changed.
Invalidation soundness conditions (Theorem 12.1.17)?
Every analysis's invalidate() is sound (not invalidated ⇒ preserved or stateless, and all dependencies survive) and every pass reports truthfully ⇒ the cache stays coherent.
Does LoopInfo fall when the dominator tree is invalidated?
No: LoopInfo::invalidate checks only its own preservation and the CFG set (LLVM 23), although computing LI requests DT. SE, BasicAA, AA and MemorySSA do fall.
What is a proxy in the new PM?
An analysis giving access to another manager: InnerAnalysisManagerProxy (module → function AM), OuterAnalysisManagerProxy (read-only cached module results from a function pass).
Required vs optional passes (LLVM 23)?
RequiredPassInfoMixin passes always run; OptionalPassInfoMixin passes may be skipped by optnone and -opt-bisect-limit via shouldRunOptionalPass callbacks.
CGSCC adaptor visiting order?
SCCs of the call graph in post-order: callees before callers, so functions are simplified before being inlined (Definition 12.1.11).
gcc-pm¶
What does a GCC pass declare in pass_data?
Type, name, properties_required/provided/destroyed (PROP_cfg, PROP_ssa, ...), todo_flags_start/finish (TODO_update_ssa, TODO_cleanup_cfg, ...).
GCC property update after a pass?
Φ' = (Φ \ destroyed) ∪ provided; required properties are checked before execute() when flag_checking (Algorithm 12.1.13).
Where is GCC's pass order written?
gcc/passes.def: INSERT_PASSES_AFTER, PUSH_INSERT_PASSES_WITHIN, NEXT_PASS(pass_ccp, true); gate() decides per function; -fdump-passes shows it.
mlir-pm¶
What anchors an MLIR pass pipeline?
An operation type (func.func, builtin.module) or op-agnostic nesting; anchored operations must be IsolatedFromAbove.
Why can MLIR run passes on sibling functions in parallel?
Isolated operations share no use-lists and passes modify only their anchor, so jobs touch disjoint IR (Proposition 12.1.21).
What is a dynamic pipeline in MLIR?
A pipeline a pass builds and runs on an operation it owns with Pass::runPipeline, still instrumented and analysis-managed.
plugins¶
What does an LLVM pass plugin export?
llvmGetPassPluginInfo returning PassPluginLibraryInfo {APIVersion = LLVM_PLUGIN_API_VERSION (2), name, version, RegisterPassBuilderCallbacks}.
Parsing callback vs extension-point callback?
A parsing callback makes a name usable in -passes=; an EP callback (registerPeepholeEPCallback, ...) inserts passes into the default O-pipelines.
Why can't opt's -passes-ep-peephole name a plugin pass?
opt parses the -passes-ep-* texts in registerEPCallbacks before plugins register their parsing callbacks.
pipelines¶
How many top-level elements do LLVM 23's default<O1>, <O2>, <O3> have?
100, 119, 122 comma-separated entries (-print-pipeline-passes).
What does -Os mean in LLVM 23?
The O2 pipeline with the optsize attribute on functions; default<Os> is rejected by opt.
Structure of buildPerModuleDefaultPipeline?
Prologue, PipelineStart EP, module simplification (inliner CGSCC pipeline with function simplification), module optimization (vectorizers, unrolling), epilogue.
phase-ordering¶
Phase-ordering problem?
Find the pass sequence w ∈ Σ^≤L minimizing a cost m(w(P)); passes do not commute (early-cse before mem2reg finds nothing).
Why do production pipelines repeat InstCombine and SimplifyCFG?
Cheap canonicalizing passes between expensive ones make each expensive pass see canonical input, whatever ran before.
Worst-case cost of exhaustive phase-order search?
Θ(|Σ|^L) pass runs when every pass yields a new program; deduplicating identical programs is what makes it feasible in practice (Kulkarni et al.).
analysis-printers¶
Why give an analysis a printer pass?
The documented print format becomes the analysis's test contract, checkable with FileCheck (print<pebble-stats>, print<domtree>).
Critical edge (Definition 12.3.2)?
An edge (b, i) where b has ≥ 2 successor slots and the target has ≥ 2 predecessor edges (isCriticalEdge with AllowIdenticalEdges=false).
Correct invalidation for an instruction-count analysis?
The default: invalidated unless it (or all) is preserved; preserving the CFG set is not enough.
strength-reduction¶
sdiv x, 2^k by shifts, correctly?
ashr(x + b, k) with b = 2^k − 1 if x < 0 else 0; b = lshr(ashr(x, N−1), N−k) (Theorem 12.3.9).
Why is sdiv x, 4 → ashr x, 2 wrong?
ashr rounds toward −∞, sdiv toward zero: they differ for every negative non-multiple of 4 (−7 / 4 = −1, ashr gives −2).
When may mul nsw x, 2^k become shl nsw x, k?
For k ≤ N−2. At k = N−1 the constant is INT_MIN; x = 1 is defined for mul nsw but poison for shl nsw (Theorem 12.3.10).
sdiv i8 x, -128 — power of two?
Only as an unsigned bit pattern (0x80); as a signed divisor it is −128, so no shift rewrite for 2^7 applies.
instrumentation¶
How many counters does spanning-tree placement need?
e − n + 1 on the extended CFG (virtual exit→entry edge): the complement of a spanning tree (Theorem 12.3.12).
How are uninstrumented edge counts recovered?
Flow conservation at a block with one unknown incident edge, repeatedly (the unknown edges form a forest).
Where does pebble-bbcount insert its increment, and why?
At the block's first insertion point, after phis and landing pads, which must stay at the top of the block.
Why can an edge counter need a new block?
On a critical edge neither end is exclusive to the edge; LLVM's PGO instrumentation splits it (SplitCriticalEdge).
lit¶
lit verdicts?
PASS, FAIL, XFAIL (expected failure that failed), XPASS (expected failure that passed: a suite failure), UNSUPPORTED (REQUIRES false / UNSUPPORTED true).
What are %s, %t, %S in lit?
The test file, a per-test temporary path, the test's directory; plus configured substitutions like %opt and %plugin in this course.
Does lit's shell use pipefail?
Yes: a RUN line fails if any command of the pipeline fails.
filecheck¶
How does CHECK-NEXT match?
Like CHECK (leftmost match after the previous match), then it fails unless exactly one newline separates it from the previous match.
Is FileCheck complete for its constraints?
Only for literal CHECK chains (Theorem 12.4.10); greediness fails with NEXT, NOT, DAG and regexes (Proposition 12.4.11).
Where is a CHECK-NOT checked?
Between the end of what precedes it and the start of what follows it (the next positive match or the next DAG group).
Effect of a CHECK-NOT between two CHECK-DAGs?
It splits them into two groups: the second must match after the first, even if the NOT's string never occurs (Theorem 12.4.12).
What does CHECK-LABEL do?
Labels are found first and cut the input into blocks; failures inside a block do not stop other blocks; a missing label aborts.
update-test-checks¶
What does update_test_checks.py generate?
Per function: CHECK-LABEL, CHECK-SAME for the signature, CHECK-NEXT per line, values captured as [[X:%.*]] and reused as [[X]].
What changes do generated checks tolerate?
Only a consistent renaming of values (Theorem 12.4.14): they behave like snapshots.
What does update_test_checks.py need to run?
opt on PATH (or --opt-binary) and the test's RUN line; it rewrites the test file in place and records UTC_ARGS.
snapshot¶
Snapshot oracle?
Pass iff the normalized output equals the reviewed golden file; accept mode rewrites the golden after review.
Weakness of snapshot tests?
Every benign output change is a false alarm; a bug present when the snapshot was accepted is never seen.
Turnt and insta?
Turnt: expect-style tool (turnt.toml, --save, --diff), Cornell; insta: Rust snapshots with cargo insta review, inline snapshots, redactions.
differential¶
Differential testing (McKeeman 1998)?
Run one program through several compilers/levels/versions; a disagreement exposes a bug in at least one — if the program is well defined.
Why must differential-testing programs be UB-free?
With undefined behavior every result conforms, so disagreement proves nothing (Theorem 12.5.10).
Programs needed to detect a bug of probability q with confidence 1−δ?
N ≥ ln(1/δ)/q (Theorem 12.5.11); expected 1/q until the first detection.
What can differential testing never see?
Bugs shared by all compared configurations and bugs with no observable effect, such as unjustified poison flags (Proposition 12.5.12).
csmith¶
How does Csmith avoid signed overflow?
Every signed arithmetic operation goes through safe_* wrappers (csmith.h) that return a defined result.
Csmith's oracle?
The program prints a checksum (CRC) of all globals; compilers are compared on it.
Csmith's reported impact?
More than 325 previously unknown bugs in C compilers, GCC and LLVM included (Yang et al., PLDI 2011).
yarpgen¶
How does YARPGen avoid UB?
It evaluates every expression on the known inputs while generating and rewrites nodes whose evaluation would be undefined.
What are YARPGen's generation policies?
Probability tables per code region biasing programs toward patterns optimizations look for (loops, arrays, reused subexpressions).
What does a YARPGen test consist of?
driver.c (inputs, main, result hash) and func.c (the test function), plus init.h.
llvm-stress¶
llvm-stress's oracle?
No crash and valid output from the tools; its functions read through pointer arguments and are not executed.
How does llvm-stress build a function?
FillFunction applies random Modifiers (load, store, binop, cast, select, cmp, vector ops) to a value pool; IntroduceControlFlow splits at i1 values; the module is verified.
llvm-stress options?
-seed and -size (number of generation steps).
grammar-fuzzing¶
When do random derivations terminate with probability 1?
When the mean offspring m ≤ 1 (Galton–Watson, Theorem 12.6.7); otherwise with probability q < 1, the least fixed point of f.
GrammarFuzzer's three phases?
Max-cost expansions up to min_nonterminals, random ones up to max_nonterminals, then min-cost expansions to close the tree.
Origins of grammar-based test generation?
Hanford's syntax machine (IBM, 1970) for PL/I compilers; Purdom's production-covering sentence generator (1972).
coverage-fuzzing¶
libFuzzer's corpus rule?
Keep a mutated input iff it has a feature (edge, hit-count bucket, comparison) not yet in the corpus (NEW); replace by shorter equal-feature inputs (REDUCE).
Why does coverage feedback beat blind fuzzing?
Checks are passed one at a time: ≤ 256·k² executions for k sequential byte checks instead of 256^k (Theorem 12.6.8).
How do you build a libFuzzer target?
Define LLVMFuzzerTestOneInput(data, size) and compile with clang -fsanitize=fuzzer,address; keep results observable or the optimizer deletes the code.
emi¶
EMI variant?
A program in which statements not executed on input I are replaced (e.g. by ;); it must behave like the original on I (Theorem 12.6.9).
Why is EMI a useful oracle?
It needs neither a second compiler nor an expected output; any output difference between P and a variant on I is a miscompilation.
Orion's result?
147 confirmed, unique bugs in GCC and LLVM in eleven months (Le, Afshari, Su, PLDI 2014).
ddmin¶
1-minimal configuration?
A failing c such that removing any single element makes the test not fail (Definition 12.7.2).
ddmin's three moves?
Reduce to a failing subset (n = 2), reduce to a failing complement (n = max(n−1, 2)), or increase granularity (n = min(2n, |c|)); stop at n = |c|.
ddmin test bounds?
≤ 2⌈log₂ N⌉ for one cause (Prop. 12.7.10); ≤ 3N² + 3N distinct tests in the worst case (Theorem 12.7.9).
Why is ddmin over lines weak on C?
Paired lines (a function header and its }) can only go together; 1-minimal is not minimal.
creduce¶
How does C-Reduce reduce?
Transformation passes (lines, tokens, balanced groups, clang_delta rewrites, renaming) applied at every position, repeated until a round makes no progress.
C-Reduce's danger for miscompile reports?
Reductions may introduce undefined behavior (e.g. uninitialized reads); interestingness tests must reject UB.
C-Reduce vs line ddmin on the lab's crash?
4 lines (≈100 s) vs 10 lines (195 tests, ≈12 s).
llvm-reduce¶
How does llvm-reduce reduce?
Delta passes per IR entity kind (functions, blocks, instructions, operands, attributes, metadata) with chunk halving; candidates are repaired to verify.
What replaced bugpoint?
llvm-reduce (and reduce_pipeline.py); LLVM 23 removed bugpoint.
When does llvm-reduce stop?
When a round of delta passes does not lower the complexity score, or after --max-pass-iterations rounds (default 5).
bisection¶
What does -opt-bisect-limit=k do?
Runs only the first k optional pass executions (numbered BISECT: running pass (i)); required passes always run.
Tests needed to bisect n states?
⌈log₂ n⌉ for a monotone predicate, which is optimal (Theorem 12.7.12).
git bisect run exit codes?
0 good; 125 skip (cannot test); any other code from 1 to 127 bad; 128 or above aborts the bisection.
tv-pnueli¶
Translation validation (Pnueli et al. 1998)?
Check each compiler run: prove that this output refines this input, instead of verifying the compiler.
Refinement t ⊒ s for straight-line IR?
For every input: s has UB, or t has no UB and (s is poison or t equals s).
What does a sound validator guarantee?
valid ⇒ the output refines the input; valid runs compose along a pipeline; nothing about unvalidated programs.
tv-necula¶
Necula's validator?
Symbolic evaluation of source and optimized target with an inferred simulation relation at cut points; VCs proved by a decision procedure (GCC, PLDI 2000).
Simulation relation?
Pairs of related program points with formulas over source and target variables, preserved along every pair of corresponding paths.
What does Necula's validator say when a VC is not proved?
unknown — incompleteness, not a counterexample.
alive¶
Alive (PLDI 2015)?
A DSL for peephole rules; SMT queries per feasible type assignment prove refinement with undef/poison or give a counterexample.
Alive's flag inference?
Try each nsw/nuw/exact position of the target and keep the flags for which the rule stays correct.
Alive's verdict on mul nsw i8 x, 128 → shl nsw i8 x, 7?
Target more poisonous than source; counterexample x = 1 (source −128, target poison).
alive2¶
Alive2 (PLDI 2021)?
Bounded translation validation of LLVM IR functions with undef, poison, memory; alive-tv, opt/clang plugins.
How does Alive2 handle loops?
Unrolls them up to a bound; executions needing more iterations are not checked, and a source that never returns within the bound gets no verdict.
Alive2 result kinds?
correct, incorrect (with a counterexample), failed to prove (timeouts, unsupported features), Alive2 errors.