llvm/lib/CodeGen/RegAllocEvictionAdvisor.h

   1 //===- RegAllocEvictionAdvisor.h - Interference resolution ------*- C++ -*-===//
   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 #ifndef LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H
  10 #define LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H
  11
  12 #include "AllocationOrder.h"
  13 #include "llvm/ADT/IndexedMap.h"
  14 #include "llvm/ADT/SmallSet.h"
  15 #include "llvm/CodeGen/LiveInterval.h"
  16 #include "llvm/CodeGen/LiveIntervals.h"
  17 #include "llvm/CodeGen/LiveRegMatrix.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/CodeGen/Register.h"
  20 #include "llvm/CodeGen/TargetRegisterInfo.h"
  21 #include "llvm/Config/llvm-config.h"
  22 #include "llvm/Pass.h"
  23
  24 namespace llvm {
  25
  26 using SmallVirtRegSet = SmallSet<Register, 16>;
  27
  28 // Live ranges pass through a number of stages as we try to allocate them.
  29 // Some of the stages may also create new live ranges:
  30 //
  31 // - Region splitting.
  32 // - Per-block splitting.
  33 // - Local splitting.
  34 // - Spilling.
  35 //
  36 // Ranges produced by one of the stages skip the previous stages when they are
  37 // dequeued. This improves performance because we can skip interference checks
  38 // that are unlikely to give any results. It also guarantees that the live
  39 // range splitting algorithm terminates, something that is otherwise hard to
  40 // ensure.
  41 enum LiveRangeStage {
  42   /// Newly created live range that has never been queued.
  43   RS_New,
  44
  45   /// Only attempt assignment and eviction. Then requeue as RS_Split.
  46   RS_Assign,
  47
  48   /// Attempt live range splitting if assignment is impossible.
  49   RS_Split,
  50
  51   /// Attempt more aggressive live range splitting that is guaranteed to make
  52   /// progress.  This is used for split products that may not be making
  53   /// progress.
  54   RS_Split2,
  55
  56   /// Live range will be spilled.  No more splitting will be attempted.
  57   RS_Spill,
  58
  59   /// Live range is in memory. Because of other evictions, it might get moved
  60   /// in a register in the end.
  61   RS_Memory,
  62
  63   /// There is nothing more we can do to this live range.  Abort compilation
  64   /// if it can't be assigned.
  65   RS_Done
  66 };
  67
  68 /// Cost of evicting interference - used by default advisor, and the eviction
  69 /// chain heuristic in RegAllocGreedy.
  70 // FIXME: this can be probably made an implementation detail of the default
  71 // advisor, if the eviction chain logic can be refactored.
  72 struct EvictionCost {
  73   unsigned BrokenHints = 0; ///< Total number of broken hints.
  74   float MaxWeight = 0;      ///< Maximum spill weight evicted.
  75
  76   EvictionCost() = default;
  77
  78   bool isMax() const { return BrokenHints == ~0u; }
  79
  80   void setMax() { BrokenHints = ~0u; }
  81
  82   void setBrokenHints(unsigned NHints) { BrokenHints = NHints; }
  83
  84   bool operator<(const EvictionCost &O) const {
  85     return std::tie(BrokenHints, MaxWeight) <
  86            std::tie(O.BrokenHints, O.MaxWeight);
  87   }
  88 };
  89
  90 /// Interface to the eviction advisor, which is responsible for making a
  91 /// decision as to which live ranges should be evicted (if any).
  92 class RAGreedy;
  93 class RegAllocEvictionAdvisor {
  94 public:
  95   RegAllocEvictionAdvisor(const RegAllocEvictionAdvisor &) = delete;
  96   RegAllocEvictionAdvisor(RegAllocEvictionAdvisor &&) = delete;
  97   virtual ~RegAllocEvictionAdvisor() = default;
  98
  99   /// Find a physical register that can be freed by evicting the FixedRegisters,
 100   /// or return NoRegister. The eviction decision is assumed to be correct (i.e.
 101   /// no fixed live ranges are evicted) and profitable.
 102   virtual MCRegister tryFindEvictionCandidate(
 103       const LiveInterval &VirtReg, const AllocationOrder &Order,
 104       uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const = 0;
 105
 106   /// Find out if we can evict the live ranges occupying the given PhysReg,
 107   /// which is a hint (preferred register) for VirtReg.
 108   virtual bool
 109   canEvictHintInterference(const LiveInterval &VirtReg, MCRegister PhysReg,
 110                            const SmallVirtRegSet &FixedRegisters) const = 0;
 111
 112   /// Returns true if the given \p PhysReg is a callee saved register and has
 113   /// not been used for allocation yet.
 114   bool isUnusedCalleeSavedReg(MCRegister PhysReg) const;
 115
 116 protected:
 117   RegAllocEvictionAdvisor(const MachineFunction &MF, const RAGreedy &RA);
 118
 119   Register canReassign(const LiveInterval &VirtReg, Register PrevReg) const;
 120
 121   // Get the upper limit of elements in the given Order we need to analize.
 122   // TODO: is this heuristic,  we could consider learning it.
 123   Optional<unsigned> getOrderLimit(const LiveInterval &VirtReg,
 124                                    const AllocationOrder &Order,
 125                                    unsigned CostPerUseLimit) const;
 126
 127   // Determine if it's worth trying to allocate this reg, given the
 128   // CostPerUseLimit
 129   // TODO: this is a heuristic component we could consider learning, too.
 130   bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const;
 131
 132   const MachineFunction &MF;
 133   const RAGreedy &RA;
 134   LiveRegMatrix *const Matrix;
 135   LiveIntervals *const LIS;
 136   VirtRegMap *const VRM;
 137   MachineRegisterInfo *const MRI;
 138   const TargetRegisterInfo *const TRI;
 139   const RegisterClassInfo &RegClassInfo;
 140   const ArrayRef<uint8_t> RegCosts;
 141
 142   /// Run or not the local reassignment heuristic. This information is
 143   /// obtained from the TargetSubtargetInfo.
 144   const bool EnableLocalReassign;
 145
 146 private:
 147   unsigned NextCascade = 1;
 148 };
 149
 150 /// ImmutableAnalysis abstraction for fetching the Eviction Advisor. We model it
 151 /// as an analysis to decouple the user from the implementation insofar as
 152 /// dependencies on other analyses goes. The motivation for it being an
 153 /// immutable pass is twofold:
 154 /// - in the ML implementation case, the evaluator is stateless but (especially
 155 /// in the development mode) expensive to set up. With an immutable pass, we set
 156 /// it up once.
 157 /// - in the 'development' mode ML case, we want to capture the training log
 158 /// during allocation (this is a log of features encountered and decisions
 159 /// made), and then measure a score, potentially a few steps after allocation
 160 /// completes. So we need the properties of an immutable pass to keep the logger
 161 /// state around until we can make that measurement.
 162 ///
 163 /// Because we need to offer additional services in 'development' mode, the
 164 /// implementations of this analysis need to implement RTTI support.
 165 class RegAllocEvictionAdvisorAnalysis : public ImmutablePass {
 166 public:
 167   enum class AdvisorMode : int { Default, Release, Development };
 168
 169   RegAllocEvictionAdvisorAnalysis(AdvisorMode Mode)
 170       : ImmutablePass(ID), Mode(Mode){};
 171   static char ID;
 172
 173   /// Get an advisor for the given context (i.e. machine function, etc)
 174   virtual std::unique_ptr<RegAllocEvictionAdvisor>
 175   getAdvisor(const MachineFunction &MF, const RAGreedy &RA) = 0;
 176   AdvisorMode getAdvisorMode() const { return Mode; }
 177
 178 protected:
 179   // This analysis preserves everything, and subclasses may have additional
 180   // requirements.
 181   void getAnalysisUsage(AnalysisUsage &AU) const override {
 182     AU.setPreservesAll();
 183   }
 184
 185 private:
 186   StringRef getPassName() const override;
 187   const AdvisorMode Mode;
 188 };
 189
 190 /// Specialization for the API used by the analysis infrastructure to create
 191 /// an instance of the eviction advisor.
 192 template <> Pass *callDefaultCtor<RegAllocEvictionAdvisorAnalysis>();
 193
 194 RegAllocEvictionAdvisorAnalysis *createReleaseModeAdvisor();
 195
 196 RegAllocEvictionAdvisorAnalysis *createDevelopmentModeAdvisor();
 197
 198 // TODO: move to RegAllocEvictionAdvisor.cpp when we move implementation
 199 // out of RegAllocGreedy.cpp
 200 class DefaultEvictionAdvisor : public RegAllocEvictionAdvisor {
 201 public:
 202   DefaultEvictionAdvisor(const MachineFunction &MF, const RAGreedy &RA)
 203       : RegAllocEvictionAdvisor(MF, RA) {}
 204
 205 private:
 206   MCRegister tryFindEvictionCandidate(const LiveInterval &,
 207                                       const AllocationOrder &, uint8_t,
 208                                       const SmallVirtRegSet &) const override;
 209   bool canEvictHintInterference(const LiveInterval &, MCRegister,
 210                                 const SmallVirtRegSet &) const override;
 211   bool canEvictInterferenceBasedOnCost(const LiveInterval &, MCRegister, bool,
 212                                        EvictionCost &,
 213                                        const SmallVirtRegSet &) const;
 214   bool shouldEvict(const LiveInterval &A, bool, const LiveInterval &B,
 215                    bool) const;
 216 };
 217 } // namespace llvm
 218
 219 #endif // LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H