LLVM  mainline
TargetRegisterInfo.cpp
Go to the documentation of this file.
00001 //===- TargetRegisterInfo.cpp - Target Register Information Implementation ===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the TargetRegisterInfo interface.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/ADT/BitVector.h"
00015 #include "llvm/CodeGen/MachineFrameInfo.h"
00016 #include "llvm/CodeGen/MachineFunction.h"
00017 #include "llvm/CodeGen/MachineRegisterInfo.h"
00018 #include "llvm/CodeGen/VirtRegMap.h"
00019 #include "llvm/IR/Function.h"
00020 #include "llvm/Support/Debug.h"
00021 #include "llvm/Support/Format.h"
00022 #include "llvm/Support/raw_ostream.h"
00023 #include "llvm/Target/TargetFrameLowering.h"
00024 #include "llvm/Target/TargetRegisterInfo.h"
00025 
00026 #define DEBUG_TYPE "target-reg-info"
00027 
00028 using namespace llvm;
00029 
00030 TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterInfoDesc *ID,
00031                              regclass_iterator RCB, regclass_iterator RCE,
00032                              const char *const *SRINames,
00033                              const unsigned *SRILaneMasks,
00034                              unsigned SRICoveringLanes)
00035   : InfoDesc(ID), SubRegIndexNames(SRINames),
00036     SubRegIndexLaneMasks(SRILaneMasks),
00037     RegClassBegin(RCB), RegClassEnd(RCE),
00038     CoveringLanes(SRICoveringLanes) {
00039 }
00040 
00041 TargetRegisterInfo::~TargetRegisterInfo() {}
00042 
00043 namespace llvm {
00044 
00045 Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI,
00046                    unsigned SubIdx) {
00047   return Printable([Reg, TRI, SubIdx](raw_ostream &OS) {
00048     if (!Reg)
00049       OS << "%noreg";
00050     else if (TargetRegisterInfo::isStackSlot(Reg))
00051       OS << "SS#" << TargetRegisterInfo::stackSlot2Index(Reg);
00052     else if (TargetRegisterInfo::isVirtualRegister(Reg))
00053       OS << "%vreg" << TargetRegisterInfo::virtReg2Index(Reg);
00054     else if (TRI && Reg < TRI->getNumRegs())
00055       OS << '%' << TRI->getName(Reg);
00056     else
00057       OS << "%physreg" << Reg;
00058     if (SubIdx) {
00059       if (TRI)
00060         OS << ':' << TRI->getSubRegIndexName(SubIdx);
00061       else
00062         OS << ":sub(" << SubIdx << ')';
00063     }
00064   });
00065 }
00066 
00067 Printable PrintRegUnit(unsigned Unit, const TargetRegisterInfo *TRI) {
00068   return Printable([Unit, TRI](raw_ostream &OS) {
00069     // Generic printout when TRI is missing.
00070     if (!TRI) {
00071       OS << "Unit~" << Unit;
00072       return;
00073     }
00074 
00075     // Check for invalid register units.
00076     if (Unit >= TRI->getNumRegUnits()) {
00077       OS << "BadUnit~" << Unit;
00078       return;
00079     }
00080 
00081     // Normal units have at least one root.
00082     MCRegUnitRootIterator Roots(Unit, TRI);
00083     assert(Roots.isValid() && "Unit has no roots.");
00084     OS << TRI->getName(*Roots);
00085     for (++Roots; Roots.isValid(); ++Roots)
00086       OS << '~' << TRI->getName(*Roots);
00087   });
00088 }
00089 
00090 Printable PrintVRegOrUnit(unsigned Unit, const TargetRegisterInfo *TRI) {
00091   return Printable([Unit, TRI](raw_ostream &OS) {
00092     if (TRI && TRI->isVirtualRegister(Unit)) {
00093       OS << "%vreg" << TargetRegisterInfo::virtReg2Index(Unit);
00094     } else {
00095       OS << PrintRegUnit(Unit, TRI);
00096     }
00097   });
00098 }
00099 
00100 Printable PrintLaneMask(LaneBitmask LaneMask) {
00101   return Printable([LaneMask](raw_ostream &OS) {
00102     OS << format("%08X", LaneMask);
00103   });
00104 }
00105 
00106 } // End of llvm namespace
00107 
00108 /// getAllocatableClass - Return the maximal subclass of the given register
00109 /// class that is alloctable, or NULL.
00110 const TargetRegisterClass *
00111 TargetRegisterInfo::getAllocatableClass(const TargetRegisterClass *RC) const {
00112   if (!RC || RC->isAllocatable())
00113     return RC;
00114 
00115   const unsigned *SubClass = RC->getSubClassMask();
00116   for (unsigned Base = 0, BaseE = getNumRegClasses();
00117        Base < BaseE; Base += 32) {
00118     unsigned Idx = Base;
00119     for (unsigned Mask = *SubClass++; Mask; Mask >>= 1) {
00120       unsigned Offset = countTrailingZeros(Mask);
00121       const TargetRegisterClass *SubRC = getRegClass(Idx + Offset);
00122       if (SubRC->isAllocatable())
00123         return SubRC;
00124       Mask >>= Offset;
00125       Idx += Offset + 1;
00126     }
00127   }
00128   return nullptr;
00129 }
00130 
00131 /// getMinimalPhysRegClass - Returns the Register Class of a physical
00132 /// register of the given type, picking the most sub register class of
00133 /// the right type that contains this physreg.
00134 const TargetRegisterClass *
00135 TargetRegisterInfo::getMinimalPhysRegClass(unsigned reg, MVT VT) const {
00136   assert(isPhysicalRegister(reg) && "reg must be a physical register");
00137 
00138   // Pick the most sub register class of the right type that contains
00139   // this physreg.
00140   const TargetRegisterClass* BestRC = nullptr;
00141   for (regclass_iterator I = regclass_begin(), E = regclass_end(); I != E; ++I){
00142     const TargetRegisterClass* RC = *I;
00143     if ((VT == MVT::Other || RC->hasType(VT)) && RC->contains(reg) &&
00144         (!BestRC || BestRC->hasSubClass(RC)))
00145       BestRC = RC;
00146   }
00147 
00148   assert(BestRC && "Couldn't find the register class");
00149   return BestRC;
00150 }
00151 
00152 /// getAllocatableSetForRC - Toggle the bits that represent allocatable
00153 /// registers for the specific register class.
00154 static void getAllocatableSetForRC(const MachineFunction &MF,
00155                                    const TargetRegisterClass *RC, BitVector &R){
00156   assert(RC->isAllocatable() && "invalid for nonallocatable sets");
00157   ArrayRef<MCPhysReg> Order = RC->getRawAllocationOrder(MF);
00158   for (unsigned i = 0; i != Order.size(); ++i)
00159     R.set(Order[i]);
00160 }
00161 
00162 BitVector TargetRegisterInfo::getAllocatableSet(const MachineFunction &MF,
00163                                           const TargetRegisterClass *RC) const {
00164   BitVector Allocatable(getNumRegs());
00165   if (RC) {
00166     // A register class with no allocatable subclass returns an empty set.
00167     const TargetRegisterClass *SubClass = getAllocatableClass(RC);
00168     if (SubClass)
00169       getAllocatableSetForRC(MF, SubClass, Allocatable);
00170   } else {
00171     for (TargetRegisterInfo::regclass_iterator I = regclass_begin(),
00172          E = regclass_end(); I != E; ++I)
00173       if ((*I)->isAllocatable())
00174         getAllocatableSetForRC(MF, *I, Allocatable);
00175   }
00176 
00177   // Mask out the reserved registers
00178   BitVector Reserved = getReservedRegs(MF);
00179   Allocatable &= Reserved.flip();
00180 
00181   return Allocatable;
00182 }
00183 
00184 static inline
00185 const TargetRegisterClass *firstCommonClass(const uint32_t *A,
00186                                             const uint32_t *B,
00187                                             const TargetRegisterInfo *TRI,
00188                                             const MVT::SimpleValueType SVT =
00189                                             MVT::SimpleValueType::Any) {
00190   const MVT VT(SVT);
00191   for (unsigned I = 0, E = TRI->getNumRegClasses(); I < E; I += 32)
00192     if (unsigned Common = *A++ & *B++) {
00193       const TargetRegisterClass *RC =
00194           TRI->getRegClass(I + countTrailingZeros(Common));
00195       if (SVT == MVT::SimpleValueType::Any || RC->hasType(VT))
00196         return RC;
00197     }
00198   return nullptr;
00199 }
00200 
00201 const TargetRegisterClass *
00202 TargetRegisterInfo::getCommonSubClass(const TargetRegisterClass *A,
00203                                       const TargetRegisterClass *B,
00204                                       const MVT::SimpleValueType SVT) const {
00205   // First take care of the trivial cases.
00206   if (A == B)
00207     return A;
00208   if (!A || !B)
00209     return nullptr;
00210 
00211   // Register classes are ordered topologically, so the largest common
00212   // sub-class it the common sub-class with the smallest ID.
00213   return firstCommonClass(A->getSubClassMask(), B->getSubClassMask(), this, SVT);
00214 }
00215 
00216 const TargetRegisterClass *
00217 TargetRegisterInfo::getMatchingSuperRegClass(const TargetRegisterClass *A,
00218                                              const TargetRegisterClass *B,
00219                                              unsigned Idx) const {
00220   assert(A && B && "Missing register class");
00221   assert(Idx && "Bad sub-register index");
00222 
00223   // Find Idx in the list of super-register indices.
00224   for (SuperRegClassIterator RCI(B, this); RCI.isValid(); ++RCI)
00225     if (RCI.getSubReg() == Idx)
00226       // The bit mask contains all register classes that are projected into B
00227       // by Idx. Find a class that is also a sub-class of A.
00228       return firstCommonClass(RCI.getMask(), A->getSubClassMask(), this);
00229   return nullptr;
00230 }
00231 
00232 const TargetRegisterClass *TargetRegisterInfo::
00233 getCommonSuperRegClass(const TargetRegisterClass *RCA, unsigned SubA,
00234                        const TargetRegisterClass *RCB, unsigned SubB,
00235                        unsigned &PreA, unsigned &PreB) const {
00236   assert(RCA && SubA && RCB && SubB && "Invalid arguments");
00237 
00238   // Search all pairs of sub-register indices that project into RCA and RCB
00239   // respectively. This is quadratic, but usually the sets are very small. On
00240   // most targets like X86, there will only be a single sub-register index
00241   // (e.g., sub_16bit projecting into GR16).
00242   //
00243   // The worst case is a register class like DPR on ARM.
00244   // We have indices dsub_0..dsub_7 projecting into that class.
00245   //
00246   // It is very common that one register class is a sub-register of the other.
00247   // Arrange for RCA to be the larger register so the answer will be found in
00248   // the first iteration. This makes the search linear for the most common
00249   // case.
00250   const TargetRegisterClass *BestRC = nullptr;
00251   unsigned *BestPreA = &PreA;
00252   unsigned *BestPreB = &PreB;
00253   if (RCA->getSize() < RCB->getSize()) {
00254     std::swap(RCA, RCB);
00255     std::swap(SubA, SubB);
00256     std::swap(BestPreA, BestPreB);
00257   }
00258 
00259   // Also terminate the search one we have found a register class as small as
00260   // RCA.
00261   unsigned MinSize = RCA->getSize();
00262 
00263   for (SuperRegClassIterator IA(RCA, this, true); IA.isValid(); ++IA) {
00264     unsigned FinalA = composeSubRegIndices(IA.getSubReg(), SubA);
00265     for (SuperRegClassIterator IB(RCB, this, true); IB.isValid(); ++IB) {
00266       // Check if a common super-register class exists for this index pair.
00267       const TargetRegisterClass *RC =
00268         firstCommonClass(IA.getMask(), IB.getMask(), this);
00269       if (!RC || RC->getSize() < MinSize)
00270         continue;
00271 
00272       // The indexes must compose identically: PreA+SubA == PreB+SubB.
00273       unsigned FinalB = composeSubRegIndices(IB.getSubReg(), SubB);
00274       if (FinalA != FinalB)
00275         continue;
00276 
00277       // Is RC a better candidate than BestRC?
00278       if (BestRC && RC->getSize() >= BestRC->getSize())
00279         continue;
00280 
00281       // Yes, RC is the smallest super-register seen so far.
00282       BestRC = RC;
00283       *BestPreA = IA.getSubReg();
00284       *BestPreB = IB.getSubReg();
00285 
00286       // Bail early if we reached MinSize. We won't find a better candidate.
00287       if (BestRC->getSize() == MinSize)
00288         return BestRC;
00289     }
00290   }
00291   return BestRC;
00292 }
00293 
00294 /// \brief Check if the registers defined by the pair (RegisterClass, SubReg)
00295 /// share the same register file.
00296 static bool shareSameRegisterFile(const TargetRegisterInfo &TRI,
00297                                   const TargetRegisterClass *DefRC,
00298                                   unsigned DefSubReg,
00299                                   const TargetRegisterClass *SrcRC,
00300                                   unsigned SrcSubReg) {
00301   // Same register class.
00302   if (DefRC == SrcRC)
00303     return true;
00304 
00305   // Both operands are sub registers. Check if they share a register class.
00306   unsigned SrcIdx, DefIdx;
00307   if (SrcSubReg && DefSubReg) {
00308     return TRI.getCommonSuperRegClass(SrcRC, SrcSubReg, DefRC, DefSubReg,
00309                                       SrcIdx, DefIdx) != nullptr;
00310   }
00311 
00312   // At most one of the register is a sub register, make it Src to avoid
00313   // duplicating the test.
00314   if (!SrcSubReg) {
00315     std::swap(DefSubReg, SrcSubReg);
00316     std::swap(DefRC, SrcRC);
00317   }
00318 
00319   // One of the register is a sub register, check if we can get a superclass.
00320   if (SrcSubReg)
00321     return TRI.getMatchingSuperRegClass(SrcRC, DefRC, SrcSubReg) != nullptr;
00322 
00323   // Plain copy.
00324   return TRI.getCommonSubClass(DefRC, SrcRC) != nullptr;
00325 }
00326 
00327 bool TargetRegisterInfo::shouldRewriteCopySrc(const TargetRegisterClass *DefRC,
00328                                               unsigned DefSubReg,
00329                                               const TargetRegisterClass *SrcRC,
00330                                               unsigned SrcSubReg) const {
00331   // If this source does not incur a cross register bank copy, use it.
00332   return shareSameRegisterFile(*this, DefRC, DefSubReg, SrcRC, SrcSubReg);
00333 }
00334 
00335 // Compute target-independent register allocator hints to help eliminate copies.
00336 void
00337 TargetRegisterInfo::getRegAllocationHints(unsigned VirtReg,
00338                                           ArrayRef<MCPhysReg> Order,
00339                                           SmallVectorImpl<MCPhysReg> &Hints,
00340                                           const MachineFunction &MF,
00341                                           const VirtRegMap *VRM,
00342                                           const LiveRegMatrix *Matrix) const {
00343   const MachineRegisterInfo &MRI = MF.getRegInfo();
00344   std::pair<unsigned, unsigned> Hint = MRI.getRegAllocationHint(VirtReg);
00345 
00346   // Hints with HintType != 0 were set by target-dependent code.
00347   // Such targets must provide their own implementation of
00348   // TRI::getRegAllocationHints to interpret those hint types.
00349   assert(Hint.first == 0 && "Target must implement TRI::getRegAllocationHints");
00350 
00351   // Target-independent hints are either a physical or a virtual register.
00352   unsigned Phys = Hint.second;
00353   if (VRM && isVirtualRegister(Phys))
00354     Phys = VRM->getPhys(Phys);
00355 
00356   // Check that Phys is a valid hint in VirtReg's register class.
00357   if (!isPhysicalRegister(Phys))
00358     return;
00359   if (MRI.isReserved(Phys))
00360     return;
00361   // Check that Phys is in the allocation order. We shouldn't heed hints
00362   // from VirtReg's register class if they aren't in the allocation order. The
00363   // target probably has a reason for removing the register.
00364   if (std::find(Order.begin(), Order.end(), Phys) == Order.end())
00365     return;
00366 
00367   // All clear, tell the register allocator to prefer this register.
00368   Hints.push_back(Phys);
00369 }
00370 
00371 bool TargetRegisterInfo::canRealignStack(const MachineFunction &MF) const {
00372   return !MF.getFunction()->hasFnAttribute("no-realign-stack");
00373 }
00374 
00375 bool TargetRegisterInfo::needsStackRealignment(
00376     const MachineFunction &MF) const {
00377   const MachineFrameInfo *MFI = MF.getFrameInfo();
00378   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
00379   const Function *F = MF.getFunction();
00380   unsigned StackAlign = TFI->getStackAlignment();
00381   bool requiresRealignment = ((MFI->getMaxAlignment() > StackAlign) ||
00382                               F->hasFnAttribute(Attribute::StackAlignment));
00383   if (MF.getFunction()->hasFnAttribute("stackrealign") || requiresRealignment) {
00384     if (canRealignStack(MF))
00385       return true;
00386     DEBUG(dbgs() << "Can't realign function's stack: " << F->getName() << "\n");
00387   }
00388   return false;
00389 }
00390 
00391 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
00392 void
00393 TargetRegisterInfo::dumpReg(unsigned Reg, unsigned SubRegIndex,
00394                             const TargetRegisterInfo *TRI) {
00395   dbgs() << PrintReg(Reg, TRI, SubRegIndex) << "\n";
00396 }
00397 #endif