1 //=== MC/MCRegisterInfo.h - Target Register Description ---------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file describes an abstract interface used to get information about a 11 // target machines register file. This information is used for a variety of 12 // purposed, especially register allocation. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_MC_MCREGISTERINFO_H 17 #define LLVM_MC_MCREGISTERINFO_H 18 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/Support/ErrorHandling.h" 21 #include <cassert> 22 23 namespace llvm { 24 25 /// An unsigned integer type large enough to represent all physical registers, 26 /// but not necessarily virtual registers. 27 typedef uint16_t MCPhysReg; 28 29 /// MCRegisterClass - Base class of TargetRegisterClass. 30 class MCRegisterClass { 31 public: 32 typedef const MCPhysReg* iterator; 33 typedef const MCPhysReg* const_iterator; 34 35 const char *Name; 36 const iterator RegsBegin; 37 const uint8_t *const RegSet; 38 const uint16_t RegsSize; 39 const uint16_t RegSetSize; 40 const uint16_t ID; 41 const uint16_t RegSize, Alignment; // Size & Alignment of register in bytes 42 const int8_t CopyCost; 43 const bool Allocatable; 44 45 /// getID() - Return the register class ID number. 46 /// 47 unsigned getID() const { return ID; } 48 49 /// getName() - Return the register class name for debugging. 50 /// 51 const char *getName() const { return Name; } 52 53 /// begin/end - Return all of the registers in this class. 54 /// 55 iterator begin() const { return RegsBegin; } 56 iterator end() const { return RegsBegin + RegsSize; } 57 58 /// getNumRegs - Return the number of registers in this class. 59 /// 60 unsigned getNumRegs() const { return RegsSize; } 61 62 /// getRegister - Return the specified register in the class. 63 /// 64 unsigned getRegister(unsigned i) const { 65 assert(i < getNumRegs() && "Register number out of range!"); 66 return RegsBegin[i]; 67 } 68 69 /// contains - Return true if the specified register is included in this 70 /// register class. This does not include virtual registers. 71 bool contains(unsigned Reg) const { 72 unsigned InByte = Reg % 8; 73 unsigned Byte = Reg / 8; 74 if (Byte >= RegSetSize) 75 return false; 76 return (RegSet[Byte] & (1 << InByte)) != 0; 77 } 78 79 /// contains - Return true if both registers are in this class. 80 bool contains(unsigned Reg1, unsigned Reg2) const { 81 return contains(Reg1) && contains(Reg2); 82 } 83 84 /// getSize - Return the size of the register in bytes, which is also the size 85 /// of a stack slot allocated to hold a spilled copy of this register. 86 unsigned getSize() const { return RegSize; } 87 88 /// getAlignment - Return the minimum required alignment for a register of 89 /// this class. 90 unsigned getAlignment() const { return Alignment; } 91 92 /// getCopyCost - Return the cost of copying a value between two registers in 93 /// this class. A negative number means the register class is very expensive 94 /// to copy e.g. status flag register classes. 95 int getCopyCost() const { return CopyCost; } 96 97 /// isAllocatable - Return true if this register class may be used to create 98 /// virtual registers. 99 bool isAllocatable() const { return Allocatable; } 100 }; 101 102 /// MCRegisterDesc - This record contains all of the information known about 103 /// a particular register. The Overlaps field contains a pointer to a zero 104 /// terminated array of registers that this register aliases, starting with 105 /// itself. This is needed for architectures like X86 which have AL alias AX 106 /// alias EAX. The SubRegs field is a zero terminated array of registers that 107 /// are sub-registers of the specific register, e.g. AL, AH are sub-registers of 108 /// AX. The SuperRegs field is a zero terminated array of registers that are 109 /// super-registers of the specific register, e.g. RAX, EAX, are super-registers 110 /// of AX. 111 /// 112 struct MCRegisterDesc { 113 uint32_t Name; // Printable name for the reg (for debugging) 114 uint32_t Overlaps; // Overlapping registers, described above 115 uint32_t SubRegs; // Sub-register set, described above 116 uint32_t SuperRegs; // Super-register set, described above 117 118 // Offset into MCRI::SubRegIndices of a list of sub-register indices for each 119 // sub-register in SubRegs. 120 uint32_t SubRegIndices; 121 122 // RegUnits - Points to the list of register units. The low 4 bits holds the 123 // Scale, the high bits hold an offset into DiffLists. See MCRegUnitIterator. 124 uint32_t RegUnits; 125 }; 126 127 /// MCRegisterInfo base class - We assume that the target defines a static 128 /// array of MCRegisterDesc objects that represent all of the machine 129 /// registers that the target has. As such, we simply have to track a pointer 130 /// to this array so that we can turn register number into a register 131 /// descriptor. 132 /// 133 /// Note this class is designed to be a base class of TargetRegisterInfo, which 134 /// is the interface used by codegen. However, specific targets *should never* 135 /// specialize this class. MCRegisterInfo should only contain getters to access 136 /// TableGen generated physical register data. It must not be extended with 137 /// virtual methods. 138 /// 139 class MCRegisterInfo { 140 public: 141 typedef const MCRegisterClass *regclass_iterator; 142 143 /// DwarfLLVMRegPair - Emitted by tablegen so Dwarf<->LLVM reg mappings can be 144 /// performed with a binary search. 145 struct DwarfLLVMRegPair { 146 unsigned FromReg; 147 unsigned ToReg; 148 149 bool operator<(DwarfLLVMRegPair RHS) const { return FromReg < RHS.FromReg; } 150 }; 151 private: 152 const MCRegisterDesc *Desc; // Pointer to the descriptor array 153 unsigned NumRegs; // Number of entries in the array 154 unsigned RAReg; // Return address register 155 unsigned PCReg; // Program counter register 156 const MCRegisterClass *Classes; // Pointer to the regclass array 157 unsigned NumClasses; // Number of entries in the array 158 unsigned NumRegUnits; // Number of regunits. 159 const uint16_t (*RegUnitRoots)[2]; // Pointer to regunit root table. 160 const MCPhysReg *DiffLists; // Pointer to the difflists array 161 const char *RegStrings; // Pointer to the string table. 162 const uint16_t *SubRegIndices; // Pointer to the subreg lookup 163 // array. 164 unsigned NumSubRegIndices; // Number of subreg indices. 165 const uint16_t *RegEncodingTable; // Pointer to array of register 166 // encodings. 167 168 unsigned L2DwarfRegsSize; 169 unsigned EHL2DwarfRegsSize; 170 unsigned Dwarf2LRegsSize; 171 unsigned EHDwarf2LRegsSize; 172 const DwarfLLVMRegPair *L2DwarfRegs; // LLVM to Dwarf regs mapping 173 const DwarfLLVMRegPair *EHL2DwarfRegs; // LLVM to Dwarf regs mapping EH 174 const DwarfLLVMRegPair *Dwarf2LRegs; // Dwarf to LLVM regs mapping 175 const DwarfLLVMRegPair *EHDwarf2LRegs; // Dwarf to LLVM regs mapping EH 176 DenseMap<unsigned, int> L2SEHRegs; // LLVM to SEH regs mapping 177 178 public: 179 /// DiffListIterator - Base iterator class that can traverse the 180 /// differentially encoded register and regunit lists in DiffLists. 181 /// Don't use this class directly, use one of the specialized sub-classes 182 /// defined below. 183 class DiffListIterator { 184 uint16_t Val; 185 const MCPhysReg *List; 186 187 protected: 188 /// Create an invalid iterator. Call init() to point to something useful. 189 DiffListIterator() : Val(0), List(0) {} 190 191 /// init - Point the iterator to InitVal, decoding subsequent values from 192 /// DiffList. The iterator will initially point to InitVal, sub-classes are 193 /// responsible for skipping the seed value if it is not part of the list. 194 void init(MCPhysReg InitVal, const MCPhysReg *DiffList) { 195 Val = InitVal; 196 List = DiffList; 197 } 198 199 /// advance - Move to the next list position, return the applied 200 /// differential. This function does not detect the end of the list, that 201 /// is the caller's responsibility (by checking for a 0 return value). 202 unsigned advance() { 203 assert(isValid() && "Cannot move off the end of the list."); 204 MCPhysReg D = *List++; 205 Val += D; 206 return D; 207 } 208 209 public: 210 211 /// isValid - returns true if this iterator is not yet at the end. 212 bool isValid() const { return List; } 213 214 /// Dereference the iterator to get the value at the current position. 215 unsigned operator*() const { return Val; } 216 217 /// Pre-increment to move to the next position. 218 void operator++() { 219 // The end of the list is encoded as a 0 differential. 220 if (!advance()) 221 List = 0; 222 } 223 }; 224 225 // These iterators are allowed to sub-class DiffListIterator and access 226 // internal list pointers. 227 friend class MCSubRegIterator; 228 friend class MCSuperRegIterator; 229 friend class MCRegAliasIterator; 230 friend class MCRegUnitIterator; 231 friend class MCRegUnitRootIterator; 232 233 /// \brief Initialize MCRegisterInfo, called by TableGen 234 /// auto-generated routines. *DO NOT USE*. 235 void InitMCRegisterInfo(const MCRegisterDesc *D, unsigned NR, unsigned RA, 236 unsigned PC, 237 const MCRegisterClass *C, unsigned NC, 238 const uint16_t (*RURoots)[2], 239 unsigned NRU, 240 const MCPhysReg *DL, 241 const char *Strings, 242 const uint16_t *SubIndices, 243 unsigned NumIndices, 244 const uint16_t *RET) { 245 Desc = D; 246 NumRegs = NR; 247 RAReg = RA; 248 PCReg = PC; 249 Classes = C; 250 DiffLists = DL; 251 RegStrings = Strings; 252 NumClasses = NC; 253 RegUnitRoots = RURoots; 254 NumRegUnits = NRU; 255 SubRegIndices = SubIndices; 256 NumSubRegIndices = NumIndices; 257 RegEncodingTable = RET; 258 } 259 260 /// \brief Used to initialize LLVM register to Dwarf 261 /// register number mapping. Called by TableGen auto-generated routines. 262 /// *DO NOT USE*. 263 void mapLLVMRegsToDwarfRegs(const DwarfLLVMRegPair *Map, unsigned Size, 264 bool isEH) { 265 if (isEH) { 266 EHL2DwarfRegs = Map; 267 EHL2DwarfRegsSize = Size; 268 } else { 269 L2DwarfRegs = Map; 270 L2DwarfRegsSize = Size; 271 } 272 } 273 274 /// \brief Used to initialize Dwarf register to LLVM 275 /// register number mapping. Called by TableGen auto-generated routines. 276 /// *DO NOT USE*. 277 void mapDwarfRegsToLLVMRegs(const DwarfLLVMRegPair *Map, unsigned Size, 278 bool isEH) { 279 if (isEH) { 280 EHDwarf2LRegs = Map; 281 EHDwarf2LRegsSize = Size; 282 } else { 283 Dwarf2LRegs = Map; 284 Dwarf2LRegsSize = Size; 285 } 286 } 287 288 /// mapLLVMRegToSEHReg - Used to initialize LLVM register to SEH register 289 /// number mapping. By default the SEH register number is just the same 290 /// as the LLVM register number. 291 /// FIXME: TableGen these numbers. Currently this requires target specific 292 /// initialization code. 293 void mapLLVMRegToSEHReg(unsigned LLVMReg, int SEHReg) { 294 L2SEHRegs[LLVMReg] = SEHReg; 295 } 296 297 /// \brief This method should return the register where the return 298 /// address can be found. 299 unsigned getRARegister() const { 300 return RAReg; 301 } 302 303 /// Return the register which is the program counter. 304 unsigned getProgramCounter() const { 305 return PCReg; 306 } 307 308 const MCRegisterDesc &operator[](unsigned RegNo) const { 309 assert(RegNo < NumRegs && 310 "Attempting to access record for invalid register number!"); 311 return Desc[RegNo]; 312 } 313 314 /// \brief Provide a get method, equivalent to [], but more useful with a 315 /// pointer to this object. 316 const MCRegisterDesc &get(unsigned RegNo) const { 317 return operator[](RegNo); 318 } 319 320 /// \brief Returns the physical register number of sub-register "Index" 321 /// for physical register RegNo. Return zero if the sub-register does not 322 /// exist. 323 unsigned getSubReg(unsigned Reg, unsigned Idx) const; 324 325 /// \brief Return a super-register of the specified register 326 /// Reg so its sub-register of index SubIdx is Reg. 327 unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx, 328 const MCRegisterClass *RC) const; 329 330 /// \brief For a given register pair, return the sub-register index 331 /// if the second register is a sub-register of the first. Return zero 332 /// otherwise. 333 unsigned getSubRegIndex(unsigned RegNo, unsigned SubRegNo) const; 334 335 /// \brief Return the human-readable symbolic target-specific name for the 336 /// specified physical register. 337 const char *getName(unsigned RegNo) const { 338 return RegStrings + get(RegNo).Name; 339 } 340 341 /// \brief Return the number of registers this target has (useful for 342 /// sizing arrays holding per register information) 343 unsigned getNumRegs() const { 344 return NumRegs; 345 } 346 347 /// \brief Return the number of sub-register indices 348 /// understood by the target. Index 0 is reserved for the no-op sub-register, 349 /// while 1 to getNumSubRegIndices() - 1 represent real sub-registers. 350 unsigned getNumSubRegIndices() const { 351 return NumSubRegIndices; 352 } 353 354 /// \brief Return the number of (native) register units in the 355 /// target. Register units are numbered from 0 to getNumRegUnits() - 1. They 356 /// can be accessed through MCRegUnitIterator defined below. 357 unsigned getNumRegUnits() const { 358 return NumRegUnits; 359 } 360 361 /// \brief Map a target register to an equivalent dwarf register 362 /// number. Returns -1 if there is no equivalent value. The second 363 /// parameter allows targets to use different numberings for EH info and 364 /// debugging info. 365 int getDwarfRegNum(unsigned RegNum, bool isEH) const; 366 367 /// \brief Map a dwarf register back to a target register. 368 int getLLVMRegNum(unsigned RegNum, bool isEH) const; 369 370 /// \brief Map a target register to an equivalent SEH register 371 /// number. Returns LLVM register number if there is no equivalent value. 372 int getSEHRegNum(unsigned RegNum) const; 373 374 regclass_iterator regclass_begin() const { return Classes; } 375 regclass_iterator regclass_end() const { return Classes+NumClasses; } 376 377 unsigned getNumRegClasses() const { 378 return (unsigned)(regclass_end()-regclass_begin()); 379 } 380 381 /// \brief Returns the register class associated with the enumeration 382 /// value. See class MCOperandInfo. 383 const MCRegisterClass& getRegClass(unsigned i) const { 384 assert(i < getNumRegClasses() && "Register Class ID out of range"); 385 return Classes[i]; 386 } 387 388 /// \brief Returns the encoding for RegNo 389 uint16_t getEncodingValue(unsigned RegNo) const { 390 assert(RegNo < NumRegs && 391 "Attempting to get encoding for invalid register number!"); 392 return RegEncodingTable[RegNo]; 393 } 394 395 /// \brief Returns true if RegB is a sub-register of RegA. 396 bool isSubRegister(unsigned RegA, unsigned RegB) const { 397 return isSuperRegister(RegB, RegA); 398 } 399 400 /// \brief Returns true if RegB is a super-register of RegA. 401 bool isSuperRegister(unsigned RegA, unsigned RegB) const; 402 403 /// \brief Returns true if RegB is a sub-register of RegA or if RegB == RegA. 404 bool isSubRegisterEq(unsigned RegA, unsigned RegB) const { 405 return isSuperRegisterEq(RegB, RegA); 406 } 407 408 /// \brief Returns true if RegB is a super-register of RegA or if 409 /// RegB == RegA. 410 bool isSuperRegisterEq(unsigned RegA, unsigned RegB) const { 411 return RegA == RegB || isSuperRegister(RegA, RegB); 412 } 413 414 }; 415 416 //===----------------------------------------------------------------------===// 417 // Register List Iterators 418 //===----------------------------------------------------------------------===// 419 420 // MCRegisterInfo provides lists of super-registers, sub-registers, and 421 // aliasing registers. Use these iterator classes to traverse the lists. 422 423 /// MCSubRegIterator enumerates all sub-registers of Reg. 424 class MCSubRegIterator : public MCRegisterInfo::DiffListIterator { 425 public: 426 MCSubRegIterator(unsigned Reg, const MCRegisterInfo *MCRI) { 427 init(Reg, MCRI->DiffLists + MCRI->get(Reg).SubRegs); 428 ++*this; 429 } 430 }; 431 432 /// MCSuperRegIterator enumerates all super-registers of Reg. 433 class MCSuperRegIterator : public MCRegisterInfo::DiffListIterator { 434 public: 435 MCSuperRegIterator(unsigned Reg, const MCRegisterInfo *MCRI) { 436 init(Reg, MCRI->DiffLists + MCRI->get(Reg).SuperRegs); 437 ++*this; 438 } 439 }; 440 441 /// MCRegAliasIterator enumerates all registers aliasing Reg. 442 /// If IncludeSelf is set, Reg itself is included in the list. 443 class MCRegAliasIterator : public MCRegisterInfo::DiffListIterator { 444 public: 445 MCRegAliasIterator(unsigned Reg, const MCRegisterInfo *MCRI, 446 bool IncludeSelf) { 447 init(Reg, MCRI->DiffLists + MCRI->get(Reg).Overlaps); 448 // Initially, the iterator points to Reg itself. 449 if (!IncludeSelf) 450 ++*this; 451 } 452 }; 453 454 // Definition for isSuperRegister. Put it down here since it needs the 455 // iterator defined above in addition to the MCRegisterInfo class itself. 456 inline bool MCRegisterInfo::isSuperRegister(unsigned RegA, unsigned RegB) const{ 457 for (MCSuperRegIterator I(RegA, this); I.isValid(); ++I) 458 if (*I == RegB) 459 return true; 460 return false; 461 } 462 463 //===----------------------------------------------------------------------===// 464 // Register Units 465 //===----------------------------------------------------------------------===// 466 467 // Register units are used to compute register aliasing. Every register has at 468 // least one register unit, but it can have more. Two registers overlap if and 469 // only if they have a common register unit. 470 // 471 // A target with a complicated sub-register structure will typically have many 472 // fewer register units than actual registers. MCRI::getNumRegUnits() returns 473 // the number of register units in the target. 474 475 // MCRegUnitIterator enumerates a list of register units for Reg. The list is 476 // in ascending numerical order. 477 class MCRegUnitIterator : public MCRegisterInfo::DiffListIterator { 478 public: 479 /// MCRegUnitIterator - Create an iterator that traverses the register units 480 /// in Reg. 481 MCRegUnitIterator(unsigned Reg, const MCRegisterInfo *MCRI) { 482 assert(Reg && "Null register has no regunits"); 483 // Decode the RegUnits MCRegisterDesc field. 484 unsigned RU = MCRI->get(Reg).RegUnits; 485 unsigned Scale = RU & 15; 486 unsigned Offset = RU >> 4; 487 488 // Initialize the iterator to Reg * Scale, and the List pointer to 489 // DiffLists + Offset. 490 init(Reg * Scale, MCRI->DiffLists + Offset); 491 492 // That may not be a valid unit, we need to advance by one to get the real 493 // unit number. The first differential can be 0 which would normally 494 // terminate the list, but since we know every register has at least one 495 // unit, we can allow a 0 differential here. 496 advance(); 497 } 498 }; 499 500 // Each register unit has one or two root registers. The complete set of 501 // registers containing a register unit is the union of the roots and their 502 // super-registers. All registers aliasing Unit can be visited like this: 503 // 504 // for (MCRegUnitRootIterator RI(Unit, MCRI); RI.isValid(); ++RI) { 505 // unsigned Root = *RI; 506 // visit(Root); 507 // for (MCSuperRegIterator SI(Root, MCRI); SI.isValid(); ++SI) 508 // visit(*SI); 509 // } 510 511 /// MCRegUnitRootIterator enumerates the root registers of a register unit. 512 class MCRegUnitRootIterator { 513 uint16_t Reg0; 514 uint16_t Reg1; 515 public: 516 MCRegUnitRootIterator(unsigned RegUnit, const MCRegisterInfo *MCRI) { 517 assert(RegUnit < MCRI->getNumRegUnits() && "Invalid register unit"); 518 Reg0 = MCRI->RegUnitRoots[RegUnit][0]; 519 Reg1 = MCRI->RegUnitRoots[RegUnit][1]; 520 } 521 522 /// \brief Dereference to get the current root register. 523 unsigned operator*() const { 524 return Reg0; 525 } 526 527 /// \brief Check if the iterator is at the end of the list. 528 bool isValid() const { 529 return Reg0; 530 } 531 532 /// \brief Preincrement to move to the next root register. 533 void operator++() { 534 assert(isValid() && "Cannot move off the end of the list."); 535 Reg0 = Reg1; 536 Reg1 = 0; 537 } 538 }; 539 540 } // End llvm namespace 541 542 #endif 543