LLVM  6.0.0svn
RegisterClassInfo.cpp
Go to the documentation of this file.
1 //===- RegisterClassInfo.cpp - Dynamic Register Class Info ----------------===//
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 RegisterClassInfo class which provides dynamic
11 // information about target register classes. Callee-saved vs. caller-saved and
12 // reserved registers depend on calling conventions and other dynamic
13 // information, so some things cannot be determined statically.
14 //
15 //===----------------------------------------------------------------------===//
16 
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/BitVector.h"
20 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/MC/MCRegisterInfo.h"
28 #include "llvm/Support/Debug.h"
30 #include <algorithm>
31 #include <cassert>
32 #include <cstdint>
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "regalloc"
37 
38 static cl::opt<unsigned>
39 StressRA("stress-regalloc", cl::Hidden, cl::init(0), cl::value_desc("N"),
40  cl::desc("Limit all regclasses to N registers"));
41 
43 
45  bool Update = false;
46  MF = &mf;
47 
48  // Allocate new array the first time we see a new target.
49  if (MF->getSubtarget().getRegisterInfo() != TRI) {
50  TRI = MF->getSubtarget().getRegisterInfo();
51  RegClass.reset(new RCInfo[TRI->getNumRegClasses()]);
52  unsigned NumPSets = TRI->getNumRegPressureSets();
53  PSetLimits.reset(new unsigned[NumPSets]);
54  std::fill(&PSetLimits[0], &PSetLimits[NumPSets], 0);
55  Update = true;
56  }
57 
58  // Does this MF have different CSRs?
59  assert(TRI && "no register info set");
60 
61  // Get the callee saved registers.
62  const MCPhysReg *CSR = MF->getRegInfo().getCalleeSavedRegs();
63  if (Update || CSR != CalleeSavedRegs) {
64  // Build a CSRAlias map. Every CSR alias saves the last
65  // overlapping CSR.
66  CalleeSavedAliases.resize(TRI->getNumRegs(), 0);
67  for (const MCPhysReg *I = CSR; *I; ++I)
68  for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI)
69  CalleeSavedAliases[*AI] = *I;
70 
71  Update = true;
72  }
73  CalleeSavedRegs = CSR;
74 
75  // Different reserved registers?
76  const BitVector &RR = MF->getRegInfo().getReservedRegs();
77  if (Reserved.size() != RR.size() || RR != Reserved) {
78  Update = true;
79  Reserved = RR;
80  }
81 
82  // Invalidate cached information from previous function.
83  if (Update)
84  ++Tag;
85 }
86 
87 /// compute - Compute the preferred allocation order for RC with reserved
88 /// registers filtered out. Volatile registers come first followed by CSR
89 /// aliases ordered according to the CSR order specified by the target.
90 void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
91  assert(RC && "no register class given");
92  RCInfo &RCI = RegClass[RC->getID()];
93 
94  // Raw register count, including all reserved regs.
95  unsigned NumRegs = RC->getNumRegs();
96 
97  if (!RCI.Order)
98  RCI.Order.reset(new MCPhysReg[NumRegs]);
99 
100  unsigned N = 0;
102  unsigned MinCost = 0xff;
103  unsigned LastCost = ~0u;
104  unsigned LastCostChange = 0;
105 
106  // FIXME: Once targets reserve registers instead of removing them from the
107  // allocation order, we can simply use begin/end here.
108  ArrayRef<MCPhysReg> RawOrder = RC->getRawAllocationOrder(*MF);
109  for (unsigned i = 0; i != RawOrder.size(); ++i) {
110  unsigned PhysReg = RawOrder[i];
111  // Remove reserved registers from the allocation order.
112  if (Reserved.test(PhysReg))
113  continue;
114  unsigned Cost = TRI->getCostPerUse(PhysReg);
115  MinCost = std::min(MinCost, Cost);
116 
117  if (CalleeSavedAliases[PhysReg])
118  // PhysReg aliases a CSR, save it for later.
119  CSRAlias.push_back(PhysReg);
120  else {
121  if (Cost != LastCost)
122  LastCostChange = N;
123  RCI.Order[N++] = PhysReg;
124  LastCost = Cost;
125  }
126  }
127  RCI.NumRegs = N + CSRAlias.size();
128  assert(RCI.NumRegs <= NumRegs && "Allocation order larger than regclass");
129 
130  // CSR aliases go after the volatile registers, preserve the target's order.
131  for (unsigned i = 0, e = CSRAlias.size(); i != e; ++i) {
132  unsigned PhysReg = CSRAlias[i];
133  unsigned Cost = TRI->getCostPerUse(PhysReg);
134  if (Cost != LastCost)
135  LastCostChange = N;
136  RCI.Order[N++] = PhysReg;
137  LastCost = Cost;
138  }
139 
140  // Register allocator stress test. Clip register class to N registers.
141  if (StressRA && RCI.NumRegs > StressRA)
142  RCI.NumRegs = StressRA;
143 
144  // Check if RC is a proper sub-class.
145  if (const TargetRegisterClass *Super =
146  TRI->getLargestLegalSuperClass(RC, *MF))
147  if (Super != RC && getNumAllocatableRegs(Super) > RCI.NumRegs)
148  RCI.ProperSubClass = true;
149 
150  RCI.MinCost = uint8_t(MinCost);
151  RCI.LastCostChange = LastCostChange;
152 
153  DEBUG({
154  dbgs() << "AllocationOrder(" << TRI->getRegClassName(RC) << ") = [";
155  for (unsigned I = 0; I != RCI.NumRegs; ++I)
156  dbgs() << ' ' << PrintReg(RCI.Order[I], TRI);
157  dbgs() << (RCI.ProperSubClass ? " ] (sub-class)\n" : " ]\n");
158  });
159 
160  // RCI is now up-to-date.
161  RCI.Tag = Tag;
162 }
163 
164 /// This is not accurate because two overlapping register sets may have some
165 /// nonoverlapping reserved registers. However, computing the allocation order
166 /// for all register classes would be too expensive.
167 unsigned RegisterClassInfo::computePSetLimit(unsigned Idx) const {
168  const TargetRegisterClass *RC = nullptr;
169  unsigned NumRCUnits = 0;
170  for (const TargetRegisterClass *C : TRI->regclasses()) {
171  const int *PSetID = TRI->getRegClassPressureSets(C);
172  for (; *PSetID != -1; ++PSetID) {
173  if ((unsigned)*PSetID == Idx)
174  break;
175  }
176  if (*PSetID == -1)
177  continue;
178 
179  // Found a register class that counts against this pressure set.
180  // For efficiency, only compute the set order for the largest set.
181  unsigned NUnits = TRI->getRegClassWeight(C).WeightLimit;
182  if (!RC || NUnits > NumRCUnits) {
183  RC = C;
184  NumRCUnits = NUnits;
185  }
186  }
187  compute(RC);
188  unsigned NReserved = RC->getNumRegs() - getNumAllocatableRegs(RC);
189  return TRI->getRegPressureSetLimit(*MF, Idx) -
190  TRI->getRegClassWeight(RC).RegWeight * NReserved;
191 }
uint64_t CallInst * C
void push_back(const T &Elt)
Definition: SmallVector.h:212
virtual unsigned getNumRegPressureSets() const =0
Get the number of dimensions of register pressure.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned getNumRegs() const
Return the number of registers in this class.
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF) const
Returns the preferred order for allocating registers from this register class in MF.
unsigned getCostPerUse(unsigned RegNo) const
Return the additional cost of using this register instead of other registers in its class...
bool test(unsigned Idx) const
Definition: BitVector.h:502
unsigned computePSetLimit(unsigned Idx) const
This is not accurate because two overlapping register sets may have some nonoverlapping reserved regi...
virtual const int * getRegClassPressureSets(const TargetRegisterClass *RC) const =0
Get the dimensions of register pressure impacted by this register class.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
iterator_range< regclass_iterator > regclasses() const
unsigned getID() const
Return the register class ID number.
unsigned getNumRegClasses() const
virtual const TargetRegisterClass * getLargestLegalSuperClass(const TargetRegisterClass *RC, const MachineFunction &) const
Returns the largest super class of RC that is legal to use in the current sub-target and has the same...
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
MCRegAliasIterator enumerates all registers aliasing Reg.
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
virtual const RegClassWeight & getRegClassWeight(const TargetRegisterClass *RC) const =0
Get the weight in units of pressure for this register class.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
const BitVector & getReservedRegs() const
getReservedRegs - Returns a reference to the frozen set of reserved registers.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
virtual unsigned getRegPressureSetLimit(const MachineFunction &MF, unsigned Idx) const =0
Get the register unit pressure limit for this dimension.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:170
static cl::opt< unsigned > StressRA("stress-regalloc", cl::Hidden, cl::init(0), cl::value_desc("N"), cl::desc("Limit all regclasses to N registers"))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
#define DEBUG(X)
Definition: Debug.h:118
void resize(size_type N)
Definition: SmallVector.h:355