regalloc2/fastalloc/
vregset.rs
use core::fmt;
use crate::ion::data_structures::VRegIndex;
use crate::VReg;
use alloc::vec;
use alloc::vec::Vec;
#[derive(Clone)]
struct VRegNode {
next: VRegIndex,
prev: VRegIndex,
vreg: VReg,
}
pub struct VRegSet {
items: Vec<VRegNode>,
head: VRegIndex,
}
impl VRegSet {
pub fn with_capacity(num_vregs: usize) -> Self {
Self {
items: vec![
VRegNode {
prev: VRegIndex::new(num_vregs),
next: VRegIndex::new(num_vregs),
vreg: VReg::invalid()
};
num_vregs + 1
],
head: VRegIndex::new(num_vregs),
}
}
pub fn insert(&mut self, vreg: VReg) {
debug_assert_eq!(self.items[vreg.vreg()].vreg, VReg::invalid());
let old_head_next = self.items[self.head.index()].next;
self.items[vreg.vreg()] = VRegNode {
next: old_head_next,
prev: self.head,
vreg,
};
self.items[self.head.index()].next = VRegIndex::new(vreg.vreg());
self.items[old_head_next.index()].prev = VRegIndex::new(vreg.vreg());
}
pub fn remove(&mut self, vreg_num: usize) {
let prev = self.items[vreg_num].prev;
let next = self.items[vreg_num].next;
self.items[prev.index()].next = next;
self.items[next.index()].prev = prev;
self.items[vreg_num].vreg = VReg::invalid();
}
pub fn is_empty(&self) -> bool {
self.items[self.head.index()].next == self.head
}
pub fn iter(&self) -> VRegSetIter {
VRegSetIter {
curr_item: self.items[self.head.index()].next,
head: self.head,
items: &self.items,
}
}
}
pub struct VRegSetIter<'a> {
curr_item: VRegIndex,
head: VRegIndex,
items: &'a [VRegNode],
}
impl<'a> Iterator for VRegSetIter<'a> {
type Item = VReg;
fn next(&mut self) -> Option<Self::Item> {
if self.curr_item != self.head {
let item = self.items[self.curr_item.index()].clone();
self.curr_item = item.next;
Some(item.vreg)
} else {
None
}
}
}
impl fmt::Debug for VRegSet {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{{ ")?;
for vreg in self.iter() {
write!(f, "{vreg} ")?;
}
write!(f, "}}")
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::RegClass;
use RegClass::*;
const VREG: fn(usize, RegClass) -> VReg = VReg::new;
#[test]
fn operations() {
let mut set = VRegSet::with_capacity(3090);
assert!(set.is_empty());
set.insert(VREG(10, Int));
set.insert(VREG(2000, Int));
set.insert(VREG(11, Vector));
set.insert(VREG(199, Float));
set.insert(VREG(23, Int));
let mut iter = set.iter();
assert_eq!(iter.next(), Some(VREG(23, Int)));
assert_eq!(iter.next(), Some(VREG(199, Float)));
assert_eq!(iter.next(), Some(VREG(11, Vector)));
assert_eq!(iter.next(), Some(VREG(2000, Int)));
assert_eq!(iter.next(), Some(VREG(10, Int)));
set.remove(23);
set.remove(11);
set.insert(VREG(73, Vector));
let mut iter = set.iter();
assert_eq!(iter.next(), Some(VREG(73, Vector)));
assert_eq!(iter.next(), Some(VREG(199, Float)));
assert_eq!(iter.next(), Some(VREG(2000, Int)));
assert_eq!(iter.next(), Some(VREG(10, Int)));
assert!(!set.is_empty());
}
#[test]
fn empty() {
let mut set = VRegSet::with_capacity(2000);
assert!(set.is_empty());
set.insert(VREG(100, Int));
assert!(!set.is_empty());
set.remove(100);
assert!(set.is_empty());
}
}