1//===- RegAllocEvictionAdvisor.cpp - eviction advisor ---------------------===//
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// Implementation of the default eviction advisor and of the Analysis pass.
10//
11//===----------------------------------------------------------------------===//
12
13#include "RegAllocEvictionAdvisor.h"
14#include "AllocationOrder.h"
15#include "RegAllocGreedy.h"
16#include "llvm/CodeGen/LiveRegMatrix.h"
17#include "llvm/CodeGen/MachineFunction.h"
18#include "llvm/CodeGen/RegisterClassInfo.h"
19#include "llvm/CodeGen/VirtRegMap.h"
20#include "llvm/InitializePasses.h"
21#include "llvm/Pass.h"
22#include "llvm/Support/CommandLine.h"
23#include "llvm/Support/ErrorHandling.h"
24#include "llvm/Target/TargetMachine.h"
25
26using namespace llvm;
27
28static cl::opt<RegAllocEvictionAdvisorAnalysis::AdvisorMode> Mode(
29 "regalloc-enable-advisor", cl::Hidden,
30 cl::init(Val: RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default),
31 cl::desc("Enable regalloc advisor mode"),
32 cl::values(
33 clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default,
34 "default", "Default"),
35 clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release,
36 "release", "precompiled"),
37 clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development,
38 "development", "for training")));
39
40static cl::opt<bool> EnableLocalReassignment(
41 "enable-local-reassign", cl::Hidden,
42 cl::desc("Local reassignment can yield better allocation decisions, but "
43 "may be compile time intensive"),
44 cl::init(Val: false));
45
46namespace llvm {
47cl::opt<unsigned> EvictInterferenceCutoff(
48 "regalloc-eviction-max-interference-cutoff", cl::Hidden,
49 cl::desc("Number of interferences after which we declare "
50 "an interference unevictable and bail out. This "
51 "is a compilation cost-saving consideration. To "
52 "disable, pass a very large number."),
53 cl::init(Val: 10));
54}
55
56#define DEBUG_TYPE "regalloc"
57#ifdef LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL
58#define LLVM_HAVE_TF_AOT
59#endif
60
61char RegAllocEvictionAdvisorAnalysis::ID = 0;
62INITIALIZE_PASS(RegAllocEvictionAdvisorAnalysis, "regalloc-evict",
63 "Regalloc eviction policy", false, true)
64
65namespace {
66class DefaultEvictionAdvisorAnalysis final
67 : public RegAllocEvictionAdvisorAnalysis {
68public:
69 DefaultEvictionAdvisorAnalysis(bool NotAsRequested)
70 : RegAllocEvictionAdvisorAnalysis(AdvisorMode::Default),
71 NotAsRequested(NotAsRequested) {}
72
73 // support for isa<> and dyn_cast.
74 static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
75 return R->getAdvisorMode() == AdvisorMode::Default;
76 }
77
78private:
79 std::unique_ptr<RegAllocEvictionAdvisor>
80 getAdvisor(const MachineFunction &MF, const RAGreedy &RA) override {
81 return std::make_unique<DefaultEvictionAdvisor>(args: MF, args: RA);
82 }
83 bool doInitialization(Module &M) override {
84 if (NotAsRequested)
85 M.getContext().emitError(ErrorStr: "Requested regalloc eviction advisor analysis "
86 "could not be created. Using default");
87 return RegAllocEvictionAdvisorAnalysis::doInitialization(M);
88 }
89 const bool NotAsRequested;
90};
91} // namespace
92
93template <> Pass *llvm::callDefaultCtor<RegAllocEvictionAdvisorAnalysis>() {
94 Pass *Ret = nullptr;
95 switch (Mode) {
96 case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default:
97 Ret = new DefaultEvictionAdvisorAnalysis(/*NotAsRequested*/ false);
98 break;
99 case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development:
100#if defined(LLVM_HAVE_TFLITE)
101 Ret = createDevelopmentModeAdvisor();
102#endif
103 break;
104 case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release:
105 Ret = createReleaseModeAdvisor();
106 break;
107 }
108 if (Ret)
109 return Ret;
110 return new DefaultEvictionAdvisorAnalysis(/*NotAsRequested*/ true);
111}
112
113StringRef RegAllocEvictionAdvisorAnalysis::getPassName() const {
114 switch (getAdvisorMode()) {
115 case AdvisorMode::Default:
116 return "Default Regalloc Eviction Advisor";
117 case AdvisorMode::Release:
118 return "Release mode Regalloc Eviction Advisor";
119 case AdvisorMode::Development:
120 return "Development mode Regalloc Eviction Advisor";
121 }
122 llvm_unreachable("Unknown advisor kind");
123}
124
125RegAllocEvictionAdvisor::RegAllocEvictionAdvisor(const MachineFunction &MF,
126 const RAGreedy &RA)
127 : MF(MF), RA(RA), Matrix(RA.getInterferenceMatrix()),
128 LIS(RA.getLiveIntervals()), VRM(RA.getVirtRegMap()),
129 MRI(&VRM->getRegInfo()), TRI(MF.getSubtarget().getRegisterInfo()),
130 RegClassInfo(RA.getRegClassInfo()), RegCosts(TRI->getRegisterCosts(MF)),
131 EnableLocalReassign(EnableLocalReassignment ||
132 MF.getSubtarget().enableRALocalReassignment(
133 OptLevel: MF.getTarget().getOptLevel())) {}
134
135/// shouldEvict - determine if A should evict the assigned live range B. The
136/// eviction policy defined by this function together with the allocation order
137/// defined by enqueue() decides which registers ultimately end up being split
138/// and spilled.
139///
140/// Cascade numbers are used to prevent infinite loops if this function is a
141/// cyclic relation.
142///
143/// @param A The live range to be assigned.
144/// @param IsHint True when A is about to be assigned to its preferred
145/// register.
146/// @param B The live range to be evicted.
147/// @param BreaksHint True when B is already assigned to its preferred register.
148bool DefaultEvictionAdvisor::shouldEvict(const LiveInterval &A, bool IsHint,
149 const LiveInterval &B,
150 bool BreaksHint) const {
151 bool CanSplit = RA.getExtraInfo().getStage(VirtReg: B) < RS_Spill;
152
153 // Be fairly aggressive about following hints as long as the evictee can be
154 // split.
155 if (CanSplit && IsHint && !BreaksHint)
156 return true;
157
158 if (A.weight() > B.weight()) {
159 LLVM_DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight() << '\n');
160 return true;
161 }
162 return false;
163}
164
165/// canEvictHintInterference - return true if the interference for VirtReg
166/// on the PhysReg, which is VirtReg's hint, can be evicted in favor of VirtReg.
167bool DefaultEvictionAdvisor::canEvictHintInterference(
168 const LiveInterval &VirtReg, MCRegister PhysReg,
169 const SmallVirtRegSet &FixedRegisters) const {
170 EvictionCost MaxCost;
171 MaxCost.setBrokenHints(1);
172 return canEvictInterferenceBasedOnCost(VirtReg, PhysReg, true, MaxCost,
173 FixedRegisters);
174}
175
176/// canEvictInterferenceBasedOnCost - Return true if all interferences between
177/// VirtReg and PhysReg can be evicted.
178///
179/// @param VirtReg Live range that is about to be assigned.
180/// @param PhysReg Desired register for assignment.
181/// @param IsHint True when PhysReg is VirtReg's preferred register.
182/// @param MaxCost Only look for cheaper candidates and update with new cost
183/// when returning true.
184/// @returns True when interference can be evicted cheaper than MaxCost.
185bool DefaultEvictionAdvisor::canEvictInterferenceBasedOnCost(
186 const LiveInterval &VirtReg, MCRegister PhysReg, bool IsHint,
187 EvictionCost &MaxCost, const SmallVirtRegSet &FixedRegisters) const {
188 // It is only possible to evict virtual register interference.
189 if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
190 return false;
191
192 bool IsLocal = VirtReg.empty() || LIS->intervalIsInOneMBB(LI: VirtReg);
193
194 // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
195 // involved in an eviction before. If a cascade number was assigned, deny
196 // evicting anything with the same or a newer cascade number. This prevents
197 // infinite eviction loops.
198 //
199 // This works out so a register without a cascade number is allowed to evict
200 // anything, and it can be evicted by anything.
201 unsigned Cascade = RA.getExtraInfo().getCascadeOrCurrentNext(Reg: VirtReg.reg());
202
203 EvictionCost Cost;
204 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
205 LiveIntervalUnion::Query &Q = Matrix->query(LR: VirtReg, RegUnit: Unit);
206 // If there is 10 or more interferences, chances are one is heavier.
207 const auto &Interferences = Q.interferingVRegs(MaxInterferingRegs: EvictInterferenceCutoff);
208 if (Interferences.size() >= EvictInterferenceCutoff)
209 return false;
210
211 // Check if any interfering live range is heavier than MaxWeight.
212 for (const LiveInterval *Intf : reverse(C: Interferences)) {
213 assert(Intf->reg().isVirtual() &&
214 "Only expecting virtual register interference from query");
215
216 // Do not allow eviction of a virtual register if we are in the middle
217 // of last-chance recoloring and this virtual register is one that we
218 // have scavenged a physical register for.
219 if (FixedRegisters.count(V: Intf->reg()))
220 return false;
221
222 // Never evict spill products. They cannot split or spill.
223 if (RA.getExtraInfo().getStage(VirtReg: *Intf) == RS_Done)
224 return false;
225 // Once a live range becomes small enough, it is urgent that we find a
226 // register for it. This is indicated by an infinite spill weight. These
227 // urgent live ranges get to evict almost anything.
228 //
229 // Also allow urgent evictions of unspillable ranges from a strictly
230 // larger allocation order.
231 bool Urgent =
232 !VirtReg.isSpillable() &&
233 (Intf->isSpillable() ||
234 RegClassInfo.getNumAllocatableRegs(RC: MRI->getRegClass(Reg: VirtReg.reg())) <
235 RegClassInfo.getNumAllocatableRegs(
236 RC: MRI->getRegClass(Reg: Intf->reg())));
237 // Only evict older cascades or live ranges without a cascade.
238 unsigned IntfCascade = RA.getExtraInfo().getCascade(Reg: Intf->reg());
239 if (Cascade == IntfCascade)
240 return false;
241
242 if (Cascade < IntfCascade) {
243 if (!Urgent)
244 return false;
245 // We permit breaking cascades for urgent evictions. It should be the
246 // last resort, though, so make it really expensive.
247 Cost.BrokenHints += 10;
248 }
249 // Would this break a satisfied hint?
250 bool BreaksHint = VRM->hasPreferredPhys(VirtReg: Intf->reg());
251 // Update eviction cost.
252 Cost.BrokenHints += BreaksHint;
253 Cost.MaxWeight = std::max(a: Cost.MaxWeight, b: Intf->weight());
254 // Abort if this would be too expensive.
255 if (!(Cost < MaxCost))
256 return false;
257 if (Urgent)
258 continue;
259 // Apply the eviction policy for non-urgent evictions.
260 if (!shouldEvict(A: VirtReg, IsHint, B: *Intf, BreaksHint))
261 return false;
262 // If !MaxCost.isMax(), then we're just looking for a cheap register.
263 // Evicting another local live range in this case could lead to suboptimal
264 // coloring.
265 if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(LI: *Intf) &&
266 (!EnableLocalReassign || !canReassign(VirtReg: *Intf, FromReg: PhysReg))) {
267 return false;
268 }
269 }
270 }
271 MaxCost = Cost;
272 return true;
273}
274
275MCRegister DefaultEvictionAdvisor::tryFindEvictionCandidate(
276 const LiveInterval &VirtReg, const AllocationOrder &Order,
277 uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const {
278 // Keep track of the cheapest interference seen so far.
279 EvictionCost BestCost;
280 BestCost.setMax();
281 MCRegister BestPhys;
282 auto MaybeOrderLimit = getOrderLimit(VirtReg, Order, CostPerUseLimit);
283 if (!MaybeOrderLimit)
284 return MCRegister::NoRegister;
285 unsigned OrderLimit = *MaybeOrderLimit;
286
287 // When we are just looking for a reduced cost per use, don't break any
288 // hints, and only evict smaller spill weights.
289 if (CostPerUseLimit < uint8_t(~0u)) {
290 BestCost.BrokenHints = 0;
291 BestCost.MaxWeight = VirtReg.weight();
292 }
293
294 for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit); I != E;
295 ++I) {
296 MCRegister PhysReg = *I;
297 assert(PhysReg);
298 if (!canAllocatePhysReg(CostPerUseLimit, PhysReg) ||
299 !canEvictInterferenceBasedOnCost(VirtReg, PhysReg, IsHint: false, MaxCost&: BestCost,
300 FixedRegisters))
301 continue;
302
303 // Best so far.
304 BestPhys = PhysReg;
305
306 // Stop if the hint can be used.
307 if (I.isHint())
308 break;
309 }
310 return BestPhys;
311}
312

source code of llvm/lib/CodeGen/RegAllocEvictionAdvisor.cpp