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