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 
isMaxEvictionCost83   bool isMax() const { return BrokenHints == ~0u; }
84 
setMaxEvictionCost85   void setMax() { BrokenHints = ~0u; }
86 
setBrokenHintsEvictionCost87   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   bool canReassign(const LiveInterval &VirtReg, MCRegister FromReg) 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 
RegAllocEvictionAdvisorAnalysis(AdvisorMode Mode)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;
getAdvisorMode()178   AdvisorMode getAdvisorMode() const { return Mode; }
logRewardIfNeeded(const MachineFunction & MF,llvm::function_ref<float ()> GetReward)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.
getAnalysisUsage(AnalysisUsage & AU)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:
DefaultEvictionAdvisor(const MachineFunction & MF,const RAGreedy & RA)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