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