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 "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   size_t getQueueSize() const { return Queue.size(); }
 160   // end (interface to eviction advisers)
 161
 162 private:
 163   // Convenient shortcuts.
 164   using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;
 165   using SmallLISet = SmallPtrSet<LiveInterval *, 4>;
 166
 167   // context
 168   MachineFunction *MF;
 169
 170   // Shortcuts to some useful interface.
 171   const TargetInstrInfo *TII;
 172   const TargetRegisterInfo *TRI;
 173   RegisterClassInfo RCI;
 174
 175   // analyses
 176   SlotIndexes *Indexes;
 177   MachineBlockFrequencyInfo *MBFI;
 178   MachineDominatorTree *DomTree;
 179   MachineLoopInfo *Loops;
 180   MachineOptimizationRemarkEmitter *ORE;
 181   EdgeBundles *Bundles;
 182   SpillPlacement *SpillPlacer;
 183   LiveDebugVariables *DebugVars;
 184   AliasAnalysis *AA;
 185
 186   // state
 187   std::unique_ptr<Spiller> SpillerInstance;
 188   PQueue Queue;
 189   std::unique_ptr<VirtRegAuxInfo> VRAI;
 190   Optional<ExtraRegInfo> ExtraInfo;
 191   std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor;
 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;
 208
 209 #ifndef NDEBUG
 210   static const char *const StageName[];
 211 #endif
 212
 213   /// EvictionTrack - Keeps track of past evictions in order to optimize region
 214   /// split decision.
 215   class EvictionTrack {
 216
 217   public:
 218     using EvictorInfo =
 219         std::pair<Register /* evictor */, MCRegister /* physreg */>;
 220     using EvicteeInfo = llvm::DenseMap<Register /* evictee */, EvictorInfo>;
 221
 222   private:
 223     /// Each Vreg that has been evicted in the last stage of selectOrSplit will
 224     /// be mapped to the evictor Vreg and the PhysReg it was evicted from.
 225     EvicteeInfo Evictees;
 226
 227   public:
 228     /// Clear all eviction information.
 229     void clear() { Evictees.clear(); }
 230
 231     ///  Clear eviction information for the given evictee Vreg.
 232     /// E.g. when Vreg get's a new allocation, the old eviction info is no
 233     /// longer relevant.
 234     /// \param Evictee The evictee Vreg for whom we want to clear collected
 235     /// eviction info.
 236     void clearEvicteeInfo(Register Evictee) { Evictees.erase(Evictee); }
 237
 238     /// Track new eviction.
 239     /// The Evictor vreg has evicted the Evictee vreg from Physreg.
 240     /// \param PhysReg The physical register Evictee was evicted from.
 241     /// \param Evictor The evictor Vreg that evicted Evictee.
 242     /// \param Evictee The evictee Vreg.
 243     void addEviction(MCRegister PhysReg, Register Evictor, Register Evictee) {
 244       Evictees[Evictee].first = Evictor;
 245       Evictees[Evictee].second = PhysReg;
 246     }
 247
 248     /// Return the Evictor Vreg which evicted Evictee Vreg from PhysReg.
 249     /// \param Evictee The evictee vreg.
 250     /// \return The Evictor vreg which evicted Evictee vreg from PhysReg. 0 if
 251     /// nobody has evicted Evictee from PhysReg.
 252     EvictorInfo getEvictor(Register Evictee) {
 253       if (Evictees.count(Evictee)) {
 254         return Evictees[Evictee];
 255       }
 256
 257       return EvictorInfo(0, 0);
 258     }
 259   };
 260
 261   // Keeps track of past evictions in order to optimize region split decision.
 262   EvictionTrack LastEvicted;
 263
 264   // splitting state.
 265   std::unique_ptr<SplitAnalysis> SA;
 266   std::unique_ptr<SplitEditor> SE;
 267
 268   /// Cached per-block interference maps
 269   InterferenceCache IntfCache;
 270
 271   /// All basic blocks where the current register has uses.
 272   SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
 273
 274   /// Global live range splitting candidate info.
 275   struct GlobalSplitCandidate {
 276     // Register intended for assignment, or 0.
 277     MCRegister PhysReg;
 278
 279     // SplitKit interval index for this candidate.
 280     unsigned IntvIdx;
 281
 282     // Interference for PhysReg.
 283     InterferenceCache::Cursor Intf;
 284
 285     // Bundles where this candidate should be live.
 286     BitVector LiveBundles;
 287     SmallVector<unsigned, 8> ActiveBlocks;
 288
 289     void reset(InterferenceCache &Cache, MCRegister Reg) {
 290       PhysReg = Reg;
 291       IntvIdx = 0;
 292       Intf.setPhysReg(Cache, Reg);
 293       LiveBundles.clear();
 294       ActiveBlocks.clear();
 295     }
 296
 297     // Set B[I] = C for every live bundle where B[I] was NoCand.
 298     unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
 299       unsigned Count = 0;
 300       for (unsigned I : LiveBundles.set_bits())
 301         if (B[I] == NoCand) {
 302           B[I] = C;
 303           Count++;
 304         }
 305       return Count;
 306     }
 307   };
 308
 309   /// Candidate info for each PhysReg in AllocationOrder.
 310   /// This vector never shrinks, but grows to the size of the largest register
 311   /// class.
 312   SmallVector<GlobalSplitCandidate, 32> GlobalCand;
 313
 314   enum : unsigned { NoCand = ~0u };
 315
 316   /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
 317   /// NoCand which indicates the stack interval.
 318   SmallVector<unsigned, 32> BundleCand;
 319
 320   /// Callee-save register cost, calculated once per machine function.
 321   BlockFrequency CSRCost;
 322
 323   /// Enable or not the consideration of the cost of local intervals created
 324   /// by a split candidate when choosing the best split candidate.
 325   bool EnableAdvancedRASplitCost;
 326
 327   /// Set of broken hints that may be reconciled later because of eviction.
 328   SmallSetVector<LiveInterval *, 8> SetOfBrokenHints;
 329
 330   /// The register cost values. This list will be recreated for each Machine
 331   /// Function
 332   ArrayRef<uint8_t> RegCosts;
 333
 334 public:
 335   RAGreedy(const RegClassFilterFunc F = allocateAllRegClasses);
 336
 337   /// Return the pass name.
 338   StringRef getPassName() const override { return "Greedy Register Allocator"; }
 339
 340   /// RAGreedy analysis usage.
 341   void getAnalysisUsage(AnalysisUsage &AU) const override;
 342   void releaseMemory() override;
 343   Spiller &spiller() override { return *SpillerInstance; }
 344   void enqueueImpl(LiveInterval *LI) override;
 345   LiveInterval *dequeue() override;
 346   MCRegister selectOrSplit(LiveInterval &,
 347                            SmallVectorImpl<Register> &) override;
 348   void aboutToRemoveInterval(LiveInterval &) override;
 349
 350   /// Perform register allocation.
 351   bool runOnMachineFunction(MachineFunction &mf) override;
 352
 353   MachineFunctionProperties getRequiredProperties() const override {
 354     return MachineFunctionProperties().set(
 355         MachineFunctionProperties::Property::NoPHIs);
 356   }
 357
 358   MachineFunctionProperties getClearedProperties() const override {
 359     return MachineFunctionProperties().set(
 360         MachineFunctionProperties::Property::IsSSA);
 361   }
 362
 363   static char ID;
 364
 365 private:
 366   MCRegister selectOrSplitImpl(LiveInterval &, SmallVectorImpl<Register> &,
 367                                SmallVirtRegSet &, unsigned = 0);
 368
 369   bool LRE_CanEraseVirtReg(Register) override;
 370   void LRE_WillShrinkVirtReg(Register) override;
 371   void LRE_DidCloneVirtReg(Register, Register) override;
 372   void enqueue(PQueue &CurQueue, LiveInterval *LI);
 373   LiveInterval *dequeue(PQueue &CurQueue);
 374
 375   BlockFrequency calcSpillCost();
 376   bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency &);
 377   bool addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
 378   bool growRegion(GlobalSplitCandidate &Cand);
 379   bool splitCanCauseEvictionChain(Register Evictee, GlobalSplitCandidate &Cand,
 380                                   unsigned BBNumber,
 381                                   const AllocationOrder &Order);
 382   bool splitCanCauseLocalSpill(unsigned VirtRegToSplit,
 383                                GlobalSplitCandidate &Cand, unsigned BBNumber,
 384                                const AllocationOrder &Order);
 385   BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,
 386                                      const AllocationOrder &Order,
 387                                      bool *CanCauseEvictionChain);
 388   bool calcCompactRegion(GlobalSplitCandidate &);
 389   void splitAroundRegion(LiveRangeEdit &, ArrayRef<unsigned>);
 390   void calcGapWeights(MCRegister, SmallVectorImpl<float> &);
 391   bool canEvictInterferenceInRange(const LiveInterval &VirtReg,
 392                                    MCRegister PhysReg, SlotIndex Start,
 393                                    SlotIndex End, EvictionCost &MaxCost) const;
 394   MCRegister getCheapestEvicteeWeight(const AllocationOrder &Order,
 395                                       const LiveInterval &VirtReg,
 396                                       SlotIndex Start, SlotIndex End,
 397                                       float *BestEvictWeight) const;
 398   void evictInterference(LiveInterval &, MCRegister,
 399                          SmallVectorImpl<Register> &);
 400   bool mayRecolorAllInterferences(MCRegister PhysReg, LiveInterval &VirtReg,
 401                                   SmallLISet &RecoloringCandidates,
 402                                   const SmallVirtRegSet &FixedRegisters);
 403
 404   MCRegister tryAssign(LiveInterval &, AllocationOrder &,
 405                        SmallVectorImpl<Register> &, const SmallVirtRegSet &);
 406   MCRegister tryEvict(LiveInterval &, AllocationOrder &,
 407                       SmallVectorImpl<Register> &, uint8_t,
 408                       const SmallVirtRegSet &);
 409   MCRegister tryRegionSplit(LiveInterval &, AllocationOrder &,
 410                             SmallVectorImpl<Register> &);
 411   /// Calculate cost of region splitting.
 412   unsigned calculateRegionSplitCost(LiveInterval &VirtReg,
 413                                     AllocationOrder &Order,
 414                                     BlockFrequency &BestCost,
 415                                     unsigned &NumCands, bool IgnoreCSR,
 416                                     bool *CanCauseEvictionChain = nullptr);
 417   /// Perform region splitting.
 418   unsigned doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
 419                          bool HasCompact, SmallVectorImpl<Register> &NewVRegs);
 420   /// Check other options before using a callee-saved register for the first
 421   /// time.
 422   MCRegister tryAssignCSRFirstTime(LiveInterval &VirtReg,
 423                                    AllocationOrder &Order, MCRegister PhysReg,
 424                                    uint8_t &CostPerUseLimit,
 425                                    SmallVectorImpl<Register> &NewVRegs);
 426   void initializeCSRCost();
 427   unsigned tryBlockSplit(LiveInterval &, AllocationOrder &,
 428                          SmallVectorImpl<Register> &);
 429   unsigned tryInstructionSplit(LiveInterval &, AllocationOrder &,
 430                                SmallVectorImpl<Register> &);
 431   unsigned tryLocalSplit(LiveInterval &, AllocationOrder &,
 432                          SmallVectorImpl<Register> &);
 433   unsigned trySplit(LiveInterval &, AllocationOrder &,
 434                     SmallVectorImpl<Register> &, const SmallVirtRegSet &);
 435   unsigned tryLastChanceRecoloring(LiveInterval &, AllocationOrder &,
 436                                    SmallVectorImpl<Register> &,
 437                                    SmallVirtRegSet &, unsigned);
 438   bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &,
 439                                SmallVirtRegSet &, unsigned);
 440   void tryHintRecoloring(LiveInterval &);
 441   void tryHintsRecoloring();
 442
 443   /// Model the information carried by one end of a copy.
 444   struct HintInfo {
 445     /// The frequency of the copy.
 446     BlockFrequency Freq;
 447     /// The virtual register or physical register.
 448     Register Reg;
 449     /// Its currently assigned register.
 450     /// In case of a physical register Reg == PhysReg.
 451     MCRegister PhysReg;
 452
 453     HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg)
 454         : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
 455   };
 456   using HintsInfo = SmallVector<HintInfo, 4>;
 457
 458   BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);
 459   void collectHintInfo(Register, HintsInfo &);
 460
 461   /// Greedy RA statistic to remark.
 462   struct RAGreedyStats {
 463     unsigned Reloads = 0;
 464     unsigned FoldedReloads = 0;
 465     unsigned ZeroCostFoldedReloads = 0;
 466     unsigned Spills = 0;
 467     unsigned FoldedSpills = 0;
 468     unsigned Copies = 0;
 469     float ReloadsCost = 0.0f;
 470     float FoldedReloadsCost = 0.0f;
 471     float SpillsCost = 0.0f;
 472     float FoldedSpillsCost = 0.0f;
 473     float CopiesCost = 0.0f;
 474
 475     bool isEmpty() {
 476       return !(Reloads || FoldedReloads || Spills || FoldedSpills ||
 477                ZeroCostFoldedReloads || Copies);
 478     }
 479
 480     void add(RAGreedyStats other) {
 481       Reloads += other.Reloads;
 482       FoldedReloads += other.FoldedReloads;
 483       ZeroCostFoldedReloads += other.ZeroCostFoldedReloads;
 484       Spills += other.Spills;
 485       FoldedSpills += other.FoldedSpills;
 486       Copies += other.Copies;
 487       ReloadsCost += other.ReloadsCost;
 488       FoldedReloadsCost += other.FoldedReloadsCost;
 489       SpillsCost += other.SpillsCost;
 490       FoldedSpillsCost += other.FoldedSpillsCost;
 491       CopiesCost += other.CopiesCost;
 492     }
 493
 494     void report(MachineOptimizationRemarkMissed &R);
 495   };
 496
 497   /// Compute statistic for a basic block.
 498   RAGreedyStats computeStats(MachineBasicBlock &MBB);
 499
 500   /// Compute and report statistic through a remark.
 501   RAGreedyStats reportStats(MachineLoop *L);
 502
 503   /// Report the statistic for each loop.
 504   void reportStats();
 505 };
 506 } // namespace llvm
 507 #endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_