From 6de0fd09da52cc5337636363170347fbc14ab2c4 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Mon, 16 Jan 2023 22:59:11 -0800 Subject: [PATCH] new ra wip --- Cargo.lock | 71 ++++ register_allocator/Cargo.toml | 4 + register_allocator/src/error.rs | 7 +- register_allocator/src/interned.rs | 102 +++-- register_allocator/src/loc.rs | 30 +- register_allocator/src/loc_set.rs | 628 ++++++++++++++++++++++++++++- register_allocator/src/macros.rs | 2 +- 7 files changed, 793 insertions(+), 51 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 987b7be..3e2f1c9 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -13,15 +13,25 @@ dependencies = [ "version_check", ] +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + [[package]] name = "bigint-presentation-code-register-allocator" version = "0.1.0" dependencies = [ + "enum-map", "eyre", "hashbrown", + "num-bigint", + "num-traits", "scoped-tls", "serde", "serde_json", + "smallvec", "thiserror", "typed-arena", ] @@ -32,6 +42,27 @@ version = "1.0.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" +[[package]] +name = "enum-map" +version = "2.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "50c25992259941eb7e57b936157961b217a4fc8597829ddef0596d6c3cd86e1a" +dependencies = [ + "enum-map-derive", + "serde", +] + +[[package]] +name = "enum-map-derive" +version = "0.11.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2a4da76b3b6116d758c7ba93f7ec6a35d2e2cf24feda76c6e38a375f4d5c59f2" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + [[package]] name = "eyre" version = "0.6.8" @@ -64,6 +95,37 @@ version = "1.0.5" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "fad582f4b9e86b6caa621cabeb0963332d92eea04729ab12892c2533951e6440" +[[package]] +name = "num-bigint" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f93ab6289c7b344a8a9f60f88d80aa20032336fe78da341afc91c8a2341fc75f" +dependencies = [ + "autocfg", + "num-integer", + "num-traits", + "serde", +] + +[[package]] +name = "num-integer" +version = "0.1.45" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "225d3389fb3509a24c93f5c29eb6bde2586b98d9f016636dff58d7c6f7569cd9" +dependencies = [ + "autocfg", + "num-traits", +] + +[[package]] +name = "num-traits" +version = "0.2.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "578ede34cf02f8924ab9447f50c28075b4d3e5b269972345e7e0372b38c6cdcd" +dependencies = [ + "autocfg", +] + [[package]] name = "once_cell" version = "1.17.0" @@ -131,6 +193,15 @@ dependencies = [ "serde", ] +[[package]] +name = "smallvec" +version = "1.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a507befe795404456341dfab10cef66ead4c041f62b8b11bbb92bffe5d0953e0" +dependencies = [ + "serde", +] + [[package]] name = "syn" version = "1.0.107" diff --git a/register_allocator/Cargo.toml b/register_allocator/Cargo.toml index b86c156..8a87392 100644 --- a/register_allocator/Cargo.toml +++ b/register_allocator/Cargo.toml @@ -13,3 +13,7 @@ thiserror = "1.0.38" typed-arena = "2.0.2" scoped-tls = "1.0.1" hashbrown = { version = "0.13.2", features = ["serde"] } +smallvec = { version = "1.10.0", features = ["serde", "union", "const_generics", "const_new"] } +num-bigint = { version = "0.4.3", features = ["serde"] } +enum-map = { version = "2.4.2", features = ["serde"] } +num-traits = "0.2.15" diff --git a/register_allocator/src/error.rs b/register_allocator/src/error.rs index 77dd128..a07fb75 100644 --- a/register_allocator/src/error.rs +++ b/register_allocator/src/error.rs @@ -1,4 +1,4 @@ -use crate::loc::BaseTy; +use crate::loc::{BaseTy, Ty}; use thiserror::Error; #[derive(Debug, Error)] @@ -15,6 +15,11 @@ pub enum Error { BaseTyMismatch, #[error("invalid sub-Loc: offset and/or reg_len out of range")] InvalidSubLocOutOfRange, + #[error("Ty mismatch: expected {expected_ty:?} got {ty:?}")] + TyMismatch { + ty: Option, + expected_ty: Option, + }, } pub type Result = std::result::Result; diff --git a/register_allocator/src/interned.rs b/register_allocator/src/interned.rs index f28d6af..f99839f 100644 --- a/register_allocator/src/interned.rs +++ b/register_allocator/src/interned.rs @@ -9,6 +9,11 @@ use std::{ rc::Rc, }; +use crate::{ + loc::Loc, + loc_set::{LocSet, LocSetMaxConflictsWith}, +}; + #[derive(Clone)] pub struct Interned { ptr: Rc, @@ -72,25 +77,28 @@ impl Ord for Interned { #[derive(Default)] struct Interners { str: Interner, + loc_set: Interner, + loc_set_max_conflicts_with_loc_set: Interner>>, + loc_set_max_conflicts_with_loc: Interner>, } -pub struct GlobalArena { +pub struct GlobalState { interners: Interners, } -scoped_tls::scoped_thread_local!(static GLOBAL_ARENA: GlobalArena); +scoped_tls::scoped_thread_local!(static GLOBAL_STATE: GlobalState); -impl GlobalArena { +impl GlobalState { pub fn scope(f: impl FnOnce() -> R) -> R { - GLOBAL_ARENA.set( - &GlobalArena { + GLOBAL_STATE.set( + &GlobalState { interners: Interners::default(), }, f, ) } - pub fn get(f: impl for<'a> FnOnce(&'a GlobalArena) -> R) -> R { - GLOBAL_ARENA.with(f) + pub fn get(f: impl for<'a> FnOnce(&'a GlobalState) -> R) -> R { + GLOBAL_STATE.with(f) } } @@ -135,26 +143,26 @@ impl Interner { } pub trait InternTarget: Intern + Hash + Eq { - fn get_interner(global_arena: &GlobalArena) -> &Interner; - fn into_interned(input: Self, global_arena: &GlobalArena) -> Interned + fn get_interner(global_state: &GlobalState) -> &Interner; + fn into_interned(input: Self, global_state: &GlobalState) -> Interned where Self: Sized, { - Self::get_interner(global_arena).intern(InternInput { + Self::get_interner(global_state).intern(InternInput { input, borrow: |v| v, into_rc: Rc::new, }) } - fn rc_into_interned(input: Rc, global_arena: &GlobalArena) -> Interned { - Self::get_interner(global_arena).intern(InternInput { + fn rc_into_interned(input: Rc, global_state: &GlobalState) -> Interned { + Self::get_interner(global_state).intern(InternInput { input, borrow: |v| &**v, into_rc: |v| v, }) } - fn rc_to_interned(input: &Rc, global_arena: &GlobalArena) -> Interned { - Self::get_interner(global_arena).intern(InternInput { + fn rc_to_interned(input: &Rc, global_state: &GlobalState) -> Interned { + Self::get_interner(global_state).intern(InternInput { input, borrow: |v| &***v, into_rc: |v| v.clone(), @@ -163,8 +171,8 @@ pub trait InternTarget: Intern + Hash + Eq { } impl InternTarget for str { - fn get_interner(global_arena: &GlobalArena) -> &Interner { - &global_arena.interners.str + fn get_interner(global_state: &GlobalState) -> &Interner { + &global_state.interners.str } } @@ -175,8 +183,8 @@ impl Intern for str { v.into() } - fn to_interned(&self, global_arena: &GlobalArena) -> Interned { - Self::get_interner(global_arena).intern(InternInput { + fn to_interned(&self, global_state: &GlobalState) -> Interned { + Self::get_interner(global_state).intern(InternInput { input: self, borrow: |v| &**v, into_rc: Self::to_rc_target, @@ -191,15 +199,15 @@ impl Intern for &'_ str { Rc::from(*v) } - fn to_interned(&self, global_arena: &GlobalArena) -> Interned { - Self::Target::to_interned(self, global_arena) + fn to_interned(&self, global_state: &GlobalState) -> Interned { + Self::Target::to_interned(self, global_state) } - fn into_interned(self, global_arena: &GlobalArena) -> Interned + fn into_interned(self, global_state: &GlobalState) -> Interned where Self: Sized, { - Self::Target::to_interned(self, global_arena) + Self::Target::to_interned(self, global_state) } } @@ -210,15 +218,15 @@ impl Intern for &'_ mut str { Rc::from(&**v) } - fn to_interned(&self, global_arena: &GlobalArena) -> Interned { - Self::Target::to_interned(self, global_arena) + fn to_interned(&self, global_state: &GlobalState) -> Interned { + Self::Target::to_interned(self, global_state) } - fn into_interned(self, global_arena: &GlobalArena) -> Interned + fn into_interned(self, global_state: &GlobalState) -> Interned where Self: Sized, { - Self::Target::to_interned(self, global_arena) + Self::Target::to_interned(self, global_state) } } @@ -229,8 +237,8 @@ impl Intern for String { Rc::from(&**v) } - fn to_interned(&self, global_arena: &GlobalArena) -> Interned { - Self::Target::to_interned(self, global_arena) + fn to_interned(&self, global_state: &GlobalState) -> Interned { + Self::Target::to_interned(self, global_state) } fn into_rc_target(v: Self) -> Rc @@ -240,11 +248,11 @@ impl Intern for String { Rc::from(v) } - fn into_interned(self, global_arena: &GlobalArena) -> Interned + fn into_interned(self, global_state: &GlobalState) -> Interned where Self: Sized, { - Self::Target::to_interned(&self, global_arena) + Self::Target::to_interned(&self, global_state) } } @@ -257,17 +265,17 @@ pub trait Intern { Self::to_rc_target(&v) } fn to_rc_target(v: &Self) -> Rc; - fn into_interned(self, global_arena: &GlobalArena) -> Interned + fn into_interned(self, global_state: &GlobalState) -> Interned where Self: Sized, { <::Target as InternTarget>::rc_into_interned( Self::into_rc_target(self), - global_arena, + global_state, ) } - fn to_interned(&self, global_arena: &GlobalArena) -> Interned { - Self::Target::rc_into_interned(Self::to_rc_target(self), global_arena) + fn to_interned(&self, global_state: &GlobalState) -> Interned { + Self::Target::rc_into_interned(Self::to_rc_target(self), global_state) } } @@ -300,18 +308,36 @@ impl Intern for T { v.into() } - fn into_interned(self, global_arena: &GlobalArena) -> Interned + fn into_interned(self, global_state: &GlobalState) -> Interned where Self: Sized, { - InternTarget::into_interned(self, global_arena) + InternTarget::into_interned(self, global_state) } - fn to_interned(&self, global_arena: &GlobalArena) -> Interned { - InternTarget::get_interner(global_arena).intern(InternInput { + fn to_interned(&self, global_state: &GlobalState) -> Interned { + InternTarget::get_interner(global_state).intern(InternInput { input: self, borrow: |v| &**v, into_rc: |v| v.clone().into(), }) } } + +impl InternTarget for LocSet { + fn get_interner(global_state: &GlobalState) -> &Interner { + &global_state.interners.loc_set + } +} + +impl InternTarget for LocSetMaxConflictsWith> { + fn get_interner(global_state: &GlobalState) -> &Interner { + &global_state.interners.loc_set_max_conflicts_with_loc_set + } +} + +impl InternTarget for LocSetMaxConflictsWith { + fn get_interner(global_state: &GlobalState) -> &Interner { + &global_state.interners.loc_set_max_conflicts_with_loc + } +} diff --git a/register_allocator/src/loc.rs b/register_allocator/src/loc.rs index 1335533..9af021e 100644 --- a/register_allocator/src/loc.rs +++ b/register_allocator/src/loc.rs @@ -1,8 +1,11 @@ use crate::error::{Error, Result}; +use enum_map::Enum; use serde::{Deserialize, Serialize}; use std::num::NonZeroU32; -#[derive(Serialize, Deserialize, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)] +#[derive( + Serialize, Deserialize, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Enum, +)] #[repr(u8)] pub enum LocKind { Gpr, @@ -32,7 +35,9 @@ impl LocKind { } } -#[derive(Serialize, Deserialize, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)] +#[derive( + Serialize, Deserialize, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Enum, +)] #[repr(u8)] pub enum BaseTy { Bits64, @@ -106,6 +111,18 @@ impl Loc { pub const fn ty(self) -> Ty { const_unwrap_res!(self.0.ty(), "Loc can only be constructed with valid fields") } + pub const fn max_start(kind: LocKind, reg_len: NonZeroU32) -> Result { + // validate Ty + const_try!(Ty::new(TyFields { + base_ty: kind.base_ty(), + reg_len + })); + let loc_count: u32 = kind.loc_count().get(); + let Some(max_start) = loc_count.checked_sub(reg_len.get()) else { + return Err(Error::InvalidRegLen) + }; + Ok(max_start) + } pub const fn new(fields: LocFields) -> Result { let LocFields { kind, @@ -113,14 +130,7 @@ impl Loc { reg_len, } = fields; - // validate Ty - const_try!(fields.ty()); - - let loc_count: u32 = kind.loc_count().get(); - let Some(max_start) = loc_count.checked_sub(reg_len.get()) else { - return Err(Error::InvalidRegLen) - }; - if start > max_start { + if start > const_try!(Self::max_start(kind, reg_len)) { Err(Error::StartNotInValidRange) } else { Ok(Self(fields)) diff --git a/register_allocator/src/loc_set.rs b/register_allocator/src/loc_set.rs index 5e51d63..b10358b 100644 --- a/register_allocator/src/loc_set.rs +++ b/register_allocator/src/loc_set.rs @@ -1,3 +1,629 @@ +use crate::{ + error::{Error, Result}, + interned::{GlobalState, Intern, InternTarget, Interned}, + loc::{BaseTy, Loc, LocFields, LocKind, Ty, TyFields}, +}; +use enum_map::{enum_map, EnumMap}; +use num_bigint::BigUint; +use num_traits::Zero; +use serde::{Deserialize, Serialize}; +use std::{ + borrow::{Borrow, Cow}, + cell::Cell, + fmt, + hash::Hash, + iter::{FusedIterator, Peekable}, + num::NonZeroU32, + ops::{ + BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, ControlFlow, Range, Sub, + SubAssign, + }, +}; + +#[derive(Deserialize)] +struct LocSetSerialized { + starts: EnumMap, + ty: Option, +} + +impl TryFrom for LocSet { + type Error = Error; + + fn try_from(value: LocSetSerialized) -> Result { + Self::from_parts(value.starts, value.ty) + } +} + +#[derive(Clone, Default, PartialEq, Eq, Hash, Serialize, Deserialize)] +#[serde(try_from = "LocSetSerialized")] pub struct LocSet { - // FIXME: finish + starts: EnumMap, + ty: Option, +} + +/// computes same value as `a & !b`, but more efficiently +fn and_not, B>(a: A, b: B) -> BigUint +where + BigUint: for<'a> BitXor, + B: for<'a> BitAnd<&'a BigUint, Output = BigUint>, +{ + // use logical equivalent that avoids needing to use BigInt + (b & a.borrow()) ^ a +} + +impl LocSet { + pub fn starts(&self) -> &EnumMap { + &self.starts + } + pub fn stops(&self) -> EnumMap { + let Some(ty) = self.ty else { + return EnumMap::default(); + }; + enum_map! {kind => &self.starts[kind] << ty.reg_len.get()} + } + pub fn ty(&self) -> Option { + self.ty + } + pub fn kinds(&self) -> impl Iterator + '_ { + self.starts + .iter() + .filter_map(|(kind, starts)| if starts.is_zero() { None } else { Some(kind) }) + } + pub fn reg_len(&self) -> Option { + self.ty.map(|v| v.reg_len) + } + pub fn base_ty(&self) -> Option { + self.ty.map(|v| v.base_ty) + } + pub fn new() -> Self { + Self::default() + } + pub fn from_parts(starts: EnumMap, ty: Option) -> Result { + let mut empty = true; + for (kind, starts) in &starts { + if !starts.is_zero() { + empty = false; + let expected_ty = Ty::new(TyFields { + base_ty: kind.base_ty(), + reg_len: ty.map(|v| v.reg_len).unwrap_or(nzu32_lit!(1)), + }) + .unwrap_or_else(|_| { + Ty::new(TyFields { + base_ty: kind.base_ty(), + reg_len: nzu32_lit!(1), + }) + .unwrap() + }); + if ty != Some(expected_ty) { + return Err(Error::TyMismatch { + ty, + expected_ty: Some(expected_ty), + }); + } + // bits() is one past max bit set, so use >= rather than > + if starts.bits() >= Loc::max_start(kind, expected_ty.reg_len)? as u64 { + return Err(Error::StartNotInValidRange); + } + } + } + if empty && ty.is_some() { + Err(Error::TyMismatch { + ty, + expected_ty: None, + }) + } else { + Ok(Self { starts, ty }) + } + } + pub fn clear(&mut self) { + for v in self.starts.values_mut() { + v.assign_from_slice(&[]); + } + } + pub fn contains(&self, value: Loc) -> bool { + Some(value.ty()) == self.ty && self.starts[value.kind].bit(value.start as _) + } + pub fn try_insert(&mut self, value: Loc) -> Result { + if self.is_empty() { + self.ty = Some(value.ty()); + self.starts[value.kind].set_bit(value.start as u64, true); + return Ok(true); + }; + let ty = Some(value.ty()); + if ty != self.ty { + return Err(Error::TyMismatch { + ty, + expected_ty: self.ty, + }); + } + let retval = !self.starts[value.kind].bit(value.start as u64); + self.starts[value.kind].set_bit(value.start as u64, true); + Ok(retval) + } + pub fn insert(&mut self, value: Loc) -> bool { + self.try_insert(value).unwrap() + } + pub fn remove(&mut self, value: Loc) -> bool { + if self.contains(value) { + self.starts[value.kind].set_bit(value.start as u64, false); + if self.starts.values().all(BigUint::is_zero) { + self.ty = None; + } + true + } else { + false + } + } + pub fn is_empty(&self) -> bool { + self.ty.is_none() + } + pub fn is_disjoint(&self, other: &LocSet) -> bool { + if self.ty != other.ty || self.is_empty() { + return true; + } + for (k, lhs) in self.starts.iter() { + let rhs = &other.starts[k]; + if !(lhs & rhs).is_zero() { + return false; + } + } + true + } + pub fn is_subset(&self, containing_set: &LocSet) -> bool { + if self.is_empty() { + return true; + } + if self.ty != containing_set.ty { + return false; + } + for (k, v) in self.starts.iter() { + let containing_set = &containing_set.starts[k]; + if !and_not(v, containing_set).is_zero() { + return false; + } + } + true + } + pub fn is_superset(&self, contained_set: &LocSet) -> bool { + contained_set.is_subset(self) + } + pub fn iter(&self) -> Iter<'_> { + if let Some(ty) = self.ty { + let mut starts = self.starts.iter().peekable(); + Iter { + internals: Some(IterInternals { + ty, + start_range: get_start_range(starts.peek()), + starts, + }), + } + } else { + Iter { internals: None } + } + } + pub fn len(&self) -> usize { + let retval: u64 = self.starts.values().map(BigUint::count_ones).sum(); + retval as usize + } +} + +#[derive(Clone, Debug)] +struct IterInternals +where + I: Iterator, + T: Clone + Borrow, +{ + ty: Ty, + starts: Peekable, + start_range: Range, +} + +impl IterInternals +where + I: Iterator, + T: Clone + Borrow, +{ + fn next(&mut self) -> Option { + let IterInternals { + ty, + ref mut starts, + ref mut start_range, + } = *self; + loop { + let (kind, ref v) = *starts.peek()?; + let Some(start) = start_range.next() else { + starts.next(); + *start_range = get_start_range(starts.peek()); + continue; + }; + if v.borrow().bit(start as u64) { + return Some( + Loc::new(LocFields { + kind, + start, + reg_len: ty.reg_len, + }) + .expect("known to be valid"), + ); + } + } + } +} + +fn get_start_range(v: Option<&(LocKind, impl Borrow)>) -> Range { + 0..v.map(|(_, v)| v.borrow().bits() as u32).unwrap_or(0) +} + +#[derive(Clone, Debug)] +pub struct Iter<'a> { + internals: Option, &'a BigUint>>, +} + +impl Iterator for Iter<'_> { + type Item = Loc; + + fn next(&mut self) -> Option { + self.internals.as_mut()?.next() + } +} + +impl FusedIterator for Iter<'_> {} + +pub struct IntoIter { + internals: Option, BigUint>>, +} + +impl Iterator for IntoIter { + type Item = Loc; + + fn next(&mut self) -> Option { + self.internals.as_mut()?.next() + } +} + +impl FusedIterator for IntoIter {} + +impl IntoIterator for LocSet { + type Item = Loc; + type IntoIter = IntoIter; + + fn into_iter(self) -> Self::IntoIter { + if let Some(ty) = self.ty { + let mut starts = self.starts.into_iter().peekable(); + IntoIter { + internals: Some(IterInternals { + ty, + start_range: get_start_range(starts.peek()), + starts, + }), + } + } else { + IntoIter { internals: None } + } + } +} + +impl<'a> IntoIterator for &'a LocSet { + type Item = Loc; + type IntoIter = Iter<'a>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl Extend for LocSet { + fn extend>(&mut self, iter: T) { + iter.into_iter().for_each(|item| { + self.insert(item); + }); + } +} + +impl> Extend for Result { + fn extend>(&mut self, iter: T) { + iter.into_iter().try_for_each(|item| { + let Ok(loc_set) = self else { + return ControlFlow::Break(()); + }; + match loc_set.try_insert(item) { + Ok(_) => ControlFlow::Continue(()), + Err(e) => { + *self = Err(e.into()); + ControlFlow::Break(()) + } + } + }); + } +} + +impl FromIterator for LocSet { + fn from_iter>(iter: T) -> Self { + let mut retval = LocSet::new(); + retval.extend(iter); + retval + } +} + +impl> FromIterator for Result { + fn from_iter>(iter: T) -> Self { + let mut retval = Ok(LocSet::new()); + retval.extend(iter); + retval + } +} + +struct HexBigUint<'a>(&'a BigUint); + +impl fmt::Debug for HexBigUint<'_> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "{:#x}", self.0) + } +} + +struct LocSetStarts<'a>(&'a EnumMap); + +impl fmt::Debug for LocSetStarts<'_> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_map() + .entries(self.0.iter().map(|(k, v)| (k, HexBigUint(v)))) + .finish() + } +} + +impl fmt::Debug for LocSet { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("LocSet") + .field("starts", &self.starts) + .finish() + } +} + +macro_rules! impl_bin_op { + ( + $bin_op:ident::$bin_op_fn:ident(), + $bin_assign_op:ident::$bin_assign_op_fn:ident(), + $starts_op:expr, + $handle_unequal_types:expr, + $update_unequal_types:expr, + ) => { + impl $bin_op<&'_ LocSet> for &'_ LocSet { + type Output = LocSet; + + fn $bin_op_fn(self, rhs: &'_ LocSet) -> Self::Output { + if self.ty != rhs.ty { + $handle_unequal_types(self, Cow::::Borrowed(rhs)) + } else { + LocSet { + starts: enum_map! {kind => $starts_op(&self.starts[kind], &rhs.starts[kind])}, + ty: self.ty, + } + } + } + } + + impl $bin_assign_op<&'_ LocSet> for LocSet { + fn $bin_assign_op_fn(&mut self, rhs: &'_ LocSet) { + if self.ty != rhs.ty { + $update_unequal_types(self, rhs); + } else { + for (kind, starts) in &mut self.starts { + let v: BigUint = std::mem::take(starts); + *starts = $starts_op(v, &rhs.starts[kind]); + } + } + } + } + + impl $bin_assign_op for LocSet { + fn $bin_assign_op_fn(&mut self, rhs: LocSet) { + self.$bin_assign_op_fn(&rhs); + } + } + + impl $bin_op<&'_ LocSet> for LocSet { + type Output = LocSet; + + fn $bin_op_fn(mut self, rhs: &'_ LocSet) -> Self::Output { + self.$bin_assign_op_fn(rhs); + self + } + } + + impl $bin_op for LocSet { + type Output = LocSet; + + fn $bin_op_fn(mut self, rhs: LocSet) -> Self::Output { + self.$bin_assign_op_fn(rhs); + self + } + } + + impl $bin_op for &'_ LocSet { + type Output = LocSet; + + fn $bin_op_fn(self, mut rhs: LocSet) -> Self::Output { + if self.ty != rhs.ty { + $handle_unequal_types(self, Cow::::Owned(rhs)) + } else { + for (kind, starts) in &mut rhs.starts { + *starts = $starts_op(&self.starts[kind], std::mem::take(starts)); + } + rhs + } + } + } + }; +} + +impl_bin_op! { + BitAnd::bitand(), + BitAndAssign::bitand_assign(), + BitAnd::bitand, + |_, _| LocSet::new(), + |lhs, _| LocSet::clear(lhs), +} + +impl_bin_op! { + BitOr::bitor(), + BitOrAssign::bitor_assign(), + BitOr::bitor, + |lhs: &LocSet, rhs: Cow| panic!("{}", Error::TyMismatch { ty: rhs.ty, expected_ty: lhs.ty }), + |lhs: &mut LocSet, rhs: &LocSet| panic!("{}", Error::TyMismatch { ty: rhs.ty, expected_ty: lhs.ty }), +} + +impl_bin_op! { + BitXor::bitxor(), + BitXorAssign::bitxor_assign(), + BitXor::bitxor, + |lhs: &LocSet, rhs: Cow| panic!("{}", Error::TyMismatch { ty: rhs.ty, expected_ty: lhs.ty }), + |lhs: &mut LocSet, rhs: &LocSet| panic!("{}", Error::TyMismatch { ty: rhs.ty, expected_ty: lhs.ty }), +} + +impl_bin_op! { + Sub::sub(), + SubAssign::sub_assign(), + and_not, + |lhs: &LocSet, _| lhs.clone(), + |_, _| {}, +} + +/// the largest number of Locs in `lhs` that a single Loc +/// from `rhs` can conflict with +#[derive(Clone)] +pub struct LocSetMaxConflictsWith { + lhs: Interned, + rhs: Rhs, + // result is not included in equality or hash + result: Cell>, +} + +impl Hash for LocSetMaxConflictsWith { + fn hash(&self, state: &mut H) { + self.lhs.hash(state); + self.rhs.hash(state); + } +} + +impl Eq for LocSetMaxConflictsWith {} + +impl PartialEq for LocSetMaxConflictsWith { + fn eq(&self, other: &Self) -> bool { + self.lhs == other.lhs && self.rhs == other.rhs + } +} + +pub trait LocSetMaxConflictsWithTrait: Clone { + fn intern( + v: LocSetMaxConflictsWith, + global_state: &GlobalState, + ) -> Interned>; + fn compute_result(lhs: &Interned, rhs: &Self, global_state: &GlobalState) -> u32; +} + +impl LocSetMaxConflictsWithTrait for Loc { + fn compute_result(lhs: &Interned, rhs: &Self, _global_state: &GlobalState) -> u32 { + // now we do the equivalent of: + // return lhs.iter().map(|loc| rhs.conflicts(loc) as u32).sum().unwrap_or(0) + let Some(reg_len) = lhs.reg_len() else { + return 0; + }; + let starts = &lhs.starts[rhs.kind]; + if starts.is_zero() { + return 0; + } + // now we do the equivalent of: + // return sum(rhs.start < start + reg_len + // and start < rhs.start + rhs.reg_len + // for start in starts) + let stops = starts << reg_len.get(); + + // find all the bit indexes `i` where `i < rhs.start + 1` + let lt_rhs_start_plus_1 = (BigUint::from(1u32) << (rhs.start + 1)) - 1u32; + + // find all the bit indexes `i` where + // `i < rhs.start + rhs.reg_len + reg_len` + let lt_rhs_start_plus_rhs_reg_len_plus_reg_len = + (BigUint::from(1u32) << (rhs.start + rhs.reg_len.get() + reg_len.get())) - 1u32; + let mut included = and_not(&stops, &stops & lt_rhs_start_plus_1); + included &= lt_rhs_start_plus_rhs_reg_len_plus_reg_len; + included.count_ones() as u32 + } + + fn intern( + v: LocSetMaxConflictsWith, + global_state: &GlobalState, + ) -> Interned> { + v.into_interned(global_state) + } +} + +impl LocSetMaxConflictsWithTrait for Interned { + fn compute_result(lhs: &Interned, rhs: &Self, global_state: &GlobalState) -> u32 { + rhs.iter() + .map(|loc| lhs.clone().max_conflicts_with(loc, global_state)) + .max() + .unwrap_or(0) + } + + fn intern( + v: LocSetMaxConflictsWith, + global_state: &GlobalState, + ) -> Interned> { + v.into_interned(global_state) + } +} + +impl LocSetMaxConflictsWith { + pub fn lhs(&self) -> &Interned { + &self.lhs + } + pub fn rhs(&self) -> &Rhs { + &self.rhs + } + pub fn result(&self, global_state: &GlobalState) -> u32 { + match self.result.get() { + Some(v) => v, + None => { + let retval = Rhs::compute_result(&self.lhs, &self.rhs, global_state); + self.result.set(Some(retval)); + retval + } + } + } +} + +impl Interned { + pub fn max_conflicts_with(self, rhs: Rhs, global_state: &GlobalState) -> u32 + where + Rhs: LocSetMaxConflictsWithTrait, + LocSetMaxConflictsWith: InternTarget, + { + LocSetMaxConflictsWithTrait::intern( + LocSetMaxConflictsWith { + lhs: self, + rhs, + result: Cell::default(), + }, + global_state, + ) + .result(global_state) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_and_not() { + for a in 0..0x10u32 { + for b in 0..0x10 { + assert_eq!( + and_not(&BigUint::from(a), BigUint::from(b)), + (a & !b).into() + ); + } + } + } } diff --git a/register_allocator/src/macros.rs b/register_allocator/src/macros.rs index 9aabe39..b7a2510 100644 --- a/register_allocator/src/macros.rs +++ b/register_allocator/src/macros.rs @@ -96,7 +96,7 @@ macro_rules! const_try { macro_rules! nzu32_lit { ($v:literal) => {{ - const V: NonZeroU32 = match NonZeroU32::new($v) { + const V: ::std::num::NonZeroU32 = match ::std::num::NonZeroU32::new($v) { Some(v) => v, None => panic!("literal must not be zero"), }; -- 2.30.2