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(|®_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(|®_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