//! Random differential fuzzer of the code generators (JITSAFE fix 4): random RIR programs -- //! integer and float arithmetic, loads and stores, calls, counted loops and diamonds, with far //! more values live at once than there are registers -- run through every tier this crate and the //! back end have (baseline and thorough register allocation, the spill-elision and copy-reuse //! knobs off and on, the O2 clean-up passes and the O3 loop passes) and compared with a direct //! RIR evaluator: the result, every memory word, and (MAKEPAD_RUN_OPT=+checkra, on here) the //! register allocation checker. A mismatch prints the seed and the knob set; `FUZZ_SEED=` //! reruns one program, `FUZZ_N=` sets how many (the gate's long run on a node). #![cfg(any(all(target_arch = "x86_64", unix), all(target_arch = "aarch64", unix)))] use relax_backend::{exec::Code, passes, rir::*}; struct Rng(u64); impl Rng { fn next(&mut self) -> u64 { self.0 ^= self.0 << 13; self.0 ^= self.0 >> 7; self.0 ^= self.0 << 17; self.0 } fn below(&mut self, n: u64) -> u64 { self.next() % n.max(1) } fn chance(&mut self, pct: u64) -> bool { self.below(100) < pct } } /// words of the memory buffer: [0, INT_WORDS) integers, [INT_WORDS, WORDS) floats const INT_WORDS: usize = 48; const WORDS: usize = 64; extern "C" fn host2(a: u64, b: u64) -> u64 { a.wrapping_mul(0x9e37_79b9_7f4a_7c15) ^ b.rotate_left(17) } extern "C" fn host6(a: u64, b: u64, c: u64, d: u64, e: u64, f: u64) -> u64 { a.wrapping_add(b.wrapping_mul(3)).wrapping_sub(c) ^ d.rotate_left(5) ^ e.wrapping_mul(f | 1) } const W64: IntTy = IntTy { bits: 64, signed: false }; const TYS: [IntTy; 8] = [I64, U64, I32, U32, IntTy { bits: 8, signed: false }, IntTy { bits: 8, signed: true }, IntTy { bits: 16, signed: false }, IntTy { bits: 16, signed: true }]; const OPS: [IOp; 9] = [IOp::Add, IOp::Sub, IOp::Mul, IOp::And, IOp::Or, IOp::Xor, IOp::Shl, IOp::Shr, IOp::Rotl]; const CONDS: [Cond; 6] = [Cond::Eq, Cond::Ne, Cond::Lt, Cond::Le, Cond::Gt, Cond::Ge]; const FOPS: [FOp; 5] = [FOp::Add, FOp::Sub, FOp::Mul, FOp::Min, FOp::Max]; /// A program builder: structured control flow (so every program ends), values kept live across it. struct Gen<'a> { f: Func, r: &'a mut Rng, mem: VReg, ints: Vec, flts: Vec, cur: u32, host2: VReg, host6: VReg, budget: u32, /// loop counters in scope: read, never redefined (every loop ends) counters: Vec, } impl Gen<'_> { fn i(&mut self, inst: Inst) { let b = &mut self.f.blocks[self.cur as usize]; b.insts.push(inst); b.pos.push(0); } fn int(&mut self) -> VReg { self.ints[self.r.below(self.ints.len() as u64) as usize] } fn flt(&mut self) -> VReg { self.flts[self.r.below(self.flts.len() as u64) as usize] } /// the result register: a fresh value (pressure) or an old one redefined (non-SSA, colouring) fn dst_i(&mut self) -> VReg { if self.r.chance(35) { let v = self.f.vreg(Cls::I); self.ints.push(v); v } else { loop { let v = self.int(); if !self.counters.contains(&v) { return v; } } } } fn dst_f(&mut self) -> VReg { if self.r.chance(30) { let v = self.f.vreg(Cls::F64); self.flts.push(v); v } else { self.flt() } } /// `v` in `ty`'s canonical (extended) form, as lowering keeps every narrow value fn canon(&mut self, v: VReg, ty: IntTy) -> VReg { if ty.bits == 64 { return v; } let c = self.f.vreg(Cls::I); self.i(Inst::Conv(Conv::IntToInt(ty), c, v)); c } /// a condition as lowering makes them: a compare's 0 / 1 fn cond(&mut self) -> VReg { let v = self.int(); let c = self.f.vreg(Cls::I); let k = self.r.below(3) as i64; self.i(Inst::ICmpI(Cond::Gt, false, c, v, k)); c } /// an operation and its type (rotates too in every width and signedness: passes::rotl) fn op_ty(&mut self) -> (IOp, IntTy) { let op = OPS[self.r.below(9) as usize]; (op, TYS[self.r.below(TYS.len() as u64) as usize]) } /// an in-bounds address: mem + 8 * (x & (words - 1)) of a region fn addr(&mut self, float: bool) -> (VReg, i32) { if self.r.chance(50) { let k = if float { INT_WORDS + self.r.below((WORDS - INT_WORDS) as u64) as usize } else { self.r.below(INT_WORDS as u64) as usize }; return (self.mem, 8 * k as i32); } let x = self.int(); let (m, t, a) = (self.f.vreg(Cls::I), self.f.vreg(Cls::I), self.f.vreg(Cls::I)); let (mask, base) = if float { ((WORDS - INT_WORDS) as i64 - 1, INT_WORDS as i64 * 8) } else { (31, 0) }; self.i(Inst::IBinI(IOp::And, W64, m, x, mask)); self.i(Inst::IBinI(IOp::Shl, W64, t, m, 3)); self.i(Inst::IBin(IOp::Add, W64, a, self.mem, t)); (a, base as i32) } fn op(&mut self) { match self.r.below(16) { 0..=3 => { let (a, mut b) = (self.int(), self.int()); let (op, ty) = self.op_ty(); let a = self.canon(a, ty); if !matches!(op, IOp::Shl | IOp::Shr | IOp::Rotl) { b = self.canon(b, ty); } // (shift counts below the width, as lowering makes them: RIR leaves wider ones open; // a rotate takes any count, mod the width) if matches!(op, IOp::Shl | IOp::Shr) { let m = self.f.vreg(Cls::I); self.i(Inst::IBinI(IOp::And, W64, m, b, ty.bits as i64 - 1)); b = m; } let d = self.dst_i(); self.i(Inst::IBin(op, ty, d, a, b)); } 4 | 5 => { let a = self.int(); let (op, ty) = self.op_ty(); let a = self.canon(a, ty); // (an immediate in the type's canonical form, as lowering makes them) let k = if matches!(op, IOp::Shl | IOp::Shr) { self.r.below(ty.bits as u64) as i64 } else if op == IOp::Rotl { self.r.below(200) as i64 } else { passes::fold_ibin(IOp::Add, ty, self.r.below(200) as i64 - 60, 0).unwrap() }; let d = self.dst_i(); self.i(Inst::IBinI(op, ty, d, a, k)); } 6 => { let (a, b) = (self.int(), self.int()); let d = self.dst_i(); let (c, s) = (CONDS[self.r.below(6) as usize], self.r.chance(50)); self.i(Inst::ICmp(c, s, d, a, b)); } 7 => { let c = self.cond(); let (a, b) = (self.int(), self.int()); let d = self.dst_i(); self.i(Inst::Sel(d, c, a, b)); } 8 => { let (a, b) = (self.flt(), self.flt()); let d = self.dst_f(); let op = FOPS[self.r.below(5) as usize]; self.i(Inst::FBin(op, true, d, a, b)); } 9 => { // float -> int (saturating, NaN -> 0) and int -> float if self.r.chance(50) { let a = self.flt(); let d = self.dst_i(); self.i(Inst::Conv(Conv::FToInt(true, I64), d, a)); } else { let a = self.int(); let t = self.f.vreg(Cls::I); self.i(Inst::IBinI(IOp::And, W64, t, a, 0xffff)); let d = self.dst_f(); self.i(Inst::Conv(Conv::IntToF(I64, true), d, t)); } } 10 | 11 => { let float = self.r.chance(25); let (a, off) = self.addr(float); if float { let d = self.dst_f(); self.i(Inst::Load(Mem::F64, d, a, off)); } else { let d = self.dst_i(); let m = [Mem::Int(8, false), Mem::Int(4, true), Mem::Int(1, false), Mem::Int(2, true)][self.r.below(4) as usize]; self.i(Inst::Load(m, d, a, off)); } } 12 | 13 => { let float = self.r.chance(25); let (a, off) = self.addr(float); if float { let v = self.flt(); self.i(Inst::Store(Mem::F64, a, off, v)); } else { let v = self.int(); let m = [Mem::Int(8, false), Mem::Int(4, false), Mem::Int(1, false)][self.r.below(3) as usize]; self.i(Inst::Store(m, a, off, v)); } } 14 => { // a call: every value live across it is saved or in a callee-saved register // (operands chosen before the result: a fresh result is not defined yet) if self.r.chance(50) { let (a, b) = (self.int(), self.int()); let d = self.dst_i(); self.i(Inst::Call(Callee::Indirect(self.host2), vec![a, b], vec![d])); } else { let args: Vec = (0..6).map(|_| self.int()).collect(); let d = self.dst_i(); self.i(Inst::Call(Callee::Indirect(self.host6), args, vec![d])); } } _ => { let a = self.int(); let d = self.dst_i(); self.i(Inst::Mov(d, a)); } } } /// a sequence of statements with nested diamonds and counted loops fn seq(&mut self, depth: u32) { let n = 2 + self.r.below(10); for _ in 0..n { if self.budget == 0 { return; } self.budget -= 1; match self.r.below(10) { 0 if depth < 3 => self.diamond(depth), 1 if depth < 2 => self.lp(depth), _ => self.op(), } } } fn diamond(&mut self, depth: u32) { let c = self.cond(); let (t, e, j) = (self.f.block(), self.f.block(), self.f.block()); self.f.blocks[self.cur as usize].term = Term::Branch(c, t, e); // values first defined in an arm are that arm's (not defined on the other path) let (ni, nf) = (self.ints.len(), self.flts.len()); self.cur = t; self.seq(depth + 1); self.ints.truncate(ni); self.flts.truncate(nf); self.f.blocks[self.cur as usize].term = Term::Jump(j); self.cur = e; if self.r.chance(60) { self.seq(depth + 1); self.ints.truncate(ni); self.flts.truncate(nf); } self.f.blocks[self.cur as usize].term = Term::Jump(j); self.cur = j; } /// for i in 0..n { body } (n <= 7, from a value: some loops run zero times) fn lp(&mut self, depth: u32) { let (i, n, c) = (self.f.vreg(Cls::I), self.f.vreg(Cls::I), self.f.vreg(Cls::I)); let src = self.int(); self.i(Inst::IBinI(IOp::And, W64, n, src, 7)); self.i(Inst::Iconst(i, 0)); let (h, body, exit) = (self.f.block(), self.f.block(), self.f.block()); self.f.blocks[self.cur as usize].term = Term::Jump(h); self.cur = h; self.i(Inst::ICmp(Cond::Lt, false, c, i, n)); self.f.blocks[h as usize].term = Term::Branch(c, body, exit); self.cur = body; // the counter is readable in the body let (ni, nf) = (self.ints.len(), self.flts.len()); self.ints.push(i); self.counters.push(i); self.seq(depth + 1); self.counters.pop(); // (the body may run zero times: what it first defines is not defined after the loop) self.ints.truncate(ni); self.flts.truncate(nf); self.i(Inst::IBinI(IOp::Add, W64, i, i, 1)); self.f.blocks[self.cur as usize].term = Term::Jump(h); self.cur = exit; } } /// A random program: f(mem, a, b, c) -> u64, every value defined at entry (no undefined reads). fn program(seed: u64) -> Func { let mut r = Rng(seed | 1); let mut f = Func::new(format!("fuzz_{:x}", seed), 0); let mem = f.vreg(Cls::I); let ps: Vec = (0..3).map(|_| f.vreg(Cls::I)).collect(); f.params = std::iter::once(mem).chain(ps.iter().copied()).collect(); f.rets = vec![Cls::I]; let entry = f.block(); let (h2, h6) = (f.vreg(Cls::I), f.vreg(Cls::I)); let mut g = Gen { f, r: &mut r, mem, ints: ps.clone(), flts: Vec::new(), cur: entry, host2: h2, host6: h6, budget: 0, counters: Vec::new() }; g.i(Inst::Iconst(h2, host2 as *const () as usize as i64)); g.i(Inst::Iconst(h6, host6 as *const () as usize as i64)); // the pressure: 20-60 integer values and 4-16 floats live from the entry on let size: u64 = std::env::var("FUZZ_SIZE").ok().and_then(|v| v.parse().ok()).unwrap_or(100); let ni = (20 + g.r.below(40)).min(size / 2 + 3); for k in 0..ni { let v = g.f.vreg(Cls::I); let p = ps[(k % 3) as usize]; let kk = g.r.below(1000) as i64 - 300; g.i(Inst::IBinI(IOp::Add, W64, v, p, kk)); g.ints.push(v); } let nf = 4 + g.r.below(12); for _ in 0..nf { let v = g.f.vreg(Cls::F64); let x = (g.r.below(2000) as f64 - 1000.0) / 8.0; g.i(Inst::Fconst(v, x.to_bits(), true)); g.flts.push(v); } g.budget = (20 + g.r.below(100)).min(size) as u32; g.seq(0); // the result: every value folded (floats through the saturating conversion) let mut acc = g.f.vreg(Cls::I); g.i(Inst::Iconst(acc, 0)); let (ints, flts) = (g.ints.clone(), g.flts.clone()); for v in ints { let (t, a) = (g.f.vreg(Cls::I), g.f.vreg(Cls::I)); g.i(Inst::IBinI(IOp::Rotl, W64, t, acc, 7)); g.i(Inst::IBin(IOp::Xor, W64, a, t, v)); acc = a; } for v in flts { let (t, a) = (g.f.vreg(Cls::I), g.f.vreg(Cls::I)); g.i(Inst::Conv(Conv::FToInt(true, I64), t, v)); g.i(Inst::IBin(IOp::Add, W64, a, acc, t)); acc = a; } let cur = g.cur; g.f.blocks[cur as usize].term = Term::Ret(vec![acc]); g.f } /// Every read of a value is defined on every path to it (a must-analysis over the CFG): an /// undefined read is a generator (or reducer) bug, never something to compare tiers on. fn undefined_read(f: &Func) -> Option { use relax_backend::regalloc::{for_defs, for_uses, term_uses}; let (nb, nv) = (f.blocks.len(), f.vregs.len()); let mut reach = vec![false; nb]; let mut work = vec![0u32]; while let Some(b) = work.pop() { if !std::mem::replace(&mut reach[b as usize], true) { work.extend(f.blocks[b as usize].term.succs()); } } let preds = relax_backend::regalloc::preds_of(f, &reach); // out[b]: defined at b's end (start: everything, shrinking to the fixed point) let mut out = vec![vec![true; nv]; nb]; let entry_in: Vec = (0..nv).map(|v| f.params.iter().any(|p| p.0 as usize == v)).collect(); let block_in = |out: &Vec>, b: usize| -> Vec { if b == 0 { return entry_in.clone(); } let mut d = vec![true; nv]; for &p in &preds[b] { for v in 0..nv { d[v] &= out[p as usize][v]; } } d }; loop { let mut changed = false; for b in 0..nb { if !reach[b] { continue; } let mut d = block_in(&out, b); for i in &f.blocks[b].insts { for_defs(i, |v| d[v.0 as usize] = true); } if d != out[b] { out[b] = d; changed = true; } } if !changed { break; } } let mut tu = Vec::new(); for b in 0..nb { if !reach[b] { continue; } let mut d = block_in(&out, b); for (k, i) in f.blocks[b].insts.iter().enumerate() { let mut bad = None; for_uses(i, |v| { if !d[v.0 as usize] && bad.is_none() { bad = Some(v); } }); if let Some(v) = bad { return Some(format!("b{} +{} {:?} reads v{} before any definition", b, k, i, v.0)); } for_defs(i, |v| d[v.0 as usize] = true); } term_uses(&f.blocks[b].term, &mut tu); if let Some(v) = tu.iter().find(|v| !d[v.0 as usize]) { return Some(format!("b{} terminator reads v{} before any definition", b, v.0)); } } None } // ---- the reference: a direct evaluator of the RIR /// None: no end (a reduction broke a loop) or a call to no known function. fn eval(f: &Func, mem: &mut [u64; WORDS], args: [u64; 3]) -> Option { let mut r = vec![0u64; f.vregs.len()]; r[f.params[0].0 as usize] = mem.as_mut_ptr() as u64; for k in 0..3 { r[f.params[k + 1].0 as usize] = args[k]; } let base = mem.as_ptr() as u64; // (an access within one word: the generator makes aligned ones; a reduction may not) let at = |a: u64, off: i32, size: usize| -> Option<(usize, usize)> { let o = a.wrapping_add(off as i64 as u64).wrapping_sub(base) as usize; (o / 8 < WORDS && o % size == 0).then_some((o / 8, o % 8)) }; let size = |m: Mem| match m { Mem::Int(n, _) => n as usize, _ => 8, }; let mut b = 0usize; let mut steps = 0u64; loop { steps += 1; if steps > 1_000_000 { return None; } for i in &f.blocks[b].insts { match *i { Inst::Iconst(d, k) => r[d.0 as usize] = k as u64, Inst::Fconst(d, k, _) => r[d.0 as usize] = k, Inst::Mov(d, a) => r[d.0 as usize] = r[a.0 as usize], Inst::IBin(op, it, d, a, x) => r[d.0 as usize] = passes::fold_ibin(op, it, r[a.0 as usize] as i64, r[x.0 as usize] as i64).expect("fold") as u64, Inst::IBinI(op, it, d, a, k) => r[d.0 as usize] = passes::fold_ibin(op, it, r[a.0 as usize] as i64, k).expect("fold") as u64, Inst::ICmp(c, s, d, a, x) => r[d.0 as usize] = passes::cmp_i(c, s, r[a.0 as usize] as i64, r[x.0 as usize] as i64) as u64, Inst::ICmpI(c, s, d, a, k) => r[d.0 as usize] = passes::cmp_i(c, s, r[a.0 as usize] as i64, k) as u64, Inst::Conv(Conv::IntToInt(it), d, a) => r[d.0 as usize] = passes::fold_ibin(IOp::Add, it, r[a.0 as usize] as i64, 0).unwrap() as u64, Inst::Sel(d, c, a, x) => r[d.0 as usize] = if r[c.0 as usize] != 0 { r[a.0 as usize] } else { r[x.0 as usize] }, Inst::FBin(op, w, d, a, x) => r[d.0 as usize] = passes::fold_fbin(op, w, r[a.0 as usize], r[x.0 as usize]), Inst::Conv(Conv::FToInt(w, it), d, a) => r[d.0 as usize] = passes::f_to_int(passes::fval(r[a.0 as usize], w), it) as u64, Inst::Conv(Conv::IntToF(it, true), d, a) => { let x = passes::fold_ibin(IOp::Add, it, r[a.0 as usize] as i64, 0).unwrap(); r[d.0 as usize] = (if it.signed { x as f64 } else { x as u64 as f64 }).to_bits(); } Inst::Load(m, d, a, off) => { let (w, o) = at(r[a.0 as usize], off, size(m))?; let word = mem[w]; r[d.0 as usize] = match m { Mem::F64 => word, Mem::Int(n, s) => { let bits = n as u32 * 8; let v = if bits == 64 { word } else { (word >> (o * 8)) & ((1u64 << bits) - 1) }; if s && bits < 64 { (((v << (64 - bits)) as i64) >> (64 - bits)) as u64 } else { v } } Mem::F32 => unreachable!(), }; } Inst::Store(m, a, off, v) => { let (w, o) = at(r[a.0 as usize], off, size(m))?; let x = r[v.0 as usize]; match m { Mem::F64 => mem[w] = x, Mem::Int(n, _) => { let bits = n as u32 * 8; if bits == 64 { mem[w] = x; } else { let mask = ((1u64 << bits) - 1) << (o * 8); mem[w] = (mem[w] & !mask) | ((x << (o * 8)) & mask); } } Mem::F32 => unreachable!(), } } Inst::Call(Callee::Indirect(t), ref args, ref rets) => { let a: Vec = args.iter().map(|v| r[v.0 as usize]).collect(); let tgt = r[t.0 as usize]; let v = if tgt == host2 as *const () as usize as u64 && a.len() == 2 { host2(a[0], a[1]) } else if tgt == host6 as *const () as usize as u64 && a.len() == 6 { host6(a[0], a[1], a[2], a[3], a[4], a[5]) } else { return None; }; r[rets[0].0 as usize] = v; } ref other => panic!("evaluator: {:?}", other), } } match &f.blocks[b].term { Term::Jump(t) => b = *t as usize, Term::Branch(c, t, e) => b = if r[c.0 as usize] != 0 { *t as usize } else { *e as usize }, Term::Ret(v) => return Some(r[v[0].0 as usize]), other => panic!("evaluator: {:?}", other), } } } // ---- the tiers #[cfg(target_arch = "x86_64")] fn native(o: &relax_session::Options, f: &Func, thorough: bool) -> Result, String> { let env = relax_backend::x64::Env { slots: SlotsPtr::NONE, tls_key: 0, tls_slow: 0, resume: 0, opt_regs: thorough, syms: 0, sym_class: 0, near: false }; let c = relax_backend::x64::compile(o, f, &env)?; // (the float constant pool follows the text: the whole code runs; nothing to link here) if !c.relocs.is_empty() { return Err(format!("{} unlinked relocations", c.relocs.len())); } Ok(c.code) } #[cfg(target_arch = "aarch64")] fn native(o: &relax_session::Options, f: &Func, thorough: bool) -> Result, String> { let env = relax_backend::arm64::Env { slots: SlotsPtr::NONE, tls_key: 0, tls_slow: 0, resume: 0, opt_regs: thorough, syms: 0, sym_class: 0, near: false }; let c = relax_backend::arm64::compile(o, f, &env)?; // (the float constant pool follows the text: the whole code runs; nothing to link here) if !c.relocs.is_empty() { return Err(format!("{} unlinked relocations", c.relocs.len())); } Ok(c.code) } fn options(knobs: &[&str]) -> relax_session::Options { let mut o = relax_session::Options::default(); o.opt = knobs.iter().map(|s| s.to_string()).collect(); // the allocation checker, fatal: a finding fails the compile // (FUZZ_NOCHECKRA=1: without it -- triage: a checker finding whose code still agrees) if std::env::var("FUZZ_NOCHECKRA").is_err() { o.opt.push("+checkra".to_string()); } o } /// The middle-end pipelines applied before code generation. #[derive(Clone, Copy, Debug)] enum Pipe { Raw, O2, O3, } fn pipe(o: &relax_session::Options, f: &Func, p: Pipe) -> Func { let mut g = f.clone(); match p { Pipe::Raw => {} Pipe::O2 => { passes::simplify(o, &mut g, None, true, true); passes::licm(o, &mut g); passes::simplify(o, &mut g, None, true, true); } Pipe::O3 => { passes::simplify(o, &mut g, None, true, true); relax_codegen::loops::unroll_const_loops(o, &mut g); relax_codegen::loops::unroll_loops(o, &mut g); relax_codegen::loops::merge_stores(o, &mut g); passes::licm(o, &mut g); passes::simplify(o, &mut g, None, true, true); } } g } const KNOBS: [&[&str]; 6] = [&[], &["-storeskip"], &["-saveskip"], &["-copyreuse"], &["-edgeload", "-defregion"], &["-regionwin", "-slotcolor"]]; fn inputs(seed: u64) -> Vec<([u64; 3], [u64; WORDS])> { let mut r = Rng(seed.wrapping_mul(0x2545_f491_4f6c_dd1d) | 1); (0..3) .map(|_| { let a = [r.next(), r.below(20), r.next() >> r.below(60)]; let mut m = [0u64; WORDS]; for (k, w) in m.iter_mut().enumerate() { *w = if k < INT_WORDS { r.next() } else { ((r.below(2000) as f64 - 1000.0) / 4.0).to_bits() }; } (a, m) }) .collect() } /// Runs program `seed` through every tier; Err names the first disagreement. fn check(seed: u64) -> Result { let f = program(seed); f.verify().map_err(|e| format!("seed {:#x}: generator made invalid RIR: {}", seed, e))?; if let Some(e) = undefined_read(&f) { return Err(format!("seed {:#x}: generator made an undefined read: {}", seed, e)); } let cases: Vec<_> = inputs(seed).into_iter().map(|(a, m)| { let mut mm = m; let r = eval(&f, &mut mm, a).expect("generated programs end"); (a, m, r, mm) }).collect(); let mut runs = 0; for p in [Pipe::Raw, Pipe::O2, Pipe::O3] { for knobs in KNOBS { let o = options(knobs); let g = pipe(&o, &f, p); g.verify().map_err(|e| format!("seed {:#x} {:?}: pass made invalid RIR: {}", seed, p, e))?; for thorough in [false, true] { let bytes = native(&o, &g, thorough).map_err(|e| format!("seed {:#x} {:?} {:?} thorough={}: {}", seed, p, knobs, thorough, e))?; let code = Code::new(&bytes).ok_or("no executable memory")?; let run: extern "C" fn(*mut u64, u64, u64, u64) -> u64 = unsafe { std::mem::transmute(code.ptr()) }; for (a, m, want, want_mem) in &cases { let mut mm = *m; let got = run(mm.as_mut_ptr(), a[0], a[1], a[2]); let mem_ok = mm.iter().zip(want_mem.iter()).enumerate().all(|(k, (x, y))| x == y || (k >= INT_WORDS && f64::from_bits(*x).is_nan() && f64::from_bits(*y).is_nan())); if got != *want || !mem_ok { let w = mm.iter().zip(want_mem.iter()).position(|(x, y)| x != y); return Err(format!("seed {:#x} {:?} knobs {:?} thorough={} args {:?}: got {:#x} want {:#x}{}", seed, p, knobs, thorough, a, got, want, w.map_or(String::new(), |k| format!(", memory word {} {:#x} want {:#x}", k, mm[k], want_mem[k])))); } runs += 1; } } } } Ok(runs) } /// Does `f` disagree with the evaluator in tier (p, knobs, thorough) on any input of `seed`? fn disagrees(f: &Func, seed: u64, p: Pipe, knobs: &[&str], thorough: bool) -> bool { if f.verify().is_err() || undefined_read(f).is_some() { return false; } // (a reduction that breaks a loop or a call is no reduction) if inputs(seed).into_iter().any(|(a, mut m)| eval(f, &mut m, a).is_none()) { return false; } let o = options(knobs); let g = pipe(&o, f, p); let Ok(bytes) = native(&o, &g, thorough) else { return true }; let code = Code::new(&bytes).unwrap(); let run: extern "C" fn(*mut u64, u64, u64, u64) -> u64 = unsafe { std::mem::transmute(code.ptr()) }; inputs(seed).into_iter().any(|(a, m)| { // (one buffer for both runs: a result that is the buffer's address agrees) let mut mm = m; let Some(want) = eval(f, &mut mm, a) else { return false }; let want_mem = mm; mm = m; let got = run(mm.as_mut_ptr(), a[0], a[1], a[2]); got != want || mm.iter().zip(want_mem.iter()).enumerate().any(|(k, (x, y))| x != y && !(k >= INT_WORDS && f64::from_bits(*x).is_nan() && f64::from_bits(*y).is_nan())) }) } /// Shrinks a failing program: each instruction in turn goes (when every read stays defined), or /// else becomes constants for what it defines, kept when the program still disagrees in that tier; /// branches go to one side. fn reduce(mut f: Func, seed: u64, p: Pipe, knobs: &[&str], thorough: bool) -> Func { loop { let mut changed = false; for b in 0..f.blocks.len() { let mut k = f.blocks[b].insts.len(); while k > 0 { k -= 1; let mut g = f.clone(); g.blocks[b].insts.remove(k); g.blocks[b].pos.remove(k); if disagrees(&g, seed, p, knobs, thorough) { f = g; changed = true; } } } // an instruction with one result becomes a copy of one of its operands (chains collapse) for b in 0..f.blocks.len() { for k in 0..f.blocks[b].insts.len() { let mut defs = Vec::new(); relax_backend::regalloc::for_defs(&f.blocks[b].insts[k], |d| defs.push(d)); let mut uses = Vec::new(); relax_backend::regalloc::for_uses(&f.blocks[b].insts[k], |u| uses.push(u)); if defs.len() != 1 || matches!(f.blocks[b].insts[k], Inst::Mov(..)) { continue; } let d = defs[0]; for u in uses { if f.vregs[u.0 as usize] != f.vregs[d.0 as usize] || u == d { continue; } let mut g = f.clone(); g.blocks[b].insts[k] = Inst::Mov(d, u); if disagrees(&g, seed, p, knobs, thorough) { f = g; changed = true; break; } } } } for b in 0..f.blocks.len() { let mut k = 0; while k < f.blocks[b].insts.len() { let mut defs = Vec::new(); relax_backend::regalloc::for_defs(&f.blocks[b].insts[k], |d| defs.push(d)); let mut g = f.clone(); let repl: Vec = defs.iter().map(|d| if g.vregs[d.0 as usize] == Cls::I { Inst::Iconst(*d, 0) } else { Inst::Fconst(*d, 0, true) }).collect(); if repl.len() == 1 && format!("{:?}", repl[0]) == format!("{:?}", g.blocks[b].insts[k]) { k += 1; continue; } let n = repl.len(); g.blocks[b].insts.splice(k..k + 1, repl); g.blocks[b].pos.splice(k..k + 1, std::iter::repeat(0).take(n)); if disagrees(&g, seed, p, knobs, thorough) { f = g; changed = true; k += n; } else { k += 1; } } } // branches: to one side for b in 0..f.blocks.len() { if let Term::Branch(_, t, e) = f.blocks[b].term { for side in [t, e] { let mut g = f.clone(); g.blocks[b].term = Term::Jump(side); if disagrees(&g, seed, p, knobs, thorough) { f = g; changed = true; break; } } } } if !changed { return f; } } } #[test] fn random_programs_agree_across_tiers() { // FUZZ_REDUCE=: the smallest program that still disagrees in its first failing tier if let Some(s) = std::env::var("FUZZ_REDUCE").ok().and_then(|s| u64::from_str_radix(s.trim_start_matches("0x"), 16).ok()) { let f = program(s); for p in [Pipe::Raw, Pipe::O2, Pipe::O3] { for knobs in KNOBS { for thorough in [false, true] { if disagrees(&f, s, p, knobs, thorough) { let r = reduce(f.clone(), s, p, knobs, thorough); let o = options(knobs); let g = pipe(&o, &r, p); eprintln!("reduced {:#x} {:?} {:?} thorough={}:\n{}", s, p, knobs, thorough, r.dump()); eprintln!("after the pipeline:\n{}", g.dump()); // the allocation (MAKEPAD_RUN_RA_TRACE) and the code (FUZZ_CODE_OUT=) // of the reduced program, for reading the miscompile std::env::set_var("MAKEPAD_RUN_RA_TRACE", &r.name); let bytes = native(&o, &g, thorough).unwrap(); std::env::remove_var("MAKEPAD_RUN_RA_TRACE"); if let Ok(path) = std::env::var("FUZZ_CODE_OUT") { std::fs::write(path, &bytes).unwrap(); } for (a, m) in inputs(s) { let mut wm = m; let want = eval(&r, &mut wm, a).unwrap_or(0); let code = Code::new(&native(&o, &g, thorough).unwrap()).unwrap(); let run: extern "C" fn(*mut u64, u64, u64, u64) -> u64 = unsafe { std::mem::transmute(code.ptr()) }; let mut mm = m; let got = run(mm.as_mut_ptr(), a[0], a[1], a[2]); eprintln!("args {:?}: got {:#x} want {:#x}; memory differs at {:?}", a, got, want, mm.iter().zip(wm.iter()).enumerate().filter(|(_, (x, y))| x != y).map(|(k, (x, y))| (k, *x, *y)).collect::>()); } return; } } } } eprintln!("{:#x} agrees everywhere", s); return; } if let Some(s) = std::env::var("FUZZ_SEED").ok().and_then(|s| u64::from_str_radix(s.trim_start_matches("0x"), 16).ok()) { eprintln!("{:?}", check(s)); if let Ok(dump) = std::env::var("FUZZ_DUMP") { if dump == "1" { eprintln!("{}", program(s).dump()); } } check(s).unwrap(); return; } let n: u64 = std::env::var("FUZZ_N").ok().and_then(|v| v.parse().ok()).unwrap_or(150); let first: u64 = std::env::var("FUZZ_FIRST").ok().and_then(|v| v.parse().ok()).unwrap_or(1); let mut fails = Vec::new(); let mut runs = 0; for k in first..first + n { let seed = k.wrapping_mul(0x9e37_79b9_7f4a_7c15); match check(seed) { Ok(r) => runs += r, Err(e) => { eprintln!("fuzz: {}", e); fails.push(seed); } } } eprintln!("fuzz: {} programs, {} native runs, {} disagree", n, runs, fails.len()); assert!(fails.is_empty(), "programs disagreeing across tiers (rerun with FUZZ_SEED=): {:x?}", fails); } /// Seeds the clock-seeded batch found (FUZZ-NEW): they block from then on, in every tier. /// - 3853108f782e2d2a (O2 thorough, checker only; the code agreed): `t = s as i8` read only in /// its low bits, coalesced with s (equal_copies) in a caller-saved register, both saved around a /// call in a loop; the checker took the cast for a copy in the register only, so the restore /// of s's save slot (stored before t existed) dropped t. const FOUND_SEEDS: [u64; 2] = [0x3853_108f_782e_2d2a, 0x475f_7b26_c831_6268]; #[test] fn found_seeds_agree_across_tiers() { let fails: Vec = FOUND_SEEDS.iter().filter_map(|&s| check(s).err()).collect(); assert!(fails.is_empty(), "found seeds disagree again:\n{}", fails.join("\n")); } // ---- minimized cases the fuzzer found (each runs through every tier like a random program) /// `x = f(.., x, ..)` in a loop with x in a caller-saved register (every callee-saved one taken /// by values live across the call): x's ranges touch at the call and merged, so allocate_low /// saved x around the call that defines it, and the restore after the result overwrote the /// result with the old x (seeds 5b89fad58bb77d74, 459be4c9d7a5904 and 14 more of the first 600). fn regress_call_redefines(n_live: usize) -> Func { let mut f = Func::new("regress_call_redefines".to_string(), 0); let mem = f.vreg(Cls::I); let ps: Vec = (0..3).map(|_| f.vreg(Cls::I)).collect(); f.params = std::iter::once(mem).chain(ps.iter().copied()).collect(); f.rets = vec![Cls::I]; let (b0, head, body, exit) = (f.block(), f.block(), f.block(), f.block()); let push = |f: &mut Func, b: u32, i: Inst| { f.blocks[b as usize].insts.push(i); f.blocks[b as usize].pos.push(0); }; let (h6, x, i, n, c) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I)); push(&mut f, b0, Inst::Iconst(h6, host6 as *const () as usize as i64)); push(&mut f, b0, Inst::Mov(x, ps[0])); push(&mut f, b0, Inst::Iconst(i, 0)); push(&mut f, b0, Inst::IBinI(IOp::And, W64, n, ps[1], 7)); // values live across the loop and its call: they take the callee-saved registers let live: Vec = (0..n_live).map(|k| { let v = f.vreg(Cls::I); push(&mut f, b0, Inst::IBinI(IOp::Add, W64, v, ps[2], 11 * k as i64 + 1)); v }).collect(); f.blocks[b0 as usize].term = Term::Jump(head); push(&mut f, head, Inst::ICmp(Cond::Lt, false, c, i, n)); f.blocks[head as usize].term = Term::Branch(c, body, exit); let z = f.vreg(Cls::I); push(&mut f, body, Inst::Iconst(z, 0)); // (read in the loop more than x is: they win the callee-saved registers, x gets a // caller-saved one) let mut t = z; for _ in 0..3 { for &v in &live { let t2 = f.vreg(Cls::I); push(&mut f, body, Inst::IBin(IOp::Add, W64, t2, t, v)); t = t2; } } push(&mut f, body, Inst::Store(Mem::Int(8, false), mem, 0, t)); push(&mut f, body, Inst::Call(Callee::Indirect(h6), vec![z, live[0], x, i, z, z], vec![x])); push(&mut f, body, Inst::IBinI(IOp::Add, W64, i, i, 1)); f.blocks[body as usize].term = Term::Jump(head); let mut acc = x; for v in live { let a = f.vreg(Cls::I); push(&mut f, exit, Inst::IBin(IOp::Xor, W64, a, acc, v)); acc = a; } f.blocks[exit as usize].term = Term::Ret(vec![acc]); f } #[test] fn regress_call_redefines_its_argument() { for n_live in [6, 12, 16] { let f = regress_call_redefines(n_live); f.verify().unwrap(); assert!(undefined_read(&f).is_none()); for p in [Pipe::Raw, Pipe::O2, Pipe::O3] { for knobs in KNOBS { for thorough in [false, true] { assert!(!disagrees(&f, 0x5b89_fad5_8bb7_7d74, p, knobs, thorough), "n_live {} {:?} {:?} thorough={}", n_live, p, knobs, thorough); } } } } } /// A narrow load of what a narrow store just wrote, the stored register wider than the store: /// simplify's store-to-load forwarding replaced the load with the whole register (`store u8 /// [p], x; load u8 [p]` gave x, not x as u8; seeds f880dbd780695b33, fb49238b68499da6, /// acd22286c6926577). fn regress_narrow_forward(m: Mem) -> Func { let mut f = Func::new("regress_narrow_forward".to_string(), 0); let mem = f.vreg(Cls::I); let ps: Vec = (0..3).map(|_| f.vreg(Cls::I)).collect(); f.params = std::iter::once(mem).chain(ps.iter().copied()).collect(); f.rets = vec![Cls::I]; let b0 = f.block(); let x = f.vreg(Cls::I); for i in [Inst::Store(m, mem, 8, ps[0]), Inst::Load(m, x, mem, 8)] { f.blocks[b0 as usize].insts.push(i); f.blocks[b0 as usize].pos.push(0); } f.blocks[b0 as usize].term = Term::Ret(vec![x]); f } #[test] fn regress_narrow_store_forwarded_to_load() { for m in [Mem::Int(1, false), Mem::Int(1, true), Mem::Int(2, false), Mem::Int(2, true), Mem::Int(4, false), Mem::Int(4, true)] { let f = regress_narrow_forward(m); f.verify().unwrap(); for p in [Pipe::Raw, Pipe::O2, Pipe::O3] { for thorough in [false, true] { assert!(!disagrees(&f, 0xf880_dbd7_8069_5b33, p, &[], thorough), "{:?} {:?} thorough={}", m, p, thorough); } } } } /// copy_reuse served a read of a spilled value from the register of its copy after the copy's /// value was dead: `u = v; t = ..; w = t ? v : y; u = 0; .. u ..` with u's first value never read. /// The read of u's second value kept u "read later in the block", but the allocator gives u's /// register away between its two definitions, here to t, so the select read t for v. Seed /// 475f7b26c8316268 (after O2: v1 spilled, `Mov v3, v1` in b29) had t a compare fused into the /// select (never written: only the allocation check saw it); `load`: t is a load, written, and the /// result is wrong. fn regress_dead_copy_reuse(load: bool) -> Func { let mut f = Func::new("regress_dead_copy_reuse".to_string(), 0); let v: Vec = (0..20).map(|_| f.vreg(Cls::I)).collect(); f.params = vec![v[0], v[1], v[2], v[3]]; f.rets = vec![Cls::I]; let (b0, b1, b2, b4, b5, b6, b12, b27, b29) = (f.block(), f.block(), f.block(), f.block(), f.block(), f.block(), f.block(), f.block(), f.block()); let push = |f: &mut Func, b: u32, i: Inst| { f.blocks[b as usize].insts.push(i); f.blocks[b as usize].pos.push(0); }; push(&mut f, b0, Inst::Iconst(v[4], 0)); for (d, s) in [(5, 4), (6, 3), (7, 3), (8, 4), (9, 3), (10, 4), (11, 3), (12, 4), (13, 4)] { push(&mut f, b0, Inst::Mov(v[d], v[s])); } f.blocks[b0 as usize].term = Term::Jump(b1); push(&mut f, b1, Inst::ICmp(Cond::Lt, false, v[14], v[13], v[2])); f.blocks[b1 as usize].term = Term::Branch(v[14], b2, b27); f.blocks[b2 as usize].term = Term::Branch(v[3], b4, b5); push(&mut f, b4, Inst::Mov(v[4], v[11])); push(&mut f, b4, Inst::Mov(v[10], v[7])); f.blocks[b4 as usize].term = Term::Jump(b6); push(&mut f, b5, Inst::Iconst(v[15], 0)); push(&mut f, b5, Inst::Sel(v[7], v[6], v[15], v[7])); push(&mut f, b5, Inst::Mov(v[8], v[0])); f.blocks[b5 as usize].term = Term::Jump(b6); push(&mut f, b6, Inst::IBinI(IOp::Add, W64, v[13], v[13], 1)); f.blocks[b6 as usize].term = Term::Jump(b1); let (x16, x17, x18) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I)); push(&mut f, b12, Inst::IBin(IOp::Xor, W64, x16, v[5], v[8])); push(&mut f, b12, Inst::IBin(IOp::Xor, W64, x17, x16, v[10])); push(&mut f, b12, Inst::IBin(IOp::Xor, W64, x18, x17, v[12])); f.blocks[b12 as usize].term = Term::Ret(vec![x18]); f.blocks[b27 as usize].term = Term::Branch(v[3], b12, b29); push(&mut f, b29, Inst::Mov(v[3], v[1])); push(&mut f, b29, if load { Inst::Load(Mem::Int(8, false), v[19], v[0], 8) } else { Inst::ICmpI(Cond::Ne, false, v[19], v[4], 0) }); push(&mut f, b29, Inst::Sel(v[12], v[19], v[1], v[9])); push(&mut f, b29, Inst::Iconst(v[3], 0)); push(&mut f, b29, Inst::Mov(v[5], v[3])); f.blocks[b29 as usize].term = Term::Jump(b12); f } #[test] fn regress_dead_copy_not_reused() { // (the select's path needs the last parameter 0; memory word 1 = 1 selects v) let cases: Vec<[u64; 3]> = vec![[0x1234_5678_9abc_def1, 3, 0], [0xfeed_beef_0000_0005, 0, 0], [7, 5, 9]]; // (the code without the allocation check first: the wrong register shows in the result) for check in [false, true] { for load in [true, false] { let f = regress_dead_copy_reuse(load); f.verify().unwrap(); assert!(undefined_read(&f).is_none()); for p in [Pipe::Raw, Pipe::O2, Pipe::O3] { for knobs in KNOBS { for thorough in [false, true] { let mut o = options(knobs); if !check { o.opt.retain(|k| k != "+checkra"); } let g = pipe(&o, &f, p); let bytes = native(&o, &g, thorough).unwrap_or_else(|e| panic!("load {} {:?} {:?} thorough={}: {}", load, p, knobs, thorough, e)); let code = Code::new(&bytes).unwrap(); let run: extern "C" fn(*mut u64, u64, u64, u64) -> u64 = unsafe { std::mem::transmute(code.ptr()) }; for a in &cases { // (one buffer for both: the result folds in its address) let mut m = [0u64; WORDS]; m[1] = 1; let want = eval(&f, &mut m, *a).unwrap(); let got = run(m.as_mut_ptr(), a[0], a[1], a[2]); assert_eq!(got, want, "load {} {:?} {:?} thorough={} check={} args {:?}", load, p, knobs, thorough, check, a); } } } } } } }