/src/regalloc2/src/fastalloc/lru.rs

Source
use crate::{FxHashSet, PReg, PRegSet, RegClass};
use alloc::vec;
use alloc::vec::Vec;
use core::{
    fmt,
    ops::{Index, IndexMut},
};

/// A least-recently-used cache organized as a linked list based on a vector.
pub struct Lru {
    /// The list of node information.
    ///
    /// Each node corresponds to a physical register.
    /// The index of a node is the `address` from the perspective of the linked list.
    pub data: Vec<LruNode>,
    /// Index of the most recently used register.
    pub head: u8,
    /// Class of registers in the cache.
    pub regclass: RegClass,
}

#[derive(Clone, Copy, Debug)]
pub struct LruNode {
    /// The previous physical register in the list.
    pub prev: u8,
    /// The next physical register in the list.
    pub next: u8,
}

impl Lru {
    pub fn new(regclass: RegClass, regs: &PRegSet) -> Self {
        let regs = regs.into_iter().collect::<Vec<_>>();
        let mut data = vec![
            LruNode {
                prev: u8::MAX,
                next: u8::MAX
            };
            PReg::MAX + 1
        ];
        let no_of_regs = regs.len();
        for i in 0..no_of_regs {
            let (reg, prev_reg, next_reg) = (
                regs[i],
                regs[i.checked_sub(1).unwrap_or(no_of_regs - 1)],
                regs[if i >= no_of_regs - 1 { 0 } else { i + 1 }],
            );
            data[reg.hw_enc()].prev = prev_reg.hw_enc() as u8;
            data[reg.hw_enc()].next = next_reg.hw_enc() as u8;
        }
        Self {
            head: if regs.is_empty() {
                u8::MAX
            } else {
                regs[0].hw_enc() as u8
            },
            data,
            regclass,
        }
    }

    /// Marks the physical register `preg` as the most recently used
    pub fn poke(&mut self, preg: PReg) {
        trace!(
            "Before poking: {:?} LRU. head: {:?}, Actual data: {:?}",
            self.regclass,
            self.head,
            self.data
        );
        trace!("About to poke {:?} in {:?} LRU", preg, self.regclass);
        let prev_newest = self.head;
        let hw_enc = preg.hw_enc() as u8;
        if hw_enc == prev_newest {
            return;
        }
        if self.data[prev_newest as usize].prev != hw_enc {
            self.remove(hw_enc as usize);
            self.insert_before(hw_enc, self.head);
        }
        self.head = hw_enc;
        trace!("Poked {:?} in {:?} LRU", preg, self.regclass);
        if cfg!(debug_assertions) {
            self.validate_lru();
        }
    }

    /// Gets the least recently used physical register.
    pub fn pop(&mut self) -> PReg {
        trace!(
            "Before popping: {:?} LRU. head: {:?}, Actual data: {:?}",
            self.regclass,
            self.head,
            self.data
        );
        trace!("Popping {:?} LRU", self.regclass);
        if self.is_empty() {
            panic!("LRU is empty");
        }
        let oldest = self.data[self.head as usize].prev;
        trace!("Popped p{oldest} in {:?} LRU", self.regclass);
        if cfg!(debug_assertions) {
            self.validate_lru();
        }
        PReg::new(oldest as usize, self.regclass)
    }

    /// Get the last PReg in the LRU from the set `from`.
    pub fn last(&self, from: PRegSet) -> Option<PReg> {
        trace!("Getting the last preg from the LRU in set {from}");
        self.last_satisfying(|preg| from.contains(preg))
    }

    /// Get the last PReg from the LRU for which `f` returns true.
    pub fn last_satisfying<F: Fn(PReg) -> bool>(&self, f: F) -> Option<PReg> {
        trace!("Getting the last preg from the LRU satisfying...");
        if self.is_empty() {
            panic!("LRU is empty");
        }
        let mut last = self.data[self.head as usize].prev;
        let init_last = last;
        loop {
            let preg = PReg::new(last as usize, self.regclass);
            if f(preg) {
                return Some(preg);
            }
            last = self.data[last as usize].prev;
            if last == init_last {
                return None;
            }
        }
    }

