1 use cranelift_codegen_shared::constants;
2 use cranelift_entity::{entity_impl, EntityRef, PrimaryMap};
3 
4 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
5 pub(crate) struct RegBankIndex(u32);
6 entity_impl!(RegBankIndex);
7 
8 pub(crate) struct RegBank {
9     pub name: &'static str,
10     pub first_unit: u8,
11     pub units: u8,
12     pub names: Vec<&'static str>,
13     pub prefix: &'static str,
14     pub pressure_tracking: bool,
15     pub pinned_reg: Option<u16>,
16     pub toprcs: Vec<RegClassIndex>,
17     pub classes: Vec<RegClassIndex>,
18 }
19 
20 impl RegBank {
new( name: &'static str, first_unit: u8, units: u8, names: Vec<&'static str>, prefix: &'static str, pressure_tracking: bool, pinned_reg: Option<u16>, ) -> Self21     pub fn new(
22         name: &'static str,
23         first_unit: u8,
24         units: u8,
25         names: Vec<&'static str>,
26         prefix: &'static str,
27         pressure_tracking: bool,
28         pinned_reg: Option<u16>,
29     ) -> Self {
30         RegBank {
31             name,
32             first_unit,
33             units,
34             names,
35             prefix,
36             pressure_tracking,
37             pinned_reg,
38             toprcs: Vec::new(),
39             classes: Vec::new(),
40         }
41     }
42 
unit_by_name(&self, name: &'static str) -> u843     fn unit_by_name(&self, name: &'static str) -> u8 {
44         let unit = if let Some(found) = self.names.iter().position(|&reg_name| reg_name == name) {
45             found
46         } else {
47             // Try to match without the bank prefix.
48             assert!(name.starts_with(self.prefix));
49             let name_without_prefix = &name[self.prefix.len()..];
50             if let Some(found) = self
51                 .names
52                 .iter()
53                 .position(|&reg_name| reg_name == name_without_prefix)
54             {
55                 found
56             } else {
57                 // Ultimate try: try to parse a number and use this in the array, eg r15 on x86.
58                 if let Ok(as_num) = name_without_prefix.parse::<u8>() {
59                     assert!(
60                         as_num < self.units,
61                         "trying to get {}, but bank only has {} registers!",
62                         name,
63                         self.units
64                     );
65                     as_num as usize
66                 } else {
67                     panic!("invalid register name {}", name);
68                 }
69             }
70         };
71         self.first_unit + (unit as u8)
72     }
73 }
74 
75 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
76 pub(crate) struct RegClassIndex(u32);
77 entity_impl!(RegClassIndex);
78 
79 pub(crate) struct RegClass {
80     pub name: &'static str,
81     pub index: RegClassIndex,
82     pub width: u8,
83     pub bank: RegBankIndex,
84     pub toprc: RegClassIndex,
85     pub count: u8,
86     pub start: u8,
87     pub subclasses: Vec<RegClassIndex>,
88 }
89 
90 impl RegClass {
new( name: &'static str, index: RegClassIndex, width: u8, bank: RegBankIndex, toprc: RegClassIndex, count: u8, start: u8, ) -> Self91     pub fn new(
92         name: &'static str,
93         index: RegClassIndex,
94         width: u8,
95         bank: RegBankIndex,
96         toprc: RegClassIndex,
97         count: u8,
98         start: u8,
99     ) -> Self {
100         Self {
101             name,
102             index,
103             width,
104             bank,
105             toprc,
106             count,
107             start,
108             subclasses: Vec::new(),
109         }
110     }
111 
112     /// Compute a bit-mask of subclasses, including self.
subclass_mask(&self) -> u64113     pub fn subclass_mask(&self) -> u64 {
114         let mut m = 1 << self.index.index();
115         for rc in self.subclasses.iter() {
116             m |= 1 << rc.index();
117         }
118         m
119     }
120 
121     /// Compute a bit-mask of the register units allocated by this register class.
mask(&self, bank_first_unit: u8) -> Vec<u32>122     pub fn mask(&self, bank_first_unit: u8) -> Vec<u32> {
123         let mut u = (self.start + bank_first_unit) as usize;
124         let mut out_mask = vec![0, 0, 0];
125         for _ in 0..self.count {
126             out_mask[u / 32] |= 1 << (u % 32);
127             u += self.width as usize;
128         }
129         out_mask
130     }
131 }
132 
133 pub(crate) enum RegClassProto {
134     TopLevel(RegBankIndex),
135     SubClass(RegClassIndex),
136 }
137 
138 pub(crate) struct RegClassBuilder {
139     pub name: &'static str,
140     pub width: u8,
141     pub count: u8,
142     pub start: u8,
143     pub proto: RegClassProto,
144 }
145 
146 impl RegClassBuilder {
new_toplevel(name: &'static str, bank: RegBankIndex) -> Self147     pub fn new_toplevel(name: &'static str, bank: RegBankIndex) -> Self {
148         Self {
149             name,
150             width: 1,
151             count: 0,
152             start: 0,
153             proto: RegClassProto::TopLevel(bank),
154         }
155     }
subclass_of( name: &'static str, parent_index: RegClassIndex, start: u8, stop: u8, ) -> Self156     pub fn subclass_of(
157         name: &'static str,
158         parent_index: RegClassIndex,
159         start: u8,
160         stop: u8,
161     ) -> Self {
162         assert!(stop >= start);
163         Self {
164             name,
165             width: 0,
166             count: stop - start,
167             start,
168             proto: RegClassProto::SubClass(parent_index),
169         }
170     }
count(mut self, count: u8) -> Self171     pub fn count(mut self, count: u8) -> Self {
172         self.count = count;
173         self
174     }
width(mut self, width: u8) -> Self175     pub fn width(mut self, width: u8) -> Self {
176         match self.proto {
177             RegClassProto::TopLevel(_) => self.width = width,
178             RegClassProto::SubClass(_) => panic!("Subclasses inherit their parent's width."),
179         }
180         self
181     }
182 }
183 
184 pub(crate) struct RegBankBuilder {
185     pub name: &'static str,
186     pub units: u8,
187     pub names: Vec<&'static str>,
188     pub prefix: &'static str,
189     pub pressure_tracking: Option<bool>,
190     pub pinned_reg: Option<u16>,
191 }
192 
193 impl RegBankBuilder {
new(name: &'static str, prefix: &'static str) -> Self194     pub fn new(name: &'static str, prefix: &'static str) -> Self {
195         Self {
196             name,
197             units: 0,
198             names: vec![],
199             prefix,
200             pressure_tracking: None,
201             pinned_reg: None,
202         }
203     }
units(mut self, units: u8) -> Self204     pub fn units(mut self, units: u8) -> Self {
205         self.units = units;
206         self
207     }
names(mut self, names: Vec<&'static str>) -> Self208     pub fn names(mut self, names: Vec<&'static str>) -> Self {
209         self.names = names;
210         self
211     }
track_pressure(mut self, track: bool) -> Self212     pub fn track_pressure(mut self, track: bool) -> Self {
213         self.pressure_tracking = Some(track);
214         self
215     }
pinned_reg(mut self, unit: u16) -> Self216     pub fn pinned_reg(mut self, unit: u16) -> Self {
217         assert!(unit < u16::from(self.units));
218         self.pinned_reg = Some(unit);
219         self
220     }
221 }
222 
223 pub(crate) struct IsaRegsBuilder {
224     pub banks: PrimaryMap<RegBankIndex, RegBank>,
225     pub classes: PrimaryMap<RegClassIndex, RegClass>,
226 }
227 
228 impl IsaRegsBuilder {
new() -> Self229     pub fn new() -> Self {
230         Self {
231             banks: PrimaryMap::new(),
232             classes: PrimaryMap::new(),
233         }
234     }
235 
add_bank(&mut self, builder: RegBankBuilder) -> RegBankIndex236     pub fn add_bank(&mut self, builder: RegBankBuilder) -> RegBankIndex {
237         let first_unit = if self.banks.is_empty() {
238             0
239         } else {
240             let last = &self.banks.last().unwrap();
241             let first_available_unit = (last.first_unit + last.units) as i8;
242             let units = builder.units;
243             let align = if units.is_power_of_two() {
244                 units
245             } else {
246                 units.next_power_of_two()
247             } as i8;
248             (first_available_unit + align - 1) & -align
249         } as u8;
250 
251         self.banks.push(RegBank::new(
252             builder.name,
253             first_unit,
254             builder.units,
255             builder.names,
256             builder.prefix,
257             builder
258                 .pressure_tracking
259                 .expect("Pressure tracking must be explicitly set"),
260             builder.pinned_reg,
261         ))
262     }
263 
add_class(&mut self, builder: RegClassBuilder) -> RegClassIndex264     pub fn add_class(&mut self, builder: RegClassBuilder) -> RegClassIndex {
265         let class_index = self.classes.next_key();
266 
267         // Finish delayed construction of RegClass.
268         let (bank, toprc, start, width) = match builder.proto {
269             RegClassProto::TopLevel(bank_index) => {
270                 self.banks
271                     .get_mut(bank_index)
272                     .unwrap()
273                     .toprcs
274                     .push(class_index);
275                 (bank_index, class_index, builder.start, builder.width)
276             }
277             RegClassProto::SubClass(parent_class_index) => {
278                 assert!(builder.width == 0);
279                 let (bank, toprc, start, width) = {
280                     let parent = self.classes.get(parent_class_index).unwrap();
281                     (parent.bank, parent.toprc, parent.start, parent.width)
282                 };
283                 for reg_class in self.classes.values_mut() {
284                     if reg_class.toprc == toprc {
285                         reg_class.subclasses.push(class_index);
286                     }
287                 }
288                 let subclass_start = start + builder.start * width;
289                 (bank, toprc, subclass_start, width)
290             }
291         };
292 
293         let reg_bank_units = self.banks.get(bank).unwrap().units;
294         assert!(start < reg_bank_units);
295 
296         let count = if builder.count != 0 {
297             builder.count
298         } else {
299             reg_bank_units / width
300         };
301 
302         let reg_class = RegClass::new(builder.name, class_index, width, bank, toprc, count, start);
303         self.classes.push(reg_class);
304 
305         let reg_bank = self.banks.get_mut(bank).unwrap();
306         reg_bank.classes.push(class_index);
307 
308         class_index
309     }
310 
311     /// Checks that the set of register classes satisfies:
312     ///
313     /// 1. Closed under intersection: The intersection of any two register
314     ///    classes in the set is either empty or identical to a member of the
315     ///    set.
316     /// 2. There are no identical classes under different names.
317     /// 3. Classes are sorted topologically such that all subclasses have a
318     ///    higher index that the superclass.
build(self) -> IsaRegs319     pub fn build(self) -> IsaRegs {
320         for reg_bank in self.banks.values() {
321             for i1 in reg_bank.classes.iter() {
322                 for i2 in reg_bank.classes.iter() {
323                     if i1 >= i2 {
324                         continue;
325                     }
326 
327                     let rc1 = self.classes.get(*i1).unwrap();
328                     let rc2 = self.classes.get(*i2).unwrap();
329 
330                     let rc1_mask = rc1.mask(0);
331                     let rc2_mask = rc2.mask(0);
332 
333                     assert!(
334                         rc1.width != rc2.width || rc1_mask != rc2_mask,
335                         "no duplicates"
336                     );
337                     if rc1.width != rc2.width {
338                         continue;
339                     }
340 
341                     let mut intersect = Vec::new();
342                     for (a, b) in rc1_mask.iter().zip(rc2_mask.iter()) {
343                         intersect.push(a & b);
344                     }
345                     if intersect == vec![0; intersect.len()] {
346                         continue;
347                     }
348 
349                     // Classes must be topologically ordered, so the intersection can't be the
350                     // superclass.
351                     assert!(intersect != rc1_mask);
352 
353                     // If the intersection is the second one, then it must be a subclass.
354                     if intersect == rc2_mask {
355                         assert!(self
356                             .classes
357                             .get(*i1)
358                             .unwrap()
359                             .subclasses
360                             .iter()
361                             .any(|x| *x == *i2));
362                     }
363                 }
364             }
365         }
366 
367         assert!(
368             self.classes.len() <= constants::MAX_NUM_REG_CLASSES,
369             "Too many register classes"
370         );
371 
372         let num_toplevel = self
373             .classes
374             .values()
375             .filter(|x| x.toprc == x.index && self.banks.get(x.bank).unwrap().pressure_tracking)
376             .count();
377 
378         assert!(
379             num_toplevel <= constants::MAX_TRACKED_TOP_RCS,
380             "Too many top-level register classes"
381         );
382 
383         IsaRegs::new(self.banks, self.classes)
384     }
385 }
386 
387 pub(crate) struct IsaRegs {
388     pub banks: PrimaryMap<RegBankIndex, RegBank>,
389     pub classes: PrimaryMap<RegClassIndex, RegClass>,
390 }
391 
392 impl IsaRegs {
new( banks: PrimaryMap<RegBankIndex, RegBank>, classes: PrimaryMap<RegClassIndex, RegClass>, ) -> Self393     fn new(
394         banks: PrimaryMap<RegBankIndex, RegBank>,
395         classes: PrimaryMap<RegClassIndex, RegClass>,
396     ) -> Self {
397         Self { banks, classes }
398     }
399 
class_by_name(&self, name: &str) -> RegClassIndex400     pub fn class_by_name(&self, name: &str) -> RegClassIndex {
401         self.classes
402             .values()
403             .find(|&class| class.name == name)
404             .unwrap_or_else(|| panic!("register class {} not found", name))
405             .index
406     }
407 
regunit_by_name(&self, class_index: RegClassIndex, name: &'static str) -> u8408     pub fn regunit_by_name(&self, class_index: RegClassIndex, name: &'static str) -> u8 {
409         let bank_index = self.classes.get(class_index).unwrap().bank;
410         self.banks.get(bank_index).unwrap().unit_by_name(name)
411     }
412 }
413