class RAGreedy

Declaration

class RAGreedy : public MachineFunctionPass,
                 public RegAllocBase,
                 private Delegate { /* full declaration omitted */ };

Description

Interface to the eviction advisor, which is responsible for making a decision as to which live ranges should be evicted (if any).

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:60

Inherits from: MachineFunctionPass, RegAllocBase, LiveRangeEdit::Delegate

Member Variables

private llvm::MachineFunction* MF
private const llvm::TargetInstrInfo* TII
private llvm::SlotIndexes* Indexes
private llvm::MachineBlockFrequencyInfo* MBFI
private llvm::MachineDominatorTree* DomTree
private llvm::MachineLoopInfo* Loops
private llvm::MachineOptimizationRemarkEmitter* ORE
private llvm::EdgeBundles* Bundles
private llvm::SpillPlacement* SpillPlacer
private llvm::LiveDebugVariables* DebugVars
private std::unique_ptr<Spiller> SpillerInstance
private llvm::RAGreedy::PQueue Queue
private std::unique_ptr<VirtRegAuxInfo> VRAI
private Optional<llvm::RAGreedy::ExtraRegInfo> ExtraInfo
private std::unique_ptr<RegAllocEvictionAdvisor> EvictAdvisor
private uint8_t CutOffInfo
private std::unique_ptr<SplitAnalysis> SA
private std::unique_ptr<SplitEditor> SE
private llvm::InterferenceCache IntfCache
Cached per-block interference maps
private SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints
All basic blocks where the current register has uses.
private SmallVector<llvm::RAGreedy::GlobalSplitCandidate, 32> GlobalCand
Candidate info for each PhysReg in AllocationOrder. This vector never shrinks, but grows to the size of the largest register class.
private SmallVector<unsigned int, 32> BundleCand
Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to NoCand which indicates the stack interval.
private llvm::BlockFrequency CSRCost
Callee-save register cost, calculated once per machine function.
private SmallSetVector<const llvm::LiveInterval*, 8> SetOfBrokenHints
Set of broken hints that may be reconciled later because of eviction.
private ArrayRef<uint8_t> RegCosts
The register cost values. This list will be recreated for each Machine Function
private bool RegClassPriorityTrumpsGlobalness
Flags for the live range priority calculation, determined once per machine function.
private bool ReverseLocalAssignment
private static const char* const[] StageName
public static char ID

Inherited from RegAllocBase:

protected TRI = nullptr
protected MRI = nullptr
protected VRM = nullptr
protected LIS = nullptr
protected Matrix = nullptr
protected RegClassInfo
protected ShouldAllocateClass
protected DeadRemats
protected static TimerGroupName
protected static TimerGroupDescription
public static VerifyEnabled

