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