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
16#include "llvm/CodeGen/RegisterClassInfo.h"
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/BitVector.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/MachineRegisterInfo.h"
22#include "llvm/CodeGen/TargetRegisterInfo.h"
23#include "llvm/CodeGen/TargetSubtargetInfo.h"
24#include "llvm/InitializePasses.h"
25#include "llvm/Support/CommandLine.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/raw_ostream.h"
28#include <algorithm>
29#include <cassert>
30#include <cstdint>
31
32using namespace llvm;
33
34#define DEBUG_TYPE "regalloc"
35
36static cl::opt<unsigned>
37StressRA("stress-regalloc", cl::Hidden, cl::init(Val: 0), cl::value_desc("N"),
38 cl::desc("Limit all regclasses to N registers"));
39
40RegisterClassInfo::RegisterClassInfo() = default;
41
42void RegisterClassInfo::runOnMachineFunction(const MachineFunction &mf,
43 bool Rev) {
44 bool Update = false;
45 MF = &mf;
46
47 auto &STI = MF->getSubtarget();
48
49 // Allocate new array the first time we see a new target.
50 if (STI.getRegisterInfo() != TRI || Reverse != Rev) {
51 Reverse = Rev;
52 TRI = STI.getRegisterInfo();
53 RegClass.reset(p: new RCInfo[TRI->getNumRegClasses()]);
54 Update = true;
55 }
56
57 // Test if CSRs have changed from the previous function.
58 const MachineRegisterInfo &MRI = MF->getRegInfo();
59 const MCPhysReg *CSR = MRI.getCalleeSavedRegs();
60 bool CSRChanged = true;
61 if (!Update) {
62 CSRChanged = false;
63 size_t LastSize = LastCalleeSavedRegs.size();
64 for (unsigned I = 0;; ++I) {
65 if (CSR[I] == 0) {
66 CSRChanged = I != LastSize;
67 break;
68 }
69 if (I >= LastSize) {
70 CSRChanged = true;
71 break;
72 }
73 if (CSR[I] != LastCalleeSavedRegs[I]) {
74 CSRChanged = true;
75 break;
76 }
77 }
78 }
79
80 // Get the callee saved registers.
81 if (CSRChanged) {
82 LastCalleeSavedRegs.clear();
83 // Build a CSRAlias map. Every CSR alias saves the last
84 // overlapping CSR.
85 CalleeSavedAliases.assign(NumElts: TRI->getNumRegUnits(), Elt: 0);
86 for (const MCPhysReg *I = CSR; *I; ++I) {
87 for (MCRegUnit U : TRI->regunits(Reg: *I))
88 CalleeSavedAliases[static_cast<unsigned>(U)] = *I;
89 LastCalleeSavedRegs.push_back(Elt: *I);
90 }
91
92 Update = true;
93 }
94
95 // Even if CSR list is same, we could have had a different allocation order
96 // if the target's CSR allocation-order mask changes.
97 BitVector CSRHintsForAllocOrder;
98 STI.getCSRAllocationOrderMask(MF: mf, Mask&: CSRHintsForAllocOrder);
99 if (IgnoreCSRForAllocOrder != CSRHintsForAllocOrder) {
100 Update = true;
101 IgnoreCSRForAllocOrder = std::move(CSRHintsForAllocOrder);
102 }
103
104 RegCosts = TRI->getRegisterCosts(MF: *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(p: new unsigned[NumPSets]);
117 std::fill(first: &PSetLimits[0], last: &PSetLimits[NumPSets], value: 0);
118 ++Tag;
119 }
120}
121
122void RegisterClassInfo::updateReservedRegs(const BitVector &ReservedInput) {
123 assert(MF && TRI && RegClass &&
124 "RegisterClassInfo must be initialized before updating reserved regs");
125 assert(ReservedInput.size() == Reserved.size() &&
126 "Reserved register bit vectors must have the same size");
127 if (ReservedInput == Reserved)
128 return;
129
130 // Cached orders cannot regain unreserved registers; recompute them lazily.
131 bool OnlyNewReservations = Reserved.subsetOf(RHS: ReservedInput);
132
133 Reserved = ReservedInput;
134
135 // Pressure limits depend on the number of allocatable registers.
136 std::fill_n(first: PSetLimits.get(), n: TRI->getNumRegPressureSets(), value: 0);
137
138 // NumRegs may hide entries beyond the stress limit, so those orders cannot
139 // safely be compacted using only their visible prefix.
140 if (!OnlyNewReservations || StressRA) {
141 ++Tag;
142 return;
143 }
144
145 for (const TargetRegisterClass &RC : TRI->regclasses()) {
146 RCInfo &Info = RegClass[RC.getID()];
147
148 // Skip stale class information.
149 if (Info.Tag != Tag)
150 continue;
151
152 unsigned NewNumRegs = 0;
153 uint8_t MinCost = uint8_t(~0u);
154 uint8_t LastCost = uint8_t(~0u);
155 unsigned LastCostChange = 0;
156
157 for (unsigned I = 0; I != Info.NumRegs; ++I) {
158 MCPhysReg PhysReg = Info.Order[I];
159 if (Reserved.test(Idx: PhysReg))
160 continue;
161
162 uint8_t Cost = RegCosts[PhysReg];
163 MinCost = std::min(a: MinCost, b: Cost);
164 if (Cost != LastCost)
165 LastCostChange = NewNumRegs;
166
167 Info.Order[NewNumRegs++] = PhysReg;
168 LastCost = Cost;
169 }
170
171 Info.NumRegs = NewNumRegs;
172 Info.MinCost = MinCost;
173 Info.LastCostChange = LastCostChange;
174
175 Info.ProperSubClass = false;
176 if (const TargetRegisterClass *Super =
177 TRI->getLargestLegalSuperClass(RC: &RC, *MF))
178 if (Super != &RC && getNumAllocatableRegs(RC: Super) > Info.NumRegs)
179 Info.ProperSubClass = true;
180 }
181}
182
183/// compute - Compute the preferred allocation order for RC with reserved
184/// registers filtered out. Volatile registers come first followed by CSR
185/// aliases ordered according to the CSR order specified by the target.
186void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
187 assert(RC && "no register class given");
188 RCInfo &RCI = RegClass[RC->getID()];
189
190 // Raw register count, including all reserved regs.
191 unsigned NumRegs = RC->getNumRegs();
192
193 if (!RCI.Order)
194 RCI.Order.reset(p: new MCPhysReg[NumRegs]);
195
196 unsigned N = 0;
197 SmallVector<MCPhysReg, 16> CSRAlias;
198 uint8_t MinCost = uint8_t(~0u);
199 uint8_t LastCost = uint8_t(~0u);
200 unsigned LastCostChange = 0;
201
202 // FIXME: Once targets reserve registers instead of removing them from the
203 // allocation order, we can simply use begin/end here.
204 ArrayRef<MCPhysReg> RawOrder = TRI->getRawAllocationOrder(RC: *RC, *MF, Reverse);
205 for (unsigned PhysReg : reverse_conditionally(C&: RawOrder, ShouldReverse: Reverse)) {
206 // Remove reserved registers from the allocation order.
207 if (Reserved.test(Idx: PhysReg))
208 continue;
209 uint8_t Cost = RegCosts[PhysReg];
210 MinCost = std::min(a: MinCost, b: Cost);
211
212 if (getLastCalleeSavedAlias(PhysReg) &&
213 (IgnoreCSRForAllocOrder.empty() ||
214 !IgnoreCSRForAllocOrder.test(Idx: PhysReg)))
215 // PhysReg aliases a CSR, save it for later.
216 CSRAlias.push_back(Elt: PhysReg);
217 else {
218 if (Cost != LastCost)
219 LastCostChange = N;
220 RCI.Order[N++] = PhysReg;
221 LastCost = Cost;
222 }
223 }
224 RCI.NumRegs = N + CSRAlias.size();
225 assert(RCI.NumRegs <= NumRegs && "Allocation order larger than regclass");
226
227 // CSR aliases go after the volatile registers, preserve the target's order.
228 for (unsigned PhysReg : CSRAlias) {
229 uint8_t Cost = RegCosts[PhysReg];
230 if (Cost != LastCost)
231 LastCostChange = N;
232 RCI.Order[N++] = PhysReg;
233 LastCost = Cost;
234 }
235
236 // Register allocator stress test. Clip register class to N registers.
237 if (StressRA && RCI.NumRegs > StressRA)
238 RCI.NumRegs = StressRA;
239
240 // Check if RC is a proper sub-class.
241 if (const TargetRegisterClass *Super =
242 TRI->getLargestLegalSuperClass(RC, *MF))
243 if (Super != RC && getNumAllocatableRegs(RC: Super) > RCI.NumRegs)
244 RCI.ProperSubClass = true;
245
246 RCI.MinCost = MinCost;
247 RCI.LastCostChange = LastCostChange;
248
249 LLVM_DEBUG({
250 dbgs() << "AllocationOrder(" << TRI->getRegClassName(RC) << ") = [";
251 for (unsigned I = 0; I != RCI.NumRegs; ++I)
252 dbgs() << ' ' << printReg(RCI.Order[I], TRI);
253 dbgs() << (RCI.ProperSubClass ? " ] (sub-class)\n" : " ]\n");
254 });
255
256 // RCI is now up-to-date.
257 RCI.Tag = Tag;
258}
259
260/// This is not accurate because two overlapping register sets may have some
261/// nonoverlapping reserved registers. However, computing the allocation order
262/// for all register classes would be too expensive.
263unsigned RegisterClassInfo::computePSetLimit(unsigned Idx) const {
264 const TargetRegisterClass *RC = TRI->getLargestRegClassForRegPressureSet(Idx);
265 assert(RC && "Failed to find register class");
266 unsigned NAllocatableRegs = getNumAllocatableRegs(RC);
267 unsigned RegPressureSetLimit = TRI->getRegPressureSetLimit(MF: *MF, Idx);
268 // If all the regs are reserved, return raw RegPressureSetLimit.
269 // One example is VRSAVERC in PowerPC.
270 // Avoid returning zero, getRegPressureSetLimit(Idx) assumes computePSetLimit
271 // return non-zero value.
272 if (NAllocatableRegs == 0)
273 return RegPressureSetLimit;
274 unsigned NReserved = RC->getNumRegs() - NAllocatableRegs;
275 unsigned ReservedRegWeight = TRI->getRegClassWeight(RC).RegWeight * NReserved;
276 // A target-provided limit may already account for restricted register
277 // availability, such as an AMDGPU occupancy requirement. If the additional
278 // reserved-register adjustment would not leave a positive limit, preserve the
279 // target's nonzero limit; zero is the PSetLimits cache sentinel.
280 if (ReservedRegWeight >= RegPressureSetLimit)
281 return RegPressureSetLimit;
282 return RegPressureSetLimit - ReservedRegWeight;
283}
284
285INITIALIZE_PASS(MachineRegisterClassInfoWrapperPass,
286 "machine-register-class-info",
287 "Machine Register Class Info Analysis", true, true)
288
289MachineRegisterClassAnalysis::Result
290MachineRegisterClassAnalysis::run(MachineFunction &MF,
291 MachineFunctionAnalysisManager &) {
292 RegisterClassInfo RCI;
293 RCI.runOnMachineFunction(mf: MF);
294 return RCI;
295}
296
297char MachineRegisterClassInfoWrapperPass::ID = 0;
298
299MachineRegisterClassInfoWrapperPass::MachineRegisterClassInfoWrapperPass()
300 : MachineFunctionPass(ID), RCI() {
301 PassRegistry &Registry = *PassRegistry::getPassRegistry();
302 initializeMachineRegisterClassInfoWrapperPassPass(Registry);
303}
304
305bool MachineRegisterClassInfoWrapperPass::runOnMachineFunction(
306 MachineFunction &MF) {
307 RCI.runOnMachineFunction(mf: MF);
308 return false;
309}
310
311void MachineRegisterClassInfoWrapperPass::anchor() {}
312
313AnalysisKey MachineRegisterClassAnalysis::Key;
314