[NFC][regalloc] Introduce the RegAllocEvictionAdvisorAnalysis

[mtrofin]

Summary

This patch introduces the eviction analysis and the eviction advisor,
the default implementation, and the scaffolding for introducing the
other implementations of the advisor.

[mtrofin]

llvm/lib/CodeGen/RegAllocEvictionAdvisor.h

276

to clarify, I plan to do the TODO after figuring out the RegAllocGreedy.h (as probably this would go there instead).

[wenlei]

llvm/lib/CodeGen/RegAllocEvictionAdvisor.cpp

38–42

Can we keep this in greedy?

51–52

Why do we need hierarchy for analysis? I would imagine that the inputs for different advisor are similar, in which case, would it be cleaner if we use one analysis that dispatches to different advisor based on Mode/Kind? That is what InlineAdvisorAnalysis does.

89–90

LLVM_DEBUG

113–115

nit: move this piece below into a helper for use in both advisor and RAGreedy.

EnableLocalReassignment ||
                          MF.getSubtarget().enableRALocalReassignment(
                              MF.getTarget().getOptLevel())

This also reminds me of the advisor layer issue discussed in the previous patch. The advisor is tied to greedy. Would be good to address that soon.

llvm/lib/CodeGen/RegAllocEvictionAdvisor.h

238

nit: Kind->Mode to be consistent with inline advisor?

[mtrofin]

llvm/lib/CodeGen/RegAllocEvictionAdvisor.cpp

38–42

We can, and just pass it through. I can try that.

51–52

In the inliner case, the scope is module-wide, i.e. all the accounting and logging we do is per module. Here, advisors are per function, but we still need to have state shared by the ML advisors: the model evaluators (expensive to set up, cheap to use, and not tied to any particular function); and logs, in the training case, which are per-function, but we want to serialize them all once at doFinalization, to produce one file.

113–115

I could frontend that, but I'm not sure it would help in this case: we don't appear to be using this field anywhere else in RAGreedy, it's only used by the methods that would move with the default advisor. (Maybe I'm missing something though?)

[mtrofin]

llvm/lib/CodeGen/RegAllocEvictionAdvisor.cpp

89–90

