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