Lab 29: Specialized Opcodes (Milestone 14)

Background

You will add type feedback and adaptive specialization: ADD becomes ADD_INT at sites that have only ever seen integers, with a guard and a de-specialization path.

Then you will build a superinstruction — the non-speculative sibling — and compare what each bought.

Why This Lab Matters

This is speculation with a cheap way back, which makes it the right rehearsal for the JIT, where the way back is expensive.
Adaptive matters more than specialized. Without backoff, a polymorphic site thrashes and gets slower.
The correctness rule — fall back freely, differ never — is the same rule the JIT needs.

Prerequisites

Lab 28 complete (or skipped deliberately, with the profile as justification).
Runtime Specialization read.

Predict First

What fraction of your policy benchmark is ADD/LT/MUL? Do their operands have uniform types?
ADD_INT using + instead of wrapping_add — what happens on i64::MAX + 1 in a debug build?
A loop alternating integer and float additions at one site. What happens without backoff?
A superinstruction fusing GET_LOCAL; GET_LOCAL. What guard does it need?
Which will win on your workload: ADD_INT or the superinstruction?

Step 1: The Hypothesis

## Optimization: adaptive specialization of ADD/LT

BASELINE   policy_10k: <ms>;  ADD 7.9% + LT 8.1% + MUL 5.1% = 21.1% of instructions
           Type census (Step 2): <n>% of ADD executions saw (Integer, Integer)

HYPOTHESIS The generic ADD does a 5-way match. If >90% of executions at a given
           site are integer-integer, a specialized ADD_INT reduces that to one
           tag comparison. Expected: 21% of instructions get ~2x cheaper →
           ~8-10% on policy_10k.

PREDICTION <ms>

Step 2: Measure the Feedback First

Before specializing, find out whether sites are actually monomorphic. Specializing a site whose types vary is a pessimization.

#![allow(unused)]
fn main() {
#[cfg(feature = "profile-types")]
self.stats.type_feedback[site].observe(a.tag(), b.tag());
}

$ cargo run --release --features profile-types -- run --stats benches/policy.ember
--- type feedback census ---
site  opcode  (Int,Int)   (Flt,Flt)   (Int,Flt)   other    verdict
0031  ADD     620,331      0           0          0        MONOMORPHIC int
0044  MUL     410,055      0           0          0        MONOMORPHIC int
0052  LT      205,027      205,028     0          0        BIMORPHIC ← would thrash
0088  ADD           0      410,055     0          0        MONOMORPHIC float

Site 0052 is the one to notice. It alternates, and specializing it without backoff would rewrite the instruction on every iteration. The census tells you that before you build anything, which is the whole point of measuring first.

Step 3: The Adaptive Counter

#![allow(unused)]
fn main() {
#[derive(Copy, Clone, Default)]
pub struct Adaptive {
    observed: TypePair,      // what we have been seeing
    count: u16,              // consecutive consistent observations
    warmup: u16,             // threshold; DOUBLES on each failure
    failures: u8,            // give up after N
}

const INITIAL_WARMUP: u16 = 64;
const MAX_FAILURES: u8 = 3;
}

   ADD ──64 consistent──▶ ADD_INT ──guard fails──▶ ADD (warmup ×2, failures+1)
                                         │
                                         └── failures == 3 ──▶ ADD_GENERIC (TERMINAL)

Exponential backoff plus a terminal state is what stops site 0052 from thrashing. Without both, a bimorphic site is slower than never specializing at all — which is the failure mode people ship, because their benchmark happened to be monomorphic.

Step 4: The Specialized Opcodes

#![allow(unused)]
fn main() {
Op::AddInt => {
    let b = self.pop(); let a = self.pop();
    match (a, b) {
        // THE GUARD. One tag comparison instead of a five-way match.
        (Value::Integer(x), Value::Integer(y)) =>
            // wrapping_add, NOT `+`. `+` panics in debug on overflow — the exact
            // bug Lab 3 fixed, reintroduced by an "optimization".
            self.push(Value::Integer(x.wrapping_add(y))),
        // Guard failed: de-specialize and retry generically. Falling back is
        // ALWAYS allowed; producing a different answer never is.
        _ => { self.despecialize(ip); self.push(a); self.push(b); self.retry_generic(ip)?; }
    }
}
}

