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