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