    /// Splices out a node from the list.
    fn remove(&mut self, hw_enc: usize) {
        trace!(
            "Before removing: {:?} LRU. head: {:?}, Actual data: {:?}",
            self.regclass,
            self.head,
            self.data
        );
        trace!("Removing p{hw_enc} from {:?} LRU", self.regclass);
        let (iprev, inext) = (
            self.data[hw_enc].prev as usize,
            self.data[hw_enc].next as usize,
        );
        self.data[iprev].next = self.data[hw_enc].next;
        self.data[inext].prev = self.data[hw_enc].prev;
        self.data[hw_enc].prev = u8::MAX;
        self.data[hw_enc].next = u8::MAX;
        if hw_enc == self.head as usize {
            if hw_enc == inext {
                // There are no regs in the LRU
                self.head = u8::MAX;
            } else {
                self.head = inext as u8;
            }
        }
        trace!("Removed p{hw_enc} from {:?} LRU", self.regclass);
        if cfg!(debug_assertions) {
            self.validate_lru();
        }
    }

    /// Insert node `i` before node `j` in the list.
    fn insert_before(&mut self, i: u8, j: u8) {
        trace!(
            "Before inserting: {:?} LRU. head: {:?}, Actual data: {:?}",
            self.regclass,
            self.head,
            self.data
        );
        trace!("Inserting p{i} before {j} in {:?} LRU", self.regclass);
        let prev = self.data[j as usize].prev;
        self.data[prev as usize].next = i;
        self.data[j as usize].prev = i;
        self.data[i as usize] = LruNode { next: j, prev };
        trace!("Done inserting p{i} before {j} in {:?} LRU", self.regclass);
        if cfg!(debug_assertions) {
            self.validate_lru();
        }
    }

    pub fn is_empty(&self) -> bool {
        self.head == u8::MAX
    }

    // Using this to debug.
    fn validate_lru(&self) {
        trace!(
            "{:?} LRU. head: {:?}, Actual data: {:?}",
            self.regclass,
            self.head,
            self.data
        );
        if self.head != u8::MAX {
            let mut node = self.data[self.head as usize].next;
            let mut seen = FxHashSet::default();
            while node != self.head {
                if seen.contains(&node) {
                    panic!(
                        "Cycle detected in {:?} LRU.\n
                        head: {:?}, actual data: {:?}",
                        self.regclass, self.head, self.data
                    );
                }
                seen.insert(node);
                node = self.data[node as usize].next;
            }
            for i in 0..self.data.len() {
                if self.data[i].prev == u8::MAX && self.data[i].next == u8::MAX {
                    // Removed
                    continue;
                }
                if self.data[i].prev == u8::MAX || self.data[i].next == u8::MAX {
                    panic!(
                        "Invalid LRU. p{} next or previous is an invalid value, but not both",
                        i
                    );
                }
                if self.data[self.data[i].prev as usize].next != i as u8 {
                    panic!(
                        "Invalid LRU. p{i} prev is p{:?}, but p{:?} next is {:?}",
                        self.data[i].prev,
                        self.data[i].prev,
                        self.data[self.data[i].prev as usize].next
                    );
                }
                if self.data[self.data[i].next as usize].prev != i as u8 {
                    panic!(
                        "Invalid LRU. p{i} next is p{:?}, but p{:?} prev is p{:?}",
                        self.data[i].next,
                        self.data[i].next,
                        self.data[self.data[i].next as usize].prev
                    );
                }
            }
        }
    }
}

