81 lines
3.4 KiB
Rust
81 lines
3.4 KiB
Rust
//! `passes::gvn_pure`: a pure value repeated where an equal one dominates it becomes a copy of
|
|
//! it, without local CSE's bounded table; constants, loads, values of another result class,
|
|
//! multi-definition values and repeats in blocks the first one does not dominate stay.
|
|
use relax_backend::passes;
|
|
use relax_backend::rir::*;
|
|
|
|
fn push(f: &mut Func, b: u32, i: Inst) {
|
|
f.blocks[b as usize].insts.push(i);
|
|
f.blocks[b as usize].pos.push(0);
|
|
}
|
|
|
|
fn movs(f: &Func) -> Vec<(VReg, VReg)> {
|
|
f.blocks.iter().flat_map(|b| b.insts.iter()).filter_map(|i| if let Inst::Mov(d, s) = i { Some((*d, *s)) } else { None }).collect()
|
|
}
|
|
|
|
#[test]
|
|
fn repeats_past_the_bounded_table_merge() {
|
|
// more distinct values than local CSE keeps, then each of them again
|
|
let mut f = Func::new("gvn_many".into(), 0);
|
|
let src = f.vreg(Cls::I);
|
|
f.params = vec![src];
|
|
f.block();
|
|
let v = f.vreg(Cls::V128);
|
|
push(&mut f, 0, Inst::VLoad(v, src, 0));
|
|
let mut first = Vec::new();
|
|
for round in 0..2 {
|
|
for k in 0..100i64 {
|
|
let d = f.vreg(Cls::I);
|
|
push(&mut f, 0, Inst::IBinI(IOp::Add, IntTy { bits: 64, signed: true }, d, src, k));
|
|
if round == 0 {
|
|
first.push(d);
|
|
}
|
|
}
|
|
}
|
|
f.blocks[0].term = Term::Ret(vec![]);
|
|
f.verify().unwrap();
|
|
assert!(passes::gvn_pure(&mut f));
|
|
let m = movs(&f);
|
|
assert_eq!(m.len(), 100);
|
|
for (k, (_, s)) in m.iter().enumerate() {
|
|
assert_eq!(*s, first[k]);
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn dominance_classes_constants_and_multi_defs() {
|
|
let mut f = Func::new("gvn_shape".into(), 0);
|
|
let (src, c) = (f.vreg(Cls::I), f.vreg(Cls::I));
|
|
f.params = vec![src, c];
|
|
let b: Vec<u32> = (0..4).map(|_| f.block()).collect();
|
|
let v = f.vreg(Cls::V128);
|
|
let (e0, e_f, k0) = (f.vreg(Cls::I), f.vreg(Cls::F32), f.vreg(Cls::I));
|
|
push(&mut f, b[0], Inst::VLoad(v, src, 0));
|
|
push(&mut f, b[0], Inst::VExtract(e0, v, 1));
|
|
push(&mut f, b[0], Inst::VExtract(e_f, v, 1)); // another class: stays
|
|
push(&mut f, b[0], Inst::Iconst(k0, 7));
|
|
f.blocks[0].term = Term::Branch(c, b[1], b[2]);
|
|
// b1, b2: siblings, each repeats the extract (dominated by b0: merged) and the constant (stays)
|
|
let (e1, k1, s1) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I));
|
|
push(&mut f, b[1], Inst::VExtract(e1, v, 1));
|
|
push(&mut f, b[1], Inst::Iconst(k1, 7));
|
|
push(&mut f, b[1], Inst::IBinI(IOp::Add, IntTy { bits: 64, signed: true }, s1, src, 3));
|
|
f.blocks[1].term = Term::Jump(b[3]);
|
|
let (e2, s2) = (f.vreg(Cls::I), f.vreg(Cls::I));
|
|
push(&mut f, b[2], Inst::VExtract(e2, v, 1));
|
|
// the sibling's value is not available here: stays
|
|
push(&mut f, b[2], Inst::IBinI(IOp::Add, IntTy { bits: 64, signed: true }, s2, src, 3));
|
|
f.blocks[2].term = Term::Jump(b[3]);
|
|
// b3: a multi-def variable's operation repeated: stays
|
|
let (x, y1, y2) = (f.vreg(Cls::I), f.vreg(Cls::I), f.vreg(Cls::I));
|
|
push(&mut f, b[3], Inst::Iconst(x, 1));
|
|
push(&mut f, b[3], Inst::IBinI(IOp::Add, IntTy { bits: 64, signed: true }, y1, x, 1));
|
|
push(&mut f, b[3], Inst::Iconst(x, 2));
|
|
push(&mut f, b[3], Inst::IBinI(IOp::Add, IntTy { bits: 64, signed: true }, y2, x, 1));
|
|
f.blocks[3].term = Term::Ret(vec![]);
|
|
f.verify().unwrap();
|
|
assert!(passes::gvn_pure(&mut f));
|
|
let mut m: Vec<(u32, u32)> = movs(&f).iter().map(|(d, s)| (d.0, s.0)).collect();
|
|
m.sort();
|
|
assert_eq!(m, vec![(e1.0, e0.0), (e2.0, e0.0)]);
|
|
}
|