370 lines · 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-exception6//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 28using namespace llvm;29 30static 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 43static 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 49namespace llvm {50cl::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_REGALLOCEVICTMODEL61#define LLVM_HAVE_TF_AOT62#endif63 64char RegAllocEvictionAdvisorAnalysisLegacy::ID = 0;65INITIALIZE_PASS(RegAllocEvictionAdvisorAnalysisLegacy, "regalloc-evict",66 "Regalloc eviction policy", false, true)67 68namespace {69class DefaultEvictionAdvisorProvider final70 : public RegAllocEvictionAdvisorProvider {71public: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 91class DefaultEvictionAdvisorAnalysisLegacy final92 : public RegAllocEvictionAdvisorAnalysisLegacy {93public: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 109private:110 const bool NotAsRequested;111};112} // namespace113 114AnalysisKey RegAllocEvictionAdvisorAnalysis::Key;115 116void 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#else129 Provider.reset(130 new DefaultEvictionAdvisorProvider(/*NotAsRequested=*/true, Ctx));131#endif132 return;133 case RegAllocEvictionAdvisorAnalysisLegacy::AdvisorMode::Release:134 Provider.reset(createReleaseModeAdvisorProvider(Ctx));135 return;136 }137}138 139RegAllocEvictionAdvisorAnalysis::Result140RegAllocEvictionAdvisorAnalysis::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 147template <>148Pass *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 supported155 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#else163 return new DefaultEvictionAdvisorAnalysisLegacy(/*NotAsRequested=*/true);164#endif165 }166 llvm_unreachable("unexpected advisor mode");167}168 169StringRef 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 181RegAllocEvictionAdvisor::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. The192/// eviction policy defined by this function together with the allocation order193/// defined by enqueue() decides which registers ultimately end up being split194/// and spilled.195///196/// Cascade numbers are used to prevent infinite loops if this function is a197/// 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 preferred201/// register.202/// @param B The live range to be evicted.203/// @param BreaksHint True when B is already assigned to its preferred register.204bool 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 be210 // 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 VirtReg222/// on the PhysReg, which is VirtReg's hint, can be evicted in favor of VirtReg.223bool DefaultEvictionAdvisor::canEvictHintInterference(224 const LiveInterval &VirtReg, MCRegister PhysReg,225 const SmallVirtRegSet &FixedRegisters) const {226 EvictionCost MaxCost;227 MaxCost.setBrokenHints(MRI->getRegClass(VirtReg.reg())->getCopyCost());228 return canEvictInterferenceBasedOnCost(VirtReg, PhysReg, true, MaxCost,229 FixedRegisters);230}231 232/// canEvictInterferenceBasedOnCost - Return true if all interferences between233/// 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 cost239/// when returning true.240/// @returns True when interference can be evicted cheaper than MaxCost.241bool 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 never251 // involved in an eviction before. If a cascade number was assigned, deny252 // evicting anything with the same or a newer cascade number. This prevents253 // infinite eviction loops.254 //255 // This works out so a register without a cascade number is allowed to evict256 // 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 middle273 // of last-chance recoloring and this virtual register is one that we274 // 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 a282 // register for it. This is indicated by an infinite spill weight. These283 // urgent live ranges get to evict almost anything.284 //285 // Also allow urgent evictions of unspillable ranges from a strictly286 // 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 the302 // last resort, though, so make it really expensive.303 Cost.BrokenHints += 10 * MRI->getRegClass(Intf->reg())->getCopyCost();304 }305 // Would this break a satisfied hint?306 bool BreaksHint = VRM->hasPreferredPhys(Intf->reg());307 // Update eviction cost.308 if (BreaksHint)309 Cost.BrokenHints += MRI->getRegClass(Intf->reg())->getCopyCost();310 311 Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight());312 // Abort if this would be too expensive.313 if (Cost >= MaxCost)314 return false;315 if (Urgent)316 continue;317 // Apply the eviction policy for non-urgent evictions.318 if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))319 return false;320 // If !MaxCost.isMax(), then we're just looking for a cheap register.321 // Evicting another local live range in this case could lead to suboptimal322 // coloring.323 if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&324 (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {325 return false;326 }327 }328 }329 MaxCost = Cost;330 return true;331}332 333MCRegister DefaultEvictionAdvisor::tryFindEvictionCandidate(334 const LiveInterval &VirtReg, const AllocationOrder &Order,335 uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const {336 // Keep track of the cheapest interference seen so far.337 EvictionCost BestCost;338 BestCost.setMax();339 MCRegister BestPhys;340 auto MaybeOrderLimit = getOrderLimit(VirtReg, Order, CostPerUseLimit);341 if (!MaybeOrderLimit)342 return MCRegister::NoRegister;343 unsigned OrderLimit = *MaybeOrderLimit;344 345 // When we are just looking for a reduced cost per use, don't break any346 // hints, and only evict smaller spill weights.347 if (CostPerUseLimit < uint8_t(~0u)) {348 BestCost.BrokenHints = 0;349 BestCost.MaxWeight = VirtReg.weight();350 }351 352 for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit); I != E;353 ++I) {354 MCRegister PhysReg = *I;355 assert(PhysReg);356 if (!canAllocatePhysReg(CostPerUseLimit, PhysReg) ||357 !canEvictInterferenceBasedOnCost(VirtReg, PhysReg, false, BestCost,358 FixedRegisters))359 continue;360 361 // Best so far.362 BestPhys = PhysReg;363 364 // Stop if the hint can be used.365 if (I.isHint())366 break;367 }368 return BestPhys;369}370