LLVM 20.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).id()] =
99 STI.ignoreCSRForAllocationOrder(mf, *AI);
100 if (IgnoreCSRForAllocOrder != CSRHintsForAllocOrder) {
101 Update = true;
102 IgnoreCSRForAllocOrder = CSRHintsForAllocOrder;
103 }
104
105 RegCosts = TRI->getRegisterCosts(*MF);
106
107 // Different reserved registers?
108 const BitVector &RR = MF->getRegInfo().getReservedRegs();
109 if (RR != Reserved) {
110 Update = true;
111 Reserved = RR;
112 }
113
114 // Invalidate cached information from previous function.
115 if (Update) {
116 unsigned NumPSets = TRI->getNumRegPressureSets();
117 PSetLimits.reset(new unsigned[NumPSets]);
118 std::fill(&PSetLimits[0], &PSetLimits[NumPSets], 0);
119 ++Tag;
120 }
121}
122
123/// compute - Compute the preferred allocation order for RC with reserved
124/// registers filtered out. Volatile registers come first followed by CSR
125/// aliases ordered according to the CSR order specified by the target.
126void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
127 assert(RC && "no register class given");
128 RCInfo &RCI = RegClass[RC->getID()];
129 auto &STI = MF->getSubtarget();
130
131 // Raw register count, including all reserved regs.
132 unsigned NumRegs = RC->getNumRegs();
133
134 if (!RCI.Order)
135 RCI.Order.reset(new MCPhysReg[NumRegs]);
136
137 unsigned N = 0;
139 uint8_t MinCost = uint8_t(~0u);
140 uint8_t LastCost = uint8_t(~0u);
141 unsigned LastCostChange = 0;
142
143 // FIXME: Once targets reserve registers instead of removing them from the
144 // allocation order, we can simply use begin/end here.
145 ArrayRef<MCPhysReg> RawOrder = RC->getRawAllocationOrder(*MF);
146 for (unsigned PhysReg : RawOrder) {
147 // Remove reserved registers from the allocation order.
148 if (Reserved.test(PhysReg))
149 continue;
150 uint8_t Cost = RegCosts[PhysReg];
151 MinCost = std::min(MinCost, Cost);
152
153 if (getLastCalleeSavedAlias(PhysReg) &&
154 !STI.ignoreCSRForAllocationOrder(*MF, PhysReg))
155 // PhysReg aliases a CSR, save it for later.
156 CSRAlias.push_back(PhysReg);
157 else {
158 if (Cost != LastCost)
159 LastCostChange = N;
160 RCI.Order[N++] = PhysReg;
161 LastCost = Cost;
162 }
163 }
164 RCI.NumRegs = N + CSRAlias.size();
165 assert(RCI.NumRegs <= NumRegs && "Allocation order larger than regclass");
166
167 // CSR aliases go after the volatile registers, preserve the target's order.
168 for (unsigned PhysReg : CSRAlias) {
169 uint8_t Cost = RegCosts[PhysReg];
170 if (Cost != LastCost)
171 LastCostChange = N;
172 RCI.Order[N++] = PhysReg;
173 LastCost = Cost;
174 }
175
176 // Register allocator stress test. Clip register class to N registers.
177 if (StressRA && RCI.NumRegs > StressRA)
178 RCI.NumRegs = StressRA;
179
180 // Check if RC is a proper sub-class.
181 if (const TargetRegisterClass *Super =
182 TRI->getLargestLegalSuperClass(RC, *MF))
183 if (Super != RC && getNumAllocatableRegs(Super) > RCI.NumRegs)
184 RCI.ProperSubClass = true;
185
186 RCI.MinCost = MinCost;
187 RCI.LastCostChange = LastCostChange;
188
189 LLVM_DEBUG({
190 dbgs() << "AllocationOrder(" << TRI->getRegClassName(RC) << ") = [";
191 for (unsigned I = 0; I != RCI.NumRegs; ++I)
192 dbgs() << ' ' << printReg(RCI.Order[I], TRI);
193 dbgs() << (RCI.ProperSubClass ? " ] (sub-class)\n" : " ]\n");
194 });
195
196 // RCI is now up-to-date.
197 RCI.Tag = Tag;
198}
199
200/// This is not accurate because two overlapping register sets may have some
201/// nonoverlapping reserved registers. However, computing the allocation order
202/// for all register classes would be too expensive.
203unsigned RegisterClassInfo::computePSetLimit(unsigned Idx) const {
204 const TargetRegisterClass *RC = nullptr;
205 unsigned NumRCUnits = 0;
206 for (const TargetRegisterClass *C : TRI->regclasses()) {
207 const int *PSetID = TRI->getRegClassPressureSets(C);
208 for (; *PSetID != -1; ++PSetID) {
209 if ((unsigned)*PSetID == Idx)
210 break;
211 }
212 if (*PSetID == -1)
213 continue;
214
215 // Found a register class that counts against this pressure set.
216 // For efficiency, only compute the set order for the largest set.
217 unsigned NUnits = TRI->getRegClassWeight(C).WeightLimit;
218 if (!RC || NUnits > NumRCUnits) {
219 RC = C;
220 NumRCUnits = NUnits;
221 }
222 }
223 assert(RC && "Failed to find register class");
224 compute(RC);
225 unsigned NAllocatableRegs = getNumAllocatableRegs(RC);
226 unsigned RegPressureSetLimit = TRI->getRegPressureSetLimit(*MF, Idx);
227 // If all the regs are reserved, return raw RegPressureSetLimit.
228 // One example is VRSAVERC in PowerPC.
229 // Avoid returning zero, getRegPressureSetLimit(Idx) assumes computePSetLimit
230 // return non-zero value.
231 if (NAllocatableRegs == 0)
232 return RegPressureSetLimit;
233 unsigned NReserved = RC->getNumRegs() - NAllocatableRegs;
234 return RegPressureSetLimit - TRI->getRegClassWeight(RC).RegWeight * NReserved;
235}
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(...)
Definition: Debug.h:106
#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:78
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
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:443
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