1 //==- RegAllocGreedy.h ------- greedy register allocator  ----------*-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 // This file defines the RAGreedy function pass for register allocation in
9 // optimized builds.
10 //===----------------------------------------------------------------------===//
11 
12 #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_
13 #define LLVM_CODEGEN_REGALLOCGREEDY_H_
14 
15 #include "InterferenceCache.h"
16 #include "RegAllocBase.h"
17 #include "RegAllocEvictionAdvisor.h"
18 #include "SpillPlacement.h"
19 #include "SplitKit.h"
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/BitVector.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/IndexedMap.h"
24 #include "llvm/ADT/SetVector.h"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/ADT/StringRef.h"
28 #include "llvm/CodeGen/CalcSpillWeights.h"
29 #include "llvm/CodeGen/LiveInterval.h"
30 #include "llvm/CodeGen/LiveRangeEdit.h"
31 #include "llvm/CodeGen/MachineFunction.h"
32 #include "llvm/CodeGen/MachineFunctionPass.h"
33 #include "llvm/CodeGen/RegisterClassInfo.h"
34 #include "llvm/CodeGen/Spiller.h"
35 #include "llvm/CodeGen/TargetRegisterInfo.h"
36 #include <algorithm>
37 #include <cstdint>
38 #include <memory>
39 #include <queue>
40 #include <utility>
41 
42 namespace llvm {
43 class AllocationOrder;
44 class AnalysisUsage;
45 class EdgeBundles;
46 class LiveDebugVariables;
47 class LiveIntervals;
48 class LiveRegMatrix;
49 class MachineBasicBlock;
50 class MachineBlockFrequencyInfo;
51 class MachineDominatorTree;
52 class MachineLoop;
53 class MachineLoopInfo;
54 class MachineOptimizationRemarkEmitter;
55 class MachineOptimizationRemarkMissed;
56 class SlotIndexes;
57 class TargetInstrInfo;
58 class VirtRegMap;
59 
60 class LLVM_LIBRARY_VISIBILITY RAGreedy : public MachineFunctionPass,
61                                          public RegAllocBase,
62                                          private LiveRangeEdit::Delegate {
63   // Interface to eviction advisers
64 public:
65   /// Track allocation stage and eviction loop prevention during allocation.
66   class ExtraRegInfo final {
67     // RegInfo - Keep additional information about each live range.
68     struct RegInfo {
69       LiveRangeStage Stage = RS_New;
70 
71       // Cascade - Eviction loop prevention. See
72       // canEvictInterferenceBasedOnCost().
73       unsigned Cascade = 0;
74 
75       RegInfo() = default;
76     };
77 
78     IndexedMap<RegInfo, VirtReg2IndexFunctor> Info;
79     unsigned NextCascade = 1;
80 
81   public:
82     ExtraRegInfo() = default;
83     ExtraRegInfo(const ExtraRegInfo &) = delete;
84 
85     LiveRangeStage getStage(Register Reg) const { return Info[Reg].Stage; }
86 
87     LiveRangeStage getStage(const LiveInterval &VirtReg) const {
88       return getStage(VirtReg.reg());
89     }
90 
91     void setStage(Register Reg, LiveRangeStage Stage) {
92       Info.grow(Reg.id());
93       Info[Reg].Stage = Stage;
94     }
95 
96     void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
97       setStage(VirtReg.reg(), Stage);
98     }
99 
100     /// Return the current stage of the register, if present, otherwise
101     /// initialize it and return that.
102     LiveRangeStage getOrInitStage(Register Reg) {
103       Info.grow(Reg.id());
104       return getStage(Reg);
105     }
106 
107     unsigned getCascade(Register Reg) const { return Info[Reg].Cascade; }
108 
109     void setCascade(Register Reg, unsigned Cascade) {
110       Info.grow(Reg.id());
111       Info[Reg].Cascade = Cascade;
112     }
113 
114     unsigned getOrAssignNewCascade(Register Reg) {
115       unsigned Cascade = getCascade(Reg);
116       if (!Cascade) {
117         Cascade = NextCascade++;
118         setCascade(Reg, Cascade);
119       }
120       return Cascade;
121     }
122 
123     unsigned getCascadeOrCurrentNext(Register Reg) const {
124       unsigned Cascade = getCascade(Reg);
125       if (!Cascade)
126         Cascade = NextCascade;
127       return Cascade;
128     }
129 
130     template <typename Iterator>
131     void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
132       for (; Begin != End; ++Begin) {
133         Register Reg = *Begin;
134         Info.grow(Reg.id());
135         if (Info[Reg].Stage == RS_New)
136           Info[Reg].Stage = NewStage;
137       }
138     }
139     void LRE_DidCloneVirtReg(Register New, Register Old);
140   };
141 
142   LiveRegMatrix *getInterferenceMatrix() const { return Matrix; }
143   LiveIntervals *getLiveIntervals() const { return LIS; }
144   VirtRegMap *getVirtRegMap() const { return VRM; }
145   const RegisterClassInfo &getRegClassInfo() const { return RegClassInfo; }
146   const ExtraRegInfo &getExtraInfo() const { return *ExtraInfo; }
147   size_t getQueueSize() const { return Queue.size(); }
148   // end (interface to eviction advisers)
149 
150 private:
151   // Convenient shortcuts.
152   using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;
153   using SmallLISet = SmallPtrSet<const LiveInterval *, 4>;
154 
155   // We need to track all tentative recolorings so we can roll back any
156   // successful and unsuccessful recoloring attempts.
157   using RecoloringStack =
158       SmallVector<std::pair<const LiveInterval *, MCRegister>, 8>;
159 
160   // context
161   MachineFunction *MF;
162 
163   // Shortcuts to some useful interface.
164   const TargetInstrInfo *TII;
165 
166   // analyses
167   SlotIndexes *Indexes;
168   MachineBlockFrequencyInfo *MBFI;
169   MachineDominatorTree *DomTree;
170   MachineLoopInfo *Loops;
171   MachineOptimizationRemarkEmitter *ORE;
172   EdgeBundles *Bundles;
173   SpillPlacement *SpillPlacer;
174   LiveDebugVariables *DebugVars;
175 
176   // state
177   std::unique_ptr<Spiller> SpillerInstance;
178   PQueue Queue;
179   std::unique_ptr<VirtRegAuxInfo> VRAI;
180   Optional<ExtraRegInfo> ExtraInfo;
181   std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor;
182 
183   // Enum CutOffStage to keep a track whether the register allocation failed
184   // because of the cutoffs encountered in last chance recoloring.
185   // Note: This is used as bitmask. New value should be next power of 2.
186   enum CutOffStage {
187     // No cutoffs encountered
188     CO_None = 0,
189 
190     // lcr-max-depth cutoff encountered
191     CO_Depth = 1,
192 
193     // lcr-max-interf cutoff encountered
194     CO_Interf = 2
195   };
196 
197   uint8_t CutOffInfo;
198 
199 #ifndef NDEBUG
200   static const char *const StageName[];
201 #endif
202 
203   // splitting state.
204   std::unique_ptr<SplitAnalysis> SA;
205   std::unique_ptr<SplitEditor> SE;
206 
207   /// Cached per-block interference maps
208   InterferenceCache IntfCache;
209 
210   /// All basic blocks where the current register has uses.
211   SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
212 
213   /// Global live range splitting candidate info.
214   struct GlobalSplitCandidate {
215     // Register intended for assignment, or 0.
216     MCRegister PhysReg;
217 
218     // SplitKit interval index for this candidate.
219     unsigned IntvIdx;
220 
221     // Interference for PhysReg.
222     InterferenceCache::Cursor Intf;
223 
224     // Bundles where this candidate should be live.
225     BitVector LiveBundles;
226     SmallVector<unsigned, 8> ActiveBlocks;
227 
228     void reset(InterferenceCache &Cache, MCRegister Reg) {
229       PhysReg = Reg;
230       IntvIdx = 0;
231       Intf.setPhysReg(Cache, Reg);
232       LiveBundles.clear();
233       ActiveBlocks.clear();
234     }
235 
236     // Set B[I] = C for every live bundle where B[I] was NoCand.
237     unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
238       unsigned Count = 0;
239       for (unsigned I : LiveBundles.set_bits())
240         if (B[I] == NoCand) {
241           B[I] = C;
242           Count++;
243         }
244       return Count;
245     }
246   };
247 
248   /// Candidate info for each PhysReg in AllocationOrder.
249   /// This vector never shrinks, but grows to the size of the largest register
250   /// class.
251   SmallVector<GlobalSplitCandidate, 32> GlobalCand;
252 
253   enum : unsigned { NoCand = ~0u };
254 
255   /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
256   /// NoCand which indicates the stack interval.
257   SmallVector<unsigned, 32> BundleCand;
258 
259   /// Callee-save register cost, calculated once per machine function.
260   BlockFrequency CSRCost;
261 
262   /// Set of broken hints that may be reconciled later because of eviction.
263   SmallSetVector<const LiveInterval *, 8> SetOfBrokenHints;
264 
265   /// The register cost values. This list will be recreated for each Machine
266   /// Function
267   ArrayRef<uint8_t> RegCosts;
268 
269   /// Flags for the live range priority calculation, determined once per
270   /// machine function.
271   bool RegClassPriorityTrumpsGlobalness;
272 
273 public:
274   RAGreedy(const RegClassFilterFunc F = allocateAllRegClasses);
275 
276   /// Return the pass name.
277   StringRef getPassName() const override { return "Greedy Register Allocator"; }
278 
279   /// RAGreedy analysis usage.
280   void getAnalysisUsage(AnalysisUsage &AU) const override;
281   void releaseMemory() override;
282   Spiller &spiller() override { return *SpillerInstance; }
283   void enqueueImpl(const LiveInterval *LI) override;
284   const LiveInterval *dequeue() override;
285   MCRegister selectOrSplit(const LiveInterval &,
286                            SmallVectorImpl<Register> &) override;
287   void aboutToRemoveInterval(const LiveInterval &) override;
288 
289   /// Perform register allocation.
290   bool runOnMachineFunction(MachineFunction &mf) override;
291 
292   MachineFunctionProperties getRequiredProperties() const override {
293     return MachineFunctionProperties().set(
294         MachineFunctionProperties::Property::NoPHIs);
295   }
296 
297   MachineFunctionProperties getClearedProperties() const override {
298     return MachineFunctionProperties().set(
299         MachineFunctionProperties::Property::IsSSA);
300   }
301 
302   static char ID;
303 
304 private:
305   MCRegister selectOrSplitImpl(const LiveInterval &,
306                                SmallVectorImpl<Register> &, SmallVirtRegSet &,
307                                RecoloringStack &, unsigned = 0);
308 
309   bool LRE_CanEraseVirtReg(Register) override;
310   void LRE_WillShrinkVirtReg(Register) override;
311   void LRE_DidCloneVirtReg(Register, Register) override;
312   void enqueue(PQueue &CurQueue, const LiveInterval *LI);
313   const LiveInterval *dequeue(PQueue &CurQueue);
314 
315   bool hasVirtRegAlloc();
316   BlockFrequency calcSpillCost();
317   bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency &);
318   bool addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
319   bool growRegion(GlobalSplitCandidate &Cand);
320   BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,
321                                      const AllocationOrder &Order);
322   bool calcCompactRegion(GlobalSplitCandidate &);
323   void splitAroundRegion(LiveRangeEdit &, ArrayRef<unsigned>);
324   void calcGapWeights(MCRegister, SmallVectorImpl<float> &);
325   void evictInterference(const LiveInterval &, MCRegister,
326                          SmallVectorImpl<Register> &);
327   bool mayRecolorAllInterferences(MCRegister PhysReg,
328                                   const LiveInterval &VirtReg,
329                                   SmallLISet &RecoloringCandidates,
330                                   const SmallVirtRegSet &FixedRegisters);
331 
332   MCRegister tryAssign(const LiveInterval &, AllocationOrder &,
333                        SmallVectorImpl<Register> &, const SmallVirtRegSet &);
334   MCRegister tryEvict(const LiveInterval &, AllocationOrder &,
335                       SmallVectorImpl<Register> &, uint8_t,
336                       const SmallVirtRegSet &);
337   MCRegister tryRegionSplit(const LiveInterval &, AllocationOrder &,
338                             SmallVectorImpl<Register> &);
339   /// Calculate cost of region splitting.
340   unsigned calculateRegionSplitCost(const LiveInterval &VirtReg,
341                                     AllocationOrder &Order,
342                                     BlockFrequency &BestCost,
343                                     unsigned &NumCands, bool IgnoreCSR);
344   /// Perform region splitting.
345   unsigned doRegionSplit(const LiveInterval &VirtReg, unsigned BestCand,
346                          bool HasCompact, SmallVectorImpl<Register> &NewVRegs);
347   /// Check other options before using a callee-saved register for the first
348   /// time.
349   MCRegister tryAssignCSRFirstTime(const LiveInterval &VirtReg,
350                                    AllocationOrder &Order, MCRegister PhysReg,
351                                    uint8_t &CostPerUseLimit,
352                                    SmallVectorImpl<Register> &NewVRegs);
353   void initializeCSRCost();
354   unsigned tryBlockSplit(const LiveInterval &, AllocationOrder &,
355                          SmallVectorImpl<Register> &);
356   unsigned tryInstructionSplit(const LiveInterval &, AllocationOrder &,
357                                SmallVectorImpl<Register> &);
358   unsigned tryLocalSplit(const LiveInterval &, AllocationOrder &,
359                          SmallVectorImpl<Register> &);
360   unsigned trySplit(const LiveInterval &, AllocationOrder &,
361                     SmallVectorImpl<Register> &, const SmallVirtRegSet &);
362   unsigned tryLastChanceRecoloring(const LiveInterval &, AllocationOrder &,
363                                    SmallVectorImpl<Register> &,
364                                    SmallVirtRegSet &, RecoloringStack &,
365                                    unsigned);
366   bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &,
367                                SmallVirtRegSet &, RecoloringStack &, unsigned);
368   void tryHintRecoloring(const LiveInterval &);
369   void tryHintsRecoloring();
370 
371   /// Model the information carried by one end of a copy.
372   struct HintInfo {
373     /// The frequency of the copy.
374     BlockFrequency Freq;
375     /// The virtual register or physical register.
376     Register Reg;
377     /// Its currently assigned register.
378     /// In case of a physical register Reg == PhysReg.
379     MCRegister PhysReg;
380 
381     HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg)
382         : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
383   };
384   using HintsInfo = SmallVector<HintInfo, 4>;
385 
386   BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);
387   void collectHintInfo(Register, HintsInfo &);
388 
389   /// Greedy RA statistic to remark.
390   struct RAGreedyStats {
391     unsigned Reloads = 0;
392     unsigned FoldedReloads = 0;
393     unsigned ZeroCostFoldedReloads = 0;
394     unsigned Spills = 0;
395     unsigned FoldedSpills = 0;
396     unsigned Copies = 0;
397     float ReloadsCost = 0.0f;
398     float FoldedReloadsCost = 0.0f;
399     float SpillsCost = 0.0f;
400     float FoldedSpillsCost = 0.0f;
401     float CopiesCost = 0.0f;
402 
403     bool isEmpty() {
404       return !(Reloads || FoldedReloads || Spills || FoldedSpills ||
405                ZeroCostFoldedReloads || Copies);
406     }
407 
408     void add(RAGreedyStats other) {
409       Reloads += other.Reloads;
410       FoldedReloads += other.FoldedReloads;
411       ZeroCostFoldedReloads += other.ZeroCostFoldedReloads;
412       Spills += other.Spills;
413       FoldedSpills += other.FoldedSpills;
414       Copies += other.Copies;
415       ReloadsCost += other.ReloadsCost;
416       FoldedReloadsCost += other.FoldedReloadsCost;
417       SpillsCost += other.SpillsCost;
418       FoldedSpillsCost += other.FoldedSpillsCost;
419       CopiesCost += other.CopiesCost;
420     }
421 
422     void report(MachineOptimizationRemarkMissed &R);
423   };
424 
425   /// Compute statistic for a basic block.
426   RAGreedyStats computeStats(MachineBasicBlock &MBB);
427 
428   /// Compute and report statistic through a remark.
429   RAGreedyStats reportStats(MachineLoop *L);
430 
431   /// Report the statistic for each loop.
432   void reportStats();
433 };
434 } // namespace llvm
435 #endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_
436