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