impl fmt::Debug for Lru {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        use alloc::format;
        let data_str = if self.head == u8::MAX {
            format!("<empty>")
        } else {
            let mut data_str = format!("p{}", self.head);
            let mut node = self.data[self.head as usize].next;
            let mut seen = FxHashSet::default();
            while node != self.head {
                if seen.contains(&node) {
                    panic!(
                        "The {:?} LRU is messed up:
                       head: {:?}, {:?} -> p{node}, actual data: {:?}",
                        self.regclass, self.head, data_str, self.data
                    );
                }
                seen.insert(node);
                data_str += &format!(" -> p{}", node);
                node = self.data[node as usize].next;
            }
            data_str
        };
        f.debug_struct("Lru")
            .field("head", if self.is_empty() { &"none" } else { &self.head })
            .field("class", &self.regclass)
            .field("data", &data_str)
            .finish()
    }
}

#[derive(Clone)]
pub struct PartedByRegClass<T> {
    pub items: [T; 3],
}

impl<T: Copy> Copy for PartedByRegClass<T> {}

impl<T> Index<RegClass> for PartedByRegClass<T> {
    type Output = T;

    fn index(&self, index: RegClass) -> &Self::Output {
        &self.items[index as usize]
    }
}

impl<T> IndexMut<RegClass> for PartedByRegClass<T> {
    fn index_mut(&mut self, index: RegClass) -> &mut Self::Output {
        &mut self.items[index as usize]
    }
}

impl<T: PartialEq> PartialEq for PartedByRegClass<T> {
    fn eq(&self, other: &Self) -> bool {
        self.items.eq(&other.items)
    }
}

/// Least-recently-used caches for register classes Int, Float, and Vector, respectively.
pub type Lrus = PartedByRegClass<Lru>;

impl Lrus {
    pub fn new(int_regs: &PRegSet, float_regs: &PRegSet, vec_regs: &PRegSet) -> Self {
        Self {
            items: [
                Lru::new(RegClass::Int, int_regs),
                Lru::new(RegClass::Float, float_regs),
                Lru::new(RegClass::Vector, vec_regs),
            ],
        }
    }
}

use core::fmt::{Debug, Display};

impl<T: Display> Display for PartedByRegClass<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{{ int: {}, float: {}, vector: {} }}",
            self.items[0], self.items[1], self.items[2]
        )
    }
}

impl<T: Debug> Debug for PartedByRegClass<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{{ int: {:?}, float: {:?}, vector: {:?} }}",
            self.items[0], self.items[1], self.items[2]
        )
    }
}

Coverage Report

Created: 2026-01-22 08:11

