#![allow(non_snake_case)]
use cursor::{Cursor, FuncCursor};
use divconst_magic_numbers::{magicS32, magicS64, magicU32, magicU64};
use divconst_magic_numbers::{MS32, MS64, MU32, MU64};
use ir::dfg::ValueDef;
use ir::instructions::Opcode;
use ir::types::{I32, I64};
use ir::Inst;
use ir::{DataFlowGraph, Function, InstBuilder, InstructionData, Type, Value};
use timing;
#[inline]
fn isPowerOf2_S32(x: i32) -> Option<(bool, u32)> {
if x == -0x8000_0000 {
return Some((true, 31));
}
let abs_x = i32::wrapping_abs(x) as u32;
if abs_x.is_power_of_two() {
return Some((x < 0, abs_x.trailing_zeros()));
}
None
}
#[inline]
fn isPowerOf2_S64(x: i64) -> Option<(bool, u32)> {
if x == -0x8000_0000_0000_0000 {
return Some((true, 63));
}
let abs_x = i64::wrapping_abs(x) as u64;
if abs_x.is_power_of_two() {
return Some((x < 0, abs_x.trailing_zeros()));
}
None
}
#[derive(Debug)]
enum DivRemByConstInfo {
DivU32(Value, u32), DivU64(Value, u64), DivS32(Value, i32),
DivS64(Value, i64),
RemU32(Value, u32),
RemU64(Value, u64),
RemS32(Value, i32),
RemS64(Value, i64),
}
fn package_up_divrem_info(
argL: Value,
argL_ty: Type,
argRs: i64,
isSigned: bool,
isRem: bool,
) -> Option<DivRemByConstInfo> {
let argRu: u64 = argRs as u64;
if !isSigned && argL_ty == I32 && argRu < 0x1_0000_0000 {
let con = if isRem {
DivRemByConstInfo::RemU32
} else {
DivRemByConstInfo::DivU32
};
return Some(con(argL, argRu as u32));
}
if !isSigned && argL_ty == I64 {
let con = if isRem {
DivRemByConstInfo::RemU64
} else {
DivRemByConstInfo::DivU64
};
return Some(con(argL, argRu));
}
if isSigned && argL_ty == I32 && (argRu <= 0x7fff_ffff || argRu >= 0xffff_ffff_8000_0000) {
let con = if isRem {
DivRemByConstInfo::RemS32
} else {
DivRemByConstInfo::DivS32
};
return Some(con(argL, argRu as i32));
}
if isSigned && argL_ty == I64 {
let con = if isRem {
DivRemByConstInfo::RemS64
} else {
DivRemByConstInfo::DivS64
};
return Some(con(argL, argRu as i64));
}
None
}
fn get_div_info(inst: Inst, dfg: &DataFlowGraph) -> Option<DivRemByConstInfo> {
let idata: &InstructionData = &dfg[inst];
if let InstructionData::BinaryImm { opcode, arg, imm } = *idata {
let (isSigned, isRem) = match opcode {
Opcode::UdivImm => (false, false),
Opcode::UremImm => (false, true),
Opcode::SdivImm => (true, false),
Opcode::SremImm => (true, true),
_other => return None,
};
let argL_ty = dfg.value_type(arg);
return package_up_divrem_info(arg, argL_ty, imm.into(), isSigned, isRem);
}
None
}
fn do_divrem_transformation(divrem_info: &DivRemByConstInfo, pos: &mut FuncCursor, inst: Inst) {
let isRem = match *divrem_info {
DivRemByConstInfo::DivU32(_, _)
| DivRemByConstInfo::DivU64(_, _)
| DivRemByConstInfo::DivS32(_, _)
| DivRemByConstInfo::DivS64(_, _) => false,
DivRemByConstInfo::RemU32(_, _)
| DivRemByConstInfo::RemU64(_, _)
| DivRemByConstInfo::RemS32(_, _)
| DivRemByConstInfo::RemS64(_, _) => true,
};
match *divrem_info {
DivRemByConstInfo::DivU32(_n1, 0) | DivRemByConstInfo::RemU32(_n1, 0) => {}
DivRemByConstInfo::DivU32(n1, 1) | DivRemByConstInfo::RemU32(n1, 1) => {
if isRem {
pos.func.dfg.replace(inst).iconst(I32, 0);
} else {
pos.func.dfg.replace(inst).copy(n1);
}
}
DivRemByConstInfo::DivU32(n1, d) | DivRemByConstInfo::RemU32(n1, d)
if d.is_power_of_two() =>
{
debug_assert!(d >= 2);
let k = d.trailing_zeros();
debug_assert!(k >= 1 && k <= 31);
if isRem {
let mask = (1u64 << k) - 1;
pos.func.dfg.replace(inst).band_imm(n1, mask as i64);
} else {
pos.func.dfg.replace(inst).ushr_imm(n1, k as i64);
}
}
DivRemByConstInfo::DivU32(n1, d) | DivRemByConstInfo::RemU32(n1, d) => {
debug_assert!(d >= 3);
let MU32 {
mulBy,
doAdd,
shiftBy,
} = magicU32(d);
let qf; let q0 = pos.ins().iconst(I32, mulBy as i64);
let q1 = pos.ins().umulhi(n1, q0);
if doAdd {
debug_assert!(shiftBy >= 1 && shiftBy <= 32);
let t1 = pos.ins().isub(n1, q1);
let t2 = pos.ins().ushr_imm(t1, 1);
let t3 = pos.ins().iadd(t2, q1);
debug_assert_ne!(shiftBy, 1);
qf = pos.ins().ushr_imm(t3, (shiftBy - 1) as i64);
} else {
debug_assert!(shiftBy >= 0 && shiftBy <= 31);
if shiftBy > 0 {
qf = pos.ins().ushr_imm(q1, shiftBy as i64);
} else {
qf = q1;
}
}
if isRem {
let tt = pos.ins().imul_imm(qf, d as i64);
pos.func.dfg.replace(inst).isub(n1, tt);
} else {
pos.func.dfg.replace(inst).copy(qf);
}
}
DivRemByConstInfo::DivU64(_n1, 0) | DivRemByConstInfo::RemU64(_n1, 0) => {}
DivRemByConstInfo::DivU64(n1, 1) | DivRemByConstInfo::RemU64(n1, 1) => {
if isRem {
pos.func.dfg.replace(inst).iconst(I64, 0);
} else {
pos.func.dfg.replace(inst).copy(n1);
}
}
DivRemByConstInfo::DivU64(n1, d) | DivRemByConstInfo::RemU64(n1, d)
if d.is_power_of_two() =>
{
debug_assert!(d >= 2);
let k = d.trailing_zeros();
debug_assert!(k >= 1 && k <= 63);
if isRem {
let mask = (1u64 << k) - 1;
pos.func.dfg.replace(inst).band_imm(n1, mask as i64);
} else {
pos.func.dfg.replace(inst).ushr_imm(n1, k as i64);
}
}
DivRemByConstInfo::DivU64(n1, d) | DivRemByConstInfo::RemU64(n1, d) => {
debug_assert!(d >= 3);
let MU64 {
mulBy,
doAdd,
shiftBy,
} = magicU64(d);
let qf; let q0 = pos.ins().iconst(I64, mulBy as i64);
let q1 = pos.ins().umulhi(n1, q0);
if doAdd {
debug_assert!(shiftBy >= 1 && shiftBy <= 64);
let t1 = pos.ins().isub(n1, q1);
let t2 = pos.ins().ushr_imm(t1, 1);
let t3 = pos.ins().iadd(t2, q1);
debug_assert_ne!(shiftBy, 1);
qf = pos.ins().ushr_imm(t3, (shiftBy - 1) as i64);
} else {
debug_assert!(shiftBy >= 0 && shiftBy <= 63);
if shiftBy > 0 {
qf = pos.ins().ushr_imm(q1, shiftBy as i64);
} else {
qf = q1;
}
}
if isRem {
let tt = pos.ins().imul_imm(qf, d as i64);
pos.func.dfg.replace(inst).isub(n1, tt);
} else {
pos.func.dfg.replace(inst).copy(qf);
}
}
DivRemByConstInfo::DivS32(_n1, -1)
| DivRemByConstInfo::RemS32(_n1, -1)
| DivRemByConstInfo::DivS32(_n1, 0)
| DivRemByConstInfo::RemS32(_n1, 0) => {}
DivRemByConstInfo::DivS32(n1, 1) | DivRemByConstInfo::RemS32(n1, 1) => {
if isRem {
pos.func.dfg.replace(inst).iconst(I32, 0);
} else {
pos.func.dfg.replace(inst).copy(n1);
}
}
DivRemByConstInfo::DivS32(n1, d) | DivRemByConstInfo::RemS32(n1, d) => {
if let Some((isNeg, k)) = isPowerOf2_S32(d) {
debug_assert!(k >= 1 && k <= 31);
let t1 = if k - 1 == 0 {
n1
} else {
pos.ins().sshr_imm(n1, (k - 1) as i64)
};
let t2 = pos.ins().ushr_imm(t1, (32 - k) as i64);
let t3 = pos.ins().iadd(n1, t2);
if isRem {
let t4 = pos.ins().band_imm(t3, i32::wrapping_neg(1 << k) as i64);
pos.func.dfg.replace(inst).isub(n1, t4);
} else {
let t4 = pos.ins().sshr_imm(t3, k as i64);
if isNeg {
pos.func.dfg.replace(inst).irsub_imm(t4, 0);
} else {
pos.func.dfg.replace(inst).copy(t4);
}
}
} else {
debug_assert!(d < -2 || d > 2);
let MS32 { mulBy, shiftBy } = magicS32(d);
let q0 = pos.ins().iconst(I32, mulBy as i64);
let q1 = pos.ins().smulhi(n1, q0);
let q2 = if d > 0 && mulBy < 0 {
pos.ins().iadd(q1, n1)
} else if d < 0 && mulBy > 0 {
pos.ins().isub(q1, n1)
} else {
q1
};
debug_assert!(shiftBy >= 0 && shiftBy <= 31);
let q3 = if shiftBy == 0 {
q2
} else {
pos.ins().sshr_imm(q2, shiftBy as i64)
};
let t1 = pos.ins().ushr_imm(q3, 31);
let qf = pos.ins().iadd(q3, t1);
if isRem {
let tt = pos.ins().imul_imm(qf, d as i64);
pos.func.dfg.replace(inst).isub(n1, tt);
} else {
pos.func.dfg.replace(inst).copy(qf);
}
}
}
DivRemByConstInfo::DivS64(_n1, -1)
| DivRemByConstInfo::RemS64(_n1, -1)
| DivRemByConstInfo::DivS64(_n1, 0)
| DivRemByConstInfo::RemS64(_n1, 0) => {}
DivRemByConstInfo::DivS64(n1, 1) | DivRemByConstInfo::RemS64(n1, 1) => {
if isRem {
pos.func.dfg.replace(inst).iconst(I64, 0);
} else {
pos.func.dfg.replace(inst).copy(n1);
}
}
DivRemByConstInfo::DivS64(n1, d) | DivRemByConstInfo::RemS64(n1, d) => {
if let Some((isNeg, k)) = isPowerOf2_S64(d) {
debug_assert!(k >= 1 && k <= 63);
let t1 = if k - 1 == 0 {
n1
} else {
pos.ins().sshr_imm(n1, (k - 1) as i64)
};
let t2 = pos.ins().ushr_imm(t1, (64 - k) as i64);
let t3 = pos.ins().iadd(n1, t2);
if isRem {
let t4 = pos.ins().band_imm(t3, i64::wrapping_neg(1 << k));
pos.func.dfg.replace(inst).isub(n1, t4);
} else {
let t4 = pos.ins().sshr_imm(t3, k as i64);
if isNeg {
pos.func.dfg.replace(inst).irsub_imm(t4, 0);
} else {
pos.func.dfg.replace(inst).copy(t4);
}
}
} else {
debug_assert!(d < -2 || d > 2);
let MS64 { mulBy, shiftBy } = magicS64(d);
let q0 = pos.ins().iconst(I64, mulBy);
let q1 = pos.ins().smulhi(n1, q0);
let q2 = if d > 0 && mulBy < 0 {
pos.ins().iadd(q1, n1)
} else if d < 0 && mulBy > 0 {
pos.ins().isub(q1, n1)
} else {
q1
};
debug_assert!(shiftBy >= 0 && shiftBy <= 63);
let q3 = if shiftBy == 0 {
q2
} else {
pos.ins().sshr_imm(q2, shiftBy as i64)
};
let t1 = pos.ins().ushr_imm(q3, 63);
let qf = pos.ins().iadd(q3, t1);
if isRem {
let tt = pos.ins().imul_imm(qf, d);
pos.func.dfg.replace(inst).isub(n1, tt);
} else {
pos.func.dfg.replace(inst).copy(qf);
}
}
}
}
}
fn simplify(pos: &mut FuncCursor, inst: Inst) {
match pos.func.dfg[inst] {
InstructionData::Binary { opcode, args } => {
if let ValueDef::Result(iconst_inst, _) = pos.func.dfg.value_def(args[1]) {
if let InstructionData::UnaryImm {
opcode: Opcode::Iconst,
mut imm,
} = pos.func.dfg[iconst_inst]
{
let new_opcode = match opcode {
Opcode::Iadd => Opcode::IaddImm,
Opcode::Imul => Opcode::ImulImm,
Opcode::Sdiv => Opcode::SdivImm,
Opcode::Udiv => Opcode::UdivImm,
Opcode::Srem => Opcode::SremImm,
Opcode::Urem => Opcode::UremImm,
Opcode::Band => Opcode::BandImm,
Opcode::Bor => Opcode::BorImm,
Opcode::Bxor => Opcode::BxorImm,
Opcode::Rotl => Opcode::RotlImm,
Opcode::Rotr => Opcode::RotrImm,
Opcode::Ishl => Opcode::IshlImm,
Opcode::Ushr => Opcode::UshrImm,
Opcode::Sshr => Opcode::SshrImm,
Opcode::Isub => {
imm = imm.wrapping_neg();
Opcode::IaddImm
}
_ => return,
};
let ty = pos.func.dfg.ctrl_typevar(inst);
pos.func
.dfg
.replace(inst)
.BinaryImm(new_opcode, ty, imm, args[0]);
}
} else if let ValueDef::Result(iconst_inst, _) = pos.func.dfg.value_def(args[0]) {
if let InstructionData::UnaryImm {
opcode: Opcode::Iconst,
imm,
} = pos.func.dfg[iconst_inst]
{
let new_opcode = match opcode {
Opcode::Isub => Opcode::IrsubImm,
_ => return,
};
let ty = pos.func.dfg.ctrl_typevar(inst);
pos.func
.dfg
.replace(inst)
.BinaryImm(new_opcode, ty, imm, args[1]);
}
}
}
InstructionData::IntCompare { opcode, cond, args } => {
debug_assert_eq!(opcode, Opcode::Icmp);
if let ValueDef::Result(iconst_inst, _) = pos.func.dfg.value_def(args[1]) {
if let InstructionData::UnaryImm {
opcode: Opcode::Iconst,
imm,
} = pos.func.dfg[iconst_inst]
{
pos.func.dfg.replace(inst).icmp_imm(cond, args[0], imm);
}
}
}
InstructionData::CondTrap { .. }
| InstructionData::Branch { .. }
| InstructionData::Ternary {
opcode: Opcode::Select,
..
} => {
let maybe = {
let args = pos.func.dfg.inst_args(inst);
if let ValueDef::Result(def_inst, _) = pos.func.dfg.value_def(args[0]) {
if let InstructionData::Unary {
opcode: Opcode::Bint,
arg: bool_val,
} = pos.func.dfg[def_inst]
{
Some(bool_val)
} else {
None
}
} else {
None
}
};
if let Some(bool_val) = maybe {
let args = pos.func.dfg.inst_args_mut(inst);
args[0] = bool_val;
}
}
_ => {}
}
}
pub fn do_preopt(func: &mut Function) {
let _tt = timing::preopt();
let mut pos = FuncCursor::new(func);
while let Some(_ebb) = pos.next_ebb() {
while let Some(inst) = pos.next_inst() {
simplify(&mut pos, inst);
let mb_dri = get_div_info(inst, &pos.func.dfg);
if let Some(divrem_info) = mb_dri {
do_divrem_transformation(&divrem_info, &mut pos, inst);
continue;
}
}
}
}