contrib/llvm-project/llvm/lib/CodeGen/RegAllocGreedy.h

   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   // splitting state.
 207   std::unique_ptr<SplitAnalysis> SA;
 208   std::unique_ptr<SplitEditor> SE;
 209
 210   /// Cached per-block interference maps
 211   InterferenceCache IntfCache;
 212
 213   /// All basic blocks where the current register has uses.
 214   SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
 215
 216   /// Global live range splitting candidate info.
 217   struct GlobalSplitCandidate {
 218     // Register intended for assignment, or 0.
 219     MCRegister PhysReg;
 220
 221     // SplitKit interval index for this candidate.
 222     unsigned IntvIdx;
 223
 224     // Interference for PhysReg.
 225     InterferenceCache::Cursor Intf;
 226
 227     // Bundles where this candidate should be live.
 228     BitVector LiveBundles;
 229     SmallVector<unsigned, 8> ActiveBlocks;
 230
 231     void reset(InterferenceCache &Cache, MCRegister Reg) {
 232       PhysReg = Reg;
 233       IntvIdx = 0;
 234       Intf.setPhysReg(Cache, Reg);
 235       LiveBundles.clear();
 236       ActiveBlocks.clear();
 237     }
 238
 239     // Set B[I] = C for every live bundle where B[I] was NoCand.
 240     unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
 241       unsigned Count = 0;
 242       for (unsigned I : LiveBundles.set_bits())
 243         if (B[I] == NoCand) {
 244           B[I] = C;
 245           Count++;
 246         }
 247       return Count;
 248     }
 249   };
 250
 251   /// Candidate info for each PhysReg in AllocationOrder.
 252   /// This vector never shrinks, but grows to the size of the largest register
 253   /// class.
 254   SmallVector<GlobalSplitCandidate, 32> GlobalCand;
 255
 256   enum : unsigned { NoCand = ~0u };
 257
 258   /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
 259   /// NoCand which indicates the stack interval.
 260   SmallVector<unsigned, 32> BundleCand;
 261
 262   /// Callee-save register cost, calculated once per machine function.
 263   BlockFrequency CSRCost;
 264
 265   /// Set of broken hints that may be reconciled later because of eviction.
 266   SmallSetVector<const LiveInterval *, 8> SetOfBrokenHints;
 267
 268   /// The register cost values. This list will be recreated for each Machine
 269   /// Function
 270   ArrayRef<uint8_t> RegCosts;
 271
 272   /// Flags for the live range priority calculation, determined once per
 273   /// machine function.
 274   bool RegClassPriorityTrumpsGlobalness;
 275
 276 public:
 277   RAGreedy(const RegClassFilterFunc F = allocateAllRegClasses);
 278
 279   /// Return the pass name.
 280   StringRef getPassName() const override { return "Greedy Register Allocator"; }
 281
 282   /// RAGreedy analysis usage.
 283   void getAnalysisUsage(AnalysisUsage &AU) const override;
 284   void releaseMemory() override;
 285   Spiller &spiller() override { return *SpillerInstance; }
 286   void enqueueImpl(const LiveInterval *LI) override;
 287   const LiveInterval *dequeue() override;
 288   MCRegister selectOrSplit(const LiveInterval &,
 289                            SmallVectorImpl<Register> &) override;
 290   void aboutToRemoveInterval(const LiveInterval &) override;
 291
 292   /// Perform register allocation.
 293   bool runOnMachineFunction(MachineFunction &mf) override;
 294
 295   MachineFunctionProperties getRequiredProperties() const override {
 296     return MachineFunctionProperties().set(
 297         MachineFunctionProperties::Property::NoPHIs);
 298   }
 299
 300   MachineFunctionProperties getClearedProperties() const override {
 301     return MachineFunctionProperties().set(
 302         MachineFunctionProperties::Property::IsSSA);
 303   }
 304
 305   static char ID;
 306
 307 private:
 308   MCRegister selectOrSplitImpl(const LiveInterval &,
 309                                SmallVectorImpl<Register> &, SmallVirtRegSet &,
 310                                RecoloringStack &, unsigned = 0);
 311
 312   bool LRE_CanEraseVirtReg(Register) override;
 313   void LRE_WillShrinkVirtReg(Register) override;
 314   void LRE_DidCloneVirtReg(Register, Register) override;
 315   void enqueue(PQueue &CurQueue, const LiveInterval *LI);
 316   const LiveInterval *dequeue(PQueue &CurQueue);
 317
 318   bool hasVirtRegAlloc();
 319   BlockFrequency calcSpillCost();
 320   bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency &);
 321   bool addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
 322   bool growRegion(GlobalSplitCandidate &Cand);
 323   BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,
 324                                      const AllocationOrder &Order);
 325   bool calcCompactRegion(GlobalSplitCandidate &);
 326   void splitAroundRegion(LiveRangeEdit &, ArrayRef<unsigned>);
 327   void calcGapWeights(MCRegister, SmallVectorImpl<float> &);
 328   void evictInterference(const LiveInterval &, MCRegister,
 329                          SmallVectorImpl<Register> &);
 330   bool mayRecolorAllInterferences(MCRegister PhysReg,
 331                                   const LiveInterval &VirtReg,
 332                                   SmallLISet &RecoloringCandidates,
 333                                   const SmallVirtRegSet &FixedRegisters);
 334
 335   MCRegister tryAssign(const LiveInterval &, AllocationOrder &,
 336                        SmallVectorImpl<Register> &, const SmallVirtRegSet &);
 337   MCRegister tryEvict(const LiveInterval &, AllocationOrder &,
 338                       SmallVectorImpl<Register> &, uint8_t,
 339                       const SmallVirtRegSet &);
 340   MCRegister tryRegionSplit(const LiveInterval &, AllocationOrder &,
 341                             SmallVectorImpl<Register> &);
 342   /// Calculate cost of region splitting.
 343   unsigned calculateRegionSplitCost(const LiveInterval &VirtReg,
 344                                     AllocationOrder &Order,
 345                                     BlockFrequency &BestCost,
 346                                     unsigned &NumCands, bool IgnoreCSR);
 347   /// Perform region splitting.
 348   unsigned doRegionSplit(const LiveInterval &VirtReg, unsigned BestCand,
 349                          bool HasCompact, SmallVectorImpl<Register> &NewVRegs);
 350   /// Check other options before using a callee-saved register for the first
 351   /// time.
 352   MCRegister tryAssignCSRFirstTime(const LiveInterval &VirtReg,
 353                                    AllocationOrder &Order, MCRegister PhysReg,
 354                                    uint8_t &CostPerUseLimit,
 355                                    SmallVectorImpl<Register> &NewVRegs);
 356   void initializeCSRCost();
 357   unsigned tryBlockSplit(const LiveInterval &, AllocationOrder &,
 358                          SmallVectorImpl<Register> &);
 359   unsigned tryInstructionSplit(const LiveInterval &, AllocationOrder &,
 360                                SmallVectorImpl<Register> &);
 361   unsigned tryLocalSplit(const LiveInterval &, AllocationOrder &,
 362                          SmallVectorImpl<Register> &);
 363   unsigned trySplit(const LiveInterval &, AllocationOrder &,
 364                     SmallVectorImpl<Register> &, const SmallVirtRegSet &);
 365   unsigned tryLastChanceRecoloring(const LiveInterval &, AllocationOrder &,
 366                                    SmallVectorImpl<Register> &,
 367                                    SmallVirtRegSet &, RecoloringStack &,
 368                                    unsigned);
 369   bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &,
 370                                SmallVirtRegSet &, RecoloringStack &, unsigned);
 371   void tryHintRecoloring(const LiveInterval &);
 372   void tryHintsRecoloring();
 373
 374   /// Model the information carried by one end of a copy.
 375   struct HintInfo {
 376     /// The frequency of the copy.
 377     BlockFrequency Freq;
 378     /// The virtual register or physical register.
 379     Register Reg;
 380     /// Its currently assigned register.
 381     /// In case of a physical register Reg == PhysReg.
 382     MCRegister PhysReg;
 383
 384     HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg)
 385         : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
 386   };
 387   using HintsInfo = SmallVector<HintInfo, 4>;
 388
 389   BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);
 390   void collectHintInfo(Register, HintsInfo &);
 391
 392   /// Greedy RA statistic to remark.
 393   struct RAGreedyStats {
 394     unsigned Reloads = 0;
 395     unsigned FoldedReloads = 0;
 396     unsigned ZeroCostFoldedReloads = 0;
 397     unsigned Spills = 0;
 398     unsigned FoldedSpills = 0;
 399     unsigned Copies = 0;
 400     float ReloadsCost = 0.0f;
 401     float FoldedReloadsCost = 0.0f;
 402     float SpillsCost = 0.0f;
 403     float FoldedSpillsCost = 0.0f;
 404     float CopiesCost = 0.0f;
 405
 406     bool isEmpty() {
 407       return !(Reloads || FoldedReloads || Spills || FoldedSpills ||
 408                ZeroCostFoldedReloads || Copies);
 409     }
 410
 411     void add(RAGreedyStats other) {
 412       Reloads += other.Reloads;
 413       FoldedReloads += other.FoldedReloads;
 414       ZeroCostFoldedReloads += other.ZeroCostFoldedReloads;
 415       Spills += other.Spills;
 416       FoldedSpills += other.FoldedSpills;
 417       Copies += other.Copies;
 418       ReloadsCost += other.ReloadsCost;
 419       FoldedReloadsCost += other.FoldedReloadsCost;
 420       SpillsCost += other.SpillsCost;
 421       FoldedSpillsCost += other.FoldedSpillsCost;
 422       CopiesCost += other.CopiesCost;
 423     }
 424
 425     void report(MachineOptimizationRemarkMissed &R);
 426   };
 427
 428   /// Compute statistic for a basic block.
 429   RAGreedyStats computeStats(MachineBasicBlock &MBB);
 430
 431   /// Compute and report statistic through a remark.
 432   RAGreedyStats reportStats(MachineLoop *L);
 433
 434   /// Report the statistic for each loop.
 435   void reportStats();
 436 };
 437 } // namespace llvm
 438 #endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_