Line	Count	Source
1		use crate::{FxHashSet, PReg, PRegSet, RegClass};
2		use alloc::vec;
3		use alloc::vec::Vec;
4		use core::{
5		fmt,
6		ops::{Index, IndexMut},
7		};
8
9		/// A least-recently-used cache organized as a linked list based on a vector.
10		pub struct Lru {
11		/// The list of node information.
12		///
13		/// Each node corresponds to a physical register.
14		/// The index of a node is the `address` from the perspective of the linked list.
15		pub data: Vec<LruNode>,
16		/// Index of the most recently used register.
17		pub head: u8,
18		/// Class of registers in the cache.
19		pub regclass: RegClass,
20		}
21
22		#[derive(Clone, Copy, Debug)]
23		pub struct LruNode {
24		/// The previous physical register in the list.
25		pub prev: u8,
26		/// The next physical register in the list.
27		pub next: u8,
28		}
29
30		impl Lru {
31	0	pub fn new(regclass: RegClass, regs: &PRegSet) -> Self {
32	0	let regs = regs.into_iter().collect::<Vec<_>>();
33	0	let mut data = vec![
34	0	LruNode {
35	0	prev: u8::MAX,
36	0	next: u8::MAX
37	0	};
38	0	PReg::MAX + 1
39		];
40	0	let no_of_regs = regs.len();
41	0	for i in 0..no_of_regs {
42	0	let (reg, prev_reg, next_reg) = (
43	0	regs[i],
44	0	regs[i.checked_sub(1).unwrap_or(no_of_regs - 1)],
45	0	regs[if i >= no_of_regs - 1 { 0 } else { i + 1 }],
46		);
47	0	data[reg.hw_enc()].prev = prev_reg.hw_enc() as u8;
48	0	data[reg.hw_enc()].next = next_reg.hw_enc() as u8;
49		}
50		Self {
51	0	head: if regs.is_empty() {
52	0	u8::MAX
53		} else {
54	0	regs[0].hw_enc() as u8
55		},
56	0	data,
57	0	regclass,
58		}
59	0	}
60
61		/// Marks the physical register `preg` as the most recently used
62	0	pub fn poke(&mut self, preg: PReg) {
63	0	trace!(
64	0	"Before poking: {:?} LRU. head: {:?}, Actual data: {:?}",
65		self.regclass,
66		self.head,
67		self.data
68		);
69	0	trace!("About to poke {:?} in {:?} LRU", preg, self.regclass);
70	0	let prev_newest = self.head;
71	0	let hw_enc = preg.hw_enc() as u8;
72	0	if hw_enc == prev_newest {
73	0	return;
74	0	}
75	0	if self.data[prev_newest as usize].prev != hw_enc {
76	0	self.remove(hw_enc as usize);
77	0	self.insert_before(hw_enc, self.head);
78	0	}
79	0	self.head = hw_enc;
80	0	trace!("Poked {:?} in {:?} LRU", preg, self.regclass);
81	0	if cfg!(debug_assertions) {
82	0	self.validate_lru();
83	0	}
84	0	}
85
86		/// Gets the least recently used physical register.
87	0	pub fn pop(&mut self) -> PReg {
88	0	trace!(
89	0	"Before popping: {:?} LRU. head: {:?}, Actual data: {:?}",
90		self.regclass,
91		self.head,
92		self.data
93		);
94	0	trace!("Popping {:?} LRU", self.regclass);
95	0	if self.is_empty() {
96	0	panic!("LRU is empty");
97	0	}
98	0	let oldest = self.data[self.head as usize].prev;
99	0	trace!("Popped p{oldest} in {:?} LRU", self.regclass);
100	0	if cfg!(debug_assertions) {
101	0	self.validate_lru();
102	0	}
103	0	PReg::new(oldest as usize, self.regclass)
104	0	}
105
106		/// Get the last PReg in the LRU from the set `from`.
107	0	pub fn last(&self, from: PRegSet) -> Option<PReg> {
108	0	trace!("Getting the last preg from the LRU in set {from}");
109	0	self.last_satisfying(\|preg\| from.contains(preg))
110	0	}
111
112		/// Get the last PReg from the LRU for which `f` returns true.
113	0	pub fn last_satisfying<F: Fn(PReg) -> bool>(&self, f: F) -> Option<PReg> {
114	0	trace!("Getting the last preg from the LRU satisfying...");
115	0	if self.is_empty() {
116	0	panic!("LRU is empty");
117	0	}
118	0	let mut last = self.data[self.head as usize].prev;
119	0	let init_last = last;
120		loop {
121	0	let preg = PReg::new(last as usize, self.regclass);
122	0	if f(preg) {
123	0	return Some(preg);
124	0	}
125	0	last = self.data[last as usize].prev;
126	0	if last == init_last {
127	0	return None;
128	0	}
129		}
130	0	}
131
132		/// Splices out a node from the list.
133	0	fn remove(&mut self, hw_enc: usize) {
134	0	trace!(
135	0	"Before removing: {:?} LRU. head: {:?}, Actual data: {:?}",
136		self.regclass,
137		self.head,
138		self.data
139		);
140	0	trace!("Removing p{hw_enc} from {:?} LRU", self.regclass);
141	0	let (iprev, inext) = (
142	0	self.data[hw_enc].prev as usize,
143	0	self.data[hw_enc].next as usize,
144	0	);
145	0	self.data[iprev].next = self.data[hw_enc].next;
146	0	self.data[inext].prev = self.data[hw_enc].prev;
147	0	self.data[hw_enc].prev = u8::MAX;
148	0	self.data[hw_enc].next = u8::MAX;
149	0	if hw_enc == self.head as usize {
150	0	if hw_enc == inext {
151	0	// There are no regs in the LRU
152	0	self.head = u8::MAX;
153	0	} else {
154	0	self.head = inext as u8;
155	0	}
156	0	}
157	0	trace!("Removed p{hw_enc} from {:?} LRU", self.regclass);
158	0	if cfg!(debug_assertions) {
159	0	self.validate_lru();
160	0	}
161	0	}
162
163		/// Insert node `i` before node `j` in the list.
164	0	fn insert_before(&mut self, i: u8, j: u8) {
165	0	trace!(
166	0	"Before inserting: {:?} LRU. head: {:?}, Actual data: {:?}",
167		self.regclass,
168		self.head,
169		self.data
170		);
171	0	trace!("Inserting p{i} before {j} in {:?} LRU", self.regclass);
172	0	let prev = self.data[j as usize].prev;
173	0	self.data[prev as usize].next = i;
174	0	self.data[j as usize].prev = i;
175	0	self.data[i as usize] = LruNode { next: j, prev };
176	0	trace!("Done inserting p{i} before {j} in {:?} LRU", self.regclass);
177	0	if cfg!(debug_assertions) {
178	0	self.validate_lru();
179	0	}
180	0	}
181
182	0	pub fn is_empty(&self) -> bool {
183	0	self.head == u8::MAX
184	0	}
185
186		// Using this to debug.
187	0	fn validate_lru(&self) {
188	0	trace!(
189	0	"{:?} LRU. head: {:?}, Actual data: {:?}",
190		self.regclass,
191		self.head,
192		self.data
193		);
194	0	if self.head != u8::MAX {
195	0	let mut node = self.data[self.head as usize].next;
196	0	let mut seen = FxHashSet::default();
197	0	while node != self.head {
198	0	if seen.contains(&node) {
199	0	panic!(
200	0	"Cycle detected in {:?} LRU.\n
201	0	head: {:?}, actual data: {:?}",
202		self.regclass, self.head, self.data
203		);
204	0	}
205	0	seen.insert(node);
206	0	node = self.data[node as usize].next;
207		}
208	0	for i in 0..self.data.len() {
209	0	if self.data[i].prev == u8::MAX && self.data[i].next == u8::MAX {
210		// Removed
211	0	continue;
212	0	}
213	0	if self.data[i].prev == u8::MAX \|\| self.data[i].next == u8::MAX {
214	0	panic!(
215	0	"Invalid LRU. p{} next or previous is an invalid value, but not both",
216		i
217		);
218	0	}
219	0	if self.data[self.data[i].prev as usize].next != i as u8 {
220	0	panic!(
221	0	"Invalid LRU. p{i} prev is p{:?}, but p{:?} next is {:?}",
222	0	self.data[i].prev,
223	0	self.data[i].prev,
224	0	self.data[self.data[i].prev as usize].next
225		);
226	0	}
227	0	if self.data[self.data[i].next as usize].prev != i as u8 {
228	0	panic!(
229	0	"Invalid LRU. p{i} next is p{:?}, but p{:?} prev is p{:?}",
230	0	self.data[i].next,
231	0	self.data[i].next,
232	0	self.data[self.data[i].next as usize].prev
233		);
234	0	}
235		}
236	0	}
237	0	}
238		}
239
240		impl fmt::Debug for Lru {
241	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
242		use alloc::format;
243	0	let data_str = if self.head == u8::MAX {
244	0	format!("<empty>")
245		} else {
246	0	let mut data_str = format!("p{}", self.head);
247	0	let mut node = self.data[self.head as usize].next;
248	0	let mut seen = FxHashSet::default();
249	0	while node != self.head {
250	0	if seen.contains(&node) {
251	0	panic!(
252	0	"The {:?} LRU is messed up:
253	0	head: {:?}, {:?} -> p{node}, actual data: {:?}",
254		self.regclass, self.head, data_str, self.data
255		);
256	0	}
257	0	seen.insert(node);
258	0	data_str += &format!(" -> p{}", node);
259	0	node = self.data[node as usize].next;
260		}
261	0	data_str
262		};
263	0	f.debug_struct("Lru")
264	0	.field("head", if self.is_empty() { &"none" } else { &self.head })
265	0	.field("class", &self.regclass)
266	0	.field("data", &data_str)
267	0	.finish()
268	0	}
269		}
270
271		#[derive(Clone)]
272		pub struct PartedByRegClass<T> {
273		pub items: [T; 3],
274		}
275
276		impl<T: Copy> Copy for PartedByRegClass<T> {}
277
278		impl<T> Index<RegClass> for PartedByRegClass<T> {
279		type Output = T;
280
281	0	fn index(&self, index: RegClass) -> &Self::Output {
282	0	&self.items[index as usize]
283	0	} Unexecuted instantiation: <regalloc2::fastalloc::lru::PartedByRegClass<core::option::Option<regalloc2::PReg>> as core::ops::index::Index<regalloc2::RegClass>>::index Unexecuted instantiation: <regalloc2::fastalloc::lru::PartedByRegClass<regalloc2::fastalloc::lru::Lru> as core::ops::index::Index<regalloc2::RegClass>>::index Unexecuted instantiation: <regalloc2::fastalloc::lru::PartedByRegClass<regalloc2::PReg> as core::ops::index::Index<regalloc2::RegClass>>::index Unexecuted instantiation: <regalloc2::fastalloc::lru::PartedByRegClass<i16> as core::ops::index::Index<regalloc2::RegClass>>::index
284		}
285
286		impl<T> IndexMut<RegClass> for PartedByRegClass<T> {
287	0	fn index_mut(&mut self, index: RegClass) -> &mut Self::Output {
288	0	&mut self.items[index as usize]
289	0	} Unexecuted instantiation: <regalloc2::fastalloc::lru::PartedByRegClass<core::option::Option<regalloc2::PReg>> as core::ops::index::IndexMut<regalloc2::RegClass>>::index_mut Unexecuted instantiation: <regalloc2::fastalloc::lru::PartedByRegClass<regalloc2::fastalloc::lru::Lru> as core::ops::index::IndexMut<regalloc2::RegClass>>::index_mut Unexecuted instantiation: <regalloc2::fastalloc::lru::PartedByRegClass<i16> as core::ops::index::IndexMut<regalloc2::RegClass>>::index_mut
290		}
291
292		impl<T: PartialEq> PartialEq for PartedByRegClass<T> {
293	0	fn eq(&self, other: &Self) -> bool {
294	0	self.items.eq(&other.items)
295	0	}
296		}
297
298		/// Least-recently-used caches for register classes Int, Float, and Vector, respectively.
299		pub type Lrus = PartedByRegClass<Lru>;
300
301		impl Lrus {
302	0	pub fn new(int_regs: &PRegSet, float_regs: &PRegSet, vec_regs: &PRegSet) -> Self {
303	0	Self {
304	0	items: [
305	0	Lru::new(RegClass::Int, int_regs),
306	0	Lru::new(RegClass::Float, float_regs),
307	0	Lru::new(RegClass::Vector, vec_regs),
308	0	],
309	0	}
310	0	}
311		}
312
313		use core::fmt::{Debug, Display};
314
315		impl<T: Display> Display for PartedByRegClass<T> {
316	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
317	0	write!(
318	0	f,
319	0	"{{ int: {}, float: {}, vector: {} }}",
320	0	self.items[0], self.items[1], self.items[2]
321		)
322	0	}
323		}
324
325		impl<T: Debug> Debug for PartedByRegClass<T> {
326	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
327	0	write!(
328	0	f,
329	0	"{{ int: {:?}, float: {:?}, vector: {:?} }}",
330	0	self.items[0], self.items[1], self.items[2]
331		)
332	0	}
333		}