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