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 "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 around the specified register.
 352   unsigned calculateRegionSplitCostAroundReg(MCPhysReg PhysReg,
 353                                              AllocationOrder &Order,
 354                                              BlockFrequency &BestCost,
 355                                              unsigned &NumCands,
 356                                              unsigned &BestCand);
 357   /// Calculate cost of region splitting.
 358   unsigned calculateRegionSplitCost(const LiveInterval &VirtReg,
 359                                     AllocationOrder &Order,
 360                                     BlockFrequency &BestCost,
 361                                     unsigned &NumCands, bool IgnoreCSR);
 362   /// Perform region splitting.
 363   unsigned doRegionSplit(const LiveInterval &VirtReg, unsigned BestCand,
 364                          bool HasCompact, SmallVectorImpl<Register> &NewVRegs);
 365   /// Try to split VirtReg around physical Hint register.
 366   bool trySplitAroundHintReg(MCPhysReg Hint, const LiveInterval &VirtReg,
 367                              SmallVectorImpl<Register> &NewVRegs,
 368                              AllocationOrder &Order);
 369   /// Check other options before using a callee-saved register for the first
 370   /// time.
 371   MCRegister tryAssignCSRFirstTime(const LiveInterval &VirtReg,
 372                                    AllocationOrder &Order, MCRegister PhysReg,
 373                                    uint8_t &CostPerUseLimit,
 374                                    SmallVectorImpl<Register> &NewVRegs);
 375   void initializeCSRCost();
 376   unsigned tryBlockSplit(const LiveInterval &, AllocationOrder &,
 377                          SmallVectorImpl<Register> &);
 378   unsigned tryInstructionSplit(const LiveInterval &, AllocationOrder &,
 379                                SmallVectorImpl<Register> &);
 380   unsigned tryLocalSplit(const LiveInterval &, AllocationOrder &,
 381                          SmallVectorImpl<Register> &);
 382   unsigned trySplit(const LiveInterval &, AllocationOrder &,
 383                     SmallVectorImpl<Register> &, const SmallVirtRegSet &);
 384   unsigned tryLastChanceRecoloring(const LiveInterval &, AllocationOrder &,
 385                                    SmallVectorImpl<Register> &,
 386                                    SmallVirtRegSet &, RecoloringStack &,
 387                                    unsigned);
 388   bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &,
 389                                SmallVirtRegSet &, RecoloringStack &, unsigned);
 390   void tryHintRecoloring(const LiveInterval &);
 391   void tryHintsRecoloring();
 392
 393   /// Model the information carried by one end of a copy.
 394   struct HintInfo {
 395     /// The frequency of the copy.
 396     BlockFrequency Freq;
 397     /// The virtual register or physical register.
 398     Register Reg;
 399     /// Its currently assigned register.
 400     /// In case of a physical register Reg == PhysReg.
 401     MCRegister PhysReg;
 402
 403     HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg)
 404         : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
 405   };
 406   using HintsInfo = SmallVector<HintInfo, 4>;
 407
 408   BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);
 409   void collectHintInfo(Register, HintsInfo &);
 410
 411   /// Greedy RA statistic to remark.
 412   struct RAGreedyStats {
 413     unsigned Reloads = 0;
 414     unsigned FoldedReloads = 0;
 415     unsigned ZeroCostFoldedReloads = 0;
 416     unsigned Spills = 0;
 417     unsigned FoldedSpills = 0;
 418     unsigned Copies = 0;
 419     float ReloadsCost = 0.0f;
 420     float FoldedReloadsCost = 0.0f;
 421     float SpillsCost = 0.0f;
 422     float FoldedSpillsCost = 0.0f;
 423     float CopiesCost = 0.0f;
 424
 425     bool isEmpty() {
 426       return !(Reloads || FoldedReloads || Spills || FoldedSpills ||
 427                ZeroCostFoldedReloads || Copies);
 428     }
 429
 430     void add(RAGreedyStats other) {
 431       Reloads += other.Reloads;
 432       FoldedReloads += other.FoldedReloads;
 433       ZeroCostFoldedReloads += other.ZeroCostFoldedReloads;
 434       Spills += other.Spills;
 435       FoldedSpills += other.FoldedSpills;
 436       Copies += other.Copies;
 437       ReloadsCost += other.ReloadsCost;
 438       FoldedReloadsCost += other.FoldedReloadsCost;
 439       SpillsCost += other.SpillsCost;
 440       FoldedSpillsCost += other.FoldedSpillsCost;
 441       CopiesCost += other.CopiesCost;
 442     }
 443
 444     void report(MachineOptimizationRemarkMissed &R);
 445   };
 446
 447   /// Compute statistic for a basic block.
 448   RAGreedyStats computeStats(MachineBasicBlock &MBB);
 449
 450   /// Compute and report statistic through a remark.
 451   RAGreedyStats reportStats(MachineLoop *L);
 452
 453   /// Report the statistic for each loop.
 454   void reportStats();
 455 };
 456 } // namespace llvm
 457 #endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_