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