From 3fbef1eba657113db8158a4917334242776271da Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Thu, 16 Feb 2023 18:19:49 -0800 Subject: [PATCH] ProgRange shouldn't be Eq Eq requires equality to be transitive, but ProgRange fails to be since 1..2 == 1..10 and 1..10 == 9..10 due to overlap but 1..2 != 9..10 --- register_allocator/src/live_range.rs | 175 +++++++++++++++++++++------ register_allocator/src/state.rs | 11 +- 2 files changed, 142 insertions(+), 44 deletions(-) diff --git a/register_allocator/src/live_range.rs b/register_allocator/src/live_range.rs index 9cf9a71..e045276 100644 --- a/register_allocator/src/live_range.rs +++ b/register_allocator/src/live_range.rs @@ -1,26 +1,110 @@ use crate::{ function::ProgPoint, index::{LiveRangeIdx, SSAValIdx}, + live_range::sealed::Sealed, loc::Loc, }; -use std::{cmp::Ordering, collections::BTreeSet, iter::FusedIterator, ops::Range}; +use std::{ + cmp::Ordering, + collections::BTreeSet, + fmt, + hash::{Hash, Hasher}, + iter::FusedIterator, + marker::PhantomData, + ops::Range, +}; + +mod sealed { + pub trait Sealed {} +} + +pub trait ProgRangeCmpKind: Sealed + Copy { + const OVERLAPPING_IS_EQ: bool; +} + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)] +pub struct OverlappingIsEq; + +impl Sealed for OverlappingIsEq {} + +impl ProgRangeCmpKind for OverlappingIsEq { + const OVERLAPPING_IS_EQ: bool = true; +} + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)] +pub struct Lexicographic; + +impl Sealed for Lexicographic {} -#[derive(Copy, Clone, Debug)] -/// a Range except that any overlapping ranges compare equal -pub struct ProgRange { +impl ProgRangeCmpKind for Lexicographic { + const OVERLAPPING_IS_EQ: bool = false; +} + +#[derive(Copy, Clone)] +/// a Range except that if `CmpKind` is `OverlappingIsEq` and two +/// ranges overlap, then they compare equal, otherwise they are +/// lexicographically ordered. +/// +/// only `ProgRange` can impl `Eq`, `ProgRange` +/// can't impl `Eq` because `Eq` requires equality to be transitive, but +/// `ProgRange` fails to be: +/// ``` +/// # use bigint_presentation_code_register_allocator::live_range::{ProgRange, OverlappingIsEq}; +/// let a = ProgRange::::from_usize_range(1..2); +/// let b = ProgRange::::from_usize_range(1..10); +/// let c = ProgRange::::from_usize_range(9..10); +/// // Eq requires a == b && b == c implies a == c +/// assert_eq!(a, b); +/// assert_eq!(b, c); +/// assert_ne!(a, c); // equality not transitive here +/// ``` +pub struct ProgRange { pub start: ProgPoint, pub end: ProgPoint, + _phantom: PhantomData, +} + +impl fmt::Debug for ProgRange { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("ProgRange") + .field("start", &self.start) + .field("end", &self.end) + .finish() + } } -impl ProgRange { +impl ProgRange { + pub const fn new(range: Range) -> Self { + let Range { start, end } = range; + Self { + start, + end, + _phantom: PhantomData, + } + } + pub const fn as_range(self) -> Range { + self.start..self.end + } + pub const fn into(self) -> ProgRange { + let Self { + start, + end, + _phantom: _, + } = self; + ProgRange { + start, + end, + _phantom: PhantomData, + } + } pub const fn is_empty(self) -> bool { self.len() == 0 } pub const fn len(self) -> usize { self.end.as_usize().saturating_sub(self.start.as_usize()) } - pub fn overlaps(self, other: Self) -> bool { - self.start < other.end && other.start < self.end + pub const fn overlaps(self, other: Self) -> bool { + self.start.as_usize() < other.end.as_usize() && other.start.as_usize() < self.end.as_usize() } pub const fn as_usize_range(self) -> Range { self.start.as_usize()..self.end.as_usize() @@ -29,6 +113,7 @@ impl ProgRange { Self { start: ProgPoint::from_usize(value.start), end: ProgPoint::from_usize(value.end), + _phantom: PhantomData, } } pub fn with_self_as_usize_range) -> R>(&mut self, f: F) -> R { @@ -37,44 +122,73 @@ impl ProgRange { *self = Self::from_usize_range(range); retval } + pub const fn eq(&self, other: &Self) -> bool { + if CmpKind::OVERLAPPING_IS_EQ && self.overlaps(*other) { + true + } else { + self.start.as_usize() == other.start.as_usize() + && self.end.as_usize() == other.end.as_usize() + } + } + pub const fn cmp(&self, other: &Self) -> Ordering { + if CmpKind::OVERLAPPING_IS_EQ && self.overlaps(*other) { + Ordering::Equal + } else if self.start.as_usize() < other.start.as_usize() { + Ordering::Less + } else if self.start.as_usize() > other.start.as_usize() { + Ordering::Greater + } else if self.end.as_usize() < other.end.as_usize() { + Ordering::Less + } else if self.end.as_usize() > other.end.as_usize() { + Ordering::Greater + } else { + Ordering::Equal + } + } } -impl Eq for ProgRange {} +impl Eq for ProgRange {} -impl PartialEq for ProgRange { +impl Hash for ProgRange { + fn hash(&self, state: &mut H) { + self.start.hash(state); + self.end.hash(state); + } +} + +impl PartialEq for ProgRange { fn eq(&self, other: &Self) -> bool { - self.cmp(other) == Ordering::Equal + self.eq(other) } } -impl PartialOrd for ProgRange { +impl PartialOrd for ProgRange { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } -impl Ord for ProgRange { +impl Ord for ProgRange +where + Self: Eq, +{ fn cmp(&self, other: &Self) -> Ordering { - if self.overlaps(*other) { - Ordering::Equal - } else { - (self.start, self.end).cmp(&(other.start, other.end)) - } + self.cmp(other) } } -impl IntoIterator for ProgRange { +impl IntoIterator for ProgRange { type Item = ProgPoint; type IntoIter = ProgRangeIter; fn into_iter(self) -> Self::IntoIter { - ProgRangeIter { range: self } + ProgRangeIter { range: self.into() } } } #[derive(Clone, Debug)] pub struct ProgRangeIter { - pub range: ProgRange, + pub range: ProgRange, } impl Iterator for ProgRangeIter { @@ -148,28 +262,9 @@ impl ExactSizeIterator for ProgRangeIter { } } -/// ensure Hash isn't implemented for ProgRange, -/// since afaict there isn't a way to implement it consistently with Ord -fn _check_prog_range_is_not_hashable() { - struct Hashable; - trait ProgRangeHashCheck: Sized { - fn _f(self) -> Hashable { - Hashable - } - } - struct S([T; 0]); - impl S { - fn _f(self) -> Hashable { - Hashable - } - } - impl ProgRangeHashCheck for S {} - let _: Hashable = S::([])._f(); -} - #[derive(Clone, Debug)] pub struct LiveRange { - pub range: ProgRange, + pub range: ProgRange, pub ssa_val: SSAValIdx, pub allocation: Option, } diff --git a/register_allocator/src/state.rs b/register_allocator/src/state.rs index 684f262..acbdc64 100644 --- a/register_allocator/src/state.rs +++ b/register_allocator/src/state.rs @@ -2,7 +2,7 @@ use crate::{ function::Function, index::LiveRangeIdx, interned::GlobalState, - live_range::{LiveRange, ProgRange}, + live_range::{Lexicographic, LiveRange, ProgRange}, loc::{Loc, SubLoc}, }; use hashbrown::HashMap; @@ -13,7 +13,7 @@ pub struct AllocatorState<'a> { global_state: &'a Rc, func: &'a Function, live_ranges: Vec, - allocations: HashMap>, + allocations: HashMap, LiveRangeIdx>>, } impl<'a> AllocatorState<'a> { @@ -34,8 +34,11 @@ impl<'a> AllocatorState<'a> { pub fn live_ranges(&self) -> &[LiveRange] { &self.live_ranges } - pub fn allocations(&self, sub_loc: SubLoc) -> &BTreeMap { - const EMPTY: &'static BTreeMap = &BTreeMap::new(); + pub fn allocations( + &self, + sub_loc: SubLoc, + ) -> &BTreeMap, LiveRangeIdx> { + const EMPTY: &'static BTreeMap, LiveRangeIdx> = &BTreeMap::new(); self.allocations.get(&sub_loc).unwrap_or(EMPTY) } pub fn remove_allocations_for(&mut self, live_range_idx: LiveRangeIdx) -> Option { -- 2.30.2