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: ExtraRegInfo()81 ExtraRegInfo() {} 82 ExtraRegInfo(const ExtraRegInfo &) = delete; 83 getStage(Register Reg)84 LiveRangeStage getStage(Register Reg) const { return Info[Reg].Stage; } 85 getStage(const LiveInterval & VirtReg)86 LiveRangeStage getStage(const LiveInterval &VirtReg) const { 87 return getStage(VirtReg.reg()); 88 } 89 setStage(Register Reg,LiveRangeStage Stage)90 void setStage(Register Reg, LiveRangeStage Stage) { 91 Info.grow(Reg.id()); 92 Info[Reg].Stage = Stage; 93 } 94 setStage(const LiveInterval & VirtReg,LiveRangeStage Stage)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. getOrInitStage(Register Reg)101 LiveRangeStage getOrInitStage(Register Reg) { 102 Info.grow(Reg.id()); 103 return getStage(Reg); 104 } 105 getCascade(Register Reg)106 unsigned getCascade(Register Reg) const { return Info[Reg].Cascade; } 107 setCascade(Register Reg,unsigned Cascade)108 void setCascade(Register Reg, unsigned Cascade) { 109 Info.grow(Reg.id()); 110 Info[Reg].Cascade = Cascade; 111 } 112 getOrAssignNewCascade(Register Reg)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 getCascadeOrCurrentNext(Register Reg)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> setStage(Iterator Begin,Iterator End,LiveRangeStage NewStage)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 getInterferenceMatrix()141 LiveRegMatrix *getInterferenceMatrix() const { return Matrix; } getLiveIntervals()142 LiveIntervals *getLiveIntervals() const { return LIS; } getVirtRegMap()143 VirtRegMap *getVirtRegMap() const { return VRM; } getRegClassInfo()144 const RegisterClassInfo &getRegClassInfo() const { return RegClassInfo; } getExtraInfo()145 const ExtraRegInfo &getExtraInfo() const { return *ExtraInfo; } getQueueSize()146 size_t getQueueSize() const { return Queue.size(); } 147 // end (interface to eviction advisers) 148 149 // Interface to priority advisers getRegClassPriorityTrumpsGlobalness()150 bool getRegClassPriorityTrumpsGlobalness() const { 151 return RegClassPriorityTrumpsGlobalness; 152 } getReverseLocalAssignment()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 resetGlobalSplitCandidate236 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. getBundlesGlobalSplitCandidate245 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 RegClassFilterFunc F = allocateAllRegClasses); 285 286 /// Return the pass name. getPassName()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; spiller()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 getRequiredProperties()302 MachineFunctionProperties getRequiredProperties() const override { 303 return MachineFunctionProperties().set( 304 MachineFunctionProperties::Property::NoPHIs); 305 } 306 getClearedProperties()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 HintInfoHintInfo401 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 isEmptyRAGreedyStats423 bool isEmpty() { 424 return !(Reloads || FoldedReloads || Spills || FoldedSpills || 425 ZeroCostFoldedReloads || Copies); 426 } 427 addRAGreedyStats428 void add(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_ 456