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