use crate::cursor::{Cursor, EncCursor};
use crate::dominator_tree::DominatorTree;
use crate::flowgraph::ControlFlowGraph;
use crate::ir::{ArgumentLoc, InstBuilder, ValueDef};
use crate::ir::{Block, Function, Inst, InstructionData, Layout, Opcode, SigRef, Value, ValueLoc};
use crate::isa::{regs_overlap, RegClass, RegInfo, RegUnit};
use crate::isa::{ConstraintKind, EncInfo, OperandConstraint, RecipeConstraints, TargetIsa};
use crate::packed_option::PackedOption;
use crate::regalloc::affinity::Affinity;
use crate::regalloc::diversion::RegDiversions;
use crate::regalloc::live_value_tracker::{LiveValue, LiveValueTracker};
use crate::regalloc::liveness::Liveness;
use crate::regalloc::liverange::LiveRange;
use crate::regalloc::register_set::RegisterSet;
use crate::regalloc::solver::{Solver, SolverError};
use crate::timing;
use core::mem;
use log::debug;
pub struct Coloring {
divert: RegDiversions,
solver: Solver,
}
enum AbiParams {
Parameters(SigRef),
Returns,
}
struct Context<'a> {
cur: EncCursor<'a>,
reginfo: RegInfo,
encinfo: EncInfo,
cfg: &'a ControlFlowGraph,
domtree: &'a DominatorTree,
liveness: &'a mut Liveness,
divert: &'a mut RegDiversions,
solver: &'a mut Solver,
usable_regs: RegisterSet,
uses_pinned_reg: bool,
}
impl Coloring {
pub fn new() -> Self {
Self {
divert: RegDiversions::new(),
solver: Solver::new(),
}
}
pub fn clear(&mut self) {
self.divert.clear();
self.solver.clear();
}
pub fn run(
&mut self,
isa: &dyn TargetIsa,
func: &mut Function,
cfg: &ControlFlowGraph,
domtree: &DominatorTree,
liveness: &mut Liveness,
tracker: &mut LiveValueTracker,
) {
let _tt = timing::ra_coloring();
debug!("Coloring for:\n{}", func.display(isa));
let mut ctx = Context {
usable_regs: isa.allocatable_registers(func),
uses_pinned_reg: isa.flags().enable_pinned_reg(),
cur: EncCursor::new(func, isa),
reginfo: isa.register_info(),
encinfo: isa.encoding_info(),
cfg,
domtree,
liveness,
divert: &mut self.divert,
solver: &mut self.solver,
};
ctx.run(tracker)
}
}
impl<'a> Context<'a> {
#[inline]
fn is_pinned_reg(&self, rc: RegClass, reg: RegUnit) -> bool {
rc.is_pinned_reg(self.uses_pinned_reg, reg)
}
fn run(&mut self, tracker: &mut LiveValueTracker) {
self.cur
.func
.locations
.resize(self.cur.func.dfg.num_values());
for &block in self.domtree.cfg_postorder().iter().rev() {
self.visit_block(block, tracker);
}
}
fn visit_block(&mut self, block: Block, tracker: &mut LiveValueTracker) {
debug!("Coloring {}:", block);
let mut regs = self.visit_block_header(block, tracker);
tracker.drop_dead_params();
self.cur.goto_top(block);
while let Some(inst) = self.cur.next_inst() {
self.cur.use_srcloc(inst);
let opcode = self.cur.func.dfg[inst].opcode();
if !opcode.is_ghost() {
let enc = self.cur.func.encodings[inst];
let constraints = self.encinfo.operand_constraints(enc);
if self.visit_inst(inst, constraints, tracker, &mut regs) {
self.replace_global_defines(inst, tracker);
self.cur.goto_inst(inst);
}
} else {
let (_throughs, kills) = tracker.process_ghost(inst);
self.process_ghost_kills(kills, &mut regs);
}
tracker.drop_dead(inst);
if opcode.is_branch() {
if let Some(branch) = self.cur.next_inst() {
debug!(
"Skip coloring {}\n from {}\n with diversions {}",
self.cur.display_inst(branch),
regs.input.display(&self.reginfo),
self.divert.display(&self.reginfo)
);
use crate::ir::instructions::BranchInfo::*;
let target = match self.cur.func.dfg.analyze_branch(branch) {
NotABranch | Table(_, _) => panic!(
"unexpected instruction {} after a conditional branch",
self.cur.display_inst(branch)
),
SingleDest(block, _) => block,
};
if self.cfg.pred_iter(target).count() == 1 {
self.divert
.save_for_block(&mut self.cur.func.entry_diversions, target);
debug!(
"Set entry-diversion for {} to\n {}",
target,
self.divert.display(&self.reginfo)
);
} else {
debug_assert!(
self.divert.is_empty(),
"Divert set is non-empty after the terminator."
);
}
assert_eq!(
self.cur.next_inst(),
None,
"Unexpected instruction after a branch group."
);
} else {
assert!(opcode.is_terminator());
}
}
}
}
fn visit_block_header(
&mut self,
block: Block,
tracker: &mut LiveValueTracker,
) -> AvailableRegs {
tracker.block_top(
block,
&self.cur.func.dfg,
self.liveness,
&self.cur.func.layout,
self.domtree,
);
self.divert.at_block(&self.cur.func.entry_diversions, block);
debug!(
"Start {} with entry-diversion set to\n {}",
block,
self.divert.display(&self.reginfo)
);
if self.cur.func.layout.entry_block() == Some(block) {
self.color_entry_params(tracker.live())
} else {
self.livein_regs(tracker.live())
}
}
fn livein_regs(&self, live: &[LiveValue]) -> AvailableRegs {
let mut regs = AvailableRegs::new(&self.usable_regs);
for lv in live.iter().filter(|lv| !lv.is_dead) {
debug!(
"Live-in: {}:{} in {}",
lv.value,
lv.affinity.display(&self.reginfo),
self.divert
.get(lv.value, &self.cur.func.locations)
.display(&self.reginfo)
);
if let Affinity::Reg(rci) = lv.affinity {
let rc = self.reginfo.rc(rci);
let loc = self.cur.func.locations[lv.value];
let reg = match loc {
ValueLoc::Reg(reg) => reg,
ValueLoc::Unassigned => panic!("Live-in {} wasn't assigned", lv.value),
ValueLoc::Stack(ss) => {
panic!("Live-in {} is in {}, should be register", lv.value, ss)
}
};
if lv.is_local {
regs.take(rc, reg, lv.is_local);
} else {
let loc = self.divert.get(lv.value, &self.cur.func.locations);
let reg_divert = match loc {
ValueLoc::Reg(reg) => reg,
ValueLoc::Unassigned => {
panic!("Diversion: Live-in {} wasn't assigned", lv.value)
}
ValueLoc::Stack(ss) => panic!(
"Diversion: Live-in {} is in {}, should be register",
lv.value, ss
),
};
regs.take_divert(rc, reg, reg_divert);
}
}
}
regs
}
fn color_entry_params(&mut self, args: &[LiveValue]) -> AvailableRegs {
let sig = &self.cur.func.signature;
debug_assert_eq!(sig.params.len(), args.len());
let mut regs = AvailableRegs::new(&self.usable_regs);
for (lv, abi) in args.iter().zip(&sig.params) {
match lv.affinity {
Affinity::Reg(rci) => {
let rc = self.reginfo.rc(rci);
if let ArgumentLoc::Reg(reg) = abi.location {
if !lv.is_dead {
regs.take(rc, reg, lv.is_local);
}
self.cur.func.locations[lv.value] = ValueLoc::Reg(reg);
} else {
panic!(
"Entry arg {} has {} affinity, but ABI {}",
lv.value,
lv.affinity.display(&self.reginfo),
abi.display(&self.reginfo)
);
}
}
Affinity::Stack => debug_assert!(abi.location.is_stack()),
Affinity::Unassigned => {}
}
}
regs
}
fn program_input_abi(&mut self, inst: Inst, abi_params: AbiParams) {
let abi_types = match abi_params {
AbiParams::Parameters(sig) => &self.cur.func.dfg.signatures[sig].params,
AbiParams::Returns => &self.cur.func.signature.returns,
};
for (abi, &value) in abi_types
.iter()
.zip(self.cur.func.dfg.inst_variable_args(inst))
{
if let ArgumentLoc::Reg(reg) = abi.location {
if let Affinity::Reg(rci) = self
.liveness
.get(value)
.expect("ABI register must have live range")
.affinity
{
let rc = self.reginfo.rc(rci);
let cur_reg = self.divert.reg(value, &self.cur.func.locations);
self.solver.reassign_in(value, rc, cur_reg, reg);
} else {
panic!("ABI argument {} should be in a register", value);
}
}
}
}
fn visit_inst(
&mut self,
inst: Inst,
constraints: Option<&RecipeConstraints>,
tracker: &mut LiveValueTracker,
regs: &mut AvailableRegs,
) -> bool {
debug!(
"Coloring {}\n from {}",
self.cur.display_inst(inst),
regs.input.display(&self.reginfo),
);
let mut color_dest_args = None;
self.solver.reset(®s.input);
if let Some(constraints) = constraints {
self.program_input_constraints(inst, constraints.ins);
}
let call_sig = self.cur.func.dfg.call_signature(inst);
if let Some(sig) = call_sig {
self.program_input_abi(inst, AbiParams::Parameters(sig));
} else if self.cur.func.dfg[inst].opcode().is_return() {
self.program_input_abi(inst, AbiParams::Returns);
} else if self.cur.func.dfg[inst].opcode().is_branch() {
if let Some(dest) = self.cur.func.dfg[inst].branch_destination() {
if self.program_block_arguments(inst, dest) {
color_dest_args = Some(dest);
}
} else {
debug_assert_eq!(
self.cur.func.dfg.inst_variable_args(inst).len(),
0,
"Can't handle block arguments: {}",
self.cur.display_inst(inst)
);
self.undivert_regs(|lr, _| !lr.is_local());
}
}
if self.solver.has_fixed_input_conflicts() {
self.divert_fixed_input_conflicts(tracker.live());
}
self.solver.inputs_done();
let (throughs, kills, defs) = tracker.process_inst(inst, &self.cur.func.dfg, self.liveness);
for lv in kills {
if let Affinity::Reg(rci) = lv.affinity {
let rc = self.reginfo.rc(rci);
let reg = self.divert.reg(lv.value, &self.cur.func.locations);
if self.is_pinned_reg(rc, reg) {
debug_assert!(lv.is_local, "pinned register SSA value can't be global");
continue;
}
debug!(
" kill {} in {} ({} {})",
lv.value,
self.reginfo.display_regunit(reg),
if lv.is_local { "local" } else { "global" },
rc
);
self.solver.add_kill(lv.value, rc, reg);
if !lv.is_local {
regs.global
.free(rc, self.cur.func.locations[lv.value].unwrap_reg());
}
}
}
debug!(" glob {}", regs.global.display(&self.reginfo));
let mut replace_global_defines = false;
if let Some(constraints) = constraints {
if constraints.fixed_outs {
self.program_fixed_outputs(
constraints.outs,
defs,
throughs,
&mut replace_global_defines,
®s.global,
);
}
}
if let Some(sig) = call_sig {
self.program_output_abi(
sig,
defs,
throughs,
&mut replace_global_defines,
®s.global,
);
}
if let Some(constraints) = constraints {
self.program_output_constraints(
inst,
constraints.outs,
defs,
&mut replace_global_defines,
®s.global,
);
}
let is_reload = match &self.cur.func.dfg[inst] {
InstructionData::Unary {
opcode: Opcode::Fill,
..
} => true,
_ => false,
};
let output_regs = self
.solver
.quick_solve(®s.global, is_reload)
.unwrap_or_else(|_| {
debug!("quick_solve failed for {}", self.solver);
self.iterate_solution(
throughs,
®s.global,
&mut replace_global_defines,
is_reload,
)
});
self.shuffle_inputs(&mut regs.input);
if let Some(dest) = color_dest_args {
self.color_block_params(inst, dest);
}
for v in self.solver.vars().iter().filter(|&v| v.is_define()) {
self.cur.func.locations[v.value] = ValueLoc::Reg(v.solution);
}
if let Some(constraints) = constraints {
if constraints.tied_ops {
for (constraint, lv) in constraints.outs.iter().zip(defs) {
if let ConstraintKind::Tied(num) = constraint.kind {
let arg = self.cur.func.dfg.inst_args(inst)[num as usize];
let reg = self.divert.reg(arg, &self.cur.func.locations);
self.cur.func.locations[lv.value] = ValueLoc::Reg(reg);
}
}
}
}
regs.input = output_regs;
for lv in defs {
let loc = self.cur.func.locations[lv.value];
debug!(
" color {} -> {}{}",
lv.value,
loc.display(&self.reginfo),
if lv.is_local {
""
} else if replace_global_defines {
" (global to be replaced)"
} else {
" (global)"
}
);
if let Affinity::Reg(rci) = lv.affinity {
let rc = self.reginfo.rc(rci);
let reg = loc.unwrap_reg();
debug_assert!(
!self.is_pinned_reg(rc, reg)
|| self.cur.func.dfg[inst].opcode() == Opcode::GetPinnedReg,
"pinned register may not be part of outputs for '{}'.",
self.cur.func.dfg[inst].opcode()
);
if self.is_pinned_reg(rc, reg) {
continue;
}
if lv.endpoint == inst {
regs.input.free(rc, reg);
debug_assert!(lv.is_local);
}
if !lv.is_local && !replace_global_defines {
regs.global.take(rc, reg);
}
}
}
self.forget_diverted(kills);
replace_global_defines
}
fn program_input_constraints(&mut self, inst: Inst, constraints: &[OperandConstraint]) {
for (constraint, &arg_val) in constraints
.iter()
.zip(self.cur.func.dfg.inst_args(inst))
.filter(|&(constraint, _)| constraint.kind != ConstraintKind::Stack)
{
let cur_reg = self.divert.reg(arg_val, &self.cur.func.locations);
match constraint.kind {
ConstraintKind::FixedReg(regunit) => {
self.solver
.reassign_in(arg_val, constraint.regclass, cur_reg, regunit);
}
ConstraintKind::FixedTied(regunit) => {
debug_assert!(
!self.is_pinned_reg(constraint.regclass, regunit),
"see comment above"
);
self.solver
.reassign_in(arg_val, constraint.regclass, cur_reg, regunit);
}
ConstraintKind::Tied(_) => {
if self.is_pinned_reg(constraint.regclass, cur_reg) {
if self.solver.can_add_var(constraint.regclass, cur_reg) {
self.solver.add_var(arg_val, constraint.regclass, cur_reg);
}
} else if !constraint.regclass.contains(cur_reg) {
self.solver.add_var(arg_val, constraint.regclass, cur_reg);
}
}
ConstraintKind::Reg => {
if !constraint.regclass.contains(cur_reg) {
self.solver.add_var(arg_val, constraint.regclass, cur_reg);
}
}
ConstraintKind::Stack => unreachable!(),
}
}
}
fn program_complete_input_constraints(&mut self) {
let inst = self.cur.current_inst().expect("Not on an instruction");
let constraints = self
.encinfo
.operand_constraints(self.cur.func.encodings[inst])
.expect("Current instruction not encoded")
.ins;
for (constraint, &arg_val) in constraints.iter().zip(self.cur.func.dfg.inst_args(inst)) {
match constraint.kind {
ConstraintKind::Reg | ConstraintKind::Tied(_) => {
let cur_reg = self.divert.reg(arg_val, &self.cur.func.locations);
if constraint.regclass.contains(cur_reg)
&& !self.is_pinned_reg(constraint.regclass, cur_reg)
{
let layout = &self.cur.func.layout;
if self.liveness[arg_val].killed_at(inst, layout.pp_block(inst), layout) {
self.solver
.add_killed_var(arg_val, constraint.regclass, cur_reg);
} else {
self.solver
.add_through_var(arg_val, constraint.regclass, cur_reg);
}
}
}
ConstraintKind::FixedReg(_)
| ConstraintKind::FixedTied(_)
| ConstraintKind::Stack => {}
}
}
}
fn program_block_arguments(&mut self, inst: Inst, dest: Block) -> bool {
self.undivert_regs(|lr, layout| lr.is_livein(dest, layout));
let br_args = self.cur.func.dfg.inst_variable_args(inst);
let dest_args = self.cur.func.dfg.block_params(dest);
debug_assert_eq!(br_args.len(), dest_args.len());
for (&dest_arg, &br_arg) in dest_args.iter().zip(br_args) {
match self.cur.func.locations[dest_arg] {
ValueLoc::Unassigned => {
if self.liveness[dest_arg].affinity.is_reg() {
return true;
}
}
ValueLoc::Reg(dest_reg) => {
if let Affinity::Reg(rci) = self.liveness[br_arg].affinity {
let rc = self.reginfo.rc(rci);
let br_reg = self.divert.reg(br_arg, &self.cur.func.locations);
self.solver.reassign_in(br_arg, rc, br_reg, dest_reg);
} else {
panic!("Branch argument {} is not in a register", br_arg);
}
}
ValueLoc::Stack(ss) => {
debug_assert_eq!(ValueLoc::Stack(ss), self.cur.func.locations[br_arg]);
}
}
}
false
}
fn color_block_params(&mut self, inst: Inst, dest: Block) {
let br_args = self.cur.func.dfg.inst_variable_args(inst);
let dest_args = self.cur.func.dfg.block_params(dest);
debug_assert_eq!(br_args.len(), dest_args.len());
for (&dest_arg, &br_arg) in dest_args.iter().zip(br_args) {
match self.cur.func.locations[dest_arg] {
ValueLoc::Unassigned => {
if self.liveness[dest_arg].affinity.is_reg() {
let br_reg = self.divert.reg(br_arg, &self.cur.func.locations);
self.cur.func.locations[dest_arg] = ValueLoc::Reg(br_reg);
}
}
ValueLoc::Reg(_) => panic!("{} arg {} already colored", dest, dest_arg),
ValueLoc::Stack(_) => {}
}
}
}
fn undivert_regs<Pred>(&mut self, mut pred: Pred)
where
Pred: FnMut(&LiveRange, &Layout) -> bool,
{
for (&value, rdiv) in self.divert.iter() {
let lr = self
.liveness
.get(value)
.expect("Missing live range for diverted register");
if pred(lr, &self.cur.func.layout) {
if let Affinity::Reg(rci) = lr.affinity {
let rc = self.reginfo.rc(rci);
self.solver.reassign_in(
value,
rc,
rdiv.to.unwrap_reg(),
rdiv.from.unwrap_reg(),
);
} else {
panic!(
"Diverted register {} with {} affinity",
value,
lr.affinity.display(&self.reginfo)
);
}
}
}
}
fn divert_fixed_input_conflicts(&mut self, live: &[LiveValue]) {
for lv in live {
if let Affinity::Reg(rci) = lv.affinity {
let toprc = self.reginfo.toprc(rci);
let reg = self.divert.reg(lv.value, &self.cur.func.locations);
if self.solver.is_fixed_input_conflict(toprc, reg) {
debug!(
"adding var to divert fixed input conflict for {}",
toprc.info.display_regunit(reg)
);
self.solver.add_var(lv.value, toprc, reg);
}
}
}
}
fn program_fixed_outputs(
&mut self,
constraints: &[OperandConstraint],
defs: &[LiveValue],
throughs: &[LiveValue],
replace_global_defines: &mut bool,
global_regs: &RegisterSet,
) {
for (constraint, lv) in constraints.iter().zip(defs) {
match constraint.kind {
ConstraintKind::FixedReg(reg) | ConstraintKind::FixedTied(reg) => {
self.add_fixed_output(lv.value, constraint.regclass, reg, throughs);
if !lv.is_local && !global_regs.is_avail(constraint.regclass, reg) {
debug!(
"Fixed output {} in {}:{} is not available in global regs",
lv.value,
constraint.regclass,
self.reginfo.display_regunit(reg)
);
*replace_global_defines = true;
}
}
ConstraintKind::Reg | ConstraintKind::Tied(_) | ConstraintKind::Stack => {}
}
}
}
fn program_output_abi(
&mut self,
sig: SigRef,
defs: &[LiveValue],
throughs: &[LiveValue],
replace_global_defines: &mut bool,
global_regs: &RegisterSet,
) {
debug_assert_eq!(defs.len(), self.cur.func.dfg.signatures[sig].returns.len());
for (i, lv) in defs.iter().enumerate() {
let abi = self.cur.func.dfg.signatures[sig].returns[i];
if let ArgumentLoc::Reg(reg) = abi.location {
if let Affinity::Reg(rci) = lv.affinity {
let rc = self.reginfo.rc(rci);
self.add_fixed_output(lv.value, rc, reg, throughs);
if !lv.is_local && !global_regs.is_avail(rc, reg) {
debug!(
"ABI output {} in {}:{} is not available in global regs",
lv.value,
rc,
self.reginfo.display_regunit(reg)
);
*replace_global_defines = true;
}
} else {
panic!("ABI argument {} should be in a register", lv.value);
}
}
}
}
fn add_fixed_output(
&mut self,
value: Value,
rc: RegClass,
reg: RegUnit,
throughs: &[LiveValue],
) {
if !self.is_pinned_reg(rc, reg) && !self.solver.add_fixed_output(rc, reg) {
for lv in throughs {
if let Affinity::Reg(rci) = lv.affinity {
let toprc2 = self.reginfo.toprc(rci);
let reg2 = self.divert.reg(lv.value, &self.cur.func.locations);
if regs_overlap(rc, reg, toprc2, reg2) {
self.solver.add_through_var(lv.value, toprc2, reg2);
}
}
}
let ok = self.solver.add_fixed_output(rc, reg);
debug_assert!(ok, "Couldn't clear fixed output interference for {}", value);
}
self.cur.func.locations[value] = ValueLoc::Reg(reg);
}
fn program_output_constraints(
&mut self,
inst: Inst,
constraints: &[OperandConstraint],
defs: &[LiveValue],
replace_global_defines: &mut bool,
global_regs: &RegisterSet,
) {
for (constraint, lv) in constraints.iter().zip(defs) {
match constraint.kind {
ConstraintKind::FixedReg(_)
| ConstraintKind::FixedTied(_)
| ConstraintKind::Stack => continue,
ConstraintKind::Reg => {
self.solver
.add_def(lv.value, constraint.regclass, !lv.is_local);
}
ConstraintKind::Tied(num) => {
let arg = self.cur.func.dfg.inst_args(inst)[num as usize];
let reg = self.divert.reg(arg, &self.cur.func.locations);
if let Some(reg) =
self.solver
.add_tied_input(arg, constraint.regclass, reg, !lv.is_local)
{
if !lv.is_local && !global_regs.is_avail(constraint.regclass, reg) {
debug!(
"Tied output {} in {}:{} is not available in global regs",
lv.value,
constraint.regclass,
self.reginfo.display_regunit(reg)
);
*replace_global_defines = true;
}
}
}
}
}
}
fn iterate_solution(
&mut self,
throughs: &[LiveValue],
global_regs: &RegisterSet,
replace_global_defines: &mut bool,
is_reload: bool,
) -> RegisterSet {
self.program_complete_input_constraints();
loop {
match self.solver.real_solve(global_regs, is_reload) {
Ok(regs) => return regs,
Err(SolverError::Divert(rc)) => {
let added = self.try_add_var(rc, throughs);
debug_assert!(added, "Ran out of registers in {}", rc);
}
Err(SolverError::Global(_value)) => {
debug!(
"Not enough global registers for {}, trying as local",
_value
);
*replace_global_defines = true;
self.solver.clear_all_global_flags();
}
};
}
}
fn try_add_var(&mut self, rc: RegClass, throughs: &[LiveValue]) -> bool {
debug!("Trying to add a {} reg from {} values", rc, throughs.len());
for lv in throughs {
if let Affinity::Reg(rci) = lv.affinity {
let toprc2 = self.reginfo.toprc(rci);
let reg2 = self.divert.reg(lv.value, &self.cur.func.locations);
if rc.contains(reg2)
&& self.solver.can_add_var(toprc2, reg2)
&& !self.is_live_on_outgoing_edge(lv.value)
{
self.solver.add_through_var(lv.value, toprc2, reg2);
return true;
}
}
}
false
}
fn is_live_on_outgoing_edge(&self, value: Value) -> bool {
use crate::ir::instructions::BranchInfo::*;
let inst = self.cur.current_inst().expect("Not on an instruction");
let layout = &self.cur.func.layout;
match self.cur.func.dfg.analyze_branch(inst) {
NotABranch => false,
SingleDest(block, _) => {
let lr = &self.liveness[value];
lr.is_livein(block, layout)
}
Table(jt, block) => {
let lr = &self.liveness[value];
!lr.is_local()
&& (block.map_or(false, |block| lr.is_livein(block, layout))
|| self.cur.func.jump_tables[jt]
.iter()
.any(|block| lr.is_livein(*block, layout)))
}
}
}
fn shuffle_inputs(&mut self, regs: &mut RegisterSet) {
use crate::regalloc::solver::Move::*;
let spills = self.solver.schedule_moves(regs);
let mut slot = [PackedOption::default(); 8];
debug_assert!(spills <= slot.len(), "Too many spills ({})", spills);
for m in self.solver.moves() {
match *m {
Reg {
value,
from,
to,
rc,
} => {
debug_assert!(
!self.is_pinned_reg(rc, to),
"pinned register used in a regmove"
);
self.divert.regmove(value, from, to);
self.cur.ins().regmove(value, from, to);
}
Spill {
value,
from,
to_slot,
..
} => {
debug_assert_eq!(slot[to_slot].expand(), None, "Overwriting slot in use");
let ss = self
.cur
.func
.stack_slots
.get_emergency_slot(self.cur.func.dfg.value_type(value), &slot[0..spills]);
slot[to_slot] = ss.into();
self.divert.regspill(value, from, ss);
self.cur.ins().regspill(value, from, ss);
}
Fill {
value,
from_slot,
to,
rc,
} => {
debug_assert!(
!self.is_pinned_reg(rc, to),
"pinned register used in a regfill"
);
let ss = slot[from_slot].take().expect("Using unallocated slot");
self.divert.regfill(value, ss, to);
self.cur.ins().regfill(value, ss, to);
}
}
}
}
fn forget_diverted(&mut self, kills: &[LiveValue]) {
if self.divert.is_empty() {
return;
}
for lv in kills {
if lv.affinity.is_reg() {
self.divert.remove(lv.value);
}
}
}
fn replace_global_defines(&mut self, inst: Inst, tracker: &mut LiveValueTracker) {
debug!("Replacing global defs on {}", self.cur.display_inst(inst));
self.cur.next_inst();
for lv in tracker.live_mut().iter_mut().rev() {
if match self.cur.func.dfg.value_def(lv.value) {
ValueDef::Result(i, _) => i != inst,
_ => true,
} {
break;
}
if lv.is_local || !lv.affinity.is_reg() {
continue;
}
let ty = self.cur.func.dfg.value_type(lv.value);
let local = self.cur.func.dfg.replace_result(lv.value, ty);
self.cur.ins().with_result(lv.value).copy(local);
let copy = self.cur.built_inst();
self.liveness.create_dead(local, inst, lv.affinity);
self.liveness.extend_locally(
local,
self.cur.func.layout.pp_block(inst),
copy,
&self.cur.func.layout,
);
self.liveness.move_def_locally(lv.value, copy);
let loc = mem::replace(&mut self.cur.func.locations[lv.value], ValueLoc::default());
self.cur.func.locations[local] = loc;
lv.value = local;
lv.endpoint = copy;
lv.is_local = true;
debug!(
" + {} with {} in {}",
self.cur.display_inst(copy),
local,
loc.display(&self.reginfo)
);
}
debug!("Done: {}", self.cur.display_inst(inst));
}
fn process_ghost_kills(&mut self, kills: &[LiveValue], regs: &mut AvailableRegs) {
for lv in kills {
if let Affinity::Reg(rci) = lv.affinity {
let rc = self.reginfo.rc(rci);
let loc = match self.divert.remove(lv.value) {
Some(loc) => loc,
None => self.cur.func.locations[lv.value],
};
regs.input.free(rc, loc.unwrap_reg());
if !lv.is_local {
regs.global
.free(rc, self.cur.func.locations[lv.value].unwrap_reg());
}
}
}
}
}
struct AvailableRegs {
input: RegisterSet,
global: RegisterSet,
}
impl AvailableRegs {
pub fn new(regs: &RegisterSet) -> Self {
Self {
input: regs.clone(),
global: regs.clone(),
}
}
pub fn take(&mut self, rc: RegClass, reg: RegUnit, is_local: bool) {
self.input.take(rc, reg);
if !is_local {
self.global.take(rc, reg);
}
}
pub fn take_divert(&mut self, rc: RegClass, reg: RegUnit, reg_divert: RegUnit) {
self.input.take(rc, reg_divert);
self.global.take(rc, reg);
}
}