LLVM 20.0.0git
Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
llvm::WindowScheduler Class Reference

The main class in the implementation of the target independent window scheduler. More...

#include "llvm/CodeGen/WindowScheduler.h"

Public Member Functions

 WindowScheduler (MachineSchedContext *C, MachineLoop &ML)
 
virtual ~WindowScheduler ()
 
bool run ()
 

Protected Member Functions

virtual ScheduleDAGInstrscreateMachineScheduler (bool OnlyBuildGraph=false)
 Two types of ScheduleDAGs are needed, one for creating dependency graphs only, and the other for list scheduling as determined by the target.
 
virtual bool initialize ()
 Initializes the algorithm and determines if it can be executed.
 
virtual void preProcess ()
 Add some related processing before running window scheduling.
 
virtual void postProcess ()
 Add some related processing after running window scheduling.
 
void backupMBB ()
 Back up the MIs in the original MBB and remove them from MBB.
 
void restoreMBB ()
 Erase the MIs in current MBB and restore the original MIs.
 
virtual void generateTripleMBB ()
 Make three copies of the original MBB to generate a new TripleMBB.
 
virtual void restoreTripleMBB ()
 Restore the order of MIs in TripleMBB after each list scheduling.
 
virtual SmallVector< unsignedgetSearchIndexes (unsigned SearchNum, unsigned SearchRatio)
 Give the folding position in the window algorithm, where different heuristics can be used.
 
virtual int calculateMaxCycle (ScheduleDAGInstrs &DAG, unsigned Offset)
 Calculate MIs execution cycle after list scheduling.
 
virtual int calculateStallCycle (unsigned Offset, int MaxCycle)
 Calculate the stall cycle between two trips after list scheduling.
 
virtual unsigned analyseII (ScheduleDAGInstrs &DAG, unsigned Offset)
 Analyzes the II value after each list scheduling.
 
virtual void schedulePhi (int Offset, unsigned &II)
 Phis are scheduled separately after each list scheduling.
 
DenseMap< MachineInstr *, int > getIssueOrder (unsigned Offset, unsigned II)
 Get the final issue order of all scheduled MIs including phis.
 
virtual void updateScheduleResult (unsigned Offset, unsigned II)
 Update the scheduling result after each list scheduling.
 
virtual bool isScheduleValid ()
 Check whether the final result of window scheduling is valid.
 
virtual void expand ()
 Using the scheduling infrastructure to expand the results of window scheduling.
 
virtual void updateLiveIntervals ()
 Update the live intervals for all registers used within MBB.
 
int getEstimatedII (ScheduleDAGInstrs &DAG)
 Estimate a II value at which all MIs will be scheduled successfully.
 
iterator_range< MachineBasicBlock::iteratorgetScheduleRange (unsigned Offset, unsigned Num)
 Gets the iterator range of MIs in the scheduling window.
 
int getOriCycle (MachineInstr *NewMI)
 Get the issue cycle of the new MI based on the cycle of the original MI.
 
MachineInstrgetOriMI (MachineInstr *NewMI)
 Get the original MI from which the new MI is cloned.
 
unsigned getOriStage (MachineInstr *OriMI, unsigned Offset)
 Get the scheduling stage, where the stage of the new MI is identical to the original MI.
 
Register getAntiRegister (MachineInstr *Phi)
 Gets the register in phi which is generated from the current MBB.
 

Protected Attributes

MachineSchedContextContext = nullptr
 
MachineFunctionMF = nullptr
 
MachineBasicBlockMBB = nullptr
 
MachineLoopLoop
 
const TargetSubtargetInfoSubtarget = nullptr
 
const TargetInstrInfoTII = nullptr
 
const TargetRegisterInfoTRI = nullptr
 
MachineRegisterInfoMRI = nullptr
 
std::unique_ptr< ScheduleDAGInstrsTripleDAG
 To innovatively identify the dependencies between MIs across two trips, we construct a DAG for a new MBB, which is created by copying the original MBB three times.
 
SmallVector< MachineInstr * > OriMIs
 OriMIs keeps the MIs removed from the original MBB.
 
SmallVector< MachineInstr * > TriMIs
 TriMIs keeps the MIs of TripleMBB, which is used to restore TripleMBB.
 
DenseMap< MachineInstr *, MachineInstr * > TriToOri
 TriToOri keeps the mappings between the MI clones in TripleMBB and their original MI.
 
DenseMap< MachineInstr *, int > OriToCycle
 OriToCycle keeps the mappings between the original MI and its issue cycle.
 
SmallVector< std::tuple< MachineInstr *, int, int, int >, 256 > SchedResult
 SchedResult keeps the result of each list scheduling, and the format of the tuple is <MI pointer, Cycle, Stage, Order ID>.
 
