/src/regalloc2/src/index.rs

Source
#[macro_export]
macro_rules! define_index {
    ($ix:ident, $storage:ident, $elem:ident) => {
        define_index!($ix);

        #[derive(Clone, Debug, Default)]
        pub struct $storage {
            storage: Vec<$elem>,
        }

        impl $storage {
            #[inline(always)]
            /// See `VecExt::preallocate`
            pub fn preallocate(&mut self, cap: usize) {
                use $crate::VecExt;
                self.storage.preallocate(cap);
            }

            #[inline(always)]
            pub fn len(&self) -> usize {
                self.storage.len()
            }

            #[inline(always)]
            pub fn iter(&self) -> impl Iterator<Item = &$elem> {
                self.storage.iter()
            }

            #[inline(always)]
            pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut $elem> {
                self.storage.iter_mut()
            }

            #[inline(always)]
            pub fn push(&mut self, value: $elem) -> $ix {
                let idx = $ix(self.storage.len() as u32);
                self.storage.push(value);
                idx
            }
        }

        impl core::ops::Index<$ix> for $storage {
            type Output = $elem;

            #[inline(always)]
            fn index(&self, i: $ix) -> &Self::Output {
                &self.storage[i.index()]
            }
        }

        impl core::ops::IndexMut<$ix> for $storage {
            #[inline(always)]
            fn index_mut(&mut self, i: $ix) -> &mut Self::Output {
                &mut self.storage[i.index()]
            }
        }

        impl<'a> IntoIterator for &'a $storage {
            type Item = &'a $elem;
            type IntoIter = core::slice::Iter<'a, $elem>;

            #[inline(always)]
            fn into_iter(self) -> Self::IntoIter {
                self.storage.iter()
            }
        }

        impl<'a> IntoIterator for &'a mut $storage {
            type Item = &'a mut $elem;
            type IntoIter = core::slice::IterMut<'a, $elem>;

            #[inline(always)]
            fn into_iter(self) -> Self::IntoIter {
                self.storage.iter_mut()
            }
        }
    };

    ($ix:ident) => {
        #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
        #[cfg_attr(
            feature = "enable-serde",
            derive(::serde::Serialize, ::serde::Deserialize)
        )]
        pub struct $ix(pub u32);
        impl $ix {
            #[inline(always)]
            pub fn new(i: usize) -> Self {
                Self(i as u32)
            }
            #[inline(always)]
            pub fn index(self) -> usize {
                debug_assert!(self.is_valid());
                self.0 as usize
            }
            #[inline(always)]
            pub fn invalid() -> Self {
                Self(u32::MAX)
            }
            #[inline(always)]
            pub fn is_invalid(self) -> bool {
                self == Self::invalid()
            }
            #[inline(always)]
            pub fn is_valid(self) -> bool {
                self != Self::invalid()
            }
            #[inline(always)]
            pub fn next(self) -> $ix {
                debug_assert!(self.is_valid());
                Self(self.0 + 1)
            }
            #[inline(always)]
            pub fn prev(self) -> $ix {
                debug_assert!(self.is_valid());
                Self(self.0 - 1)
            }

            #[inline(always)]
            pub fn raw_u32(self) -> u32 {
                self.0
            }
        }

        impl crate::index::ContainerIndex for $ix {}
    };
}

pub trait ContainerIndex: Clone + Copy + core::fmt::Debug + PartialEq + Eq {}

pub trait ContainerComparator {
    type Ix: ContainerIndex;
    fn compare(&self, a: Self::Ix, b: Self::Ix) -> core::cmp::Ordering;
}

define_index!(Inst);
define_index!(Block);

#[derive(Clone, Copy, Debug)]
#[cfg_attr(
    feature = "enable-serde",
    derive(::serde::Serialize, ::serde::Deserialize)
)]
pub struct InstRange(Inst, Inst);

impl InstRange {
    #[inline(always)]
    pub fn new(from: Inst, to: Inst) -> Self {
        debug_assert!(from.index() <= to.index());
        InstRange(from, to)
    }

    #[inline(always)]
    pub fn first(self) -> Inst {
        debug_assert!(self.len() > 0);
        self.0
    }

    #[inline(always)]
    pub fn last(self) -> Inst {
        debug_assert!(self.len() > 0);
        self.1.prev()
    }

    #[inline(always)]
    pub fn rest(self) -> InstRange {
        debug_assert!(self.len() > 0);
        InstRange::new(self.0.next(), self.1)
    }

    #[inline(always)]
    pub fn len(self) -> usize {
        self.1.index() - self.0.index()
    }

    #[inline(always)]
    pub fn iter(self) -> impl DoubleEndedIterator<Item = Inst> {
        (self.0.index()..self.1.index()).map(|i| Inst::new(i))
    }
}

