regalloc2/ion/
reg_traversal.rs

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

regalloc2/ion/
reg_traversal.rs
