446 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8// This file defines the RAGreedy function pass for register allocation in9// 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 <cstdint>37#include <memory>38#include <queue>39#include <utility>40 41namespace llvm {42class AllocationOrder;43class AnalysisUsage;44class EdgeBundles;45class LiveDebugVariablesWrapperLegacy;46class LiveIntervals;47class LiveRegMatrix;48class MachineBasicBlock;49class MachineBlockFrequencyInfo;50class MachineDominatorTree;51class MachineLoop;52class MachineLoopInfo;53class MachineOptimizationRemarkEmitter;54class MachineOptimizationRemarkMissed;55class SlotIndexes;56class TargetInstrInfo;57class VirtRegMap;58 59class LLVM_LIBRARY_VISIBILITY RAGreedy : public RegAllocBase,60 private LiveRangeEdit::Delegate {61public:62 struct RequiredAnalyses;63 64 // Interface to eviction advisers65 /// 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. See72 // 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, otherwise101 /// 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 advisers151 bool getRegClassPriorityTrumpsGlobalness() const {152 return RegClassPriorityTrumpsGlobalness;153 }154 bool getReverseLocalAssignment() const { return ReverseLocalAssignment; }155 // end (interface to priority advisers)156 157private: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 any163 // successful and unsuccessful recoloring attempts.164 using RecoloringStack =165 SmallVector<std::pair<const LiveInterval *, MCRegister>, 8>;166 167 // context168 MachineFunction *MF = nullptr;169 170 // Shortcuts to some useful interface.171 const TargetInstrInfo *TII = nullptr;172 173 // analyses174 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 LiveStacks *LSS = nullptr; // Used by InlineSpiller183 // Proxy for the advisors184 RegAllocEvictionAdvisorProvider *EvictProvider = nullptr;185 RegAllocPriorityAdvisorProvider *PriorityProvider = nullptr;186 187 // state188 std::unique_ptr<Spiller> SpillerInstance;189 PQueue Queue;190 std::unique_ptr<VirtRegAuxInfo> VRAI;191 std::optional<ExtraRegInfo> ExtraInfo;192 std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor;193 194 std::unique_ptr<RegAllocPriorityAdvisor> PriorityAdvisor;195 196 // Enum CutOffStage to keep a track whether the register allocation failed197 // because of the cutoffs encountered in last chance recoloring.198 // Note: This is used as bitmask. New value should be next power of 2.199 enum CutOffStage {200 // No cutoffs encountered201 CO_None = 0,202 203 // lcr-max-depth cutoff encountered204 CO_Depth = 1,205 206 // lcr-max-interf cutoff encountered207 CO_Interf = 2208 };209 210 uint8_t CutOffInfo = CutOffStage::CO_None;211 212#ifndef NDEBUG213 static const char *const StageName[];214#endif215 216 // splitting state.217 std::unique_ptr<SplitAnalysis> SA;218 std::unique_ptr<SplitEditor> SE;219 220 /// Cached per-block interference maps221 InterferenceCache IntfCache;222 223 /// All basic blocks where the current register has uses.224 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;225 226 /// Global live range splitting candidate info.227 struct GlobalSplitCandidate {228 // Register intended for assignment, or 0.229 MCRegister PhysReg;230 231 // SplitKit interval index for this candidate.232 unsigned IntvIdx;233 234 // Interference for PhysReg.235 InterferenceCache::Cursor Intf;236 237 // Bundles where this candidate should be live.238 BitVector LiveBundles;239 SmallVector<unsigned, 8> ActiveBlocks;240 241 void reset(InterferenceCache &Cache, MCRegister Reg) {242 PhysReg = Reg;243 IntvIdx = 0;244 Intf.setPhysReg(Cache, Reg);245 LiveBundles.clear();246 ActiveBlocks.clear();247 }248 249 // Set B[I] = C for every live bundle where B[I] was NoCand.250 unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {251 unsigned Count = 0;252 for (unsigned I : LiveBundles.set_bits())253 if (B[I] == NoCand) {254 B[I] = C;255 Count++;256 }257 return Count;258 }259 };260 261 /// Candidate info for each PhysReg in AllocationOrder.262 /// This vector never shrinks, but grows to the size of the largest register263 /// class.264 SmallVector<GlobalSplitCandidate, 32> GlobalCand;265 266 enum : unsigned { NoCand = ~0u };267 268 /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to269 /// NoCand which indicates the stack interval.270 SmallVector<unsigned, 32> BundleCand;271 272 /// Callee-save register cost, calculated once per machine function.273 BlockFrequency CSRCost;274 275 /// Set of broken hints that may be reconciled later because of eviction.276 SmallSetVector<const LiveInterval *, 8> SetOfBrokenHints;277 278 /// The register cost values. This list will be recreated for each Machine279 /// Function280 ArrayRef<uint8_t> RegCosts;281 282 /// Flags for the live range priority calculation, determined once per283 /// machine function.284 bool RegClassPriorityTrumpsGlobalness = false;285 286 bool ReverseLocalAssignment = false;287 288public:289 RAGreedy(RequiredAnalyses &Analyses, const RegAllocFilterFunc F = nullptr);290 291 Spiller &spiller() override { return *SpillerInstance; }292 void enqueueImpl(const LiveInterval *LI) override;293 const LiveInterval *dequeue() override;294 MCRegister selectOrSplit(const LiveInterval &,295 SmallVectorImpl<Register> &) override;296 void aboutToRemoveInterval(const LiveInterval &) override;297 298 /// Perform register allocation.299 bool run(MachineFunction &mf);300 301 void releaseMemory();302 303private:304 MCRegister selectOrSplitImpl(const LiveInterval &,305 SmallVectorImpl<Register> &, SmallVirtRegSet &,306 RecoloringStack &, unsigned = 0);307 308 bool LRE_CanEraseVirtReg(Register) override;309 void LRE_WillShrinkVirtReg(Register) override;310 void LRE_DidCloneVirtReg(Register, Register) override;311 void enqueue(PQueue &CurQueue, const LiveInterval *LI);312 const LiveInterval *dequeue(PQueue &CurQueue);313 314 bool hasVirtRegAlloc();315 BlockFrequency calcSpillCost();316 bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency &);317 bool addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);318 bool growRegion(GlobalSplitCandidate &Cand);319 BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,320 const AllocationOrder &Order);321 bool calcCompactRegion(GlobalSplitCandidate &);322 void splitAroundRegion(LiveRangeEdit &, ArrayRef<unsigned>);323 void calcGapWeights(MCRegister, SmallVectorImpl<float> &);324 void evictInterference(const LiveInterval &, MCRegister,325 SmallVectorImpl<Register> &);326 bool mayRecolorAllInterferences(MCRegister PhysReg,327 const LiveInterval &VirtReg,328 SmallLISet &RecoloringCandidates,329 const SmallVirtRegSet &FixedRegisters);330 331 MCRegister tryAssign(const LiveInterval &, AllocationOrder &,332 SmallVectorImpl<Register> &, const SmallVirtRegSet &);333 MCRegister tryEvict(const LiveInterval &, AllocationOrder &,334 SmallVectorImpl<Register> &, uint8_t,335 const SmallVirtRegSet &);336 MCRegister tryRegionSplit(const LiveInterval &, AllocationOrder &,337 SmallVectorImpl<Register> &);338 /// Calculate cost of region splitting around the specified register.339 unsigned calculateRegionSplitCostAroundReg(MCRegister PhysReg,340 AllocationOrder &Order,341 BlockFrequency &BestCost,342 unsigned &NumCands,343 unsigned &BestCand);344 /// Calculate cost of region splitting.345 unsigned calculateRegionSplitCost(const LiveInterval &VirtReg,346 AllocationOrder &Order,347 BlockFrequency &BestCost,348 unsigned &NumCands, bool IgnoreCSR);349 /// Perform region splitting.350 MCRegister doRegionSplit(const LiveInterval &VirtReg, unsigned BestCand,351 bool HasCompact,352 SmallVectorImpl<Register> &NewVRegs);353 /// Try to split VirtReg around physical Hint register.354 bool trySplitAroundHintReg(MCRegister Hint, const LiveInterval &VirtReg,355 SmallVectorImpl<Register> &NewVRegs,356 AllocationOrder &Order);357 /// Check other options before using a callee-saved register for the first358 /// time.359 MCRegister tryAssignCSRFirstTime(const LiveInterval &VirtReg,360 AllocationOrder &Order, MCRegister PhysReg,361 uint8_t &CostPerUseLimit,362 SmallVectorImpl<Register> &NewVRegs);363 void initializeCSRCost();364 MCRegister tryBlockSplit(const LiveInterval &, AllocationOrder &,365 SmallVectorImpl<Register> &);366 MCRegister tryInstructionSplit(const LiveInterval &, AllocationOrder &,367 SmallVectorImpl<Register> &);368 MCRegister tryLocalSplit(const LiveInterval &, AllocationOrder &,369 SmallVectorImpl<Register> &);370 MCRegister trySplit(const LiveInterval &, AllocationOrder &,371 SmallVectorImpl<Register> &, const SmallVirtRegSet &);372 MCRegister tryLastChanceRecoloring(const LiveInterval &, AllocationOrder &,373 SmallVectorImpl<Register> &,374 SmallVirtRegSet &, RecoloringStack &,375 unsigned);376 bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &,377 SmallVirtRegSet &, RecoloringStack &, unsigned);378 void tryHintRecoloring(const LiveInterval &);379 void tryHintsRecoloring();380 381 /// Model the information carried by one end of a copy.382 struct HintInfo {383 /// The frequency of the copy.384 BlockFrequency Freq;385 /// The virtual register or physical register.386 Register Reg;387 /// Its currently assigned register.388 /// In case of a physical register Reg == PhysReg.389 MCRegister PhysReg;390 391 HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg)392 : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}393 };394 using HintsInfo = SmallVector<HintInfo, 4>;395 396 BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);397 void collectHintInfo(Register, HintsInfo &);398 399 /// Greedy RA statistic to remark.400 struct RAGreedyStats {401 unsigned Reloads = 0;402 unsigned FoldedReloads = 0;403 unsigned ZeroCostFoldedReloads = 0;404 unsigned Spills = 0;405 unsigned FoldedSpills = 0;406 unsigned Copies = 0;407 float ReloadsCost = 0.0f;408 float FoldedReloadsCost = 0.0f;409 float SpillsCost = 0.0f;410 float FoldedSpillsCost = 0.0f;411 float CopiesCost = 0.0f;412 413 bool isEmpty() {414 return !(Reloads || FoldedReloads || Spills || FoldedSpills ||415 ZeroCostFoldedReloads || Copies);416 }417 418 void add(const RAGreedyStats &other) {419 Reloads += other.Reloads;420 FoldedReloads += other.FoldedReloads;421 ZeroCostFoldedReloads += other.ZeroCostFoldedReloads;422 Spills += other.Spills;423 FoldedSpills += other.FoldedSpills;424 Copies += other.Copies;425 ReloadsCost += other.ReloadsCost;426 FoldedReloadsCost += other.FoldedReloadsCost;427 SpillsCost += other.SpillsCost;428 FoldedSpillsCost += other.FoldedSpillsCost;429 CopiesCost += other.CopiesCost;430 }431 432 void report(MachineOptimizationRemarkMissed &R);433 };434 435 /// Compute statistic for a basic block.436 RAGreedyStats computeStats(MachineBasicBlock &MBB);437 438 /// Compute and report statistic through a remark.439 RAGreedyStats reportStats(MachineLoop *L);440 441 /// Report the statistic for each loop.442 void reportStats();443};444} // namespace llvm445#endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_446