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