regalloc2/ion/
reg_traversal.rs

1use crate::{MachineEnv, PReg, RegClass};
2
3/// This iterator represents a traversal through all allocatable
4/// registers of a given class, in a certain order designed to
5/// minimize allocation contention.
6///
7/// The order in which we try registers is somewhat complex:
8/// - First, if there is a hint, we try that.
9/// - Then, we try registers in a traversal order that is based on an
10///   "offset" (usually the bundle index) spreading pressure evenly
11///   among registers to reduce commitment-map contention.
12/// - Within that scan, we try registers in two groups: first,
13///   prferred registers; then, non-preferred registers. (In normal
14///   usage, these consist of caller-save and callee-save registers
15///   respectively, to minimize clobber-saves; but they need not.)
16
17pub struct RegTraversalIter<'a> {
18    env: &'a MachineEnv,
19    class: usize,
20    hints: [Option<PReg>; 2],
21    hint_idx: usize,
22    pref_idx: usize,
23    non_pref_idx: usize,
24    offset_pref: usize,
25    offset_non_pref: usize,
26    is_fixed: bool,
27    fixed: Option<PReg>,
28}
29
30impl<'a> RegTraversalIter<'a> {
31    pub fn new(
32        env: &'a MachineEnv,
33        class: RegClass,
34        hint_reg: PReg,
35        hint2_reg: PReg,
36        offset: usize,
37        fixed: Option<PReg>,
38    ) -> Self {
39        let mut hint_reg = if hint_reg != PReg::invalid() {
40            Some(hint_reg)
41        } else {
42            None
43        };
44        let mut hint2_reg = if hint2_reg != PReg::invalid() {
45            Some(hint2_reg)
46        } else {
47            None
48        };
49
50        if hint_reg.is_none() {
51            hint_reg = hint2_reg;
52            hint2_reg = None;
53        }
54        let hints = [hint_reg, hint2_reg];
55        let class = class as u8 as usize;
56        let offset_pref = if env.preferred_regs_by_class[class].len() > 0 {
57            offset % env.preferred_regs_by_class[class].len()
58        } else {
59            0
60        };
61        let offset_non_pref = if env.non_preferred_regs_by_class[class].len() > 0 {
62            offset % env.non_preferred_regs_by_class[class].len()
63        } else {
64            0
65        };
66        Self {
67            env,
68            class,
69            hints,
70            hint_idx: 0,
71            pref_idx: 0,
72            non_pref_idx: 0,
73            offset_pref,
74            offset_non_pref,
75            is_fixed: fixed.is_some(),
76            fixed,
77        }
78    }
79}
80
81impl<'a> std::iter::Iterator for RegTraversalIter<'a> {
82    type Item = PReg;
83
84    fn next(&mut self) -> Option<PReg> {
85        if self.is_fixed {
86            let ret = self.fixed;
87            self.fixed = None;
88            return ret;
89        }
90
91        fn wrap(idx: usize, limit: usize) -> usize {
92            if idx >= limit {
93                idx - limit
94            } else {
95                idx
96            }
97        }
98        if self.hint_idx < 2 && self.hints[self.hint_idx].is_some() {
99            let h = self.hints[self.hint_idx];
100            self.hint_idx += 1;
101            return h;
102        }
103        while self.pref_idx < self.env.preferred_regs_by_class[self.class].len() {
104            let arr = &self.env.preferred_regs_by_class[self.class][..];
105            let r = arr[wrap(self.pref_idx + self.offset_pref, arr.len())];
106            self.pref_idx += 1;
107            if Some(r) == self.hints[0] || Some(r) == self.hints[1] {
108                continue;
109            }
110            return Some(r);
111        }
112        while self.non_pref_idx < self.env.non_preferred_regs_by_class[self.class].len() {
113            let arr = &self.env.non_preferred_regs_by_class[self.class][..];
114            let r = arr[wrap(self.non_pref_idx + self.offset_non_pref, arr.len())];
115            self.non_pref_idx += 1;
116            if Some(r) == self.hints[0] || Some(r) == self.hints[1] {
117                continue;
118            }
119            return Some(r);
120        }
121        None
122    }
123}
regalloc2/ion/reg_traversal.rs

regalloc2/ion/
reg_traversal.rs
