use log::{info, log_enabled, trace, Level};
use std::default;
use std::env;
use std::fmt;
use crate::data_structures::{BlockIx, InstIx, InstPoint, Point, RealReg, RegVecsAndBounds};
use crate::inst_stream::{add_spills_reloads_and_moves, InstToInsertAndExtPoint};
use crate::{
checker::CheckerContext, reg_maps::MentionRegUsageMapper, Function, RealRegUniverse,
RegAllocError, RegAllocResult, RegClass, Set, SpillSlot, VirtualReg, NUM_REG_CLASSES,
};
use analysis::{AnalysisInfo, RangeFrag};
use smallvec::SmallVec;
mod analysis;
mod assign_registers;
mod resolve_moves;
#[derive(Default)]
pub(crate) struct Statistics {
only_large: bool,
num_fixed: usize,
num_vregs: usize,
num_virtual_ranges: usize,
peak_active: usize,
peak_inactive: usize,
num_try_allocate_reg: usize,
num_try_allocate_reg_success: usize,
num_reg_splits: usize,
num_reg_splits_success: usize,
}
impl Drop for Statistics {
fn drop(&mut self) {
if self.only_large && self.num_vregs < 1000 {
return;
}
println!(
"stats: {} fixed; {} vreg; {} vranges; {} peak-active; {} peak-inactive, {} direct-alloc; {} total-alloc; {} partial-splits; {} partial-splits-attempts",
self.num_fixed,
self.num_vregs,
self.num_virtual_ranges,
self.peak_active,
self.peak_inactive,
self.num_try_allocate_reg_success,
self.num_try_allocate_reg,
self.num_reg_splits_success,
self.num_reg_splits,
);
}
}
#[derive(Copy, Clone, Debug)]
enum OptimalSplitStrategy {
From,
To,
NextFrom,
NextNextFrom,
PrevTo,
PrevPrevTo,
Mid,
}
#[derive(Clone)]
pub struct LinearScanOptions {
split_strategy: OptimalSplitStrategy,
partial_split: bool,
partial_split_near_end: bool,
stats: bool,
large_stats: bool,
}
impl default::Default for LinearScanOptions {
fn default() -> Self {
let optimal_split_strategy = match env::var("LSRA_SPLIT") {
Ok(s) => match s.as_str() {
"t" | "to" => OptimalSplitStrategy::To,
"n" => OptimalSplitStrategy::NextFrom,
"nn" => OptimalSplitStrategy::NextNextFrom,
"p" => OptimalSplitStrategy::PrevTo,
"pp" => OptimalSplitStrategy::PrevPrevTo,
"m" | "mid" => OptimalSplitStrategy::Mid,
_ => OptimalSplitStrategy::From,
},
Err(_) => OptimalSplitStrategy::From,
};
let large_stats = env::var("LSRA_LARGE_STATS").is_ok();
let stats = env::var("LSRA_STATS").is_ok() || large_stats;
let partial_split = env::var("LSRA_PARTIAL").is_ok();
let partial_split_near_end = env::var("LSRA_PARTIAL_END").is_ok();
Self {
split_strategy: optimal_split_strategy,
partial_split,
partial_split_near_end,
stats,
large_stats,
}
}
}
impl fmt::Debug for LinearScanOptions {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
writeln!(fmt, "linear scan")?;
write!(fmt, " split: {:?}", self.split_strategy)
}
}
type RegUses = RegVecsAndBounds;
#[derive(Clone, Copy, PartialEq, Eq)]
struct IntId(pub(crate) usize);
impl fmt::Debug for IntId {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
write!(fmt, "int{}", self.0)
}
}
#[derive(Clone)]
struct FixedInterval {
reg: RealReg,
frags: Vec<RangeFrag>,
}
impl fmt::Display for FixedInterval {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "fixed {:?} [", self.reg)?;
for (i, frag) in self.frags.iter().enumerate() {
if i > 0 {
write!(f, ", ")?;
}
write!(f, "({:?}, {:?})", frag.first, frag.last)?;
}
write!(f, "]")
}
}
#[derive(Clone)]
pub(crate) struct VirtualInterval {
id: IntId,
vreg: VirtualReg,
parent: Option<IntId>,
ancestor: Option<IntId>,
child: Option<IntId>,
location: Location,
mentions: MentionMap,
start: InstPoint,
end: InstPoint,
}
impl fmt::Display for VirtualInterval {
fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(fmt, "virtual {:?}", self.id)?;
if let Some(ref p) = self.parent {
write!(fmt, " (parent={:?})", p)?;
}
write!(
fmt,
": {:?} {} [{:?}; {:?}]",
self.vreg, self.location, self.start, self.end
)
}
}
impl VirtualInterval {
fn new(
id: IntId,
vreg: VirtualReg,
start: InstPoint,
end: InstPoint,
mentions: MentionMap,
) -> Self {
Self {
id,
vreg,
parent: None,
ancestor: None,
child: None,
location: Location::None,
mentions,
start,
end,
}
}
fn mentions(&self) -> &MentionMap {
&self.mentions
}
fn mentions_mut(&mut self) -> &mut MentionMap {
&mut self.mentions
}
fn covers(&self, pos: InstPoint) -> bool {
self.start <= pos && pos <= self.end
}
}
#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
pub struct Mention(u8);
impl fmt::Debug for Mention {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
let mut comma = false;
if self.0 & 1 == 1 {
write!(fmt, "use")?;
comma = true;
}
if (self.0 >> 1) & 1 == 1 {
if comma {
write!(fmt, ",")?;
}
write!(fmt, "mod")?;
comma = true;
}
if (self.0 >> 2) & 1 == 1 {
if comma {
write!(fmt, ",")?;
}
write!(fmt, "def")?;
}
Ok(())
}
}
impl Mention {
fn new() -> Self {
Self(0)
}
fn add_use(&mut self) {
self.0 |= 1 << 0;
}
fn add_mod(&mut self) {
self.0 |= 1 << 1;
}
fn add_def(&mut self) {
self.0 |= 1 << 2;
}
fn remove_use(&mut self) {
self.0 &= !(1 << 0);
}
fn is_use(&self) -> bool {
(self.0 & 0b001) != 0
}
fn is_mod(&self) -> bool {
(self.0 & 0b010) != 0
}
fn is_def(&self) -> bool {
(self.0 & 0b100) != 0
}
fn is_use_or_mod(&self) -> bool {
(self.0 & 0b011) != 0
}
fn is_mod_or_def(&self) -> bool {
(self.0 & 0b110) != 0
}
}
pub type MentionMap = SmallVec<[(InstIx, Mention); 2]>;
#[derive(Debug, Clone, Copy)]
pub(crate) enum Location {
None,
Reg(RealReg),
Stack(SpillSlot),
}
impl Location {
pub(crate) fn reg(&self) -> Option<RealReg> {
match self {
Location::Reg(reg) => Some(*reg),
_ => None,
}
}
pub(crate) fn spill(&self) -> Option<SpillSlot> {
match self {
Location::Stack(slot) => Some(*slot),
_ => None,
}
}
pub(crate) fn is_none(&self) -> bool {
match self {
Location::None => true,
_ => false,
}
}
}
impl fmt::Display for Location {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
match self {
Location::None => write!(fmt, "none"),
Location::Reg(reg) => write!(fmt, "{:?}", reg),
Location::Stack(slot) => write!(fmt, "{:?}", slot),
}
}
}
pub struct Intervals {
virtuals: Vec<VirtualInterval>,
fixeds: Vec<FixedInterval>,
}
impl Intervals {
fn get(&self, int_id: IntId) -> &VirtualInterval {
&self.virtuals[int_id.0]
}
fn get_mut(&mut self, int_id: IntId) -> &mut VirtualInterval {
&mut self.virtuals[int_id.0]
}
fn num_virtual_intervals(&self) -> usize {
self.virtuals.len()
}
fn set_reg(&mut self, int_id: IntId, reg: RealReg) {
let int = self.get_mut(int_id);
debug_assert!(int.location.is_none());
int.location = Location::Reg(reg);
}
fn set_spill(&mut self, int_id: IntId, slot: SpillSlot) {
let int = self.get_mut(int_id);
debug_assert!(int.location.spill().is_none());
int.location = Location::Stack(slot);
}
fn push_interval(&mut self, int: VirtualInterval) {
debug_assert!(int.id.0 == self.virtuals.len());
self.virtuals.push(int);
}
fn set_child(&mut self, int_id: IntId, child_id: IntId) {
if let Some(prev_child) = self.virtuals[int_id.0].child.clone() {
self.virtuals[child_id.0].child = Some(prev_child);
self.virtuals[prev_child.0].parent = Some(child_id);
}
self.virtuals[int_id.0].child = Some(child_id);
}
}
#[inline(never)]
fn next_use(interval: &VirtualInterval, pos: InstPoint, _reg_uses: &RegUses) -> Option<InstPoint> {
if log_enabled!(Level::Trace) {
trace!("find next use of {} after {:?}", interval, pos);
}
let mentions = interval.mentions();
let target = InstPoint::max(pos, interval.start);
let ret = match mentions.binary_search_by_key(&target.iix(), |mention| mention.0) {
Ok(index) => {
let mention = &mentions[index];
if target.pt() == Point::Use {
if mention.1.is_use_or_mod() {
Some(InstPoint::new_use(mention.0))
} else {
Some(InstPoint::new_def(mention.0))
}
} else if target.pt() == Point::Def && mention.1.is_mod_or_def() {
Some(target)
} else if index == mentions.len() - 1 {
None
} else {
let mention = &mentions[index + 1];
if mention.1.is_use_or_mod() {
Some(InstPoint::new_use(mention.0))
} else {
Some(InstPoint::new_def(mention.0))
}
}
}
Err(index) => {
if index == mentions.len() {
None
} else {
let mention = &mentions[index];
if mention.1.is_use_or_mod() {
Some(InstPoint::new_use(mention.0))
} else {
Some(InstPoint::new_def(mention.0))
}
}
}
};
let ret = match ret {
Some(pos) => {
if pos <= interval.end {
Some(pos)
} else {
None
}
}
None => None,
};
ret
}
#[inline(never)]
fn last_use(interval: &VirtualInterval, pos: InstPoint, _reg_uses: &RegUses) -> Option<InstPoint> {
if log_enabled!(Level::Trace) {
trace!("searching last use of {} before {:?}", interval, pos,);
}
let mentions = interval.mentions();
let target = InstPoint::min(pos, interval.end);
let ret = match mentions.binary_search_by_key(&target.iix(), |mention| mention.0) {
Ok(index) => {
let mention = &mentions[index];
if target.pt() == Point::Def {
if mention.1.is_mod_or_def() {
Some(InstPoint::new_def(mention.0))
} else {
Some(InstPoint::new_use(mention.0))
}
} else if target.pt() == Point::Use && mention.1.is_use() {
Some(target)
} else if index == 0 {
None
} else {
let mention = &mentions[index - 1];
if mention.1.is_mod_or_def() {
Some(InstPoint::new_def(mention.0))
} else {
Some(InstPoint::new_use(mention.0))
}
}
}
Err(index) => {
if index == 0 {
None
} else {
let mention = &mentions[index - 1];
if mention.1.is_mod_or_def() {
Some(InstPoint::new_def(mention.0))
} else {
Some(InstPoint::new_use(mention.0))
}
}
}
};
let ret = match ret {
Some(pos) => {
if pos >= interval.start {
Some(pos)
} else {
None
}
}
None => None,
};
trace!("mentions: {:?}", mentions);
trace!("found: {:?}", ret);
ret
}
fn compute_scratches(
reg_universe: &RealRegUniverse,
) -> Result<Vec<Option<RealReg>>, RegAllocError> {
let mut scratches_by_rc = vec![None; NUM_REG_CLASSES];
for i in 0..NUM_REG_CLASSES {
if let Some(info) = ®_universe.allocable_by_class[i] {
if info.first == info.last {
return Err(RegAllocError::Other(
"at least 2 registers required for linear scan".into(),
));
}
let scratch = if let Some(suggested_reg) = info.suggested_scratch {
reg_universe.regs[suggested_reg].0
} else {
return Err(RegAllocError::MissingSuggestedScratchReg(
RegClass::rc_from_u32(i as u32),
));
};
scratches_by_rc[i] = Some(scratch);
}
}
Ok(scratches_by_rc)
}
#[inline(never)]
pub(crate) fn run<F: Function>(
func: &mut F,
reg_universe: &RealRegUniverse,
use_checker: bool,
opts: &LinearScanOptions,
) -> Result<RegAllocResult<F>, RegAllocError> {
let AnalysisInfo {
reg_vecs_and_bounds: reg_uses,
intervals,
liveins,
liveouts,
..
} = analysis::run(func, reg_universe).map_err(|err| RegAllocError::Analysis(err))?;
let scratches_by_rc = compute_scratches(reg_universe)?;
let stats = if opts.stats {
let mut stats = Statistics::default();
stats.num_fixed = intervals.fixeds.len();
stats.num_virtual_ranges = intervals.virtuals.len();
stats.num_vregs = intervals
.virtuals
.iter()
.map(|virt| virt.vreg.get_index())
.fold(0, |a, b| usize::max(a, b));
stats.only_large = opts.large_stats;
Some(stats)
} else {
None
};
if log_enabled!(Level::Trace) {
trace!("fixed intervals:");
for int in &intervals.fixeds {
trace!("{}", int);
}
trace!("");
trace!("unassigned intervals:");
for int in &intervals.virtuals {
trace!("{}", int);
for mention in &int.mentions {
trace!(" mention @ {:?}: {:?}", mention.0, mention.1);
}
}
trace!("");
}
let (intervals, mut num_spill_slots) = assign_registers::run(
opts,
func,
®_uses,
reg_universe,
&scratches_by_rc,
intervals,
stats,
)?;
let virtuals = &intervals.virtuals;
let memory_moves = resolve_moves::run(
func,
®_uses,
virtuals,
&liveins,
&liveouts,
&mut num_spill_slots,
&scratches_by_rc,
);
apply_registers(
func,
virtuals,
memory_moves,
reg_universe,
num_spill_slots,
use_checker,
)
}
#[inline(never)]
fn set_registers<F: Function>(
func: &mut F,
virtual_intervals: &Vec<VirtualInterval>,
reg_universe: &RealRegUniverse,
use_checker: bool,
memory_moves: &Vec<InstToInsertAndExtPoint>,
) -> Set<RealReg> {
info!("set_registers");
let mut checker: Option<CheckerContext> = None;
let mut insn_blocks: Vec<BlockIx> = vec![];
if use_checker {
checker = Some(CheckerContext::new(
func,
reg_universe,
memory_moves,
&[],
&[],
&[],
));
insn_blocks.resize(func.insns().len(), BlockIx::new(0));
for block_ix in func.blocks() {
for insn_ix in func.block_insns(block_ix) {
insn_blocks[insn_ix.get() as usize] = block_ix;
}
}
}
let mut clobbered_registers = Set::empty();
let capacity = virtual_intervals
.iter()
.map(|int| int.mentions.len())
.fold(0, |a, b| a + b);
if capacity == 0 {
return clobbered_registers;
}
let mut mention_map = Vec::with_capacity(capacity);
for int in virtual_intervals {
let rreg = match int.location.reg() {
Some(rreg) => rreg,
_ => continue,
};
trace!("int: {}", int);
trace!(" {:?}", int.mentions);
for &mention in &int.mentions {
mention_map.push((mention.0, mention.1, int.vreg, rreg));
}
}
mention_map.sort_unstable_by_key(|quad| quad.0);
let mut mapper = MentionRegUsageMapper::new();
let flush_inst = |func: &mut F,
mapper: &mut MentionRegUsageMapper,
iix: InstIx,
checker: Option<&mut CheckerContext>| {
trace!("map_regs for {:?}", iix);
let mut inst = func.get_insn_mut(iix);
F::map_regs(&mut inst, mapper);
if let Some(checker) = checker {
let block_ix = insn_blocks[iix.get() as usize];
checker
.handle_insn(reg_universe, func, block_ix, iix, mapper)
.unwrap();
}
mapper.clear();
};
let mut prev_iix = mention_map[0].0;
for (iix, mention_set, vreg, rreg) in mention_map {
if prev_iix != iix {
flush_inst(func, &mut mapper, prev_iix, checker.as_mut());
prev_iix = iix;
}
trace!(
"{:?}: {:?} is in {:?} at {:?}",
iix,
vreg,
rreg,
mention_set
);
if mention_set.is_use() {
if let Some(prev_rreg) = mapper.lookup_use(vreg) {
debug_assert_eq!(prev_rreg, rreg, "different use allocs for {:?}", vreg);
}
mapper.set_use(vreg, rreg);
}
let included_in_clobbers = func.is_included_in_clobbers(func.get_insn(iix));
if mention_set.is_mod() {
if let Some(prev_rreg) = mapper.lookup_use(vreg) {
debug_assert_eq!(prev_rreg, rreg, "different use allocs for {:?}", vreg);
}
if let Some(prev_rreg) = mapper.lookup_def(vreg) {
debug_assert_eq!(prev_rreg, rreg, "different def allocs for {:?}", vreg);
}
mapper.set_use(vreg, rreg);
mapper.set_def(vreg, rreg);
if included_in_clobbers {
clobbered_registers.insert(rreg);
}
}
if mention_set.is_def() {
if let Some(prev_rreg) = mapper.lookup_def(vreg) {
debug_assert_eq!(prev_rreg, rreg, "different def allocs for {:?}", vreg);
}
mapper.set_def(vreg, rreg);
if included_in_clobbers {
clobbered_registers.insert(rreg);
}
}
}
flush_inst(func, &mut mapper, prev_iix, checker.as_mut());
clobbered_registers
}
#[inline(never)]
fn apply_registers<F: Function>(
func: &mut F,
virtual_intervals: &Vec<VirtualInterval>,
memory_moves: Vec<InstToInsertAndExtPoint>,
reg_universe: &RealRegUniverse,
num_spill_slots: u32,
use_checker: bool,
) -> Result<RegAllocResult<F>, RegAllocError> {
info!("apply_registers");
let clobbered_registers = set_registers(
func,
virtual_intervals,
reg_universe,
use_checker,
&memory_moves,
);
let safepoint_insns = vec![];
let (final_insns, target_map, new_to_old_insn_map, new_safepoint_insns) =
add_spills_reloads_and_moves(func, &safepoint_insns, memory_moves)
.map_err(|e| RegAllocError::Other(e))?;
assert!(new_safepoint_insns.is_empty());
clobbered_registers.filter_map(|®| {
if reg.get_index() >= reg_universe.allocable {
None
} else {
Some(reg)
}
});
Ok(RegAllocResult {
insns: final_insns,
target_map,
orig_insn_map: new_to_old_insn_map,
clobbered_registers,
num_spill_slots,
block_annotations: None,
stackmaps: vec![],
new_safepoint_insns,
})
}