I think we want to warn back to the user. Maybe we should instead mark somehow the created object (which can only be the Default anyway) and in its doInitialization, where we have a LLVMContext, emit an error? (not sure if there's a precedent)

alternatively: we can have the analysis as a final class and delegate to an implementation which we create in doInitialization. The implementation then can have additional requirements for doInitialization/doFinalization and getAnalysisUsage, if it needs.

wdyt?

[wenlei]

llvm/lib/CodeGen/RegAllocEvictionAdvisor.cpp

51–52

Okay, so IIUC, the states that need to be shared by advisors are specific to different Modes? Otherwise, we could still have a generic analysis.

I'm asking because by looking at the default analysis it doesn't seem necessary, but it might make sense if it's needed for the actual ML advisors.

89–90

I think we want to warn back to the user. Maybe we should instead mark somehow the created object (which can only be the Default anyway) and in its doInitialization, where we have a LLVMContext, emit an error? (not sure if there's a precedent)

It feels to me that this is just an intermediate state. The switch uses enum so it has to be one of the three values, then when all modes are implemented, such error path should never happen. If it's just to guard against misuse in this intermediate state, I guess an assertion is fine too as it's temporary anyways?

113–115

Took another look, you're right. sorry for the confusion.

[mtrofin]

llvm/lib/CodeGen/RegAllocEvictionAdvisor.cpp

51–52

Okay, so IIUC, the states that need to be shared by advisors are specific to different Modes?

Yes, that is correct. The Release mode would use an AOT-ed model evaluator. The Development mode uses an interpreted evaluator, and also has the logging infrastructure to manage. In that respect, it's akin to the InlineAdvisor.

Otherwise, we could still have a generic analysis.

I'm asking because by looking at the default analysis it doesn't seem necessary, but it might make sense if it's needed for the actual ML advisors.

Indeed, that's the

89–90

It's helpful for testing the flag works correctly. Also, because we need build opt-in for mlgo, it would be possible to build clang without it but then turn around and ask for 'release' mode, for example. We should message that to the user. I guess we could llvm_unreachable, too - basically, I just don't want to silently go to default.

One advantage of messaging through LLVMContext would be that we could easily turn the error into a warning, and also we avoid ICEing like llvm_unreachable does. I'll prototype something.

113–115

Ack. So we can then leave the flag definition here, too, correct?

[wenlei]

llvm/lib/CodeGen/RegAllocEvictionAdvisor.cpp

113–115

Sounds good.

[mtrofin]

Incorporated naming feedback, also handing unsupported advisor case through regular diagnostics mechanisms (Ctx.error)

[wenlei]

llvm/include/llvm/Analysis/ReplayInlineSettings.h

1 ↗

(On Diff #394924)

Is this an intentional change/refactor to include here?

[mtrofin]

removed unintended addition

llvm/include/llvm/Analysis/ReplayInlineSettings.h

1 ↗

(On Diff #394924)

no, thanks for the catch. forgot a git add and did a git checkout

[wenlei]

lgtm, thanks.

llvm/include/llvm/InitializePasses.h

 void initializePromoteLegacyPassPass(PassRegistry&);
 void initializePruneEHPass(PassRegistry&);
 void initializeRABasicPass(PassRegistry&);
 void initializePseudoProbeInserterPass(PassRegistry &);
 void initializeRAGreedyPass(PassRegistry&);
 void initializeReachingDefAnalysisPass(PassRegistry&);
 void initializeReassociateLegacyPassPass(PassRegistry&);
 void initializeRedundantDbgInstEliminationPass(PassRegistry&);
+void initializeRegAllocEvictionAdvisorAnalysisPass(PassRegistry &);
 void initializeRegAllocFastPass(PassRegistry&);
 void initializeRegBankSelectPass(PassRegistry&);
 void initializeRegToMemLegacyPass(PassRegistry&);
 void initializeRegUsageInfoCollectorPass(PassRegistry&);
 void initializeRegUsageInfoPropagationPass(PassRegistry&);
 void initializeRegionInfoPassPass(PassRegistry&);
 void initializeRegionOnlyPrinterPass(PassRegistry&);
 void initializeRegionOnlyViewerPass(PassRegistry&);

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   PseudoProbeInserter.cpp
   PseudoSourceValue.cpp
   RDFGraph.cpp
   RDFLiveness.cpp
   RDFRegisters.cpp
   ReachingDefAnalysis.cpp
   RegAllocBase.cpp
   RegAllocBasic.cpp
+  RegAllocEvictionAdvisor.cpp
   RegAllocFast.cpp
   RegAllocGreedy.cpp
   RegAllocPBQP.cpp
   RegAllocScore.cpp
   RegisterClassInfo.cpp
   RegisterCoalescer.cpp
   RegisterPressure.cpp
   RegisterScavenging.cpp

llvm/lib/CodeGen/RegAllocEvictionAdvisor.h

 #include "llvm/ADT/IndexedMap.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/LiveRegMatrix.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Register.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
+#include "llvm/Config/llvm-config.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
 
 using SmallVirtRegSet = SmallSet<Register, 16>;
 
 // Live ranges pass through a number of stages as we try to allocate them.
 // Some of the stages may also create new live ranges:
for (; Begin != End; ++Begin) {
       Register Reg = *Begin;
       Info.grow(Reg.id());
       if (Info[Reg].Stage == RS_New)
         Info[Reg].Stage = NewStage;
     }
   }
   void LRE_DidCloneVirtReg(Register New, Register Old);
 };
+
+/// Interface to the eviction advisor, which is responsible for making a
+/// decision as to which live ranges should be evicted (if any).
+class RegAllocEvictionAdvisor {
+public:
+  RegAllocEvictionAdvisor(const RegAllocEvictionAdvisor &) = delete;
+  RegAllocEvictionAdvisor(RegAllocEvictionAdvisor &&) = delete;
+  virtual ~RegAllocEvictionAdvisor() = default;
+
+  /// Find a physical register that can be freed by evicting the FixedRegisters,
+  /// or return NoRegister. The eviction decision is assumed to be correct (i.e.
+  /// no fixed live ranges are evicted) and profitable.
+  virtual MCRegister
+  tryFindEvictionCandidate(LiveInterval &VirtReg, const AllocationOrder &Order,
+                           uint8_t CostPerUseLimit,
+                           const SmallVirtRegSet &FixedRegisters) const = 0;
+
+  /// Find out if we can evict the live ranges occupying the given PhysReg,
+  /// which is a hint (preferred register) for VirtReg.
+  virtual bool
+  canEvictHintInterference(LiveInterval &VirtReg, MCRegister PhysReg,
+                           const SmallVirtRegSet &FixedRegisters) const = 0;
+
+  /// Returns true if the given \p PhysReg is a callee saved register and has
+  /// not been used for allocation yet.
+  bool isUnusedCalleeSavedReg(MCRegister PhysReg) const;
+
+protected:
+  RegAllocEvictionAdvisor(const MachineFunction &MF, LiveRegMatrix *Matrix,
+                          LiveIntervals *LIS, VirtRegMap *VRM,
+                          const RegisterClassInfo &RegClassInfo,
+                          ExtraRegInfo *ExtraInfo);
+
+  Register canReassign(LiveInterval &VirtReg, Register PrevReg) const;
+
+  const MachineFunction &MF;
+  LiveRegMatrix *const Matrix;
+  LiveIntervals *const LIS;
+  VirtRegMap *const VRM;
+  MachineRegisterInfo *const MRI;
+  const TargetRegisterInfo *const TRI;
+  const RegisterClassInfo &RegClassInfo;
+  const ArrayRef<uint8_t> RegCosts;
+  ExtraRegInfo *const ExtraInfo;
+
+  /// Run or not the local reassignment heuristic. This information is
+  /// obtained from the TargetSubtargetInfo.
+  const bool EnableLocalReassign;
+
+private:
+  unsigned NextCascade = 1;
+};
+
+/// ImmutableAnalysis abstraction for fetching the Eviction Advisor. We model it
+/// as an analysis to decouple the user from the implementation insofar as
+/// dependencies on other analyses goes. The motivation for it being an
+/// immutable pass is twofold:
+/// - in the ML implementation case, the evaluator is stateless but (especially
+/// in the development mode) expensive to set up. With an immutable pass, we set
+/// it up once.
+/// - in the 'development' mode ML case, we want to capture the training log
+/// during allocation (this is a log of features encountered and decisions
+/// made), and then measure a score, potentially a few steps after allocation
+/// completes. So we need the properties of an immutable pass to keep the logger
+/// state around until we can make that measurement.
+///
+/// Because we need to offer additional services in 'development' mode, the
+/// implementations of this analysis need to implement RTTI support.
+class RegAllocEvictionAdvisorAnalysis : public ImmutablePass {
+public:
+  enum class AdvisorKind : int { Default, Release, Development };
+
+  RegAllocEvictionAdvisorAnalysis(AdvisorKind Kind)
+      : ImmutablePass(ID), Kind(Kind){};
+  static char ID;
+
+  /// Get an advisor for the given context (i.e. machine function, etc)
+  virtual std::unique_ptr<RegAllocEvictionAdvisor>
+  getAdvisor(const MachineFunction &MF, LiveRegMatrix *Matrix,
+             LiveIntervals *LIS, VirtRegMap *VRM,
+             const RegisterClassInfo &RegClassInfo,
+             ExtraRegInfo *ExtraInfo) = 0;
+  AdvisorKind getAdvisorKind() const { return Kind; }
+
+private:
+  // This analysis preserves everything, and subclasses may have additional
+  // requirements.
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+
+  StringRef getPassName() const override;
+  const AdvisorKind Kind;
+};
+
+/// Specialization for the API used by the analysis infrastructure to create
+/// an instance of the eviction advisor.
+template <> Pass *callDefaultCtor<RegAllocEvictionAdvisorAnalysis>();
+
+// TODO(mtrofin): implement these.
+#ifdef LLVM_HAVE_TF_AOT
+RegAllocEvictionAdvisorAnalysis *createReleaseModeAdvisor();
+#endif
+
+#ifdef LLVM_HAVE_TF_API
+RegAllocEvictionAdvisorAnalysis *createDevelopmentModeAdvisor();
+#endif
+
+// TODO: move to RegAllocEvictionAdvisor.cpp when we move implementation
+// out of RegAllocGreedy.cpp
+class DefaultEvictionAdvisor : public RegAllocEvictionAdvisor {
+public:
+  DefaultEvictionAdvisor(const MachineFunction &MF, LiveRegMatrix *Matrix,
+                         LiveIntervals *LIS, VirtRegMap *VRM,
+                         const RegisterClassInfo &RegClassInfo,
+                         ExtraRegInfo *ExtraInfo)
+      : RegAllocEvictionAdvisor(MF, Matrix, LIS, VRM, RegClassInfo, ExtraInfo) {
+  }
+
+private:
+  MCRegister tryFindEvictionCandidate(LiveInterval &, const AllocationOrder &,
+                                      uint8_t,
+                                      const SmallVirtRegSet &) const override;
+  bool canEvictHintInterference(LiveInterval &, MCRegister,
+                                const SmallVirtRegSet &) const override;
+  bool canEvictInterferenceBasedOnCost(LiveInterval &, MCRegister, bool,
+                                       EvictionCost &,
+                                       const SmallVirtRegSet &) const;
+  bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool) const;
+};
 } // namespace llvm
 
 #endif // LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H

