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