LLVM 19.0.0git
RegisterClassInfo.cpp
Go to the documentation of this file.
1//===- RegisterClassInfo.cpp - Dynamic Register Class Info ----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the RegisterClassInfo class which provides dynamic
10// information about target register classes. Callee-saved vs. caller-saved and
11// reserved registers depend on calling conventions and other dynamic
12// information, so some things cannot be determined statically.
13//
14//===----------------------------------------------------------------------===//
15
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/BitVector.h"
26#include "llvm/Support/Debug.h"
28#include <algorithm>
29#include <cassert>
30#include <cstdint>
31
32using namespace llvm;
33
34#define DEBUG_TYPE "regalloc"
35
37StressRA("stress-regalloc", cl::Hidden, cl::init(0), cl::value_desc("N"),
38 cl::desc("Limit all regclasses to N registers"));
39
41
43 bool Update = false;
44 MF = &mf;
45
46 auto &STI = MF->getSubtarget();
47
48 // Allocate new array the first time we see a new target.
49 if (STI.getRegisterInfo() != TRI) {
50 TRI = STI.getRegisterInfo();
51 RegClass.reset(new RCInfo[TRI->getNumRegClasses()]);
52 Update = true;
53 }
54
55 // Test if CSRs have changed from the previous function.
56 const MachineRegisterInfo &MRI = MF->getRegInfo();
57 const MCPhysReg *CSR = MRI.getCalleeSavedRegs();
58 bool CSRChanged = true;
59 if (!Update) {
60 CSRChanged = false;
61 size_t LastSize = LastCalleeSavedRegs.size();
62 for (unsigned I = 0;; ++I) {
63 if (CSR[I] == 0) {
64 CSRChanged = I != LastSize;
65 break;
66 }
67 if (I >= LastSize) {
68 CSRChanged = true;
69 break;
70 }
71 if (CSR[I] != LastCalleeSavedRegs[I]) {
72 CSRChanged = true;
73 break;
74 }
75 }
76 }
77
78 // Get the callee saved registers.
79 if (CSRChanged) {
80 LastCalleeSavedRegs.clear();
81 // Build a CSRAlias map. Every CSR alias saves the last
82 // overlapping CSR.
83 CalleeSavedAliases.assign(TRI->getNumRegUnits(), 0);
84 for (const MCPhysReg *I = CSR; *I; ++I) {
85 for (MCRegUnit U : TRI->regunits(*I))
86 CalleeSavedAliases[U] = *I;
87 LastCalleeSavedRegs.push_back(*I);
88 }
89
90 Update = true;
91 }
92
93 // Even if CSR list is same, we could have had a different allocation order
94 // if ignoreCSRForAllocationOrder is evaluated differently.
95 BitVector CSRHintsForAllocOrder(TRI->getNumRegs());
96 for (const MCPhysReg *I = CSR; *I; ++I)
97 for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI)
98 CSRHintsForAllocOrder[*AI] = STI.ignoreCSRForAllocationOrder(mf, *AI);
99 if (IgnoreCSRForAllocOrder != CSRHintsForAllocOrder) {
100 Update = true;
101 IgnoreCSRForAllocOrder = CSRHintsForAllocOrder;
102 }
103
104 RegCosts = TRI->getRegisterCosts(*MF);
105
106 // Different reserved registers?
107 const BitVector &RR = MF->getRegInfo().getReservedRegs();
108 if (RR != Reserved) {
109 Update = true;
110 Reserved = RR;
111 }
112
113 // Invalidate cached information from previous function.
114 if (Update) {
115 unsigned NumPSets = TRI->getNumRegPressureSets();
116 PSetLimits.reset(new unsigned[NumPSets]);
117 std::fill(&PSetLimits[0], &PSetLimits[NumPSets], 0);
118 ++Tag;
119 }
120}
121
122/// compute - Compute the preferred allocation order for RC with reserved
123/// registers filtered out. Volatile registers come first followed by CSR
124/// aliases ordered according to the CSR order specified by the target.
125void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
126 assert(RC && "no register class given");
127 RCInfo &RCI = RegClass[RC->getID()];
128 auto &STI = MF->getSubtarget();
129
130 // Raw register count, including all reserved regs.
131 unsigned NumRegs = RC->getNumRegs();
132
133 if (!RCI.Order)
134 RCI.Order.reset(new MCPhysReg[NumRegs]);
135
136 unsigned N = 0;
138 uint8_t MinCost = uint8_t(~0u);
139 uint8_t LastCost = uint8_t(~0u);
140 unsigned LastCostChange = 0;
141
142 // FIXME: Once targets reserve registers instead of removing them from the
143 // allocation order, we can simply use begin/end here.
144 ArrayRef<MCPhysReg> RawOrder = RC->getRawAllocationOrder(*MF);
145 for (unsigned PhysReg : RawOrder) {
146 // Remove reserved registers from the allocation order.
147 if (Reserved.test(PhysReg))
148 continue;
149 uint8_t Cost = RegCosts[PhysReg];
150 MinCost = std::min(MinCost, Cost);
151
152 if (getLastCalleeSavedAlias(PhysReg) &&
153 !STI.ignoreCSRForAllocationOrder(*MF, PhysReg))
154 // PhysReg aliases a CSR, save it for later.
155 CSRAlias.push_back(PhysReg);
156 else {
157 if (Cost != LastCost)
158 LastCostChange = N;
159 RCI.Order[N++] = PhysReg;
160 LastCost = Cost;
161 }
162 }
163 RCI.NumRegs = N + CSRAlias.size();
164 assert(RCI.NumRegs <= NumRegs && "Allocation order larger than regclass");
165
166 // CSR aliases go after the volatile registers, preserve the target's order.
167 for (unsigned PhysReg : CSRAlias) {
168 uint8_t Cost = RegCosts[PhysReg];
169 if (Cost != LastCost)
170 LastCostChange = N;
171 RCI.Order[N++] = PhysReg;
172 LastCost = Cost;
173 }
174
175 // Register allocator stress test. Clip register class to N registers.
176 if (StressRA && RCI.NumRegs > StressRA)
177 RCI.NumRegs = StressRA;
178
179 // Check if RC is a proper sub-class.
180 if (const TargetRegisterClass *Super =
181 TRI->getLargestLegalSuperClass(RC, *MF))
182 if (Super != RC && getNumAllocatableRegs(Super) > RCI.NumRegs)
183 RCI.ProperSubClass = true;
184
185 RCI.MinCost = MinCost;
186 RCI.LastCostChange = LastCostChange;
187
188 LLVM_DEBUG({
189 dbgs() << "AllocationOrder(" << TRI->getRegClassName(RC) << ") = [";
190 for (unsigned I = 0; I != RCI.NumRegs; ++I)
191 dbgs() << ' ' << printReg(RCI.Order[I], TRI);
192 dbgs() << (RCI.ProperSubClass ? " ] (sub-class)\n" : " ]\n");
193 });
194
195 // RCI is now up-to-date.
196 RCI.Tag = Tag;
197}
198
199/// This is not accurate because two overlapping register sets may have some
200/// nonoverlapping reserved registers. However, computing the allocation order
201/// for all register classes would be too expensive.
202unsigned RegisterClassInfo::computePSetLimit(unsigned Idx) const {
203 const TargetRegisterClass *RC = nullptr;
204 unsigned NumRCUnits = 0;
205 for (const TargetRegisterClass *C : TRI->regclasses()) {
206 const int *PSetID = TRI->getRegClassPressureSets(C);
207 for (; *PSetID != -1; ++PSetID) {
208 if ((unsigned)*PSetID == Idx)
209 break;
210 }
211 if (*PSetID == -1)
212 continue;
213
214 // Found a register class that counts against this pressure set.
215 // For efficiency, only compute the set order for the largest set.
216 unsigned NUnits = TRI->getRegClassWeight(C).WeightLimit;
217 if (!RC || NUnits > NumRCUnits) {
218 RC = C;
219 NumRCUnits = NUnits;
220 }
221 }
222 assert(RC && "Failed to find register class");
223 compute(RC);
224 unsigned NAllocatableRegs = getNumAllocatableRegs(RC);
225 unsigned RegPressureSetLimit = TRI->getRegPressureSetLimit(*MF, Idx);
226 // If all the regs are reserved, return raw RegPressureSetLimit.
227 // One example is VRSAVERC in PowerPC.
228 // Avoid returning zero, getRegPressureSetLimit(Idx) assumes computePSetLimit
229 // return non-zero value.
230 if (NAllocatableRegs == 0)
231 return RegPressureSetLimit;
232 unsigned NReserved = RC->getNumRegs() - NAllocatableRegs;
233 return RegPressureSetLimit - TRI->getRegClassWeight(RC).RegWeight * NReserved;
234}
unsigned const MachineRegisterInfo * MRI
This file implements the BitVector class.
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#define I(x, y, z)
Definition: MD5.cpp:58
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())
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool test(unsigned Idx) const
Definition: BitVector.h:461
MCRegAliasIterator enumerates all registers aliasing Reg.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
const BitVector & getReservedRegs() const
getReservedRegs - Returns a reference to the frozen set of reserved registers.
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
MCRegister getLastCalleeSavedAlias(MCRegister PhysReg) const
getLastCalleeSavedAlias - Returns the last callee saved register that overlaps PhysReg,...
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
unsigned computePSetLimit(unsigned Idx) const
This is not accurate because two overlapping register sets may have some nonoverlapping reserved regi...
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
unsigned getNumRegs() const
Return the number of registers in this class.
unsigned getID() const
Return the register class ID number.
ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF) const
Returns the preferred order for allocating registers from this register class in MF.
virtual unsigned getNumRegPressureSets() const =0
Get the number of dimensions of register pressure.
iterator_range< regclass_iterator > regclasses() const
ArrayRef< uint8_t > getRegisterCosts(const MachineFunction &MF) const
Get a list of cost values for all registers that correspond to the index returned by RegisterCostTabl...
unsigned getNumRegClasses() const
virtual const int * getRegClassPressureSets(const TargetRegisterClass *RC) const =0
Get the dimensions of register pressure impacted by this register class.
virtual const RegClassWeight & getRegClassWeight(const TargetRegisterClass *RC) const =0
Get the weight in units of pressure for this register class.
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...
virtual unsigned getRegPressureSetLimit(const MachineFunction &MF, unsigned Idx) const =0
Get the register unit pressure limit for this dimension.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
InstructionCost Cost
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
#define N