use crate::{RealReg, RegUsageMapper, VirtualReg};
use smallvec::SmallVec;
use std::mem;
#[derive(Debug)]
pub struct VrangeRegUsageMapper {
slots: Vec<RealReg>,
overlay: SmallVec<[(VirtualReg, RealReg); 16]>,
}
impl VrangeRegUsageMapper {
pub(crate) fn new(vreg_capacity: usize) -> VrangeRegUsageMapper {
VrangeRegUsageMapper {
slots: Vec::with_capacity(vreg_capacity),
overlay: SmallVec::new(),
}
}
fn is_overlay_large_enough_to_sort(&self) -> bool {
self.overlay.spilled()
}
pub(crate) fn set_overlay(&mut self, vreg: VirtualReg, rreg: Option<RealReg>) {
let rreg = rreg.unwrap_or(RealReg::invalid());
self.overlay.push((vreg, rreg));
}
pub(crate) fn finish_overlay(&mut self) {
if self.overlay.len() == 0 || !self.is_overlay_large_enough_to_sort() {
return;
}
self.overlay.sort_by_key(|pair| pair.0);
let mut last_vreg = self.overlay[0].0;
let mut out = 0;
for i in 1..self.overlay.len() {
let this_vreg = self.overlay[i].0;
if this_vreg != last_vreg {
out += 1;
}
if i != out {
self.overlay[out] = self.overlay[i];
}
last_vreg = this_vreg;
}
let new_len = out + 1;
self.overlay.truncate(new_len);
}
pub(crate) fn merge_overlay(&mut self) {
let mappings = mem::replace(&mut self.overlay, SmallVec::new());
for (vreg, rreg) in mappings.into_iter() {
self.set_direct_internal(vreg, rreg);
}
}
pub(crate) fn set_direct(&mut self, vreg: VirtualReg, rreg: Option<RealReg>) {
debug_assert!(self.overlay.is_empty());
let rreg = rreg.unwrap_or(RealReg::invalid());
self.set_direct_internal(vreg, rreg);
}
fn set_direct_internal(&mut self, vreg: VirtualReg, rreg: RealReg) {
let idx = vreg.get_index();
if idx >= self.slots.len() {
self.slots.resize(idx + 1, RealReg::invalid());
}
self.slots[idx] = rreg;
}
fn lookup_direct(&self, vreg: VirtualReg) -> Option<RealReg> {
let idx = vreg.get_index();
if idx >= self.slots.len() {
None
} else {
Some(self.slots[idx])
}
}
fn lookup_overlay(&self, vreg: VirtualReg) -> Option<RealReg> {
if self.is_overlay_large_enough_to_sort() {
if let Ok(idx) = self.overlay.binary_search_by_key(&vreg, |pair| pair.0) {
return Some(self.overlay[idx].1);
}
} else {
for &(this_vreg, this_rreg) in self.overlay.iter().rev() {
if this_vreg == vreg {
return Some(this_rreg);
}
}
}
None
}
pub(crate) fn is_empty(&self) -> bool {
self.overlay.iter().all(|pair| pair.1.is_invalid())
&& self.slots.iter().all(|rreg| rreg.is_invalid())
}
}
impl RegUsageMapper for VrangeRegUsageMapper {
fn get_use(&self, vreg: VirtualReg) -> Option<RealReg> {
self.lookup_direct(vreg)
.and_then(|reg| reg.maybe_valid())
}
fn get_def(&self, vreg: VirtualReg) -> Option<RealReg> {
self.lookup_overlay(vreg)
.or_else(|| self.lookup_direct(vreg))
.and_then(|reg| reg.maybe_valid())
}
fn get_mod(&self, vreg: VirtualReg) -> Option<RealReg> {
let result = self.get_use(vreg);
debug_assert_eq!(result, self.get_def(vreg));
result
}
}
#[cfg(test)]
mod test {
use super::*;
use crate::{Reg, RegClass, VirtualReg};
fn vreg(idx: u32) -> VirtualReg {
Reg::new_virtual(RegClass::I64, idx).to_virtual_reg()
}
fn rreg(idx: u8) -> RealReg {
Reg::new_real(RegClass::I64, 0, idx).to_real_reg()
}
#[test]
fn test_reg_use_mapper() {
let mut mapper = VrangeRegUsageMapper::new( 16);
assert_eq!(None, mapper.get_use(vreg(0)));
assert_eq!(None, mapper.get_def(vreg(0)));
assert_eq!(None, mapper.get_mod(vreg(0)));
mapper.set_direct(vreg(0), Some(rreg(1)));
mapper.set_direct(vreg(1), Some(rreg(2)));
assert_eq!(Some(rreg(1)), mapper.get_use(vreg(0)));
assert_eq!(Some(rreg(1)), mapper.get_def(vreg(0)));
assert_eq!(Some(rreg(1)), mapper.get_mod(vreg(0)));
assert_eq!(Some(rreg(2)), mapper.get_use(vreg(1)));
assert_eq!(Some(rreg(2)), mapper.get_def(vreg(1)));
assert_eq!(Some(rreg(2)), mapper.get_mod(vreg(1)));
mapper.set_overlay(vreg(0), Some(rreg(3)));
mapper.set_overlay(vreg(2), Some(rreg(4)));
mapper.finish_overlay();
assert_eq!(Some(rreg(1)), mapper.get_use(vreg(0)));
assert_eq!(Some(rreg(3)), mapper.get_def(vreg(0)));
assert_eq!(Some(rreg(2)), mapper.get_use(vreg(1)));
assert_eq!(Some(rreg(2)), mapper.get_def(vreg(1)));
assert_eq!(Some(rreg(2)), mapper.get_mod(vreg(1)));
assert_eq!(None, mapper.get_use(vreg(2)));
assert_eq!(Some(rreg(4)), mapper.get_def(vreg(2)));
mapper.merge_overlay();
assert_eq!(Some(rreg(3)), mapper.get_use(vreg(0)));
assert_eq!(Some(rreg(2)), mapper.get_use(vreg(1)));
assert_eq!(Some(rreg(4)), mapper.get_use(vreg(2)));
assert_eq!(None, mapper.get_use(vreg(3)));
mapper.set_overlay(vreg(0), None);
mapper.finish_overlay();
assert_eq!(Some(rreg(3)), mapper.get_use(vreg(0)));
assert_eq!(None, mapper.get_def(vreg(0)));
mapper.merge_overlay();
for i in (2..50).rev() {
mapper.set_overlay(vreg(i), Some(rreg((i + 100) as u8)));
}
mapper.finish_overlay();
assert_eq!(None, mapper.get_use(vreg(0)));
assert_eq!(Some(rreg(2)), mapper.get_use(vreg(1)));
assert_eq!(Some(rreg(4)), mapper.get_use(vreg(2)));
for i in 2..50 {
assert_eq!(Some(rreg((i + 100) as u8)), mapper.get_def(vreg(i)));
}
mapper.merge_overlay();
for i in (0..100).rev() {
mapper.set_overlay(vreg(i), None);
}
mapper.finish_overlay();
for i in 0..100 {
assert_eq!(None, mapper.get_def(vreg(i)));
}
assert_eq!(false, mapper.is_empty());
mapper.merge_overlay();
assert_eq!(true, mapper.is_empty());
mapper.set_overlay(vreg(1), Some(rreg(1)));
mapper.set_overlay(vreg(1), Some(rreg(2)));
mapper.finish_overlay();
assert_eq!(Some(rreg(2)), mapper.get_def(vreg(1)));
mapper.merge_overlay();
assert_eq!(Some(rreg(2)), mapper.get_use(vreg(1)));
mapper.set_overlay(vreg(1), Some(rreg(2)));
mapper.set_overlay(vreg(1), None);
mapper.finish_overlay();
assert_eq!(None, mapper.get_def(vreg(1)));
mapper.merge_overlay();
assert_eq!(None, mapper.get_use(vreg(1)));
for i in 0..100 {
mapper.set_overlay(vreg(2), Some(rreg(i)));
}
for i in 0..100 {
mapper.set_overlay(vreg(2), Some(rreg(2 * i)));
}
mapper.finish_overlay();
assert_eq!(Some(rreg(198)), mapper.get_def(vreg(2)));
mapper.merge_overlay();
assert_eq!(Some(rreg(198)), mapper.get_use(vreg(2)));
for i in 0..100 {
mapper.set_overlay(vreg(2), Some(rreg(i)));
}
for _ in 0..100 {
mapper.set_overlay(vreg(2), None);
}
mapper.finish_overlay();
assert_eq!(None, mapper.get_def(vreg(50)));
mapper.merge_overlay();
assert_eq!(None, mapper.get_use(vreg(50)));
}
}
#[derive(Debug)]
pub struct MentionRegUsageMapper {
uses: SmallVec<[(VirtualReg, RealReg); 8]>,
defs: SmallVec<[(VirtualReg, RealReg); 8]>,
}
impl MentionRegUsageMapper {
pub(crate) fn new() -> Self {
Self {
uses: SmallVec::new(),
defs: SmallVec::new(),
}
}
pub(crate) fn clear(&mut self) {
self.uses.clear();
self.defs.clear();
}
pub(crate) fn lookup_use(&self, vreg: VirtualReg) -> Option<RealReg> {
self.uses.iter().find(|&pair| pair.0 == vreg).map(|x| x.1)
}
pub(crate) fn lookup_def(&self, vreg: VirtualReg) -> Option<RealReg> {
self.defs.iter().find(|&pair| pair.0 == vreg).map(|x| x.1)
}
pub(crate) fn set_use(&mut self, vreg: VirtualReg, rreg: RealReg) {
self.uses.push((vreg, rreg));
}
pub(crate) fn set_def(&mut self, vreg: VirtualReg, rreg: RealReg) {
self.defs.push((vreg, rreg));
}
}
impl RegUsageMapper for MentionRegUsageMapper {
fn get_use(&self, vreg: VirtualReg) -> Option<RealReg> {
return self.lookup_use(vreg);
}
fn get_def(&self, vreg: VirtualReg) -> Option<RealReg> {
return self.lookup_def(vreg);
}
fn get_mod(&self, vreg: VirtualReg) -> Option<RealReg> {
let result = self.lookup_use(vreg);
debug_assert_eq!(result, self.lookup_def(vreg));
return result;
}
}