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