LLVM API Documentation

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/Target/TargetRegisterInfo.h"
00015 #include "llvm/ADT/BitVector.h"
00016 #include "llvm/CodeGen/MachineFunction.h"
00017 #include "llvm/CodeGen/MachineRegisterInfo.h"
00018 #include "llvm/CodeGen/VirtRegMap.h"
00019 #include "llvm/Support/Debug.h"
00020 #include "llvm/Support/raw_ostream.h"
00021 
00022 using namespace llvm;
00023 
00024 TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterInfoDesc *ID,
00025                              regclass_iterator RCB, regclass_iterator RCE,
00026                              const char *const *SRINames,
00027                              const unsigned *SRILaneMasks,
00028                              unsigned SRICoveringLanes)
00029   : InfoDesc(ID), SubRegIndexNames(SRINames),
00030     SubRegIndexLaneMasks(SRILaneMasks),
00031     RegClassBegin(RCB), RegClassEnd(RCE),
00032     CoveringLanes(SRICoveringLanes) {
00033 }
00034 
00035 TargetRegisterInfo::~TargetRegisterInfo() {}
00036 
00037 void PrintReg::print(raw_ostream &OS) const {
00038   if (!Reg)
00039     OS << "%noreg";
00040   else if (TargetRegisterInfo::isStackSlot(Reg))
00041     OS << "SS#" << TargetRegisterInfo::stackSlot2Index(Reg);
00042   else if (TargetRegisterInfo::isVirtualRegister(Reg))
00043     OS << "%vreg" << TargetRegisterInfo::virtReg2Index(Reg);
00044   else if (TRI && Reg < TRI->getNumRegs())
00045     OS << '%' << TRI->getName(Reg);
00046   else
00047     OS << "%physreg" << Reg;
00048   if (SubIdx) {
00049     if (TRI)
00050       OS << ':' << TRI->getSubRegIndexName(SubIdx);
00051     else
00052       OS << ":sub(" << SubIdx << ')';
00053   }
00054 }
00055 
00056 void PrintRegUnit::print(raw_ostream &OS) const {
00057   // Generic printout when TRI is missing.
00058   if (!TRI) {
00059     OS << "Unit~" << Unit;
00060     return;
00061   }
00062 
00063   // Check for invalid register units.
00064   if (Unit >= TRI->getNumRegUnits()) {
00065     OS << "BadUnit~" << Unit;
00066     return;
00067   }
00068 
00069   // Normal units have at least one root.
00070   MCRegUnitRootIterator Roots(Unit, TRI);
00071   assert(Roots.isValid() && "Unit has no roots.");
00072   OS << TRI->getName(*Roots);
00073   for (++Roots; Roots.isValid(); ++Roots)
00074     OS << '~' << TRI->getName(*Roots);
00075 }
00076 
00077 void PrintVRegOrUnit::print(raw_ostream &OS) const {
00078   if (TRI && TRI->isVirtualRegister(Unit)) {
00079     OS << "%vreg" << TargetRegisterInfo::virtReg2Index(Unit);
00080     return;
00081   }
00082   PrintRegUnit::print(OS);
00083 }
00084 
00085 /// getAllocatableClass - Return the maximal subclass of the given register
00086 /// class that is alloctable, or NULL.
00087 const TargetRegisterClass *
00088 TargetRegisterInfo::getAllocatableClass(const TargetRegisterClass *RC) const {
00089   if (!RC || RC->isAllocatable())
00090     return RC;
00091 
00092   const unsigned *SubClass = RC->getSubClassMask();
00093   for (unsigned Base = 0, BaseE = getNumRegClasses();
00094        Base < BaseE; Base += 32) {
00095     unsigned Idx = Base;
00096     for (unsigned Mask = *SubClass++; Mask; Mask >>= 1) {
00097       unsigned Offset = countTrailingZeros(Mask);
00098       const TargetRegisterClass *SubRC = getRegClass(Idx + Offset);
00099       if (SubRC->isAllocatable())
00100         return SubRC;
00101       Mask >>= Offset;
00102       Idx += Offset + 1;
00103     }
00104   }
00105   return nullptr;
00106 }
00107 
00108 /// getMinimalPhysRegClass - Returns the Register Class of a physical
00109 /// register of the given type, picking the most sub register class of
00110 /// the right type that contains this physreg.
00111 const TargetRegisterClass *
00112 TargetRegisterInfo::getMinimalPhysRegClass(unsigned reg, MVT VT) const {
00113   assert(isPhysicalRegister(reg) && "reg must be a physical register");
00114 
00115   // Pick the most sub register class of the right type that contains
00116   // this physreg.
00117   const TargetRegisterClass* BestRC = nullptr;
00118   for (regclass_iterator I = regclass_begin(), E = regclass_end(); I != E; ++I){
00119     const TargetRegisterClass* RC = *I;
00120     if ((VT == MVT::Other || RC->hasType(VT)) && RC->contains(reg) &&
00121         (!BestRC || BestRC->hasSubClass(RC)))
00122       BestRC = RC;
00123   }
00124 
00125   assert(BestRC && "Couldn't find the register class");
00126   return BestRC;
00127 }
00128 
00129 /// getAllocatableSetForRC - Toggle the bits that represent allocatable
00130 /// registers for the specific register class.
00131 static void getAllocatableSetForRC(const MachineFunction &MF,
00132                                    const TargetRegisterClass *RC, BitVector &R){
00133   assert(RC->isAllocatable() && "invalid for nonallocatable sets");
00134   ArrayRef<MCPhysReg> Order = RC->getRawAllocationOrder(MF);
00135   for (unsigned i = 0; i != Order.size(); ++i)
00136     R.set(Order[i]);
00137 }
00138 
00139 BitVector TargetRegisterInfo::getAllocatableSet(const MachineFunction &MF,
00140                                           const TargetRegisterClass *RC) const {
00141   BitVector Allocatable(getNumRegs());
00142   if (RC) {
00143     // A register class with no allocatable subclass returns an empty set.
00144     const TargetRegisterClass *SubClass = getAllocatableClass(RC);
00145     if (SubClass)
00146       getAllocatableSetForRC(MF, SubClass, Allocatable);
00147   } else {
00148     for (TargetRegisterInfo::regclass_iterator I = regclass_begin(),
00149          E = regclass_end(); I != E; ++I)
00150       if ((*I)->isAllocatable())
00151         getAllocatableSetForRC(MF, *I, Allocatable);
00152   }
00153 
00154   // Mask out the reserved registers
00155   BitVector Reserved = getReservedRegs(MF);
00156   Allocatable &= Reserved.flip();
00157 
00158   return Allocatable;
00159 }
00160 
00161 static inline
00162 const TargetRegisterClass *firstCommonClass(const uint32_t *A,
00163                                             const uint32_t *B,
00164                                             const TargetRegisterInfo *TRI) {
00165   for (unsigned I = 0, E = TRI->getNumRegClasses(); I < E; I += 32)
00166     if (unsigned Common = *A++ & *B++)
00167       return TRI->getRegClass(I + countTrailingZeros(Common));
00168   return nullptr;
00169 }
00170 
00171 const TargetRegisterClass *
00172 TargetRegisterInfo::getCommonSubClass(const TargetRegisterClass *A,
00173                                       const TargetRegisterClass *B) const {
00174   // First take care of the trivial cases.
00175   if (A == B)
00176     return A;
00177   if (!A || !B)
00178     return nullptr;
00179 
00180   // Register classes are ordered topologically, so the largest common
00181   // sub-class it the common sub-class with the smallest ID.
00182   return firstCommonClass(A->getSubClassMask(), B->getSubClassMask(), this);
00183 }
00184 
00185 const TargetRegisterClass *
00186 TargetRegisterInfo::getMatchingSuperRegClass(const TargetRegisterClass *A,
00187                                              const TargetRegisterClass *B,
00188                                              unsigned Idx) const {
00189   assert(A && B && "Missing register class");
00190   assert(Idx && "Bad sub-register index");
00191 
00192   // Find Idx in the list of super-register indices.
00193   for (SuperRegClassIterator RCI(B, this); RCI.isValid(); ++RCI)
00194     if (RCI.getSubReg() == Idx)
00195       // The bit mask contains all register classes that are projected into B
00196       // by Idx. Find a class that is also a sub-class of A.
00197       return firstCommonClass(RCI.getMask(), A->getSubClassMask(), this);
00198   return nullptr;
00199 }
00200 
00201 const TargetRegisterClass *TargetRegisterInfo::
00202 getCommonSuperRegClass(const TargetRegisterClass *RCA, unsigned SubA,
00203                        const TargetRegisterClass *RCB, unsigned SubB,
00204                        unsigned &PreA, unsigned &PreB) const {
00205   assert(RCA && SubA && RCB && SubB && "Invalid arguments");
00206 
00207   // Search all pairs of sub-register indices that project into RCA and RCB
00208   // respectively. This is quadratic, but usually the sets are very small. On
00209   // most targets like X86, there will only be a single sub-register index
00210   // (e.g., sub_16bit projecting into GR16).
00211   //
00212   // The worst case is a register class like DPR on ARM.
00213   // We have indices dsub_0..dsub_7 projecting into that class.
00214   //
00215   // It is very common that one register class is a sub-register of the other.
00216   // Arrange for RCA to be the larger register so the answer will be found in
00217   // the first iteration. This makes the search linear for the most common
00218   // case.
00219   const TargetRegisterClass *BestRC = nullptr;
00220   unsigned *BestPreA = &PreA;
00221   unsigned *BestPreB = &PreB;
00222   if (RCA->getSize() < RCB->getSize()) {
00223     std::swap(RCA, RCB);
00224     std::swap(SubA, SubB);
00225     std::swap(BestPreA, BestPreB);
00226   }
00227 
00228   // Also terminate the search one we have found a register class as small as
00229   // RCA.
00230   unsigned MinSize = RCA->getSize();
00231 
00232   for (SuperRegClassIterator IA(RCA, this, true); IA.isValid(); ++IA) {
00233     unsigned FinalA = composeSubRegIndices(IA.getSubReg(), SubA);
00234     for (SuperRegClassIterator IB(RCB, this, true); IB.isValid(); ++IB) {
00235       // Check if a common super-register class exists for this index pair.
00236       const TargetRegisterClass *RC =
00237         firstCommonClass(IA.getMask(), IB.getMask(), this);
00238       if (!RC || RC->getSize() < MinSize)
00239         continue;
00240 
00241       // The indexes must compose identically: PreA+SubA == PreB+SubB.
00242       unsigned FinalB = composeSubRegIndices(IB.getSubReg(), SubB);
00243       if (FinalA != FinalB)
00244         continue;
00245 
00246       // Is RC a better candidate than BestRC?
00247       if (BestRC && RC->getSize() >= BestRC->getSize())
00248         continue;
00249 
00250       // Yes, RC is the smallest super-register seen so far.
00251       BestRC = RC;
00252       *BestPreA = IA.getSubReg();
00253       *BestPreB = IB.getSubReg();
00254 
00255       // Bail early if we reached MinSize. We won't find a better candidate.
00256       if (BestRC->getSize() == MinSize)
00257         return BestRC;
00258     }
00259   }
00260   return BestRC;
00261 }
00262 
00263 // Compute target-independent register allocator hints to help eliminate copies.
00264 void
00265 TargetRegisterInfo::getRegAllocationHints(unsigned VirtReg,
00266                                           ArrayRef<MCPhysReg> Order,
00267                                           SmallVectorImpl<MCPhysReg> &Hints,
00268                                           const MachineFunction &MF,
00269                                           const VirtRegMap *VRM) const {
00270   const MachineRegisterInfo &MRI = MF.getRegInfo();
00271   std::pair<unsigned, unsigned> Hint = MRI.getRegAllocationHint(VirtReg);
00272 
00273   // Hints with HintType != 0 were set by target-dependent code.
00274   // Such targets must provide their own implementation of
00275   // TRI::getRegAllocationHints to interpret those hint types.
00276   assert(Hint.first == 0 && "Target must implement TRI::getRegAllocationHints");
00277 
00278   // Target-independent hints are either a physical or a virtual register.
00279   unsigned Phys = Hint.second;
00280   if (VRM && isVirtualRegister(Phys))
00281     Phys = VRM->getPhys(Phys);
00282 
00283   // Check that Phys is a valid hint in VirtReg's register class.
00284   if (!isPhysicalRegister(Phys))
00285     return;
00286   if (MRI.isReserved(Phys))
00287     return;
00288   // Check that Phys is in the allocation order. We shouldn't heed hints
00289   // from VirtReg's register class if they aren't in the allocation order. The
00290   // target probably has a reason for removing the register.
00291   if (std::find(Order.begin(), Order.end(), Phys) == Order.end())
00292     return;
00293 
00294   // All clear, tell the register allocator to prefer this register.
00295   Hints.push_back(Phys);
00296 }
00297 
00298 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
00299 void
00300 TargetRegisterInfo::dumpReg(unsigned Reg, unsigned SubRegIndex,
00301                             const TargetRegisterInfo *TRI) {
00302   dbgs() << PrintReg(Reg, TRI, SubRegIndex) << "\n";
00303 }
00304 #endif