12#ifndef LLVM_CODEGEN_REGALLOCGREEDY_H_
13#define LLVM_CODEGEN_REGALLOCGREEDY_H_
47class LiveDebugVariables;
50class MachineBasicBlock;
51class MachineBlockFrequencyInfo;
52class MachineDominatorTree;
55class MachineOptimizationRemarkEmitter;
56class MachineOptimizationRemarkMissed;
80 unsigned NextCascade = 1;
89 return getStage(VirtReg.
reg());
98 setStage(VirtReg.
reg(), Stage);
105 return getStage(
Reg);
116 unsigned Cascade = getCascade(
Reg);
118 Cascade = NextCascade++;
119 setCascade(
Reg, Cascade);
125 unsigned Cascade = getCascade(
Reg);
127 Cascade = NextCascade;
131 template <
typename Iterator>
133 for (; Begin !=
End; ++Begin) {
153 return RegClassPriorityTrumpsGlobalness;
160 using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;
165 using RecoloringStack =
185 std::unique_ptr<Spiller> SpillerInstance;
187 std::unique_ptr<VirtRegAuxInfo> VRAI;
188 std::optional<ExtraRegInfo> ExtraInfo;
189 std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor;
191 std::unique_ptr<RegAllocPriorityAdvisor> PriorityAdvisor;
207 uint8_t CutOffInfo = CutOffStage::CO_None;
210 static const char *
const StageName[];
214 std::unique_ptr<SplitAnalysis> SA;
215 std::unique_ptr<SplitEditor> SE;
218 InterferenceCache IntfCache;
221 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
224 struct GlobalSplitCandidate {
232 InterferenceCache::Cursor Intf;
235 BitVector LiveBundles;
236 SmallVector<unsigned, 8> ActiveBlocks;
238 void reset(InterferenceCache &Cache, MCRegister
Reg) {
241 Intf.setPhysReg(Cache,
Reg);
243 ActiveBlocks.clear();
247 unsigned getBundles(SmallVectorImpl<unsigned> &
B,
unsigned C) {
249 for (
unsigned I : LiveBundles.set_bits())
250 if (
B[
I] == NoCand) {
261 SmallVector<GlobalSplitCandidate, 32> GlobalCand;
263 enum :
unsigned {
NoCand = ~0
u };
267 SmallVector<unsigned, 32> BundleCand;
270 BlockFrequency CSRCost;
273 SmallSetVector<const LiveInterval *, 8> SetOfBrokenHints;
277 ArrayRef<uint8_t> RegCosts;
281 bool RegClassPriorityTrumpsGlobalness =
false;
283 bool ReverseLocalAssignment =
false;
286 RAGreedy(
const RegClassFilterFunc
F = allocateAllRegClasses);
293 void releaseMemory()
override;
299 void aboutToRemoveInterval(
const LiveInterval &)
override;
306 MachineFunctionProperties::Property::NoPHIs);
311 MachineFunctionProperties::Property::IsSSA);
321 bool LRE_CanEraseVirtReg(
Register)
override;
322 void LRE_WillShrinkVirtReg(
Register)
override;
327 bool hasVirtRegAlloc();
331 bool growRegion(GlobalSplitCandidate &Cand);
334 bool calcCompactRegion(GlobalSplitCandidate &);
339 bool mayRecolorAllInterferences(
MCRegister PhysReg,
352 unsigned calculateRegionSplitCostAroundReg(
MCPhysReg PhysReg,
358 unsigned calculateRegionSplitCost(
const LiveInterval &VirtReg,
361 unsigned &NumCands,
bool IgnoreCSR);
363 unsigned doRegionSplit(
const LiveInterval &VirtReg,
unsigned BestCand,
373 uint8_t &CostPerUseLimit,
375 void initializeCSRCost();
391 void tryHintsRecoloring();
404 : Freq(Freq),
Reg(
Reg), PhysReg(PhysReg) {}
406 using HintsInfo = SmallVector<HintInfo, 4>;
408 BlockFrequency getBrokenHintFreq(
const HintsInfo &, MCRegister);
409 void collectHintInfo(
Register, HintsInfo &);
412 struct RAGreedyStats {
413 unsigned Reloads = 0;
414 unsigned FoldedReloads = 0;
415 unsigned ZeroCostFoldedReloads = 0;
417 unsigned FoldedSpills = 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;
426 return !(Reloads || FoldedReloads || Spills || FoldedSpills ||
427 ZeroCostFoldedReloads ||
Copies);
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;
437 ReloadsCost += other.ReloadsCost;
438 FoldedReloadsCost += other.FoldedReloadsCost;
439 SpillsCost += other.SpillsCost;
440 FoldedSpillsCost += other.FoldedSpillsCost;
441 CopiesCost += other.CopiesCost;
444 void report(MachineOptimizationRemarkMissed &R);
448 RAGreedyStats computeStats(MachineBasicBlock &
MBB);
451 RAGreedyStats reportStats(MachineLoop *L);
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
#define LLVM_LIBRARY_VISIBILITY
This file defines the DenseMap class.
const HexagonInstrInfo * TII
This file implements an indexed map.
Promote Memory to Register
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),...
Cursor - The primary query interface for the block interference cache.
LiveInterval - This class represents the liveness of a register, or stack slot.
Callback methods for LiveRangeEdit owners.
Wrapper class representing physical registers. Should be passed by value.
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)
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
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...
Wrapper class representing virtual and physical registers.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
TargetInstrInfo - Interface to description of machine instruction set.
This is an optimization pass for GlobalISel generic memory operations.
@ RS_New
Newly created live range that has never been queued.