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