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