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