LLVM  8.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  Update = true;
53  }
54 
55  // Does this MF have different CSRs?
56  assert(TRI && "no register info set");
57 
58  // Get the callee saved registers.
59  const MCPhysReg *CSR = MF->getRegInfo().getCalleeSavedRegs();
60  if (Update || CSR != CalleeSavedRegs) {
61  // Build a CSRAlias map. Every CSR alias saves the last
62  // overlapping CSR.
63  CalleeSavedAliases.resize(TRI->getNumRegs(), 0);
64  for (const MCPhysReg *I = CSR; *I; ++I)
65  for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI)
66  CalleeSavedAliases[*AI] = *I;
67 
68  Update = true;
69  }
70  CalleeSavedRegs = CSR;
71 
72  // Different reserved registers?
73  const BitVector &RR = MF->getRegInfo().getReservedRegs();
74  if (Reserved.size() != RR.size() || RR != Reserved) {
75  Update = true;
76  Reserved = RR;
77  }
78 
79  // Invalidate cached information from previous function.
80  if (Update) {
81  unsigned NumPSets = TRI->getNumRegPressureSets();
82  PSetLimits.reset(new unsigned[NumPSets]);
83  std::fill(&PSetLimits[0], &PSetLimits[NumPSets], 0);
84  ++Tag;
85  }
86 }
87 
88 /// compute - Compute the preferred allocation order for RC with reserved
89 /// registers filtered out. Volatile registers come first followed by CSR
90 /// aliases ordered according to the CSR order specified by the target.
91 void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
92  assert(RC && "no register class given");
93  RCInfo &RCI = RegClass[RC->getID()];
94 
95  // Raw register count, including all reserved regs.
96  unsigned NumRegs = RC->getNumRegs();
97 
98  if (!RCI.Order)
99  RCI.Order.reset(new MCPhysReg[NumRegs]);
100 
101  unsigned N = 0;
103  unsigned MinCost = 0xff;
104  unsigned LastCost = ~0u;
105  unsigned LastCostChange = 0;
106 
107  // FIXME: Once targets reserve registers instead of removing them from the
108  // allocation order, we can simply use begin/end here.
109  ArrayRef<MCPhysReg> RawOrder = RC->getRawAllocationOrder(*MF);
110  for (unsigned i = 0; i != RawOrder.size(); ++i) {
111  unsigned PhysReg = RawOrder[i];
112  // Remove reserved registers from the allocation order.
113  if (Reserved.test(PhysReg))
114  continue;
115  unsigned Cost = TRI->getCostPerUse(PhysReg);
116  MinCost = std::min(MinCost, Cost);
117 
118  if (CalleeSavedAliases[PhysReg])
119  // PhysReg aliases a CSR, save it for later.
120  CSRAlias.push_back(PhysReg);
121  else {
122  if (Cost != LastCost)
123  LastCostChange = N;
124  RCI.Order[N++] = PhysReg;
125  LastCost = Cost;
126  }
127  }
128  RCI.NumRegs = N + CSRAlias.size();
129  assert(RCI.NumRegs <= NumRegs && "Allocation order larger than regclass");
130 
131  // CSR aliases go after the volatile registers, preserve the target's order.
132  for (unsigned i = 0, e = CSRAlias.size(); i != e; ++i) {
133  unsigned PhysReg = CSRAlias[i];
134  unsigned Cost = TRI->getCostPerUse(PhysReg);
135  if (Cost != LastCost)
136  LastCostChange = N;
137  RCI.Order[N++] = PhysReg;
138  LastCost = Cost;
139  }
140 
141  // Register allocator stress test. Clip register class to N registers.
142  if (StressRA && RCI.NumRegs > StressRA)
143  RCI.NumRegs = StressRA;
144 
145  // Check if RC is a proper sub-class.
146  if (const TargetRegisterClass *Super =
147  TRI->getLargestLegalSuperClass(RC, *MF))
148  if (Super != RC && getNumAllocatableRegs(Super) > RCI.NumRegs)
149  RCI.ProperSubClass = true;
150 
151  RCI.MinCost = uint8_t(MinCost);
152  RCI.LastCostChange = LastCostChange;
153 
154  LLVM_DEBUG({
155  dbgs() << "AllocationOrder(" << TRI->getRegClassName(RC) << ") = [";
156  for (unsigned I = 0; I != RCI.NumRegs; ++I)
157  dbgs() << ' ' << printReg(RCI.Order[I], TRI);
158  dbgs() << (RCI.ProperSubClass ? " ] (sub-class)\n" : " ]\n");
159  });
160 
161  // RCI is now up-to-date.
162  RCI.Tag = Tag;
163 }
164 
165 /// This is not accurate because two overlapping register sets may have some
166 /// nonoverlapping reserved registers. However, computing the allocation order
167 /// for all register classes would be too expensive.
168 unsigned RegisterClassInfo::computePSetLimit(unsigned Idx) const {
169  const TargetRegisterClass *RC = nullptr;
170  unsigned NumRCUnits = 0;
171  for (const TargetRegisterClass *C : TRI->regclasses()) {
172  const int *PSetID = TRI->getRegClassPressureSets(C);
173  for (; *PSetID != -1; ++PSetID) {
174  if ((unsigned)*PSetID == Idx)
175  break;
176  }
177  if (*PSetID == -1)
178  continue;
179 
180  // Found a register class that counts against this pressure set.
181  // For efficiency, only compute the set order for the largest set.
182  unsigned NUnits = TRI->getRegClassWeight(C).WeightLimit;
183  if (!RC || NUnits > NumRCUnits) {
184  RC = C;
185  NumRCUnits = NUnits;
186  }
187  }
188  compute(RC);
189  unsigned NReserved = RC->getNumRegs() - getNumAllocatableRegs(RC);
190  return TRI->getRegPressureSetLimit(*MF, Idx) -
191  TRI->getRegClassWeight(RC).RegWeight * NReserved;
192 }
uint64_t CallInst * C
virtual unsigned getNumRegPressureSets() const =0
Get the number of dimensions of register pressure.
This class represents lattice values for constants.
Definition: AllocatorList.h:24
unsigned getNumRegs() const
Return the number of registers in this class.
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.
void push_back(const T &Elt)
Definition: SmallVector.h:218
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.
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
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...
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:419
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.
size_t size() const
Definition: SmallVector.h:53
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:133
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 LLVM_DEBUG(X)
Definition: Debug.h:123
void resize(size_type N)
Definition: SmallVector.h:351