regalloc2/fastalloc/
lru.rs

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

regalloc2/fastalloc/
lru.rs