llvm/lib/CodeGen/RegAllocEvictionAdvisor.cpp

+//===- RegAllocEvictionAdvisor.cpp - eviction advisor ---------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of the default eviction advisor and of the Analysis pass.
+//
+//===----------------------------------------------------------------------===//
+
+#include "RegAllocEvictionAdvisor.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/RegisterClassInfo.h"
+#include "llvm/CodeGen/VirtRegMap.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/PassRegistry.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Target/TargetMachine.h"
+
+using namespace llvm;
+
+static cl::opt<RegAllocEvictionAdvisorAnalysis::AdvisorKind> Mode(
+    "regalloc-enable-advisor", cl::Hidden,
+    cl::init(RegAllocEvictionAdvisorAnalysis::AdvisorKind::Default),
+    cl::desc("Enable regalloc advisor mode"),
+    cl::values(
+        clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorKind::Default,
+                   "default", "Default"),
+        clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorKind::Release,
+                   "release", "precompiled"),
+        clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorKind::Development,
+                   "development", "for training")));
+
+static cl::opt<bool> EnableLocalReassignment(
+    "enable-local-reassign", cl::Hidden,
+    cl::desc("Local reassignment can yield better allocation decisions, but "
+             "may be compile time intensive"),
+    cl::init(false));
+
+#define DEBUG_TYPE "regalloc"
+
+char RegAllocEvictionAdvisorAnalysis::ID = 0;
+INITIALIZE_PASS(RegAllocEvictionAdvisorAnalysis, "regalloc-evict",
+                "Regalloc eviction policy", false, true)
+
+namespace {
+class DefaultEvictionAdvisorAnalysis final
+    : public RegAllocEvictionAdvisorAnalysis {
+public:
+  DefaultEvictionAdvisorAnalysis()
+      : RegAllocEvictionAdvisorAnalysis(AdvisorKind::Default) {}
+
+  // support for isa<> and dyn_cast.
+  static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
+    return R->getAdvisorKind() == AdvisorKind::Default;
+  }
+
+private:
+  std::unique_ptr<RegAllocEvictionAdvisor>
+  getAdvisor(const MachineFunction &MF, LiveRegMatrix *Matrix,
+             LiveIntervals *LIS, VirtRegMap *VRM,
+             const RegisterClassInfo &RegClassInfo,
+             ExtraRegInfo *ExtraInfo) override {
+    return std::make_unique<DefaultEvictionAdvisor>(MF, Matrix, LIS, VRM,
+                                                    RegClassInfo, ExtraInfo);
+  }
+};
+} // namespace
+
+template <> Pass *llvm::callDefaultCtor<RegAllocEvictionAdvisorAnalysis>() {
+  Pass *Ret = nullptr;
+  switch (Mode) {
+  case RegAllocEvictionAdvisorAnalysis::AdvisorKind::Default:
+    Ret = new DefaultEvictionAdvisorAnalysis();
+    break;
+  case RegAllocEvictionAdvisorAnalysis::AdvisorKind::Development:
+    // TODO(mtrofin): add implementation
+    break;
+  case RegAllocEvictionAdvisorAnalysis::AdvisorKind::Release:
+    // TODO(mtrofin): add implementation
+    break;
+  }
+  if (Ret)
+    return Ret;
+  dbgs() << "Requested regalloc eviction advisor analysis could be created. "
+            "Using default";
+  return new DefaultEvictionAdvisorAnalysis();
+}
+
+StringRef RegAllocEvictionAdvisorAnalysis::getPassName() const {
+  switch (getAdvisorKind()) {
+  case AdvisorKind::Default:
+    return "Default Regalloc Eviction Advisor";
+  case AdvisorKind::Release:
+    return "Release mode Regalloc Eviction Advisor";
+  case AdvisorKind::Development:
+    return "Development mode Regalloc Eviction Advisor";
+  }
+  llvm_unreachable("Unknown advisor kind");
+}
+
+RegAllocEvictionAdvisor::RegAllocEvictionAdvisor(
+    const MachineFunction &MF, LiveRegMatrix *Matrix, LiveIntervals *LIS,
+    VirtRegMap *VRM, const RegisterClassInfo &RegClassInfo,
+    ExtraRegInfo *ExtraInfo)
+    : MF(MF), Matrix(Matrix), LIS(LIS), VRM(VRM), MRI(&VRM->getRegInfo()),
+      TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RegClassInfo),
+      RegCosts(TRI->getRegisterCosts(MF)), ExtraInfo(ExtraInfo),
+      EnableLocalReassign(EnableLocalReassignment ||
+                          MF.getSubtarget().enableRALocalReassignment(
+                              MF.getTarget().getOptLevel())) {}