#[cfg(test)]
mod test {
    use alloc::vec;
    use alloc::vec::Vec;

    use super::*;

    #[test]
    fn test_inst_range() {
        let range = InstRange::new(Inst::new(0), Inst::new(0));
        debug_assert_eq!(range.len(), 0);

        let range = InstRange::new(Inst::new(0), Inst::new(5));
        debug_assert_eq!(range.first().index(), 0);
        debug_assert_eq!(range.last().index(), 4);
        debug_assert_eq!(range.len(), 5);
        debug_assert_eq!(
            range.iter().collect::<Vec<_>>(),
            vec![
                Inst::new(0),
                Inst::new(1),
                Inst::new(2),
                Inst::new(3),
                Inst::new(4)
            ]
        );
    }
}

Coverage Report

Created: 2026-08-02 07:35

Line	Count	Source
1		#[macro_export]
2		macro_rules! define_index {
3		($ix:ident, $storage:ident, $elem:ident) => {
4		define_index!($ix);
5
6		#[derive(Clone, Debug, Default)]
7		pub struct $storage {
8		storage: Vec<$elem>,
9		}
10
11		impl $storage {
12		#[inline(always)]
13		/// See `VecExt::preallocate`
14	0	pub fn preallocate(&mut self, cap: usize) {
15		use $crate::VecExt;
16	0	self.storage.preallocate(cap);
17	0	} Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRanges>::preallocate Unexecuted instantiation: <regalloc2::ion::data_structures::VRegs>::preallocate Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSets>::preallocate Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundles>::preallocate
18
19		#[inline(always)]
20	0	pub fn len(&self) -> usize {
21	0	self.storage.len()
22	0	} Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRanges>::len Unexecuted instantiation: <regalloc2::ion::data_structures::VRegs>::len Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSets>::len Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundles>::len
23
24		#[inline(always)]
25	0	pub fn iter(&self) -> impl Iterator<Item = &$elem> {
26	0	self.storage.iter()
27	0	} Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSets>::iter Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRanges>::iter Unexecuted instantiation: <regalloc2::ion::data_structures::VRegs>::iter Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundles>::iter
28
29		#[inline(always)]
30	0	pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut $elem> {
31	0	self.storage.iter_mut()
32	0	} Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRanges>::iter_mut Unexecuted instantiation: <regalloc2::ion::data_structures::VRegs>::iter_mut Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSets>::iter_mut Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundles>::iter_mut
33
34		#[inline(always)]
35	0	pub fn push(&mut self, value: $elem) -> $ix {
36	0	let idx = $ix(self.storage.len() as u32);
37	0	self.storage.push(value);
38	0	idx
39	0	} Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRanges>::push Unexecuted instantiation: <regalloc2::ion::data_structures::VRegs>::push Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSets>::push Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundles>::push
40		}
41
42		impl core::ops::Index<$ix> for $storage {
43		type Output = $elem;
44
45		#[inline(always)]
46	0	fn index(&self, i: $ix) -> &Self::Output {
47	0	&self.storage[i.index()]
48	0	} Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundles as core::ops::index::Index<regalloc2::ion::data_structures::LiveBundleIndex>>::index Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRanges as core::ops::index::Index<regalloc2::ion::data_structures::LiveRangeIndex>>::index Unexecuted instantiation: <regalloc2::ion::data_structures::VRegs as core::ops::index::Index<regalloc2::ion::data_structures::VRegIndex>>::index Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSets as core::ops::index::Index<regalloc2::ion::data_structures::SpillSetIndex>>::index
49		}
50
51		impl core::ops::IndexMut<$ix> for $storage {
52		#[inline(always)]
53	0	fn index_mut(&mut self, i: $ix) -> &mut Self::Output {
54	0	&mut self.storage[i.index()]
55	0	} Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRanges as core::ops::index::IndexMut<regalloc2::ion::data_structures::LiveRangeIndex>>::index_mut Unexecuted instantiation: <regalloc2::ion::data_structures::VRegs as core::ops::index::IndexMut<regalloc2::ion::data_structures::VRegIndex>>::index_mut Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSets as core::ops::index::IndexMut<regalloc2::ion::data_structures::SpillSetIndex>>::index_mut Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundles as core::ops::index::IndexMut<regalloc2::ion::data_structures::LiveBundleIndex>>::index_mut
56		}
57
58		impl<'a> IntoIterator for &'a $storage {
59		type Item = &'a $elem;
60		type IntoIter = core::slice::Iter<'a, $elem>;
61
62		#[inline(always)]
63	0	fn into_iter(self) -> Self::IntoIter {
64	0	self.storage.iter()
65	0	} Unexecuted instantiation: <&regalloc2::ion::data_structures::LiveRanges as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <&regalloc2::ion::data_structures::VRegs as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <&regalloc2::ion::data_structures::SpillSets as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <&regalloc2::ion::data_structures::LiveBundles as core::iter::traits::collect::IntoIterator>::into_iter
66		}
67
68		impl<'a> IntoIterator for &'a mut $storage {
69		type Item = &'a mut $elem;
70		type IntoIter = core::slice::IterMut<'a, $elem>;
71
72		#[inline(always)]
73	0	fn into_iter(self) -> Self::IntoIter {
74	0	self.storage.iter_mut()
75	0	} Unexecuted instantiation: <&mut regalloc2::ion::data_structures::SpillSets as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <&mut regalloc2::ion::data_structures::LiveBundles as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <&mut regalloc2::ion::data_structures::LiveRanges as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <&mut regalloc2::ion::data_structures::VRegs as core::iter::traits::collect::IntoIterator>::into_iter
76		}
77		};
78
79		($ix:ident) => {
80		#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
81		#[cfg_attr(
82		feature = "enable-serde",
83		derive(::serde::Serialize, ::serde::Deserialize)
84		)]
85		pub struct $ix(pub u32);
86		impl $ix {
87		#[inline(always)]
88	0	pub fn new(i: usize) -> Self {
89	0	Self(i as u32)
90	0	} Unexecuted instantiation: <regalloc2::index::Inst>::new Unexecuted instantiation: <regalloc2::index::Block>::new Unexecuted instantiation: <regalloc2::ion::data_structures::VRegIndex>::new Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRangeIndex>::new Unexecuted instantiation: <regalloc2::ion::data_structures::UseIndex>::new Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSetIndex>::new Unexecuted instantiation: <regalloc2::ion::data_structures::PRegIndex>::new Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSlotIndex>::new Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundleIndex>::new
91		#[inline(always)]
92	0	pub fn index(self) -> usize {
93	0	debug_assert!(self.is_valid());
94	0	self.0 as usize
95	0	} Unexecuted instantiation: <regalloc2::ion::data_structures::VRegIndex>::index Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundleIndex>::index Unexecuted instantiation: <regalloc2::index::Inst>::index Unexecuted instantiation: <regalloc2::index::Block>::index Unexecuted instantiation: <regalloc2::ion::data_structures::UseIndex>::index Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRangeIndex>::index Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSetIndex>::index Unexecuted instantiation: <regalloc2::ion::data_structures::PRegIndex>::index Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSlotIndex>::index
96		#[inline(always)]
97	0	pub fn invalid() -> Self {
98	0	Self(u32::MAX)
99	0	} Unexecuted instantiation: <regalloc2::index::Inst>::invalid Unexecuted instantiation: <regalloc2::index::Block>::invalid Unexecuted instantiation: <regalloc2::ion::data_structures::UseIndex>::invalid Unexecuted instantiation: <regalloc2::ion::data_structures::PRegIndex>::invalid Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRangeIndex>::invalid Unexecuted instantiation: <regalloc2::ion::data_structures::VRegIndex>::invalid Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSetIndex>::invalid Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSlotIndex>::invalid Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundleIndex>::invalid
100		#[inline(always)]
101	0	pub fn is_invalid(self) -> bool {
102	0	self == Self::invalid()
103	0	} Unexecuted instantiation: <regalloc2::index::Block>::is_invalid Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRangeIndex>::is_invalid Unexecuted instantiation: <regalloc2::ion::data_structures::UseIndex>::is_invalid Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSetIndex>::is_invalid Unexecuted instantiation: <regalloc2::ion::data_structures::PRegIndex>::is_invalid Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSlotIndex>::is_invalid Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundleIndex>::is_invalid Unexecuted instantiation: <regalloc2::index::Inst>::is_invalid Unexecuted instantiation: <regalloc2::ion::data_structures::VRegIndex>::is_invalid
104		#[inline(always)]
105	0	pub fn is_valid(self) -> bool {
106	0	self != Self::invalid()
107	0	} Unexecuted instantiation: <regalloc2::index::Block>::is_valid Unexecuted instantiation: <regalloc2::ion::data_structures::UseIndex>::is_valid Unexecuted instantiation: <regalloc2::ion::data_structures::VRegIndex>::is_valid Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSetIndex>::is_valid Unexecuted instantiation: <regalloc2::ion::data_structures::PRegIndex>::is_valid Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSlotIndex>::is_valid Unexecuted instantiation: <regalloc2::index::Inst>::is_valid Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRangeIndex>::is_valid Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundleIndex>::is_valid
108		#[inline(always)]
109	0	pub fn next(self) -> $ix {
110	0	debug_assert!(self.is_valid());
111	0	Self(self.0 + 1)
112	0	} Unexecuted instantiation: <regalloc2::index::Inst>::next Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRangeIndex>::next Unexecuted instantiation: <regalloc2::ion::data_structures::UseIndex>::next Unexecuted instantiation: <regalloc2::ion::data_structures::VRegIndex>::next Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSetIndex>::next Unexecuted instantiation: <regalloc2::ion::data_structures::PRegIndex>::next Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSlotIndex>::next Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundleIndex>::next Unexecuted instantiation: <regalloc2::index::Block>::next
113		#[inline(always)]
114	0	pub fn prev(self) -> $ix {
115	0	debug_assert!(self.is_valid());
116	0	Self(self.0 - 1)
117	0	} Unexecuted instantiation: <regalloc2::index::Inst>::prev Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRangeIndex>::prev Unexecuted instantiation: <regalloc2::ion::data_structures::UseIndex>::prev Unexecuted instantiation: <regalloc2::ion::data_structures::VRegIndex>::prev Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSetIndex>::prev Unexecuted instantiation: <regalloc2::ion::data_structures::PRegIndex>::prev Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSlotIndex>::prev Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundleIndex>::prev Unexecuted instantiation: <regalloc2::index::Block>::prev
118
119		#[inline(always)]
120	0	pub fn raw_u32(self) -> u32 {
121	0	self.0
122	0	} Unexecuted instantiation: <regalloc2::ion::data_structures::VRegIndex>::raw_u32 Unexecuted instantiation: <regalloc2::index::Block>::raw_u32 Unexecuted instantiation: <regalloc2::ion::data_structures::LiveRangeIndex>::raw_u32 Unexecuted instantiation: <regalloc2::ion::data_structures::UseIndex>::raw_u32 Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSetIndex>::raw_u32 Unexecuted instantiation: <regalloc2::ion::data_structures::PRegIndex>::raw_u32 Unexecuted instantiation: <regalloc2::ion::data_structures::SpillSlotIndex>::raw_u32 Unexecuted instantiation: <regalloc2::index::Inst>::raw_u32 Unexecuted instantiation: <regalloc2::ion::data_structures::LiveBundleIndex>::raw_u32
123		}
124
125		impl crate::index::ContainerIndex for $ix {}
126		};
127		}
128
129		pub trait ContainerIndex: Clone + Copy + core::fmt::Debug + PartialEq + Eq {}
130
131		pub trait ContainerComparator {
132		type Ix: ContainerIndex;
133		fn compare(&self, a: Self::Ix, b: Self::Ix) -> core::cmp::Ordering;
134		}
135
136		define_index!(Inst);
137		define_index!(Block);
138
139		#[derive(Clone, Copy, Debug)]
140		#[cfg_attr(
141		feature = "enable-serde",
142		derive(::serde::Serialize, ::serde::Deserialize)
143		)]
144		pub struct InstRange(Inst, Inst);
145
146		impl InstRange {
147		#[inline(always)]
148	0	pub fn new(from: Inst, to: Inst) -> Self {
149	0	debug_assert!(from.index() <= to.index());
150	0	InstRange(from, to)
151	0	}
152
153		#[inline(always)]
154	0	pub fn first(self) -> Inst {
155	0	debug_assert!(self.len() > 0);
156	0	self.0
157	0	}
158
159		#[inline(always)]
160	0	pub fn last(self) -> Inst {
161	0	debug_assert!(self.len() > 0);
162	0	self.1.prev()
163	0	}
164
165		#[inline(always)]
166	0	pub fn rest(self) -> InstRange {
167	0	debug_assert!(self.len() > 0);
168	0	InstRange::new(self.0.next(), self.1)
169	0	}
170
171		#[inline(always)]
172	0	pub fn len(self) -> usize {
173	0	self.1.index() - self.0.index()
174	0	}
175
176		#[inline(always)]
177	0	pub fn iter(self) -> impl DoubleEndedIterator<Item = Inst> {
178	0	(self.0.index()..self.1.index()).map(\|i\| Inst::new(i))
179	0	}
180		}
181
182		#[cfg(test)]
183		mod test {
184		use alloc::vec;
185		use alloc::vec::Vec;
186
187		use super::*;
188
189		#[test]
190		fn test_inst_range() {
191		let range = InstRange::new(Inst::new(0), Inst::new(0));
192		debug_assert_eq!(range.len(), 0);
193
194		let range = InstRange::new(Inst::new(0), Inst::new(5));
195		debug_assert_eq!(range.first().index(), 0);
196		debug_assert_eq!(range.last().index(), 4);
197		debug_assert_eq!(range.len(), 5);
198		debug_assert_eq!(
199		range.iter().collect::<Vec<_>>(),
200		vec![
201		Inst::new(0),
202		Inst::new(1),
203		Inst::new(2),
204		Inst::new(3),
205		Inst::new(4)
206		]
207		);
208		}
209		}