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_TFLITE) 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(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 } 312