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