use super::RegisterSet;
use dbg::DisplayList;
use entity::{SparseMap, SparseMapValue};
use ir::Value;
use isa::{RegClass, RegUnit};
use regalloc::register_set::RegSetIter;
use std::cmp;
use std::fmt;
use std::mem;
use std::u16;
use std::vec::Vec;
pub struct Variable {
pub value: Value,
from: Option<RegUnit>,
is_input: bool,
is_output: bool,
is_global: bool,
domain: u16,
pub solution: RegUnit,
constraint: RegClass,
}
impl Variable {
fn new_live(value: Value, constraint: RegClass, from: RegUnit, is_output: bool) -> Self {
Self {
value,
constraint,
from: Some(from),
is_input: true,
is_output,
is_global: false,
domain: 0,
solution: !0,
}
}
fn new_def(value: Value, constraint: RegClass, is_global: bool) -> Self {
Self {
value,
constraint,
from: None,
is_input: false,
is_output: true,
is_global,
domain: 0,
solution: !0,
}
}
pub fn is_define(&self) -> bool {
self.from.is_none()
}
fn iter(&self, iregs: &RegisterSet, oregs: &RegisterSet, gregs: &RegisterSet) -> RegSetIter {
if !self.is_output {
debug_assert!(!self.is_global, "Global implies output");
debug_assert!(self.is_input, "Missing interference set");
return iregs.iter(self.constraint);
}
let mut r = oregs.clone();
if self.is_input {
r.intersect(iregs);
}
if self.is_global {
r.intersect(gregs);
}
r.iter(self.constraint)
}
}
impl fmt::Display for Variable {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}({}", self.value, self.constraint)?;
if let Some(reg) = self.from {
write!(f, ", from {}", self.constraint.info.display_regunit(reg))?;
}
if self.is_input {
write!(f, ", in")?;
}
if self.is_output {
write!(f, ", out")?;
}
if self.is_global {
write!(f, ", global")?;
}
if self.is_define() {
write!(f, ", def")?;
}
if self.domain > 0 {
write!(f, ", {}", self.domain)?;
}
write!(f, ")")
}
}
#[derive(Clone, Debug)]
pub struct Assignment {
pub value: Value,
pub from: RegUnit,
pub to: RegUnit,
pub rc: RegClass,
}
impl SparseMapValue<Value> for Assignment {
fn key(&self) -> Value {
self.value
}
}
impl fmt::Display for Assignment {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let ri = self.rc.info;
write!(
f,
"{}:{}({} -> {})",
self.value,
self.rc,
ri.display_regunit(self.from),
ri.display_regunit(self.to)
)
}
}
#[derive(Clone, PartialEq)]
pub enum Move {
Reg {
value: Value,
rc: RegClass,
from: RegUnit,
to: RegUnit,
},
Spill {
value: Value,
rc: RegClass,
from: RegUnit,
to_slot: usize,
},
Fill {
value: Value,
rc: RegClass,
from_slot: usize,
to: RegUnit,
},
}
impl Move {
fn with_assignment(a: &Assignment) -> Option<Self> {
if a.from != a.to {
Some(Move::Reg {
value: a.value,
from: a.from,
to: a.to,
rc: a.rc,
})
} else {
None
}
}
#[cfg_attr(feature = "cargo-clippy", allow(wrong_self_convention))]
fn from_reg(&self) -> Option<(RegClass, RegUnit)> {
match *self {
Move::Reg { rc, from, .. } | Move::Spill { rc, from, .. } => Some((rc, from)),
Move::Fill { .. } => None,
}
}
fn to_reg(&self) -> Option<(RegClass, RegUnit)> {
match *self {
Move::Reg { rc, to, .. } | Move::Fill { rc, to, .. } => Some((rc, to)),
Move::Spill { .. } => None,
}
}
fn replace_to_reg(&mut self, new: RegUnit) -> RegUnit {
mem::replace(
match *self {
Move::Reg { ref mut to, .. } | Move::Fill { ref mut to, .. } => to,
Move::Spill { .. } => panic!("No to register in a spill {}", self),
},
new,
)
}
fn change_to_spill(&mut self, slot: usize) -> RegUnit {
match self.clone() {
Move::Reg {
value,
rc,
from,
to,
} => {
*self = Move::Spill {
value,
rc,
from,
to_slot: slot,
};
to
}
_ => panic!("Expected reg move: {}", self),
}
}
fn value(&self) -> Value {
match *self {
Move::Reg { value, .. } | Move::Fill { value, .. } | Move::Spill { value, .. } => value,
}
}
fn rc(&self) -> RegClass {
match *self {
Move::Reg { rc, .. } | Move::Fill { rc, .. } | Move::Spill { rc, .. } => rc,
}
}
}
impl fmt::Display for Move {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match *self {
Move::Reg {
value,
from,
to,
rc,
} => write!(
f,
"{}:{}({} -> {})",
value,
rc,
rc.info.display_regunit(from),
rc.info.display_regunit(to)
),
Move::Spill {
value,
from,
to_slot,
rc,
} => write!(
f,
"{}:{}({} -> slot {})",
value,
rc,
rc.info.display_regunit(from),
to_slot
),
Move::Fill {
value,
from_slot,
to,
rc,
} => write!(
f,
"{}:{}(slot {} -> {})",
value,
rc,
from_slot,
rc.info.display_regunit(to)
),
}
}
}
impl fmt::Debug for Move {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let as_display: &fmt::Display = self;
as_display.fmt(f)
}
}
pub struct Solver {
assignments: SparseMap<Value, Assignment>,
vars: Vec<Variable>,
inputs_done: bool,
regs_in: RegisterSet,
regs_out: RegisterSet,
moves: Vec<Move>,
fills: Vec<Move>,
}
impl Solver {
pub fn new() -> Self {
Self {
assignments: SparseMap::new(),
vars: Vec::new(),
inputs_done: false,
regs_in: RegisterSet::new(),
regs_out: RegisterSet::new(),
moves: Vec::new(),
fills: Vec::new(),
}
}
pub fn clear(&mut self) {
self.assignments.clear();
self.vars.clear();
self.inputs_done = false;
self.regs_in = RegisterSet::new();
self.regs_out = RegisterSet::new();
self.moves.clear();
self.fills.clear();
}
pub fn reset(&mut self, regs: &RegisterSet) {
self.assignments.clear();
self.vars.clear();
self.inputs_done = false;
self.regs_in = regs.clone();
self.regs_out = RegisterSet::new();
self.moves.clear();
self.fills.clear();
}
pub fn reassign_in(&mut self, value: Value, rc: RegClass, from: RegUnit, to: RegUnit) {
dbg!(
"reassign_in({}:{}, {} -> {})",
value,
rc,
rc.info.display_regunit(from),
rc.info.display_regunit(to)
);
debug_assert!(!self.inputs_done);
if self.regs_in.is_avail(rc, from) {
if let Some(idx) = self.vars.iter().position(|v| v.value == value) {
let v = self.vars.remove(idx);
dbg!("-> converting variable {} to a fixed constraint", v);
debug_assert!(
v.constraint.contains(to),
"Incompatible constraints for {}",
value
);
} else {
panic!("Invalid from register for fixed {} constraint", value);
}
}
self.regs_in.free(rc, from);
self.regs_out.take(rc, to);
self.assignments.insert(Assignment {
value,
rc,
from,
to,
});
}
pub fn add_var(&mut self, value: Value, constraint: RegClass, from: RegUnit) {
dbg!(
"add_var({}:{}, from={})",
value,
constraint,
constraint.info.display_regunit(from)
);
debug_assert!(!self.inputs_done);
self.add_live_var(value, constraint, from, true);
}
pub fn add_killed_var(&mut self, value: Value, constraint: RegClass, from: RegUnit) {
dbg!(
"add_killed_var({}:{}, from={})",
value,
constraint,
constraint.info.display_regunit(from)
);
debug_assert!(self.inputs_done);
self.add_live_var(value, constraint, from, false);
}
pub fn add_through_var(&mut self, value: Value, constraint: RegClass, from: RegUnit) {
dbg!(
"add_through_var({}:{}, from={})",
value,
constraint,
constraint.info.display_regunit(from)
);
debug_assert!(self.inputs_done);
self.add_live_var(value, constraint, from, true);
}
fn add_live_var(
&mut self,
value: Value,
constraint: RegClass,
from: RegUnit,
live_through: bool,
) {
if self.regs_in.is_avail(constraint, from) {
if let Some(v) = self.vars.iter_mut().find(|v| v.value == value) {
if let Some(rc) = v.constraint.intersect(constraint) {
dbg!("-> combining constraint with {} yields {}", v, rc);
v.constraint = rc;
return;
} else {
panic!("Incompatible constraints: {} + {}", constraint, v)
}
}
if let Some(a) = self.assignments.get(value) {
dbg!("-> already fixed assignment {}", a);
debug_assert!(
constraint.contains(a.to),
"Incompatible constraints for {}",
value
);
return;
}
dbg!("{}", self);
panic!("Wrong from register for {}", value);
}
let new_var = Variable::new_live(value, constraint, from, live_through);
dbg!("-> new var: {}", new_var);
self.regs_in.free(constraint, from);
if self.inputs_done && live_through {
self.regs_out.free(constraint, from);
}
self.vars.push(new_var);
}
pub fn has_fixed_input_conflicts(&self) -> bool {
debug_assert!(!self.inputs_done);
self.regs_out.interferes_with(&self.regs_in)
}
pub fn is_fixed_input_conflict(&self, rc: RegClass, reg: RegUnit) -> bool {
debug_assert!(!self.inputs_done);
!self.regs_out.is_avail(rc, reg)
}
pub fn inputs_done(&mut self) {
debug_assert!(!self.has_fixed_input_conflicts());
self.regs_in.intersect(&self.regs_out);
self.regs_out = self.regs_in.clone();
self.inputs_done = true;
}
pub fn add_kill(&mut self, value: Value, rc: RegClass, reg: RegUnit) {
debug_assert!(self.inputs_done);
if let Some(a) = self.assignments.get(value) {
debug_assert_eq!(a.from, reg);
self.regs_out.free(a.rc, a.to);
return;
}
if let Some(v) = self.vars.iter_mut().find(|v| v.value == value) {
debug_assert!(v.is_input);
v.is_output = false;
return;
}
self.regs_out.free(rc, reg);
}
pub fn add_tied_input(
&mut self,
value: Value,
rc: RegClass,
reg: RegUnit,
is_global: bool,
) -> Option<RegUnit> {
debug_assert!(self.inputs_done);
if let Some(a) = self.assignments.get(value) {
debug_assert_eq!(a.from, reg);
self.regs_out.take(a.rc, a.to);
return Some(a.to);
}
if let Some(v) = self.vars.iter_mut().find(|v| v.value == value) {
debug_assert!(v.is_input);
v.is_output = true;
v.is_global = is_global;
return None;
}
if is_global {
let mut new_var = Variable::new_live(value, rc, reg, true);
new_var.is_global = true;
dbg!("add_tied_input: new tied-global value: {}", new_var);
self.vars.push(new_var);
self.regs_in.free(rc, reg);
} else {
self.regs_out.take(rc, reg);
}
None
}
#[allow(dead_code)]
pub fn add_fixed_output(&mut self, rc: RegClass, reg: RegUnit) -> bool {
debug_assert!(self.inputs_done);
if self.regs_out.is_avail(rc, reg) {
self.regs_out.take(rc, reg);
true
} else {
false
}
}
pub fn add_def(&mut self, value: Value, constraint: RegClass, is_global: bool) {
debug_assert!(self.inputs_done);
self.vars
.push(Variable::new_def(value, constraint, is_global));
}
pub fn clear_all_global_flags(&mut self) {
for v in &mut self.vars {
v.is_global = false;
}
}
}
pub enum SolverError {
Divert(RegClass),
Global(Value),
}
impl Solver {
pub fn quick_solve(&mut self, global_regs: &RegisterSet) -> Result<RegisterSet, SolverError> {
self.find_solution(global_regs)
}
pub fn real_solve(&mut self, global_regs: &RegisterSet) -> Result<RegisterSet, SolverError> {
for v in &mut self.vars {
let d = v.iter(&self.regs_in, &self.regs_out, global_regs).len();
v.domain = cmp::min(d, u16::MAX as usize) as u16;
}
self.vars.sort_unstable_by_key(|v| {
(
v.domain,
!(v.is_input && v.is_output),
!v.solution,
v.from.unwrap_or(0),
v.value,
)
});
dbg!("real_solve for {}", self);
self.find_solution(global_regs)
}
fn find_solution(&mut self, global_regs: &RegisterSet) -> Result<RegisterSet, SolverError> {
let mut iregs = self.regs_in.clone();
let mut oregs = self.regs_out.clone();
let mut gregs = global_regs.clone();
for v in &mut self.vars {
let rc = v.constraint;
let reg = match v.iter(&iregs, &oregs, &gregs).next() {
Some(reg) => reg,
None => {
if v.is_global && gregs.iter(rc).next().is_none() {
return Err(SolverError::Global(v.value));
} else {
return Err(SolverError::Divert(rc));
}
}
};
v.solution = reg;
if v.is_input {
iregs.take(rc, reg);
}
if v.is_output {
oregs.take(rc, reg);
}
if v.is_global {
gregs.take(rc, reg);
}
}
Ok(oregs)
}
pub fn vars(&self) -> &[Variable] {
&self.vars
}
pub fn can_add_var(&mut self, _value: Value, constraint: RegClass, from: RegUnit) -> bool {
!self.regs_in.is_avail(constraint, from)
}
}
impl Solver {
fn collect_moves(&mut self) {
self.moves.clear();
for v in &self.vars {
if let Some(from) = v.from {
if from != v.solution {
self.moves.push(Move::Reg {
value: v.value,
from,
to: v.solution,
rc: v.constraint,
});
}
}
}
self.moves
.extend(self.assignments.values().filter_map(Move::with_assignment));
if !(self.moves.is_empty()) {
dbg!("collect_moves: {}", DisplayList(&self.moves));
}
}
pub fn schedule_moves(&mut self, regs: &RegisterSet) -> usize {
self.collect_moves();
debug_assert!(self.fills.is_empty());
let mut num_spill_slots = 0;
let mut avail = regs.clone();
let mut i = 0;
while i < self.moves.len() + self.fills.len() {
if i >= self.moves.len() {
self.moves.append(&mut self.fills);
}
if let Some(j) = self.moves[i..].iter().position(|m| match m.to_reg() {
Some((rc, reg)) => avail.is_avail(rc, reg),
None => true,
}) {
self.moves.swap(i, i + j);
let m = &self.moves[i];
if let Some((rc, reg)) = m.to_reg() {
avail.take(rc, reg);
}
if let Some((rc, reg)) = m.from_reg() {
avail.free(rc, reg);
}
dbg!("move #{}: {}", i, m);
i += 1;
continue;
}
let j = self.moves[i..]
.iter()
.enumerate()
.min_by_key(|&(_, m)| !m.rc().width)
.unwrap()
.0;
self.moves.swap(i, i + j);
let m = self.moves[i].clone();
let toprc = m.rc().toprc();
if let Some(reg) = avail.iter(toprc).next() {
dbg!(
"breaking cycle at {} with available {} register {}",
m,
toprc,
toprc.info.display_regunit(reg)
);
let old_to_reg = self.moves[i].replace_to_reg(reg);
self.moves.push(Move::Reg {
value: m.value(),
rc: toprc,
from: reg,
to: old_to_reg,
});
continue;
}
let slot = num_spill_slots;
num_spill_slots += 1;
dbg!("breaking cycle at {} with slot {}", m, slot);
let old_to_reg = self.moves[i].change_to_spill(slot);
self.fills.push(Move::Fill {
value: m.value(),
rc: toprc,
from_slot: slot,
to: old_to_reg,
});
}
num_spill_slots
}
pub fn moves(&self) -> &[Move] {
&self.moves
}
}
impl fmt::Display for Solver {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let reginfo = self.vars.first().map(|v| v.constraint.info);
writeln!(f, "Solver {{ inputs_done: {},", self.inputs_done)?;
writeln!(f, " in: {}", self.regs_in.display(reginfo))?;
writeln!(f, " out: {}", self.regs_out.display(reginfo))?;
writeln!(
f,
" assignments: {}",
DisplayList(self.assignments.as_slice())
)?;
writeln!(f, " vars: {}", DisplayList(&self.vars))?;
writeln!(f, " moves: {}", DisplayList(&self.moves))?;
writeln!(f, "}}")
}
}
#[cfg(test)]
#[cfg(build_arm32)]
mod tests {
use super::{Move, Solver};
use entity::EntityRef;
use ir::Value;
use isa::{RegClass, RegInfo, RegUnit, TargetIsa};
use regalloc::RegisterSet;
use std::boxed::Box;
use std::str::FromStr;
use target_lexicon;
fn arm32() -> Option<Box<TargetIsa>> {
use isa;
use settings;
let shared_builder = settings::builder();
let shared_flags = settings::Flags::new(shared_builder);
isa::lookup(triple!("arm"))
.ok()
.map(|b| b.finish(shared_flags))
}
fn rc_by_name(reginfo: &RegInfo, name: &str) -> RegClass {
reginfo
.classes
.iter()
.find(|rc| rc.name == name)
.expect("Can't find named register class.")
}
fn mov(value: Value, rc: RegClass, from: RegUnit, to: RegUnit) -> Move {
Move::Reg {
value,
rc,
from,
to,
}
}
fn spill(value: Value, rc: RegClass, from: RegUnit, to_slot: usize) -> Move {
Move::Spill {
value,
rc,
from,
to_slot,
}
}
fn fill(value: Value, rc: RegClass, from_slot: usize, to: RegUnit) -> Move {
Move::Fill {
value,
rc,
from_slot,
to,
}
}
#[test]
fn simple_moves() {
let isa = arm32().expect("This test requires arm32 support");
let reginfo = isa.register_info();
let gpr = rc_by_name(®info, "GPR");
let r0 = gpr.unit(0);
let r1 = gpr.unit(1);
let r2 = gpr.unit(2);
let gregs = RegisterSet::new();
let mut regs = RegisterSet::new();
let mut solver = Solver::new();
let v10 = Value::new(10);
let v11 = Value::new(11);
regs.take(gpr, r1);
solver.reset(®s);
solver.reassign_in(v10, gpr, r1, r0);
solver.inputs_done();
assert!(solver.quick_solve(&gregs).is_ok());
assert_eq!(solver.schedule_moves(®s), 0);
assert_eq!(solver.moves(), &[mov(v10, gpr, r1, r0)]);
regs.take(gpr, r0);
solver.reset(®s);
solver.reassign_in(v10, gpr, r0, r1);
solver.reassign_in(v11, gpr, r1, r2);
solver.inputs_done();
assert!(solver.quick_solve(&gregs).is_ok());
assert_eq!(solver.schedule_moves(®s), 0);
assert_eq!(
solver.moves(),
&[mov(v11, gpr, r1, r2), mov(v10, gpr, r0, r1)]
);
solver.reset(®s);
solver.reassign_in(v10, gpr, r0, r1);
solver.reassign_in(v11, gpr, r1, r0);
solver.inputs_done();
assert!(solver.quick_solve(&gregs).is_ok());
assert_eq!(solver.schedule_moves(®s), 0);
assert_eq!(
solver.moves(),
&[
mov(v10, gpr, r0, r2),
mov(v11, gpr, r1, r0),
mov(v10, gpr, r2, r1),
]
);
}
#[test]
fn harder_move_cycles() {
let isa = arm32().expect("This test requires arm32 support");
let reginfo = isa.register_info();
let s = rc_by_name(®info, "S");
let d = rc_by_name(®info, "D");
let d0 = d.unit(0);
let d1 = d.unit(1);
let d2 = d.unit(2);
let s0 = s.unit(0);
let s1 = s.unit(1);
let s2 = s.unit(2);
let s3 = s.unit(3);
let gregs = RegisterSet::new();
let mut regs = RegisterSet::new();
let mut solver = Solver::new();
let v10 = Value::new(10);
let v11 = Value::new(11);
let v12 = Value::new(12);
regs.take(d, d0);
regs.take(d, d1);
solver.reset(®s);
solver.reassign_in(v10, d, d0, d1);
solver.reassign_in(v11, s, s2, s0);
solver.reassign_in(v12, s, s3, s1);
solver.inputs_done();
assert!(solver.quick_solve(&gregs).is_ok());
assert_eq!(solver.schedule_moves(®s), 0);
assert_eq!(
solver.moves(),
&[
mov(v10, d, d0, d2),
mov(v11, s, s2, s0),
mov(v12, s, s3, s1),
mov(v10, d, d2, d1),
]
);
solver.reset(®s);
solver.reassign_in(v11, s, s0, s2);
solver.reassign_in(v12, s, s1, s3);
solver.reassign_in(v10, d, d1, d0);
solver.inputs_done();
assert!(solver.quick_solve(&gregs).is_ok());
assert_eq!(solver.schedule_moves(®s), 0);
assert_eq!(
solver.moves(),
&[
mov(v10, d, d1, d2),
mov(v12, s, s1, s3),
mov(v11, s, s0, s2),
mov(v10, d, d2, d0),
]
);
}
#[test]
fn emergency_spill() {
let isa = arm32().expect("This test requires arm32 support");
let reginfo = isa.register_info();
let gpr = rc_by_name(®info, "GPR");
let r0 = gpr.unit(0);
let r1 = gpr.unit(1);
let r2 = gpr.unit(2);
let r3 = gpr.unit(3);
let r4 = gpr.unit(4);
let r5 = gpr.unit(5);
let gregs = RegisterSet::new();
let mut regs = RegisterSet::new();
let mut solver = Solver::new();
let v10 = Value::new(10);
let v11 = Value::new(11);
let v12 = Value::new(12);
let v13 = Value::new(13);
let v14 = Value::new(14);
let v15 = Value::new(15);
for i in 0..16 {
regs.take(gpr, gpr.unit(i));
}
solver.reset(®s);
solver.reassign_in(v10, gpr, r0, r1);
solver.reassign_in(v11, gpr, r1, r2);
solver.reassign_in(v12, gpr, r2, r0);
solver.inputs_done();
assert!(solver.quick_solve(&gregs).is_ok());
assert_eq!(solver.schedule_moves(®s), 1);
assert_eq!(
solver.moves(),
&[
spill(v10, gpr, r0, 0),
mov(v12, gpr, r2, r0),
mov(v11, gpr, r1, r2),
fill(v10, gpr, 0, r1),
]
);
solver.reset(®s);
solver.reassign_in(v10, gpr, r0, r1);
solver.reassign_in(v11, gpr, r1, r2);
solver.reassign_in(v12, gpr, r2, r0);
solver.reassign_in(v13, gpr, r3, r4);
solver.reassign_in(v14, gpr, r4, r5);
solver.reassign_in(v15, gpr, r5, r3);
solver.inputs_done();
assert!(solver.quick_solve(&gregs).is_ok());
assert_eq!(solver.schedule_moves(®s), 1);
assert_eq!(
solver.moves(),
&[
spill(v10, gpr, r0, 0),
mov(v12, gpr, r2, r0),
mov(v11, gpr, r1, r2),
mov(v13, gpr, r3, r1), mov(v15, gpr, r5, r3),
mov(v14, gpr, r4, r5),
mov(v13, gpr, r1, r4),
fill(v10, gpr, 0, r1), ]
);
}
}