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