Method Overview

  • private bool LRE_CanEraseVirtReg(llvm::Register)
  • private void LRE_DidCloneVirtReg(llvm::Register, llvm::Register)
  • private void LRE_WillShrinkVirtReg(llvm::Register)
  • public RAGreedy(const llvm::RegClassFilterFunc F = allocateAllRegClasses)
  • public void aboutToRemoveInterval(const llvm::LiveInterval &)
  • private bool addSplitConstraints(InterferenceCache::Cursor, llvm::BlockFrequency &)
  • private bool addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned int>)
  • private bool calcCompactRegion(llvm::RAGreedy::GlobalSplitCandidate &)
  • private void calcGapWeights(llvm::MCRegister, SmallVectorImpl<float> &)
  • private llvm::BlockFrequency calcGlobalSplitCost(llvm::RAGreedy::GlobalSplitCandidate &, const llvm::AllocationOrder & Order)
  • private llvm::BlockFrequency calcSpillCost()
  • private unsigned int calculateRegionSplitCost(const llvm::LiveInterval & VirtReg, llvm::AllocationOrder & Order, llvm::BlockFrequency & BestCost, unsigned int & NumCands, bool IgnoreCSR)
  • private void collectHintInfo(llvm::Register, llvm::RAGreedy::HintsInfo &)
  • private llvm::RAGreedy::RAGreedyStats computeStats(llvm::MachineBasicBlock & MBB)
  • public const llvm::LiveInterval * dequeue()
  • private const llvm::LiveInterval * dequeue(llvm::RAGreedy::PQueue & CurQueue)
  • private unsigned int doRegionSplit(const llvm::LiveInterval & VirtReg, unsigned int BestCand, bool HasCompact, SmallVectorImpl<llvm::Register> & NewVRegs)
  • private void enqueue(llvm::RAGreedy::PQueue & CurQueue, const llvm::LiveInterval * LI)
  • public void enqueueImpl(const llvm::LiveInterval * LI)
  • private void evictInterference(const llvm::LiveInterval &, llvm::MCRegister, SmallVectorImpl<llvm::Register> &)
  • public void getAnalysisUsage(llvm::AnalysisUsage & AU) const
  • private llvm::BlockFrequency getBrokenHintFreq(const llvm::RAGreedy::HintsInfo &, llvm::MCRegister)
  • public llvm::MachineFunctionProperties getClearedProperties() const
  • public const llvm::RAGreedy::ExtraRegInfo & getExtraInfo() const
  • public llvm::LiveRegMatrix * getInterferenceMatrix() const
  • public llvm::LiveIntervals * getLiveIntervals() const
  • public llvm::StringRef getPassName() const
  • public size_t getQueueSize() const
  • public const llvm::RegisterClassInfo & getRegClassInfo() const
  • public llvm::MachineFunctionProperties getRequiredProperties() const
  • public llvm::VirtRegMap * getVirtRegMap() const
  • private bool growRegion(llvm::RAGreedy::GlobalSplitCandidate & Cand)
  • private bool hasVirtRegAlloc()
  • private void initializeCSRCost()
  • private bool mayRecolorAllInterferences(llvm::MCRegister PhysReg, const llvm::LiveInterval & VirtReg, llvm::RAGreedy::SmallLISet & RecoloringCandidates, const llvm::SmallVirtRegSet & FixedRegisters)
  • public void releaseMemory()
  • private void reportStats()
  • private llvm::RAGreedy::RAGreedyStats reportStats(llvm::MachineLoop * L)
  • public bool runOnMachineFunction(llvm::MachineFunction & mf)
  • public llvm::MCRegister selectOrSplit(const llvm::LiveInterval &, SmallVectorImpl<llvm::Register> &)
  • private llvm::MCRegister selectOrSplitImpl(const llvm::LiveInterval &, SmallVectorImpl<llvm::Register> &, llvm::SmallVirtRegSet &, llvm::RAGreedy::RecoloringStack &, unsigned int = 0)
  • public llvm::Spiller & spiller()
  • private void splitAroundRegion(llvm::LiveRangeEdit &, ArrayRef<unsigned int>)
  • private llvm::MCRegister tryAssign(const llvm::LiveInterval &, llvm::AllocationOrder &, SmallVectorImpl<llvm::Register> &, const llvm::SmallVirtRegSet &)
  • private llvm::MCRegister tryAssignCSRFirstTime(const llvm::LiveInterval & VirtReg, llvm::AllocationOrder & Order, llvm::MCRegister PhysReg, uint8_t & CostPerUseLimit, SmallVectorImpl<llvm::Register> & NewVRegs)
  • private unsigned int tryBlockSplit(const llvm::LiveInterval &, llvm::AllocationOrder &, SmallVectorImpl<llvm::Register> &)
  • private llvm::MCRegister tryEvict(const llvm::LiveInterval &, llvm::AllocationOrder &, SmallVectorImpl<llvm::Register> &, uint8_t, const llvm::SmallVirtRegSet &)
  • private void tryHintRecoloring(const llvm::LiveInterval &)
  • private void tryHintsRecoloring()
  • private unsigned int tryInstructionSplit(const llvm::LiveInterval &, llvm::AllocationOrder &, SmallVectorImpl<llvm::Register> &)
  • private unsigned int tryLastChanceRecoloring(const llvm::LiveInterval &, llvm::AllocationOrder &, SmallVectorImpl<llvm::Register> &, llvm::SmallVirtRegSet &, llvm::RAGreedy::RecoloringStack &, unsigned int)
  • private unsigned int tryLocalSplit(const llvm::LiveInterval &, llvm::AllocationOrder &, SmallVectorImpl<llvm::Register> &)
  • private bool tryRecoloringCandidates(llvm::RAGreedy::PQueue &, SmallVectorImpl<llvm::Register> &, llvm::SmallVirtRegSet &, llvm::RAGreedy::RecoloringStack &, unsigned int)
  • private llvm::MCRegister tryRegionSplit(const llvm::LiveInterval &, llvm::AllocationOrder &, SmallVectorImpl<llvm::Register> &)
  • private unsigned int trySplit(const llvm::LiveInterval &, llvm::AllocationOrder &, SmallVectorImpl<llvm::Register> &, const llvm::SmallVirtRegSet &)

