regalloc2/ion/
reg_traversal.rs

1//! Iterate over available registers.
2
3use crate::{MachineEnv, PReg, PRegSet, PRegSetIter, RegClass};
4
5/// Keep track of where we are in the register traversal.
6struct Cursor {
7    first: PRegSetIter,
8    second: PRegSetIter,
9}
10
11impl Cursor {
12    #[inline]
13    fn new(registers: &PRegSet, class: RegClass, offset_hint: usize) -> Self {
14        let mut mask = PRegSet::empty();
15        mask.add_up_to(PReg::new(offset_hint % PReg::MAX, class));
16        let first = *registers & mask.invert();
17        let second = *registers & mask;
18        Self {
19            first: first.into_iter(),
20            second: second.into_iter(),
21        }
22    }
23
24    fn next(&mut self) -> Option<PReg> {
25        self.first.next().or_else(|| self.second.next())
26    }
27}
28
29/// This iterator represents a traversal through all allocatable registers of a
30/// given class, in a certain order designed to minimize allocation contention.
31///
32/// The order in which we try registers is somewhat complex:
33/// - First, if the register is fixed (i.e., pre-assigned), return that and stop
34///   iteration.
35/// - Then, if there is a hint, try that one.
36/// - Next we try registers in a traversal order that is based on an "offset"
37///   (usually the bundle index) spreading pressure evenly among registers to
38///   reduce commitment-map contention.
39/// - Within that scan, we try registers in two groups: first, preferred
40///   registers; then, non-preferred registers. (In normal usage, these consist
41///   of caller-save and callee-save registers respectively, to minimize
42///   clobber-saves; but they need not.)
43pub struct RegTraversalIter {
44    is_fixed: bool,
45    fixed: Option<PReg>,
46    use_hint: bool,
47    hint: Option<PReg>,
48    preferred: Cursor,
49    non_preferred: Cursor,
50    limit: Option<usize>,
51}
52
53impl RegTraversalIter {
54    pub fn new(
55        env: &MachineEnv,
56        class: RegClass,
57        fixed: Option<PReg>,
58        hint: Option<PReg>,
59        offset: usize,
60        limit: Option<usize>,
61    ) -> Self {
62        debug_assert!(fixed != Some(PReg::invalid()));
63        debug_assert!(hint != Some(PReg::invalid()));
64
65        let class_index = class as u8 as usize;
66        let preferred = Cursor::new(&env.preferred_regs_by_class[class_index], class, offset);
67        let non_preferred =
68            Cursor::new(&env.non_preferred_regs_by_class[class_index], class, offset);
69
70        Self {
71            is_fixed: fixed.is_some(),
72            fixed,
73            use_hint: hint.is_some(),
74            hint,
75            preferred,
76            non_preferred,
77            limit,
78        }
79    }
80}
81
82impl core::iter::Iterator for RegTraversalIter {
83    type Item = PReg;
84
85    fn next(&mut self) -> Option<PReg> {
86        if self.is_fixed {
87            return self.fixed.take();
88        }
89
90        if self.use_hint {
91            self.use_hint = false;
92            if self.hint.unwrap().hw_enc() < self.limit.unwrap_or(usize::MAX) {
93                return self.hint;
94            }
95        }
96
97        while let Some(reg) = self.preferred.next() {
98            if Some(reg) == self.hint || reg.hw_enc() >= self.limit.unwrap_or(usize::MAX) {
99                continue; // Try again; we already tried the hint or we are outside of the register range limit.
100            }
101            return Some(reg);
102        }
103
104        while let Some(reg) = self.non_preferred.next() {
105            if Some(reg) == self.hint || reg.hw_enc() >= self.limit.unwrap_or(usize::MAX) {
106                continue; // Try again; we already tried the hint or we are outside of the register range limit.
107            }
108            return Some(reg);
109        }
110
111        None
112    }
113}
regalloc2/ion/reg_traversal.rs

regalloc2/ion/
reg_traversal.rs
