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/Target/TargetRegisterInfo.h"
  15 #include "llvm/ADT/BitVector.h"
  16 #include "llvm/CodeGen/MachineFunction.h"
  17 #include "llvm/CodeGen/MachineRegisterInfo.h"
  18 #include "llvm/CodeGen/VirtRegMap.h"
  19 #include "llvm/Support/raw_ostream.h"
  20 #include "llvm/Target/TargetMachine.h"
  21
  22 using namespace llvm;
  23
  24 TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterInfoDesc *ID,
  25                              regclass_iterator RCB, regclass_iterator RCE,
  26                              const char *const *SRINames,
  27                              const unsigned *SRILaneMasks)
  28   : InfoDesc(ID), SubRegIndexNames(SRINames),
  29     SubRegIndexLaneMasks(SRILaneMasks),
  30     RegClassBegin(RCB), RegClassEnd(RCE) {
  31 }
  32
  33 TargetRegisterInfo::~TargetRegisterInfo() {}
  34
  35 void PrintReg::print(raw_ostream &OS) const {
  36   if (!Reg)
  37     OS << "%noreg";
  38   else if (TargetRegisterInfo::isStackSlot(Reg))
  39     OS << "SS#" << TargetRegisterInfo::stackSlot2Index(Reg);
  40   else if (TargetRegisterInfo::isVirtualRegister(Reg))
  41     OS << "%vreg" << TargetRegisterInfo::virtReg2Index(Reg);
  42   else if (TRI && Reg < TRI->getNumRegs())
  43     OS << '%' << TRI->getName(Reg);
  44   else
  45     OS << "%physreg" << Reg;
  46   if (SubIdx) {
  47     if (TRI)
  48       OS << ':' << TRI->getSubRegIndexName(SubIdx);
  49     else
  50       OS << ":sub(" << SubIdx << ')';
  51   }
  52 }
  53
  54 void PrintRegUnit::print(raw_ostream &OS) const {
  55   // Generic printout when TRI is missing.
  56   if (!TRI) {
  57     OS << "Unit~" << Unit;
  58     return;
  59   }
  60
  61   // Check for invalid register units.
  62   if (Unit >= TRI->getNumRegUnits()) {
  63     OS << "BadUnit~" << Unit;
  64     return;
  65   }
  66
  67   // Normal units have at least one root.
  68   MCRegUnitRootIterator Roots(Unit, TRI);
  69   assert(Roots.isValid() && "Unit has no roots.");
  70   OS << TRI->getName(*Roots);
  71   for (++Roots; Roots.isValid(); ++Roots)
  72     OS << '~' << TRI->getName(*Roots);
  73 }
  74
  75 /// getAllocatableClass - Return the maximal subclass of the given register
  76 /// class that is alloctable, or NULL.
  77 const TargetRegisterClass *
  78 TargetRegisterInfo::getAllocatableClass(const TargetRegisterClass *RC) const {
  79   if (!RC || RC->isAllocatable())
  80     return RC;
  81
  82   const unsigned *SubClass = RC->getSubClassMask();
  83   for (unsigned Base = 0, BaseE = getNumRegClasses();
  84        Base < BaseE; Base += 32) {
  85     unsigned Idx = Base;
  86     for (unsigned Mask = *SubClass++; Mask; Mask >>= 1) {
  87       unsigned Offset = CountTrailingZeros_32(Mask);
  88       const TargetRegisterClass *SubRC = getRegClass(Idx + Offset);
  89       if (SubRC->isAllocatable())
  90         return SubRC;
  91       Mask >>= Offset;
  92       Idx += Offset + 1;
  93     }
  94   }
  95   return NULL;
  96 }
  97
  98 /// getMinimalPhysRegClass - Returns the Register Class of a physical
  99 /// register of the given type, picking the most sub register class of
 100 /// the right type that contains this physreg.
 101 const TargetRegisterClass *
 102 TargetRegisterInfo::getMinimalPhysRegClass(unsigned reg, EVT VT) const {
 103   assert(isPhysicalRegister(reg) && "reg must be a physical register");
 104
 105   // Pick the most sub register class of the right type that contains
 106   // this physreg.
 107   const TargetRegisterClass* BestRC = 0;
 108   for (regclass_iterator I = regclass_begin(), E = regclass_end(); I != E; ++I){
 109     const TargetRegisterClass* RC = *I;
 110     if ((VT == MVT::Other || RC->hasType(VT)) && RC->contains(reg) &&
 111         (!BestRC || BestRC->hasSubClass(RC)))
 112       BestRC = RC;
 113   }
 114
 115   assert(BestRC && "Couldn't find the register class");
 116   return BestRC;
 117 }
 118
 119 /// getAllocatableSetForRC - Toggle the bits that represent allocatable
 120 /// registers for the specific register class.
 121 static void getAllocatableSetForRC(const MachineFunction &MF,
 122                                    const TargetRegisterClass *RC, BitVector &R){
 123   assert(RC->isAllocatable() && "invalid for nonallocatable sets");
 124   ArrayRef<uint16_t> Order = RC->getRawAllocationOrder(MF);
 125   for (unsigned i = 0; i != Order.size(); ++i)
 126     R.set(Order[i]);
 127 }
 128
 129 BitVector TargetRegisterInfo::getAllocatableSet(const MachineFunction &MF,
 130                                           const TargetRegisterClass *RC) const {
 131   BitVector Allocatable(getNumRegs());
 132   if (RC) {
 133     // A register class with no allocatable subclass returns an empty set.
 134     const TargetRegisterClass *SubClass = getAllocatableClass(RC);
 135     if (SubClass)
 136       getAllocatableSetForRC(MF, SubClass, Allocatable);
 137   } else {
 138     for (TargetRegisterInfo::regclass_iterator I = regclass_begin(),
 139          E = regclass_end(); I != E; ++I)
 140       if ((*I)->isAllocatable())
 141         getAllocatableSetForRC(MF, *I, Allocatable);
 142   }
 143
 144   // Mask out the reserved registers
 145   BitVector Reserved = getReservedRegs(MF);
 146   Allocatable &= Reserved.flip();
 147
 148   return Allocatable;
 149 }
 150
 151 static inline
 152 const TargetRegisterClass *firstCommonClass(const uint32_t *A,
 153                                             const uint32_t *B,
 154                                             const TargetRegisterInfo *TRI) {
 155   for (unsigned I = 0, E = TRI->getNumRegClasses(); I < E; I += 32)
 156     if (unsigned Common = *A++ & *B++)
 157       return TRI->getRegClass(I + CountTrailingZeros_32(Common));
 158   return 0;
 159 }
 160
 161 const TargetRegisterClass *
 162 TargetRegisterInfo::getCommonSubClass(const TargetRegisterClass *A,
 163                                       const TargetRegisterClass *B) const {
 164   // First take care of the trivial cases.
 165   if (A == B)
 166     return A;
 167   if (!A || !B)
 168     return 0;
 169
 170   // Register classes are ordered topologically, so the largest common
 171   // sub-class it the common sub-class with the smallest ID.
 172   return firstCommonClass(A->getSubClassMask(), B->getSubClassMask(), this);
 173 }
 174
 175 const TargetRegisterClass *
 176 TargetRegisterInfo::getMatchingSuperRegClass(const TargetRegisterClass *A,
 177                                              const TargetRegisterClass *B,
 178                                              unsigned Idx) const {
 179   assert(A && B && "Missing register class");
 180   assert(Idx && "Bad sub-register index");
 181
 182   // Find Idx in the list of super-register indices.
 183   for (SuperRegClassIterator RCI(B, this); RCI.isValid(); ++RCI)
 184     if (RCI.getSubReg() == Idx)
 185       // The bit mask contains all register classes that are projected into B
 186       // by Idx. Find a class that is also a sub-class of A.
 187       return firstCommonClass(RCI.getMask(), A->getSubClassMask(), this);
 188   return 0;
 189 }
 190
 191 const TargetRegisterClass *TargetRegisterInfo::
 192 getCommonSuperRegClass(const TargetRegisterClass *RCA, unsigned SubA,
 193                        const TargetRegisterClass *RCB, unsigned SubB,
 194                        unsigned &PreA, unsigned &PreB) const {
 195   assert(RCA && SubA && RCB && SubB && "Invalid arguments");
 196
 197   // Search all pairs of sub-register indices that project into RCA and RCB
 198   // respectively. This is quadratic, but usually the sets are very small. On
 199   // most targets like X86, there will only be a single sub-register index
 200   // (e.g., sub_16bit projecting into GR16).
 201   //
 202   // The worst case is a register class like DPR on ARM.
 203   // We have indices dsub_0..dsub_7 projecting into that class.
 204   //
 205   // It is very common that one register class is a sub-register of the other.
 206   // Arrange for RCA to be the larger register so the answer will be found in
 207   // the first iteration. This makes the search linear for the most common
 208   // case.
 209   const TargetRegisterClass *BestRC = 0;
 210   unsigned *BestPreA = &PreA;
 211   unsigned *BestPreB = &PreB;
 212   if (RCA->getSize() < RCB->getSize()) {
 213     std::swap(RCA, RCB);
 214     std::swap(SubA, SubB);
 215     std::swap(BestPreA, BestPreB);
 216   }
 217
 218   // Also terminate the search one we have found a register class as small as
 219   // RCA.
 220   unsigned MinSize = RCA->getSize();
 221
 222   for (SuperRegClassIterator IA(RCA, this, true); IA.isValid(); ++IA) {
 223     unsigned FinalA = composeSubRegIndices(IA.getSubReg(), SubA);
 224     for (SuperRegClassIterator IB(RCB, this, true); IB.isValid(); ++IB) {
 225       // Check if a common super-register class exists for this index pair.
 226       const TargetRegisterClass *RC =
 227         firstCommonClass(IA.getMask(), IB.getMask(), this);
 228       if (!RC || RC->getSize() < MinSize)
 229         continue;
 230
 231       // The indexes must compose identically: PreA+SubA == PreB+SubB.
 232       unsigned FinalB = composeSubRegIndices(IB.getSubReg(), SubB);
 233       if (FinalA != FinalB)
 234         continue;
 235
 236       // Is RC a better candidate than BestRC?
 237       if (BestRC && RC->getSize() >= BestRC->getSize())
 238         continue;
 239
 240       // Yes, RC is the smallest super-register seen so far.
 241       BestRC = RC;
 242       *BestPreA = IA.getSubReg();
 243       *BestPreB = IB.getSubReg();
 244
 245       // Bail early if we reached MinSize. We won't find a better candidate.
 246       if (BestRC->getSize() == MinSize)
 247         return BestRC;
 248     }
 249   }
 250   return BestRC;
 251 }
 252
 253 // Compute target-independent register allocator hints to help eliminate copies.
 254 void
 255 TargetRegisterInfo::getRegAllocationHints(unsigned VirtReg,
 256                                           ArrayRef<MCPhysReg> Order,
 257                                           SmallVectorImpl<MCPhysReg> &Hints,
 258                                           const MachineFunction &MF,
 259                                           const VirtRegMap *VRM) const {
 260   const MachineRegisterInfo &MRI = MF.getRegInfo();
 261   std::pair<unsigned, unsigned> Hint = MRI.getRegAllocationHint(VirtReg);
 262
 263   // Hints with HintType != 0 were set by target-dependent code.
 264   // Such targets must provide their own implementation of
 265   // TRI::getRegAllocationHints to interpret those hint types.
 266   assert(Hint.first == 0 && "Target must implement TRI::getRegAllocationHints");
 267
 268   // Target-independent hints are either a physical or a virtual register.
 269   unsigned Phys = Hint.second;
 270   if (VRM && isVirtualRegister(Phys))
 271     Phys = VRM->getPhys(Phys);
 272
 273   // Check that Phys is a valid hint in VirtReg's register class.
 274   if (!isPhysicalRegister(Phys))
 275     return;
 276   if (MRI.isReserved(Phys))
 277     return;
 278   // Check that Phys is in the allocation order. We shouldn't heed hints
 279   // from VirtReg's register class if they aren't in the allocation order. The
 280   // target probably has a reason for removing the register.
 281   if (std::find(Order.begin(), Order.end(), Phys) == Order.end())
 282     return;
 283
 284   // All clear, tell the register allocator to prefer this register.
 285   Hints.push_back(Phys);
 286 }