use crate::bitset::BitSet;
use crate::cursor::{Cursor, FuncCursor};
use crate::flowgraph::ControlFlowGraph;
use crate::ir::types::{I32, I64};
use crate::ir::{self, InstBuilder, MemFlags};
use crate::isa::TargetIsa;
#[cfg(any(
feature = "x86",
feature = "arm32",
feature = "arm64",
feature = "riscv"
))]
use crate::predicates;
#[cfg(any(
feature = "x86",
feature = "arm32",
feature = "arm64",
feature = "riscv"
))]
use alloc::vec::Vec;
use crate::timing;
use alloc::collections::BTreeSet;
mod boundary;
mod call;
mod globalvalue;
mod heap;
mod libcall;
mod split;
mod table;
use self::call::expand_call;
use self::globalvalue::expand_global_value;
use self::heap::expand_heap_addr;
pub(crate) use self::libcall::expand_as_libcall;
use self::table::expand_table_addr;
enum LegalizeInstResult {
Done,
Legalized,
SplitLegalizePending,
}
fn legalize_inst(
inst: ir::Inst,
pos: &mut FuncCursor,
cfg: &mut ControlFlowGraph,
isa: &dyn TargetIsa,
) -> LegalizeInstResult {
let opcode = pos.func.dfg[inst].opcode();
if opcode.is_call() {
if boundary::handle_call_abi(isa, inst, pos.func, cfg) {
return LegalizeInstResult::Legalized;
}
} else if opcode.is_return() {
if boundary::handle_return_abi(inst, pos.func, cfg) {
return LegalizeInstResult::Legalized;
}
} else if opcode.is_branch() {
split::simplify_branch_arguments(&mut pos.func.dfg, inst);
} else if opcode == ir::Opcode::Isplit {
pos.use_srcloc(inst);
let arg = match pos.func.dfg[inst] {
ir::InstructionData::Unary { arg, .. } => pos.func.dfg.resolve_aliases(arg),
_ => panic!("Expected isplit: {}", pos.func.dfg.display_inst(inst, None)),
};
match pos.func.dfg.value_def(arg) {
ir::ValueDef::Result(inst, _num) => {
if let ir::InstructionData::Binary {
opcode: ir::Opcode::Iconcat,
..
} = pos.func.dfg[inst]
{
} else {
return LegalizeInstResult::SplitLegalizePending;
}
}
ir::ValueDef::Param(_block, _num) => {}
}
let res = pos.func.dfg.inst_results(inst).to_vec();
assert_eq!(res.len(), 2);
let (resl, resh) = (res[0], res[1]);
pos.func.dfg.clear_results(inst);
pos.remove_inst();
let curpos = pos.position();
let srcloc = pos.srcloc();
let (xl, xh) = split::isplit(pos.func, cfg, curpos, srcloc, arg);
pos.func.dfg.change_to_alias(resl, xl);
pos.func.dfg.change_to_alias(resh, xh);
return LegalizeInstResult::Legalized;
}
match pos.func.update_encoding(inst, isa) {
Ok(()) => LegalizeInstResult::Done,
Err(action) => {
if action(inst, pos.func, cfg, isa) {
return LegalizeInstResult::Legalized;
}
if expand_as_libcall(inst, pos.func, isa) {
LegalizeInstResult::Legalized
} else {
LegalizeInstResult::Done
}
}
}
}
pub fn legalize_function(func: &mut ir::Function, cfg: &mut ControlFlowGraph, isa: &dyn TargetIsa) {
let _tt = timing::legalize();
debug_assert!(cfg.is_valid());
boundary::legalize_signatures(func, isa);
func.encodings.resize(func.dfg.num_insts());
let mut pos = FuncCursor::new(func);
let func_begin = pos.position();
while let Some(block) = pos.next_block() {
split::split_block_params(pos.func, cfg, block);
}
pos.set_position(func_begin);
let mut pending_splits = BTreeSet::new();
while let Some(_block) = pos.next_block() {
let mut prev_pos = pos.position();
while let Some(inst) = pos.next_inst() {
match legalize_inst(inst, &mut pos, cfg, isa) {
LegalizeInstResult::Done => prev_pos = pos.position(),
LegalizeInstResult::Legalized => pos.set_position(prev_pos),
LegalizeInstResult::SplitLegalizePending => {
pending_splits.insert(inst);
}
}
}
}
for inst in pending_splits {
pos.goto_inst(inst);
legalize_inst(inst, &mut pos, cfg, isa);
}
if !isa.flags().enable_jump_tables() {
pos.func.jump_tables.clear();
}
}
pub fn simple_legalize(func: &mut ir::Function, cfg: &mut ControlFlowGraph, isa: &dyn TargetIsa) {
let mut pos = FuncCursor::new(func);
let func_begin = pos.position();
pos.set_position(func_begin);
while let Some(_block) = pos.next_block() {
let mut prev_pos = pos.position();
while let Some(inst) = pos.next_inst() {
let expanded = match pos.func.dfg[inst].opcode() {
ir::Opcode::BrIcmp
| ir::Opcode::GlobalValue
| ir::Opcode::HeapAddr
| ir::Opcode::StackLoad
| ir::Opcode::StackStore
| ir::Opcode::TableAddr
| ir::Opcode::Trapnz
| ir::Opcode::Trapz
| ir::Opcode::ResumableTrapnz
| ir::Opcode::BandImm
| ir::Opcode::BorImm
| ir::Opcode::BxorImm
| ir::Opcode::IaddImm
| ir::Opcode::IfcmpImm
| ir::Opcode::ImulImm
| ir::Opcode::IrsubImm
| ir::Opcode::IshlImm
| ir::Opcode::RotlImm
| ir::Opcode::RotrImm
| ir::Opcode::SdivImm
| ir::Opcode::SremImm
| ir::Opcode::SshrImm
| ir::Opcode::UdivImm
| ir::Opcode::UremImm
| ir::Opcode::UshrImm
| ir::Opcode::IcmpImm => expand(inst, &mut pos.func, cfg, isa),
_ => false,
};
if expanded {
pos.set_position(prev_pos);
} else {
prev_pos = pos.position();
}
}
}
}
include!(concat!(env!("OUT_DIR"), "/legalizer.rs"));
fn expand_cond_trap(
inst: ir::Inst,
func: &mut ir::Function,
cfg: &mut ControlFlowGraph,
_isa: &dyn TargetIsa,
) {
let trapz;
let (arg, code, opcode) = match func.dfg[inst] {
ir::InstructionData::CondTrap { opcode, arg, code } => {
trapz = match opcode {
ir::Opcode::Trapz => true,
ir::Opcode::Trapnz | ir::Opcode::ResumableTrapnz => false,
_ => panic!("Expected cond trap: {}", func.dfg.display_inst(inst, None)),
};
(arg, code, opcode)
}
_ => panic!("Expected cond trap: {}", func.dfg.display_inst(inst, None)),
};
let old_block = func.layout.pp_block(inst);
let new_block_trap = func.dfg.make_block();
let new_block_resume = func.dfg.make_block();
if trapz {
func.dfg.replace(inst).brnz(arg, new_block_resume, &[]);
} else {
func.dfg.replace(inst).brz(arg, new_block_resume, &[]);
}
let mut pos = FuncCursor::new(func).after_inst(inst);
pos.use_srcloc(inst);
pos.ins().jump(new_block_trap, &[]);
pos.insert_block(new_block_trap);
match opcode {
ir::Opcode::Trapz | ir::Opcode::Trapnz => {
pos.ins().trap(code);
}
ir::Opcode::ResumableTrapnz => {
pos.ins().resumable_trap(code);
pos.ins().jump(new_block_resume, &[]);
}
_ => unreachable!(),
}
pos.insert_block(new_block_resume);
cfg.recompute_block(pos.func, old_block);
cfg.recompute_block(pos.func, new_block_resume);
cfg.recompute_block(pos.func, new_block_trap);
}
fn expand_br_table(
inst: ir::Inst,
func: &mut ir::Function,
cfg: &mut ControlFlowGraph,
isa: &dyn TargetIsa,
) {
if isa.flags().enable_jump_tables() {
expand_br_table_jt(inst, func, cfg, isa);
} else {
expand_br_table_conds(inst, func, cfg, isa);
}
}
fn expand_br_table_jt(
inst: ir::Inst,
func: &mut ir::Function,
cfg: &mut ControlFlowGraph,
isa: &dyn TargetIsa,
) {
use crate::ir::condcodes::IntCC;
let (arg, default_block, table) = match func.dfg[inst] {
ir::InstructionData::BranchTable {
opcode: ir::Opcode::BrTable,
arg,
destination,
table,
} => (arg, destination, table),
_ => panic!("Expected br_table: {}", func.dfg.display_inst(inst, None)),
};
let block = func.layout.pp_block(inst);
let jump_table_block = func.dfg.make_block();
let mut pos = FuncCursor::new(func).at_inst(inst);
pos.use_srcloc(inst);
let table_size = pos.func.jump_tables[table].len() as i64;
let oob = pos
.ins()
.icmp_imm(IntCC::UnsignedGreaterThanOrEqual, arg, table_size);
pos.ins().brnz(oob, default_block, &[]);
pos.ins().jump(jump_table_block, &[]);
pos.insert_block(jump_table_block);
let addr_ty = isa.pointer_type();
let arg = if pos.func.dfg.value_type(arg) == addr_ty {
arg
} else {
pos.ins().uextend(addr_ty, arg)
};
let base_addr = pos.ins().jump_table_base(addr_ty, table);
let entry = pos
.ins()
.jump_table_entry(arg, base_addr, I32.bytes() as u8, table);
let addr = pos.ins().iadd(base_addr, entry);
pos.ins().indirect_jump_table_br(addr, table);
pos.remove_inst();
cfg.recompute_block(pos.func, block);
cfg.recompute_block(pos.func, jump_table_block);
}
fn expand_br_table_conds(
inst: ir::Inst,
func: &mut ir::Function,
cfg: &mut ControlFlowGraph,
_isa: &dyn TargetIsa,
) {
use crate::ir::condcodes::IntCC;
let (arg, default_block, table) = match func.dfg[inst] {
ir::InstructionData::BranchTable {
opcode: ir::Opcode::BrTable,
arg,
destination,
table,
} => (arg, destination, table),
_ => panic!("Expected br_table: {}", func.dfg.display_inst(inst, None)),
};
let block = func.layout.pp_block(inst);
let table_size = func.jump_tables[table].len();
let mut cond_failed_block = vec![];
if table_size >= 1 {
cond_failed_block = alloc::vec::Vec::with_capacity(table_size - 1);
for _ in 0..table_size - 1 {
cond_failed_block.push(func.dfg.make_block());
}
}
let mut pos = FuncCursor::new(func).at_inst(inst);
pos.use_srcloc(inst);
#[allow(clippy::needless_range_loop)]
for i in 0..table_size {
let dest = pos.func.jump_tables[table].as_slice()[i];
let t = pos.ins().icmp_imm(IntCC::Equal, arg, i as i64);
pos.ins().brnz(t, dest, &[]);
if i < table_size - 1 {
let block = cond_failed_block[i];
pos.ins().jump(block, &[]);
pos.insert_block(block);
}
}
pos.ins().jump(default_block, &[]);
pos.remove_inst();
cfg.recompute_block(pos.func, block);
for failed_block in cond_failed_block.into_iter() {
cfg.recompute_block(pos.func, failed_block);
}
}
fn expand_select(
inst: ir::Inst,
func: &mut ir::Function,
cfg: &mut ControlFlowGraph,
_isa: &dyn TargetIsa,
) {
let (ctrl, tval, fval) = match func.dfg[inst] {
ir::InstructionData::Ternary {
opcode: ir::Opcode::Select,
args,
} => (args[0], args[1], args[2]),
_ => panic!("Expected select: {}", func.dfg.display_inst(inst, None)),
};
let old_block = func.layout.pp_block(inst);
let result = func.dfg.first_result(inst);
func.dfg.clear_results(inst);
let new_block = func.dfg.make_block();
func.dfg.attach_block_param(new_block, result);
func.dfg.replace(inst).brnz(ctrl, new_block, &[tval]);
let mut pos = FuncCursor::new(func).after_inst(inst);
pos.use_srcloc(inst);
pos.ins().jump(new_block, &[fval]);
pos.insert_block(new_block);
cfg.recompute_block(pos.func, new_block);
cfg.recompute_block(pos.func, old_block);
}
fn expand_br_icmp(
inst: ir::Inst,
func: &mut ir::Function,
cfg: &mut ControlFlowGraph,
_isa: &dyn TargetIsa,
) {
let (cond, a, b, destination, block_args) = match func.dfg[inst] {
ir::InstructionData::BranchIcmp {
cond,
destination,
ref args,
..
} => (
cond,
args.get(0, &func.dfg.value_lists).unwrap(),
args.get(1, &func.dfg.value_lists).unwrap(),
destination,
args.as_slice(&func.dfg.value_lists)[2..].to_vec(),
),
_ => panic!("Expected br_icmp {}", func.dfg.display_inst(inst, None)),
};
let old_block = func.layout.pp_block(inst);
func.dfg.clear_results(inst);
let icmp_res = func.dfg.replace(inst).icmp(cond, a, b);
let mut pos = FuncCursor::new(func).after_inst(inst);
pos.use_srcloc(inst);
pos.ins().brnz(icmp_res, destination, &block_args);
cfg.recompute_block(pos.func, destination);
cfg.recompute_block(pos.func, old_block);
}
fn expand_fconst(
inst: ir::Inst,
func: &mut ir::Function,
_cfg: &mut ControlFlowGraph,
_isa: &dyn TargetIsa,
) {
let ty = func.dfg.value_type(func.dfg.first_result(inst));
debug_assert!(!ty.is_vector(), "Only scalar fconst supported: {}", ty);
let mut pos = FuncCursor::new(func).at_inst(inst);
pos.use_srcloc(inst);
let ival = match pos.func.dfg[inst] {
ir::InstructionData::UnaryIeee32 {
opcode: ir::Opcode::F32const,
imm,
} => pos.ins().iconst(ir::types::I32, i64::from(imm.bits())),
ir::InstructionData::UnaryIeee64 {
opcode: ir::Opcode::F64const,
imm,
} => pos.ins().iconst(ir::types::I64, imm.bits() as i64),
_ => panic!("Expected fconst: {}", pos.func.dfg.display_inst(inst, None)),
};
pos.func.dfg.replace(inst).bitcast(ty, ival);
}
fn expand_stack_load(
inst: ir::Inst,
func: &mut ir::Function,
_cfg: &mut ControlFlowGraph,
isa: &dyn TargetIsa,
) {
let ty = func.dfg.value_type(func.dfg.first_result(inst));
let addr_ty = isa.pointer_type();
let mut pos = FuncCursor::new(func).at_inst(inst);
pos.use_srcloc(inst);
let (stack_slot, offset) = match pos.func.dfg[inst] {
ir::InstructionData::StackLoad {
opcode: _opcode,
stack_slot,
offset,
} => (stack_slot, offset),
_ => panic!(
"Expected stack_load: {}",
pos.func.dfg.display_inst(inst, None)
),
};
let addr = pos.ins().stack_addr(addr_ty, stack_slot, offset);
let mflags = MemFlags::trusted();
pos.func.dfg.replace(inst).load(ty, mflags, addr, 0);
}
fn expand_stack_store(
inst: ir::Inst,
func: &mut ir::Function,
_cfg: &mut ControlFlowGraph,
isa: &dyn TargetIsa,
) {
let addr_ty = isa.pointer_type();
let mut pos = FuncCursor::new(func).at_inst(inst);
pos.use_srcloc(inst);
let (val, stack_slot, offset) = match pos.func.dfg[inst] {
ir::InstructionData::StackStore {
opcode: _opcode,
arg,
stack_slot,
offset,
} => (arg, stack_slot, offset),
_ => panic!(
"Expected stack_store: {}",
pos.func.dfg.display_inst(inst, None)
),
};
let addr = pos.ins().stack_addr(addr_ty, stack_slot, offset);
let mut mflags = MemFlags::new();
mflags.set_notrap();
mflags.set_aligned();
pos.func.dfg.replace(inst).store(mflags, val, addr, 0);
}
fn narrow_load(
inst: ir::Inst,
func: &mut ir::Function,
_cfg: &mut ControlFlowGraph,
isa: &dyn TargetIsa,
) {
let mut pos = FuncCursor::new(func).at_inst(inst);
pos.use_srcloc(inst);
let (ptr, offset, flags) = match pos.func.dfg[inst] {
ir::InstructionData::Load {
opcode: ir::Opcode::Load,
arg,
offset,
flags,
} => (arg, offset, flags),
_ => panic!("Expected load: {}", pos.func.dfg.display_inst(inst, None)),
};
let res_ty = pos.func.dfg.ctrl_typevar(inst);
let small_ty = res_ty.half_width().expect("Can't narrow load");
let al = pos.ins().load(small_ty, flags, ptr, offset);
let ah = pos.ins().load(
small_ty,
flags,
ptr,
offset.try_add_i64(8).expect("load offset overflow"),
);
let (al, ah) = match flags.endianness(isa.endianness()) {
ir::Endianness::Little => (al, ah),
ir::Endianness::Big => (ah, al),
};
pos.func.dfg.replace(inst).iconcat(al, ah);
}
fn narrow_store(
inst: ir::Inst,
func: &mut ir::Function,
_cfg: &mut ControlFlowGraph,
isa: &dyn TargetIsa,
) {
let mut pos = FuncCursor::new(func).at_inst(inst);
pos.use_srcloc(inst);
let (val, ptr, offset, flags) = match pos.func.dfg[inst] {
ir::InstructionData::Store {
opcode: ir::Opcode::Store,
args,
offset,
flags,
} => (args[0], args[1], offset, flags),
_ => panic!("Expected store: {}", pos.func.dfg.display_inst(inst, None)),
};
let (al, ah) = pos.ins().isplit(val);
let (al, ah) = match flags.endianness(isa.endianness()) {
ir::Endianness::Little => (al, ah),
ir::Endianness::Big => (ah, al),
};
pos.ins().store(flags, al, ptr, offset);
pos.ins().store(
flags,
ah,
ptr,
offset.try_add_i64(8).expect("store offset overflow"),
);
pos.remove_inst();
}
fn narrow_iconst(
inst: ir::Inst,
func: &mut ir::Function,
_cfg: &mut ControlFlowGraph,
isa: &dyn TargetIsa,
) {
let imm: i64 = if let ir::InstructionData::UnaryImm {
opcode: ir::Opcode::Iconst,
imm,
} = &func.dfg[inst]
{
(*imm).into()
} else {
panic!("unexpected instruction in narrow_iconst");
};
let mut pos = FuncCursor::new(func).at_inst(inst);
pos.use_srcloc(inst);
let ty = pos.func.dfg.ctrl_typevar(inst);
if isa.pointer_bits() == 32 && ty == I64 {
let low = pos.ins().iconst(I32, imm & 0xffffffff);
let high = pos.ins().iconst(I32, imm >> 32);
pos.func.dfg.replace(inst).iconcat(low, high);
return;
}
unimplemented!("missing encoding or legalization for iconst.{:?}", ty);
}
fn narrow_icmp_imm(
inst: ir::Inst,
func: &mut ir::Function,
_cfg: &mut ControlFlowGraph,
_isa: &dyn TargetIsa,
) {
use crate::ir::condcodes::{CondCode, IntCC};
let (arg, cond, imm): (ir::Value, IntCC, i64) = match func.dfg[inst] {
ir::InstructionData::IntCompareImm {
opcode: ir::Opcode::IcmpImm,
arg,
cond,
imm,
} => (arg, cond, imm.into()),
_ => panic!("unexpected instruction in narrow_icmp_imm"),
};
let mut pos = FuncCursor::new(func).at_inst(inst);
pos.use_srcloc(inst);
let ty = pos.func.dfg.ctrl_typevar(inst);
let ty_half = ty.half_width().unwrap();
let mask = ((1u128 << ty_half.bits()) - 1) as i64;
let imm_low = pos.ins().iconst(ty_half, imm & mask);
let imm_high = pos.ins().iconst(
ty_half,
imm.checked_shr(ty_half.bits().into()).unwrap_or(0) & mask,
);
let (arg_low, arg_high) = pos.ins().isplit(arg);
match cond {
IntCC::Equal => {
let res_low = pos.ins().icmp(cond, arg_low, imm_low);
let res_high = pos.ins().icmp(cond, arg_high, imm_high);
pos.func.dfg.replace(inst).band(res_low, res_high);
}
IntCC::NotEqual => {
let res_low = pos.ins().icmp(cond, arg_low, imm_low);
let res_high = pos.ins().icmp(cond, arg_high, imm_high);
pos.func.dfg.replace(inst).bor(res_low, res_high);
}
IntCC::SignedGreaterThan
| IntCC::SignedGreaterThanOrEqual
| IntCC::SignedLessThan
| IntCC::SignedLessThanOrEqual
| IntCC::UnsignedGreaterThan
| IntCC::UnsignedGreaterThanOrEqual
| IntCC::UnsignedLessThan
| IntCC::UnsignedLessThanOrEqual => {
let b1 = pos.ins().icmp(cond.without_equal(), arg_high, imm_high);
let b2 = pos
.ins()
.icmp(cond.inverse().without_equal(), arg_high, imm_high);
let b3 = pos.ins().icmp(cond.unsigned(), arg_low, imm_low);
let c1 = pos.ins().bnot(b2);
let c2 = pos.ins().band(c1, b3);
pos.func.dfg.replace(inst).bor(b1, c2);
}
_ => unimplemented!("missing legalization for condition {:?}", cond),
}
}