//! version_bounds_loops: a counted loop's bounds checks proved by one guard in front of a //! check-free clone, the original loop the fallback. Each case runs the RIR before and after the //! pass through a small evaluator over the same inputs, including lengths that make the guard //! fail and inputs that panic, and requires identical memory, results and panic (index, len, //! number of stores done before it). use relax_backend::regalloc::reachable; use relax_backend::rir::*; use relax_codegen::version; const U64: IntTy = IntTy { bits: 64, signed: false }; fn push(f: &mut Func, b: u32, i: Inst) { f.blocks[b as usize].insts.push(i); f.blocks[b as usize].pos.push(1); } fn term(f: &mut Func, b: u32, t: Term) { f.blocks[b as usize].term = t; } #[derive(Debug, PartialEq)] enum Out { Ret(Vec, Vec, usize), Panic(u64, u64, Vec, usize), } // Blocks executed past the original function's 8 (axpy shapes): the clone ran. thread_local! { static CLONE_STEPS: std::cell::Cell = const { std::cell::Cell::new(0) }; } /// Integer-only evaluator: memory is one byte vector, pointers are offsets into it. A Host call /// is the bounds panic (index, len). Returns the result, the memory and the number of stores. fn eval(f: &Func, args: &[u64], mem0: &[u8]) -> Out { let mut mem = mem0.to_vec(); let mut r = vec![0u64; f.vregs.len()]; for (p, a) in f.params.iter().zip(args) { r[p.0 as usize] = *a; } let mut stores = 0usize; let mut b = 0usize; let mut steps = 0u64; loop { steps += 1; assert!(steps < 10_000_000, "runaway"); if b > 8 { // past axpy's 8 blocks and the guard: a block the versioning added (the clone) ran CLONE_STEPS.with(|c| c.set(c.get() + 1)); } for i in &f.blocks[b].insts { match *i { Inst::Iconst(d, k) => r[d.0 as usize] = k as u64, Inst::Mov(d, s) => r[d.0 as usize] = r[s.0 as usize], Inst::Sel(d, c, a, b2) => r[d.0 as usize] = if r[c.0 as usize] != 0 { r[a.0 as usize] } else { r[b2.0 as usize] }, Inst::Conv(Conv::IntToInt(t), d, s) => { let v = r[s.0 as usize]; r[d.0 as usize] = if t.bits >= 64 { v } else if t.signed { (((v << (64 - t.bits)) as i64) >> (64 - t.bits)) as u64 } else { v & ((1u64 << t.bits) - 1) }; } Inst::IBin(op, it, d, a, c) => r[d.0 as usize] = typed(it, op, r[a.0 as usize], r[c.0 as usize]), Inst::IBinI(op, it, d, a, k) => r[d.0 as usize] = typed(it, op, r[a.0 as usize], k as u64), Inst::ICmp(cc, s, d, a, c) => r[d.0 as usize] = cmp(cc, s, r[a.0 as usize], r[c.0 as usize]) as u64, Inst::ICmpI(cc, s, d, a, k) => r[d.0 as usize] = cmp(cc, s, r[a.0 as usize], k as u64) as u64, Inst::Load(Mem::Int(4, false), d, a, off) => { let p = (r[a.0 as usize] as i64 + off as i64) as usize; r[d.0 as usize] = u32::from_le_bytes(mem[p..p + 4].try_into().unwrap()) as u64; } Inst::Store(Mem::Int(4, _), a, off, s) => { let p = (r[a.0 as usize] as i64 + off as i64) as usize; mem[p..p + 4].copy_from_slice(&(r[s.0 as usize] as u32).to_le_bytes()); stores += 1; } Inst::Call(Callee::Host(_), ref a, _) => { return Out::Panic(r[a[0].0 as usize], r[a[1].0 as usize], mem, stores); } ref other => panic!("eval: {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(vs) => return Out::Ret(vs.iter().map(|v| r[v.0 as usize]).collect(), mem, stores), t => panic!("eval: {t:?}"), } } } /// an operation of a type: unsigned widths below 64 wrap (the result zero-extended); rotates and /// remainders at the type's width fn typed(it: IntTy, op: IOp, a: u64, b: u64) -> u64 { if it.bits >= 64 || it.signed { return bin(op, a, b); } let m = (1u64 << it.bits) - 1; match op { IOp::Rotl => { let (a, k) = (a & m, b % it.bits as u64); ((a << k) | (a >> ((it.bits as u64 - k) % it.bits as u64))) & m } _ => bin(op, a, b) & m, } } fn bin(op: IOp, a: u64, b: u64) -> u64 { match op { IOp::Rem => a % b, IOp::Div => a / b, IOp::Rotl => a.rotate_left(b as u32), IOp::Add => a.wrapping_add(b), IOp::Sub => a.wrapping_sub(b), IOp::Mul => a.wrapping_mul(b), IOp::And => a & b, IOp::Or => a | b, IOp::Xor => a ^ b, IOp::Shl => a << (b & 63), IOp::Shr => a >> (b & 63), _ => panic!("bin {op:?}"), } } fn cmp(c: Cond, s: bool, a: u64, b: u64) -> bool { if s { let (a, b) = (a as i64, b as i64); return match c { Cond::Lt => a < b, Cond::Le => a <= b, Cond::Gt => a > b, Cond::Ge => a >= b, Cond::Eq => a == b, Cond::Ne => a != b, }; } match c { Cond::Lt => a < b, Cond::Le => a <= b, Cond::Gt => a > b, Cond::Ge => a >= b, Cond::Eq => a == b, Cond::Ne => a != b, } } /// `for i in start..n { y[i] = y[i] + x[i + k] * 3 }` with both checks (y: i < ylen, x: i + k < xlen), /// in the shape fold_ranges leaves (`t = i; i = i + 1` after the header's test). /// params: y, ylen, x, xlen, n, start fn axpy(k: i64, check_y: bool) -> Func { axpy_sym(k, check_y, false) } /// as axpy; `sym`: the x index is `(t + m) - w + k` with m, w two more params (a 2D stencil's /// `y * w + x - w`) fn axpy_sym(k: i64, check_y: bool, sym: bool) -> Func { let mut f = Func::new("axpy".into(), 0); let v: Vec = (0..8).map(|_| f.vreg(Cls::I)).collect(); let (y, ylen, x, xlen, n, start) = (v[0], v[1], v[2], v[3], v[4], v[5]); f.params.extend([y, ylen, x, xlen, n, start, v[6], v[7]]); for _ in 0..8 { f.block(); } let (i, c, t, i2, cy, xi, cx, off, offx, yv, xv, m, s, ya, xa) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I)); push(&mut f, 0, Inst::Mov(i, start)); term(&mut f, 0, Term::Jump(1)); // b1: header test push(&mut f, 1, Inst::ICmp(Cond::Lt, false, c, i, n)); term(&mut f, 1, Term::Branch(c, 2, 5)); // b2: t = i; i = i + 1; y check push(&mut f, 2, Inst::Mov(t, i)); push(&mut f, 2, Inst::IBinI(IOp::Add, U64, i2, i, 1)); push(&mut f, 2, Inst::Mov(i, i2)); if check_y { push(&mut f, 2, Inst::ICmp(Cond::Lt, false, cy, t, ylen)); term(&mut f, 2, Term::Branch(cy, 3, 6)); } else { term(&mut f, 2, Term::Jump(3)); } // b3: x check of t + k let tk = if sym { let (a1, a2) = (f.vreg(Cls::I), f.vreg(Cls::I)); push(&mut f, 3, Inst::IBin(IOp::Add, U64, a1, v[6], t)); push(&mut f, 3, Inst::IBin(IOp::Sub, U64, a2, a1, v[7])); a2 } else { t }; if k >= 0 { push(&mut f, 3, Inst::IBinI(IOp::Add, U64, xi, tk, k)); } else { push(&mut f, 3, Inst::IBinI(IOp::Sub, U64, xi, tk, -k)); } push(&mut f, 3, Inst::ICmp(Cond::Lt, false, cx, xi, xlen)); term(&mut f, 3, Term::Branch(cx, 4, 7)); // b4: body push(&mut f, 4, Inst::IBinI(IOp::Shl, U64, off, t, 2)); push(&mut f, 4, Inst::IBinI(IOp::Shl, U64, offx, xi, 2)); push(&mut f, 4, Inst::IBin(IOp::Add, U64, ya, y, off)); push(&mut f, 4, Inst::IBin(IOp::Add, U64, xa, x, offx)); push(&mut f, 4, Inst::Load(Mem::Int(4, false), yv, ya, 0)); push(&mut f, 4, Inst::Load(Mem::Int(4, false), xv, xa, 0)); push(&mut f, 4, Inst::IBinI(IOp::Mul, U64, m, xv, 3)); push(&mut f, 4, Inst::IBin(IOp::Add, U64, s, yv, m)); push(&mut f, 4, Inst::Store(Mem::Int(4, false), ya, 0, s)); term(&mut f, 4, Term::Jump(1)); // b5: exit, returns the counter (a value read after the loop) f.rets.push(Cls::I); term(&mut f, 5, Term::Ret(vec![i])); for (b, (a0, a1)) in [(6u32, (t, ylen)), (7u32, (xi, xlen))] { let sym = f.vreg(Cls::I); push(&mut f, b, Inst::Iconst(sym, 0)); push(&mut f, b, Inst::Call(Callee::Host(Sym { id: 5, off: 0 }), vec![a0, a1, sym], Vec::new())); term(&mut f, b, Term::Unreachable); } f } fn run_cases(orig: &Func, new: &Func) -> usize { run_cases_mw(orig, new, &[(0, 0)]) } fn run_cases_mw(orig: &Func, new: &Func, mws: &[(u64, u64)]) -> usize { // memory: y at 0 (64 u32), x at 256 (64 u32) let mut mem = vec![0u8; 512]; for j in 0..128u32 { mem[j as usize * 4..j as usize * 4 + 4].copy_from_slice(&(j * 7 + 1).to_le_bytes()); } let mut cases = 0; let mut panics = 0; for ylen in [0u64, 1, 5, 20, 40, 64] { for xlen in [0u64, 3, 19, 20, 21, 40, 64] { for n in [0u64, 1, 4, 19, 20, 21, 40, 64] { for start in [0u64, 1, 2, 3, 30] { for &(m, w) in mws { let args = [0, ylen, 256, xlen, n, start, m, w]; let a = eval(orig, &args, &mem); let b = eval(new, &args, &mem); assert_eq!(a, b, "ylen {ylen} xlen {xlen} n {n} start {start} m {m} w {w}"); if matches!(a, Out::Panic(..)) { panics += 1; } cases += 1; } } } } } assert!(panics > 0 && panics < cases, "the cases cover both panicking and clean runs"); cases } fn clone_has_no_checks(f: &Func) -> bool { // some reachable loop runs without any branch to an Unreachable block let reach = reachable(f); let cold = |b: u32| matches!(f.blocks[b as usize].term, Term::Unreachable); let reach_loop_blocks: Vec = (0..f.blocks.len()).filter(|&b| reach[b]).collect(); reach_loop_blocks.iter().any(|&b| matches!(f.blocks[b].term, Term::Jump(t) if !cold(t))) && f.blocks.len() > 8 } fn versioned(mut f: Func) -> (Func, Func) { let orig = f.clone(); let changed = version::version_bounds_loops(&relax_session::Options::default(), &mut f); assert!(changed, "versioned"); (orig, f) } #[test] fn axpy_two_checks_offset_zero() { let (orig, new) = versioned(axpy(0, true)); assert!(clone_has_no_checks(&new)); // the clone's two checks are gone: count Branch terms to cold blocks in appended blocks let cold = |b: u32| matches!(new.blocks[b as usize].term, Term::Unreachable); let clone_checks = new.blocks[8..].iter().filter(|b| matches!(b.term, Term::Branch(_, t, e) if cold(t) || cold(e))).count(); assert_eq!(clone_checks, 0); run_cases(&orig, &new); } #[test] fn stencil_positive_offset() { let (orig, new) = versioned(axpy(2, true)); run_cases(&orig, &new); } #[test] fn negative_offset_needs_start() { let (orig, new) = versioned(axpy(-1, false)); run_cases(&orig, &new); } /// The clone renames the counter copy t although the original's panic block reads it (the clone /// cannot reach that block): later single-def passes and the vectoriser see a loop-local t. #[test] fn clone_renames_values_only_cold_blocks_read() { let (_, new) = versioned(axpy(0, true)); let t = match new.blocks[2].insts[0] { Inst::Mov(d, _) => d, _ => unreachable!(), }; let clone_defines_t = new.blocks[8..].iter().any(|b| b.insts.iter().any(|i| matches!(i, Inst::Mov(d, _) if *d == t))); assert!(!clone_defines_t); } /// The index copy also defined after the loop (a storage-dead zero, as lowering emits): the check /// is still proved, and the clone still renames it. #[test] fn outside_def_of_index_copy() { let mut f = axpy(0, true); let t = match f.blocks[2].insts[0] { Inst::Mov(d, _) => d, _ => unreachable!(), }; f.blocks[5].insts.insert(0, Inst::Iconst(t, 0)); f.blocks[5].pos.insert(0, 1); let (orig, new) = versioned(f); let cold = |b: u32| matches!(new.blocks[b as usize].term, Term::Unreachable); let clone_checks = new.blocks[8..].iter().filter(|b| matches!(b.term, Term::Branch(_, t, e) if cold(t) || cold(e))).count(); assert_eq!(clone_checks, 0); run_cases(&orig, &new); } /// Offsets with loop-invariant vregs (2D stencil rows): positive, negative and wrapping offsets. #[test] fn symbolic_offsets() { for k in [0i64, 1, -1, 3] { let (orig, new) = versioned(axpy_sym(k, true, true)); let mws: Vec<(u64, u64)> = vec![(0, 0), (5, 0), (0, 5), (5, 5), (8, 3), (3, 8), (0, 1), (1, 0), (40, 2), (u64::MAX, 0), (0, u64::MAX), (u64::MAX - 3, 0)]; run_cases_mw(&orig, &new, &mws); } } /// A counter stepping by 2 (or 3): negative constant and symbolic offsets get the end-based guard /// (`i0 + o <= n + o <= len`, `n <= MAX - step`), the results equal the checked loop's. #[test] fn stepped_counter_offsets() { for step in [2i64, 3] { for (k, sym) in [(-1i64, false), (-2, false), (0, true), (-1, true), (2, true)] { let mut f = axpy_sym(k, true, sym); for i in f.blocks[2].insts.iter_mut() { if let Inst::IBinI(IOp::Add, _, _, _, s) = i { *s = step; } } let (orig, new) = versioned(f); let mws: Vec<(u64, u64)> = if sym { vec![(0, 0), (5, 0), (0, 5), (5, 5), (8, 3), (3, 8), (u64::MAX, 0), (0, u64::MAX)] } else { vec![(0, 0)] }; let before = CLONE_STEPS.with(|c| c.get()); run_cases_mw(&orig, &new, &mws); assert!(CLONE_STEPS.with(|c| c.get()) > before, "the guard never chose the clone (step {step} k {k} sym {sym})"); } } } #[test] fn not_counted_left_alone() { // the bound redefined in the loop: no counted loop, nothing versioned let mut f = axpy(0, true); let n = f.params[4]; push(&mut f, 4, Inst::IBinI(IOp::Add, U64, n, n, 0)); let before = f.blocks.len(); assert!(!version::version_bounds_loops(&relax_session::Options::default(), &mut f)); assert_eq!(f.blocks.len(), before); } #[test] fn stale_read_after_increment_not_proved() { // the x index reads i after the increment (i + 0 is the next value): it may equal n, so the // check stays in the clone; the y check (fresh t) is still versioned let mut f = axpy(0, true); let i = match f.blocks[0].insts[0] { Inst::Mov(d, _) => d, _ => unreachable!(), }; let xi = match f.blocks[3].insts[0] { Inst::IBinI(_, _, d, _, _) => d, _ => unreachable!(), }; f.blocks[3].insts[0] = Inst::IBinI(IOp::Add, U64, xi, i, 0); let (orig, new) = versioned(f); let cold = |b: u32| matches!(new.blocks[b as usize].term, Term::Unreachable); let clone_checks = new.blocks[8..].iter().filter(|b| matches!(b.term, Term::Branch(_, t, e) if cold(t) || cold(e))).count(); assert_eq!(clone_checks, 1); // memory comparison: the x read at i reaches index n, inside the 128-word buffer run_cases(&orig, &new); } /// The clone of `y[i] += k * x[i]` after rotation (one block): the stream-map vectoriser must take it. #[test] fn clone_shape_vectorises() { let mut f = Func::new("axpy_clone".into(), 0); let p: Vec = (0..4).map(|_| f.vreg(Cls::I)).collect(); let k = f.vreg(Cls::F32); let (y, ylen, x, _xlen) = (p[0], p[1], p[2], p[3]); f.params.extend([p[0], p[1], p[2], p[3], k]); for _ in 0..4 { f.block(); } let i = f.vreg(Cls::I); let (c0, t, i2, off, xa, xv, m, ya, yv, s, c1) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::F32), f.vreg(Cls::F32), f.vreg(Cls::I), f.vreg(Cls::F32), f.vreg(Cls::F32), f.vreg(Cls::I)); push(&mut f, 0, Inst::Iconst(i, 0)); push(&mut f, 0, Inst::ICmp(Cond::Lt, false, c0, i, ylen)); term(&mut f, 0, Term::Branch(c0, 1, 2)); push(&mut f, 1, Inst::Mov(t, i)); push(&mut f, 1, Inst::IBinI(IOp::Add, U64, i2, i, 1)); push(&mut f, 1, Inst::Mov(i, i2)); push(&mut f, 1, Inst::IBinI(IOp::Shl, U64, off, t, 2)); push(&mut f, 1, Inst::IBin(IOp::Add, U64, xa, x, off)); push(&mut f, 1, Inst::Load(Mem::F32, xv, xa, 0)); push(&mut f, 1, Inst::FBin(FOp::Mul, false, m, k, xv)); push(&mut f, 1, Inst::IBin(IOp::Add, U64, ya, y, off)); push(&mut f, 1, Inst::Load(Mem::F32, yv, ya, 0)); push(&mut f, 1, Inst::FBin(FOp::Add, false, s, yv, m)); push(&mut f, 1, Inst::Store(Mem::F32, ya, 0, s)); push(&mut f, 1, Inst::ICmp(Cond::Lt, false, c1, i, ylen)); term(&mut f, 1, Term::Branch(c1, 1, 2)); term(&mut f, 2, Term::Ret(vec![])); let mut g = f.clone(); let n0 = f.blocks.len(); let ch = relax_codegen::loops::vectorize_reductions(&relax_session::Options::default(), &mut f); assert!(ch && f.blocks.len() > n0, "vectorised"); // t read in an unreachable block outside the loop (an original loop's panic block) let b = g.block(); push(&mut g, b, Inst::Call(Callee::Host(Sym { id: 5, off: 0 }), vec![t, ylen], Vec::new())); term(&mut g, b, Term::Unreachable); let n0 = g.blocks.len(); let ch = relax_codegen::loops::vectorize_reductions(&relax_session::Options::default(), &mut g); eprintln!("with outside read of t: vectorised {}", ch && g.blocks.len() > n0); } /// `for i in 0..n { y[i] += if flag { 1 } else { x[i] } }` with flag a param: two loops, chosen once. #[test] fn unswitch_invariant_branch() { let mut f = Func::new("unsw".into(), 0); let p: Vec = (0..5).map(|_| f.vreg(Cls::I)).collect(); let (y, x, n, flag, _) = (p[0], p[1], p[2], p[3], p[4]); f.params.extend([p[0], p[1], p[2], p[3]]); for _ in 0..6 { f.block(); } let (i, c, off, ya, yv, xa, xv, s, one, z) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I)); push(&mut f, 0, Inst::Iconst(i, 0)); term(&mut f, 0, Term::Jump(1)); push(&mut f, 1, Inst::ICmp(Cond::Lt, false, c, i, n)); term(&mut f, 1, Term::Branch(c, 2, 5)); push(&mut f, 2, Inst::IBinI(IOp::Shl, U64, off, i, 2)); push(&mut f, 2, Inst::IBin(IOp::Add, U64, ya, y, off)); push(&mut f, 2, Inst::Load(Mem::Int(4, false), yv, ya, 0)); term(&mut f, 2, Term::Branch(flag, 3, 4)); push(&mut f, 3, Inst::Iconst(one, 1)); push(&mut f, 3, Inst::IBin(IOp::Add, U64, s, yv, one)); push(&mut f, 3, Inst::Store(Mem::Int(4, false), ya, 0, s)); push(&mut f, 3, Inst::IBinI(IOp::Add, U64, i, i, 1)); term(&mut f, 3, Term::Jump(1)); push(&mut f, 4, Inst::IBin(IOp::Add, U64, xa, x, off)); push(&mut f, 4, Inst::Load(Mem::Int(4, false), xv, xa, 0)); push(&mut f, 4, Inst::IBin(IOp::Add, U64, z, yv, xv)); push(&mut f, 4, Inst::Store(Mem::Int(4, false), ya, 0, z)); push(&mut f, 4, Inst::IBinI(IOp::Add, U64, i, i, 1)); term(&mut f, 4, Term::Jump(1)); f.rets.push(Cls::I); term(&mut f, 5, Term::Ret(vec![i])); let orig = f.clone(); assert!(version::unswitch_loops(&relax_session::Options::default(), &mut f)); // neither copy branches on flag any more let reach = reachable(&f); assert!(!f.blocks.iter().enumerate().any(|(b, bl)| reach[b] && matches!(bl.term, Term::Branch(c, _, _) if c == flag))); let mut mem = vec![0u8; 512]; for j in 0..128u32 { mem[j as usize * 4..j as usize * 4 + 4].copy_from_slice(&(j * 3 + 2).to_le_bytes()); } for n in [0u64, 1, 7, 64] { for fl in [0u64, 1, 2] { let args = [0, 256, n, fl]; assert_eq!(eval(&orig, &args, &mem), eval(&f, &args, &mem), "n {n} flag {fl}"); } } } /// `out[i] = a[i].wrapping_mul(3) ^ b[i] >> 1` (u32) after versioning and rotation: one block, a /// constant shift among the lane operations; the stream-map vectoriser takes it. #[test] fn u32_map_with_shift_vectorises() { let mut f = Func::new("mix_clone".into(), 0); let p: Vec = (0..4).map(|_| f.vreg(Cls::I)).collect(); let (out, a, b, n) = (p[0], p[1], p[2], p[3]); f.params.extend([out, a, b, n]); for _ in 0..3 { f.block(); } let i = f.vreg(Cls::I); let (c0, t, i2, off, aa, av, m, ba, bv, sh, x, oa, c1) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I)); let u32t = IntTy { bits: 32, signed: false }; push(&mut f, 0, Inst::Iconst(i, 0)); push(&mut f, 0, Inst::ICmp(Cond::Lt, false, c0, i, n)); term(&mut f, 0, Term::Branch(c0, 1, 2)); push(&mut f, 1, Inst::Mov(t, i)); push(&mut f, 1, Inst::IBinI(IOp::Add, U64, i2, i, 1)); push(&mut f, 1, Inst::Mov(i, i2)); push(&mut f, 1, Inst::IBinI(IOp::Shl, U64, off, t, 2)); push(&mut f, 1, Inst::IBin(IOp::Add, U64, aa, a, off)); push(&mut f, 1, Inst::Load(Mem::Int(4, false), av, aa, 0)); push(&mut f, 1, Inst::IBinI(IOp::Mul, u32t, m, av, 3)); push(&mut f, 1, Inst::IBin(IOp::Add, U64, ba, b, off)); push(&mut f, 1, Inst::Load(Mem::Int(4, false), bv, ba, 0)); push(&mut f, 1, Inst::IBinI(IOp::Shr, u32t, sh, bv, 1)); push(&mut f, 1, Inst::IBin(IOp::Xor, u32t, x, m, sh)); push(&mut f, 1, Inst::IBin(IOp::Add, U64, oa, out, off)); push(&mut f, 1, Inst::Store(Mem::Int(4, false), oa, 0, x)); push(&mut f, 1, Inst::ICmp(Cond::Lt, false, c1, i, n)); term(&mut f, 1, Term::Branch(c1, 1, 2)); term(&mut f, 2, Term::Ret(vec![])); let n0 = f.blocks.len(); let ch = relax_codegen::loops::vectorize_reductions(&relax_session::Options::default(), &mut f); assert!(ch && f.blocks.len() > n0, "vectorised"); assert!(f.blocks.iter().any(|b| b.insts.iter().any(|i| matches!(i, Inst::VX(VX::ShrUI(_, 1), ..))))); } /// `base = if a.cmp(&b) == Greater { base } else { mid }` (binary_search's step): the Ordering is a /// diamond (`-1` on one arm, `a == b ? 0 : 1` on the other) narrowed to i8 and compared with 1. /// simplify must leave no branch (the arms are speculated, the compare distributed over the /// Ordering's assignments) and compute the same results. #[test] fn ordering_diamond_becomes_selects() { let mut f = Func::new("ord".into(), 0); let p: Vec = (0..4).map(|_| f.vreg(Cls::I)).collect(); f.params.extend(p.iter().copied()); let (a, b, base, mid) = (p[0], p[1], p[2], p[3]); for _ in 0..4 { f.block(); } let (c, o, e, z, one, t, o8, g, r) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I)); push(&mut f, 0, Inst::Iconst(z, 0)); push(&mut f, 0, Inst::Iconst(one, 1)); push(&mut f, 0, Inst::ICmp(Cond::Lt, false, c, a, b)); term(&mut f, 0, Term::Branch(c, 1, 2)); push(&mut f, 1, Inst::Iconst(o, -1)); term(&mut f, 1, Term::Jump(3)); push(&mut f, 2, Inst::ICmp(Cond::Eq, false, e, a, b)); push(&mut f, 2, Inst::Sel(t, e, z, one)); push(&mut f, 2, Inst::Mov(o, t)); term(&mut f, 2, Term::Jump(3)); push(&mut f, 3, Inst::Conv(Conv::IntToInt(IntTy { bits: 8, signed: true }), o8, o)); push(&mut f, 3, Inst::ICmpI(Cond::Eq, true, g, o8, 1)); push(&mut f, 3, Inst::Sel(r, g, base, mid)); f.rets.push(Cls::I); term(&mut f, 3, Term::Ret(vec![r])); let orig = f.clone(); relax_backend::passes::simplify(&relax_session::Options::default(), &mut f, None, true, true); relax_backend::passes::simplify(&relax_session::Options::default(), &mut f, None, true, true); let reach = reachable(&f); let branches = f.blocks.iter().enumerate().filter(|(bi, bl)| reach[*bi] && matches!(bl.term, Term::Branch(..))).count(); for x in [0u64, 1, 5, 9, u64::MAX] { for y in [0u64, 1, 5, 9, u64::MAX] { let args = [x, y, 100, 200]; assert_eq!(eval(&orig, &args, &[]), eval(&f, &args, &[]), "a {x} b {y}"); } } // one compare (`a <= b`) and one select remain let live: usize = f.blocks.iter().enumerate().filter(|(bi, _)| reach[*bi]).map(|(_, b)| b.insts.len()).sum(); assert!(live <= 2, "left: {:?}", f.blocks.iter().map(|b| &b.insts).collect::>()); assert_eq!(branches, 0, "branch left:\n{:?}", f.blocks.iter().map(|b| (&b.insts, &b.term)).collect::>()); } /// The same step once the Ordering is already a select tree (`a < b ? -1 : (a == b ? 0 : 1)`, /// narrowed to i8, compared with 1): one compare and one select remain. #[test] fn ordering_select_tree_folds() { let mut f = Func::new("ord2".into(), 0); let p: Vec = (0..4).map(|_| f.vreg(Cls::I)).collect(); f.params.extend(p.iter().copied()); let (a, b, base, mid) = (p[0], p[1], p[2], p[3]); f.block(); let v: Vec = (0..10).map(|_| f.vreg(Cls::I)).collect(); let (m1, z, one, lt, eq, t, o, o8, g, r) = (v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]); push(&mut f, 0, Inst::Iconst(m1, -1)); push(&mut f, 0, Inst::Iconst(z, 0)); push(&mut f, 0, Inst::Iconst(one, 1)); push(&mut f, 0, Inst::ICmp(Cond::Lt, false, lt, a, b)); push(&mut f, 0, Inst::ICmp(Cond::Eq, false, eq, a, b)); push(&mut f, 0, Inst::Sel(t, eq, z, one)); push(&mut f, 0, Inst::Sel(o, lt, m1, t)); push(&mut f, 0, Inst::Conv(Conv::IntToInt(IntTy { bits: 8, signed: true }), o8, o)); push(&mut f, 0, Inst::ICmpI(Cond::Eq, true, g, o8, 1)); push(&mut f, 0, Inst::Sel(r, g, base, mid)); f.rets.push(Cls::I); term(&mut f, 0, Term::Ret(vec![r])); let orig = f.clone(); for _ in 0..2 { relax_backend::passes::simplify(&relax_session::Options::default(), &mut f, None, true, true); } for x in [0u64, 1, 5, 9, u64::MAX] { for y in [0u64, 1, 5, 9, u64::MAX] { let args = [x, y, 100, 200]; assert_eq!(eval(&orig, &args, &[]), eval(&f, &args, &[]), "a {x} b {y}"); } } let live: usize = f.blocks.iter().map(|b| b.insts.len()).sum(); assert!(live <= 2, "left: {:?}", f.blocks.iter().map(|b| &b.insts).collect::>()); } /// `x % c == 0` and `x % c != 0` (u32 and u64) become a multiply by c's inverse (and a rotate for even /// c) and an unsigned compare; exact for every tested x. #[test] fn divisibility_tests_fold() { for bits in [32u8, 64] { for c in [3u64, 5, 6, 7, 10, 12, 24, 100, 641, 1000, 65535, 0x7fff_ffff] { for eq in [true, false] { let it = IntTy { bits, signed: false }; let mut f = Func::new("rem".into(), 0); let x = f.vreg(Cls::I); f.params.push(x); f.block(); let (kc, r, d) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I)); push(&mut f, 0, Inst::Iconst(kc, c as i64)); push(&mut f, 0, Inst::IBin(IOp::Rem, it, r, x, kc)); push(&mut f, 0, Inst::ICmpI(if eq { Cond::Eq } else { Cond::Ne }, false, d, r, 0)); f.rets.push(Cls::I); term(&mut f, 0, Term::Ret(vec![d])); let orig = f.clone(); relax_backend::passes::simplify(&relax_session::Options::default(), &mut f, None, true, true); assert!(!f.blocks[0].insts.iter().any(|i| matches!(i, Inst::IBin(IOp::Rem | IOp::MulHi, ..))), "c {c} bits {bits}: {:?}", f.blocks[0].insts); let m = if bits == 64 { u64::MAX } else { (1u64 << bits) - 1 }; let mut xs: Vec = vec![0, 1, 2, c - 1, c, c + 1, 2 * c, 3 * c - 1, m, m - 1, m / c * c, m / c * c + 1]; let mut s = 0x9E37_79B9_7F4A_7C15u64; for _ in 0..2000 { s ^= s << 13; s ^= s >> 7; s ^= s << 17; xs.push(s & m); xs.push((s % 1000) * c & m); } for xv in xs.iter().map(|v| v & m) { assert_eq!(eval(&orig, &[xv], &[]), eval(&f, &[xv], &[]), "x {xv} c {c} bits {bits} eq {eq}"); } } } } } /// `c ? 1 : 0` and `c ? 0 : 1` of a compare: c and c ^ 1 (no select left); x / 1 is x and x % 1 is 0. #[test] fn bool_selects_and_unit_divisors_fold() { for (k1, k0) in [(1i64, 0i64), (0, 1)] { let mut f = Func::new("sel01".into(), 0); let (a, b) = (f.vreg(Cls::I), f.vreg(Cls::I)); f.params.extend([a, b]); f.block(); let v: Vec = (0..8).map(|_| f.vreg(Cls::I)).collect(); push(&mut f, 0, Inst::Iconst(v[0], k1)); push(&mut f, 0, Inst::Iconst(v[1], k0)); push(&mut f, 0, Inst::ICmp(Cond::Lt, false, v[2], a, b)); push(&mut f, 0, Inst::Sel(v[3], v[2], v[0], v[1])); push(&mut f, 0, Inst::Iconst(v[4], 1)); push(&mut f, 0, Inst::IBin(IOp::Div, U64, v[5], a, v[4])); push(&mut f, 0, Inst::IBin(IOp::Rem, IntTy { bits: 32, signed: true }, v[6], b, v[4])); push(&mut f, 0, Inst::IBin(IOp::Add, U64, v[7], v[3], v[5])); f.rets.extend([Cls::I, Cls::I]); term(&mut f, 0, Term::Ret(vec![v[7], v[6]])); let orig = f.clone(); relax_backend::passes::simplify(&relax_session::Options::default(), &mut f, None, true, true); assert!(!f.blocks[0].insts.iter().any(|i| matches!(i, Inst::Sel(..) | Inst::IBin(IOp::Div | IOp::Rem, ..))), "{:?}", f.blocks[0].insts); for x in [0u64, 1, 5, 9, u64::MAX] { for y in [0u64, 1, 5, 9, (-3i64) as u64] { assert_eq!(eval(&orig, &[x, y], &[]), eval(&f, &[x, y], &[]), "a {x} b {y} k1 {k1}"); } } } } /// A float load read only by FToBits becomes an integer load (f32 and f64), and an integer /// load read only by BitsToF a float load. #[test] fn float_loads_read_as_bits_load_integers() { for (fm, w, im) in [(Mem::F32, false, Mem::Int(4, false)), (Mem::F64, true, Mem::Int(8, false))] { let mut f = Func::new("lb".into(), 0); let p = f.vreg(Cls::I); f.params.push(p); f.block(); let x = f.vreg(if w { Cls::F64 } else { Cls::F32 }); let (d, y) = (f.vreg(Cls::I), f.vreg(Cls::I)); let z = f.vreg(if w { Cls::F64 } else { Cls::F32 }); push(&mut f, 0, Inst::Load(fm, x, p, 8)); push(&mut f, 0, Inst::Conv(Conv::FToBits(w), d, x)); push(&mut f, 0, Inst::Load(im, y, p, 16)); push(&mut f, 0, Inst::Conv(Conv::BitsToF(w), z, y)); f.rets.extend([Cls::I, if w { Cls::F64 } else { Cls::F32 }]); term(&mut f, 0, Term::Ret(vec![d, z])); relax_backend::passes::simplify(&relax_session::Options::default(), &mut f, None, true, true); let insts = &f.blocks[0].insts; assert!(!insts.iter().any(|i| matches!(i, Inst::Conv(..))), "{insts:?}"); assert!(insts.iter().any(|i| matches!(i, Inst::Load(m, _, _, 8) if *m == im)), "{insts:?}"); assert!(insts.iter().any(|i| matches!(i, Inst::Load(m, _, _, 16) if *m == fm)), "{insts:?}"); } } /// Lomuto's cyclic step: `*gap = *left; *left = *right; gap = right; right += 4` with gap entering /// as right - 4: the gap's reads become `right - 4`, the memory and result do not change, and the /// store through the gap shares right's base. #[test] fn previous_iv_copy_reads_the_stepped_pointer() { let mut f = Func::new("gap".into(), 0); let (base, end) = (f.vreg(Cls::I), f.vreg(Cls::I)); f.params.extend([base, end]); for _ in 0..4 { f.block(); } let v: Vec = (0..8).map(|_| f.vreg(Cls::I)).collect(); let (g, r, c, x, y, left) = (v[0], v[1], v[2], v[3], v[4], v[5]); // entry: gap = base, right = base + 4, left = base + 40 push(&mut f, 0, Inst::Mov(g, base)); push(&mut f, 0, Inst::IBinI(IOp::Add, U64, r, base, 4)); push(&mut f, 0, Inst::IBinI(IOp::Add, U64, left, base, 40)); term(&mut f, 0, Term::Jump(1)); push(&mut f, 1, Inst::ICmp(Cond::Lt, false, c, r, end)); term(&mut f, 1, Term::Branch(c, 2, 3)); push(&mut f, 2, Inst::Load(Mem::Int(4, false), x, left, 0)); push(&mut f, 2, Inst::Store(Mem::Int(4, false), g, 0, x)); push(&mut f, 2, Inst::Load(Mem::Int(4, false), y, r, 0)); push(&mut f, 2, Inst::Store(Mem::Int(4, false), left, 0, y)); push(&mut f, 2, Inst::Mov(g, r)); push(&mut f, 2, Inst::IBinI(IOp::Add, U64, r, r, 4)); term(&mut f, 2, Term::Jump(1)); f.rets.push(Cls::I); term(&mut f, 3, Term::Ret(vec![g])); let orig = f.clone(); assert!(version::prev_iv_copies(&relax_session::Options::default(), &mut f)); assert!(f.blocks[2].insts.iter().any(|i| matches!(i, Inst::IBinI(IOp::Add, _, _, rr, -4) if *rr == r)), "{:?}", f.blocks[2].insts); assert!(!version::prev_iv_copies(&relax_session::Options::default(), &mut f), "a second round finds nothing"); let mem0: Vec = (0..64u8).collect(); for n in [0u64, 1, 2, 5, 8] { let args = [0u64, 4 + 4 * n]; assert_eq!(eval(&orig, &args, &mem0), eval(&f, &args, &mem0), "n {n}"); } // the step twice per iteration (lomuto's source unrolling): both copies' reads rewritten let mut u = orig.clone(); let body = u.blocks[2].insts.clone(); u.blocks[2].insts.extend(body); u.blocks[2].pos = vec![1; u.blocks[2].insts.len()]; let u0 = u.clone(); assert!(version::prev_iv_copies(&relax_session::Options::default(), &mut u)); let n_rewrites = u.blocks[2].insts.iter().filter(|i| matches!(i, Inst::IBinI(IOp::Add, _, _, rr, -4) if *rr == r)).count(); assert_eq!(n_rewrites, 2, "{:?}", u.blocks[2].insts); for n in [0u64, 2, 4, 6] { let args = [0u64, 4 + 4 * n]; assert_eq!(eval(&u0, &args, &mem0), eval(&u, &args, &mem0), "unrolled n {n}"); } // entry offset that does not match the step: left alone let mut h = orig.clone(); h.blocks[0].insts[1] = Inst::IBinI(IOp::Add, U64, r, base, 8); assert!(!version::prev_iv_copies(&relax_session::Options::default(), &mut h)); }