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/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:
  70   DefaultEvictionAdvisorAnalysis(bool NotAsRequested)
  71       : RegAllocEvictionAdvisorAnalysis(AdvisorMode::Default),
  72         NotAsRequested(NotAsRequested) {}
  73
  74   // support for isa<> and dyn_cast.
  75   static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
  76     return R->getAdvisorMode() == AdvisorMode::Default;
  77   }
  78
  79 private:
  80   std::unique_ptr<RegAllocEvictionAdvisor>
  81   getAdvisor(const MachineFunction &MF, const RAGreedy &RA) override {
  82     return std::make_unique<DefaultEvictionAdvisor>(MF, RA);
  83   }
  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
  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
 114 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
 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.
 149 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 << '\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.
 168 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.
 186 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
 276 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 }