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