1 //==- TargetRegisterInfo.cpp - Target Register Information Implementation --==// 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 implements the TargetRegisterInfo interface. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/TargetRegisterInfo.h" 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/BitVector.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/StringExtras.h" 19 #include "llvm/CodeGen/MachineFrameInfo.h" 20 #include "llvm/CodeGen/MachineFunction.h" 21 #include "llvm/CodeGen/MachineRegisterInfo.h" 22 #include "llvm/CodeGen/MachineValueType.h" 23 #include "llvm/CodeGen/TargetFrameLowering.h" 24 #include "llvm/CodeGen/TargetSubtargetInfo.h" 25 #include "llvm/CodeGen/VirtRegMap.h" 26 #include "llvm/IR/Attributes.h" 27 #include "llvm/IR/Function.h" 28 #include "llvm/MC/MCRegisterInfo.h" 29 #include "llvm/Support/Compiler.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/MathExtras.h" 32 #include "llvm/Support/Printable.h" 33 #include "llvm/Support/raw_ostream.h" 34 #include <cassert> 35 #include <utility> 36 37 #define DEBUG_TYPE "target-reg-info" 38 39 using namespace llvm; 40 41 TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterInfoDesc *ID, 42 regclass_iterator RCB, regclass_iterator RCE, 43 const char *const *SRINames, 44 const LaneBitmask *SRILaneMasks, 45 LaneBitmask SRICoveringLanes, 46 const RegClassInfo *const RCIs, 47 unsigned Mode) 48 : InfoDesc(ID), SubRegIndexNames(SRINames), 49 SubRegIndexLaneMasks(SRILaneMasks), 50 RegClassBegin(RCB), RegClassEnd(RCE), 51 CoveringLanes(SRICoveringLanes), 52 RCInfos(RCIs), HwMode(Mode) { 53 } 54 55 TargetRegisterInfo::~TargetRegisterInfo() = default; 56 57 void TargetRegisterInfo::markSuperRegs(BitVector &RegisterSet, unsigned Reg) 58 const { 59 for (MCSuperRegIterator AI(Reg, this, true); AI.isValid(); ++AI) 60 RegisterSet.set(*AI); 61 } 62 63 bool TargetRegisterInfo::checkAllSuperRegsMarked(const BitVector &RegisterSet, 64 ArrayRef<MCPhysReg> Exceptions) const { 65 // Check that all super registers of reserved regs are reserved as well. 66 BitVector Checked(getNumRegs()); 67 for (unsigned Reg : RegisterSet.set_bits()) { 68 if (Checked[Reg]) 69 continue; 70 for (MCSuperRegIterator SR(Reg, this); SR.isValid(); ++SR) { 71 if (!RegisterSet[*SR] && !is_contained(Exceptions, Reg)) { 72 dbgs() << "Error: Super register " << printReg(*SR, this) 73 << " of reserved register " << printReg(Reg, this) 74 << " is not reserved.\n"; 75 return false; 76 } 77 78 // We transitively check superregs. So we can remember this for later 79 // to avoid compiletime explosion in deep register hierarchies. 80 Checked.set(*SR); 81 } 82 } 83 return true; 84 } 85 86 namespace llvm { 87 88 Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI, 89 unsigned SubIdx) { 90 return Printable([Reg, TRI, SubIdx](raw_ostream &OS) { 91 if (!Reg) 92 OS << "%noreg"; 93 else if (TargetRegisterInfo::isStackSlot(Reg)) 94 OS << "SS#" << TargetRegisterInfo::stackSlot2Index(Reg); 95 else if (TargetRegisterInfo::isVirtualRegister(Reg)) 96 OS << '%' << TargetRegisterInfo::virtReg2Index(Reg); 97 else if (!TRI) 98 OS << '%' << "physreg" << Reg; 99 else if (Reg < TRI->getNumRegs()) { 100 OS << '%'; 101 printLowerCase(TRI->getName(Reg), OS); 102 } else 103 llvm_unreachable("Register kind is unsupported."); 104 105 if (SubIdx) { 106 if (TRI) 107 OS << ':' << TRI->getSubRegIndexName(SubIdx); 108 else 109 OS << ":sub(" << SubIdx << ')'; 110 } 111 }); 112 } 113 114 Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI) { 115 return Printable([Unit, TRI](raw_ostream &OS) { 116 // Generic printout when TRI is missing. 117 if (!TRI) { 118 OS << "Unit~" << Unit; 119 return; 120 } 121 122 // Check for invalid register units. 123 if (Unit >= TRI->getNumRegUnits()) { 124 OS << "BadUnit~" << Unit; 125 return; 126 } 127 128 // Normal units have at least one root. 129 MCRegUnitRootIterator Roots(Unit, TRI); 130 assert(Roots.isValid() && "Unit has no roots."); 131 OS << TRI->getName(*Roots); 132 for (++Roots; Roots.isValid(); ++Roots) 133 OS << '~' << TRI->getName(*Roots); 134 }); 135 } 136 137 Printable printVRegOrUnit(unsigned Unit, const TargetRegisterInfo *TRI) { 138 return Printable([Unit, TRI](raw_ostream &OS) { 139 if (TRI && TRI->isVirtualRegister(Unit)) { 140 OS << '%' << TargetRegisterInfo::virtReg2Index(Unit); 141 } else { 142 OS << printRegUnit(Unit, TRI); 143 } 144 }); 145 } 146 147 } // end namespace llvm 148 149 /// getAllocatableClass - Return the maximal subclass of the given register 150 /// class that is alloctable, or NULL. 151 const TargetRegisterClass * 152 TargetRegisterInfo::getAllocatableClass(const TargetRegisterClass *RC) const { 153 if (!RC || RC->isAllocatable()) 154 return RC; 155 156 for (BitMaskClassIterator It(RC->getSubClassMask(), *this); It.isValid(); 157 ++It) { 158 const TargetRegisterClass *SubRC = getRegClass(It.getID()); 159 if (SubRC->isAllocatable()) 160 return SubRC; 161 } 162 return nullptr; 163 } 164 165 /// getMinimalPhysRegClass - Returns the Register Class of a physical 166 /// register of the given type, picking the most sub register class of 167 /// the right type that contains this physreg. 168 const TargetRegisterClass * 169 TargetRegisterInfo::getMinimalPhysRegClass(unsigned reg, MVT VT) const { 170 assert(isPhysicalRegister(reg) && "reg must be a physical register"); 171 172 // Pick the most sub register class of the right type that contains 173 // this physreg. 174 const TargetRegisterClass* BestRC = nullptr; 175 for (const TargetRegisterClass* RC : regclasses()) { 176 if ((VT == MVT::Other || isTypeLegalForClass(*RC, VT)) && 177 RC->contains(reg) && (!BestRC || BestRC->hasSubClass(RC))) 178 BestRC = RC; 179 } 180 181 assert(BestRC && "Couldn't find the register class"); 182 return BestRC; 183 } 184 185 /// getAllocatableSetForRC - Toggle the bits that represent allocatable 186 /// registers for the specific register class. 187 static void getAllocatableSetForRC(const MachineFunction &MF, 188 const TargetRegisterClass *RC, BitVector &R){ 189 assert(RC->isAllocatable() && "invalid for nonallocatable sets"); 190 ArrayRef<MCPhysReg> Order = RC->getRawAllocationOrder(MF); 191 for (unsigned i = 0; i != Order.size(); ++i) 192 R.set(Order[i]); 193 } 194 195 BitVector TargetRegisterInfo::getAllocatableSet(const MachineFunction &MF, 196 const TargetRegisterClass *RC) const { 197 BitVector Allocatable(getNumRegs()); 198 if (RC) { 199 // A register class with no allocatable subclass returns an empty set. 200 const TargetRegisterClass *SubClass = getAllocatableClass(RC); 201 if (SubClass) 202 getAllocatableSetForRC(MF, SubClass, Allocatable); 203 } else { 204 for (const TargetRegisterClass *C : regclasses()) 205 if (C->isAllocatable()) 206 getAllocatableSetForRC(MF, C, Allocatable); 207 } 208 209 // Mask out the reserved registers 210 BitVector Reserved = getReservedRegs(MF); 211 Allocatable &= Reserved.flip(); 212 213 return Allocatable; 214 } 215 216 static inline 217 const TargetRegisterClass *firstCommonClass(const uint32_t *A, 218 const uint32_t *B, 219 const TargetRegisterInfo *TRI, 220 const MVT::SimpleValueType SVT = 221 MVT::SimpleValueType::Any) { 222 const MVT VT(SVT); 223 for (unsigned I = 0, E = TRI->getNumRegClasses(); I < E; I += 32) 224 if (unsigned Common = *A++ & *B++) { 225 const TargetRegisterClass *RC = 226 TRI->getRegClass(I + countTrailingZeros(Common)); 227 if (SVT == MVT::SimpleValueType::Any || TRI->isTypeLegalForClass(*RC, VT)) 228 return RC; 229 } 230 return nullptr; 231 } 232 233 const TargetRegisterClass * 234 TargetRegisterInfo::getCommonSubClass(const TargetRegisterClass *A, 235 const TargetRegisterClass *B, 236 const MVT::SimpleValueType SVT) const { 237 // First take care of the trivial cases. 238 if (A == B) 239 return A; 240 if (!A || !B) 241 return nullptr; 242 243 // Register classes are ordered topologically, so the largest common 244 // sub-class it the common sub-class with the smallest ID. 245 return firstCommonClass(A->getSubClassMask(), B->getSubClassMask(), this, SVT); 246 } 247 248 const TargetRegisterClass * 249 TargetRegisterInfo::getMatchingSuperRegClass(const TargetRegisterClass *A, 250 const TargetRegisterClass *B, 251 unsigned Idx) const { 252 assert(A && B && "Missing register class"); 253 assert(Idx && "Bad sub-register index"); 254 255 // Find Idx in the list of super-register indices. 256 for (SuperRegClassIterator RCI(B, this); RCI.isValid(); ++RCI) 257 if (RCI.getSubReg() == Idx) 258 // The bit mask contains all register classes that are projected into B 259 // by Idx. Find a class that is also a sub-class of A. 260 return firstCommonClass(RCI.getMask(), A->getSubClassMask(), this); 261 return nullptr; 262 } 263 264 const TargetRegisterClass *TargetRegisterInfo:: 265 getCommonSuperRegClass(const TargetRegisterClass *RCA, unsigned SubA, 266 const TargetRegisterClass *RCB, unsigned SubB, 267 unsigned &PreA, unsigned &PreB) const { 268 assert(RCA && SubA && RCB && SubB && "Invalid arguments"); 269 270 // Search all pairs of sub-register indices that project into RCA and RCB 271 // respectively. This is quadratic, but usually the sets are very small. On 272 // most targets like X86, there will only be a single sub-register index 273 // (e.g., sub_16bit projecting into GR16). 274 // 275 // The worst case is a register class like DPR on ARM. 276 // We have indices dsub_0..dsub_7 projecting into that class. 277 // 278 // It is very common that one register class is a sub-register of the other. 279 // Arrange for RCA to be the larger register so the answer will be found in 280 // the first iteration. This makes the search linear for the most common 281 // case. 282 const TargetRegisterClass *BestRC = nullptr; 283 unsigned *BestPreA = &PreA; 284 unsigned *BestPreB = &PreB; 285 if (getRegSizeInBits(*RCA) < getRegSizeInBits(*RCB)) { 286 std::swap(RCA, RCB); 287 std::swap(SubA, SubB); 288 std::swap(BestPreA, BestPreB); 289 } 290 291 // Also terminate the search one we have found a register class as small as 292 // RCA. 293 unsigned MinSize = getRegSizeInBits(*RCA); 294 295 for (SuperRegClassIterator IA(RCA, this, true); IA.isValid(); ++IA) { 296 unsigned FinalA = composeSubRegIndices(IA.getSubReg(), SubA); 297 for (SuperRegClassIterator IB(RCB, this, true); IB.isValid(); ++IB) { 298 // Check if a common super-register class exists for this index pair. 299 const TargetRegisterClass *RC = 300 firstCommonClass(IA.getMask(), IB.getMask(), this); 301 if (!RC || getRegSizeInBits(*RC) < MinSize) 302 continue; 303 304 // The indexes must compose identically: PreA+SubA == PreB+SubB. 305 unsigned FinalB = composeSubRegIndices(IB.getSubReg(), SubB); 306 if (FinalA != FinalB) 307 continue; 308 309 // Is RC a better candidate than BestRC? 310 if (BestRC && getRegSizeInBits(*RC) >= getRegSizeInBits(*BestRC)) 311 continue; 312 313 // Yes, RC is the smallest super-register seen so far. 314 BestRC = RC; 315 *BestPreA = IA.getSubReg(); 316 *BestPreB = IB.getSubReg(); 317 318 // Bail early if we reached MinSize. We won't find a better candidate. 319 if (getRegSizeInBits(*BestRC) == MinSize) 320 return BestRC; 321 } 322 } 323 return BestRC; 324 } 325 326 /// \brief Check if the registers defined by the pair (RegisterClass, SubReg) 327 /// share the same register file. 328 static bool shareSameRegisterFile(const TargetRegisterInfo &TRI, 329 const TargetRegisterClass *DefRC, 330 unsigned DefSubReg, 331 const TargetRegisterClass *SrcRC, 332 unsigned SrcSubReg) { 333 // Same register class. 334 if (DefRC == SrcRC) 335 return true; 336 337 // Both operands are sub registers. Check if they share a register class. 338 unsigned SrcIdx, DefIdx; 339 if (SrcSubReg && DefSubReg) { 340 return TRI.getCommonSuperRegClass(SrcRC, SrcSubReg, DefRC, DefSubReg, 341 SrcIdx, DefIdx) != nullptr; 342 } 343 344 // At most one of the register is a sub register, make it Src to avoid 345 // duplicating the test. 346 if (!SrcSubReg) { 347 std::swap(DefSubReg, SrcSubReg); 348 std::swap(DefRC, SrcRC); 349 } 350 351 // One of the register is a sub register, check if we can get a superclass. 352 if (SrcSubReg) 353 return TRI.getMatchingSuperRegClass(SrcRC, DefRC, SrcSubReg) != nullptr; 354 355 // Plain copy. 356 return TRI.getCommonSubClass(DefRC, SrcRC) != nullptr; 357 } 358 359 bool TargetRegisterInfo::shouldRewriteCopySrc(const TargetRegisterClass *DefRC, 360 unsigned DefSubReg, 361 const TargetRegisterClass *SrcRC, 362 unsigned SrcSubReg) const { 363 // If this source does not incur a cross register bank copy, use it. 364 return shareSameRegisterFile(*this, DefRC, DefSubReg, SrcRC, SrcSubReg); 365 } 366 367 // Compute target-independent register allocator hints to help eliminate copies. 368 bool 369 TargetRegisterInfo::getRegAllocationHints(unsigned VirtReg, 370 ArrayRef<MCPhysReg> Order, 371 SmallVectorImpl<MCPhysReg> &Hints, 372 const MachineFunction &MF, 373 const VirtRegMap *VRM, 374 const LiveRegMatrix *Matrix) const { 375 const MachineRegisterInfo &MRI = MF.getRegInfo(); 376 std::pair<unsigned, unsigned> Hint = MRI.getRegAllocationHint(VirtReg); 377 378 // Hints with HintType != 0 were set by target-dependent code. 379 // Such targets must provide their own implementation of 380 // TRI::getRegAllocationHints to interpret those hint types. 381 assert(Hint.first == 0 && "Target must implement TRI::getRegAllocationHints"); 382 383 // Target-independent hints are either a physical or a virtual register. 384 unsigned Phys = Hint.second; 385 if (VRM && isVirtualRegister(Phys)) 386 Phys = VRM->getPhys(Phys); 387 388 // Check that Phys is a valid hint in VirtReg's register class. 389 if (!isPhysicalRegister(Phys)) 390 return false; 391 if (MRI.isReserved(Phys)) 392 return false; 393 // Check that Phys is in the allocation order. We shouldn't heed hints 394 // from VirtReg's register class if they aren't in the allocation order. The 395 // target probably has a reason for removing the register. 396 if (!is_contained(Order, Phys)) 397 return false; 398 399 // All clear, tell the register allocator to prefer this register. 400 Hints.push_back(Phys); 401 return false; 402 } 403 404 bool TargetRegisterInfo::canRealignStack(const MachineFunction &MF) const { 405 return !MF.getFunction()->hasFnAttribute("no-realign-stack"); 406 } 407 408 bool TargetRegisterInfo::needsStackRealignment( 409 const MachineFunction &MF) const { 410 const MachineFrameInfo &MFI = MF.getFrameInfo(); 411 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 412 const Function *F = MF.getFunction(); 413 unsigned StackAlign = TFI->getStackAlignment(); 414 bool requiresRealignment = ((MFI.getMaxAlignment() > StackAlign) || 415 F->hasFnAttribute(Attribute::StackAlignment)); 416 if (MF.getFunction()->hasFnAttribute("stackrealign") || requiresRealignment) { 417 if (canRealignStack(MF)) 418 return true; 419 DEBUG(dbgs() << "Can't realign function's stack: " << F->getName() << "\n"); 420 } 421 return false; 422 } 423 424 bool TargetRegisterInfo::regmaskSubsetEqual(const uint32_t *mask0, 425 const uint32_t *mask1) const { 426 unsigned N = (getNumRegs()+31) / 32; 427 for (unsigned I = 0; I < N; ++I) 428 if ((mask0[I] & mask1[I]) != mask0[I]) 429 return false; 430 return true; 431 } 432 433 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 434 LLVM_DUMP_METHOD 435 void TargetRegisterInfo::dumpReg(unsigned Reg, unsigned SubRegIndex, 436 const TargetRegisterInfo *TRI) { 437 dbgs() << printReg(Reg, TRI, SubRegIndex) << "\n"; 438 } 439 #endif 440