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 <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 advisers
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() {}
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(Reg: VirtReg.reg());
89 }
90
91 void setStage(Register Reg, LiveRangeStage Stage) {
92 Info.grow(N: Reg.id());
93 Info[Reg].Stage = Stage;
94 }
95
96 void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
97 setStage(Reg: 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(N: 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(N: 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(N: 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 advisers
151 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 any
163 // successful and unsuccessful recoloring attempts.
164 using RecoloringStack =
165 SmallVector<std::pair<const LiveInterval *, MCRegister>, 8>;
166
167 // context
168 MachineFunction *MF = nullptr;
169
170 // Shortcuts to some useful interface.
171 const TargetInstrInfo *TII = nullptr;
172
173 // analyses
174 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 InlineSpiller
183 // Proxy for the advisors
184 RegAllocEvictionAdvisorProvider *EvictProvider = nullptr;
185 RegAllocPriorityAdvisorProvider *PriorityProvider = nullptr;
186
187 // state
188 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 failed
197 // 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 encountered
201 CO_None = 0,
202
203 // lcr-max-depth cutoff encountered
204 CO_Depth = 1,
205
206 // lcr-max-interf cutoff encountered
207 CO_Interf = 2
208 };
209
210 uint8_t CutOffInfo = CutOffStage::CO_None;
211
212#ifndef NDEBUG
213 static const char *const StageName[];
214#endif
215
216 // splitting state.
217 std::unique_ptr<SplitAnalysis> SA;
218 std::unique_ptr<SplitEditor> SE;
219
220 /// Cached per-block interference maps
221 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, PhysReg: 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 register
263 /// 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 to
269 /// 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 Machine
279 /// Function
280 ArrayRef<uint8_t> RegCosts;
281
282 /// Flags for the live range priority calculation, determined once per
283 /// 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 first
358 /// 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 llvm
445#endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_
446