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