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 | |
26 | using namespace llvm; |
27 | |
28 | static 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 | |
40 | static 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 | |
46 | namespace llvm { |
47 | cl::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 | |
61 | char RegAllocEvictionAdvisorAnalysis::ID = 0; |
62 | INITIALIZE_PASS(RegAllocEvictionAdvisorAnalysis, "regalloc-evict" , |
63 | "Regalloc eviction policy" , false, true) |
64 | |
65 | namespace { |
66 | class DefaultEvictionAdvisorAnalysis final |
67 | : public RegAllocEvictionAdvisorAnalysis { |
68 | public: |
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 | |
78 | private: |
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 | |
93 | template <> 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 | |
113 | StringRef 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 | |
125 | RegAllocEvictionAdvisor::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. |
148 | bool 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. |
167 | bool 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. |
185 | bool 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 | |
275 | MCRegister 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 | |