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 103 tryFindEvictionCandidate(LiveInterval &VirtReg, const AllocationOrder &Order, 104 uint8_t CostPerUseLimit, 105 const SmallVirtRegSet &FixedRegisters) const = 0; 106 107 /// Find out if we can evict the live ranges occupying the given PhysReg, 108 /// which is a hint (preferred register) for VirtReg. 109 virtual bool 110 canEvictHintInterference(LiveInterval &VirtReg, MCRegister PhysReg, 111 const SmallVirtRegSet &FixedRegisters) const = 0; 112 113 /// Returns true if the given \p PhysReg is a callee saved register and has 114 /// not been used for allocation yet. 115 bool isUnusedCalleeSavedReg(MCRegister PhysReg) const; 116 117 protected: 118 RegAllocEvictionAdvisor(MachineFunction &MF, const RAGreedy &RA); 119 120 Register canReassign(LiveInterval &VirtReg, Register PrevReg) const; 121 122 // Get the upper limit of elements in the given Order we need to analize. 123 // TODO: is this heuristic, we could consider learning it. 124 Optional<unsigned> getOrderLimit(const LiveInterval &VirtReg, 125 const AllocationOrder &Order, 126 unsigned CostPerUseLimit) const; 127 128 // Determine if it's worth trying to allocate this reg, given the 129 // CostPerUseLimit 130 // TODO: this is a heuristic component we could consider learning, too. 131 bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const; 132 133 const MachineFunction &MF; 134 const RAGreedy &RA; 135 LiveRegMatrix *const Matrix; 136 LiveIntervals *const LIS; 137 VirtRegMap *const VRM; 138 MachineRegisterInfo *const MRI; 139 const TargetRegisterInfo *const TRI; 140 const RegisterClassInfo &RegClassInfo; 141 const ArrayRef<uint8_t> RegCosts; 142 143 /// Run or not the local reassignment heuristic. This information is 144 /// obtained from the TargetSubtargetInfo. 145 const bool EnableLocalReassign; 146 147 private: 148 unsigned NextCascade = 1; 149 }; 150 151 /// ImmutableAnalysis abstraction for fetching the Eviction Advisor. We model it 152 /// as an analysis to decouple the user from the implementation insofar as 153 /// dependencies on other analyses goes. The motivation for it being an 154 /// immutable pass is twofold: 155 /// - in the ML implementation case, the evaluator is stateless but (especially 156 /// in the development mode) expensive to set up. With an immutable pass, we set 157 /// it up once. 158 /// - in the 'development' mode ML case, we want to capture the training log 159 /// during allocation (this is a log of features encountered and decisions 160 /// made), and then measure a score, potentially a few steps after allocation 161 /// completes. So we need the properties of an immutable pass to keep the logger 162 /// state around until we can make that measurement. 163 /// 164 /// Because we need to offer additional services in 'development' mode, the 165 /// implementations of this analysis need to implement RTTI support. 166 class RegAllocEvictionAdvisorAnalysis : public ImmutablePass { 167 public: 168 enum class AdvisorMode : int { Default, Release, Development }; 169 170 RegAllocEvictionAdvisorAnalysis(AdvisorMode Mode) 171 : ImmutablePass(ID), Mode(Mode){}; 172 static char ID; 173 174 /// Get an advisor for the given context (i.e. machine function, etc) 175 virtual std::unique_ptr<RegAllocEvictionAdvisor> 176 getAdvisor(MachineFunction &MF, const RAGreedy &RA) = 0; 177 AdvisorMode getAdvisorMode() const { return Mode; } 178 179 protected: 180 // This analysis preserves everything, and subclasses may have additional 181 // requirements. 182 void getAnalysisUsage(AnalysisUsage &AU) const override { 183 AU.setPreservesAll(); 184 } 185 186 private: 187 StringRef getPassName() const override; 188 const AdvisorMode Mode; 189 }; 190 191 /// Specialization for the API used by the analysis infrastructure to create 192 /// an instance of the eviction advisor. 193 template <> Pass *callDefaultCtor<RegAllocEvictionAdvisorAnalysis>(); 194 195 RegAllocEvictionAdvisorAnalysis *createReleaseModeAdvisor(); 196 197 RegAllocEvictionAdvisorAnalysis *createDevelopmentModeAdvisor(); 198 199 // TODO: move to RegAllocEvictionAdvisor.cpp when we move implementation 200 // out of RegAllocGreedy.cpp 201 class DefaultEvictionAdvisor : public RegAllocEvictionAdvisor { 202 public: 203 DefaultEvictionAdvisor(MachineFunction &MF, const RAGreedy &RA) 204 : RegAllocEvictionAdvisor(MF, RA) {} 205 206 private: 207 MCRegister tryFindEvictionCandidate(LiveInterval &, const AllocationOrder &, 208 uint8_t, 209 const SmallVirtRegSet &) const override; 210 bool canEvictHintInterference(LiveInterval &, MCRegister, 211 const SmallVirtRegSet &) const override; 212 bool canEvictInterferenceBasedOnCost(LiveInterval &, MCRegister, bool, 213 EvictionCost &, 214 const SmallVirtRegSet &) const; 215 bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool) const; 216 }; 217 } // namespace llvm 218 219 #endif // LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H 220