llvm/lib/CodeGen/RegAllocGreedy.cpp

static cl::opt<unsigned> LastChanceRecoloringMaxInterference(
     cl::init(8));
 
 static cl::opt<bool> ExhaustiveSearch(
     "exhaustive-register-search", cl::NotHidden,
     cl::desc("Exhaustive Search for registers bypassing the depth "
              "and interference cutoffs of last chance recoloring"),
     cl::Hidden);
 
-static cl::opt<bool> EnableLocalReassignment(
-    "enable-local-reassign", cl::Hidden,
-    cl::desc("Local reassignment can yield better allocation decisions, but "
-             "may be compile time intensive"),
-    cl::init(false));
-
 static cl::opt<bool> EnableDeferredSpilling(
     "enable-deferred-spilling", cl::Hidden,
     cl::desc("Instead of spilling a variable right away, defer the actual "
              "code insertion to the end of the allocation. That way the "
              "allocator might still find a suitable coloring for this "
              "variable because of other evicted variables."),
     cl::init(false));
 
class RAGreedy : public MachineFunctionPass,
   LiveDebugVariables *DebugVars;
   AliasAnalysis *AA;
 
   // state
   std::unique_ptr<Spiller> SpillerInstance;
   PQueue Queue;
   std::unique_ptr<VirtRegAuxInfo> VRAI;
   Optional<ExtraRegInfo> ExtraInfo;
+  std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor;
 
   // Enum CutOffStage to keep a track whether the register allocation failed
   // because of the cutoffs encountered in last chance recoloring.
   // Note: This is used as bitmask. New value should be next power of 2.
   enum CutOffStage {
     // No cutoffs encountered
     CO_None = 0,
 
#endif
 
   /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
   /// NoCand which indicates the stack interval.
   SmallVector<unsigned, 32> BundleCand;
 
   /// Callee-save register cost, calculated once per machine function.
   BlockFrequency CSRCost;
 
-  /// Run or not the local reassignment heuristic. This information is
-  /// obtained from the TargetSubtargetInfo.
-  bool EnableLocalReassign;
-
   /// Enable or not the consideration of the cost of local intervals created
   /// by a split candidate when choosing the best split candidate.
   bool EnableAdvancedRASplitCost;
 
   /// Set of broken hints that may be reconciled later because of eviction.
   SmallSetVector<LiveInterval *, 8> SetOfBrokenHints;
 
   /// The register cost values. This list will be recreated for each Machine
bool splitCanCauseLocalSpill(unsigned VirtRegToSplit,
                                GlobalSplitCandidate &Cand, unsigned BBNumber,
                                const AllocationOrder &Order);
   BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,
                                      const AllocationOrder &Order,
                                      bool *CanCauseEvictionChain);
   bool calcCompactRegion(GlobalSplitCandidate&);
   void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>);
   void calcGapWeights(MCRegister, SmallVectorImpl<float> &);
-  Register canReassign(LiveInterval &VirtReg, Register PrevReg) const;
-  bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool) const;
-  bool canEvictInterferenceBasedOnCost(LiveInterval &, MCRegister, bool,
-                                       EvictionCost &,
-                                       const SmallVirtRegSet &) const;
-  bool canEvictHintInterference(LiveInterval &, MCRegister,
-                                const SmallVirtRegSet &) const;
   bool canEvictInterferenceInRange(const LiveInterval &VirtReg,
                                    MCRegister PhysReg, SlotIndex Start,
                                    SlotIndex End, EvictionCost &MaxCost) const;
   MCRegister getCheapestEvicteeWeight(const AllocationOrder &Order,
                                       const LiveInterval &VirtReg,
                                       SlotIndex Start, SlotIndex End,
                                       float *BestEvictWeight) const;
   void evictInterference(LiveInterval &, MCRegister,
struct HintInfo {
     HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg)
         : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
   };
   using HintsInfo = SmallVector<HintInfo, 4>;
 
   BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);
   void collectHintInfo(Register, HintsInfo &);
 
