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