LLVM 18.0.0git
RegAllocGreedy.h
Go to the documentation of this file.
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"
19#include "SpillPlacement.h"
20#include "SplitKit.h"
21#include "llvm/ADT/ArrayRef.h"
22#include "llvm/ADT/BitVector.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/IndexedMap.h"
25#include "llvm/ADT/SetVector.h"
28#include "llvm/ADT/StringRef.h"
37#include <algorithm>
38#include <cstdint>
39#include <memory>
40#include <queue>
41#include <utility>
42
43namespace llvm {
44class AllocationOrder;
45class AnalysisUsage;
46class EdgeBundles;
47class LiveDebugVariables;
48class LiveIntervals;
49class LiveRegMatrix;
50class MachineBasicBlock;
51class MachineBlockFrequencyInfo;
52class MachineDominatorTree;
53class MachineLoop;
54class MachineLoopInfo;
55class MachineOptimizationRemarkEmitter;
56class MachineOptimizationRemarkMissed;
57class SlotIndexes;
58class TargetInstrInfo;
59class VirtRegMap;
60
62 public RegAllocBase,
64 // Interface to eviction advisers
65public:
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
80 unsigned NextCascade = 1;
81
82 public:
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(VirtReg.reg());
90 }
91
93 Info.grow(Reg.id());
94 Info[Reg].Stage = Stage;
95 }
96
97 void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
98 setStage(VirtReg.reg(), Stage);
99 }
100
101 /// Return the current stage of the register, if present, otherwise
102 /// initialize it and return that.
104 Info.grow(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(Reg.id());
112 Info[Reg].Cascade = Cascade;
113 }
114
116 unsigned Cascade = getCascade(Reg);
117 if (!Cascade) {
118 Cascade = NextCascade++;
119 setCascade(Reg, Cascade);
120 }
121 return Cascade;
122 }
123
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(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
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
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>>;
162
163 // We need to track all tentative recolorings so we can roll back any
164 // successful and unsuccessful recoloring attempts.
165 using RecoloringStack =
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;
180 EdgeBundles *Bundles = nullptr;
181 SpillPlacement *SpillPlacer = nullptr;
182 LiveDebugVariables *DebugVars = nullptr;
183
184 // state
185 std::unique_ptr<Spiller> SpillerInstance;
186 PQueue Queue;
187 std::unique_ptr<VirtRegAuxInfo> VRAI;
188 std::optional<ExtraRegInfo> ExtraInfo;
189 std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor;
190
191 std::unique_ptr<RegAllocPriorityAdvisor> PriorityAdvisor;
192
193 // Enum CutOffStage to keep a track whether the register allocation failed
194 // because of the cutoffs encountered in last chance recoloring.
195 // Note: This is used as bitmask. New value should be next power of 2.
196 enum CutOffStage {
197 // No cutoffs encountered
198 CO_None = 0,
199
200 // lcr-max-depth cutoff encountered
201 CO_Depth = 1,
202
203 // lcr-max-interf cutoff encountered
204 CO_Interf = 2
205 };
206
207 uint8_t CutOffInfo = CutOffStage::CO_None;
208
209#ifndef NDEBUG
210 static const char *const StageName[];
211#endif
212
213 // splitting state.
214 std::unique_ptr<SplitAnalysis> SA;
215 std::unique_ptr<SplitEditor> SE;
216
217 /// Cached per-block interference maps
218 InterferenceCache IntfCache;
219
220 /// All basic blocks where the current register has uses.
221 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
222
223 /// Global live range splitting candidate info.
224 struct GlobalSplitCandidate {
225 // Register intended for assignment, or 0.
226 MCRegister PhysReg;
227
228 // SplitKit interval index for this candidate.
229 unsigned IntvIdx;
230
231 // Interference for PhysReg.
232 InterferenceCache::Cursor Intf;
233
234 // Bundles where this candidate should be live.
235 BitVector LiveBundles;
236 SmallVector<unsigned, 8> ActiveBlocks;
237
238 void reset(InterferenceCache &Cache, MCRegister Reg) {
239 PhysReg = Reg;
240 IntvIdx = 0;
241 Intf.setPhysReg(Cache, Reg);
242 LiveBundles.clear();
243 ActiveBlocks.clear();
244 }
245
246 // Set B[I] = C for every live bundle where B[I] was NoCand.
247 unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
248 unsigned Count = 0;
249 for (unsigned I : LiveBundles.set_bits())
250 if (B[I] == NoCand) {
251 B[I] = C;
252 Count++;
253 }
254 return Count;
255 }
256 };
257
258 /// Candidate info for each PhysReg in AllocationOrder.
259 /// This vector never shrinks, but grows to the size of the largest register
260 /// class.
261 SmallVector<GlobalSplitCandidate, 32> GlobalCand;
262
263 enum : unsigned { NoCand = ~0u };
264
265 /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
266 /// NoCand which indicates the stack interval.
267 SmallVector<unsigned, 32> BundleCand;
268
269 /// Callee-save register cost, calculated once per machine function.
270 BlockFrequency CSRCost;
271
272 /// Set of broken hints that may be reconciled later because of eviction.
273 SmallSetVector<const LiveInterval *, 8> SetOfBrokenHints;
274
275 /// The register cost values. This list will be recreated for each Machine
276 /// Function
277 ArrayRef<uint8_t> RegCosts;
278
279 /// Flags for the live range priority calculation, determined once per
280 /// machine function.
281 bool RegClassPriorityTrumpsGlobalness = false;
282
283 bool ReverseLocalAssignment = false;
284
285public:
286 RAGreedy(const RegClassFilterFunc F = allocateAllRegClasses);
287
288 /// Return the pass name.
289 StringRef getPassName() const override { return "Greedy Register Allocator"; }
290
291 /// RAGreedy analysis usage.
292 void getAnalysisUsage(AnalysisUsage &AU) const override;
293 void releaseMemory() override;
294 Spiller &spiller() override { return *SpillerInstance; }
295 void enqueueImpl(const LiveInterval *LI) override;
296 const LiveInterval *dequeue() override;
297 MCRegister selectOrSplit(const LiveInterval &,
298 SmallVectorImpl<Register> &) override;
299 void aboutToRemoveInterval(const LiveInterval &) override;
300
301 /// Perform register allocation.
302 bool runOnMachineFunction(MachineFunction &mf) override;
303
306 MachineFunctionProperties::Property::NoPHIs);
307 }
308
311 MachineFunctionProperties::Property::IsSSA);
312 }
313
314 static char ID;
315
316private:
317 MCRegister selectOrSplitImpl(const LiveInterval &,
319 RecoloringStack &, unsigned = 0);
320
321 bool LRE_CanEraseVirtReg(Register) override;
322 void LRE_WillShrinkVirtReg(Register) override;
323 void LRE_DidCloneVirtReg(Register, Register) override;
324 void enqueue(PQueue &CurQueue, const LiveInterval *LI);
325 const LiveInterval *dequeue(PQueue &CurQueue);
326
327 bool hasVirtRegAlloc();
328 BlockFrequency calcSpillCost();
329 bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency &);
330 bool addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
331 bool growRegion(GlobalSplitCandidate &Cand);
332 BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,
333 const AllocationOrder &Order);
334 bool calcCompactRegion(GlobalSplitCandidate &);
335 void splitAroundRegion(LiveRangeEdit &, ArrayRef<unsigned>);
336 void calcGapWeights(MCRegister, SmallVectorImpl<float> &);
337 void evictInterference(const LiveInterval &, MCRegister,
339 bool mayRecolorAllInterferences(MCRegister PhysReg,
340 const LiveInterval &VirtReg,
341 SmallLISet &RecoloringCandidates,
342 const SmallVirtRegSet &FixedRegisters);
343
344 MCRegister tryAssign(const LiveInterval &, AllocationOrder &,
346 MCRegister tryEvict(const LiveInterval &, AllocationOrder &,
347 SmallVectorImpl<Register> &, uint8_t,
348 const SmallVirtRegSet &);
349 MCRegister tryRegionSplit(const LiveInterval &, AllocationOrder &,
351 /// Calculate cost of region splitting around the specified register.
352 unsigned calculateRegionSplitCostAroundReg(MCPhysReg PhysReg,
353 AllocationOrder &Order,
354 BlockFrequency &BestCost,
355 unsigned &NumCands,
356 unsigned &BestCand);
357 /// Calculate cost of region splitting.
358 unsigned calculateRegionSplitCost(const LiveInterval &VirtReg,
359 AllocationOrder &Order,
360 BlockFrequency &BestCost,
361 unsigned &NumCands, bool IgnoreCSR);
362 /// Perform region splitting.
363 unsigned doRegionSplit(const LiveInterval &VirtReg, unsigned BestCand,
364 bool HasCompact, SmallVectorImpl<Register> &NewVRegs);
365 /// Try to split VirtReg around physical Hint register.
366 bool trySplitAroundHintReg(MCPhysReg Hint, const LiveInterval &VirtReg,
368 AllocationOrder &Order);
369 /// Check other options before using a callee-saved register for the first
370 /// time.
371 MCRegister tryAssignCSRFirstTime(const LiveInterval &VirtReg,
372 AllocationOrder &Order, MCRegister PhysReg,
373 uint8_t &CostPerUseLimit,
374 SmallVectorImpl<Register> &NewVRegs);
375 void initializeCSRCost();
376 unsigned tryBlockSplit(const LiveInterval &, AllocationOrder &,
378 unsigned tryInstructionSplit(const LiveInterval &, AllocationOrder &,
380 unsigned tryLocalSplit(const LiveInterval &, AllocationOrder &,
382 unsigned trySplit(const LiveInterval &, AllocationOrder &,
384 unsigned tryLastChanceRecoloring(const LiveInterval &, AllocationOrder &,
387 unsigned);
388 bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &,
389 SmallVirtRegSet &, RecoloringStack &, unsigned);
390 void tryHintRecoloring(const LiveInterval &);
391 void tryHintsRecoloring();
392
393 /// Model the information carried by one end of a copy.
394 struct HintInfo {
395 /// The frequency of the copy.
396 BlockFrequency Freq;
397 /// The virtual register or physical register.
399 /// Its currently assigned register.
400 /// In case of a physical register Reg == PhysReg.
401 MCRegister PhysReg;
402
403 HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg)
404 : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
405 };
406 using HintsInfo = SmallVector<HintInfo, 4>;
407
408 BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);
409 void collectHintInfo(Register, HintsInfo &);
410
411 /// Greedy RA statistic to remark.
412 struct RAGreedyStats {
413 unsigned Reloads = 0;
414 unsigned FoldedReloads = 0;
415 unsigned ZeroCostFoldedReloads = 0;
416 unsigned Spills = 0;
417 unsigned FoldedSpills = 0;
418 unsigned Copies = 0;
419 float ReloadsCost = 0.0f;
420 float FoldedReloadsCost = 0.0f;
421 float SpillsCost = 0.0f;
422 float FoldedSpillsCost = 0.0f;
423 float CopiesCost = 0.0f;
424
425 bool isEmpty() {
426 return !(Reloads || FoldedReloads || Spills || FoldedSpills ||
427 ZeroCostFoldedReloads || Copies);
428 }
429
430 void add(RAGreedyStats other) {
431 Reloads += other.Reloads;
432 FoldedReloads += other.FoldedReloads;
433 ZeroCostFoldedReloads += other.ZeroCostFoldedReloads;
434 Spills += other.Spills;
435 FoldedSpills += other.FoldedSpills;
436 Copies += other.Copies;
437 ReloadsCost += other.ReloadsCost;
438 FoldedReloadsCost += other.FoldedReloadsCost;
439 SpillsCost += other.SpillsCost;
440 FoldedSpillsCost += other.FoldedSpillsCost;
441 CopiesCost += other.CopiesCost;
442 }
443
444 void report(MachineOptimizationRemarkMissed &R);
445 };
446
447 /// Compute statistic for a basic block.
448 RAGreedyStats computeStats(MachineBasicBlock &MBB);
449
450 /// Compute and report statistic through a remark.
451 RAGreedyStats reportStats(MachineLoop *L);
452
453 /// Report the statistic for each loop.
454 void reportStats();
455};
456} // namespace llvm
457#endif // #ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_
MachineBasicBlock & MBB
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
#define LLVM_LIBRARY_VISIBILITY
Definition: Compiler.h:131
This file defines the DenseMap class.
bool End
Definition: ELF_riscv.cpp:469
const HexagonInstrInfo * TII
Hexagon Hardware Loops
This file implements an indexed map.
Live Register Matrix
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned Reg
Promote Memory to Register
Definition: Mem2Reg.cpp:114
SI Lower i1 Copies
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Cursor - The primary query interface for the block interference cache.
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
Register reg() const
Definition: LiveInterval.h:717
Callback methods for LiveRangeEdit owners.
Definition: LiveRangeEdit.h:45
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
Track allocation stage and eviction loop prevention during allocation.
LiveRangeStage getStage(Register Reg) const
void setCascade(Register Reg, unsigned Cascade)
unsigned getOrAssignNewCascade(Register Reg)
LiveRangeStage getStage(const LiveInterval &VirtReg) const
ExtraRegInfo(const ExtraRegInfo &)=delete
void setStage(Register Reg, LiveRangeStage Stage)
void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage)
void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage)
unsigned getCascade(Register Reg) const
unsigned getCascadeOrCurrentNext(Register Reg) const
LiveRangeStage getOrInitStage(Register Reg)
Return the current stage of the register, if present, otherwise initialize it and return that.
StringRef getPassName() const override
Return the pass name.
MachineFunctionProperties getClearedProperties() const override
const ExtraRegInfo & getExtraInfo() const
Spiller & spiller() override
MachineFunctionProperties getRequiredProperties() const override
VirtRegMap * getVirtRegMap() const
LiveIntervals * getLiveIntervals() const
const RegisterClassInfo & getRegClassInfo() const
bool getReverseLocalAssignment() const
static char ID
size_t getQueueSize() const
LiveRegMatrix * getInterferenceMatrix() const
bool getRegClassPriorityTrumpsGlobalness() const
RegAllocBase provides the register allocation driver and interface that can be extended to add intere...
Definition: RegAllocBase.h:61
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
SlotIndexes pass.
Definition: SlotIndexes.h:301
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Spiller interface.
Definition: Spiller.h:24
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ RS_New
Newly created live range that has never been queued.