Lesson 24.2 — Compile-time versus run-time: proving, dispatching, speculating

Techniques: static check elimination — prove at compile time that a run-time check cannot fail and delete it (Pebble's bounds and overflow checks); multiversioning with run-time dispatch — compile several variants and choose one at run time, per machine (target_clones, ifuncs) or per loop entry (alias-check versioning); speculation with guards and deoptimization — compile under an assumption that cannot be proved, test it with a guard, and fall back to unoptimized code, reconstructing its state from a side table · Pebble implements: static elimination (pebble-bce, Ch 18; in -O1 via Lesson 24.1), measured by the lab's benchmark (E2); the other two are studied on LLVM and read in the stack maps llc emits · Drill: none (see §9) · Prerequisites: Lesson 18.9, Lesson 0.3 (tiers, deoptimization, OSR), Lesson 20.10 · Time: 4 hours

Pebble's xs[i] costs a comparison and a conditional branch every time it runs, because the language promises a trap on a bad index. There are three places that cost can go. The compiler can prove that \(0 \le i < N\) and emit nothing: the cost moves entirely to compile time, and it moves there only when a proof exists. The compiler can emit two loops, one with checks and one without, and a test at the loop entry that picks the checked one when the bound is unknown: the cost becomes one test per loop entry plus code size. Or the compiler can assume the index is in range, emit the fast loop only, guard the assumption, and on failure jump to an interpreter with a reconstructed frame: the cost becomes a test per iteration that always predicts well, plus a side table, plus the rare disaster. Every language implementation makes this choice for every check, and every dynamic-language JIT makes it for types, shapes and call targets too. This lesson gives the three answers their definitions, their proofs and their price, and reads the artifacts they leave in LLVM's output: the deleted pebble_trap calls, the .resolver function of a target_clones symbol, and the stack map of a deoptimize call.

1. Problem and motivation

Static check elimination

Gupta [Gup90] and Bodík, Gupta and Sarkar [BGS00] made array bounds checks a compiler problem: a check is redundant if a dataflow analysis proves that the index is in range on every path, and a check can be hoisted out of a loop if the loop's trip count and the index's recurrence are known. Java implementations invested in it because the language mandates the check and benchmarks are loops over arrays; Swift and Rust inherited the same economics, and Pebble is in that family by design (spec §11.3). The chapter 18 pass pebble-bce is the course's instance: it asks ScalarEvolution whether icmp ult i, N is known true at the check. What this lesson adds is the accounting: on the eight benchmarks, how many of the checks survive, and what they cost against -O2.

Multiversioning with run-time dispatch

When the property cannot be proved at compile time but is cheap to test at run time, compile both outcomes. The oldest form is CPU dispatch: GCC's target_clones attribute [GCC-MultipleTarget] compiles a function once per instruction-set extension and emits a resolver that picks the variant when the dynamic linker first binds the symbol (an IFUNC). LLVM's LoopVersioning [LLVM-LoopVersioning] does it for aliasing: the vectorizer compiles a vector loop that assumes a and b do not overlap, and a scalar loop that does not, and tests the pointer ranges at the loop entry. Neither needs a proof, and neither can be wrong: both versions are correct, only their speed differs.

Speculation with guards and deoptimization

When the property is probably true and testing it is cheap but compiling both outcomes is not (the slow path would be the whole unoptimized function), compile only the fast one and keep an escape hatch. Hölzle, Chambers and Ungar [HCU92] built this for Self: optimized code carries guards, and a failed guard triggers deoptimization, which rebuilds the interpreter's frames from a side table (a "scope descriptor") and continues there. Every JavaScript and Java JIT works this way (Lesson 0.3). LLVM provides the pieces to language implementers: llvm.experimental.guard and llvm.experimental.deoptimize with a "deopt" operand bundle, lowered to a statepoint whose stack map records where the interpreter's values live [LLVM-Statepoints].

2. Definitions and algorithms

Definition 24.2.1 (Compile-time and run-time cost of a decision)

A decision \(\delta\) concerns a predicate \(\pi\) (an index is in range, two pointers do not alias, a callee is \(f\)) at a program point that executes \(n\) times. Let \(t_c(\delta)\) be the compile-time cost of the strategy chosen for \(\delta\), \(t_r(\delta)\) its run-time cost per execution when \(\pi\) holds, and \(t_f(\delta)\) per execution when \(\pi\) fails. The total cost is \(t_c + n\,(p\,t_r + (1 - p)\,t_f)\) where \(p\) is the fraction of executions where \(\pi\) holds. A strategy is sound if the program's observable behavior is the same as with the check kept, for every execution.

The three strategies on xs[i] with \(N = 1024\)

strategy	\(t_c\)	\(t_r\)	\(t_f\)	when it applies
keep the check	0	cmp + branch	trap	always
prove and delete	a SCEV query	0	(never fails: proved)	a proof exists
version	compile 2 loops	one test per loop entry, amortized	the checked loop	\(\pi\) is testable once per region
speculate + guard	1 loop + side table	cmp + branch, always predicted	deoptimize: microseconds	\(p \approx 1\)

Static check elimination

Definition 24.2.2 (Redundant check)

A check assert c at point \(q\) (Pebble: br c, ok, trap) is redundant if \(c\) evaluates to true on every execution that reaches \(q\). It is provably redundant by an analysis \(\mathcal{A}\) if \(\mathcal{A}\) establishes a fact at \(q\) that implies \(c\): for a bounds check, \(0 \le i < N\) from the recurrence of \(i\) and the conditions of the branches that dominate \(q\) (Lesson 18.9, Theorem 18.9.2).

Algorithm 24.2.3 (Check elimination by dominating facts and recurrences: what pebble-bce does)

• Input: a function in SSA and loop-simplify form; ScalarEvolution \(\mathrm{SE}\).
• Output: the function with every provably redundant bounds check replaced by an unconditional branch.
• Precondition: every check has the shape %c = icmp ult %i, N; br %c, %ok, %trap with %trap a block that calls pebble_trap and ends in unreachable (the code generator's shape, Lesson 11.6).
• Postcondition: behavior is unchanged (Theorem 24.2.8); no remaining check is provable by \(\mathrm{SE}\) alone.
• Invariant: every check removed so far was provably redundant on the function as it was when it was examined; later removals cannot make an earlier one wrong, because removing a check only deletes an edge to a trap block (it adds no facts).

function EliminateChecks(F, SE):
    for each check (c = icmp ult i, N; br c, ok, trap) in F:
        if SE.isKnownPredicateAt(ult, SCEV(i), N, at = the branch):     # recurrences + dominating conditions
            replace the branch by `br ok`
    delete every trap block without predecessors

How many checks survive: -O0, your -O1, LLVM's -O2

Reproduce (pebblec 23.1.2 build from -DPEBBLE_USE_SOLUTION=all; SOL as in Lesson 24.1):

for p in checks matmul nbody sort; do
  for L in -O0 -O1 -O2; do
    echo "$p $L: $($SOL/bin/pebblec $L --emit=llvm labs/ch24-capstone/inputs/bench/bench-$p.pbl -o - | grep -c 'call void @pebble_trap')"
  done
done

Output (complete):

checks -O0: 14
checks -O1: 12
checks -O2: 3
matmul -O0: 20
matmul -O1: 6
matmul -O2: 0
nbody -O0: 8
nbody -O1: 0
nbody -O2: 0
sort -O0: 11
sort -O1: 6
sort -O2: 1

What to notice: each pebble_trap call is one surviving check (overflow, bounds, division). -O1 removes those whose index is a for counter bounded by the array length (matmul: 14 of 20; nbody: all 8, where the loops have constant bounds and the arithmetic is float). -O2 removes more because IndVarSimplify rewrites the recurrences into a form its range analysis proves, and CorrelatedValuePropagation (through LazyValueInfo) reasons from the conditions of the dominating branches, including the checks' own. The 3 checks -O2 keeps in bench-checks are genuinely not provable: xs[i] = (i * 37) % 101 can overflow only if i * 37 does, and the multiplication's range is what the check is about. The run time follows the count: 28.7, 13.0 and 11.5 ms (benchmark.md).

Multiversioning with run-time dispatch

Definition 24.2.4 (Versioned region)

A versioned region for predicate \(\pi\) is a triple \((T, R_\pi, R_{\neg\pi})\): a test \(T\) that evaluates \(\pi\) at the region's entry, and two copies of the region, \(R_\pi\) compiled under the assumption \(\pi\) and \(R_{\neg\pi}\) compiled without it, with \(T\) branching to \(R_\pi\) iff \(\pi\) holds. CPU dispatch is the special case where \(\pi\) is "the CPU supports feature set \(X\)", the region is a whole function, and \(T\) runs once, at symbol resolution (an IFUNC resolver).

Algorithm 24.2.5 (Loop versioning, after LLVM's LoopVersioning)

• Input: a loop \(L\) in loop-simplify form; a set of run-time checks \(\Pi\) (pointer-range checks from the loop access analysis, or a SCEV predicate) whose truth makes a transformation legal.
• Output: the CFG with \(L\) duplicated: \(L_\pi\) (to be transformed) and \(L_{\neg\pi}\) (the original), and a preheader test.
• Precondition: every check in \(\Pi\) is loop-invariant, so it can be evaluated in the preheader.
• Postcondition: every execution runs exactly one of the two loops and produces the original result (Theorem 24.2.9); \(L_\pi\) may now be transformed under \(\Pi\).
• Invariant: the phis at the loop exits merge the values of both copies.

function VersionLoop(L, Π):
    pre ← preheader(L)
    L' ← Clone(L)                                    # the fallback copy, unchanged
    t ← in pre: conjunction of the checks in Π       # e.g. (a_end <= b_begin) or (b_end <= a_begin)
    replace pre's terminator by br t, header(L), header(L')
    for each exit block e of L:
        for each phi φ in e:  add an incoming value from the matching block of L'
    AddNoAliasMetadata(L, Π)                         # what the vectorizer will rely on
    return (L, L')

Two multiversioned artifacts: an IFUNC resolver and a vectorizer's alias check

Reproduce (clang 23.1.2, x86-64):

cat > clones.c <<'EOF'
__attribute__((target_clones("avx2", "default")))
long dot(const long *a, const long *b, int n) {
  long s = 0;
  for (int i = 0; i < n; i++) s += a[i] * b[i];
  return s;
}
EOF
clang-23 -O2 -fno-discard-value-names -S -emit-llvm clones.c -o - | grep -E '^define|ifunc|resolver|ret ptr'
cat > axpy.c <<'EOF'
void axpy(long n, double *a, double *b, double k) {
  for (long i = 0; i < n; i++) a[i] = a[i] + k * b[i];
}
EOF
clang-23 -O2 -fno-discard-value-names -S -emit-llvm axpy.c -o - | grep -E '^[a-z.0-9]+:|bound[01]|found.conflict' | head -8

Output (the dot listing complete; axpy abridged by the head -8 to the labels up to the check):

$dot.resolver = comdat any
@dot.ifunc = weak_odr dso_local alias i64 (ptr, ptr, i32), ptr @dot
@dot = weak_odr dso_local ifunc i64 (ptr, ptr, i32), ptr @dot.resolver
define dso_local i64 @dot.avx2.0(ptr nofree noundef readonly captures(none) %a, ptr nofree noundef readonly captures(none) %b, i32 noundef %n) #0 {
define dso_local i64 @dot.default.1(ptr nofree noundef readonly captures(none) %a, ptr nofree noundef readonly captures(none) %b, i32 noundef %n) #1 {
define weak_odr dso_local ptr @dot.resolver() #2 comdat {
resolver_entry:
  ret ptr %dot.avx2.0.dot.default.1
entry:
for.body.preheader:                               ; preds = %entry
vector.memcheck:                                  ; preds = %for.body.preheader
  %bound0 = icmp ult ptr %a, %scevgep10
  %bound1 = icmp ult ptr %b, %scevgep
  %found.conflict = and i1 %bound0, %bound1
  br i1 %found.conflict, label %for.body.preheader14, label %vector.ph
vector.ph:                                        ; preds = %vector.memcheck

What to notice: dot became two function bodies (.avx2.0, .default.1) and an ifunc whose resolver runs __builtin_cpu_supports once and returns the address of the variant: Definition 24.2.4 with \(T\) evaluated by the dynamic linker. axpy is the loop form: vector.memcheck tests whether the two arrays overlap (%found.conflict) and branches to the vector loop (vector.ph) or to the original scalar loop; the check costs two comparisons per call, and the vector loop runs under an assumption the compiler could not prove (a and b are arbitrary pointers).

Speculation with guards and deoptimization

Definition 24.2.6 (Assumption, guard, deoptimization point)

An assumption \(A\) is a predicate the optimized code \(O\) was compiled under. A guard \(g_A\) is a test of \(A\) placed before the first instruction of \(O\) that depends on it. A deoptimization point is a call deoptimize(state) reached when a guard fails, where state names, for every live variable of the unoptimized program at the corresponding point, the value it has in \(O\) (a register, a stack slot or a constant). The deoptimization transfers control to the unoptimized code \(U\) at that point, after building \(U\)'s frame from state. It is exact if the resulting execution of \(U\) is one \(U\) could have produced on its own.

Algorithm 24.2.7 (Guarded speculation with deoptimization, after [HCU92] and LLVM's deoptimize)

• Input: a function \(U\), a set of assumptions \(A_1, \dots, A_k\) with their profiles, and the optimizer.
• Output: \(O\) = the function optimized under \(A_1 \dots A_k\), with a guard per assumption and a side table (stack map) per deoptimization point.
• Precondition: every \(A_i\) is testable by a side-effect-free expression at its guard; for every deoptimization point the set of live variables of \(U\) at the matching point is known.
• Postcondition: every execution of \(O\) either satisfies all guards and computes what \(U\) computes, or deoptimizes at the first failing guard into \(U\)'s state (Theorem 24.2.10).
• Invariant: at every guard, the values of \(U\)'s live variables are recoverable from \(O\)'s state through the side table.

function Speculate(U, assumptions):
    O ← copy of U
    for A in assumptions:
        p ← first point of O whose transformation needs A
        insert at p:  if not A: deoptimize(liveState_U(p))       # the guard and its "deopt" bundle
    O ← Optimize(O, assuming every A after its guard)          # e.g. delete the checks A subsumes
    for each deoptimize call d in O:
        record in the stack map: for each live variable v of U at d's point, where O keeps v
    return O

at run time, deoptimize(d):
    frame ← new frame of U at d's point
    for each (v, location) in stackmap[d]: frame[v] ← read(location)
    discard O's frame; continue U at d's point                 # or in the interpreter (Lesson 0.3)

A deoptimization point compiled by llc: the call, and its stack map

Reproduce (llc 23.1.2, llvm-readobj 23.1.2, x86-64):

cat > deopt.ll <<'EOF'
declare i64 @llvm.experimental.deoptimize.i64(...)
define i64 @fast(i64 %x, i1 %assumption) {
entry:
  br i1 %assumption, label %ok, label %slow
ok:
  %r = mul i64 %x, 3
  ret i64 %r
slow:
  %d = call i64 (...) @llvm.experimental.deoptimize.i64(i32 7) [ "deopt"(i64 %x, i64 42) ]
  ret i64 %d
}
EOF
llc -O2 deopt.ll -o - | sed -n '/^fast:/,/Lfunc_end0/p' | grep -v '^\s*\.cfi'
llc -O2 -filetype=obj deopt.ll -o deopt.o && llvm-readobj --stackmap deopt.o | sed -n '/Num Records/,$p'

Output (complete):

fast:                                   # @fast
# %bb.0:                                # %entry
    testb   $1, %sil
    je  .LBB0_2
# %bb.1:                                # %ok
    leaq    (%rdi,%rdi,2), %rax
    retq
.LBB0_2:                                # %slow
    pushq   %rax
    movq    %rdi, (%rsp)
    movl    $7, %edi
    callq   __llvm_deoptimize@PLT
.Ltmp0:
.Lfunc_end0:
Num Records: 1
  Record ID: 2882400015, instruction offset: 26
    5 locations:
      #1: Constant 0, size: 8
      #2: Constant 0, size: 8
      #3: Constant 2, size: 8
      #4: Indirect [R#7 + 0], size: 8
      #5: Constant 42, size: 8
    0 live-outs: [ ]

What to notice: the guard is testb $1, %sil; je, the fast path is three instructions, and the slow path calls the runtime's __llvm_deoptimize (a symbol the language runtime provides) with the actual argument 7 in %edi. The stack map is the side table of Algorithm 24.2.7: record ID 2882400015 (the statepoint ID, 0xABCDEF00 + 15), the offset of the call, and the "deopt" state: three header constants (calling convention, flags, and 2 = the number of deopt values), then %x spilled to [rsp + 0] (Indirect [R#7 + 0], register 7 is rsp) and the constant 42. The runtime reads exactly these locations to rebuild the interpreter frame; the movq %rdi, (%rsp) before the call exists for no other reason.

3. Worked example

Running example (used for every technique in this lesson): the inner loop of bench-checks,

for i in 8..1024 { window = window + (prefix[i] - prefix[i - 8]); }

with the three checks it carries per iteration: bounds on prefix[i], bounds on prefix[i - 8], and overflow on the two additions and the subtraction (five checks; the i - 8 subtraction is a sixth). Its CFG after lowering:

flowchart TD
  H([header: i < 1024?]) --> B1[c1 = i ult 1024]
  B1 -->|c1| B2[c2 = i-8 ult 1024]
  B1 -->|!c1| T1[trap bounds]
  B2 -->|c2| B3[o = ssubo/saddo checks]
  B2 -->|!c2| T2[trap bounds]
  B3 -->|ok| L[latch: i = i + 1]
  B3 -->|overflow| T3[trap overflow]
  L --> H
  H -->|done| X[exit]

Static check elimination

Algorithm 24.2.3 asks ScalarEvolution about each check at its branch:

check	fact needed	what SE knows at the branch	verdict
prefix[i]: \(i <_u 1024\)	\(0 \le i < 1024\)	\(i = \{8,+,1\}\), guarded by \(i < 1024\) (the header)	redundant: removed
prefix[i - 8]: \(i - 8 <_u 1024\)	\(0 \le i - 8 < 1024\)	\(i - 8 = \{0,+,1\}\), and \(i < 1024 \Rightarrow i - 8 < 1016\)	redundant: removed
i - 8 overflow	\(i - 8 \ge -2^{63}\)	\(i \ge 8\)	redundant: removed
prefix[i] - prefix[i-8] overflow	the loaded values' ranges	unknown (array contents)	kept
window + (...) overflow	the sum's range	unknown	kept

Three of the five per-iteration checks go; the two that stay are about data, not indices, and no static analysis can prove them for arbitrary input. This is the -O1 column of the box in §2 (14 → 12 for the whole program: the outer loop's own checks and the first loop's are the difference).

Multiversioning with run-time dispatch

Suppose the bound were a parameter n instead of the constant 1024 and the array a &[int; 1024] parameter: the index checks are no longer provable, but \(\pi\) = "\(n \le 1024\)" is testable once. Algorithm 24.2.5 with \(\Pi = \{n \le 1024\}\):

step	action	result
1	clone the loop	\(L\) (to be optimized), \(L'\) (original, with checks)
2	test in the preheader	br (n <= 1024), header(L), header(L')
3	fix the exit phis	window merges from both latches
4	optimize \(L\) under \(\pi\)	the two bounds checks are now provable in \(L\) (Algorithm 24.2.3 with the added fact)

Cost: one comparison per call, twice the loop's code; the checked copy is never executed when \(n \le 1024\) but must exist. This is exactly what clang -O2 did to axpy with the alias check.

Speculation with guards and deoptimization

With the same parameter n, a JIT that has observed \(n \le 1024\) on every previous call compiles \(L\) alone under the assumption \(A\): \(n \le 1024\), with a guard at the loop entry and a deoptimization point whose state is \(\{i, \mathit{window}, n, \mathit{prefix}\}\). Trace of Algorithm 24.2.7 on a call with \(n = 2000\):

step	where	what happens
1	guard at loop entry	\(A\) fails: br to the deopt block
2	deoptimize(i = 8, window = 0, n = 2000, prefix = the frame slot)	the runtime reads the stack map: \(i\) is the constant 8, window is in %rax, n in %rsi, prefix at [rbp - 16]
3	frame reconstruction	a frame of the unoptimized loop is built with those four values
4	resume	the unoptimized loop runs with its checks; the first out-of-range index traps as the language requires
5	afterwards	the profile records \(A\) as violated; the next compilation of the function does not assume it

The guard costs one comparison per call (like the version test) but there is one loop in memory, not two; the price is the runtime machinery of step 2–3, which LLVM leaves to the language implementer (__llvm_deoptimize).

Try it

There is no drill for this lesson (§9 says why). Instead: pebblec -O1 --emit=llvm labs/ch24-capstone/inputs/bench/bench-checks.pbl -o - | grep -B3 'pebble_trap' shows every surviving check with the comparison that feeds it; decide for each one whether it is about an index or about data.

4. Invariants and correctness

Static check elimination

Theorem 24.2.8 (Soundness of check elimination)

Let \(\mathcal{A}\) be a sound analysis (every fact it reports at \(q\) holds on every execution reaching \(q\)). If Algorithm 24.2.3 removes a check whose condition \(c\) is implied by a fact of \(\mathcal{A}\) at \(q\), the transformed function has the same observable behavior as the original on every input.

Proof

Consider any execution of the original and the same input on the transformed function. Both run identically until the first removed check \(q\) is reached (nothing before it changed). At \(q\) the original evaluates \(c\); by soundness of \(\mathcal{A}\) and the implication, \(c\) is true, so the original continues to ok. The transformed function branches to ok unconditionally. The states agree again, and the argument repeats at the next removed check. No other instruction was changed, so outputs, traps at kept checks and the exit status coincide. The trap blocks deleted afterwards had no predecessors, so no execution reached them. Removing the edge adds no fact for \(\mathcal{A}\), which is why the invariant of Algorithm 24.2.3 is maintained regardless of the order of removals.

When it breaks: the shape precondition. A check whose trap block is reachable by another path (a merged trap block) would still be deleted correctly by this argument, but a check written icmp slt (signed) with a negative index would not be caught by the unsigned fact \(i <_u N\); the code generator's ult on a 64-bit index is what makes one comparison cover both bounds (Lesson 11.6).

Multiversioning with run-time dispatch

Theorem 24.2.9 (Versioning preserves behavior)

If \(R_{\neg\pi}\) is the original region and \(R_\pi\) is obtained from a copy of it by transformations that are correct under the assumption \(\pi\), then the versioned region computes the original result on every execution, provided the test \(T\) has no side effects and \(\pi\) is invariant over the region.

Proof

Two cases per execution of the region. If \(T\) evaluates to false, control enters \(R_{\neg\pi}\), an unchanged copy: same result. If \(T\) evaluates to true, \(\pi\) holds at entry and, being invariant over the region, at every point of \(R_\pi\); the transformations applied to \(R_\pi\) are correct under \(\pi\) by hypothesis, so \(R_\pi\) computes what the copy computed before transformation, which is what the original computes. The exit phis select the value of whichever copy ran. \(T\) itself changes no state. For CPU dispatch the argument is the same with \(\pi\) evaluated once by the resolver; the loader caches the choice, so every call runs the selected body.

Speculation with guards and deoptimization

Theorem 24.2.10 (Exactness of deoptimization)

Let \(O\) be compiled from \(U\) by Algorithm 24.2.7, and suppose the transformations applied under assumption \(A_i\) only affect instructions dominated by \(g_{A_i}\) and preserve, at every deoptimization point \(d\), the values of the live variables of \(U\) recorded in the stack map. Then every execution of \(O\) produces the observable behavior of an execution of \(U\).

Proof

Let an execution of \(O\) reach guard \(g_{A_i}\). If it passes, the code after it was compiled under \(A_i\), which holds, and by the correctness of the transformations it computes what \(U\) computes until the next guard. If it fails, control reaches \(d\); by the hypothesis on the stack map, for every live variable \(v\) of \(U\) at the matching point \(p\), the recorded location holds the value \(v\) has in the execution of \(U\) that made the same choices so far (all earlier guards passed, and code before \(g_{A_i}\) is unaffected by \(A_i\) because it is not dominated by the guard). The rebuilt frame is therefore a state of \(U\) at \(p\), and continuing \(U\) from it yields an execution of \(U\). Dead variables of \(U\) are not recorded, and need not be: no later instruction of \(U\) reads them (Definition 14.3.6 of liveness). Induction over the guards reached completes the argument. Where it breaks: a transformation that moved a side effect above the guard (a store hoisted past \(g_{A_i}\)), which would have executed in \(O\) but not yet in \(U\) at \(p\): LLVM forbids this by giving llvm.experimental.guard and deoptimize calls the memory effects of an unknown call, so nothing crosses them.

5. Complexity

\(n\) = instructions, \(k\) = checks, \(q\) = the cost of one SCEV query (Lesson 18.3: polynomial in the expression size, cached), \(v\) = variants, \(s\) = the region's size, \(g\) = guards, \(\ell\) = live variables at a deoptimization point.

Technique	Compile time	Run time	Space	Justification
Static check elimination	\(O(k \cdot q)\)	\(-1\) compare-and-branch per removed check per execution	none	one query per check (Algorithm 24.2.3)
Multiversioning	\(O(v \cdot s)\) to compile the variants, plus the transformations on \(R_\pi\)	one test per region entry (IFUNC: once per process)	\(v \cdot s\) code	Definition 24.2.4: every variant is emitted
Speculation + deoptimization	\(O(s)\) for one variant plus \(O(g \cdot \ell)\) for the stack maps	one predicted branch per guard; a deoptimization costs a frame rebuild, \(O(\ell)\) reads, plus the transfer to \(U\) (Lesson 0.3: microseconds)	\(O(g \cdot \ell)\) side table	Algorithm 24.2.7 records \(\ell\) locations per point

Pathological family (versioning). A loop nest of depth \(m\) with an independent run-time predicate per level, versioned at every level, has \(2^m\) loop copies (each level's two versions each contain two versions of the next); LLVM's LoopVersioning is applied once per loop and the vectorizer's -runtime-memory-check-threshold (8 pointer pairs) caps the test, not the nesting, so the growth is left to the pass ordering. Pathological family (speculation). A guard that fails with probability \(1 - p\) per execution deoptimizes \(n(1 - p)\) times; with \(t_f \approx 10^4\) instructions per deoptimization and \(t_r = 1\), speculation loses to keeping the check as soon as \(1 - p > 10^{-4}\): this is why JITs count failures and stop assuming (Deoptimizer bailout counts in V8 [V8-Deopt]).

At scale: on the eight benchmarks the checks that -O2 cannot remove are 9 of 72, and every one of them is about data, not indices (the §2 box); Lesson 0.3's -XX:+PrintCompilation box shows HotSpot's made not entrant lines, each one a body abandoned after a deoptimization.

6. Variants and refinements

Static check elimination

• Loop-level hoisting [BGS00]: prove the check for the whole loop from the trip count and hoist a single check before it; trade-off: a check before the loop may trap earlier than the original (before side effects of iterations that would have run), which is only legal if the loop has none, or if the language allows imprecise traps (Java's does not; Pebble's does not).
• Inductive range check elimination (LLVM IRCE, llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp): split the iteration space into a pre-loop, a main loop where the check is provable, and a post-loop; trade-off: three loops instead of one, only worthwhile for hot loops (LLVM runs it only when a language enables it).
• Correlated value propagation on the trap edge (LLVM CorrelatedValuePropagation, Lesson 17.1's lattice with ranges): the unreachable trap block makes the condition a fact in ok; trade-off: needs LazyValueInfo's per-edge facts, which are expensive across large functions.
• Overflow checks as with.overflow intrinsics (Lesson 11.6): keeping the check and the operation together lets the back end fold them into one jo; trade-off: the check cannot be removed by a pass that does not understand the intrinsic.

Multiversioning with run-time dispatch

• Function multiversioning by attribute (target_clones, target("...") overloads) [GCC-MultipleTarget]: resolved by the loader once; trade-off: every clone is emitted whether or not the CPU exists in the fleet.
• Loop versioning for aliasing and for SCEV predicates [LLVM-LoopVersioning]: the tests are pointer ranges or predicate checks; trade-off: the vectorizer's runtime-check threshold limits the number of pointer pairs (8).
• Versioning by value profile (Lesson 20.10, indirect-call promotion): if (callee == f) inline f() else call callee; trade-off: the test is per call, and a wrong profile makes it pure overhead.
• Interpreter-side dispatch (Lesson 0.2's inline caches): the variant is selected per call site by a cached shape; trade-off: the cache itself is a run-time data structure.

Speculation with guards and deoptimization

• Uncommon traps and OSR [HCU92, Lesson 0.3]: HotSpot's uncommon_trap is a deoptimization point that also changes the profile so the next compilation does not repeat the assumption; OSR enters optimized code mid-loop, the reverse transfer; trade-off: two side tables (deopt and OSR) per method.
• Guard widening and loop predication (LLVM GuardWidening, LoopPredication, llvm/lib/Transforms/Scalar/LoopPredication.cpp): combine several guards into one, or hoist a per-iteration guard to the loop entry as a guard on the whole trip count; trade-off: the widened guard fails more often than each original (it deoptimizes when any would).
• Explicit guards vs. deoptimize calls [LLVM-Statepoints]: llvm.experimental.guard(cond) is an intrinsic the optimizer understands as a guard (it can widen and predicate it), lowered late by lower-guard-intrinsic into br cond, ok, deopt with a deoptimize call; trade-off: the intrinsic blocks optimizations that do not know it, so it is lowered as soon as guard-specific passes are done.
• Deoptimization to an interpreter vs. to baseline code (V8's Ignition vs. Sparkplug, Lesson 0.3): the reconstructed frame is an interpreter frame (simple, slow) or a baseline-compiled frame (needs a second frame layout); trade-off: engineering.

7. In real compilers

Static check elimination

LLVM

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp — InductiveRangeCheckElimination::run, InductiveRangeCheck::extractRangeChecksFromBranch (LLVM 23.1.2) [LLVM-IRCE]: the loop-splitting form of Algorithm 24.2.3, used by Java-on-LLVM implementations (Azul Falcon). The general facts come from llvm/lib/Analysis/ScalarEvolution.cpp — ScalarEvolution::isKnownPredicateAt and isLoopEntryGuardedByCond, which pebble-bce calls; llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp uses the trap edges.

• Pebble solutions/pebble/lib/Passes/Loops/BCE.cpp — the course's Algorithm 24.2.3 (Chapter 18, E5).
• GCC gcc/tree-vrp.cc and gcc/gimple-range.cc (GCC 15): value-range propagation removes __builtin_trap-guarded checks the same way (-fsanitize=bounds checks are ordinary conditionals to it).
• HotSpot src/hotspot/share/opto/loopTransform.cpp — PhaseIdealLoop::do_range_check (OpenJDK 21): range-check elimination by loop splitting with pre/main/post loops, the design IRCE copies.

Find where LLVM does it. In llvm/lib/Analysis/ScalarEvolution.cpp, find ScalarEvolution::isKnownPredicateAt. Question: which two sources of facts does it combine (which function does it call for the dominating branches)?

Multiversioning with run-time dispatch

LLVM

llvm/lib/Transforms/Utils/LoopVersioning.cpp — LoopVersioning::versionLoop, annotateLoopWithNoAlias (LLVM 23.1.2) [LLVM-LoopVersioning]: Algorithm 24.2.5, with the checks from LoopAccessInfo. target_clones is expanded by Clang's CodeGenModule::emitMultiVersionFunctions and lowered to ifunc + .resolver (clang/lib/CodeGen/CodeGenModule.cpp); the vectorizer's copy is llvm/lib/Analysis/LoopAccessAnalysis.cpp — RuntimePointerChecking and the option -runtime-memory-check-threshold (default 8 pointer pairs), which the vectorizer's versioning obeys.

• GCC gcc/multiple_target.cc — expand_target_clones, create_dispatcher_calls (GCC 15) [GCC-MultipleTarget]: the origin of target_clones.
• glibc sysdeps/x86_64/multiarch/ifunc-*.h: memcpy and friends are IFUNCs selected by CPU features at load time, the model both compilers follow.

Find where LLVM does it. In llvm/lib/Transforms/Utils/LoopVersioning.cpp, find LoopVersioning::versionLoop. Question: which utility clones the loop, and what does annotateLoopWithNoAlias attach to the versioned loop's memory instructions? (Quiz find-loop-versioning.)

Speculation with guards and deoptimization

LLVM

llvm/lib/CodeGen/SelectionDAG/StatepointLowering.cpp — SelectionDAGBuilder::LowerCallSiteWithDeoptBundleImpl, lowerStatepointMetaArgs (LLVM 23.1.2) [LLVM-StatepointLowering]: a deoptimize call becomes a statepoint whose "deopt" operands are recorded by llvm/lib/CodeGen/StackMaps.cpp — StackMaps::recordStatepoint, serializeToStackMapSection (the .llvm_stackmaps section the box reads) [LLVM-StackMaps]. llvm/lib/Transforms/Scalar/LowerGuardIntrinsic.cpp turns llvm.experimental.guard into the branch-and-deoptimize shape; LoopPredication.cpp hoists guards.

• HotSpot src/hotspot/share/runtime/deoptimization.cpp — Deoptimization::fetch_unroll_info, unpack_frames (OpenJDK 21): frame reconstruction from scope descriptors, the design of [HCU92].
• V8 src/deoptimizer/deoptimizer.cc — Deoptimizer::DoComputeOutputFrames (V8 13.6) [V8-Deopt]: builds the interpreter frames from the optimized frame's translation.

Find where LLVM does it. In llvm/lib/CodeGen/StackMaps.cpp, find StackMaps::recordStatepoint and the record layout it produces. Question: what are the three constants that precede the deopt values in every statepoint record (the box shows them as Constant 0, Constant 0, Constant 2)?

8. Comparison

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Static check elimination	removes a check iff a proof exists (sound; Theorem 24.2.8): 14 → 12 → 3 traps on bench-checks at -O0/-O1/-O2	compile time only · SCEV queries per check	zero run-time cost for proved checks; the rest stay	moderate (SCEV, dominating conditions)	Java, Swift, Rust, Pebble bounds checks
Multiversioning, run-time dispatch	\(k\) variants, one selected per call or per loop entry	code size \(\times k\); one indirect call or test · cheap	best variant per machine or per input; no correctness risk	low (attributes) to moderate (loop versioning)	target_clones, glibc ifuncs, LoopVersioning
Speculation with deoptimization	any assumption, with a guard; exact recovery (Theorem 24.2.10)	a test per guard; deopt is slow but rare	fastest when assumptions hold; cliffs when they fail	high: side tables, frame reconstruction	HotSpot, V8, llvm.experimental.deoptimize

Choose a static proof when the analysis can find it: it is free at run time and cannot be wrong. Choose versioning when the predicate is testable once per region and both outcomes occur in practice (unknown bounds, possibly aliasing pointers, several CPUs): it doubles code, never behavior. Choose speculation when the assumption holds almost always, the slow path is large, and you already have an interpreter or baseline tier to fall into: it is the only one of the three that needs a runtime.

Measured: the surviving-check counts of the §2 box, and their run-time consequence in benchmark.md (bench-checks: 28.7 / 13.0 / 11.5 ms for 14 / 12 / 3 checks).

9. Assessment

• Quiz: redundant-check-table (mapping), dominating-condition-check (single), versioning-exit-phi (single), find-loop-versioning (text), deopt-stackmap-locations (mapping), speculation-break-even (number). Tags static-elimination, multiversioning, speculation.
• Drill: none. The decisions of this lesson are cost-model judgments on real programs rather than a mechanical procedure with a unique answer; the quiz asks them on concrete instances (redundant-check-table, speculation-break-even), and the stack-map reading is exercised by the gc-roots drill of Lesson 24.5, whose oracle is the same liveness computation.
• Flashcards: tags static-elimination, multiversioning, speculation.
• Exercises: E2 (the benchmark report: explain each program's ratio with the checks that survive).

Pitfall

A guard is not a check. br i1 %inb, label %ok, label %trap and br i1 %inb, label %ok, label %deopt look alike, but the first is semantics (the trap is the program's behavior) and the second is a bet (the deopt block continues the same program). Pebble can never turn its checks into guards, because the trap message and the exit status are observable; a Pebble JIT could speculate only on things the language does not observe, such as which function a call reaches after inlining.

References

See the chapter references.