Four pairs is enough: ADD_INT, ADD_FLOAT, LT_INT, LT_FLOAT. Add more only if the census says so.

Step 5: The Superinstruction (No Guard)

The non-speculative sibling, and worth building for contrast:

$ ember run --stats --profile-pairs benches/policy.ember
--- most common instruction PAIRS ---
  GET_LOCAL, GET_LOCAL      1,020,941
  GET_LOCAL, GET_FIELD        820,110
  GET_FIELD, LOAD_INT         410,055

#![allow(unused)]
fn main() {
// Fused at COMPILE time from a static peephole pass. No feedback, no guard,
// no de-specialization — it assumes nothing about types.
Op::GetLocal2(u8, u8) => {
    let b = self.frame().base;
    self.push(self.stack[b + a as usize]);
    self.push(self.stack[b + c as usize]);
}
}

One dispatch instead of two, and no correctness surface at all. Compare the two optimizations honestly in Step 6: the superinstruction is simpler, safer, and may well win.

Step 6: Measure and Compare

Change	Lines	Correctness surface
Baseline	—	—
+ specialization	~180	a guard, a fallback, backoff
+ superinstructions	~60	none
both

That table is the deliverable, and the interesting column is the last one. If the superinstruction gets 60% of the win for 30% of the code and none of the correctness risk, that is the better engineering — and you would not know without building both.

The Trace

$ ember run --trace-specialize -e '
local s = 0
for i = 1, 200 do s = s + i end
for i = 1, 200 do s = s + i * 1.5 end
return s'

site 0021  ADD   observing (Int,Int)   count=64/64   → SPECIALIZE ADD_INT
site 0021  ADD_INT  hits=136
site 0021  ADD_INT  GUARD FAIL (Int,Float)  → despecialize, warmup 64→128, failures=1
site 0021  ADD   observing (Int,Float) count=128/128 → SPECIALIZE ADD_FLOAT
site 0021  ADD_FLOAT hits=72
--- specialization report ---
  sites specialized: 3   guard failures: 1   terminal: 0

Now the thrashing case, which is what backoff exists for:

$ ember run --trace-specialize -e '
local s = 0
for i = 1, 1000 do
  if i % 2 == 0 then s = s + i else s = s + i * 1.0 end
end
return s'

site 0034  ADD  → ADD_INT      (warmup 64)
site 0034  GUARD FAIL → ADD    (warmup 128, failures=1)
site 0034  ADD  → ADD_FLOAT    (warmup 128)
site 0034  GUARD FAIL → ADD    (warmup 256, failures=2)
site 0034  ADD  → ADD_INT      (warmup 256)
site 0034  GUARD FAIL → ADD    (failures=3) → TERMINAL: ADD_GENERIC
--- specialization report ---
  sites specialized: 1   guard failures: 3   terminal: 1     ← stopped trying

Six transitions and then it stops. Delete the backoff and this site rewrites its instruction ~1,000 times, and the "optimization" makes the loop measurably slower. Run it both ways — this is a five-minute experiment and it is the most persuasive argument for adaptivity you will get.

Expected Output

$ cargo test --test specialization
test specialized_agrees_with_generic_on_every_value_pair ... ok
test add_int_wraps_and_does_not_panic ... ok
test bimorphic_sites_reach_a_terminal_state ... ok
test specialization_does_not_change_program_output ... ok

$ cargo test --test differential
test backends_agree_on_the_whole_corpus ... ok

PREDICTION. Rank the three. By how much is the middle one worse than the first?

RESULT. Record all three in docs/learning/14-performance.md. Then delete the no-backoff flag — you have made the point, and a flag that only exists to be worse is a liability.

Test

