LLVM 20.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/IndexedMap.h"
24#include "llvm/ADT/SetVector.h"
26#include "llvm/ADT/StringRef.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
60 public RegAllocBase,
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
78 unsigned NextCascade = 1;
79
80 public:
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(VirtReg.reg());
88 }
89
91 Info.grow(Reg.id());
92 Info[Reg].Stage = Stage;
93 }
94
95 void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
96 setStage(VirtReg.reg(), Stage);
97 }
98
99 /// Return the current stage of the register, if present, otherwise
100 /// initialize it and return that.
102 Info.grow(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(Reg.id());
110 Info[Reg].Cascade = Cascade;
111 }
112
114 unsigned Cascade = getCascade(Reg);
115 if (!Cascade) {
116 Cascade = NextCascade++;
117 setCascade(Reg, Cascade);
118 }
119 return Cascade;
120 }
121
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(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
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
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>>;
160
161 // We need to track all tentative recolorings so we can roll back any
162 // successful and unsuccessful recoloring attempts.
163 using RecoloringStack =
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;
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, 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
304 MachineFunctionProperties::Property::NoPHIs);
305 }
306
309 MachineFunctionProperties::Property::IsSSA);
310 }
311
312 static char ID;
313
314private:
315 MCRegister selectOrSplitImpl(const LiveInterval &,
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,
337 bool mayRecolorAllInterferences(MCRegister PhysReg,
338 const LiveInterval &VirtReg,
339 SmallLISet &RecoloringCandidates,
340 const SmallVirtRegSet &FixedRegisters);
341
342 MCRegister tryAssign(const LiveInterval &, AllocationOrder &,
344 MCRegister tryEvict(const LiveInterval &, AllocationOrder &,
345 SmallVectorImpl<Register> &, uint8_t,
346 const SmallVirtRegSet &);
347 MCRegister tryRegionSplit(const LiveInterval &, AllocationOrder &,
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,
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 &,
376 unsigned tryInstructionSplit(const LiveInterval &, AllocationOrder &,
378 unsigned tryLocalSplit(const LiveInterval &, AllocationOrder &,
380 unsigned trySplit(const LiveInterval &, AllocationOrder &,
382 unsigned tryLastChanceRecoloring(const LiveInterval &, AllocationOrder &,
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.
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_
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
bool End
Definition: ELF_riscv.cpp:480
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:110
SI Lower i1 Copies
This file implements a set that has insertion order iteration characteristics.
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:687
Register reg() const
Definition: LiveInterval.h:718
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:62
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
SlotIndexes pass.
Definition: SlotIndexes.h:297
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:587
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
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.