MCRegisterInfo.h revision bed23081860275c79137f65d592920e7991b8198
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 23namespace llvm { 24 25/// An unsigned integer type large enough to represent all physical registers, 26/// but not necessarily virtual registers. 27typedef uint16_t MCPhysReg; 28 29/// MCRegisterClass - Base class of TargetRegisterClass. 30class MCRegisterClass { 31public: 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 information about a particular 103/// register. The SubRegs field is a zero terminated array of registers that 104/// are sub-registers of the specific register, e.g. AL, AH are sub-registers 105/// of AX. The SuperRegs field is a zero terminated array of registers that are 106/// super-registers of the specific register, e.g. RAX, EAX, are 107/// super-registers of AX. 108/// 109struct MCRegisterDesc { 110 uint32_t Name; // Printable name for the reg (for debugging) 111 uint32_t SubRegs; // Sub-register set, described above 112 uint32_t SuperRegs; // Super-register set, described above 113 114 // Offset into MCRI::SubRegIndices of a list of sub-register indices for each 115 // sub-register in SubRegs. 116 uint32_t SubRegIndices; 117 118 // RegUnits - Points to the list of register units. The low 4 bits holds the 119 // Scale, the high bits hold an offset into DiffLists. See MCRegUnitIterator. 120 uint32_t RegUnits; 121}; 122 123/// MCRegisterInfo base class - We assume that the target defines a static 124/// array of MCRegisterDesc objects that represent all of the machine 125/// registers that the target has. As such, we simply have to track a pointer 126/// to this array so that we can turn register number into a register 127/// descriptor. 128/// 129/// Note this class is designed to be a base class of TargetRegisterInfo, which 130/// is the interface used by codegen. However, specific targets *should never* 131/// specialize this class. MCRegisterInfo should only contain getters to access 132/// TableGen generated physical register data. It must not be extended with 133/// virtual methods. 134/// 135class MCRegisterInfo { 136public: 137 typedef const MCRegisterClass *regclass_iterator; 138 139 /// DwarfLLVMRegPair - Emitted by tablegen so Dwarf<->LLVM reg mappings can be 140 /// performed with a binary search. 141 struct DwarfLLVMRegPair { 142 unsigned FromReg; 143 unsigned ToReg; 144 145 bool operator<(DwarfLLVMRegPair RHS) const { return FromReg < RHS.FromReg; } 146 }; 147 148 /// SubRegCoveredBits - Emitted by tablegen: bit range covered by a subreg 149 /// index, -1 in any being invalid. 150 struct SubRegCoveredBits { 151 uint16_t Offset; 152 uint16_t Size; 153 }; 154private: 155 const MCRegisterDesc *Desc; // Pointer to the descriptor array 156 unsigned NumRegs; // Number of entries in the array 157 unsigned RAReg; // Return address register 158 unsigned PCReg; // Program counter register 159 const MCRegisterClass *Classes; // Pointer to the regclass array 160 unsigned NumClasses; // Number of entries in the array 161 unsigned NumRegUnits; // Number of regunits. 162 const uint16_t (*RegUnitRoots)[2]; // Pointer to regunit root table. 163 const MCPhysReg *DiffLists; // Pointer to the difflists array 164 const char *RegStrings; // Pointer to the string table. 165 const uint16_t *SubRegIndices; // Pointer to the subreg lookup 166 // array. 167 const SubRegCoveredBits *SubRegIdxRanges; // Pointer to the subreg covered 168 // bit ranges array. 169 unsigned NumSubRegIndices; // Number of subreg indices. 170 const uint16_t *RegEncodingTable; // Pointer to array of register 171 // encodings. 172 173 unsigned L2DwarfRegsSize; 174 unsigned EHL2DwarfRegsSize; 175 unsigned Dwarf2LRegsSize; 176 unsigned EHDwarf2LRegsSize; 177 const DwarfLLVMRegPair *L2DwarfRegs; // LLVM to Dwarf regs mapping 178 const DwarfLLVMRegPair *EHL2DwarfRegs; // LLVM to Dwarf regs mapping EH 179 const DwarfLLVMRegPair *Dwarf2LRegs; // Dwarf to LLVM regs mapping 180 const DwarfLLVMRegPair *EHDwarf2LRegs; // Dwarf to LLVM regs mapping EH 181 DenseMap<unsigned, int> L2SEHRegs; // LLVM to SEH regs mapping 182 183public: 184 /// DiffListIterator - Base iterator class that can traverse the 185 /// differentially encoded register and regunit lists in DiffLists. 186 /// Don't use this class directly, use one of the specialized sub-classes 187 /// defined below. 188 class DiffListIterator { 189 uint16_t Val; 190 const MCPhysReg *List; 191 192 protected: 193 /// Create an invalid iterator. Call init() to point to something useful. 194 DiffListIterator() : Val(0), List(0) {} 195 196 /// init - Point the iterator to InitVal, decoding subsequent values from 197 /// DiffList. The iterator will initially point to InitVal, sub-classes are 198 /// responsible for skipping the seed value if it is not part of the list. 199 void init(MCPhysReg InitVal, const MCPhysReg *DiffList) { 200 Val = InitVal; 201 List = DiffList; 202 } 203 204 /// advance - Move to the next list position, return the applied 205 /// differential. This function does not detect the end of the list, that 206 /// is the caller's responsibility (by checking for a 0 return value). 207 unsigned advance() { 208 assert(isValid() && "Cannot move off the end of the list."); 209 MCPhysReg D = *List++; 210 Val += D; 211 return D; 212 } 213 214 public: 215 216 /// isValid - returns true if this iterator is not yet at the end. 217 bool isValid() const { return List; } 218 219 /// Dereference the iterator to get the value at the current position. 220 unsigned operator*() const { return Val; } 221 222 /// Pre-increment to move to the next position. 223 void operator++() { 224 // The end of the list is encoded as a 0 differential. 225 if (!advance()) 226 List = 0; 227 } 228 }; 229 230 // These iterators are allowed to sub-class DiffListIterator and access 231 // internal list pointers. 232 friend class MCSubRegIterator; 233 friend class MCSuperRegIterator; 234 friend class MCRegUnitIterator; 235 friend class MCRegUnitRootIterator; 236 237 /// \brief Initialize MCRegisterInfo, called by TableGen 238 /// auto-generated routines. *DO NOT USE*. 239 void InitMCRegisterInfo(const MCRegisterDesc *D, unsigned NR, unsigned RA, 240 unsigned PC, 241 const MCRegisterClass *C, unsigned NC, 242 const uint16_t (*RURoots)[2], 243 unsigned NRU, 244 const MCPhysReg *DL, 245 const char *Strings, 246 const uint16_t *SubIndices, 247 unsigned NumIndices, 248 const SubRegCoveredBits *SubIdxRanges, 249 const uint16_t *RET) { 250 Desc = D; 251 NumRegs = NR; 252 RAReg = RA; 253 PCReg = PC; 254 Classes = C; 255 DiffLists = DL; 256 RegStrings = Strings; 257 NumClasses = NC; 258 RegUnitRoots = RURoots; 259 NumRegUnits = NRU; 260 SubRegIndices = SubIndices; 261 NumSubRegIndices = NumIndices; 262 SubRegIdxRanges = SubIdxRanges; 263 RegEncodingTable = RET; 264 } 265 266 /// \brief Used to initialize LLVM register to Dwarf 267 /// register number mapping. Called by TableGen auto-generated routines. 268 /// *DO NOT USE*. 269 void mapLLVMRegsToDwarfRegs(const DwarfLLVMRegPair *Map, unsigned Size, 270 bool isEH) { 271 if (isEH) { 272 EHL2DwarfRegs = Map; 273 EHL2DwarfRegsSize = Size; 274 } else { 275 L2DwarfRegs = Map; 276 L2DwarfRegsSize = Size; 277 } 278 } 279 280 /// \brief Used to initialize Dwarf register to LLVM 281 /// register number mapping. Called by TableGen auto-generated routines. 282 /// *DO NOT USE*. 283 void mapDwarfRegsToLLVMRegs(const DwarfLLVMRegPair *Map, unsigned Size, 284 bool isEH) { 285 if (isEH) { 286 EHDwarf2LRegs = Map; 287 EHDwarf2LRegsSize = Size; 288 } else { 289 Dwarf2LRegs = Map; 290 Dwarf2LRegsSize = Size; 291 } 292 } 293 294 /// mapLLVMRegToSEHReg - Used to initialize LLVM register to SEH register 295 /// number mapping. By default the SEH register number is just the same 296 /// as the LLVM register number. 297 /// FIXME: TableGen these numbers. Currently this requires target specific 298 /// initialization code. 299 void mapLLVMRegToSEHReg(unsigned LLVMReg, int SEHReg) { 300 L2SEHRegs[LLVMReg] = SEHReg; 301 } 302 303 /// \brief This method should return the register where the return 304 /// address can be found. 305 unsigned getRARegister() const { 306 return RAReg; 307 } 308 309 /// Return the register which is the program counter. 310 unsigned getProgramCounter() const { 311 return PCReg; 312 } 313 314 const MCRegisterDesc &operator[](unsigned RegNo) const { 315 assert(RegNo < NumRegs && 316 "Attempting to access record for invalid register number!"); 317 return Desc[RegNo]; 318 } 319 320 /// \brief Provide a get method, equivalent to [], but more useful with a 321 /// pointer to this object. 322 const MCRegisterDesc &get(unsigned RegNo) const { 323 return operator[](RegNo); 324 } 325 326 /// \brief Returns the physical register number of sub-register "Index" 327 /// for physical register RegNo. Return zero if the sub-register does not 328 /// exist. 329 unsigned getSubReg(unsigned Reg, unsigned Idx) const; 330 331 /// \brief Return a super-register of the specified register 332 /// Reg so its sub-register of index SubIdx is Reg. 333 unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx, 334 const MCRegisterClass *RC) const; 335 336 /// \brief For a given register pair, return the sub-register index 337 /// if the second register is a sub-register of the first. Return zero 338 /// otherwise. 339 unsigned getSubRegIndex(unsigned RegNo, unsigned SubRegNo) const; 340 341 /// \brief Get the bit range covered by a given sub-register index. 342 /// In some cases, for instance non-contiguous synthesized indices, 343 /// there is no meaningful bit range to get, so return true if \p Offset 344 /// and \p Size were set. 345 bool getSubRegIdxCoveredBits(unsigned Idx, 346 unsigned &Offset, unsigned &Size) const; 347 348 /// \brief Return the human-readable symbolic target-specific name for the 349 /// specified physical register. 350 const char *getName(unsigned RegNo) const { 351 return RegStrings + get(RegNo).Name; 352 } 353 354 /// \brief Return the number of registers this target has (useful for 355 /// sizing arrays holding per register information) 356 unsigned getNumRegs() const { 357 return NumRegs; 358 } 359 360 /// \brief Return the number of sub-register indices 361 /// understood by the target. Index 0 is reserved for the no-op sub-register, 362 /// while 1 to getNumSubRegIndices() - 1 represent real sub-registers. 363 unsigned getNumSubRegIndices() const { 364 return NumSubRegIndices; 365 } 366 367 /// \brief Return the number of (native) register units in the 368 /// target. Register units are numbered from 0 to getNumRegUnits() - 1. They 369 /// can be accessed through MCRegUnitIterator defined below. 370 unsigned getNumRegUnits() const { 371 return NumRegUnits; 372 } 373 374 /// \brief Map a target register to an equivalent dwarf register 375 /// number. Returns -1 if there is no equivalent value. The second 376 /// parameter allows targets to use different numberings for EH info and 377 /// debugging info. 378 int getDwarfRegNum(unsigned RegNum, bool isEH) const; 379 380 /// \brief Map a dwarf register back to a target register. 381 int getLLVMRegNum(unsigned RegNum, bool isEH) const; 382 383 /// \brief Map a target register to an equivalent SEH register 384 /// number. Returns LLVM register number if there is no equivalent value. 385 int getSEHRegNum(unsigned RegNum) const; 386 387 regclass_iterator regclass_begin() const { return Classes; } 388 regclass_iterator regclass_end() const { return Classes+NumClasses; } 389 390 unsigned getNumRegClasses() const { 391 return (unsigned)(regclass_end()-regclass_begin()); 392 } 393 394 /// \brief Returns the register class associated with the enumeration 395 /// value. See class MCOperandInfo. 396 const MCRegisterClass& getRegClass(unsigned i) const { 397 assert(i < getNumRegClasses() && "Register Class ID out of range"); 398 return Classes[i]; 399 } 400 401 /// \brief Returns the encoding for RegNo 402 uint16_t getEncodingValue(unsigned RegNo) const { 403 assert(RegNo < NumRegs && 404 "Attempting to get encoding for invalid register number!"); 405 return RegEncodingTable[RegNo]; 406 } 407 408 /// \brief Returns true if RegB is a sub-register of RegA. 409 bool isSubRegister(unsigned RegA, unsigned RegB) const { 410 return isSuperRegister(RegB, RegA); 411 } 412 413 /// \brief Returns true if RegB is a super-register of RegA. 414 bool isSuperRegister(unsigned RegA, unsigned RegB) const; 415 416 /// \brief Returns true if RegB is a sub-register of RegA or if RegB == RegA. 417 bool isSubRegisterEq(unsigned RegA, unsigned RegB) const { 418 return isSuperRegisterEq(RegB, RegA); 419 } 420 421 /// \brief Returns true if RegB is a super-register of RegA or if 422 /// RegB == RegA. 423 bool isSuperRegisterEq(unsigned RegA, unsigned RegB) const { 424 return RegA == RegB || isSuperRegister(RegA, RegB); 425 } 426 427}; 428 429//===----------------------------------------------------------------------===// 430// Register List Iterators 431//===----------------------------------------------------------------------===// 432 433// MCRegisterInfo provides lists of super-registers, sub-registers, and 434// aliasing registers. Use these iterator classes to traverse the lists. 435 436/// MCSubRegIterator enumerates all sub-registers of Reg. 437/// If IncludeSelf is set, Reg itself is included in the list. 438class MCSubRegIterator : public MCRegisterInfo::DiffListIterator { 439public: 440 MCSubRegIterator(unsigned Reg, const MCRegisterInfo *MCRI, 441 bool IncludeSelf = false) { 442 init(Reg, MCRI->DiffLists + MCRI->get(Reg).SubRegs); 443 // Initially, the iterator points to Reg itself. 444 if (!IncludeSelf) 445 ++*this; 446 } 447}; 448 449/// MCSuperRegIterator enumerates all super-registers of Reg. 450/// If IncludeSelf is set, Reg itself is included in the list. 451class MCSuperRegIterator : public MCRegisterInfo::DiffListIterator { 452public: 453 MCSuperRegIterator() {} 454 MCSuperRegIterator(unsigned Reg, const MCRegisterInfo *MCRI, 455 bool IncludeSelf = false) { 456 init(Reg, MCRI->DiffLists + MCRI->get(Reg).SuperRegs); 457 // Initially, the iterator points to Reg itself. 458 if (!IncludeSelf) 459 ++*this; 460 } 461}; 462 463// Definition for isSuperRegister. Put it down here since it needs the 464// iterator defined above in addition to the MCRegisterInfo class itself. 465inline bool MCRegisterInfo::isSuperRegister(unsigned RegA, unsigned RegB) const{ 466 for (MCSuperRegIterator I(RegA, this); I.isValid(); ++I) 467 if (*I == RegB) 468 return true; 469 return false; 470} 471 472//===----------------------------------------------------------------------===// 473// Register Units 474//===----------------------------------------------------------------------===// 475 476// Register units are used to compute register aliasing. Every register has at 477// least one register unit, but it can have more. Two registers overlap if and 478// only if they have a common register unit. 479// 480// A target with a complicated sub-register structure will typically have many 481// fewer register units than actual registers. MCRI::getNumRegUnits() returns 482// the number of register units in the target. 483 484// MCRegUnitIterator enumerates a list of register units for Reg. The list is 485// in ascending numerical order. 486class MCRegUnitIterator : public MCRegisterInfo::DiffListIterator { 487public: 488 /// MCRegUnitIterator - Create an iterator that traverses the register units 489 /// in Reg. 490 MCRegUnitIterator() {} 491 MCRegUnitIterator(unsigned Reg, const MCRegisterInfo *MCRI) { 492 assert(Reg && "Null register has no regunits"); 493 // Decode the RegUnits MCRegisterDesc field. 494 unsigned RU = MCRI->get(Reg).RegUnits; 495 unsigned Scale = RU & 15; 496 unsigned Offset = RU >> 4; 497 498 // Initialize the iterator to Reg * Scale, and the List pointer to 499 // DiffLists + Offset. 500 init(Reg * Scale, MCRI->DiffLists + Offset); 501 502 // That may not be a valid unit, we need to advance by one to get the real 503 // unit number. The first differential can be 0 which would normally 504 // terminate the list, but since we know every register has at least one 505 // unit, we can allow a 0 differential here. 506 advance(); 507 } 508}; 509 510// Each register unit has one or two root registers. The complete set of 511// registers containing a register unit is the union of the roots and their 512// super-registers. All registers aliasing Unit can be visited like this: 513// 514// for (MCRegUnitRootIterator RI(Unit, MCRI); RI.isValid(); ++RI) { 515// for (MCSuperRegIterator SI(*RI, MCRI, true); SI.isValid(); ++SI) 516// visit(*SI); 517// } 518 519/// MCRegUnitRootIterator enumerates the root registers of a register unit. 520class MCRegUnitRootIterator { 521 uint16_t Reg0; 522 uint16_t Reg1; 523public: 524 MCRegUnitRootIterator() : Reg0(0), Reg1(0) {} 525 MCRegUnitRootIterator(unsigned RegUnit, const MCRegisterInfo *MCRI) { 526 assert(RegUnit < MCRI->getNumRegUnits() && "Invalid register unit"); 527 Reg0 = MCRI->RegUnitRoots[RegUnit][0]; 528 Reg1 = MCRI->RegUnitRoots[RegUnit][1]; 529 } 530 531 /// \brief Dereference to get the current root register. 532 unsigned operator*() const { 533 return Reg0; 534 } 535 536 /// \brief Check if the iterator is at the end of the list. 537 bool isValid() const { 538 return Reg0; 539 } 540 541 /// \brief Preincrement to move to the next root register. 542 void operator++() { 543 assert(isValid() && "Cannot move off the end of the list."); 544 Reg0 = Reg1; 545 Reg1 = 0; 546 } 547}; 548 549/// MCRegAliasIterator enumerates all registers aliasing Reg. If IncludeSelf is 550/// set, Reg itself is included in the list. This iterator does not guarantee 551/// any ordering or that entries are unique. 552class MCRegAliasIterator { 553private: 554 unsigned Reg; 555 const MCRegisterInfo *MCRI; 556 bool IncludeSelf; 557 558 MCRegUnitIterator RI; 559 MCRegUnitRootIterator RRI; 560 MCSuperRegIterator SI; 561public: 562 MCRegAliasIterator(unsigned Reg, const MCRegisterInfo *MCRI, 563 bool IncludeSelf) 564 : Reg(Reg), MCRI(MCRI), IncludeSelf(IncludeSelf) { 565 566 // Initialize the iterators. 567 for (RI = MCRegUnitIterator(Reg, MCRI); RI.isValid(); ++RI) { 568 for (RRI = MCRegUnitRootIterator(*RI, MCRI); RRI.isValid(); ++RRI) { 569 for (SI = MCSuperRegIterator(*RRI, MCRI, true); SI.isValid(); ++SI) { 570 if (!(!IncludeSelf && Reg == *SI)) 571 return; 572 } 573 } 574 } 575 } 576 577 bool isValid() const { 578 return RI.isValid(); 579 } 580 581 unsigned operator*() const { 582 assert (SI.isValid() && "Cannot dereference an invalid iterator."); 583 return *SI; 584 } 585 586 void advance() { 587 // Assuming SI is valid. 588 ++SI; 589 if (SI.isValid()) return; 590 591 ++RRI; 592 if (RRI.isValid()) { 593 SI = MCSuperRegIterator(*RRI, MCRI, true); 594 return; 595 } 596 597 ++RI; 598 if (RI.isValid()) { 599 RRI = MCRegUnitRootIterator(*RI, MCRI); 600 SI = MCSuperRegIterator(*RRI, MCRI, true); 601 } 602 } 603 604 void operator++() { 605 assert(isValid() && "Cannot move off the end of the list."); 606 do advance(); 607 while (!IncludeSelf && isValid() && *SI == Reg); 608 } 609}; 610 611} // End llvm namespace 612 613#endif 614