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/CodeGen/CalcSpillWeights.h" 29 #include "llvm/CodeGen/LiveInterval.h" 30 #include "llvm/CodeGen/LiveRangeEdit.h" 31 #include "llvm/CodeGen/MachineFunction.h" 32 #include "llvm/CodeGen/MachineFunctionPass.h" 33 #include "llvm/CodeGen/RegisterClassInfo.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 LiveDebugVariables; 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() = default; 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 private: 151 // Convenient shortcuts. 152 using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>; 153 using SmallLISet = SmallPtrSet<const LiveInterval *, 4>; 154 155 // We need to track all tentative recolorings so we can roll back any 156 // successful and unsuccessful recoloring attempts. 157 using RecoloringStack = 158 SmallVector<std::pair<const LiveInterval *, MCRegister>, 8>; 159 160 // context 161 MachineFunction *MF; 162 163 // Shortcuts to some useful interface. 164 const TargetInstrInfo *TII; 165 166 // analyses 167 SlotIndexes *Indexes; 168 MachineBlockFrequencyInfo *MBFI; 169 MachineDominatorTree *DomTree; 170 MachineLoopInfo *Loops; 171 MachineOptimizationRemarkEmitter *ORE; 172 EdgeBundles *Bundles; 173 SpillPlacement *SpillPlacer; 174 LiveDebugVariables *DebugVars; 175 176 // state 177 std::unique_ptr<Spiller> SpillerInstance; 178 PQueue Queue; 179 std::unique_ptr<VirtRegAuxInfo> VRAI; 180 Optional<ExtraRegInfo> ExtraInfo; 181 std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor; 182 183 // Enum CutOffStage to keep a track whether the register allocation failed 184 // because of the cutoffs encountered in last chance recoloring. 185 // Note: This is used as bitmask. New value should be next power of 2. 186 enum CutOffStage { 187 // No cutoffs encountered 188 CO_None = 0, 189 190 // lcr-max-depth cutoff encountered 191 CO_Depth = 1, 192 193 // lcr-max-interf cutoff encountered 194 CO_Interf = 2 195 }; 196 197 uint8_t CutOffInfo; 198 199 #ifndef NDEBUG 200 static const char *const StageName[]; 201 #endif 202 203 // splitting state. 204 std::unique_ptr<SplitAnalysis> SA; 205 std::unique_ptr<SplitEditor> SE; 206 207 /// Cached per-block interference maps 208 InterferenceCache IntfCache; 209 210 /// All basic blocks where the current register has uses. 211 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 212 213 /// Global live range splitting candidate info. 214 struct GlobalSplitCandidate { 215 // Register intended for assignment, or 0. 216 MCRegister PhysReg; 217 218 // SplitKit interval index for this candidate. 219 unsigned IntvIdx; 220 221 // Interference for PhysReg. 222 InterferenceCache::Cursor Intf; 223 224 // Bundles where this candidate should be live. 225 BitVector LiveBundles; 226 SmallVector<unsigned, 8> ActiveBlocks; 227 228 void reset(InterferenceCache &Cache, MCRegister Reg) { 229 PhysReg = Reg; 230 IntvIdx = 0; 231 Intf.setPhysReg(Cache, Reg); 232 LiveBundles.clear(); 233 ActiveBlocks.clear(); 234 } 235 236 // Set B[I] = C for every live bundle where B[I] was NoCand. 237 unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) { 238 unsigned Count = 0; 239 for (unsigned I : LiveBundles.set_bits()) 240 if (B[I] == NoCand) { 241 B[I] = C; 242 Count++; 243 } 244 return Count; 245 } 246 }; 247 248 /// Candidate info for each PhysReg in AllocationOrder. 249 /// This vector never shrinks, but grows to the size of the largest register 250 /// class. 251 SmallVector<GlobalSplitCandidate, 32> GlobalCand; 252 253 enum : unsigned { NoCand = ~0u }; 254 255 /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to 256 /// NoCand which indicates the stack interval. 257 SmallVector<unsigned, 32> BundleCand; 258 259 /// Callee-save register cost, calculated once per machine function. 260 BlockFrequency CSRCost; 261 262 /// Set of broken hints that may be reconciled later because of eviction. 263 SmallSetVector<const LiveInterval *, 8> SetOfBrokenHints; 264 265 /// The register cost values. This list will be recreated for each Machine 266 /// Function 267 ArrayRef<uint8_t> RegCosts; 268 269 /// Flags for the live range priority calculation, determined once per 270 /// machine function. 271 bool RegClassPriorityTrumpsGlobalness; 272 273 public: 274 RAGreedy(const RegClassFilterFunc F = allocateAllRegClasses); 275 276 /// Return the pass name. 277 StringRef getPassName() const override { return "Greedy Register Allocator"; } 278 279 /// RAGreedy analysis usage. 280 void getAnalysisUsage(AnalysisUsage &AU) const override; 281 void releaseMemory() override; 282 Spiller &spiller() override { return *SpillerInstance; } 283 void enqueueImpl(const LiveInterval *LI) override; 284 const LiveInterval *dequeue() override; 285 MCRegister selectOrSplit(const LiveInterval &, 286 SmallVectorImpl<Register> &) override; 287 void aboutToRemoveInterval(const LiveInterval &) override; 288 289 /// Perform register allocation. 290 bool runOnMachineFunction(MachineFunction &mf) override; 291 292 MachineFunctionProperties getRequiredProperties() const override { 293 return MachineFunctionProperties().set( 294 MachineFunctionProperties::Property::NoPHIs); 295 } 296 297 MachineFunctionProperties getClearedProperties() const override { 298 return MachineFunctionProperties().set( 299 MachineFunctionProperties::Property::IsSSA); 300 } 301 302 static char ID; 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. 340 unsigned calculateRegionSplitCost(const LiveInterval &VirtReg, 341 AllocationOrder &Order, 342 BlockFrequency &BestCost, 343 unsigned &NumCands, bool IgnoreCSR); 344 /// Perform region splitting. 345 unsigned doRegionSplit(const LiveInterval &VirtReg, unsigned BestCand, 346 bool HasCompact, SmallVectorImpl<Register> &NewVRegs); 347 /// Check other options before using a callee-saved register for the first 348 /// time. 349 MCRegister tryAssignCSRFirstTime(const LiveInterval &VirtReg, 350 AllocationOrder &Order, MCRegister PhysReg, 351 uint8_t &CostPerUseLimit, 352 SmallVectorImpl<Register> &NewVRegs); 353 void initializeCSRCost(); 354 unsigned tryBlockSplit(const LiveInterval &, AllocationOrder &, 355 SmallVectorImpl<Register> &); 356 unsigned tryInstructionSplit(const LiveInterval &, AllocationOrder &, 357 SmallVectorImpl<Register> &); 358 unsigned tryLocalSplit(const LiveInterval &, AllocationOrder &, 359 SmallVectorImpl<Register> &); 360 unsigned trySplit(const LiveInterval &, AllocationOrder &, 361 SmallVectorImpl<Register> &, const SmallVirtRegSet &); 362 unsigned tryLastChanceRecoloring(const LiveInterval &, AllocationOrder &, 363 SmallVectorImpl<Register> &, 364 SmallVirtRegSet &, RecoloringStack &, 365 unsigned); 366 bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &, 367 SmallVirtRegSet &, RecoloringStack &, unsigned); 368 void tryHintRecoloring(const LiveInterval &); 369 void tryHintsRecoloring(); 370 371 /// Model the information carried by one end of a copy. 372 struct HintInfo { 373 /// The frequency of the copy. 374 BlockFrequency Freq; 375 /// The virtual register or physical register. 376 Register Reg; 377 /// Its currently assigned register. 378 /// In case of a physical register Reg == PhysReg. 379 MCRegister PhysReg; 380 381 HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg) 382 : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {} 383 }; 384 using HintsInfo = SmallVector<HintInfo, 4>; 385 386 BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister); 387 void collectHintInfo(Register, HintsInfo &); 388 389 /// Greedy RA statistic to remark. 390 struct RAGreedyStats { 391 unsigned Reloads = 0; 392 unsigned FoldedReloads = 0; 393 unsigned ZeroCostFoldedReloads = 0; 394 unsigned Spills = 0; 395 unsigned FoldedSpills = 0; 396 unsigned Copies = 0; 397 float ReloadsCost = 0.0f; 398 float FoldedReloadsCost = 0.0f; 399 float SpillsCost = 0.0f; 400 float FoldedSpillsCost = 0.0f; 401 float CopiesCost = 0.0f; 402 403 bool isEmpty() { 404 return !(Reloads || FoldedReloads || Spills || FoldedSpills || 405 ZeroCostFoldedReloads || Copies); 406 } 407 408 void add(RAGreedyStats other) { 409 Reloads += other.Reloads; 410 FoldedReloads += other.FoldedReloads; 411 ZeroCostFoldedReloads += other.ZeroCostFoldedReloads; 412 Spills += other.Spills; 413 FoldedSpills += other.FoldedSpills; 414 Copies += other.Copies; 415 ReloadsCost += other.ReloadsCost; 416 FoldedReloadsCost += other.FoldedReloadsCost; 417 SpillsCost += other.SpillsCost; 418 FoldedSpillsCost += other.FoldedSpillsCost; 419 CopiesCost += other.CopiesCost; 420 } 421 422 void report(MachineOptimizationRemarkMissed &R); 423 }; 424 425 /// Compute statistic for a basic block. 426 RAGreedyStats computeStats(MachineBasicBlock &MBB); 427 428 /// Compute and report statistic through a remark. 429 RAGreedyStats reportStats(MachineLoop *L); 430 431 /// Report the statistic for each loop. 432 void reportStats(); 433 }; 434 } // namespace llvm 435 #endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_ 436