unsigned SchedPhiNum = 0
 SchedPhiNum records the number of phi in the original MBB, and the scheduling starts with MI after phis.
 
unsigned SchedInstrNum = 0
 SchedInstrNum records the MIs involved in scheduling in the original MBB, excluding debug instructions.
 
unsigned BestII = UINT_MAX
 BestII and BestOffset record the characteristics of the best scheduling result and are used together with SchedResult as the final window scheduling result.
 
unsigned BestOffset = 0
 
unsigned BaseII = 0
 BaseII is the II obtained when the window offset is SchedPhiNum.
 

Detailed Description

The main class in the implementation of the target independent window scheduler.

Definition at line 61 of file WindowScheduler.h.

Constructor & Destructor Documentation

◆ WindowScheduler()

WindowScheduler::WindowScheduler ( MachineSchedContext C,
MachineLoop ML 
)

Definition at line 103 of file WindowScheduler.cpp.

References createMachineScheduler(), and TripleDAG.

◆ ~WindowScheduler()

virtual llvm::WindowScheduler::~WindowScheduler ( )
inlinevirtual

Definition at line 108 of file WindowScheduler.h.

Member Function Documentation

◆ analyseII()

unsigned WindowScheduler::analyseII ( ScheduleDAGInstrs DAG,
unsigned  Offset 
)
protectedvirtual

Analyzes the II value after each list scheduling.

Definition at line 521 of file WindowScheduler.cpp.

References calculateMaxCycle(), calculateStallCycle(), llvm::dbgs(), LLVM_DEBUG, llvm::Offset, and WindowIILimit.

Referenced by run().

◆ backupMBB()

void WindowScheduler::backupMBB ( )
protected

◆ calculateMaxCycle()

int WindowScheduler::calculateMaxCycle ( ScheduleDAGInstrs DAG,
unsigned  Offset 
)
protectedvirtual

◆ calculateStallCycle()

int WindowScheduler::calculateStallCycle ( unsigned  Offset,
int  MaxCycle 
)
protectedvirtual

Calculate the stall cycle between two trips after list scheduling.

Definition at line 492 of file WindowScheduler.cpp.

References llvm::dbgs(), getOriCycle(), getScheduleRange(), LLVM_DEBUG, MI, llvm::Offset, Range, SchedInstrNum, TripleDAG, and WindowIILimit.

Referenced by analyseII().

◆ createMachineScheduler()

ScheduleDAGInstrs * WindowScheduler::createMachineScheduler ( bool  OnlyBuildGraph = false)
protectedvirtual

Two types of ScheduleDAGs are needed, one for creating dependency graphs only, and the other for list scheduling as determined by the target.

Definition at line 165 of file WindowScheduler.cpp.

References Context, llvm::TargetPassConfig::createMachineScheduler(), and llvm::MachineSchedContext::PassConfig.

Referenced by run(), and WindowScheduler().

◆ expand()

void WindowScheduler::expand ( )
protectedvirtual

Using the scheduling infrastructure to expand the results of window scheduling.

It is usually necessary to add prologue and epilogue MBBs.

Definition at line 619 of file WindowScheduler.cpp.

References A, B, llvm::ModuloScheduleExpander::cleanup(), Context, llvm::dbgs(), llvm::ModuloScheduleExpander::expand(), Info, llvm::MachineSchedContext::LIS, LLVM_DEBUG, MF, MI, SchedResult, and llvm::stable_sort().

Referenced by run().

◆ generateTripleMBB()

void WindowScheduler::generateTripleMBB ( )
protectedvirtual

◆ getAntiRegister()

Register WindowScheduler::getAntiRegister ( MachineInstr Phi)
protected

Gets the register in phi which is generated from the current MBB.

Definition at line 699 of file WindowScheduler.cpp.

References assert(), and MBB.

Referenced by generateTripleMBB(), and schedulePhi().

◆ getEstimatedII()

int WindowScheduler::getEstimatedII ( ScheduleDAGInstrs DAG)
protected

Estimate a II value at which all MIs will be scheduled successfully.

Definition at line 414 of file WindowScheduler.cpp.

References MaxDepth, and llvm::ScheduleDAG::SUnits.

Referenced by calculateMaxCycle().

◆ getIssueOrder()

DenseMap< MachineInstr *, int > WindowScheduler::getIssueOrder ( unsigned  Offset,
unsigned  II 
)
protected

◆ getOriCycle()

int WindowScheduler::getOriCycle ( MachineInstr NewMI)
protected

Get the issue cycle of the new MI based on the cycle of the original MI.

Definition at line 668 of file WindowScheduler.cpp.

References assert(), OriToCycle, and TriToOri.

Referenced by calculateMaxCycle(), calculateStallCycle(), getIssueOrder(), and schedulePhi().

◆ getOriMI()

