Chapter 13 · Local Optimization & Transformation Correctness¶

Part 3 · Analysis Foundations & SSA · about 3 weeks · Previous: Ch 12 · Next: Ch 14

The problem¶

You are given a function in SSA form, as LLVM IR, and a small window of it: one instruction with its operands, one basic block, or a straight-line stretch of blocks. Produce a function that is cheaper (fewer, cheaper or shorter-latency instructions) and refines the original: for every input, each behavior of the new function is one the original allows (Definition 13.8.2). Refinement lets an optimizer remove undefined behavior and resolve nondeterminism, but never add either, and every poison-generating flag (nsw, nuw, exact, disjoint, samesign, nneg) and fast-math flag it keeps must be justified. This chapter surveys the techniques that work within such windows: constant folding, peephole engines (hand-written, embedded matchers, rule DSLs), superoptimizers that find rewrites, canonical forms and the rewriting theory that says when a rule set stops and gives one answer, local value numbering with memory, DAGs and dead-code elimination, reassociation, strength reduction of multiplication and division by constants, and, running through all of it, how to prove or check that a transformation is correct (SMT with Alive2, bounded exhaustive checking, translation validation vs verified compilers). In LLVM these are ConstantFolding, InstSimplify/InstCombine with PatternMatch, EarlyCSE, DCE, Reassociate, SelectionDAG's BuildUDIV/BuildSDIV and the GlobalISel combiner; in pebblec your five passes (pebble-constfold, pebble-peephole, pebble-lvn, pebble-dce, pebble-reassociate) run on the IR the front end emits, and the global versions of the same ideas return in Ch 17.

What you will be able to do¶

