use crate::isa::reg::{Reg, RegClass}; /// A bit set to track register availability. pub(crate) struct RegSet { /// Bitset to track general purpose register availability. gpr: RegBitSet, /// Bitset to track floating-point register availability. fpr: RegBitSet, } use std::ops::{Index, IndexMut}; impl Index for RegSet { type Output = RegBitSet; fn index(&self, class: RegClass) -> &Self::Output { match class { RegClass::Int => &self.gpr, RegClass::Float => &self.fpr, c => unreachable!("Unexpected register class {:?}", c), } } } impl IndexMut for RegSet { fn index_mut(&mut self, class: RegClass) -> &mut Self::Output { match class { RegClass::Int => &mut self.gpr, RegClass::Float => &mut self.fpr, c => unreachable!("Unexpected register class {:?}", c), } } } /// Bitset for a particular register class. pub struct RegBitSet { /// The register class. class: RegClass, /// The set of allocatable allocatable: u64, /// The set of non-alloctable registers. non_allocatable: u64, /// The max number of registers. /// Invariant: /// When allocating or freeing a register the encoding (index) of the /// register must be less than the max property. max: usize, } impl RegBitSet { /// Creates an integer register class bitset. pub fn int(allocatable: u64, non_allocatable: u64, max: usize) -> Self { // Assert that one set is the complement of the other. debug_assert!(allocatable & non_allocatable == 0); Self { class: RegClass::Int, allocatable, non_allocatable, max, } } /// Creates a float register class bitset. pub fn float(allocatable: u64, non_allocatable: u64, max: usize) -> Self { // Assert that one set is the complement of the other. debug_assert!(allocatable & non_allocatable == 0); Self { class: RegClass::Float, allocatable, non_allocatable, max, } } } impl RegSet { /// Create a new register set. pub fn new(gpr: RegBitSet, fpr: RegBitSet) -> Self { debug_assert!(gpr.class == RegClass::Int); debug_assert!(fpr.class == RegClass::Float); Self { gpr, fpr } } /// Allocate the next available register of the given class, /// returning `None` if there are no more registers available. pub fn reg_for_class(&mut self, class: RegClass) -> Option { self.available(class).then(|| { let bitset = &self[class]; let index = bitset.allocatable.trailing_zeros(); self.allocate(class, index.into()); Reg::from(class, index as usize) }) } /// Request a specific register. pub fn reg(&mut self, reg: Reg) -> Option { let index = reg.hw_enc(); self.named_reg_available(reg).then(|| { self.allocate(reg.class(), index.try_into().unwrap()); reg }) } /// Marks the specified register as available, utilizing the /// register class to determine the bitset that requires updating. pub fn free(&mut self, reg: Reg) { let bitset = &self[reg.class()]; let index = reg.hw_enc(); assert!(index < bitset.max); let index = u64::try_from(index).unwrap(); if !self.is_non_allocatable(reg.class(), index) { self[reg.class()].allocatable |= 1 << index; } } /// Returns true if the specified register is allocatable. pub fn named_reg_available(&self, reg: Reg) -> bool { let bitset = &self[reg.class()]; assert!(reg.hw_enc() < bitset.max); let index = 1 << reg.hw_enc(); (!bitset.allocatable & index) == 0 || self.is_non_allocatable(reg.class(), reg.hw_enc().try_into().unwrap()) } fn available(&self, class: RegClass) -> bool { let bitset = &self[class]; bitset.allocatable != 0 } fn allocate(&mut self, class: RegClass, index: u64) { if !self.is_non_allocatable(class, index) { self[class].allocatable &= !(1 << index); } } fn is_non_allocatable(&self, class: RegClass, index: u64) -> bool { let bitset = &self[class]; let non_allocatable = bitset.non_allocatable; non_allocatable != 0 && !non_allocatable & (1 << index) == 0 } } #[cfg(test)] mod tests { use super::{Reg, RegBitSet, RegClass, RegSet}; const UNIVERSE: u64 = (1 << 16) - 1; const MAX: usize = 16; #[test] fn test_any_gpr() { let bitset = RegBitSet::int(UNIVERSE, !UNIVERSE, MAX); let zero = RegBitSet::float(0, 0, MAX); let mut set = RegSet::new(bitset, zero); for _ in 0..16 { let gpr = set.reg_for_class(RegClass::Int); assert!(gpr.is_some()) } assert!(!set.available(RegClass::Int)); assert!(set.reg_for_class(RegClass::Int).is_none()) } #[test] fn test_gpr() { let non_allocatable: u64 = 1 << 5; let all = UNIVERSE & !non_allocatable; let non_alloc = Reg::int(5); let alloc = Reg::int(2); let bitset = RegBitSet::int(all, non_allocatable, MAX); let zero = RegBitSet::float(0, 0, MAX); let mut set = RegSet::new(bitset, zero); // Requesting a non alloctable register returns the register // and doesn't allocate it. assert!(set.reg(non_alloc).is_some()); assert!(set.reg(non_alloc).is_some()); // Requesting an allocatable register twice returns none the // second time. assert!(set.reg(alloc).is_some()); assert!(set.reg(alloc).is_none()); } #[test] fn test_free_reg() { let set = RegBitSet::int(UNIVERSE, !UNIVERSE, MAX); let zero = RegBitSet::float(0, 0, MAX); let mut set = RegSet::new(set, zero); let gpr = set.reg_for_class(RegClass::Int).unwrap(); set.free(gpr); assert!(set.reg(gpr).is_some()); } }