MachineInstr * WindowScheduler::getOriMI ( MachineInstr NewMI)
protected

Get the original MI from which the new MI is cloned.

Definition at line 675 of file WindowScheduler.cpp.

References assert(), and TriToOri.

Referenced by calculateMaxCycle(), getIssueOrder(), and schedulePhi().

◆ getOriStage()

unsigned WindowScheduler::getOriStage ( MachineInstr OriMI,
unsigned  Offset 
)
protected

Get the scheduling stage, where the stage of the new MI is identical to the original MI.

Definition at line 680 of file WindowScheduler.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::find(), MI, llvm::Offset, OriMIs, and SchedPhiNum.

Referenced by calculateMaxCycle(), schedulePhi(), and updateScheduleResult().

◆ getScheduleRange()

iterator_range< MachineBasicBlock::iterator > WindowScheduler::getScheduleRange ( unsigned  Offset,
unsigned  Num 
)
protected

Gets the iterator range of MIs in the scheduling window.

Definition at line 660 of file WindowScheduler.cpp.

References llvm::MachineBasicBlock::begin(), llvm::make_range(), MBB, and llvm::Offset.

Referenced by calculateMaxCycle(), calculateStallCycle(), getIssueOrder(), and run().

◆ getSearchIndexes()

SmallVector< unsigned > WindowScheduler::getSearchIndexes ( unsigned  SearchNum,
unsigned  SearchRatio 
)
protectedvirtual

Give the folding position in the window algorithm, where different heuristics can be used.

It determines the performance and compilation time of the algorithm.

Definition at line 399 of file WindowScheduler.cpp.

References assert(), Idx, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and SchedInstrNum.

Referenced by run().

◆ initialize()

bool WindowScheduler::initialize ( )
protectedvirtual

◆ isScheduleValid()

virtual bool llvm::WindowScheduler::isScheduleValid ( )
inlineprotectedvirtual

Check whether the final result of window scheduling is valid.

Definition at line 149 of file WindowScheduler.h.

References BestOffset, and SchedPhiNum.

Referenced by run().

◆ postProcess()

void WindowScheduler::postProcess ( )
protectedvirtual

Add some related processing after running window scheduling.

Definition at line 260 of file WindowScheduler.cpp.

References restoreMBB(), and TripleDAG.

Referenced by run().

◆ preProcess()

void WindowScheduler::preProcess ( )
protectedvirtual

Add some related processing before running window scheduling.

Definition at line 248 of file WindowScheduler.cpp.

References llvm::MachineSchedContext::AA, backupMBB(), llvm::MachineBasicBlock::begin(), Context, generateTripleMBB(), llvm::MachineBasicBlock::getFirstTerminator(), MBB, and TripleDAG.

Referenced by run().

◆ restoreMBB()

void WindowScheduler::restoreMBB ( )
protected

◆ restoreTripleMBB()

void WindowScheduler::restoreTripleMBB ( )
protectedvirtual

Restore the order of MIs in TripleMBB after each list scheduling.

Definition at line 385 of file WindowScheduler.cpp.

References llvm::MachineBasicBlock::begin(), Context, llvm::LiveIntervals::handleMove(), I, llvm::MachineSchedContext::LIS, MBB, MI, llvm::SmallVectorBase< Size_T >::size(), llvm::MachineBasicBlock::splice(), and TriMIs.

Referenced by run().

◆ run()

bool WindowScheduler::run ( )

◆ schedulePhi()

void WindowScheduler::schedulePhi ( int  Offset,
unsigned II 
)
protectedvirtual

◆ updateLiveIntervals()

void WindowScheduler::updateLiveIntervals ( )
protectedvirtual

◆ updateScheduleResult()

void WindowScheduler::updateScheduleResult ( unsigned  Offset,
unsigned  II 
)
protectedvirtual

Update the scheduling result after each list scheduling.

Definition at line 592 of file WindowScheduler.cpp.

References assert(), BaseII, BestII, BestOffset, getIssueOrder(), getOriStage(), II, llvm::Offset, OriToCycle, SchedPhiNum, and SchedResult.

Referenced by run().

Member Data Documentation

◆ BaseII

unsigned llvm::WindowScheduler::BaseII = 0
protected

BaseII is the II obtained when the window offset is SchedPhiNum.

This offset is the initial position of the sliding window.

Definition at line 104 of file WindowScheduler.h.

Referenced by initialize(), and updateScheduleResult().

◆ BestII

unsigned llvm::WindowScheduler::BestII = UINT_MAX
protected

BestII and BestOffset record the characteristics of the best scheduling result and are used together with SchedResult as the final window scheduling result.

Definition at line 100 of file WindowScheduler.h.

Referenced by initialize(), run(), and updateScheduleResult().

◆ BestOffset

