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