1 //==- RegAllocGreedy.h ------- greedy register allocator ----------*-C++-*-==//
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
7 //===----------------------------------------------------------------------===//
8 // This file defines the RAGreedy function pass for register allocation in
10 //===----------------------------------------------------------------------===//
12 #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_
13 #define LLVM_CODEGEN_REGALLOCGREEDY_H_
15 #include "InterferenceCache.h"
16 #include "RegAllocBase.h"
17 #include "RegAllocEvictionAdvisor.h"
18 #include "SpillPlacement.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"
43 class AllocationOrder;
46 class LiveDebugVariables;
49 class MachineBasicBlock;
50 class MachineBlockFrequencyInfo;
51 class MachineDominatorTree;
53 class MachineLoopInfo;
54 class MachineOptimizationRemarkEmitter;
55 class MachineOptimizationRemarkMissed;
57 class TargetInstrInfo;
60 class LLVM_LIBRARY_VISIBILITY RAGreedy : public MachineFunctionPass,
62 private LiveRangeEdit::Delegate {
63 // Interface to eviction advisers
65 /// Track allocation stage and eviction loop prevention during allocation.
66 class ExtraRegInfo final {
67 // RegInfo - Keep additional information about each live range.
69 LiveRangeStage Stage = RS_New;
71 // Cascade - Eviction loop prevention. See
72 // canEvictInterferenceBasedOnCost().
78 IndexedMap<RegInfo, VirtReg2IndexFunctor> Info;
79 unsigned NextCascade = 1;
82 ExtraRegInfo() = default;
83 ExtraRegInfo(const ExtraRegInfo &) = delete;
85 LiveRangeStage getStage(Register Reg) const { return Info[Reg].Stage; }
87 LiveRangeStage getStage(const LiveInterval &VirtReg) const {
88 return getStage(VirtReg.reg());
91 void setStage(Register Reg, LiveRangeStage Stage) {
93 Info[Reg].Stage = Stage;
96 void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
97 setStage(VirtReg.reg(), Stage);
100 /// Return the current stage of the register, if present, otherwise
101 /// initialize it and return that.
102 LiveRangeStage getOrInitStage(Register Reg) {
104 return getStage(Reg);
107 unsigned getCascade(Register Reg) const { return Info[Reg].Cascade; }
109 void setCascade(Register Reg, unsigned Cascade) {
111 Info[Reg].Cascade = Cascade;
114 unsigned getOrAssignNewCascade(Register Reg) {
115 unsigned Cascade = getCascade(Reg);
117 Cascade = NextCascade++;
118 setCascade(Reg, Cascade);
123 unsigned getCascadeOrCurrentNext(Register Reg) const {
124 unsigned Cascade = getCascade(Reg);
126 Cascade = NextCascade;
130 template <typename Iterator>
131 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
132 for (; Begin != End; ++Begin) {
133 Register Reg = *Begin;
135 if (Info[Reg].Stage == RS_New)
136 Info[Reg].Stage = NewStage;
139 void LRE_DidCloneVirtReg(Register New, Register Old);
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)
151 // Convenient shortcuts.
152 using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;
153 using SmallLISet = SmallPtrSet<const LiveInterval *, 4>;
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>;
163 // Shortcuts to some useful interface.
164 const TargetInstrInfo *TII;
167 SlotIndexes *Indexes;
168 MachineBlockFrequencyInfo *MBFI;
169 MachineDominatorTree *DomTree;
170 MachineLoopInfo *Loops;
171 MachineOptimizationRemarkEmitter *ORE;
172 EdgeBundles *Bundles;
173 SpillPlacement *SpillPlacer;
174 LiveDebugVariables *DebugVars;
177 std::unique_ptr<Spiller> SpillerInstance;
179 std::unique_ptr<VirtRegAuxInfo> VRAI;
180 Optional<ExtraRegInfo> ExtraInfo;
181 std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor;
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.
187 // No cutoffs encountered
190 // lcr-max-depth cutoff encountered
193 // lcr-max-interf cutoff encountered
200 static const char *const StageName[];
204 std::unique_ptr<SplitAnalysis> SA;
205 std::unique_ptr<SplitEditor> SE;
207 /// Cached per-block interference maps
208 InterferenceCache IntfCache;
210 /// All basic blocks where the current register has uses.
211 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
213 /// Global live range splitting candidate info.
214 struct GlobalSplitCandidate {
215 // Register intended for assignment, or 0.
218 // SplitKit interval index for this candidate.
221 // Interference for PhysReg.
222 InterferenceCache::Cursor Intf;
224 // Bundles where this candidate should be live.
225 BitVector LiveBundles;
226 SmallVector<unsigned, 8> ActiveBlocks;
228 void reset(InterferenceCache &Cache, MCRegister Reg) {
231 Intf.setPhysReg(Cache, Reg);
233 ActiveBlocks.clear();
236 // Set B[I] = C for every live bundle where B[I] was NoCand.
237 unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
239 for (unsigned I : LiveBundles.set_bits())
240 if (B[I] == NoCand) {
248 /// Candidate info for each PhysReg in AllocationOrder.
249 /// This vector never shrinks, but grows to the size of the largest register
251 SmallVector<GlobalSplitCandidate, 32> GlobalCand;
253 enum : unsigned { NoCand = ~0u };
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;
259 /// Callee-save register cost, calculated once per machine function.
260 BlockFrequency CSRCost;
262 /// Set of broken hints that may be reconciled later because of eviction.
263 SmallSetVector<const LiveInterval *, 8> SetOfBrokenHints;
265 /// The register cost values. This list will be recreated for each Machine
267 ArrayRef<uint8_t> RegCosts;
269 /// Flags for the live range priority calculation, determined once per
270 /// machine function.
271 bool RegClassPriorityTrumpsGlobalness;
274 RAGreedy(const RegClassFilterFunc F = allocateAllRegClasses);
276 /// Return the pass name.
277 StringRef getPassName() const override { return "Greedy Register Allocator"; }
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;
289 /// Perform register allocation.
290 bool runOnMachineFunction(MachineFunction &mf) override;
292 MachineFunctionProperties getRequiredProperties() const override {
293 return MachineFunctionProperties().set(
294 MachineFunctionProperties::Property::NoPHIs);
297 MachineFunctionProperties getClearedProperties() const override {
298 return MachineFunctionProperties().set(
299 MachineFunctionProperties::Property::IsSSA);
305 MCRegister selectOrSplitImpl(const LiveInterval &,
306 SmallVectorImpl<Register> &, SmallVirtRegSet &,
307 RecoloringStack &, unsigned = 0);
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);
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);
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
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 &,
366 bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &,
367 SmallVirtRegSet &, RecoloringStack &, unsigned);
368 void tryHintRecoloring(const LiveInterval &);
369 void tryHintsRecoloring();
371 /// Model the information carried by one end of a copy.
373 /// The frequency of the copy.
375 /// The virtual register or physical register.
377 /// Its currently assigned register.
378 /// In case of a physical register Reg == PhysReg.
381 HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg)
382 : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
384 using HintsInfo = SmallVector<HintInfo, 4>;
386 BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);
387 void collectHintInfo(Register, HintsInfo &);
389 /// Greedy RA statistic to remark.
390 struct RAGreedyStats {
391 unsigned Reloads = 0;
392 unsigned FoldedReloads = 0;
393 unsigned ZeroCostFoldedReloads = 0;
395 unsigned FoldedSpills = 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;
404 return !(Reloads || FoldedReloads || Spills || FoldedSpills ||
405 ZeroCostFoldedReloads || Copies);
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;
422 void report(MachineOptimizationRemarkMissed &R);
425 /// Compute statistic for a basic block.
426 RAGreedyStats computeStats(MachineBasicBlock &MBB);
428 /// Compute and report statistic through a remark.
429 RAGreedyStats reportStats(MachineLoop *L);
431 /// Report the statistic for each loop.
435 #endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_