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