TargetRegisterInfo.cpp revision 7eafc3e7be067709c6fcdae7b7fc4994c7ec2377 
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
22using namespace llvm;
23
24TargetRegisterInfo::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
33TargetRegisterInfo::~TargetRegisterInfo() {}
34
35void 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
54void 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.
77const TargetRegisterClass *
78TargetRegisterInfo::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.
101const TargetRegisterClass *
102TargetRegisterInfo::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.
121static 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
129BitVector 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
151static inline
152const 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
161const TargetRegisterClass *
162TargetRegisterInfo::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
175const TargetRegisterClass *
176TargetRegisterInfo::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
191const TargetRegisterClass *TargetRegisterInfo::
192getCommonSuperRegClass(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.
254void
255TargetRegisterInfo::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}
287