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