use crate::cursor::{Cursor, EncCursor};
use crate::dominator_tree::DominatorTree;
use crate::entity::{SparseMap, SparseMapValue};
use crate::ir::{AbiParam, ArgumentLoc, InstBuilder};
use crate::ir::{Block, Function, Inst, InstructionData, Opcode, Value, ValueLoc};
use crate::isa::RegClass;
use crate::isa::{ConstraintKind, EncInfo, Encoding, RecipeConstraints, TargetIsa};
use crate::regalloc::affinity::Affinity;
use crate::regalloc::live_value_tracker::{LiveValue, LiveValueTracker};
use crate::regalloc::liveness::Liveness;
use crate::timing;
use crate::topo_order::TopoOrder;
use alloc::vec::Vec;
use log::debug;
pub struct Reload {
candidates: Vec<ReloadCandidate>,
reloads: SparseMap<Value, ReloadedValue>,
}
struct Context<'a> {
cur: EncCursor<'a>,
encinfo: EncInfo,
domtree: &'a DominatorTree,
liveness: &'a mut Liveness,
topo: &'a mut TopoOrder,
candidates: &'a mut Vec<ReloadCandidate>,
reloads: &'a mut SparseMap<Value, ReloadedValue>,
}
impl Reload {
pub fn new() -> Self {
Self {
candidates: Vec::new(),
reloads: SparseMap::new(),
}
}
pub fn clear(&mut self) {
self.candidates.clear();
self.reloads.clear();
}
pub fn run(
&mut self,
isa: &dyn TargetIsa,
func: &mut Function,
domtree: &DominatorTree,
liveness: &mut Liveness,
topo: &mut TopoOrder,
tracker: &mut LiveValueTracker,
) {
let _tt = timing::ra_reload();
debug!("Reload for:\n{}", func.display(isa));
let mut ctx = Context {
cur: EncCursor::new(func, isa),
encinfo: isa.encoding_info(),
domtree,
liveness,
topo,
candidates: &mut self.candidates,
reloads: &mut self.reloads,
};
ctx.run(tracker)
}
}
struct ReloadCandidate {
argidx: usize,
value: Value,
regclass: RegClass,
}
struct ReloadedValue {
stack: Value,
reg: Value,
}
impl SparseMapValue<Value> for ReloadedValue {
fn key(&self) -> Value {
self.stack
}
}
impl<'a> Context<'a> {
fn run(&mut self, tracker: &mut LiveValueTracker) {
self.topo.reset(self.cur.func.layout.blocks());
while let Some(block) = self.topo.next(&self.cur.func.layout, self.domtree) {
self.visit_block(block, tracker);
}
}
fn visit_block(&mut self, block: Block, tracker: &mut LiveValueTracker) {
debug!("Reloading {}:", block);
self.visit_block_header(block, tracker);
tracker.drop_dead_params();
while let Some(inst) = self.cur.current_inst() {
if !self.cur.func.dfg[inst].opcode().is_ghost() {
let encoding = self.cur.func.encodings[inst];
self.visit_inst(block, inst, encoding, tracker);
tracker.drop_dead(inst);
} else {
self.cur.next_inst();
}
}
}
fn visit_block_header(&mut self, block: Block, tracker: &mut LiveValueTracker) {
let (liveins, args) = tracker.block_top(
block,
&self.cur.func.dfg,
self.liveness,
&self.cur.func.layout,
self.domtree,
);
if self.cur.func.layout.entry_block() == Some(block) {
debug_assert_eq!(liveins.len(), 0);
self.visit_entry_params(block, args);
} else {
self.visit_block_params(block, args);
}
}
fn visit_entry_params(&mut self, block: Block, args: &[LiveValue]) {
debug_assert_eq!(self.cur.func.signature.params.len(), args.len());
self.cur.goto_first_inst(block);
for (arg_idx, arg) in args.iter().enumerate() {
let abi = self.cur.func.signature.params[arg_idx];
match abi.location {
ArgumentLoc::Reg(_) => {
if arg.affinity.is_stack() {
let reg = self
.cur
.func
.dfg
.replace_block_param(arg.value, abi.value_type);
let affinity = Affinity::abi(&abi, self.cur.isa);
self.liveness.create_dead(reg, block, affinity);
self.insert_spill(block, arg.value, reg);
}
}
ArgumentLoc::Stack(_) => {
debug_assert!(arg.affinity.is_stack());
}
ArgumentLoc::Unassigned => panic!("Unexpected ABI location"),
}
}
}
fn visit_block_params(&mut self, block: Block, _args: &[LiveValue]) {
self.cur.goto_first_inst(block);
}
fn visit_inst(
&mut self,
block: Block,
inst: Inst,
encoding: Encoding,
tracker: &mut LiveValueTracker,
) {
self.cur.use_srcloc(inst);
let constraints = self.encinfo.operand_constraints(encoding);
debug_assert!(self.candidates.is_empty());
self.find_candidates(inst, constraints);
if let InstructionData::Unary {
opcode: Opcode::Copy,
arg,
} = self.cur.func.dfg[inst]
{
let dst_vals = self.cur.func.dfg.inst_results(inst);
if dst_vals.len() == 1 {
let dst_val = dst_vals[0];
let can_transform = match (
self.cur.func.locations[arg],
self.cur.func.locations[dst_val],
) {
(ValueLoc::Stack(src_slot), ValueLoc::Stack(dst_slot)) => {
src_slot == dst_slot && {
let src_ty = self.cur.func.dfg.value_type(arg);
let dst_ty = self.cur.func.dfg.value_type(dst_val);
debug_assert!(src_ty == dst_ty);
src_ty.is_int() || src_ty.is_float()
}
}
_ => false,
};
if can_transform {
self.cur.func.dfg.replace(inst).copy_nop(arg);
let ok = self.cur.func.update_encoding(inst, self.cur.isa).is_ok();
debug_assert!(ok, "copy_nop encoding missing for this type");
self.reloads.clear();
let _ = tracker.process_inst(inst, &self.cur.func.dfg, self.liveness);
self.cur.next_inst();
self.candidates.clear();
return;
}
}
}
if let InstructionData::Unary {
opcode: Opcode::Copy,
..
} = self.cur.func.dfg[inst]
{
self.reload_copy_candidates(inst);
} else {
self.reload_inst_candidates(block, inst);
}
self.reloads.clear();
let (_throughs, _kills, defs) =
tracker.process_inst(inst, &self.cur.func.dfg, self.liveness);
self.cur.next_inst();
if let Some(constraints) = constraints {
for (lv, op) in defs.iter().zip(constraints.outs) {
if lv.affinity.is_stack() && op.kind != ConstraintKind::Stack {
if let InstructionData::Unary {
opcode: Opcode::Copy,
arg,
} = self.cur.func.dfg[inst]
{
self.cur.func.dfg.replace(inst).spill(arg);
let ok = self.cur.func.update_encoding(inst, self.cur.isa).is_ok();
debug_assert!(ok);
} else {
let value_type = self.cur.func.dfg.value_type(lv.value);
let reg = self.cur.func.dfg.replace_result(lv.value, value_type);
self.liveness.create_dead(reg, inst, Affinity::new(op));
self.insert_spill(block, lv.value, reg);
}
}
}
}
let retvals = &defs[self.cur.func.dfg[inst]
.opcode()
.constraints()
.num_fixed_results()..];
if !retvals.is_empty() {
let sig = self
.cur
.func
.dfg
.call_signature(inst)
.expect("Extra results on non-call instruction");
for (i, lv) in retvals.iter().enumerate() {
let abi = self.cur.func.dfg.signatures[sig].returns[i];
debug_assert!(
abi.location.is_reg(),
"expected reg; got {:?}",
abi.location
);
if lv.affinity.is_stack() {
let reg = self.cur.func.dfg.replace_result(lv.value, abi.value_type);
self.liveness
.create_dead(reg, inst, Affinity::abi(&abi, self.cur.isa));
self.insert_spill(block, lv.value, reg);
}
}
}
}
fn reload_inst_candidates(&mut self, block: Block, inst: Inst) {
for cand in self.candidates.iter_mut() {
if let Some(reload) = self.reloads.get(cand.value) {
cand.value = reload.reg;
continue;
}
let reg = self.cur.ins().fill(cand.value);
let fill = self.cur.built_inst();
self.reloads.insert(ReloadedValue {
stack: cand.value,
reg,
});
cand.value = reg;
let affinity = Affinity::Reg(cand.regclass.into());
self.liveness.create_dead(reg, fill, affinity);
self.liveness
.extend_locally(reg, block, inst, &self.cur.func.layout);
}
if !self.candidates.is_empty() {
let args = self.cur.func.dfg.inst_args_mut(inst);
while let Some(cand) = self.candidates.pop() {
args[cand.argidx] = cand.value;
}
}
}
fn reload_copy_candidates(&mut self, inst: Inst) {
debug_assert!(self.candidates.is_empty() || self.candidates.len() == 1);
if let Some(cand) = self.candidates.pop() {
self.cur.func.dfg.replace(inst).fill(cand.value);
let ok = self.cur.func.update_encoding(inst, self.cur.isa).is_ok();
debug_assert!(ok);
}
}
fn find_candidates(&mut self, inst: Inst, constraints: Option<&RecipeConstraints>) {
let args = self.cur.func.dfg.inst_args(inst);
if let Some(constraints) = constraints {
for (argidx, (op, &arg)) in constraints.ins.iter().zip(args).enumerate() {
if op.kind != ConstraintKind::Stack && self.liveness[arg].affinity.is_stack() {
self.candidates.push(ReloadCandidate {
argidx,
value: arg,
regclass: op.regclass,
})
}
}
}
let offset = self.cur.func.dfg[inst]
.opcode()
.constraints()
.num_fixed_value_arguments();
if args.len() == offset {
return;
}
let var_args = &args[offset..];
if let Some(sig) = self.cur.func.dfg.call_signature(inst) {
handle_abi_args(
self.candidates,
&self.cur.func.dfg.signatures[sig].params,
var_args,
offset,
self.cur.isa,
self.liveness,
);
} else if self.cur.func.dfg[inst].opcode().is_return() {
handle_abi_args(
self.candidates,
&self.cur.func.signature.returns,
var_args,
offset,
self.cur.isa,
self.liveness,
);
}
}
fn insert_spill(&mut self, block: Block, stack: Value, reg: Value) {
self.cur.ins().with_result(stack).spill(reg);
let inst = self.cur.built_inst();
self.liveness.move_def_locally(stack, inst);
self.liveness
.extend_locally(reg, block, inst, &self.cur.func.layout);
}
}
fn handle_abi_args(
candidates: &mut Vec<ReloadCandidate>,
abi_types: &[AbiParam],
var_args: &[Value],
offset: usize,
isa: &dyn TargetIsa,
liveness: &Liveness,
) {
debug_assert_eq!(abi_types.len(), var_args.len());
for ((abi, &arg), argidx) in abi_types.iter().zip(var_args).zip(offset..) {
if abi.location.is_reg() {
let lv = liveness.get(arg).expect("Missing live range for ABI arg");
if lv.affinity.is_stack() {
candidates.push(ReloadCandidate {
argidx,
value: arg,
regclass: isa.regclass_for_abi_type(abi.value_type),
});
}
}
}
}