Classify an optimization by scope (local, superlocal, regional, global) and fold constants exactly, including poison, UB and IEEE 754 corner cases; implement both folding and a flag-aware peephole engine for LLVM IR.
State the refinement relation with UB, poison, undef and freeze, and decide for a rewrite which flags it may keep; find a counterexample by hand, with Alive2 and with your own bounded exhaustive checker.
Trace local value numbering with commutativity, identities, folding and memory versions, and the DAG construction of a block; prove why flag intersection is required.
Compute Briggs–Cooper ranks and the reassociated order of an expression tree, and a minimal-height tree with arrival times; prove which flags survive.
Derive and verify the magic multiplier for unsigned and signed division by a constant (Granlund–Montgomery, the exact criterion), and a shift-add chain for multiplication.
Argue termination and confluence of a rule set (measures, Newman's lemma, critical pairs), and compare hand-written combiners with rule DSLs and superoptimizers by power, speed and verifiability.
Find where LLVM 23, GCC and Cranelift implement each technique (InstCombineAddSub.cpp, PatternMatch.h, match.pd, EarlyCSE.cpp, Reassociate.cpp, DivisionByConstantInfo.cpp, ISLE opts/*.isle) and reproduce their behavior with opt, llc, gcc and alive-tv.

Prerequisites: Ch 9, especially Lesson 9.7 (poison, undef, freeze, UB, the flags and refinement, which this chapter builds on); Ch 10 (IRBuilder, PatternMatch, RAUW); Ch 12 (new-pass-manager passes with parameters, lit + FileCheck, Alive2 as a test oracle); from Ch 8, basic blocks and the value-numbering drill. Lesson 13.6 uses reverse postorder and loops (Ch 15); it defines what it needs.

Notation¶

Shared notation follows the house notation: §1 (sets, functions, logic), §3 (graphs and CFGs), §7 (dataflow, SSA, IR), §8 (complexity) and §9 (numbered statements). Numbered statements are 13.k.m (lesson \(k\)). Integers are \(N\)-bit two's-complement bit patterns; "signed" and "unsigned" are interpretations, never types. In this chapter:

Symbol	Meaning
\(N\), \(\texttt{i}N\)	bit width; the LLVM integer type of that width
\(\mathbb{V}_N\)	values of \(\texttt{i}N\): \(\{0, \ldots, 2^N - 1\} \cup \{\mathsf{poison}\}\) (Definition 13.8.1)
\(\mathsf{poison}\), \(\mathsf{undef}\), \(\mathsf{UB}\)	the poison value, the (deprecated) undef value, immediate undefined behavior (Lesson 9.7; Definitions 13.8.1–13.8.5)
\([\![\mathsf{op}_F]\!]\)	the semantics of operation \(\mathsf{op}\) with flag set \(F\) (Definition 13.1.5)
\(\mathcal{B}(f, \vec{x})\)	the set of outcomes (values, poison, UB) of \(f\) on input \(\vec{x}\) over all nondeterministic choices (Definition 13.8.1)
\(s \sqsupseteq t\)	\(t\) refines \(s\) (Definition 13.8.2); for values, the definedness order \(\mathsf{poison} \sqsupseteq v\) (Definition 13.8.5)
\(\rho = L \Rightarrow R\), \(\sigma\)	a rewrite rule with pattern \(L\) and result \(R\); a matching substitution (Definitions 13.2.1–13.2.2)
\(C\), \(C_1\), \(C_2\), \(\vec{C}\)	constants in a rule; symbolic constants of a generalized rule (Definition 13.3.7)
R1–R17	the course rule set of exercise E2 (exercises.md)
\(\mathrm{WP}\)	weakest precondition of a generalized rule (Definition 13.3.7)
\(c(\cdot)\), \(\beta\)	STOKE's cost function and inverse temperature (Algorithm 13.3.5)
\(\to\), \(\to^{}\), \(\leftrightarrow^{}\), \(\downarrow\)	a rewrite relation, its reflexive-transitive and equivalence closures, joinability (Definition 13.4.1)
\(\mu = (I, S, A, M)\)	the lexicographic termination measure of R1–R17 (Theorem 13.4.9)
\(\mathrm{VN}(v)\), \(\kappa(i)\)	value number of \(v\); the key of instruction \(i\) (Definitions 13.5.1–13.5.2)
\(\mathit{mem}\)	the memory version of local value numbering (Definition 13.5.4)
\(R(B)\), \(\mathrm{rank}(v)\)	1-based reverse-postorder number of block \(B\); Briggs–Cooper rank of a value (Definition 13.6.2)
\(a_j\), \(T\)	arrival time of leaf \(j\); completion time of a tree (Definition 13.6.4)
\(\mathrm{NAF}(c)\)	non-adjacent form of a constant \(c\) (Definition 13.7.1)
\(m\), \(\ell\), \(e\)	magic multiplier \(\lceil 2^{N+\ell}/d \rceil\), post-shift, error \(md - 2^{N+\ell}\) (Definition 13.7.3)
\(n_c\)	the largest \(x < 2^N\) with \(x \bmod d = d - 1\) (Definition 13.7.5)
`nnan` `ninf` `nsz` `arcp` `contract` `afn` `reassoc`	LLVM's fast-math flags (Definition 13.8.8)

Technique map¶

Family	Techniques (origin)	Lesson
Scopes and folding	Optimization scopes: local, superlocal (extended basic blocks), regional (dominator-based) and global (Cocke & Schwartz 1970 [CS70]; Briggs, Cooper & Simpson 1997 [BCS97]; Cooper & Torczon [EaC3]); constant folding with exact semantics and IEEE 754 arithmetic ([IEEE754]; LLVM `ConstantFolding` [LLVM-ConstantFolding], GCC `fold-const` [GCC-fold-const])	13.1
Peephole engines	Peephole optimization (McKeeman 1965 [McK65]; Davidson & Fraser 1980 [DF80]); hand-written combiners (LLVM InstCombine and the InstSimplify/InstCombine contract [LLVM-InstCombine, LLVM-ICGuide]); embedded pattern matchers (LLVM `PatternMatch` [LLVM-PatternMatch]); external pattern DSLs (GCC `match.pd` + `genmatch` [GCC-matchpd, GCC-MaS]; Cranelift ISLE [Cranelift-ISLE, Cranelift-ISLE-ref]; the GlobalISel combiner [LLVM-GISelCombine])	13.2
Superoptimization	Enumerative superoptimization (Massalin 1987 [Mas87]; GNU superoptimizer, Granlund & Kenner 1992 [GK92]; Bansal & Aiken 2006 [BA06]); stochastic superoptimization (STOKE, Schkufza, Sharma & Aiken 2013 [SSA13]); solver-based synthesis (CEGIS, Gulwani et al. 2011 [GJTV11]; Souper, Sasnauskas et al. 2017 [SCC+17]); learned and generalized rewrite rules (Alive-Infer, Menendez & Nagarakatte 2017 [MN17]; Hydra, Mukherjee & Regehr 2024 [MR24])	13.3
Canonicalization and rewriting	Canonical forms (operand order by rank, constants on the right, strict predicates; LLVM `getComplexity` [LLVM-InstCombine]); termination and confluence (Newman 1942 [New42]; Knuth & Bendix 1970 [KB70]; Baader & Nipkow 1998 [BN98])	13.4
Value numbering, DAGs, DCE	Local value numbering (Cocke & Schwartz 1970 [CS70]) with commutativity, identities and folding; memory in value numbering (memory versions; EarlyCSE generations [LLVM-EarlyCSE]); DAG-based local optimization (Aho, Johnson & Ullman 1977 [AJU77]; Aho, Lam, Sethi & Ullman [Dragon2 §8.5]; SelectionDAG [LLVM-SelectionDAG]); worklist dead-code elimination [LLVM-DCE]	13.5
Reassociation	Rank-based reassociation (Briggs & Cooper 1994 [BC94]; LLVM Reassociate [LLVM-Reassociate], GCC reassoc [GCC-reassoc]); tree-height reduction (Baer & Bovet 1968 [BB68]; Brent 1974 [Bre74]; Huffman-style merging, Golumbic 1976 [Gol76]; LLVM MachineCombiner [LLVM-MachineCombiner])	13.6
Strength reduction	Multiplication by constants (Reitwiesner 1960 [Rei60]; Bernstein 1986 [Ber86]); division by invariant integers (Granlund & Montgomery 1994 [GM94]; Warren [War13, ch. 10]; LLVM [LLVM-DivConst])	13.7
Transformation correctness	Refinement; undefined behavior, poison, `undef` and `freeze` (Lee et al. 2017 [LHK+17]; [LLVM-LangRef]); poison-generating flags (`nsw nuw exact disjoint samesign nneg`); floating-point semantics and fast-math flags ([IEEE754]; Menendez, Nagarakatte & Gupta 2016 [MNG16])	13.8
Verifying transformations	SMT-based verification (Alive, Lopes et al. 2015 [LMNR15]; Alive-FP 2016 [MNG16]; Alive2, Lopes et al. 2021 [LLM+21]); bounded exhaustive checking and its bitwidth caveats; translation validation (Pnueli, Siegel & Singerman 1998 [PSS98]; Necula 2000 [Nec00]) vs verified compilers (CompCert, Leroy 2009 [Ler09]; Csmith's findings, Yang et al. 2011 [YCER11])	13.9

flowchart LR
  CS[Local value numbering<br/>Cocke–Schwartz 1970] -->|extend scope| SC[Superlocal / dominator VN<br/>EarlyCSE]
  CS -->|same information, as a graph| DAG[Block DAGs<br/>Aho–Johnson–Ullman 1977]
  CF[Constant folding] --> PH[Peephole optimization<br/>McKeeman 1965]
  PH -->|retargetable, rule-based| DF[Davidson–Fraser 1980]
  PH -->|rules as C++| HC[Hand-written combiners<br/>InstCombine]
  HC -->|readable patterns| PM[Embedded matchers<br/>PatternMatch]
  DF -->|rules as data| DSL[Pattern DSLs<br/>match.pd, ISLE, GISel]
  PH -->|find the rules| SO[Superoptimization<br/>Massalin 1987]
  SO -->|learn a peephole table| BA[Bansal–Aiken 2006]
  SO -->|random search| ST[STOKE 2013]
  SO -->|SMT synthesis| SP[Souper 2017]
  SP -->|generalize| GEN[Alive-Infer 2017, Hydra 2024]
  HC -->|one form per class| CAN[Canonical forms]
  CAN -->|termination, confluence| RW[Newman 1942<br/>Knuth–Bendix 1970]
  CAN --> RA[Reassociation by rank<br/>Briggs–Cooper 1994]
  RA -.->|opposite goal: parallelism| TH[Tree-height reduction<br/>Baer–Bovet 1968, Brent 1974]
  CF --> SR[Mul/div by constants<br/>Bernstein 1986, GM 1994]
  REF[Refinement, poison, freeze<br/>Lee et al. 2017] --> AL[Alive 2015, Alive2 2021]
  REF --> BX[Bounded exhaustive checking]
  AL --> TV[Translation validation<br/>Pnueli 1998, Necula 2000]
  TV -.->|alternative| CC[Verified compiler<br/>CompCert 2009]
  AL -.->|verifies rules of| DSL
  AL -.->|verifies rules of| HC

Who uses what¶

System	Technique	Notes
LLVM 23 (middle end)	Constant folding (`ConstantFolding.cpp`, `ConstantFold.cpp`); InstSimplify + InstCombine written with `PatternMatch`, canonical operand order by `getComplexity`; EarlyCSE (dominator-scoped value numbering with memory generations); DCE/ADCE; Reassociate with ranks	Lessons 13.1, 13.2, 13.4, 13.5, 13.6
LLVM 23 (back end)	SelectionDAG (block DAGs with a CSE map; `BuildUDIV`/`BuildSDIV` magic numbers); GlobalISel combiner rules in TableGen; MachineCombiner (latency-driven reassociation)	Lessons 13.2, 13.5, 13.6, 13.7
GCC 15	`match.pd` compiled by `genmatch` (a rule DSL); `fold-const.cc`; SCCVN (FRE); `tree-ssa-reassoc` with ranks; `expand_divmod` magic numbers	Lessons 13.1, 13.2, 13.6, 13.7
Cranelift	ISLE: mid-end simplification rules and instruction lowering in one DSL (`opts/*.isle`), including division by constants	Lessons 13.2, 13.7
MLIR	Canonicalization patterns and the greedy worklist rewrite driver	Lessons 13.2, 13.4
CompCert	Verified value numbering over extended basic blocks; a compiler proved to preserve behavior	Lessons 13.1, 13.9
Alive2, Souper, STOKE, GNU superoptimizer	Checking InstCombine rules and whole LLVM passes by SMT; synthesizing rewrites for LLVM IR; stochastic search for x86-64; enumerative search for short idioms	Lessons 13.3, 13.9

Comparison¶

One row per technique, the same rows as the lessons' §8 tables (each lesson has the "Choose it when…" paragraphs).

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Local scope (one block)	Only redundancy/constants within a block	\(O(n)\) · fastest	Simple, easy to debug	Lowest	Peepholes, LVN, block-level combiners (SelectionDAG)
Superlocal scope (EBB)	+ facts along EBB paths	\(O(n)\) with a scoped table	Same as local, path by path	Low	CompCert CSE; historical VN
Regional (dominator tree)	+ facts from all dominators	\(O(n)\) + dominator tree	Misses join and partial redundancy	Low–medium	EarlyCSE, DVNT
Global (whole CFG)	Joins, partial redundancy, loops	Iterative dataflow / SSA · slower	Most precise intraprocedural	High	GVN, PRE, SCCP (Ch 14, 17)
Constant folding	Exactly the constant subexpressions	\(O(n + u)\) worklist · negligible	Exact if it models the target; pitfalls in §4	Low per op, high to get every corner right	Everywhere: front ends, IRBuilder, InstSimplify
Hand-written combiner	Unlimited: any C++ (analyses such as KnownBits inside rules)	\(O(m\ell)\) per pop · fast (compiled, hand-ordered)	Rules are code: hard to audit or verify; flag handling by hand	High per rule, lowest infrastructure	LLVM InstCombine, GCC `combine.cc`, `pebble-peephole`
Embedded pattern matcher	Same as its host language, patterns readable	\(O(\ell)\) per pattern · as fast as hand-written	Rules read like math; preconditions still ad hoc	Medium (a template library)	LLVM `PatternMatch`, MLIR C++ patterns
External pattern DSL	Limited to what the DSL expresses (+ escape hatches)	Decision tree \(O(d)\) · compiled: fast; interpreted: slower (lab: 75–95 vs 25–40 ms)	Rules are data: can be verified (Alive, Crocus), listed, counted	High infrastructure, lowest per rule	GCC `match.pd`, Cranelift ISLE, GlobalISel combiner, `pebble-peephole-dsl`
Enumerative superoptimization	Optimal within \(I\), \(K\) and \(L\)	Exponential in \(L\) · \(L \le 4\)–5	Optimal, verified if a full check follows	Low (the lab tool: ~300 lines)	Finding short branch-free idioms; building peephole tables (GSO, Bansal–Aiken)
Stochastic superoptimization (STOKE)	Reaches long sequences; no optimality guarantee	Unbounded random walk · minutes–hours	Verified rewrites; quality depends on cost model	High (x86 semantics, verifier)	Hot kernels, research
Solver-based synthesis (Souper)	Complete for its templates and components	One SMT query per candidate · seconds–minutes per fragment	Verified; finds missing IR optimizations	High (SMT encodings of IR)	Offline discovery of LLVM InstCombine rules
Learned rewrite rules (Alive-Infer, Hydra)	Rules with symbolic constants and weakest-like preconditions	Verification per width · minutes	Generalized, verified rules, even code	High	Turning superoptimizer findings into compiler rules
Canonical forms (partial canonicalization)	Removes syntactic variants; does not decide equivalence	\(O(n)\) · negligible	Fewer rules needed; later passes see equal things as equal	Low, but needs discipline across all rules	InstCombine, ISLE cprop, GCC fold; before value numbering
Termination and confluence reasoning (measures, critical pairs, completion)	Guarantees the engine stops and (if confluent) is order-independent	Critical pairs \(O(m^2\ell^2)\); completion may diverge	Proofs, not code; catches looping and order-dependent rule sets	Medium (by hand) to high (tools)	Designing rule sets (E2), term-rewriting tools, e-graph rule synthesis
Local value numbering	All redundancy within a block, up to commutativity and the identities it knows	\(O(n)\) expected · very fast	Needs flag intersection to be sound	Low (a hash table)	EarlyCSE/GVN building block, `pebble-lvn`
Memory in value numbering	Redundant loads and forwarding between writes; conservative at every store/call	\(O(1)\) per memory op	Sound without alias analysis, imprecise	Low (a counter)	EarlyCSE generations, GVN with MemDep, MemorySSA
DAG-based local optimization	Same redundancy as LVN, plus reordering and dead-node removal for non-SSA code	\(O(n)\) · fast	Reassembly choices affect registers (NP-hard to optimize)	Medium	Textbook block optimization, SelectionDAG
Worklist DCE	Removes trivially dead code, not dead cycles	\(O(n + u)\) · very fast	Always sound	Lowest	Every pass cleans up after itself; `dce`, `pebble-dce`
Rank-based reassociation	Exposes loop invariants, constants and common subexpressions; can destroy sharing	\(O(n + \sum k \log k)\) · fast	Left-deep chains (long critical paths); must drop `nsw`	Medium	Mid-level: LLVM Reassociate, GCC reassoc, `pebble-reassociate`
Tree-height reduction	Minimal critical path for one tree (with arrival times)	\(O(k \log k)\) per tree	Balanced trees need more registers	Low–medium	Back end with latencies: MachineCombiner; vectorized reductions
Multiplication by constants	Exact for every constant; gain only when the chain is short	\(O(b)\) to compute · 1–3 cheap instructions vs a 3-cycle `mul`	Target-dependent; wrong cost models make code slower	Low (NAF), medium (search + costs)	Instruction selection (x86 `lea`, AArch64 shifted operands)
Division by invariant integers	Exact for every \(N\)-bit dividend (Theorems 13.7.4–13.7.10)	\(O(N)\) to compute · 1 multiply + few ops vs a 20–90-cycle divide	Always a large win; needs a proof per variant	Medium (the proofs are the hard part)	Every compiler: SelectionDAG `BuildUDIV`/`BuildSDIV`, GCC `expand_divmod`, Cranelift ISLE rules
Refinement	The correctness criterion: allows removing UB and nondeterminism, never adding them	Deciding it: Lesson 13.9	Counterexamples pinpoint inputs	Conceptual; tools do the work	Specifying every optimization; Alive2, CompCert
Undefined behavior and poison	Poison defers UB so speculation is sound; `freeze` stops propagation	—	Subtle: `undef` duplication bugs	High (every pass must respect it)	LLVM IR semantics, Rust MIR (UB), C/C++ front ends
Poison-generating flags	Carry source-level facts (no overflow, exactness) into the IR	\(O(1)\) per rule to decide with ExactEqual	Most peephole bugs are flag bugs	Medium per rule	InstCombine, E2, reassociation (E5), LVN (E3)
Floating-point semantics and fast-math	IEEE exactness by default; per-flag licenses	—	Rules must consider \(-0\), NaN, \(\infty\)	Medium	Numerics; `-ffast-math`, `-ffp-contract`
SMT-based verification (Alive, Alive2, Alive-FP)	Complete for fixed widths, all widths up to 64; memory and FP supported; loops bounded	NP-hard · seconds, timeouts on wide mul/div	Counterexample with the failing check	Very high (semantics in SMT)	Proving InstCombine rules; validating LLVM's test suite
Bounded exhaustive checking	Complete at small widths only; a test beyond them	Exponential in total input bits · instant at 8 bits	First counterexample in a fixed order	Low (an interpreter)	Unit tests of analyses; drills; the lab's checker; quick rule screening
Translation validation and verified compilers	TV: per run, may say unknown; CompCert: all runs, fewer optimizations	TV: per pass per function; CompCert: normal compile	TV: counterexamples; CompCert: no bugs in verified parts [YCER11]	TV high; verified compiler very high	Alive2 over LLVM; CompCert in safety-critical code

Comparison-lab results (reproduce with uv run python labs/ch13-peephole/measure.py --build build/<preset> --repeat 7; reference solutions, Linux x86-64): the hand-written engine (pebble-peephole) and the DSL engine (pebble-peephole-dsl) produce the same code on every function of the corpus — 4 824 → 4 185 instructions with 1 355 rule applications on synthetic.ll, 70 → 60 on programs.ll; on the 30× corpus (144 720 instructions) the hand-written engine takes 25–40 ms and the interpreted DSL engine 75–95 ms beyond a 225–250 ms opt no-op run; 286 vs 403 source lines, of which 29 are the DSL's rules. The bounded checker decides a two-argument i8 rewrite (66 049 inputs) in 0.03 s; the superoptimizer explores 962 736 candidates for signum up to length 3 in 0.1 s.

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 13.1	scopes, constant folding	Pebble implements `pebble-constfold` (E1); quiz; flashcards
2	Lesson 13.2	hand-written combiners, embedded matchers, pattern DSLs	Pebble implements `pebble-peephole` (E2); lab Part A (`pebble-peephole-dsl`) and Part D (measurement)
3	Lesson 13.3	enumerative, stochastic, solver-based superoptimization; learned rules	★ lab Part C (`ch13-superopt`); theory + quiz for STOKE, Souper, Alive-Infer/Hydra
4	Lesson 13.4	canonical forms, termination and confluence	E2's canonicalizing rules and its termination measure; lab Part D (two engines, one result); quiz
5	Lesson 13.5	LVN, memory in VN, DAGs, DCE	drill `lvn-table`; Pebble implements `pebble-lvn` (E3) and `pebble-dce` (E4); drill `value-numbering` (Ch 8)
6	Lesson 13.6	rank-based reassociation, tree-height reduction	drill `reassoc-ranks`; Pebble implements `pebble-reassociate` (E5)
7	Lesson 13.7	multiplication and division by constants	drill `magic-division`; E2's power-of-two rules R10–R14; lab Part B checks magic numbers at small widths
8	Lesson 13.8	refinement, UB/poison/freeze, flags, fast-math	drills `rewrite-validity`, `flags`, `poison-propagation` (Ch 9); the flag rules of E2, E3, E5
9	Lesson 13.9	SMT verification, bounded exhaustive checking, TV vs verified compilers	lab Part B (`ch13-rewrite-check`), cross-checked with `instcombine` and Alive2
10	Exercises	Pebble uses constant folding, a flag-aware hand-written peephole engine, LVN with memory versions, worklist DCE and rank-based reassociation	`./course test 13`
11	Comparison lab `labs/ch13-peephole/`	hand-written vs DSL engine; bounded checker; ★ superoptimizer	lab tests + measurement
12	Theory test	all	`./course quiz 13` (≥ 80 % to finish)

Practice and check¶

./course drill lvn-table --difficulty medium    # fill in a value-numbering table (commutativity, identities, memory)
./course drill rewrite-validity                 # valid rewrite? if not, give a counterexample input
./course drill magic-division                   # magic multiplier and shift for x / d
./course drill reassoc-ranks                    # ranks and the reassociated operand order
./course flash 13                               # daily, a few minutes
./course quiz 13                                # after the lessons
./course test 13                                # after the exercises and the lab
./course status                                 # done = quiz ≥ 80 % and tests pass

References¶

The chapter's annotated bibliography — papers, textbook sections, pinned source files and docs — is in references.md. Start with: [LHK+17] (poison, undef and freeze, the semantics every lesson relies on), [LLM+21] (Alive2), [GM94] (division by invariant integers), [BC94] (ranks and reassociation), [Mas87] and [SCC+17] (superoptimization then and now), [EaC3, Ch. 8] (local optimization and value numbering), and the InstCombine contributor guide [LLVM-ICGuide].