register_allocator/src/live_range.rs

   1 use crate::{
   2     function::ProgPoint,
   3     index::{LiveRangeIdx, SSAValIdx},
   4     loc::Loc,
   5 };
   6 use std::{cmp::Ordering, collections::BTreeSet, iter::FusedIterator, ops::Range};
   7
   8 #[derive(Copy, Clone, Debug)]
   9 /// a Range<ProgPoint> except that any overlapping ranges compare equal
  10 pub struct ProgRange {
  11     pub start: ProgPoint,
  12     pub end: ProgPoint,
  13 }
  14
  15 impl ProgRange {
  16     pub const fn is_empty(self) -> bool {
  17         self.len() == 0
  18     }
  19     pub const fn len(self) -> usize {
  20         self.end.as_usize().saturating_sub(self.start.as_usize())
  21     }
  22     pub fn overlaps(self, other: Self) -> bool {
  23         self.start < other.end && other.start < self.end
  24     }
  25     pub const fn as_usize_range(self) -> Range<usize> {
  26         self.start.as_usize()..self.end.as_usize()
  27     }
  28     pub const fn from_usize_range(value: Range<usize>) -> Self {
  29         Self {
  30             start: ProgPoint::from_usize(value.start),
  31             end: ProgPoint::from_usize(value.end),
  32         }
  33     }
  34     pub fn with_self_as_usize_range<R, F: FnOnce(&mut Range<usize>) -> R>(&mut self, f: F) -> R {
  35         let mut range = self.as_usize_range();
  36         let retval = f(&mut range);
  37         *self = Self::from_usize_range(range);
  38         retval
  39     }
  40 }
  41
  42 impl Eq for ProgRange {}
  43
  44 impl PartialEq for ProgRange {
  45     fn eq(&self, other: &Self) -> bool {
  46         self.cmp(other) == Ordering::Equal
  47     }
  48 }
  49
  50 impl PartialOrd for ProgRange {
  51     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
  52         Some(self.cmp(other))
  53     }
  54 }
  55
  56 impl Ord for ProgRange {
  57     fn cmp(&self, other: &Self) -> Ordering {
  58         if self.overlaps(*other) {
  59             Ordering::Equal
  60         } else {
  61             (self.start, self.end).cmp(&(other.start, other.end))
  62         }
  63     }
  64 }
  65
  66 impl IntoIterator for ProgRange {
  67     type Item = ProgPoint;
  68     type IntoIter = ProgRangeIter;
  69
  70     fn into_iter(self) -> Self::IntoIter {
  71         ProgRangeIter { range: self }
  72     }
  73 }
  74
  75 #[derive(Clone, Debug)]
  76 pub struct ProgRangeIter {
  77     pub range: ProgRange,
  78 }
  79
  80 impl Iterator for ProgRangeIter {
  81     type Item = ProgPoint;
  82
  83     fn next(&mut self) -> Option<Self::Item> {
  84         self.range
  85             .with_self_as_usize_range(|range| range.next())
  86             .map(ProgPoint::from_usize)
  87     }
  88
  89     fn size_hint(&self) -> (usize, Option<usize>) {
  90         (self.len(), Some(self.len()))
  91     }
  92
  93     fn count(self) -> usize {
  94         self.range.as_usize_range().count()
  95     }
  96
  97     fn last(self) -> Option<Self::Item> {
  98         self.range
  99             .as_usize_range()
 100             .last()
 101             .map(ProgPoint::from_usize)
 102     }
 103
 104     fn nth(&mut self, n: usize) -> Option<Self::Item> {
 105         self.range
 106             .with_self_as_usize_range(|range| range.nth(n))
 107             .map(ProgPoint::from_usize)
 108     }
 109
 110     fn fold<B, F>(mut self, init: B, mut f: F) -> B
 111     where
 112         F: FnMut(B, Self::Item) -> B,
 113     {
 114         self.range.with_self_as_usize_range(|range| {
 115             range.fold(init, |a, b| f(a, ProgPoint::from_usize(b)))
 116         })
 117     }
 118 }
 119
 120 impl DoubleEndedIterator for ProgRangeIter {
 121     fn next_back(&mut self) -> Option<Self::Item> {
 122         self.range
 123             .with_self_as_usize_range(|range| range.next_back())
 124             .map(ProgPoint::from_usize)
 125     }
 126
 127     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
 128         self.range
 129             .with_self_as_usize_range(|range| range.nth_back(n))
 130             .map(ProgPoint::from_usize)
 131     }
 132
 133     fn rfold<B, F>(mut self, init: B, mut f: F) -> B
 134     where
 135         F: FnMut(B, Self::Item) -> B,
 136     {
 137         self.range.with_self_as_usize_range(|range| {
 138             range.rfold(init, |a, b| f(a, ProgPoint::from_usize(b)))
 139         })
 140     }
 141 }
 142
 143 impl FusedIterator for ProgRangeIter {}
 144
 145 impl ExactSizeIterator for ProgRangeIter {
 146     fn len(&self) -> usize {
 147         self.range.as_usize_range().len()
 148     }
 149 }
 150
 151 /// ensure Hash isn't implemented for ProgRange,
 152 /// since afaict there isn't a way to implement it consistently with Ord
 153 fn _check_prog_range_is_not_hashable() {
 154     struct Hashable<const HASHABLE: bool>;
 155     trait ProgRangeHashCheck: Sized {
 156         fn _f(self) -> Hashable<false> {
 157             Hashable
 158         }
 159     }
 160     struct S<T>([T; 0]);
 161     impl<T: std::hash::Hash> S<T> {
 162         fn _f(self) -> Hashable<true> {
 163             Hashable
 164         }
 165     }
 166     impl<T> ProgRangeHashCheck for S<T> {}
 167     let _: Hashable<false> = S::<ProgRange>([])._f();
 168 }
 169
 170 #[derive(Clone, Debug)]
 171 pub struct LiveRange {
 172     pub range: ProgRange,
 173     pub ssa_val: SSAValIdx,
 174     pub allocation: Option<Loc>,
 175 }
 176
 177 pub struct LiveRangeBundle {
 178     pub live_ranges: BTreeSet<LiveRangeIdx>,
 179     pub allocation: Option<Loc>,
 180 }