-  bool isUnusedCalleeSavedReg(MCRegister PhysReg) const;
-
   /// Greedy RA statistic to remark.
   struct RAGreedyStats {
     unsigned Reloads = 0;
     unsigned FoldedReloads = 0;
     unsigned ZeroCostFoldedReloads = 0;
     unsigned Spills = 0;
     unsigned FoldedSpills = 0;
     unsigned Copies = 0;

 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
 INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix)
 INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
 INITIALIZE_PASS_DEPENDENCY(SpillPlacement)
 INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
+INITIALIZE_PASS_DEPENDENCY(RegAllocEvictionAdvisorAnalysis)
 INITIALIZE_PASS_END(RAGreedy, "greedy",
                 "Greedy Register Allocator", false, false)
 
 #ifndef NDEBUG
 const char *const RAGreedy::StageName[] = {
     "RS_New",
     "RS_Assign",
     "RS_Split",
void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addPreserved<MachineLoopInfo>();
   AU.addRequired<VirtRegMap>();
   AU.addPreserved<VirtRegMap>();
   AU.addRequired<LiveRegMatrix>();
   AU.addPreserved<LiveRegMatrix>();
   AU.addRequired<EdgeBundles>();
   AU.addRequired<SpillPlacement>();
   AU.addRequired<MachineOptimizationRemarkEmitterPass>();
+  AU.addRequired<RegAllocEvictionAdvisorAnalysis>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 //===----------------------------------------------------------------------===//
 //                     LiveRangeEdit delegate methods
 //===----------------------------------------------------------------------===//
 
 bool RAGreedy::LRE_CanEraseVirtReg(Register VirtReg) {
MCRegister RAGreedy::tryAssign(LiveInterval &VirtReg,
 
   // If we missed a simple hint, try to cheaply evict interference from the
   // preferred register.
   if (Register Hint = MRI->getSimpleHint(VirtReg.reg()))
     if (Order.isHint(Hint)) {
       MCRegister PhysHint = Hint.asMCReg();
       LLVM_DEBUG(dbgs() << "missed hint " << printReg(PhysHint, TRI) << '\n');
 
-      if (canEvictHintInterference(VirtReg, PhysHint, FixedRegisters)) {
+      if (EvictAdvisor->canEvictHintInterference(VirtReg, PhysHint,
+                                                 FixedRegisters)) {
         evictInterference(VirtReg, PhysHint, NewVRegs);
         return PhysHint;
       }
       // Record the missed hint, we may be able to recover
       // at the end if the surrounding allocation changed.
       SetOfBrokenHints.insert(&VirtReg);
     }
 
MCRegister RAGreedy::tryAssign(LiveInterval &VirtReg,
   MCRegister CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost, FixedRegisters);
   return CheapReg ? CheapReg : PhysReg;
 }
 
 //===----------------------------------------------------------------------===//
 //                         Interference eviction
 //===----------------------------------------------------------------------===//
 
-Register RAGreedy::canReassign(LiveInterval &VirtReg, Register PrevReg) const {
+Register RegAllocEvictionAdvisor::canReassign(LiveInterval &VirtReg,
+                                              Register PrevReg) const {
   auto Order =
       AllocationOrder::create(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
   MCRegister PhysReg;
   for (auto I = Order.begin(), E = Order.end(); I != E && !PhysReg; ++I) {
     if ((*I).id() == PrevReg.id())
       continue;
 
     MCRegUnitIterator Units(*I, TRI);

 /// Cascade numbers are used to prevent infinite loops if this function is a
 /// cyclic relation.
 ///
 /// @param A          The live range to be assigned.
 /// @param IsHint     True when A is about to be assigned to its preferred
 ///                   register.
 /// @param B          The live range to be evicted.
 /// @param BreaksHint True when B is already assigned to its preferred register.
-bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
-                           LiveInterval &B, bool BreaksHint) const {
+bool DefaultEvictionAdvisor::shouldEvict(LiveInterval &A, bool IsHint,
+                                         LiveInterval &B,
+                                         bool BreaksHint) const {
   bool CanSplit = ExtraInfo->getStage(B) < RS_Spill;
 
   // Be fairly aggressive about following hints as long as the evictee can be
   // split.
   if (CanSplit && IsHint && !BreaksHint)
     return true;
 
   if (A.weight() > B.weight()) {
     LLVM_DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight() << '\n');
     return true;
   }
   return false;
 }
 
 /// canEvictHintInterference - return true if the interference for VirtReg
 /// on the PhysReg, which is VirtReg's hint, can be evicted in favor of VirtReg.
-bool RAGreedy::canEvictHintInterference(
+bool DefaultEvictionAdvisor::canEvictHintInterference(
     LiveInterval &VirtReg, MCRegister PhysReg,
     const SmallVirtRegSet &FixedRegisters) const {
   EvictionCost MaxCost;
   MaxCost.setBrokenHints(1);
   return canEvictInterferenceBasedOnCost(VirtReg, PhysReg, true, MaxCost,
                                          FixedRegisters);
 }
 
 /// canEvictInterferenceBasedOnCost - Return true if all interferences between
 /// VirtReg and PhysReg can be evicted.
 ///
 /// @param VirtReg Live range that is about to be assigned.
 /// @param PhysReg Desired register for assignment.
 /// @param IsHint  True when PhysReg is VirtReg's preferred register.
 /// @param MaxCost Only look for cheaper candidates and update with new cost
 ///                when returning true.
 /// @returns True when interference can be evicted cheaper than MaxCost.
-bool RAGreedy::canEvictInterferenceBasedOnCost(
+bool DefaultEvictionAdvisor::canEvictInterferenceBasedOnCost(
     LiveInterval &VirtReg, MCRegister PhysReg, bool IsHint,
     EvictionCost &MaxCost, const SmallVirtRegSet &FixedRegisters) const {
   // It is only possible to evict virtual register interference.
   if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
     return false;
 
   bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
 
for (LiveInterval *Intf : Intfs) {
     ExtraInfo->setCascade(Intf->reg(), Cascade);
     ++NumEvicted;
     NewVRegs.push_back(Intf->reg());
   }
 }
 
 /// Returns true if the given \p PhysReg is a callee saved register and has not
 /// been used for allocation yet.
-bool RAGreedy::isUnusedCalleeSavedReg(MCRegister PhysReg) const {
+bool RegAllocEvictionAdvisor::isUnusedCalleeSavedReg(MCRegister PhysReg) const {
   MCRegister CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg);
   if (!CSR)
     return false;
 
   return !Matrix->isPhysRegUsed(PhysReg);
 }
 
-MCRegister RAGreedy::tryFindEvictionCandidate(
+MCRegister DefaultEvictionAdvisor::tryFindEvictionCandidate(
     LiveInterval &VirtReg, const AllocationOrder &Order,
     uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const {
   // Keep track of the cheapest interference seen so far.
   EvictionCost BestCost;
   BestCost.setMax();
   MCRegister BestPhys;
   unsigned OrderLimit = Order.getOrder().size();
 

 /// @return         Physreg to assign VirtReg, or 0.
 MCRegister RAGreedy::tryEvict(LiveInterval &VirtReg, AllocationOrder &Order,
                               SmallVectorImpl<Register> &NewVRegs,
                               uint8_t CostPerUseLimit,
                               const SmallVirtRegSet &FixedRegisters) {
   NamedRegionTimer T("evict", "Evict", TimerGroupName, TimerGroupDescription,
                      TimePassesIsEnabled);
 
-  MCRegister BestPhys =
-      tryFindEvictionCandidate(VirtReg, Order, CostPerUseLimit, FixedRegisters);
+  MCRegister BestPhys = EvictAdvisor->tryFindEvictionCandidate(
+      VirtReg, Order, CostPerUseLimit, FixedRegisters);
   if (BestPhys.isValid())
     evictInterference(VirtReg, BestPhys, NewVRegs);
   return BestPhys;
 }
 
 //===----------------------------------------------------------------------===//
 //                              Region Splitting
 //===----------------------------------------------------------------------===//

 unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg,
                                             AllocationOrder &Order,
                                             BlockFrequency &BestCost,
                                             unsigned &NumCands, bool IgnoreCSR,
                                             bool *CanCauseEvictionChain) {
   unsigned BestCand = NoCand;
   for (MCPhysReg PhysReg : Order) {
     assert(PhysReg);
-    if (IgnoreCSR && isUnusedCalleeSavedReg(PhysReg))
+    if (IgnoreCSR && EvictAdvisor->isUnusedCalleeSavedReg(PhysReg))
       continue;
 
     // Discard bad candidates before we run out of interference cache cursors.
     // This will only affect register classes with a lot of registers (>32).
     if (NumCands == IntfCache.getMaxCursors()) {
       unsigned WorstCount = ~0u;
       unsigned Worst = 0;
       for (unsigned CandIndex = 0; CandIndex != NumCands; ++CandIndex) {
auto Order =
       AllocationOrder::create(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
   if (MCRegister PhysReg =
           tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
     // If VirtReg got an assignment, the eviction info is no longer relevant.
     LastEvicted.clearEvicteeInfo(VirtReg.reg());
     // When NewVRegs is not empty, we may have made decisions such as evicting
     // a virtual register, go with the earlier decisions and use the physical
     // register.
-    if (CSRCost.getFrequency() && isUnusedCalleeSavedReg(PhysReg) &&
-        NewVRegs.empty()) {
+    if (CSRCost.getFrequency() &&
+        EvictAdvisor->isUnusedCalleeSavedReg(PhysReg) && NewVRegs.empty()) {
       MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
                                                 CostPerUseLimit, NewVRegs);
       if (CSRReg || !NewVRegs.empty())
         // Return now if we decide to use a CSR or create new vregs due to
         // pre-splitting.
         return CSRReg;
     } else
       return PhysReg;
bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
   LLVM_DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
                     << "********** Function: " << mf.getName() << '\n');
 
   MF = &mf;
   TRI = MF->getSubtarget().getRegisterInfo();
   TII = MF->getSubtarget().getInstrInfo();
   RCI.runOnMachineFunction(mf);
 
-  EnableLocalReassign = EnableLocalReassignment ||
-                        MF->getSubtarget().enableRALocalReassignment(
-                            MF->getTarget().getOptLevel());
-
   EnableAdvancedRASplitCost =
       ConsiderLocalIntervalCost.getNumOccurrences()
           ? ConsiderLocalIntervalCost
           : MF->getSubtarget().enableAdvancedRASplitCost();
 
   if (VerifyEnabled)
     MF->verify(this, "Before greedy register allocator");
 
bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
 
   VRAI->calculateSpillWeightsAndHints();
 
   LLVM_DEBUG(LIS->dump());
 
   SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
   SE.reset(new SplitEditor(*SA, *AA, *LIS, *VRM, *DomTree, *MBFI, *VRAI));
   ExtraInfo.emplace();
+  EvictAdvisor = getAnalysis<RegAllocEvictionAdvisorAnalysis>().getAdvisor(
+      *MF, Matrix, LIS, VRM, RegClassInfo, &*ExtraInfo);
   IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);
   GlobalCand.resize(32);  // This will grow as needed.
   SetOfBrokenHints.clear();
   LastEvicted.clear();
 
   allocatePhysRegs();
   tryHintsRecoloring();
 
   if (VerifyEnabled)
     MF->verify(this, "Before post optimization");
   postOptimization();
   reportStats();
 
   releaseMemory();
   return true;
 }

llvm/test/CodeGen/AArch64/O3-pipeline.ll

 ; RUN: llc --debugify-and-strip-all-safe=0 -mtriple=arm64-- -O3 -debug-pass=Structure < %s -o /dev/null 2>&1 | \
 ; RUN:     grep -v "Verify generated machine code" | FileCheck %s
 
 ; REQUIRES: asserts
 
 ; CHECK-LABEL: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT: Target Pass Configuration
 ; CHECK-NEXT: Machine Module Information
 ; CHECK-NEXT: Target Transform Information
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT: Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Create Garbage Collector Module Metadata
 ; CHECK-NEXT: Machine Branch Probability Analysis
+; CHECK-NEXT: Default Regalloc Eviction Advisor
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Pre-ISel Intrinsic Lowering
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Expand Atomic instructions
 ; CHECK-NEXT:     SVE intrinsics optimizations
 ; CHECK-NEXT:       FunctionPass Manager
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:     FunctionPass Manager

llvm/test/CodeGen/AMDGPU/llc-pipeline.ll

 ; GCN-O1-NEXT:AMDGPU Address space based Alias Analysis
 ; GCN-O1-NEXT:External Alias Analysis
 ; GCN-O1-NEXT:Type-Based Alias Analysis
 ; GCN-O1-NEXT:Scoped NoAlias Alias Analysis
 ; GCN-O1-NEXT:Argument Register Usage Information Storage
 ; GCN-O1-NEXT:Create Garbage Collector Module Metadata
 ; GCN-O1-NEXT:Machine Branch Probability Analysis
 ; GCN-O1-NEXT:Register Usage Information Storage
+; GCN-O1-NEXT:Default Regalloc Eviction Advisor
 ; GCN-O1-NEXT:  ModulePass Manager
 ; GCN-O1-NEXT:    Pre-ISel Intrinsic Lowering
 ; GCN-O1-NEXT:    AMDGPU Printf lowering
 ; GCN-O1-NEXT:      FunctionPass Manager
 ; GCN-O1-NEXT:        Dominator Tree Construction
 ; GCN-O1-NEXT:    Lower ctors and dtors for AMDGPU
 ; GCN-O1-NEXT:    Fix function bitcasts for AMDGPU
 ; GCN-O1-NEXT:    FunctionPass Manager

 ; GCN-O1-OPTS-NEXT:AMDGPU Address space based Alias Analysis
 ; GCN-O1-OPTS-NEXT:External Alias Analysis
 ; GCN-O1-OPTS-NEXT:Type-Based Alias Analysis
 ; GCN-O1-OPTS-NEXT:Scoped NoAlias Alias Analysis
 ; GCN-O1-OPTS-NEXT:Argument Register Usage Information Storage
 ; GCN-O1-OPTS-NEXT:Create Garbage Collector Module Metadata
 ; GCN-O1-OPTS-NEXT:Machine Branch Probability Analysis
 ; GCN-O1-OPTS-NEXT:Register Usage Information Storage
+; GCN-O1-OPTS-NEXT:Default Regalloc Eviction Advisor
 ; GCN-O1-OPTS-NEXT:  ModulePass Manager
 ; GCN-O1-OPTS-NEXT:    Pre-ISel Intrinsic Lowering
 ; GCN-O1-OPTS-NEXT:    AMDGPU Printf lowering
 ; GCN-O1-OPTS-NEXT:      FunctionPass Manager
 ; GCN-O1-OPTS-NEXT:        Dominator Tree Construction
 ; GCN-O1-OPTS-NEXT:    Lower ctors and dtors for AMDGPU
 ; GCN-O1-OPTS-NEXT:    Fix function bitcasts for AMDGPU
 ; GCN-O1-OPTS-NEXT:    FunctionPass Manager

 ; GCN-O2-NEXT:AMDGPU Address space based Alias Analysis
 ; GCN-O2-NEXT:External Alias Analysis
 ; GCN-O2-NEXT:Type-Based Alias Analysis
 ; GCN-O2-NEXT:Scoped NoAlias Alias Analysis
 ; GCN-O2-NEXT:Argument Register Usage Information Storage
 ; GCN-O2-NEXT:Create Garbage Collector Module Metadata
 ; GCN-O2-NEXT:Machine Branch Probability Analysis
 ; GCN-O2-NEXT:Register Usage Information Storage
+; GCN-O2-NEXT:Default Regalloc Eviction Advisor
 ; GCN-O2-NEXT:  ModulePass Manager
 ; GCN-O2-NEXT:    Pre-ISel Intrinsic Lowering
 ; GCN-O2-NEXT:    AMDGPU Printf lowering
 ; GCN-O2-NEXT:      FunctionPass Manager
 ; GCN-O2-NEXT:        Dominator Tree Construction
 ; GCN-O2-NEXT:    Lower ctors and dtors for AMDGPU
 ; GCN-O2-NEXT:    Fix function bitcasts for AMDGPU
 ; GCN-O2-NEXT:    FunctionPass Manager

 ; GCN-O3-NEXT:AMDGPU Address space based Alias Analysis
 ; GCN-O3-NEXT:External Alias Analysis
 ; GCN-O3-NEXT:Type-Based Alias Analysis
 ; GCN-O3-NEXT:Scoped NoAlias Alias Analysis
 ; GCN-O3-NEXT:Argument Register Usage Information Storage
 ; GCN-O3-NEXT:Create Garbage Collector Module Metadata
 ; GCN-O3-NEXT:Machine Branch Probability Analysis
 ; GCN-O3-NEXT:Register Usage Information Storage
+; GCN-O3-NEXT:Default Regalloc Eviction Advisor
 ; GCN-O3-NEXT:  ModulePass Manager
 ; GCN-O3-NEXT:    Pre-ISel Intrinsic Lowering
 ; GCN-O3-NEXT:    AMDGPU Printf lowering
 ; GCN-O3-NEXT:      FunctionPass Manager
 ; GCN-O3-NEXT:        Dominator Tree Construction
 ; GCN-O3-NEXT:    Lower ctors and dtors for AMDGPU
 ; GCN-O3-NEXT:    Fix function bitcasts for AMDGPU
 ; GCN-O3-NEXT:    FunctionPass Manager

llvm/test/CodeGen/Generic/llc-start-stop.ll

 ; STOP-BEFORE-NOT: Loop Strength Reduction
 
 ; RUN: llc < %s -debug-pass=Structure -start-after=loop-reduce -o /dev/null 2>&1 | FileCheck %s -check-prefix=START-AFTER
 ; START-AFTER: -aa -mergeicmps
 ; START-AFTER: FunctionPass Manager
 ; START-AFTER-NEXT: Dominator Tree Construction
 
 ; RUN: llc < %s -debug-pass=Structure -start-before=loop-reduce -o /dev/null 2>&1 | FileCheck %s -check-prefix=START-BEFORE
-; START-BEFORE: -machine-branch-prob -domtree
+; START-BEFORE: -machine-branch-prob -regalloc-evict -domtree
 ; START-BEFORE: FunctionPass Manager
 ; START-BEFORE: Loop Strength Reduction
 ; START-BEFORE-NEXT: Basic Alias Analysis (stateless AA impl)
 
 ; RUN: not --crash llc < %s -start-before=nonexistent -o /dev/null 2>&1 | FileCheck %s -check-prefix=NONEXISTENT-START-BEFORE
 ; RUN: not --crash llc < %s -stop-before=nonexistent -o /dev/null 2>&1 | FileCheck %s -check-prefix=NONEXISTENT-STOP-BEFORE
 ; RUN: not --crash llc < %s -start-after=nonexistent -o /dev/null 2>&1 | FileCheck %s -check-prefix=NONEXISTENT-START-AFTER
 ; RUN: not --crash llc < %s -stop-after=nonexistent -o /dev/null 2>&1 | FileCheck %s -check-prefix=NONEXISTENT-STOP-AFTER

llvm/test/CodeGen/MLRegalloc/default-eviction-advisor.ll

+; Check that, in the absence of dependencies, we emit an error message when
+; trying to use ML-driven advisor.
+; REQUIRES: !have_tf_aot
+; REQUIRES: !have_tf_api
+; RUN: llc -O2 -regalloc-enable-advisor=development < %s 2>&1 | FileCheck %s
+; RUN: llc -O2 -regalloc-enable-advisor=release < %s 2>&1 | FileCheck %s
+; RUN: llc -O2 -regalloc-enable-advisor=default < %s 2>&1 | FileCheck %s --check-prefix=DEFAULT
+
+define void @f2(i64 %lhs, i64 %rhs, i64* %addr) {
+  %sum = add i64 %lhs, %rhs
+  store i64 %sum, i64* %addr
+  ret void
+}
+
+; CHECK: Requested regalloc eviction advisor analysis could be created. Using default
+; DEFAULT-NOT: Requested regalloc eviction advisor analysis could be created. Using default
 No newline at end of file

llvm/test/CodeGen/PowerPC/O3-pipeline.ll

 ; RUN: llc --debugify-and-strip-all-safe=0 -mtriple=powerpc64-- -O3 \
 ; RUN:   -debug-pass=Structure < %s -o /dev/null 2>&1 | \
 ; RUN:   grep -v "Verify generated machine code" | FileCheck %s
 
 ; REQUIRES: asserts
 ; CHECK-LABEL: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT: Target Pass Configuration
 ; CHECK-NEXT: Machine Module Information
 ; CHECK-NEXT: Target Transform Information
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT: Create Garbage Collector Module Metadata
 ; CHECK-NEXT: Machine Branch Probability Analysis
+; CHECK-NEXT: Default Regalloc Eviction Advisor
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Pre-ISel Intrinsic Lowering
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Convert i1 constants to i32/i64 if they are returned
 ; CHECK-NEXT:       Expand Atomic instructions
 ; CHECK-NEXT:     PPC Lower MASS Entries
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction

 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Linux PPC Assembly Printer
 ; CHECK-NEXT:       Free MachineFunction
 
 define void @f() {
   ret void
 }
 No newline at end of file

llvm/test/CodeGen/X86/opt-pipeline.ll

 ; CHECK-NEXT: Machine Module Information
 ; CHECK-NEXT: Target Transform Information
 ; CHECK-NEXT: Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT: Create Garbage Collector Module Metadata
 ; CHECK-NEXT: Machine Branch Probability Analysis
+; CHECK-NEXT: Default Regalloc Eviction Advisor
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Pre-ISel Intrinsic Lowering
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Expand Atomic instructions
 ; CHECK-NEXT:       Lower AMX intrinsics
 ; CHECK-NEXT:       Lower AMX type for load/store
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       Dominator Tree Construction