#![allow(unused)]
fn main() {
#[test]
fn specialized_agrees_with_generic_on_every_value_pair() {
    // The correctness rule: falling back is ALWAYS allowed, differing NEVER is.
    for (generic, spec) in SPECIALIZATION_PAIRS {
        for (a, b) in interesting_value_pairs() {   // i64::MIN/MAX, NaN, ±0.0, inf, mixed
            match execute_one(spec, a, b) {
                Ok(v) => assert_eq!(v, execute_one(generic, a, b).unwrap(),
                                    "{spec:?} differs from {generic:?} on ({a:?}, {b:?})"),
                Err(Guard) => {}
                Err(e) => panic!("{spec:?} errored where {generic:?} did not: {e:?}"),
            }
        }
    }
}

#[test]
fn add_int_wraps_and_does_not_panic() {
    // Debug builds included — that is the point.
    assert_eq!(run_specialized("return 9223372036854775807 + 1"), "-9223372036854775808");
}

#[test]
fn bimorphic_sites_reach_a_terminal_state() {
    let stats = run_with_spec_stats(
        "local s=0 for i=1,1000 do if i%2==0 then s=s+i else s=s+i*1.0 end end return s");
    assert!(stats.specialization_transitions <= 8,
            "site thrashed: {} transitions", stats.specialization_transitions);
    assert_eq!(stats.terminal_sites, 1);
}

#[test]
fn specialization_does_not_change_program_output() {
    for case in corpus() {
        assert_eq!(run_with_specialization(&case.src), run_without_specialization(&case.src),
                   "{} output changed", case.name);
    }
}

#[test]
fn superinstructions_need_no_guard() {
    // A structural check: GetLocal2 must have no fallback path, because it
    // assumes nothing. If it grew one, it is not a superinstruction any more.
    assert!(!vm_source_for(Op::GetLocal2(0,0)).contains("despecialize"));
}
}

Challenge Extensions

Specialize GET_FIELD by shape, unifying this lab with Lab 28: the cache is the specialization. This is what CPython's LOAD_ATTR_INSTANCE_VALUE does.
ADD_IMM. n + 1 is extremely common. Fold the constant into the instruction, as Lua 5.4's OP_ADDI does. No feedback needed — it is a compile-time peephole.
A superinstruction generator. Profile the corpus, emit the top ten pairs as fused opcodes, and measure. This is the classic Forth/Ertl technique, automated.
Quickening. Replace LOAD_CONST k with LOAD_CONST_INT n when the constant is a small integer, at first execution. No guard, no feedback, one branch removed.
Feed specialization to the JIT. Lab 30's compiled code can read the same feedback and skip the guard where the site is terminal-monomorphic — which is exactly how V8's feedback vectors reach TurboFan.

Deliverables

The hypothesis and predicted number written before measuring.
The type-feedback census, taken before specializing anything, with per-site verdicts.
Adaptive with per-site counters, exponential backoff, and a terminal state.
At least two specialized opcode pairs, using wrapping_* arithmetic.
At least one superinstruction, with the structural test that it has no fallback.
The four-row comparison table, including the correctness-surface column.
--trace-specialize showing transitions, guard failures, and terminal sites.
The backoff experiment, all three configurations, and the no-backoff flag deleted afterwards.
interesting_value_pairs() covering i64::MIN/MAX, NaN, ±0.0, inf, and mixed types.
The instruction-count baseline regenerated deliberately, with the diff read.
Differential tests green.

Validation / Self-check

What did the type census say about your policy's sites? How many were monomorphic?
Why wrapping_add and not +? Which earlier lab is that?
What are the two mechanisms that stop a bimorphic site thrashing? What happened without them?
State the correctness rule for a specialized opcode, and the test that enforces it.
How does a superinstruction differ from a specialization? Which needed fewer lines and which won?
Which three values broke a naive specialized path?
Why must the instruction-count baseline be regenerated deliberately rather than automatically?
If the superinstruction got most of the win with none of the risk, what does that say about which to build first?

Next: Lab 30 — A Cranelift JIT.

Open-Source Engineer & Contributor