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(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(false));
45 
46 cl::opt<unsigned> EvictInterferenceCutoff(
47     "regalloc-eviction-max-interference-cutoff", cl::Hidden,
48     cl::desc("Number of interferences after which we declare "
49              "an interference unevictable and bail out. This "
50              "is a compilation cost-saving consideration. To "
51              "disable, pass a very large number."),
52     cl::init(10));
53 
54 #define DEBUG_TYPE "regalloc"
55 #ifdef LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL
56 #define LLVM_HAVE_TF_AOT
57 #endif
58 
59 char RegAllocEvictionAdvisorAnalysis::ID = 0;
60 INITIALIZE_PASS(RegAllocEvictionAdvisorAnalysis, "regalloc-evict",
61                 "Regalloc eviction policy", false, true)
62 
63 namespace {
64 class DefaultEvictionAdvisorAnalysis final
65     : public RegAllocEvictionAdvisorAnalysis {
66 public:
67   DefaultEvictionAdvisorAnalysis(bool NotAsRequested)
68       : RegAllocEvictionAdvisorAnalysis(AdvisorMode::Default),
69         NotAsRequested(NotAsRequested) {}
70 
71   // support for isa<> and dyn_cast.
72   static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
73     return R->getAdvisorMode() == AdvisorMode::Default;
74   }
75 
76 private:
77   std::unique_ptr<RegAllocEvictionAdvisor>
78   getAdvisor(const MachineFunction &MF, const RAGreedy &RA) override {
79     return std::make_unique<DefaultEvictionAdvisor>(MF, RA);
80   }
81   bool doInitialization(Module &M) override {
82     if (NotAsRequested)
83       M.getContext().emitError("Requested regalloc eviction advisor analysis "
84                                "could be created. Using default");
85     return RegAllocEvictionAdvisorAnalysis::doInitialization(M);
86   }
87   const bool NotAsRequested;
88 };
89 } // namespace
90 
91 template <> Pass *llvm::callDefaultCtor<RegAllocEvictionAdvisorAnalysis>() {
92   Pass *Ret = nullptr;
93   switch (Mode) {
94   case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default:
95     Ret = new DefaultEvictionAdvisorAnalysis(/*NotAsRequested*/ false);
96     break;
97   case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development:
98 #if defined(LLVM_HAVE_TF_API)
99     Ret = createDevelopmentModeAdvisor();
100 #endif
101     break;
102   case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release:
103 #if defined(LLVM_HAVE_TF_AOT)
104     Ret = createReleaseModeAdvisor();
105 #endif
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                               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(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(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(VirtReg.reg());
202 
203   EvictionCost Cost;
204   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
205     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
206     // If there is 10 or more interferences, chances are one is heavier.
207     const auto &Interferences = Q.interferingVRegs(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(Interferences)) {
213       assert(Register::isVirtualRegister(Intf->reg()) &&
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(Intf->reg()))
220         return false;
221 
222       // Never evict spill products. They cannot split or spill.
223       if (RA.getExtraInfo().getStage(*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(MRI->getRegClass(VirtReg.reg())) <
235                RegClassInfo.getNumAllocatableRegs(
236                    MRI->getRegClass(Intf->reg())));
237       // Only evict older cascades or live ranges without a cascade.
238       unsigned IntfCascade = RA.getExtraInfo().getCascade(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(Intf->reg());
251       // Update eviction cost.
252       Cost.BrokenHints += BreaksHint;
253       Cost.MaxWeight = std::max(Cost.MaxWeight, 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(VirtReg, IsHint, *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(*Intf) &&
266           (!EnableLocalReassign || !canReassign(*Intf, 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, false, 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