llvm/lib/CodeGen/RegAllocEvictionAdvisor.cpp

   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 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(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>(MF, RA);
  82   }
  83   bool doInitialization(Module &M) override {
  84     if (NotAsRequested)
  85       M.getContext().emitError("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                               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 (MCRegUnit Unit : TRI->regunits(PhysReg)) {
 205     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, Unit);
 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(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(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 }