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/DenseMap.h" 24 #include "llvm/ADT/IndexedMap.h" 25 #include "llvm/ADT/SetVector.h" 26 #include "llvm/ADT/SmallPtrSet.h" 27 #include "llvm/ADT/SmallVector.h" 28 #include "llvm/ADT/StringRef.h" 29 #include "llvm/CodeGen/CalcSpillWeights.h" 30 #include "llvm/CodeGen/LiveInterval.h" 31 #include "llvm/CodeGen/LiveRangeEdit.h" 32 #include "llvm/CodeGen/MachineFunction.h" 33 #include "llvm/CodeGen/MachineFunctionPass.h" 34 #include "llvm/CodeGen/RegisterClassInfo.h" 35 #include "llvm/CodeGen/Spiller.h" 36 #include "llvm/CodeGen/TargetRegisterInfo.h" 37 #include <algorithm> 38 #include <cstdint> 39 #include <memory> 40 #include <queue> 41 #include <utility> 42 43 namespace llvm { 44 class AllocationOrder; 45 class AnalysisUsage; 46 class EdgeBundles; 47 class LiveDebugVariables; 48 class LiveIntervals; 49 class LiveRegMatrix; 50 class MachineBasicBlock; 51 class MachineBlockFrequencyInfo; 52 class MachineDominatorTree; 53 class MachineLoop; 54 class MachineLoopInfo; 55 class MachineOptimizationRemarkEmitter; 56 class MachineOptimizationRemarkMissed; 57 class SlotIndexes; 58 class TargetInstrInfo; 59 class VirtRegMap; 60 61 class LLVM_LIBRARY_VISIBILITY RAGreedy : public MachineFunctionPass, 62 public RegAllocBase, 63 private LiveRangeEdit::Delegate { 64 // Interface to eviction advisers 65 public: 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: 83 ExtraRegInfo() {} 84 ExtraRegInfo(const ExtraRegInfo &) = delete; 85 86 LiveRangeStage getStage(Register Reg) const { return Info[Reg].Stage; } 87 88 LiveRangeStage getStage(const LiveInterval &VirtReg) const { 89 return getStage(VirtReg.reg()); 90 } 91 92 void setStage(Register Reg, LiveRangeStage Stage) { 93 Info.grow(Reg.id()); 94 Info[Reg].Stage = Stage; 95 } 96 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. 103 LiveRangeStage getOrInitStage(Register Reg) { 104 Info.grow(Reg.id()); 105 return getStage(Reg); 106 } 107 108 unsigned getCascade(Register Reg) const { return Info[Reg].Cascade; } 109 110 void setCascade(Register Reg, unsigned Cascade) { 111 Info.grow(Reg.id()); 112 Info[Reg].Cascade = Cascade; 113 } 114 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 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> 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 143 LiveRegMatrix *getInterferenceMatrix() const { return Matrix; } 144 LiveIntervals *getLiveIntervals() const { return LIS; } 145 VirtRegMap *getVirtRegMap() const { return VRM; } 146 const RegisterClassInfo &getRegClassInfo() const { return RegClassInfo; } 147 const ExtraRegInfo &getExtraInfo() const { return *ExtraInfo; } 148 size_t getQueueSize() const { return Queue.size(); } 149 // end (interface to eviction advisers) 150 151 // Interface to priority advisers 152 bool getRegClassPriorityTrumpsGlobalness() const { 153 return RegClassPriorityTrumpsGlobalness; 154 } 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 184 // state 185 std::unique_ptr<Spiller> SpillerInstance; 186 PQueue Queue; 187 std::unique_ptr<VirtRegAuxInfo> VRAI; 188 std::optional<ExtraRegInfo> ExtraInfo; 189 std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor; 190 191 std::unique_ptr<RegAllocPriorityAdvisor> PriorityAdvisor; 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 = CutOffStage::CO_None; 208 209 #ifndef NDEBUG 210 static const char *const StageName[]; 211 #endif 212 213 // splitting state. 214 std::unique_ptr<SplitAnalysis> SA; 215 std::unique_ptr<SplitEditor> SE; 216 217 /// Cached per-block interference maps 218 InterferenceCache IntfCache; 219 220 /// All basic blocks where the current register has uses. 221 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 222 223 /// Global live range splitting candidate info. 224 struct GlobalSplitCandidate { 225 // Register intended for assignment, or 0. 226 MCRegister PhysReg; 227 228 // SplitKit interval index for this candidate. 229 unsigned IntvIdx; 230 231 // Interference for PhysReg. 232 InterferenceCache::Cursor Intf; 233 234 // Bundles where this candidate should be live. 235 BitVector LiveBundles; 236 SmallVector<unsigned, 8> ActiveBlocks; 237 238 void reset(InterferenceCache &Cache, MCRegister Reg) { 239 PhysReg = Reg; 240 IntvIdx = 0; 241 Intf.setPhysReg(Cache, Reg); 242 LiveBundles.clear(); 243 ActiveBlocks.clear(); 244 } 245 246 // Set B[I] = C for every live bundle where B[I] was NoCand. 247 unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) { 248 unsigned Count = 0; 249 for (unsigned I : LiveBundles.set_bits()) 250 if (B[I] == NoCand) { 251 B[I] = C; 252 Count++; 253 } 254 return Count; 255 } 256 }; 257 258 /// Candidate info for each PhysReg in AllocationOrder. 259 /// This vector never shrinks, but grows to the size of the largest register 260 /// class. 261 SmallVector<GlobalSplitCandidate, 32> GlobalCand; 262 263 enum : unsigned { NoCand = ~0u }; 264 265 /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to 266 /// NoCand which indicates the stack interval. 267 SmallVector<unsigned, 32> BundleCand; 268 269 /// Callee-save register cost, calculated once per machine function. 270 BlockFrequency CSRCost; 271 272 /// Set of broken hints that may be reconciled later because of eviction. 273 SmallSetVector<const LiveInterval *, 8> SetOfBrokenHints; 274 275 /// The register cost values. This list will be recreated for each Machine 276 /// Function 277 ArrayRef<uint8_t> RegCosts; 278 279 /// Flags for the live range priority calculation, determined once per 280 /// machine function. 281 bool RegClassPriorityTrumpsGlobalness = false; 282 283 bool ReverseLocalAssignment = false; 284 285 public: 286 RAGreedy(const RegClassFilterFunc F = allocateAllRegClasses); 287 288 /// Return the pass name. 289 StringRef getPassName() const override { return "Greedy Register Allocator"; } 290 291 /// RAGreedy analysis usage. 292 void getAnalysisUsage(AnalysisUsage &AU) const override; 293 void releaseMemory() override; 294 Spiller &spiller() override { return *SpillerInstance; } 295 void enqueueImpl(const LiveInterval *LI) override; 296 const LiveInterval *dequeue() override; 297 MCRegister selectOrSplit(const LiveInterval &, 298 SmallVectorImpl<Register> &) override; 299 void aboutToRemoveInterval(const LiveInterval &) override; 300 301 /// Perform register allocation. 302 bool runOnMachineFunction(MachineFunction &mf) override; 303 304 MachineFunctionProperties getRequiredProperties() const override { 305 return MachineFunctionProperties().set( 306 MachineFunctionProperties::Property::NoPHIs); 307 } 308 309 MachineFunctionProperties getClearedProperties() const override { 310 return MachineFunctionProperties().set( 311 MachineFunctionProperties::Property::IsSSA); 312 } 313 314 static char ID; 315 316 private: 317 MCRegister selectOrSplitImpl(const LiveInterval &, 318 SmallVectorImpl<Register> &, SmallVirtRegSet &, 319 RecoloringStack &, unsigned = 0); 320 321 bool LRE_CanEraseVirtReg(Register) override; 322 void LRE_WillShrinkVirtReg(Register) override; 323 void LRE_DidCloneVirtReg(Register, Register) override; 324 void enqueue(PQueue &CurQueue, const LiveInterval *LI); 325 const LiveInterval *dequeue(PQueue &CurQueue); 326 327 bool hasVirtRegAlloc(); 328 BlockFrequency calcSpillCost(); 329 bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency &); 330 bool addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 331 bool growRegion(GlobalSplitCandidate &Cand); 332 BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &, 333 const AllocationOrder &Order); 334 bool calcCompactRegion(GlobalSplitCandidate &); 335 void splitAroundRegion(LiveRangeEdit &, ArrayRef<unsigned>); 336 void calcGapWeights(MCRegister, SmallVectorImpl<float> &); 337 void evictInterference(const LiveInterval &, MCRegister, 338 SmallVectorImpl<Register> &); 339 bool mayRecolorAllInterferences(MCRegister PhysReg, 340 const LiveInterval &VirtReg, 341 SmallLISet &RecoloringCandidates, 342 const SmallVirtRegSet &FixedRegisters); 343 344 MCRegister tryAssign(const LiveInterval &, AllocationOrder &, 345 SmallVectorImpl<Register> &, const SmallVirtRegSet &); 346 MCRegister tryEvict(const LiveInterval &, AllocationOrder &, 347 SmallVectorImpl<Register> &, uint8_t, 348 const SmallVirtRegSet &); 349 MCRegister tryRegionSplit(const LiveInterval &, AllocationOrder &, 350 SmallVectorImpl<Register> &); 351 /// Calculate cost of region splitting. 352 unsigned calculateRegionSplitCost(const LiveInterval &VirtReg, 353 AllocationOrder &Order, 354 BlockFrequency &BestCost, 355 unsigned &NumCands, bool IgnoreCSR); 356 /// Perform region splitting. 357 unsigned doRegionSplit(const LiveInterval &VirtReg, unsigned BestCand, 358 bool HasCompact, SmallVectorImpl<Register> &NewVRegs); 359 /// Check other options before using a callee-saved register for the first 360 /// time. 361 MCRegister tryAssignCSRFirstTime(const LiveInterval &VirtReg, 362 AllocationOrder &Order, MCRegister PhysReg, 363 uint8_t &CostPerUseLimit, 364 SmallVectorImpl<Register> &NewVRegs); 365 void initializeCSRCost(); 366 unsigned tryBlockSplit(const LiveInterval &, AllocationOrder &, 367 SmallVectorImpl<Register> &); 368 unsigned tryInstructionSplit(const LiveInterval &, AllocationOrder &, 369 SmallVectorImpl<Register> &); 370 unsigned tryLocalSplit(const LiveInterval &, AllocationOrder &, 371 SmallVectorImpl<Register> &); 372 unsigned trySplit(const LiveInterval &, AllocationOrder &, 373 SmallVectorImpl<Register> &, const SmallVirtRegSet &); 374 unsigned tryLastChanceRecoloring(const LiveInterval &, AllocationOrder &, 375 SmallVectorImpl<Register> &, 376 SmallVirtRegSet &, RecoloringStack &, 377 unsigned); 378 bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &, 379 SmallVirtRegSet &, RecoloringStack &, unsigned); 380 void tryHintRecoloring(const LiveInterval &); 381 void tryHintsRecoloring(); 382 383 /// Model the information carried by one end of a copy. 384 struct HintInfo { 385 /// The frequency of the copy. 386 BlockFrequency Freq; 387 /// The virtual register or physical register. 388 Register Reg; 389 /// Its currently assigned register. 390 /// In case of a physical register Reg == PhysReg. 391 MCRegister PhysReg; 392 393 HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg) 394 : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {} 395 }; 396 using HintsInfo = SmallVector<HintInfo, 4>; 397 398 BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister); 399 void collectHintInfo(Register, HintsInfo &); 400 401 /// Greedy RA statistic to remark. 402 struct RAGreedyStats { 403 unsigned Reloads = 0; 404 unsigned FoldedReloads = 0; 405 unsigned ZeroCostFoldedReloads = 0; 406 unsigned Spills = 0; 407 unsigned FoldedSpills = 0; 408 unsigned Copies = 0; 409 float ReloadsCost = 0.0f; 410 float FoldedReloadsCost = 0.0f; 411 float SpillsCost = 0.0f; 412 float FoldedSpillsCost = 0.0f; 413 float CopiesCost = 0.0f; 414 415 bool isEmpty() { 416 return !(Reloads || FoldedReloads || Spills || FoldedSpills || 417 ZeroCostFoldedReloads || Copies); 418 } 419 420 void add(RAGreedyStats other) { 421 Reloads += other.Reloads; 422 FoldedReloads += other.FoldedReloads; 423 ZeroCostFoldedReloads += other.ZeroCostFoldedReloads; 424 Spills += other.Spills; 425 FoldedSpills += other.FoldedSpills; 426 Copies += other.Copies; 427 ReloadsCost += other.ReloadsCost; 428 FoldedReloadsCost += other.FoldedReloadsCost; 429 SpillsCost += other.SpillsCost; 430 FoldedSpillsCost += other.FoldedSpillsCost; 431 CopiesCost += other.CopiesCost; 432 } 433 434 void report(MachineOptimizationRemarkMissed &R); 435 }; 436 437 /// Compute statistic for a basic block. 438 RAGreedyStats computeStats(MachineBasicBlock &MBB); 439 440 /// Compute and report statistic through a remark. 441 RAGreedyStats reportStats(MachineLoop *L); 442 443 /// Report the statistic for each loop. 444 void reportStats(); 445 }; 446 } // namespace llvm 447 #endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_ 448