Inherited from RegAllocBase:

Inherited from MachineFunctionPass:

Inherited from FunctionPass:

Inherited from Pass:

Methods

bool LRE_CanEraseVirtReg(llvm::Register)

Description

Called when a virtual register is no longer used. Return false to defer its deletion from LiveIntervals.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:311

Parameters

llvm::Register 

void LRE_DidCloneVirtReg(llvm::Register,
                         llvm::Register)

Description

Called after cloning a virtual register. This is used for new registers representing connected components of Old.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:313

Parameters

llvm::Register
llvm::Register 

void LRE_WillShrinkVirtReg(llvm::Register)

Description

Called before shrinking the live range of a virtual register.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:312

Parameters

llvm::Register 

RAGreedy(const llvm::RegClassFilterFunc F =
             allocateAllRegClasses)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:276

Parameters

const llvm::RegClassFilterFunc F = allocateAllRegClasses

void aboutToRemoveInterval(
    const llvm::LiveInterval&)

Description

Method called when the allocator is about to remove a LiveInterval.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:289

Parameters

const llvm::LiveInterval& 

bool addSplitConstraints(
    InterferenceCache::Cursor,
    llvm::BlockFrequency&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:319

Parameters

InterferenceCache::Cursor
llvm::BlockFrequency& 

bool addThroughConstraints(
    InterferenceCache::Cursor,
    ArrayRef<unsigned int>)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:320

Parameters

InterferenceCache::Cursor
ArrayRef<unsigned int> 

bool calcCompactRegion(
    llvm::RAGreedy::GlobalSplitCandidate&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:324

Parameters

llvm::RAGreedy::GlobalSplitCandidate& 

void calcGapWeights(llvm::MCRegister,
                    SmallVectorImpl<float>&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:326

Parameters

llvm::MCRegister
SmallVectorImpl<float>& 

llvm::BlockFrequency calcGlobalSplitCost(
    llvm::RAGreedy::GlobalSplitCandidate&,
    const llvm::AllocationOrder& Order)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:322

Parameters

llvm::RAGreedy::GlobalSplitCandidate&
const llvm::AllocationOrder& Order

llvm::BlockFrequency calcSpillCost()

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:318

unsigned int calculateRegionSplitCost(
    const llvm::LiveInterval& VirtReg,
    llvm::AllocationOrder& Order,
    llvm::BlockFrequency& BestCost,
    unsigned int& NumCands,
    bool IgnoreCSR)

Description

Calculate cost of region splitting.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:342

Parameters

const llvm::LiveInterval& VirtReg
llvm::AllocationOrder& Order
llvm::BlockFrequency& BestCost
unsigned int& NumCands
bool IgnoreCSR

void collectHintInfo(llvm::Register,
                     llvm::RAGreedy::HintsInfo&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:389

Parameters

llvm::Register
llvm::RAGreedy::HintsInfo& 

llvm::RAGreedy::RAGreedyStats computeStats(
    llvm::MachineBasicBlock& MBB)

Description

Compute statistic for a basic block.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:428

Parameters

llvm::MachineBasicBlock& MBB

const llvm::LiveInterval* dequeue()

Description

dequeue - Return the next unassigned register, or NULL.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:286

const llvm::LiveInterval* dequeue(
    llvm::RAGreedy::PQueue& CurQueue)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:315

Parameters

llvm::RAGreedy::PQueue& CurQueue

unsigned int doRegionSplit(
    const llvm::LiveInterval& VirtReg,
    unsigned int BestCand,
    bool HasCompact,
    SmallVectorImpl<llvm::Register>& NewVRegs)

Description

Perform region splitting.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:347

Parameters

const llvm::LiveInterval& VirtReg
unsigned int BestCand
bool HasCompact
SmallVectorImpl<llvm::Register>& NewVRegs

void enqueue(llvm::RAGreedy::PQueue& CurQueue,
             const llvm::LiveInterval* LI)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:314

Parameters

llvm::RAGreedy::PQueue& CurQueue
const llvm::LiveInterval* LI

void enqueueImpl(const llvm::LiveInterval* LI)

Description

enqueue - Add VirtReg to the priority queue of unassigned registers.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:285

Parameters

const llvm::LiveInterval* LI

void evictInterference(
    const llvm::LiveInterval&,
    llvm::MCRegister,
    SmallVectorImpl<llvm::Register>&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:327

Parameters

const llvm::LiveInterval&
llvm::MCRegister
SmallVectorImpl<llvm::Register>& 

void getAnalysisUsage(
    llvm::AnalysisUsage& AU) const

Description

RAGreedy analysis usage.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:282

Parameters

llvm::AnalysisUsage& AU

llvm::BlockFrequency getBrokenHintFreq(
    const llvm::RAGreedy::HintsInfo&,
    llvm::MCRegister)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:388

Parameters

const llvm::RAGreedy::HintsInfo&
llvm::MCRegister 

llvm::MachineFunctionProperties
getClearedProperties() const

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:299

const llvm::RAGreedy::ExtraRegInfo& getExtraInfo()
    const

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:146

llvm::LiveRegMatrix* getInterferenceMatrix() const

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:142

llvm::LiveIntervals* getLiveIntervals() const

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:143

llvm::StringRef getPassName() const

Description

Return the pass name.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:279

size_t getQueueSize() const

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:147

const llvm::RegisterClassInfo& getRegClassInfo()
    const

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:145

llvm::MachineFunctionProperties
getRequiredProperties() const

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:294

llvm::VirtRegMap* getVirtRegMap() const

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:144

bool growRegion(
    llvm::RAGreedy::GlobalSplitCandidate& Cand)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:321

Parameters

llvm::RAGreedy::GlobalSplitCandidate& Cand

bool hasVirtRegAlloc()

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:317

void initializeCSRCost()

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:355

bool mayRecolorAllInterferences(
    llvm::MCRegister PhysReg,
    const llvm::LiveInterval& VirtReg,
    llvm::RAGreedy::SmallLISet&
        RecoloringCandidates,
    const llvm::SmallVirtRegSet& FixedRegisters)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:329

Parameters

llvm::MCRegister PhysReg
const llvm::LiveInterval& VirtReg
llvm::RAGreedy::SmallLISet& RecoloringCandidates
const llvm::SmallVirtRegSet& FixedRegisters

void releaseMemory()

Description

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memory when it is no longer needed. The default behavior of passes is to hold onto memory for the entire duration of their lifetime (which is the entire compile time). For pipelined passes, this is not a big deal because that memory gets recycled every time the pass is invoked on another program unit. For IP passes, it is more important to free memory when it is unused. Optionally implement this function to release pass memory when it is no longer used.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:283

void reportStats()

Description

Report the statistic for each loop.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:434

llvm::RAGreedy::RAGreedyStats reportStats(
    llvm::MachineLoop* L)

Description

Compute and report statistic through a remark.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:431

Parameters

llvm::MachineLoop* L

bool runOnMachineFunction(
    llvm::MachineFunction& mf)

Description

Perform register allocation.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:292

Parameters

llvm::MachineFunction& mf

llvm::MCRegister selectOrSplit(
    const llvm::LiveInterval&,
    SmallVectorImpl<llvm::Register>&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:287

Parameters

const llvm::LiveInterval&
SmallVectorImpl<llvm::Register>& 

llvm::MCRegister selectOrSplitImpl(
    const llvm::LiveInterval&,
    SmallVectorImpl<llvm::Register>&,
    llvm::SmallVirtRegSet&,
    llvm::RAGreedy::RecoloringStack&,
    unsigned int = 0)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:307

Parameters

const llvm::LiveInterval&
SmallVectorImpl<llvm::Register>&
llvm::SmallVirtRegSet&
llvm::RAGreedy::RecoloringStack&
unsigned int = 0

llvm::Spiller& spiller()

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:284

void splitAroundRegion(llvm::LiveRangeEdit&,
                       ArrayRef<unsigned int>)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:325

Parameters

llvm::LiveRangeEdit&
ArrayRef<unsigned int> 

llvm::MCRegister tryAssign(
    const llvm::LiveInterval&,
    llvm::AllocationOrder&,
    SmallVectorImpl<llvm::Register>&,
    const llvm::SmallVirtRegSet&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:334

Parameters

const llvm::LiveInterval&
llvm::AllocationOrder&
SmallVectorImpl<llvm::Register>&
const llvm::SmallVirtRegSet& 

llvm::MCRegister tryAssignCSRFirstTime(
    const llvm::LiveInterval& VirtReg,
    llvm::AllocationOrder& Order,
    llvm::MCRegister PhysReg,
    uint8_t& CostPerUseLimit,
    SmallVectorImpl<llvm::Register>& NewVRegs)

Description

Check other options before using a callee-saved register for the first time.

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:351

Parameters

const llvm::LiveInterval& VirtReg
llvm::AllocationOrder& Order
llvm::MCRegister PhysReg
uint8_t& CostPerUseLimit
SmallVectorImpl<llvm::Register>& NewVRegs

unsigned int tryBlockSplit(
    const llvm::LiveInterval&,
    llvm::AllocationOrder&,
    SmallVectorImpl<llvm::Register>&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:356

Parameters

const llvm::LiveInterval&
llvm::AllocationOrder&
SmallVectorImpl<llvm::Register>& 

llvm::MCRegister tryEvict(
    const llvm::LiveInterval&,
    llvm::AllocationOrder&,
    SmallVectorImpl<llvm::Register>&,
    uint8_t,
    const llvm::SmallVirtRegSet&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:336

Parameters

const llvm::LiveInterval&
llvm::AllocationOrder&
SmallVectorImpl<llvm::Register>&
uint8_t
const llvm::SmallVirtRegSet& 

void tryHintRecoloring(const llvm::LiveInterval&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:370

Parameters

const llvm::LiveInterval& 

void tryHintsRecoloring()

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:371

unsigned int tryInstructionSplit(
    const llvm::LiveInterval&,
    llvm::AllocationOrder&,
    SmallVectorImpl<llvm::Register>&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:358

Parameters

const llvm::LiveInterval&
llvm::AllocationOrder&
SmallVectorImpl<llvm::Register>& 

unsigned int tryLastChanceRecoloring(
    const llvm::LiveInterval&,
    llvm::AllocationOrder&,
    SmallVectorImpl<llvm::Register>&,
    llvm::SmallVirtRegSet&,
    llvm::RAGreedy::RecoloringStack&,
    unsigned int)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:364

Parameters

const llvm::LiveInterval&
llvm::AllocationOrder&
SmallVectorImpl<llvm::Register>&
llvm::SmallVirtRegSet&
llvm::RAGreedy::RecoloringStack&
unsigned int 

unsigned int tryLocalSplit(
    const llvm::LiveInterval&,
    llvm::AllocationOrder&,
    SmallVectorImpl<llvm::Register>&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:360

Parameters

const llvm::LiveInterval&
llvm::AllocationOrder&
SmallVectorImpl<llvm::Register>& 

bool tryRecoloringCandidates(
    llvm::RAGreedy::PQueue&,
    SmallVectorImpl<llvm::Register>&,
    llvm::SmallVirtRegSet&,
    llvm::RAGreedy::RecoloringStack&,
    unsigned int)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:368

Parameters

llvm::RAGreedy::PQueue&
SmallVectorImpl<llvm::Register>&
llvm::SmallVirtRegSet&
llvm::RAGreedy::RecoloringStack&
unsigned int 

llvm::MCRegister tryRegionSplit(
    const llvm::LiveInterval&,
    llvm::AllocationOrder&,
    SmallVectorImpl<llvm::Register>&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:339

Parameters

const llvm::LiveInterval&
llvm::AllocationOrder&
SmallVectorImpl<llvm::Register>& 

unsigned int trySplit(
    const llvm::LiveInterval&,
    llvm::AllocationOrder&,
    SmallVectorImpl<llvm::Register>&,
    const llvm::SmallVirtRegSet&)

Declared at: llvm/lib/CodeGen/RegAllocGreedy.h:362

Parameters

const llvm::LiveInterval&
llvm::AllocationOrder&
SmallVectorImpl<llvm::Register>&
const llvm::SmallVirtRegSet&