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   // 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_