lib/CodeGen/TargetRegisterInfo.cpp

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