register_allocator/src/index.rs

   1 use serde::{de::DeserializeOwned, Deserialize, Serialize};
   2 use std::{fmt, hash::Hash, iter::FusedIterator, ops::Range};
   3
   4 pub trait DisplayOptionIdx {
   5     type Type: fmt::Display;
   6     fn display_option_idx(self) -> Self::Type;
   7 }
   8
   9 pub trait IndexTy: Copy + fmt::Debug + Ord + Hash + Serialize + DeserializeOwned {
  10     fn new(value: usize) -> Self;
  11     fn get(self) -> usize;
  12     fn next(self) -> Self {
  13         Self::new(self.get() + 1)
  14     }
  15     fn prev(self) -> Self {
  16         Self::new(self.get() - 1)
  17     }
  18 }
  19
  20 #[derive(Debug, Clone)]
  21 pub struct RangeIter<T: IndexTy>(pub Range<T>);
  22
  23 impl<T: IndexTy> RangeIter<T> {
  24     pub fn as_usize_range(&self) -> Range<usize> {
  25         self.0.start.get()..self.0.end.get()
  26     }
  27     pub fn from_usize_range(range: Range<usize>) -> Self {
  28         Self(T::new(range.start)..T::new(range.end))
  29     }
  30     pub fn with_self_as_usize_range<R, F: FnOnce(&mut Range<usize>) -> R>(&mut self, f: F) -> R {
  31         let mut range = self.as_usize_range();
  32         let retval = f(&mut range);
  33         *self = Self::from_usize_range(range);
  34         retval
  35     }
  36 }
  37
  38 impl<T: IndexTy> Iterator for RangeIter<T> {
  39     type Item = T;
  40
  41     fn next(&mut self) -> Option<Self::Item> {
  42         self.with_self_as_usize_range(|r| r.next().map(T::new))
  43     }
  44
  45     fn size_hint(&self) -> (usize, Option<usize>) {
  46         self.as_usize_range().size_hint()
  47     }
  48
  49     fn nth(&mut self, n: usize) -> Option<Self::Item> {
  50         self.with_self_as_usize_range(|r| r.nth(n).map(T::new))
  51     }
  52
  53     fn fold<B, F>(self, init: B, mut f: F) -> B
  54     where
  55         F: FnMut(B, Self::Item) -> B,
  56     {
  57         self.as_usize_range()
  58             .fold(init, move |a, v| f(a, T::new(v)))
  59     }
  60 }
  61
  62 impl<T: IndexTy> FusedIterator for RangeIter<T> {}
  63
  64 impl<T: IndexTy> ExactSizeIterator for RangeIter<T> {
  65     fn len(&self) -> usize {
  66         self.as_usize_range().len()
  67     }
  68 }
  69
  70 impl<T: IndexTy> DoubleEndedIterator for RangeIter<T> {
  71     fn next_back(&mut self) -> Option<Self::Item> {
  72         self.with_self_as_usize_range(|r| r.next_back().map(T::new))
  73     }
  74
  75     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
  76         self.with_self_as_usize_range(|r| r.nth_back(n).map(T::new))
  77     }
  78
  79     fn rfold<B, F>(self, init: B, mut f: F) -> B
  80     where
  81         F: FnMut(B, Self::Item) -> B,
  82     {
  83         self.as_usize_range()
  84             .rfold(init, move |a, v| f(a, T::new(v)))
  85     }
  86 }
  87
  88 macro_rules! define_index {
  89     ($name:ident) => {
  90         #[derive(
  91             Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize,
  92         )]
  93         #[serde(transparent)]
  94         pub struct $name {
  95             value: usize,
  96         }
  97
  98         impl IndexTy for $name {
  99             fn new(value: usize) -> Self {
 100                 Self { value }
 101             }
 102             fn get(self) -> usize {
 103                 self.value
 104             }
 105         }
 106
 107         impl $name {
 108             pub const fn new(value: usize) -> Self {
 109                 Self { value }
 110             }
 111             pub const fn get(self) -> usize {
 112                 self.value
 113             }
 114             pub const fn next(self) -> Self {
 115                 Self {
 116                     value: self.value + 1,
 117                 }
 118             }
 119             pub const fn prev(self) -> Self {
 120                 Self {
 121                     value: self.value - 1,
 122                 }
 123             }
 124         }
 125
 126         const _: () = {
 127             #[derive(Copy, Clone)]
 128             pub struct DisplayOptionIdxImpl(Option<$name>);
 129
 130             impl fmt::Debug for DisplayOptionIdxImpl {
 131                 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 132                     fmt::Display::fmt(self, f)
 133                 }
 134             }
 135
 136             impl fmt::Display for DisplayOptionIdxImpl {
 137                 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 138                     match self.0 {
 139                         Some(v) => v.fmt(f),
 140                         None => write!(f, "none"),
 141                     }
 142                 }
 143             }
 144             impl DisplayOptionIdx for Option<$name> {
 145                 type Type = DisplayOptionIdxImpl;
 146
 147                 fn display_option_idx(self) -> Self::Type {
 148                     DisplayOptionIdxImpl(self)
 149                 }
 150             }
 151         };
 152     };
 153 }
 154
 155 define_index!(SSAValIdx);
 156 define_index!(InstIdx);
 157 define_index!(BlockIdx);
 158 define_index!(BlockParamIdx);
 159 define_index!(OperandIdx);
 160
 161 impl fmt::Display for SSAValIdx {
 162     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 163         write!(f, "v{}", self.get())
 164     }
 165 }
 166
 167 impl fmt::Display for InstIdx {
 168     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 169         write!(f, "inst{}", self.get())
 170     }
 171 }
 172
 173 impl fmt::Display for BlockIdx {
 174     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 175         write!(f, "blk{}", self.get())
 176     }
 177 }
 178
 179 impl fmt::Display for BlockParamIdx {
 180     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 181         write!(f, "bparam{}", self.get())
 182     }
 183 }
 184
 185 impl fmt::Display for OperandIdx {
 186     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 187         write!(f, "operand{}", self.get())
 188     }
 189 }
 190
 191 impl BlockIdx {
 192     pub const ENTRY_BLOCK: BlockIdx = BlockIdx::new(0);
 193 }
 194
 195 /// range of instruction indexes from `start` inclusive to `end` exclusive.
 196 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
 197 pub struct InstRange {
 198     pub start: InstIdx,
 199     pub end: InstIdx,
 200 }
 201
 202 impl fmt::Display for InstRange {
 203     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 204         write!(f, "inst{}..{}", self.start.get(), self.end.get())
 205     }
 206 }
 207
 208 impl IntoIterator for InstRange {
 209     type Item = InstIdx;
 210     type IntoIter = InstRangeIter;
 211     fn into_iter(self) -> Self::IntoIter {
 212         self.iter()
 213     }
 214 }
 215
 216 impl InstRange {
 217     pub const fn iter(self) -> InstRangeIter {
 218         InstRangeIter(self.start.get()..self.end.get())
 219     }
 220     pub const fn is_empty(self) -> bool {
 221         self.start.get() >= self.end.get()
 222     }
 223     pub const fn first(self) -> Option<InstIdx> {
 224         Some(const_try_opt!(self.split_first()).0)
 225     }
 226     pub const fn last(self) -> Option<InstIdx> {
 227         Some(const_try_opt!(self.split_last()).0)
 228     }
 229     pub const fn split_first(self) -> Option<(InstIdx, InstRange)> {
 230         if self.is_empty() {
 231             None
 232         } else {
 233             Some((
 234                 self.start,
 235                 Self {
 236                     start: self.start.next(),
 237                     end: self.end,
 238                 },
 239             ))
 240         }
 241     }
 242     pub const fn split_last(self) -> Option<(InstIdx, InstRange)> {
 243         if self.is_empty() {
 244             None
 245         } else {
 246             Some((
 247                 self.end.prev(),
 248                 Self {
 249                     start: self.start,
 250                     end: self.end.prev(),
 251                 },
 252             ))
 253         }
 254     }
 255     pub const fn len(self) -> usize {
 256         if self.is_empty() {
 257             0
 258         } else {
 259             self.end.get() - self.start.get()
 260         }
 261     }
 262 }
 263
 264 #[derive(Clone, Debug)]
 265 pub struct InstRangeIter(Range<usize>);
 266
 267 impl InstRangeIter {
 268     pub const fn range(self) -> InstRange {
 269         InstRange {
 270             start: InstIdx::new(self.0.start),
 271             end: InstIdx::new(self.0.end),
 272         }
 273     }
 274 }
 275
 276 impl Iterator for InstRangeIter {
 277     type Item = InstIdx;
 278
 279     fn next(&mut self) -> Option<Self::Item> {
 280         self.0.next().map(InstIdx::new)
 281     }
 282
 283     fn size_hint(&self) -> (usize, Option<usize>) {
 284         let v = self.0.len();
 285         (v, Some(v))
 286     }
 287
 288     fn count(self) -> usize
 289     where
 290         Self: Sized,
 291     {
 292         self.len()
 293     }
 294
 295     fn last(self) -> Option<Self::Item>
 296     where
 297         Self: Sized,
 298     {
 299         self.0.last().map(InstIdx::new)
 300     }
 301
 302     fn nth(&mut self, n: usize) -> Option<Self::Item> {
 303         self.0.nth(n).map(InstIdx::new)
 304     }
 305 }
 306
 307 impl FusedIterator for InstRangeIter {}
 308
 309 impl DoubleEndedIterator for InstRangeIter {
 310     fn next_back(&mut self) -> Option<Self::Item> {
 311         self.0.next_back().map(InstIdx::new)
 312     }
 313
 314     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
 315         self.0.nth_back(n).map(InstIdx::new)
 316     }
 317 }
 318
 319 impl ExactSizeIterator for InstRangeIter {
 320     fn len(&self) -> usize {
 321         self.0.len()
 322     }
 323 }