unsigned llvm::WindowScheduler::BestOffset = 0
protected

Definition at line 101 of file WindowScheduler.h.

Referenced by initialize(), isScheduleValid(), run(), and updateScheduleResult().

◆ Context

MachineSchedContext* llvm::WindowScheduler::Context = nullptr
protected

◆ Loop

MachineLoop& llvm::WindowScheduler::Loop
protected

Definition at line 66 of file WindowScheduler.h.

◆ MBB

MachineBasicBlock* llvm::WindowScheduler::MBB = nullptr
protected

◆ MF

MachineFunction* llvm::WindowScheduler::MF = nullptr
protected

Definition at line 64 of file WindowScheduler.h.

Referenced by expand(), generateTripleMBB(), and initialize().

◆ MRI

MachineRegisterInfo* llvm::WindowScheduler::MRI = nullptr
protected

Definition at line 70 of file WindowScheduler.h.

Referenced by generateTripleMBB(), and schedulePhi().

◆ OriMIs

SmallVector<MachineInstr *> llvm::WindowScheduler::OriMIs
protected

OriMIs keeps the MIs removed from the original MBB.

Definition at line 80 of file WindowScheduler.h.

Referenced by backupMBB(), generateTripleMBB(), getOriStage(), initialize(), and restoreMBB().

◆ OriToCycle

DenseMap<MachineInstr *, int> llvm::WindowScheduler::OriToCycle
protected

OriToCycle keeps the mappings between the original MI and its issue cycle.

Definition at line 87 of file WindowScheduler.h.

Referenced by calculateMaxCycle(), getOriCycle(), initialize(), run(), schedulePhi(), and updateScheduleResult().

◆ SchedInstrNum

unsigned llvm::WindowScheduler::SchedInstrNum = 0
protected

SchedInstrNum records the MIs involved in scheduling in the original MBB, excluding debug instructions.

Definition at line 96 of file WindowScheduler.h.

Referenced by calculateMaxCycle(), calculateStallCycle(), getIssueOrder(), getSearchIndexes(), initialize(), and run().

◆ SchedPhiNum

unsigned llvm::WindowScheduler::SchedPhiNum = 0
protected

SchedPhiNum records the number of phi in the original MBB, and the scheduling starts with MI after phis.

Definition at line 93 of file WindowScheduler.h.

Referenced by getOriStage(), initialize(), isScheduleValid(), run(), and updateScheduleResult().

◆ SchedResult

SmallVector<std::tuple<MachineInstr *, int, int, int>, 256> llvm::WindowScheduler::SchedResult
protected

SchedResult keeps the result of each list scheduling, and the format of the tuple is <MI pointer, Cycle, Stage, Order ID>.

Definition at line 90 of file WindowScheduler.h.

Referenced by expand(), initialize(), and updateScheduleResult().

◆ Subtarget

const TargetSubtargetInfo* llvm::WindowScheduler::Subtarget = nullptr
protected

Definition at line 67 of file WindowScheduler.h.

Referenced by calculateMaxCycle(), and initialize().

◆ TII

const TargetInstrInfo* llvm::WindowScheduler::TII = nullptr
protected

Definition at line 68 of file WindowScheduler.h.

Referenced by calculateMaxCycle(), and initialize().

◆ TRI

const TargetRegisterInfo* llvm::WindowScheduler::TRI = nullptr
protected

Definition at line 69 of file WindowScheduler.h.

Referenced by generateTripleMBB().

◆ TriMIs

SmallVector<MachineInstr *> llvm::WindowScheduler::TriMIs
protected

TriMIs keeps the MIs of TripleMBB, which is used to restore TripleMBB.

Definition at line 82 of file WindowScheduler.h.

Referenced by generateTripleMBB(), initialize(), and restoreTripleMBB().

◆ TripleDAG

std::unique_ptr<ScheduleDAGInstrs> llvm::WindowScheduler::TripleDAG
protected

To innovatively identify the dependencies between MIs across two trips, we construct a DAG for a new MBB, which is created by copying the original MBB three times.

We refer to this new MBB as 'TripleMBB' and the corresponding DAG as 'TripleDAG'. If the dependencies are more than two trips, we avoid applying window algorithm by identifying successive phis in the old MBB.

Definition at line 78 of file WindowScheduler.h.

Referenced by calculateStallCycle(), postProcess(), preProcess(), schedulePhi(), and WindowScheduler().

◆ TriToOri

DenseMap<MachineInstr *, MachineInstr *> llvm::WindowScheduler::TriToOri
protected

TriToOri keeps the mappings between the MI clones in TripleMBB and their original MI.

Definition at line 85 of file WindowScheduler.h.

Referenced by generateTripleMBB(), getOriCycle(), getOriMI(), and initialize().


The documentation for this class was generated from the following files: