synth_verify/fact_spec.rs
1//! Proof-carrying specialization — VCR-PERF-002 / #494 **Phase 2**: the
2//! single-elision prototype (value-range facts ⇒ dead conditional-branch
3//! elision, the `gust_mix` clamp shape).
4//!
5//! Design source of truth: `docs/design/proof-carrying-specialization.md`
6//! ("How synth consumes facts: the per-elision proof obligation"). loom is the
7//! PROVER (its validator discharged the `wsc.facts` invariants upstream);
8//! synth is a CONDITIONAL optimizer: it never re-derives a fact — it proves
9//! the correctness of its OWN transformation *given* the fact, per elision
10//! site, BEFORE emission, through the ordeal-backed [`BvSolver`]
11//! (certificate-checked pure-Rust QF_BV; every `Unsat` verdict carries an
12//! LRAT proof validated by the trusted `ordeal-lrat` checker before it is
13//! reported).
14//!
15//! # The transformation
16//!
17//! Working on the decoded [`WasmOp`] stream (backend-agnostic — the rewritten
18//! stream feeds whichever selector the driver picks), the pass walks the
19//! function top-level with a symbolic state (stack + locals as QF_BV terms via
20//! the existing [`WasmSemantics`] encoder) and, at every no-`else`
21//! `if … end`, discharges the obligation
22//!
23//! ```text
24//! premise P (every value-range fact reached so far, asserted as a hypothesis)
25//! obligation UNSAT( P ∧ cond ≠ 0 )
26//! ```
27//!
28//! `UNSAT(P ∧ cond ≠ 0)` implies the design doc's
29//! `UNSAT(P ∧ general_lowering(x) ≠ specialized_lowering(x))`: a no-`else`
30//! `if` whose condition is 0 on every P-admissible input never executes its
31//! body, and wasm validation forces a no-`else` `if` blocktype to have
32//! identical param/result types, so the not-taken path is the identity — the
33//! general and specialized lowerings agree on every input P admits. The
34//! stronger query is deliberately used because it is decided in the pure
35//! QF_BV fragment with no control-flow encoding.
36//!
37//! - **UNSAT (certificate-checked)** → the elision is ADMITTED: the
38//! condition-producing op slice (proven pure and contiguous) plus the whole
39//! `if … end` region are deleted; the certificate line is logged per
40//! function (the evidence trail).
41//! - **Sat / Unknown / conflict-budget exceeded / any shape outside the
42//! tracked fragment** → **DECLINE LOUDLY**: the general lowering is
43//! emitted. There is no silent wrong-code path; the conservative fallback
44//! is today's codegen.
45//!
46//! # Soundness of the symbolic tracking (over-approximation discipline)
47//!
48//! * Values produced by ops outside the tracked i32 fragment never enter the
49//! state: the walk STOPS at the first untracked op (no further elisions in
50//! the function; everything already admitted was justified independently).
51//! * Locals are seeded as fresh unconstrained variables (a superset of both
52//! parameter values and the zero-init of non-param locals — sound).
53//! * A DECLINED `if` region may or may not execute: every local it assigns
54//! (at any nesting depth) is havocked to a fresh variable, and its block
55//! results are pushed as fresh variables.
56//! * An ADMITTED `if` region provably never executes, so state is unchanged.
57//! * `div`/`rem` (i32 AND i64) are tracked since Phase 2b (#494
58//! divisor-nonzero), but NEVER deleted: they can trap, and a deleted
59//! condition slice must be effect-free under ALL inputs, not just
60//! P-admissible ones — so a div result always carries `start = None`
61//! (non-erasable) and its value is havocked to a fresh variable. What
62//! Phase 2b adds is per-site TRAP-GUARD elision marks consumed by the
63//! direct selector (see "The div/rem guard obligations" below).
64//!
65//! # The div/rem guard obligations (Phase 2b, #494 divisor-nonzero)
66//!
67//! A `div`/`rem` lowering carries up to TWO trap guards, and they fall to two
68//! INDEPENDENT obligations — this is the #633/#634 two-guard distinction:
69//!
70//! ```text
71//! divide-by-zero guard (div_u/div_s/rem_u/rem_s, i32+i64):
72//! UNSAT( P ∧ divisor == 0 )
73//! INT_MIN/-1 overflow guard (div_s ONLY; rem_s(INT_MIN,-1)==0 never traps):
74//! UNSAT( P ∧ dividend == INT_MIN ∧ divisor == -1 )
75//! ```
76//!
77//! A divisor-nonzero fact (kind 3) discharges the first but NOT the second —
78//! `divisor ≠ 0` does not exclude `divisor == -1`, so the overflow guard is
79//! RETAINED unless the premises independently prove the second obligation
80//! (e.g. a value-range fact `divisor ∈ [1, N]` proves both). Each discharged
81//! obligation becomes a per-site elision mark ([`FactSpecResult::elide_div_zero`]
82//! / [`FactSpecResult::elide_div_ovf`], indices into the RETURNED stream);
83//! the driver threads them to the direct selector, which omits exactly that
84//! guard. Sat / Unknown / no-premise ⇒ loud decline, the guard is emitted.
85//!
86//! # Flag gating
87//!
88//! The driver only invokes this pass when `SYNTH_FACT_SPEC` is set (default
89//! OFF) AND the module carried a parseable `wsc.facts` section. Frozen
90//! fixtures carry no facts section, so every frozen anchor is bit-identical
91//! trivially; with the flag off the pass does not run at all.
92
93use crate::solver::{CheckOutcome, new_solver};
94use crate::term::{BV, Bool};
95use crate::wasm_semantics::WasmSemantics;
96use std::collections::{HashMap, HashSet};
97use synth_core::WasmOp;
98use synth_core::wsc_facts::{FactKind, WscFact};
99
100/// Outcome of specializing one function. `ops`/`block_arity`/`kept` are only
101/// meaningful when [`changed`](Self::changed) — otherwise they echo the input.
102#[derive(Debug)]
103pub struct FactSpecResult {
104 /// The (possibly rewritten) op stream.
105 pub ops: Vec<WasmOp>,
106 /// The blocktype-arity side-table matching `ops` (one entry per
107 /// `Block`/`Loop`/`If` in op order — entries of deleted openers removed).
108 pub block_arity: Vec<(u8, u8)>,
109 /// Indices into the ORIGINAL op stream that were kept, in order. Lets the
110 /// driver filter parallel side-tables (e.g. `op_offsets` for DWARF).
111 pub kept: Vec<usize>,
112 /// One certificate line per ADMITTED elision (logged per function).
113 pub admitted: Vec<String>,
114 /// One line per LOUD DECLINE (the general lowering is emitted for these).
115 pub declined: Vec<String>,
116 /// #494 phase 2b: indices (into the RETURNED `ops` stream) of div/rem
117 /// ops whose divide-by-zero trap guard was certificate-elided
118 /// (`UNSAT(P ∧ divisor == 0)` discharged per site).
119 pub elide_div_zero: Vec<usize>,
120 /// #494 phase 2b: indices (into the RETURNED `ops` stream) of `div_s`
121 /// ops whose `INT_MIN / -1` overflow guard was certificate-elided — a
122 /// SEPARATE obligation (`UNSAT(P ∧ dividend == INT_MIN ∧ divisor == -1)`);
123 /// a divisor-nonzero fact alone never lands here (#633/#634).
124 pub elide_div_ovf: Vec<usize>,
125 /// True when `ops` differs from the input (at least one region deletion).
126 stream_changed: bool,
127}
128
129impl FactSpecResult {
130 /// True when the op STREAM was rewritten (region deletions). Guard-elision
131 /// marks do not rewrite the stream — check
132 /// [`elide_div_zero`](Self::elide_div_zero) /
133 /// [`elide_div_ovf`](Self::elide_div_ovf) separately.
134 pub fn changed(&self) -> bool {
135 self.stream_changed
136 }
137}
138
139/// A symbolic operand-stack slot.
140#[derive(Clone)]
141struct Val {
142 bv: BV,
143 /// Start of the contiguous, side-effect-free op range that produced this
144 /// value — `None` when the producing slice is impure (`local.tee`) or not
145 /// provably contiguous. Only a `Some` slice may be deleted.
146 start: Option<usize>,
147 /// Index of the op that (last) produced this value.
148 created: usize,
149}
150
151/// Specialize one function's op stream against its `wsc.facts` premises.
152///
153/// `block_arity` is the decoder's ordinal side-table (one `(params, results)`
154/// entry per `Block`/`Loop`/`If` in op order); `facts` is the per-function
155/// slice (`CompileConfig::current_func_facts`); `params_i64` is the declared
156/// param-width table (`CompileConfig::current_func_params_i64` — `true` ⇒
157/// param `k` is 64-bit), which fixes the symbolic width of a param
158/// `local.get` (Phase 2b tracks i64 divisors). Total: every input yields a
159/// result — inapplicable shapes surface as loud declines, never errors.
160pub fn specialize_function(
161 func_name: &str,
162 ops: &[WasmOp],
163 block_arity: &[(u8, u8)],
164 facts: &[WscFact],
165 params_i64: &[bool],
166) -> FactSpecResult {
167 let mut pass = Pass::new(func_name, ops, block_arity, facts, params_i64);
168 pass.walk();
169 pass.finish()
170}
171
172/// #494 phase 2b RED-TEAM lever (debug builds ONLY): treat a Sat verdict on
173/// the divide-by-zero guard obligation as an admit anyway. Exists so the
174/// differential oracle can DEMONSTRATE the divergence an unsound admit would
175/// cause (wasmtime traps at divisor == 0, the forced build does not) and then
176/// show the Sat-decline restoring the guard byte-identically. Compiled out of
177/// release builds; every forced admit screams in its certificate line.
178#[cfg(debug_assertions)]
179fn force_admit_unsound() -> bool {
180 std::env::var("SYNTH_FACT_SPEC_FORCE_ADMIT").is_ok_and(|v| v != "0")
181}
182
183#[cfg(not(debug_assertions))]
184fn force_admit_unsound() -> bool {
185 false
186}
187
188struct Pass<'a> {
189 func: &'a str,
190 ops: &'a [WasmOp],
191 block_arity: &'a [(u8, u8)],
192 /// op index → ordinal into `block_arity` (for `Block`/`Loop`/`If` ops).
193 opener_ordinal: HashMap<usize, usize>,
194 /// op index → signed range fact attached to that op's result (raw s64
195 /// bounds; clamped to the value's width at attach time).
196 range_facts: HashMap<usize, (i64, i64)>,
197 /// op indices carrying a divisor-nonzero fact (kind 3): `value ≠ 0`.
198 nonzero_facts: HashSet<usize>,
199 /// Declared param widths (`true` ⇒ 64-bit) — fixes `local.get` widths.
200 params_i64: &'a [bool],
201 sem: WasmSemantics,
202 stack: Vec<Val>,
203 locals: HashMap<u32, BV>,
204 /// Every fresh variable created (name order), for Sat counterexamples.
205 vars: Vec<BV>,
206 fresh: u32,
207 premises: Vec<Bool>,
208 premise_desc: Vec<String>,
209 /// Inclusive op-index ranges to delete (disjoint, ascending).
210 deletions: Vec<(usize, usize)>,
211 admitted: Vec<String>,
212 declined: Vec<String>,
213 /// #494 phase 2b: ORIGINAL op indices marked for zero-guard elision.
214 zero_marks: Vec<usize>,
215 /// #494 phase 2b: ORIGINAL op indices marked for overflow-guard elision.
216 ovf_marks: Vec<usize>,
217}
218
219impl<'a> Pass<'a> {
220 fn new(
221 func: &'a str,
222 ops: &'a [WasmOp],
223 block_arity: &'a [(u8, u8)],
224 facts: &'a [WscFact],
225 params_i64: &'a [bool],
226 ) -> Self {
227 let mut opener_ordinal = HashMap::new();
228 let mut ord = 0usize;
229 for (i, op) in ops.iter().enumerate() {
230 if matches!(op, WasmOp::Block | WasmOp::Loop | WasmOp::If) {
231 opener_ordinal.insert(i, ord);
232 ord += 1;
233 }
234 }
235 let mut range_facts = HashMap::new();
236 let mut nonzero_facts = HashSet::new();
237 for f in facts {
238 // Out-of-range value_id is vacuous (encoding doc's rule).
239 if (f.value_id as usize) >= ops.len() {
240 continue;
241 }
242 match f.kind {
243 FactKind::ValueRange { lo, hi } => {
244 // Raw s64 bounds; clamped to the value's width when the
245 // walk attaches the premise. An inverted bound is vacuous.
246 if lo <= hi {
247 range_facts.insert(f.value_id as usize, (lo, hi));
248 }
249 }
250 // #494 phase 2b: divisor-nonzero (kind 3) — `value ≠ 0`.
251 FactKind::DivisorNonZero => {
252 nonzero_facts.insert(f.value_id as usize);
253 }
254 _ => {}
255 }
256 }
257 Self {
258 func,
259 ops,
260 block_arity,
261 opener_ordinal,
262 range_facts,
263 nonzero_facts,
264 params_i64,
265 // No memory model needed: memory ops are outside the tracked
266 // fragment (the walk stops there).
267 sem: WasmSemantics::new_with_memory(Vec::new()),
268 stack: Vec::new(),
269 locals: HashMap::new(),
270 vars: Vec::new(),
271 fresh: 0,
272 premises: Vec::new(),
273 premise_desc: Vec::new(),
274 deletions: Vec::new(),
275 admitted: Vec::new(),
276 declined: Vec::new(),
277 zero_marks: Vec::new(),
278 ovf_marks: Vec::new(),
279 }
280 }
281
282 fn fresh_var(&mut self, name: String) -> BV {
283 let v = BV::new_const(name, 32);
284 self.vars.push(v.clone());
285 v
286 }
287
288 fn local_bv(&mut self, idx: u32) -> BV {
289 if let Some(bv) = self.locals.get(&idx) {
290 return bv.clone();
291 }
292 // A not-yet-seen local's width comes from the declared param table
293 // (#494 phase 2b tracks i64 divisors); non-param locals default to
294 // 32 bits — an i64 op reading one fails the width check and declines.
295 let width = if self.params_i64.get(idx as usize).copied().unwrap_or(false) {
296 64
297 } else {
298 32
299 };
300 let v = BV::new_const(format!("fs_l{idx}"), width);
301 self.vars.push(v.clone());
302 self.locals.insert(idx, v.clone());
303 v
304 }
305
306 /// Attach the premises of every fact naming op `i`'s result, at the
307 /// value's own width.
308 fn attach_fact(&mut self, i: usize, bv: &BV) {
309 let width = bv.get_size();
310 if let Some(&(lo, hi)) = self.range_facts.get(&i) {
311 // Clamp the s64 bound to the value's width (the phase-2 rule for
312 // 32-bit values; 64-bit values take the bound verbatim). A bound
313 // that inverts after clamping is impossible for a genuine value
314 // of this width — fact validity is loom's obligation (trust
315 // split), so we keep the phase-2 clamp semantics unchanged.
316 let (lo, hi) = if width == 32 {
317 (
318 lo.clamp(i64::from(i32::MIN), i64::from(i32::MAX)),
319 hi.clamp(i64::from(i32::MIN), i64::from(i32::MAX)),
320 )
321 } else {
322 (lo, hi)
323 };
324 let lo_bv = BV::from_i64(lo, width);
325 let hi_bv = BV::from_i64(hi, width);
326 let p = Bool::and(&[&bv.bvsge(&lo_bv), &bv.bvsle(&hi_bv)]);
327 self.premises.push(p);
328 self.premise_desc
329 .push(format!("value(op#{i}) ∈ [{lo}, {hi}] (signed, i{width})"));
330 }
331 if self.nonzero_facts.contains(&i) {
332 // #494 phase 2b: divisor-nonzero (kind 3).
333 let p = bv.ne(BV::from_i64(0, width));
334 self.premises.push(p);
335 self.premise_desc
336 .push(format!("value(op#{i}) ≠ 0 (i{width})"));
337 }
338 }
339
340 fn push(&mut self, bv: BV, start: Option<usize>, created: usize) {
341 self.stack.push(Val { bv, start, created });
342 }
343
344 /// Find the matching `End` for the opener at `i`; also reports whether a
345 /// top-level `Else` occurs. `None` = malformed nesting (stop the walk).
346 fn matching_end(&self, i: usize) -> Option<(usize, bool)> {
347 let mut depth = 0usize;
348 let mut has_else = false;
349 for (j, op) in self.ops.iter().enumerate().skip(i + 1) {
350 match op {
351 WasmOp::Block | WasmOp::Loop | WasmOp::If => depth += 1,
352 WasmOp::Else if depth == 0 => has_else = true,
353 WasmOp::End => {
354 if depth == 0 {
355 return Some((j, has_else));
356 }
357 depth -= 1;
358 }
359 _ => {}
360 }
361 }
362 None
363 }
364
365 /// Continuation after a DECLINED `if` region `[i..=end]`: the body may or
366 /// may not run, so havoc every local it assigns (any depth) and model its
367 /// block results as fresh variables.
368 fn havoc_region(&mut self, i: usize, end: usize, arity: (u8, u8)) {
369 let ops = self.ops;
370 for op in &ops[i + 1..end] {
371 if let WasmOp::LocalSet(idx) | WasmOp::LocalTee(idx) = op {
372 let n = self.fresh;
373 self.fresh += 1;
374 let v = self.fresh_var(format!("fs_h{n}"));
375 self.locals.insert(*idx, v);
376 }
377 }
378 for _ in 0..arity.0 {
379 self.stack.pop();
380 }
381 for k in 0..arity.1 {
382 let n = self.fresh;
383 self.fresh += 1;
384 let v = self.fresh_var(format!("fs_r{n}_{k}"));
385 self.push(v, None, end);
386 }
387 }
388
389 fn decline(&mut self, msg: String) {
390 self.declined
391 .push(format!("{}: {} — general lowering emitted", self.func, msg));
392 }
393
394 /// #494 phase 2b: discharge the per-site div/rem trap-guard obligations
395 /// for the op at `i` (`op_name`, operand width `width`, dividend `a`,
396 /// divisor `b`), recording elision marks for the lowering. TWO independent
397 /// obligations (the #633/#634 two-guard distinction):
398 ///
399 /// - zero guard (every div/rem): `UNSAT(P ∧ divisor == 0)`;
400 /// - overflow guard (`div_s` only): `UNSAT(P ∧ dividend == INT_MIN ∧
401 /// divisor == -1)` — divisor-nonzero alone NEVER discharges this.
402 ///
403 /// Sat / Unknown / no-premise ⇒ loud decline; the guard is emitted.
404 fn try_elide_div_guards(&mut self, i: usize, op_name: &str, is_div_s: bool, a: &Val, b: &Val) {
405 let width = b.bv.get_size();
406 if self.premises.is_empty() {
407 self.decline(format!(
408 "op#{i} {op_name} — no premise reaches this site; both trap guards retained"
409 ));
410 return;
411 }
412 // Obligation 1: the divide-by-zero guard.
413 let mut solver = new_solver();
414 for p in &self.premises {
415 solver.assert(p);
416 }
417 solver.assert(&b.bv.eq(BV::from_i64(0, width)));
418 match solver.check() {
419 CheckOutcome::Unsat => {
420 self.zero_marks.push(i);
421 self.admitted.push(format!(
422 "{}: op#{i} {op_name} — divide-by-zero guard elided: UNSAT(P ∧ divisor == 0) via {} (certificate-checked QF_BV; every Unsat carries an LRAT proof validated by ordeal-lrat); P = {{{}}}; divisor = {}",
423 self.func,
424 solver.name(),
425 self.premise_desc.join(" ∧ "),
426 b.bv,
427 ));
428 }
429 CheckOutcome::Sat => {
430 let cex = self.counterexample(solver.as_ref());
431 if force_admit_unsound() {
432 // RED-TEAM lever (debug builds only): admit the Sat site
433 // anyway so the differential oracle can demonstrate the
434 // divergence. Screams, and still logs the model.
435 self.zero_marks.push(i);
436 self.admitted.push(format!(
437 "{}: op#{i} {op_name} — divide-by-zero guard elided by UNSOUND FORCED ADMIT (SYNTH_FACT_SPEC_FORCE_ADMIT, red-team oracle lever, debug builds only) — obligation was Sat (counterexample: {cex}); NEVER use in production",
438 self.func,
439 ));
440 } else {
441 self.decline(format!(
442 "op#{i} {op_name} — zero-guard obligation Sat (divisor can be 0 under P; counterexample: {cex}); guard retained"
443 ));
444 }
445 }
446 CheckOutcome::Unknown(reason) => {
447 self.decline(format!(
448 "op#{i} {op_name} — zero-guard obligation Unknown ({reason}); conservative decline, guard retained"
449 ));
450 }
451 }
452 // Obligation 2: the INT_MIN/-1 overflow guard — div_s only, and a
453 // SEPARATE proof (#633/#634): divisor ≠ 0 does not exclude -1.
454 if !is_div_s {
455 return;
456 }
457 let int_min = if width == 64 {
458 i64::MIN
459 } else {
460 i64::from(i32::MIN)
461 };
462 let mut solver = new_solver();
463 for p in &self.premises {
464 solver.assert(p);
465 }
466 solver.assert(&a.bv.eq(BV::from_i64(int_min, width)));
467 solver.assert(&b.bv.eq(BV::from_i64(-1, width)));
468 match solver.check() {
469 CheckOutcome::Unsat => {
470 self.ovf_marks.push(i);
471 self.admitted.push(format!(
472 "{}: op#{i} {op_name} — INT{width}_MIN/-1 overflow guard elided: UNSAT(P ∧ dividend == INT{width}_MIN ∧ divisor == -1) via {} (certificate-checked QF_BV; every Unsat carries an LRAT proof validated by ordeal-lrat); P = {{{}}}",
473 self.func,
474 solver.name(),
475 self.premise_desc.join(" ∧ "),
476 ));
477 }
478 CheckOutcome::Sat => {
479 let cex = self.counterexample(solver.as_ref());
480 self.decline(format!(
481 "op#{i} {op_name} — overflow-guard obligation Sat (dividend == INT{width}_MIN with divisor == -1 is possible under P; counterexample: {cex}); the #633 overflow guard is RETAINED — a divisor-nonzero premise alone never elides it"
482 ));
483 }
484 CheckOutcome::Unknown(reason) => {
485 self.decline(format!(
486 "op#{i} {op_name} — overflow-guard obligation Unknown ({reason}); conservative decline, the #633 overflow guard is RETAINED"
487 ));
488 }
489 }
490 }
491
492 /// Read the model back for an actionable counterexample string.
493 fn counterexample(&self, solver: &dyn crate::solver::BvSolver) -> String {
494 let cex: Vec<String> = self
495 .vars
496 .iter()
497 .filter_map(|v| {
498 let name = format!("{v}");
499 solver.value(v).map(|x| {
500 if v.get_size() == 64 {
501 format!("{name}={}", x as u64 as i64)
502 } else {
503 format!("{name}={}", x as u32 as i32)
504 }
505 })
506 })
507 .collect();
508 if cex.is_empty() {
509 "<no model>".to_string()
510 } else {
511 cex.join(", ")
512 }
513 }
514
515 /// Discharge the per-elision obligation for the no-`else` `if` at `i`
516 /// (matching `End` at `end`, condition `cond`). Returns true iff admitted.
517 fn try_elide(&mut self, i: usize, end: usize, cond: &Val) -> bool {
518 if self.premises.is_empty() {
519 self.decline(format!(
520 "op#{i} `if` — no premise reaches this site (no usable value-range fact)"
521 ));
522 return false;
523 }
524 let mut solver = new_solver();
525 for p in &self.premises {
526 solver.assert(p);
527 }
528 let taken = cond.bv.ne(BV::from_i64(0, 32));
529 solver.assert(&taken);
530 match solver.check() {
531 CheckOutcome::Unsat => {
532 let Some(start) = cond.start else {
533 // Proven dead, but the condition slice has a side effect
534 // (`local.tee`) or is not provably contiguous — deleting
535 // it could drop live work. Conservative: keep everything.
536 self.decline(format!(
537 "op#{i} `if` proven dead (UNSAT) but its condition slice is not \
538 erasable (impure or non-contiguous producer)"
539 ));
540 return false;
541 };
542 self.deletions.push((start, end));
543 self.admitted.push(format!(
544 "{}: op#{i} `if` (+condition slice) — ops [{start}..={end}] elided \
545 ({} ops): UNSAT(P ∧ cond ≠ 0) via {} (certificate-checked QF_BV; \
546 every Unsat carries an LRAT proof validated by ordeal-lrat); \
547 P = {{{}}}; cond = {}",
548 self.func,
549 end - start + 1,
550 solver.name(),
551 self.premise_desc.join(" ∧ "),
552 cond.bv,
553 ));
554 true
555 }
556 CheckOutcome::Sat => {
557 // Read the model back for an actionable counterexample.
558 let cex: Vec<String> = self
559 .vars
560 .iter()
561 .filter_map(|v| {
562 let name = format!("{v}");
563 solver
564 .value(v)
565 .map(|x| format!("{name}={}", x as u32 as i32))
566 })
567 .collect();
568 self.decline(format!(
569 "op#{i} `if` — obligation Sat (branch reachable under P; \
570 counterexample: {})",
571 if cex.is_empty() {
572 "<no model>".to_string()
573 } else {
574 cex.join(", ")
575 }
576 ));
577 false
578 }
579 CheckOutcome::Unknown(reason) => {
580 self.decline(format!(
581 "op#{i} `if` — obligation Unknown ({reason}); conservative decline"
582 ));
583 false
584 }
585 }
586 }
587
588 /// Discharge the select-collapse obligation for the branchless `select`
589 /// at op `i`. The operands are `(val1, val2, cond)` in wasm select order
590 /// (`val1` deepest, `cond` on top); the runtime result is
591 /// `(cond != 0) ? val1 : val2`. When a value-range premise pins the
592 /// condition CONSTANT under `P` the select collapses to one operand — the
593 /// branchless sibling of the Phase-2 no-else `if` elision, and the shape
594 /// gust_mix's `clamp` actually uses (`max`/`min` via `select`).
595 ///
596 /// Two mutually exclusive obligations, both certificate-checked QF_BV.
597 /// `UNSAT(P ∧ cond ≠ 0)` means `cond` is always 0, so the result is `val2`
598 /// (delete `val1`'s producer slice plus the condition-slice-through-
599 /// `select`). `UNSAT(P ∧ cond == 0)` means `cond` is always non-zero, so
600 /// the result is `val1` (delete the `val2`+condition+`select` contiguous
601 /// slice). Anything else (Sat both ways = genuinely non-constant; Unknown;
602 /// an impure/non-contiguous erasable slice) DECLINES LOUDLY and the general
603 /// branchless select stands. Returns the surviving operand's `Val` on
604 /// admit, `None` on decline.
605 fn try_collapse_select(&mut self, i: usize, val1: &Val, val2: &Val, cond: &Val) -> Option<Val> {
606 if self.premises.is_empty() {
607 self.decline(format!(
608 "op#{i} select — no premise reaches this site (no usable value-range fact)"
609 ));
610 return None;
611 }
612 // The condition slice must be a pure, contiguous producer ending
613 // immediately before the `select` — otherwise deleting it could drop
614 // live work (`local.tee`) or leave a gap.
615 let Some(sc) = cond.start else {
616 self.decline(format!(
617 "op#{i} select — condition slice is impure or non-contiguous (not erasable)"
618 ));
619 return None;
620 };
621 if cond.created + 1 != i {
622 self.decline(format!(
623 "op#{i} select — condition is not produced immediately before the select \
624 (non-contiguous)"
625 ));
626 return None;
627 }
628
629 // Obligation B first (the clamp shape: the guard condition is
630 // constant-FALSE, so the identity operand `val2` survives).
631 let mut solver = new_solver();
632 for p in &self.premises {
633 solver.assert(p);
634 }
635 solver.assert(&cond.bv.ne(BV::from_i64(0, 32)));
636 match solver.check() {
637 CheckOutcome::Unsat => {
638 // cond ≡ 0 ⇒ result = val2. Delete val1's slice AND the
639 // condition-slice-through-select. val2 (kept) sits between.
640 let Some(s1) = val1.start else {
641 self.decline(format!(
642 "op#{i} select proven false-arm (UNSAT cond ≠ 0) but the val1 slice \
643 is not erasable (impure/non-contiguous) — collapse declined"
644 ));
645 return None;
646 };
647 if val1.created >= sc {
648 self.decline(format!(
649 "op#{i} select — val1 slice overlaps the condition slice; collapse \
650 declined"
651 ));
652 return None;
653 }
654 self.deletions.push((s1, val1.created));
655 self.deletions.push((sc, i));
656 self.admitted.push(format!(
657 "{}: op#{i} select — collapsed to the false-arm (val2): \
658 UNSAT(P ∧ cond ≠ 0) via {} (certificate-checked QF_BV; every Unsat \
659 carries an LRAT proof validated by ordeal-lrat); deleted val1 slice \
660 [{s1}..={}] + condition/select [{sc}..={i}]; P = {{{}}}; cond = {}",
661 self.func,
662 solver.name(),
663 val1.created,
664 self.premise_desc.join(" ∧ "),
665 cond.bv,
666 ));
667 return Some(val2.clone());
668 }
669 CheckOutcome::Sat => { /* cond can be non-zero — try obligation A */ }
670 CheckOutcome::Unknown(reason) => {
671 self.decline(format!(
672 "op#{i} select — false-arm obligation Unknown ({reason}); conservative \
673 decline"
674 ));
675 return None;
676 }
677 }
678
679 // Obligation A: cond ≡ non-zero ⇒ result = val1. Delete the
680 // val2+condition+select contiguous slice.
681 let mut solver = new_solver();
682 for p in &self.premises {
683 solver.assert(p);
684 }
685 solver.assert(&cond.bv.eq(BV::from_i64(0, 32)));
686 match solver.check() {
687 CheckOutcome::Unsat => {
688 let Some(s2) = val2.start else {
689 self.decline(format!(
690 "op#{i} select proven true-arm (UNSAT cond == 0) but the val2 slice \
691 is not erasable (impure/non-contiguous) — collapse declined"
692 ));
693 return None;
694 };
695 if val2.created + 1 != sc {
696 self.decline(format!(
697 "op#{i} select — val2 slice not adjacent to the condition slice \
698 (non-contiguous); collapse declined"
699 ));
700 return None;
701 }
702 // [s2 ..= i] is one contiguous pure range (val2 + cond + select).
703 self.deletions.push((s2, i));
704 self.admitted.push(format!(
705 "{}: op#{i} select — collapsed to the true-arm (val1): \
706 UNSAT(P ∧ cond == 0) via {} (certificate-checked QF_BV; every Unsat \
707 carries an LRAT proof validated by ordeal-lrat); deleted val2/condition/\
708 select [{s2}..={i}]; P = {{{}}}; cond = {}",
709 self.func,
710 solver.name(),
711 self.premise_desc.join(" ∧ "),
712 cond.bv,
713 ));
714 Some(val1.clone())
715 }
716 CheckOutcome::Sat => {
717 let cex = self.counterexample(solver.as_ref());
718 self.decline(format!(
719 "op#{i} select — condition is not constant under P (both arms reachable; \
720 counterexample: {cex}); branchless select retained"
721 ));
722 None
723 }
724 CheckOutcome::Unknown(reason) => {
725 self.decline(format!(
726 "op#{i} select — true-arm obligation Unknown ({reason}); conservative \
727 decline"
728 ));
729 None
730 }
731 }
732 }
733
734 /// #494 Phase 3+: redundant-mask (narrowing) elision. When the value `a`
735 /// is proven narrow enough that `a & b == a` on every P-admissible input
736 /// (`UNSAT(P ∧ (a & b) ≠ a)`), the `i32.and` is the identity — its mask
737 /// operand `b` and the `and` op itself are deleted and `a` flows through
738 /// unchanged. This is the "known-narrow-value ⇒ drop the mask" class: a
739 /// dissolved primitive gives LLVM no range on the value, so it keeps the
740 /// `and`/`uxtb`; the fact makes the mask provably dead. Only the common
741 /// wasm order (`value ; const-mask ; and`, keep `a`) is handled — anything
742 /// else DECLINES LOUDLY and the general `and` stands. Returns the surviving
743 /// operand's `Val` on admit (deletion recorded), `None` on decline.
744 fn try_elide_mask(&mut self, i: usize, a: &Val, b: &Val, result_bv: &BV) -> Option<Val> {
745 if self.premises.is_empty() {
746 self.decline(format!(
747 "op#{i} i32.and — no premise reaches this site (no usable value-range fact)"
748 ));
749 return None;
750 }
751 // The mask operand `b` must be a pure, contiguous producer sitting
752 // immediately between `a`'s slice and the `and` — otherwise deleting
753 // it could drop live work (`local.tee`) or leave a gap.
754 let Some(sb) = b.start else {
755 self.decline(format!(
756 "op#{i} i32.and — mask slice is impure or non-contiguous (not erasable)"
757 ));
758 return None;
759 };
760 if a.created + 1 != sb || b.created + 1 != i {
761 self.decline(format!(
762 "op#{i} i32.and — mask operand is not produced immediately before the and \
763 (non-contiguous)"
764 ));
765 return None;
766 }
767 let mut solver = new_solver();
768 for p in &self.premises {
769 solver.assert(p);
770 }
771 // UNSAT(P ∧ (value & mask) ≠ value) ⇒ the mask never clears a bit of
772 // the value under P ⇒ the `and` is the identity, so the general and
773 // the specialized lowerings (result = value) agree on every P input.
774 solver.assert(&result_bv.ne(&a.bv));
775 match solver.check() {
776 CheckOutcome::Unsat => {
777 self.deletions.push((sb, i));
778 self.admitted.push(format!(
779 "{}: op#{i} i32.and — redundant mask elided (value proven narrow): \
780 UNSAT(P ∧ (value & mask) ≠ value) via {} (certificate-checked QF_BV; \
781 every Unsat carries an LRAT proof validated by ordeal-lrat); deleted \
782 mask/and [{sb}..={i}]; P = {{{}}}; value = {}",
783 self.func,
784 solver.name(),
785 self.premise_desc.join(" ∧ "),
786 a.bv,
787 ));
788 Some(a.clone())
789 }
790 CheckOutcome::Sat => {
791 let cex = self.counterexample(solver.as_ref());
792 self.decline(format!(
793 "op#{i} i32.and — mask is not redundant under P (value can carry a bit \
794 outside the mask; counterexample: {cex}); general and retained"
795 ));
796 None
797 }
798 CheckOutcome::Unknown(reason) => {
799 self.decline(format!(
800 "op#{i} i32.and — mask-redundancy obligation Unknown ({reason}); \
801 conservative decline, general and retained"
802 ));
803 None
804 }
805 }
806 }
807
808 fn walk(&mut self) {
809 if self.range_facts.is_empty() && self.nonzero_facts.is_empty() {
810 self.decline(
811 "no usable value-range or divisor-nonzero fact targets this function".to_string(),
812 );
813 return;
814 }
815 let ops = self.ops;
816 let mut i = 0usize;
817 while i < ops.len() {
818 let op = &ops[i];
819 match op {
820 WasmOp::Nop => {}
821 WasmOp::I32Const(v) => {
822 let bv = self.sem.encode_op(&WasmOp::I32Const(*v), &[]);
823 self.attach_fact(i, &bv);
824 self.push(bv, Some(i), i);
825 }
826 // #494 phase 2b: tracked so an i64 divisor term can be built
827 // (the i64 fragment is const/local/div-rem only — anything
828 // else stops the walk as before).
829 WasmOp::I64Const(v) => {
830 let bv = self.sem.encode_op(&WasmOp::I64Const(*v), &[]);
831 self.attach_fact(i, &bv);
832 self.push(bv, Some(i), i);
833 }
834 WasmOp::LocalGet(idx) => {
835 let bv = self.local_bv(*idx);
836 self.attach_fact(i, &bv);
837 self.push(bv, Some(i), i);
838 }
839 WasmOp::LocalSet(idx) => {
840 let Some(v) = self.stack.pop() else {
841 self.decline(format!("op#{i} local.set on empty symbolic stack"));
842 return;
843 };
844 self.locals.insert(*idx, v.bv);
845 }
846 WasmOp::LocalTee(idx) => {
847 let Some(top) = self.stack.last_mut() else {
848 self.decline(format!("op#{i} local.tee on empty symbolic stack"));
849 return;
850 };
851 // The tee is a side effect: its slice must never be
852 // deleted as a "pure condition producer".
853 top.start = None;
854 top.created = i;
855 let bv = top.bv.clone();
856 self.locals.insert(*idx, bv.clone());
857 self.attach_fact(i, &bv);
858 }
859 WasmOp::Drop => {
860 if self.stack.pop().is_none() {
861 self.decline(format!("op#{i} drop on empty symbolic stack"));
862 return;
863 }
864 }
865 WasmOp::I32Eqz => {
866 let Some(a) = self.stack.pop() else {
867 self.decline(format!("op#{i} unary op on empty symbolic stack"));
868 return;
869 };
870 if a.bv.get_size() != 32 {
871 self.decline(format!("op#{i} i32.eqz on a non-32-bit operand"));
872 return;
873 }
874 let bv = self.sem.encode_op(op, &[a.bv]);
875 self.attach_fact(i, &bv);
876 let start = a.start.filter(|_| a.created + 1 == i);
877 self.push(bv, start, i);
878 }
879 // #494 Phase 3+: `i32.and` — tracked like the other trap-free
880 // binops, but additionally attempts the redundant-mask elision
881 // (a proven-narrow value makes the mask the identity). A
882 // NON-eliding `and` pushes the EXACT `(bv, start, i)` the
883 // general binop arm below produces — so flag-off stays
884 // byte-identical.
885 WasmOp::I32And => {
886 let (Some(b), Some(a)) = (self.stack.pop(), self.stack.pop()) else {
887 self.decline(format!("op#{i} binop on underflowing symbolic stack"));
888 return;
889 };
890 if a.bv.get_size() != 32 || b.bv.get_size() != 32 {
891 self.decline(format!("op#{i} i32 binop on a non-32-bit operand"));
892 return;
893 }
894 let bv = self.sem.encode_op(op, &[a.bv.clone(), b.bv.clone()]);
895 self.attach_fact(i, &bv);
896 // The general binop arm's contiguity proof, verbatim.
897 let start = match (a.start, b.start) {
898 (Some(sa), Some(sb)) if a.created + 1 == sb && b.created + 1 == i => {
899 Some(sa)
900 }
901 _ => None,
902 };
903 match self.try_elide_mask(i, &a, &b, &bv) {
904 // Admitted: the mask/and slice was recorded for
905 // deletion; the surviving value flows through. `start =
906 // None` keeps the collapsed result out of any later
907 // erasable slice (conservative, like select-collapse).
908 Some(surviving) => self.push(surviving.bv, None, i),
909 // Declined (loud): the general `and` stands, pushed
910 // exactly as the general binop arm would.
911 None => self.push(bv, start, i),
912 }
913 }
914 // Tracked, trap-free i32 binops (div/rem excluded on purpose:
915 // they can trap, and a deleted slice must be effect-free).
916 WasmOp::I32Add
917 | WasmOp::I32Sub
918 | WasmOp::I32Mul
919 | WasmOp::I32Or
920 | WasmOp::I32Xor
921 | WasmOp::I32Shl
922 | WasmOp::I32ShrS
923 | WasmOp::I32ShrU
924 | WasmOp::I32Rotl
925 | WasmOp::I32Rotr
926 | WasmOp::I32Eq
927 | WasmOp::I32Ne
928 | WasmOp::I32LtS
929 | WasmOp::I32LtU
930 | WasmOp::I32LeS
931 | WasmOp::I32LeU
932 | WasmOp::I32GtS
933 | WasmOp::I32GtU
934 | WasmOp::I32GeS
935 | WasmOp::I32GeU => {
936 let (Some(b), Some(a)) = (self.stack.pop(), self.stack.pop()) else {
937 self.decline(format!("op#{i} binop on underflowing symbolic stack"));
938 return;
939 };
940 if a.bv.get_size() != 32 || b.bv.get_size() != 32 {
941 self.decline(format!("op#{i} i32 binop on a non-32-bit operand"));
942 return;
943 }
944 let bv = self.sem.encode_op(op, &[a.bv, b.bv]);
945 self.attach_fact(i, &bv);
946 // Contiguity proof for the combined producer slice:
947 // a's slice, immediately followed by b's, immediately
948 // followed by this op. Anything else ⇒ not erasable.
949 let start = match (a.start, b.start) {
950 (Some(sa), Some(sb)) if a.created + 1 == sb && b.created + 1 == i => {
951 Some(sa)
952 }
953 _ => None,
954 };
955 self.push(bv, start, i);
956 }
957 // #494 phase 2b: i32/i64 div/rem — TRACKED (upgrading the
958 // phase-2 hard stop), never DELETED. The op can trap, so its
959 // result carries `start = None` (it can never sit inside an
960 // erasable condition slice); the walk instead discharges the
961 // per-site guard obligations (see the module docs' two-guard
962 // distinction) and marks the op for the lowering. Downstream
963 // soundness: if the op traps, nothing after it executes (any
964 // later admitted elision is vacuous on that path); if it does
965 // not, its result is havocked to a fresh variable.
966 WasmOp::I32DivU
967 | WasmOp::I32DivS
968 | WasmOp::I32RemU
969 | WasmOp::I32RemS
970 | WasmOp::I64DivU
971 | WasmOp::I64DivS
972 | WasmOp::I64RemU
973 | WasmOp::I64RemS => {
974 let (Some(b), Some(a)) = (self.stack.pop(), self.stack.pop()) else {
975 self.decline(format!("op#{i} div/rem on underflowing symbolic stack"));
976 return;
977 };
978 let (op_name, expect, is_div_s) = match op {
979 WasmOp::I32DivU => ("i32.div_u", 32, false),
980 WasmOp::I32DivS => ("i32.div_s", 32, true),
981 WasmOp::I32RemU => ("i32.rem_u", 32, false),
982 WasmOp::I32RemS => ("i32.rem_s", 32, false),
983 WasmOp::I64DivU => ("i64.div_u", 64, false),
984 WasmOp::I64DivS => ("i64.div_s", 64, true),
985 WasmOp::I64RemU => ("i64.rem_u", 64, false),
986 _ => ("i64.rem_s", 64, false),
987 };
988 if a.bv.get_size() != expect || b.bv.get_size() != expect {
989 self.decline(format!(
990 "op#{i} {op_name} on operands of unexpected width (symbolic widths {}/{}, expected {expect})",
991 a.bv.get_size(),
992 b.bv.get_size()
993 ));
994 return;
995 }
996 self.try_elide_div_guards(i, op_name, is_div_s, &a, &b);
997 // Havoc the result; `start = None` keeps a possibly-
998 // trapping op out of every erasable condition slice.
999 let n = self.fresh;
1000 self.fresh += 1;
1001 let v = self.fresh_var(format!("fs_d{n}"));
1002 self.attach_fact(i, &v);
1003 self.push(v, None, i);
1004 }
1005 WasmOp::If => {
1006 let Some(cond) = self.stack.pop() else {
1007 self.decline(format!("op#{i} `if` on empty symbolic stack"));
1008 return;
1009 };
1010 if cond.bv.get_size() != 32 {
1011 self.decline(format!("op#{i} `if` condition is not 32-bit"));
1012 return;
1013 }
1014 let Some((end, has_else)) = self.matching_end(i) else {
1015 self.decline(format!("op#{i} `if` without matching `end`"));
1016 return;
1017 };
1018 let Some(&ord) = self.opener_ordinal.get(&i) else {
1019 self.decline(format!("op#{i} `if` missing from the opener ordinal map"));
1020 return;
1021 };
1022 let Some(&arity) = self.block_arity.get(ord) else {
1023 self.decline(format!(
1024 "op#{i} `if` has no block_arity entry (side-table desync)"
1025 ));
1026 return;
1027 };
1028 if has_else {
1029 self.decline(format!(
1030 "op#{i} `if`/`else` — only no-else `if` is in Phase-2 scope"
1031 ));
1032 self.havoc_region(i, end, arity);
1033 } else if self.try_elide(i, end, &cond) {
1034 // Region provably never executes: state unchanged
1035 // (params-as-results pass-through is the identity for
1036 // a no-else `if`, whose blocktype has equal
1037 // param/result types by wasm validation).
1038 } else {
1039 self.havoc_region(i, end, arity);
1040 }
1041 i = end + 1;
1042 continue;
1043 }
1044 // #494 Phase 3: branchless `select` — the sibling of the
1045 // Phase-2 no-else `if` elision, and the shape gust_mix's
1046 // clamp actually lowers to (`max`/`min` via select). A
1047 // value-range premise that pins the condition constant
1048 // collapses it to one operand (stream deletion, like `if`).
1049 WasmOp::Select => {
1050 let (Some(cond), Some(val2), Some(val1)) =
1051 (self.stack.pop(), self.stack.pop(), self.stack.pop())
1052 else {
1053 self.decline(format!("op#{i} select on underflowing symbolic stack"));
1054 return;
1055 };
1056 // Only the plain i32 `select` (0x1B) is tracked; a typed
1057 // select over i64/f-operands declines and havocs.
1058 if cond.bv.get_size() != 32
1059 || val1.bv.get_size() != 32
1060 || val2.bv.get_size() != 32
1061 {
1062 self.decline(format!(
1063 "op#{i} select on non-32-bit operand(s) — only i32 select is tracked"
1064 ));
1065 let v = self.fresh_var(format!("fs_sel{i}"));
1066 self.push(v, None, i);
1067 i += 1;
1068 continue;
1069 }
1070 match self.try_collapse_select(i, &val1, &val2, &cond) {
1071 // Admitted: the surviving operand's producer slice
1072 // stays; the other operand + condition slice + the
1073 // `select` were recorded for deletion. `start = None`
1074 // keeps the collapsed result out of any later erasable
1075 // slice (conservative).
1076 Some(surviving) => self.push(surviving.bv, None, i),
1077 // Declined (loud): the branchless select stands. Havoc
1078 // the result — a fresh var means any obligation over it
1079 // downstream is Sat, so it can never seed an unsound
1080 // chained collapse.
1081 None => {
1082 let v = self.fresh_var(format!("fs_sel{i}"));
1083 self.push(v, None, i);
1084 }
1085 }
1086 }
1087 // Function-final `End` (top-level): done.
1088 WasmOp::End => break,
1089 WasmOp::Return => break,
1090 other => {
1091 // First op outside the tracked fragment: stop. Everything
1092 // already admitted was justified independently of what
1093 // follows; declining the REST loudly keeps honesty.
1094 self.decline(format!(
1095 "op#{i} {other:?} is outside the tracked i32 fragment — \
1096 fact tracking stops here (no further elisions in this function)"
1097 ));
1098 return;
1099 }
1100 }
1101 i += 1;
1102 }
1103 }
1104
1105 fn finish(self) -> FactSpecResult {
1106 let Pass {
1107 ops,
1108 block_arity,
1109 deletions,
1110 admitted,
1111 declined,
1112 zero_marks,
1113 ovf_marks,
1114 ..
1115 } = self;
1116 if deletions.is_empty() {
1117 return FactSpecResult {
1118 ops: ops.to_vec(),
1119 block_arity: block_arity.to_vec(),
1120 kept: (0..ops.len()).collect(),
1121 admitted,
1122 declined,
1123 // No rewrite ⇒ original indices ARE the output indices.
1124 elide_div_zero: zero_marks,
1125 elide_div_ovf: ovf_marks,
1126 stream_changed: false,
1127 };
1128 }
1129 let deleted = |i: usize| deletions.iter().any(|&(s, e)| i >= s && i <= e);
1130 let mut out_ops = Vec::with_capacity(ops.len());
1131 let mut out_arity = Vec::with_capacity(block_arity.len());
1132 let mut kept = Vec::with_capacity(ops.len());
1133 let mut ord = 0usize;
1134 for (i, op) in ops.iter().enumerate() {
1135 let is_opener = matches!(op, WasmOp::Block | WasmOp::Loop | WasmOp::If);
1136 if !deleted(i) {
1137 out_ops.push(op.clone());
1138 kept.push(i);
1139 if is_opener && let Some(&a) = block_arity.get(ord) {
1140 out_arity.push(a);
1141 }
1142 }
1143 if is_opener {
1144 ord += 1;
1145 }
1146 }
1147 // Remap the guard-elision marks into the REWRITTEN index space. A
1148 // marked div/rem can never sit inside a deleted range (deleted ranges
1149 // are contiguous PURE condition slices plus proven-dead `if` regions
1150 // the walk skipped over; a div result's `start = None` bars it from
1151 // any erasable slice) — the filter below is defense in depth.
1152 let remap = |marks: Vec<usize>| -> Vec<usize> {
1153 marks
1154 .into_iter()
1155 .filter_map(|m| {
1156 debug_assert!(!deleted(m), "guard mark op#{m} inside a deleted range");
1157 kept.binary_search(&m).ok()
1158 })
1159 .collect()
1160 };
1161 FactSpecResult {
1162 ops: out_ops,
1163 block_arity: out_arity,
1164 elide_div_zero: remap(zero_marks),
1165 elide_div_ovf: remap(ovf_marks),
1166 kept,
1167 admitted,
1168 declined,
1169 stream_changed: true,
1170 }
1171 }
1172}
1173
1174#[cfg(test)]
1175mod tests {
1176 use super::*;
1177 use WasmOp::*;
1178
1179 fn fact(value_id: u32, lo: i64, hi: i64) -> WscFact {
1180 WscFact {
1181 func_index: 0,
1182 value_id,
1183 kind: FactKind::ValueRange { lo, hi },
1184 }
1185 }
1186
1187 /// The gust_mix clamp shape: clamp(ch + 476, 1000, 2000) via two
1188 /// no-else `if`s over a local.
1189 fn clamp_ops() -> Vec<WasmOp> {
1190 vec![
1191 LocalGet(0), // 0 ch ← fact target
1192 I32Const(476), // 1
1193 I32Add, // 2 v = ch+476
1194 LocalSet(1), // 3
1195 LocalGet(1), // 4
1196 I32Const(1000), // 5
1197 I32LtS, // 6
1198 If, // 7
1199 I32Const(1000), // 8
1200 LocalSet(1), // 9
1201 End, // 10
1202 LocalGet(1), // 11
1203 I32Const(2000), // 12
1204 I32GtS, // 13
1205 If, // 14
1206 I32Const(2000), // 15
1207 LocalSet(1), // 16
1208 End, // 17
1209 LocalGet(1), // 18
1210 End, // 19
1211 ]
1212 }
1213
1214 const CLAMP_ARITY: &[(u8, u8)] = &[(0, 0), (0, 0)];
1215
1216 #[test]
1217 fn clamp_shape_elides_both_branches_under_the_proven_bound_494() {
1218 let ops = clamp_ops();
1219 let r = specialize_function("gust_mix", &ops, CLAMP_ARITY, &[fact(0, 524, 1524)], &[]);
1220 assert_eq!(r.admitted.len(), 2, "declines: {:?}", r.declined);
1221 assert!(r.changed());
1222 assert_eq!(
1223 r.ops,
1224 vec![
1225 LocalGet(0),
1226 I32Const(476),
1227 I32Add,
1228 LocalSet(1),
1229 LocalGet(1),
1230 End
1231 ],
1232 "both clamp comparisons + branches + bodies must be gone"
1233 );
1234 assert_eq!(r.block_arity, vec![], "both If arity entries removed");
1235 assert_eq!(r.kept, vec![0, 1, 2, 3, 18, 19]);
1236 // The certificate evidence trail names the engine and the premise.
1237 for line in &r.admitted {
1238 assert!(line.contains("UNSAT"), "{line}");
1239 assert!(line.contains("certificate-checked"), "{line}");
1240 assert!(line.contains("[524, 1524]"), "{line}");
1241 }
1242 }
1243
1244 #[test]
1245 fn wrong_wide_bound_is_sat_and_declines_loudly_494() {
1246 // ch ∈ [0, 4000] does NOT make the clamp dead (ch=0 → v=476 < 1000):
1247 // the obligation is Sat and BOTH sites decline with a counterexample.
1248 let ops = clamp_ops();
1249 let r = specialize_function("gust_mix", &ops, CLAMP_ARITY, &[fact(0, 0, 4000)], &[]);
1250 assert_eq!(r.admitted.len(), 0);
1251 assert!(!r.changed());
1252 assert_eq!(r.ops, ops, "declined ⇒ byte-identical op stream");
1253 assert_eq!(r.block_arity, CLAMP_ARITY.to_vec());
1254 assert!(
1255 r.declined
1256 .iter()
1257 .any(|d| d.contains("Sat") && d.contains("counterexample")),
1258 "declines must be loud and carry a model: {:?}",
1259 r.declined
1260 );
1261 }
1262
1263 #[test]
1264 fn partially_dead_bound_elides_only_the_proven_branch_494() {
1265 // ch ∈ [524, 4000]: v ≥ 1000 so the LOW clamp is dead, but v can
1266 // exceed 2000 so the HIGH clamp must survive.
1267 let ops = clamp_ops();
1268 let r = specialize_function("gust_mix", &ops, CLAMP_ARITY, &[fact(0, 524, 4000)], &[]);
1269 assert_eq!(r.admitted.len(), 1, "declines: {:?}", r.declined);
1270 assert_eq!(r.declined.len(), 1);
1271 assert_eq!(
1272 r.ops,
1273 vec![
1274 LocalGet(0),
1275 I32Const(476),
1276 I32Add,
1277 LocalSet(1),
1278 LocalGet(1),
1279 I32Const(2000),
1280 I32GtS,
1281 If,
1282 I32Const(2000),
1283 LocalSet(1),
1284 End,
1285 LocalGet(1),
1286 End,
1287 ]
1288 );
1289 assert_eq!(r.block_arity, vec![(0, 0)], "one If survives");
1290 }
1291
1292 #[test]
1293 fn no_facts_changes_nothing_494() {
1294 let ops = clamp_ops();
1295 let r = specialize_function("gust_mix", &ops, CLAMP_ARITY, &[], &[]);
1296 assert!(!r.changed());
1297 assert_eq!(r.ops, ops);
1298 assert!(!r.declined.is_empty(), "the no-fact case is a loud decline");
1299 }
1300
1301 // ---- #494 Phase 3: branchless select-collapse ----
1302
1303 /// gust_mix's clamp lowered branchlessly via `select` (the shape LLVM
1304 /// emits): `max(v,1000)` = `(v<1000)?1000:v`, `min(v,2000)` =
1305 /// `(v>2000)?2000:v`. No `If`/`End` — no block_arity entries.
1306 fn select_clamp_ops() -> Vec<WasmOp> {
1307 vec![
1308 LocalGet(0), // 0 ch ← fact target
1309 I32Const(476), // 1
1310 I32Add, // 2 v = ch+476
1311 LocalSet(1), // 3
1312 I32Const(1000), // 4 val1 (low clamp)
1313 LocalGet(1), // 5 val2 = v
1314 LocalGet(1), // 6 cond slice
1315 I32Const(1000), // 7
1316 I32LtS, // 8 cond = v < 1000
1317 Select, // 9 → max(v,1000)
1318 LocalSet(1), // 10
1319 I32Const(2000), // 11 val1 (high clamp)
1320 LocalGet(1), // 12 val2 = v
1321 LocalGet(1), // 13 cond slice
1322 I32Const(2000), // 14
1323 I32GtS, // 15 cond = v > 2000
1324 Select, // 16 → min(v,2000) = result
1325 End, // 17
1326 ]
1327 }
1328
1329 #[test]
1330 fn select_clamp_collapses_both_selects_under_the_proven_bound_494() {
1331 let ops = select_clamp_ops();
1332 let r = specialize_function("gust_mix", &ops, &[], &[fact(0, 524, 1524)], &[]);
1333 assert_eq!(r.admitted.len(), 2, "declines: {:?}", r.declined);
1334 assert!(r.changed());
1335 assert_eq!(
1336 r.ops,
1337 vec![
1338 LocalGet(0),
1339 I32Const(476),
1340 I32Add,
1341 LocalSet(1),
1342 LocalGet(1), // val2 of select 1 (identity survives)
1343 LocalSet(1),
1344 LocalGet(1), // val2 of select 2 (identity survives)
1345 End,
1346 ],
1347 "both branchless clamps must collapse to the identity operand"
1348 );
1349 assert_eq!(r.kept, vec![0, 1, 2, 3, 5, 10, 12, 17]);
1350 for line in &r.admitted {
1351 assert!(line.contains("UNSAT"), "{line}");
1352 assert!(line.contains("certificate-checked"), "{line}");
1353 assert!(line.contains("select"), "{line}");
1354 assert!(line.contains("[524, 1524]"), "{line}");
1355 }
1356 }
1357
1358 #[test]
1359 fn select_clamp_wrong_bound_is_sat_and_declines_byte_identically_494() {
1360 // ch ∈ [0, 4000]: ch=0 → v=476 < 1000 so the low clamp genuinely
1361 // fires; both selects are non-constant ⇒ loud Sat decline, no rewrite.
1362 let ops = select_clamp_ops();
1363 let r = specialize_function("gust_mix", &ops, &[], &[fact(0, 0, 4000)], &[]);
1364 assert_eq!(r.admitted.len(), 0);
1365 assert!(!r.changed());
1366 assert_eq!(r.ops, ops, "declined ⇒ byte-identical op stream");
1367 assert!(
1368 r.declined
1369 .iter()
1370 .any(|d| d.contains("not constant") && d.contains("counterexample")),
1371 "declines must be loud and carry a model: {:?}",
1372 r.declined
1373 );
1374 }
1375
1376 #[test]
1377 fn select_collapses_to_true_arm_when_condition_proven_nonzero_494() {
1378 // result = cond ? val1 : val2 with cond ≡ 1 (fact ∈ [1,1]) ⇒ keep val1.
1379 let ops = vec![
1380 I32Const(111), // 0 val1
1381 I32Const(222), // 1 val2
1382 LocalGet(0), // 2 cond ← fact ∈ [1,1] (always non-zero)
1383 Select, // 3 → val1
1384 End, // 4
1385 ];
1386 let r = specialize_function("f", &ops, &[], &[fact(2, 1, 1)], &[]);
1387 assert_eq!(r.admitted.len(), 1, "declines: {:?}", r.declined);
1388 assert_eq!(r.ops, vec![I32Const(111), End]);
1389 assert!(
1390 r.admitted[0].contains("true-arm") && r.admitted[0].contains("cond == 0"),
1391 "{}",
1392 r.admitted[0]
1393 );
1394 }
1395
1396 #[test]
1397 fn select_without_constraining_premise_declines_no_false_collapse_494() {
1398 // A TRUE ValueRange fact exists (so the walk runs) but targets val1,
1399 // not the condition; the select's condition carries no premise ⇒
1400 // non-constant ⇒ Sat decline, byte-identical.
1401 let ops = vec![
1402 I32Const(111), // 0 val1 ← fact ∈ [111,111] (true, non-constraining)
1403 I32Const(222), // 1 val2
1404 LocalGet(0), // 2 cond — unconstrained
1405 Select, // 3
1406 End, // 4
1407 ];
1408 let r = specialize_function("f", &ops, &[], &[fact(0, 111, 111)], &[]);
1409 assert_eq!(r.admitted.len(), 0);
1410 assert!(!r.changed());
1411 assert_eq!(r.ops, ops);
1412 }
1413
1414 #[test]
1415 fn declined_if_havocs_its_locals_no_false_admit_downstream_494() {
1416 // The FIRST if is undecidable (condition on an unconstrained local),
1417 // and its body rewrites local 1 — so the SECOND if (which would be
1418 // dead under the fact alone) must NOT be admitted: local 1 is
1419 // havocked by the declined region.
1420 let ops = vec![
1421 LocalGet(0), // 0 ← fact ch ∈ [524, 1524]
1422 I32Const(476), // 1
1423 I32Add, // 2
1424 LocalSet(1), // 3
1425 LocalGet(2), // 4 unconstrained
1426 If, // 5
1427 I32Const(-9), // 6
1428 LocalSet(1), // 7 havocs local 1
1429 End, // 8
1430 LocalGet(1), // 9
1431 I32Const(2000), // 10
1432 I32GtS, // 11
1433 If, // 12
1434 I32Const(2000), // 13
1435 LocalSet(1), // 14
1436 End, // 15
1437 LocalGet(1), // 16
1438 End, // 17
1439 ];
1440 let r = specialize_function("f", &ops, CLAMP_ARITY, &[fact(0, 524, 1524)], &[]);
1441 assert_eq!(
1442 r.admitted.len(),
1443 0,
1444 "havocked local must block the downstream elision: {:?}",
1445 r.admitted
1446 );
1447 assert_eq!(r.ops, ops);
1448 }
1449
1450 #[test]
1451 fn if_with_else_declines_494() {
1452 let ops = vec![
1453 LocalGet(0), // 0 ← fact forces cond = 0
1454 If, // 1
1455 I32Const(1), // 2
1456 LocalSet(1), // 3
1457 Else, // 4
1458 I32Const(2), // 5
1459 LocalSet(1), // 6
1460 End, // 7
1461 LocalGet(1), // 8
1462 End, // 9
1463 ];
1464 let r = specialize_function("f", &ops, &[(0, 0)], &[fact(0, 0, 0)], &[]);
1465 assert_eq!(r.admitted.len(), 0);
1466 assert!(
1467 r.declined.iter().any(|d| d.contains("else")),
1468 "{:?}",
1469 r.declined
1470 );
1471 assert_eq!(r.ops, ops);
1472 }
1473
1474 #[test]
1475 fn nested_opener_inside_elided_body_fixes_block_arity_ordinals_494() {
1476 // A dead outer if contains a nested if: BOTH arity entries vanish and
1477 // the SURVIVING later block keeps its (translated) entry.
1478 let ops = vec![
1479 LocalGet(0), // 0 ← fact [5,5] ⇒ eqz = 0
1480 I32Eqz, // 1
1481 If, // 2 (ordinal 0)
1482 LocalGet(0), // 3
1483 If, // 4 (ordinal 1, nested)
1484 I32Const(7), // 5
1485 LocalSet(1), // 6
1486 End, // 7
1487 End, // 8
1488 Block, // 9 (ordinal 2, survives)
1489 End, // 10
1490 End, // 11
1491 ];
1492 let arity = &[(0, 0), (0, 0), (0, 1)];
1493 let r = specialize_function("f", &ops, arity, &[fact(0, 5, 5)], &[]);
1494 assert_eq!(r.admitted.len(), 1, "declines: {:?}", r.declined);
1495 // The condition slice starts at op 0 (LocalGet feeds the eqz), so the
1496 // whole deleted range is [0..=8]; only the trailing block survives.
1497 assert_eq!(r.ops, vec![Block, End, End]);
1498 assert_eq!(r.kept, vec![9, 10, 11]);
1499 assert_eq!(
1500 r.block_arity,
1501 vec![(0, 1)],
1502 "only the surviving Block's entry"
1503 );
1504 }
1505
1506 #[test]
1507 fn tee_condition_slice_is_not_erasable_494() {
1508 // cond built through local.tee: proven dead, but deleting the slice
1509 // would lose the local write ⇒ decline (loud), stream unchanged.
1510 let ops = vec![
1511 LocalGet(0), // 0 ← fact [1,1]
1512 LocalTee(1), // 1 side effect in the slice
1513 I32Eqz, // 2 = 0 under the fact
1514 If, // 3
1515 I32Const(9), // 4
1516 LocalSet(2), // 5
1517 End, // 6
1518 End, // 7
1519 ];
1520 let r = specialize_function("f", &ops, &[(0, 0)], &[fact(0, 1, 1)], &[]);
1521 assert_eq!(r.admitted.len(), 0);
1522 assert!(
1523 r.declined
1524 .iter()
1525 .any(|d| d.contains("not") && d.contains("erasable")),
1526 "{:?}",
1527 r.declined
1528 );
1529 assert_eq!(r.ops, ops);
1530 }
1531
1532 #[test]
1533 fn untracked_op_stops_tracking_loudly_494() {
1534 let ops = vec![
1535 LocalGet(0), // 0 ← fact
1536 I64ExtendI32S, // 1 untracked ⇒ stop
1537 Drop, // 2
1538 End, // 3
1539 ];
1540 let r = specialize_function("f", &ops, &[], &[fact(0, 1, 2)], &[]);
1541 assert!(!r.changed());
1542 assert!(
1543 r.declined.iter().any(|d| d.contains("outside the tracked")),
1544 "{:?}",
1545 r.declined
1546 );
1547 }
1548
1549 fn nonzero_fact(value_id: u32) -> WscFact {
1550 WscFact {
1551 func_index: 0,
1552 value_id,
1553 kind: FactKind::DivisorNonZero,
1554 }
1555 }
1556
1557 // ================= #494 phase 2b: div/rem trap-guard elision =================
1558
1559 #[test]
1560 fn divisor_range_excluding_zero_elides_zero_guard_all_rem_div_494() {
1561 // div_u, rem_u, rem_s by a param divisor proven ∈ [1, 100]: every
1562 // zero guard falls to UNSAT(P ∧ divisor == 0); the stream itself is
1563 // untouched (marks only).
1564 let ops = vec![
1565 LocalGet(0), // 0 n
1566 LocalGet(1), // 1 d ← fact [1,100]
1567 I32DivU, // 2 → zero mark
1568 Drop, // 3
1569 LocalGet(0), // 4
1570 LocalGet(1), // 5 ← fact [1,100]
1571 I32RemU, // 6 → zero mark
1572 Drop, // 7
1573 LocalGet(0), // 8
1574 LocalGet(1), // 9 ← fact [1,100]
1575 I32RemS, // 10 → zero mark
1576 End, // 11
1577 ];
1578 let facts = [fact(1, 1, 100), fact(5, 1, 100), fact(9, 1, 100)];
1579 let r = specialize_function("f", &ops, &[], &facts, &[]);
1580 assert_eq!(
1581 r.elide_div_zero,
1582 vec![2, 6, 10],
1583 "declines: {:?}",
1584 r.declined
1585 );
1586 assert_eq!(
1587 r.elide_div_ovf,
1588 Vec::<usize>::new(),
1589 "no div_s in the stream"
1590 );
1591 assert!(!r.changed(), "guard marks never rewrite the op stream");
1592 assert_eq!(r.ops, ops);
1593 assert_eq!(r.admitted.len(), 3);
1594 for line in &r.admitted {
1595 assert!(line.contains("divide-by-zero guard elided"), "{line}");
1596 assert!(line.contains("UNSAT(P ∧ divisor == 0)"), "{line}");
1597 assert!(line.contains("certificate-checked"), "{line}");
1598 }
1599 }
1600
1601 #[test]
1602 fn nonzero_fact_elides_zero_guard_but_retains_div_s_overflow_guard_494() {
1603 // THE TWO-GUARD DISTINCTION (#633/#634): a divisor-nonzero fact (kind
1604 // 3) discharges UNSAT(P ∧ divisor == 0) but NOT the overflow
1605 // obligation — divisor ≠ 0 still admits divisor == -1 with dividend
1606 // == INT_MIN, so the overflow guard is RETAINED with a loud decline.
1607 let ops = vec![
1608 LocalGet(0), // 0
1609 LocalGet(1), // 1 ← divisor-nonzero fact
1610 I32DivS, // 2
1611 End, // 3
1612 ];
1613 let r = specialize_function("f", &ops, &[], &[nonzero_fact(1)], &[]);
1614 assert_eq!(r.elide_div_zero, vec![2], "declines: {:?}", r.declined);
1615 assert_eq!(
1616 r.elide_div_ovf,
1617 Vec::<usize>::new(),
1618 "divisor ≠ 0 must NOT elide the INT_MIN/-1 overflow guard"
1619 );
1620 assert!(
1621 r.declined
1622 .iter()
1623 .any(|d| d.contains("overflow-guard obligation Sat") && d.contains("RETAINED")),
1624 "{:?}",
1625 r.declined
1626 );
1627 }
1628
1629 #[test]
1630 fn positive_range_discharges_both_div_s_obligations_494() {
1631 // divisor ∈ [1, 100] excludes BOTH 0 and -1 — the two obligations
1632 // are discharged independently and both guards fall.
1633 let ops = vec![LocalGet(0), LocalGet(1), I32DivS, End];
1634 let r = specialize_function("f", &ops, &[], &[fact(1, 1, 100)], &[]);
1635 assert_eq!(r.elide_div_zero, vec![2], "declines: {:?}", r.declined);
1636 assert_eq!(r.elide_div_ovf, vec![2]);
1637 assert_eq!(r.admitted.len(), 2, "one certificate line per obligation");
1638 assert!(
1639 r.admitted
1640 .iter()
1641 .any(|a| a.contains("overflow guard elided")
1642 && a.contains("dividend == INT32_MIN ∧ divisor == -1")),
1643 "{:?}",
1644 r.admitted
1645 );
1646 }
1647
1648 #[test]
1649 fn range_including_zero_is_sat_and_declines_the_zero_guard_494() {
1650 // divisor ∈ [0, 100]: divisor == 0 is P-admissible — the obligation
1651 // is Sat, the decline is loud and carries a model, no mark is set.
1652 let ops = vec![LocalGet(0), LocalGet(1), I32DivU, End];
1653 let r = specialize_function("f", &ops, &[], &[fact(1, 0, 100)], &[]);
1654 assert_eq!(r.elide_div_zero, Vec::<usize>::new());
1655 assert!(
1656 r.declined
1657 .iter()
1658 .any(|d| d.contains("zero-guard obligation Sat") && d.contains("counterexample")),
1659 "{:?}",
1660 r.declined
1661 );
1662 }
1663
1664 #[test]
1665 fn i64_div_s_nonzero_fact_zero_guard_only_overflow_retained_494() {
1666 // Oracle 5 at the pass level: i64.div_s with an i64 param divisor
1667 // carrying a divisor-nonzero fact — the zero guard is proven dead,
1668 // the INT64_MIN/-1 overflow guard (#633/#634) is RETAINED.
1669 let ops = vec![LocalGet(0), LocalGet(1), I64DivS, End];
1670 let r = specialize_function("f", &ops, &[], &[nonzero_fact(1)], &[true, true]);
1671 assert_eq!(r.elide_div_zero, vec![2], "declines: {:?}", r.declined);
1672 assert_eq!(
1673 r.elide_div_ovf,
1674 Vec::<usize>::new(),
1675 "i64 overflow guard retained"
1676 );
1677 assert!(
1678 r.declined.iter().any(|d| d.contains("RETAINED")),
1679 "{:?}",
1680 r.declined
1681 );
1682 }
1683
1684 #[test]
1685 fn i64_div_s_positive_range_discharges_both_obligations_494() {
1686 let ops = vec![LocalGet(0), LocalGet(1), I64DivS, End];
1687 let r = specialize_function("f", &ops, &[], &[fact(1, 1, 1000)], &[true, true]);
1688 assert_eq!(r.elide_div_zero, vec![2], "declines: {:?}", r.declined);
1689 assert_eq!(r.elide_div_ovf, vec![2]);
1690 }
1691
1692 #[test]
1693 fn i64_div_on_undeclared_width_declines_no_marks_494() {
1694 // Without the params_i64 table the divisor local is symbolically
1695 // 32-bit — the width check declines rather than building a
1696 // wrong-width obligation.
1697 let ops = vec![LocalGet(0), LocalGet(1), I64DivU, End];
1698 let r = specialize_function("f", &ops, &[], &[nonzero_fact(1)], &[]);
1699 assert_eq!(r.elide_div_zero, Vec::<usize>::new());
1700 assert!(
1701 r.declined.iter().any(|d| d.contains("unexpected width")),
1702 "{:?}",
1703 r.declined
1704 );
1705 }
1706
1707 #[test]
1708 fn div_with_no_premise_declines_loudly_494() {
1709 // The function carries a fact, but no premise reaches the divisor —
1710 // the obligation cannot even be posed; both guards stay.
1711 let ops = vec![
1712 LocalGet(0), // 0 ← fact on the DIVIDEND, not the divisor
1713 LocalGet(1), // 1 unconstrained divisor
1714 I32DivU, // 2
1715 End, // 3
1716 ];
1717 // A fact on op 0 (the dividend): premises exist but do not constrain
1718 // the divisor — Sat, decline.
1719 let r = specialize_function("f", &ops, &[], &[fact(0, 1, 5)], &[]);
1720 assert_eq!(r.elide_div_zero, Vec::<usize>::new());
1721 assert!(
1722 r.declined
1723 .iter()
1724 .any(|d| d.contains("zero-guard obligation Sat")),
1725 "{:?}",
1726 r.declined
1727 );
1728 }
1729
1730 #[test]
1731 fn guard_marks_are_remapped_through_a_clamp_elision_494() {
1732 // A clamp elision rewrites the stream; a downstream div's mark must
1733 // land on the REWRITTEN index (the driver feeds the rewritten stream
1734 // to the selector, which keys guards by its own op index).
1735 let ops = vec![
1736 LocalGet(0), // 0 ← fact [524, 1524]
1737 I32Const(476), // 1
1738 I32Add, // 2
1739 LocalSet(1), // 3
1740 LocalGet(1), // 4 -+ low clamp (elided 4..=10)
1741 I32Const(1000), // 5 |
1742 I32LtS, // 6 |
1743 If, // 7 |
1744 I32Const(1000), // 8 |
1745 LocalSet(1), // 9 |
1746 End, // 10 -+
1747 LocalGet(1), // 11
1748 LocalGet(0), // 12 divisor = ch ∈ [524, 1524] ⇒ nonzero
1749 I32DivU, // 13 → zero mark (rewritten index 6)
1750 End, // 14
1751 ];
1752 let r = specialize_function("f", &ops, &[(0, 0)], &[fact(0, 524, 1524)], &[]);
1753 assert!(r.changed(), "declines: {:?}", r.declined);
1754 assert_eq!(r.kept, vec![0, 1, 2, 3, 11, 12, 13, 14]);
1755 assert_eq!(
1756 r.ops,
1757 vec![
1758 LocalGet(0),
1759 I32Const(476),
1760 I32Add,
1761 LocalSet(1),
1762 LocalGet(1),
1763 LocalGet(0),
1764 I32DivU,
1765 End
1766 ]
1767 );
1768 assert_eq!(
1769 r.elide_div_zero,
1770 vec![6],
1771 "mark remapped from original op#13 to rewritten op#6"
1772 );
1773 }
1774
1775 // ============ #494 Phase 3+: redundant-mask (narrowing) elision ============
1776
1777 /// A representative dissolved DSP kernel: pack two proven-11-bit lanes,
1778 /// `lo | (hi << 11)`. Both `& 0x7FF` masks are redundant under the lane
1779 /// bounds — LLVM keeps them (no range on the params); the facts drop them.
1780 fn pack_lanes_ops() -> Vec<WasmOp> {
1781 vec![
1782 LocalGet(0), // 0 lo ← fact [0, 2047]
1783 I32Const(0x7FF), // 1
1784 I32And, // 2 lo & 0x7FF (redundant)
1785 LocalGet(1), // 3 hi ← fact [0, 2047]
1786 I32Const(0x7FF), // 4
1787 I32And, // 5 hi & 0x7FF (redundant)
1788 I32Const(11), // 6
1789 I32Shl, // 7 hi << 11
1790 I32Or, // 8 lo | (hi << 11)
1791 End, // 9
1792 ]
1793 }
1794
1795 #[test]
1796 fn narrow_value_elides_redundant_mask_494() {
1797 // lo, hi ∈ [0, 2047] ⇒ `x & 0x7FF == x`: both masks fall to
1798 // UNSAT(P ∧ (value & mask) ≠ value); each deletes its `const;and` pair.
1799 let ops = pack_lanes_ops();
1800 let r = specialize_function(
1801 "gust_kernel",
1802 &ops,
1803 &[],
1804 &[fact(0, 0, 2047), fact(3, 0, 2047)],
1805 &[],
1806 );
1807 assert_eq!(r.admitted.len(), 2, "declines: {:?}", r.declined);
1808 assert!(r.changed());
1809 assert_eq!(
1810 r.ops,
1811 vec![
1812 LocalGet(0), // lo flows through the elided mask
1813 LocalGet(1), // hi flows through the elided mask
1814 I32Const(11),
1815 I32Shl,
1816 I32Or,
1817 End,
1818 ],
1819 "both redundant masks must be gone, the arithmetic intact"
1820 );
1821 assert_eq!(r.kept, vec![0, 3, 6, 7, 8, 9]);
1822 for line in &r.admitted {
1823 assert!(line.contains("UNSAT(P ∧ (value & mask) ≠ value)"), "{line}");
1824 assert!(line.contains("certificate-checked"), "{line}");
1825 assert!(line.contains("redundant mask elided"), "{line}");
1826 }
1827 }
1828
1829 #[test]
1830 fn wide_bound_makes_mask_live_and_declines_byte_identically_494() {
1831 // lo ∈ [0, 0xFFF]: value 0x800 has bit 11 set, OUTSIDE the 0x7FF mask,
1832 // so `x & 0x7FF != x` is Sat — the mask is genuinely live. BOTH sites
1833 // decline loudly with a counterexample; the stream is byte-identical.
1834 let ops = pack_lanes_ops();
1835 let r = specialize_function(
1836 "gust_kernel",
1837 &ops,
1838 &[],
1839 &[fact(0, 0, 0xFFF), fact(3, 0, 0xFFF)],
1840 &[],
1841 );
1842 assert_eq!(r.admitted.len(), 0);
1843 assert!(!r.changed());
1844 assert_eq!(r.ops, ops, "declined ⇒ byte-identical op stream");
1845 assert!(
1846 r.declined
1847 .iter()
1848 .any(|d| d.contains("not redundant") && d.contains("counterexample")),
1849 "declines must be loud and carry a model: {:?}",
1850 r.declined
1851 );
1852 }
1853
1854 #[test]
1855 fn mask_without_constraining_premise_declines_no_false_elision_494() {
1856 // A TRUE ValueRange fact exists (so the walk runs) but targets the mask
1857 // const, not the value; the masked value carries no premise ⇒ the
1858 // obligation is Sat ⇒ loud decline, byte-identical.
1859 let ops = vec![
1860 LocalGet(0), // 0 value — unconstrained
1861 I32Const(0x7FF), // 1 mask ← fact [0x7FF, 0x7FF] (true, non-constraining)
1862 I32And, // 2
1863 End, // 3
1864 ];
1865 let r = specialize_function("f", &ops, &[], &[fact(1, 0x7FF, 0x7FF)], &[]);
1866 assert_eq!(r.admitted.len(), 0);
1867 assert!(!r.changed());
1868 assert_eq!(r.ops, ops);
1869 }
1870
1871 #[test]
1872 fn signed_narrow_bound_that_admits_negative_keeps_the_mask_494() {
1873 // value ∈ [-1, 2047]: -1 is all-ones, so `-1 & 0x7FF = 0x7FF != -1` —
1874 // the obligation is Sat and the mask is (correctly) retained. Guards
1875 // against a naive "hi ≤ mask" shortcut that ignores the sign bit.
1876 let ops = vec![
1877 LocalGet(0), // 0 ← fact [-1, 2047]
1878 I32Const(0x7FF), // 1
1879 I32And, // 2
1880 End, // 3
1881 ];
1882 let r = specialize_function("f", &ops, &[], &[fact(0, -1, 2047)], &[]);
1883 assert_eq!(
1884 r.admitted.len(),
1885 0,
1886 "a negative value fails the mask identity"
1887 );
1888 assert!(!r.changed());
1889 assert_eq!(r.ops, ops);
1890 }
1891
1892 #[test]
1893 fn mask_elision_no_facts_changes_nothing_494() {
1894 let ops = pack_lanes_ops();
1895 let r = specialize_function("gust_kernel", &ops, &[], &[], &[]);
1896 assert!(!r.changed());
1897 assert_eq!(r.ops, ops);
1898 assert!(!r.declined.is_empty(), "the no-fact case is a loud decline");
1899 }
1900
1901 #[test]
1902 fn out_of_range_value_id_is_vacuous_494() {
1903 let ops = clamp_ops();
1904 let r = specialize_function("f", &ops, CLAMP_ARITY, &[fact(999, 524, 1524)], &[]);
1905 assert!(!r.changed());
1906 assert_eq!(r.ops, ops);
1907 }
1908}