LLVM: llvm::WindowScheduler Class Reference (original) (raw)

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

#include "[llvm/CodeGen/WindowScheduler.h](WindowScheduler%5F8h%5Fsource.html)"

Protected Member Functions
virtual ScheduleDAGInstrs * createMachineScheduler (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< unsigned > getSearchIndexes (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::iterator > getScheduleRange (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.
MachineInstr * getOriMI (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
MachineSchedContext * Context = nullptr
MachineFunction * MF = nullptr
MachineBasicBlock * MBB = nullptr
MachineLoop & Loop
const TargetSubtargetInfo * Subtarget = nullptr
const TargetInstrInfo * TII = nullptr
const TargetRegisterInfo * TRI = nullptr
MachineRegisterInfo * MRI = nullptr
std::unique_ptr< ScheduleDAGInstrs > TripleDAG
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.

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

Definition at line 61 of file WindowScheduler.h.

Definition at line 104 of file WindowScheduler.cpp.

References llvm::CallingConv::C, Context, createMachineScheduler(), Loop, MBB, MF, ML, MRI, Subtarget, TII, TRI, and TripleDAG.

◆ ~WindowScheduler()

virtual llvm::WindowScheduler::~WindowScheduler ( ) virtualdefault

◆ analyseII()

◆ backupMBB()

void WindowScheduler::backupMBB ( ) protected

◆ calculateMaxCycle()

Calculate MIs execution cycle after list scheduling.

Definition at line 422 of file WindowScheduler.cpp.

References llvm::dbgs(), getEstimatedII(), getOriCycle(), getOriMI(), getOriStage(), getScheduleRange(), llvm::ScheduleDAGInstrs::getSUnit(), LLVM_DEBUG, MI, llvm::Offset, OriToCycle, Range, SchedInstrNum, Subtarget, TII, and WindowIILimit.

Referenced by analyseII().

◆ calculateStallCycle()

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

◆ 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 166 of file WindowScheduler.cpp.

References Context.

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 620 of file WindowScheduler.cpp.

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

Referenced by run().

◆ generateTripleMBB()

void WindowScheduler::generateTripleMBB ( ) protectedvirtual

Make three copies of the original MBB to generate a new TripleMBB.

Definition at line 290 of file WindowScheduler.cpp.

References assert(), getAntiRegister(), MBB, MF, MI, MRI, OriMIs, TRI, TriMIs, TriToOri, and updateLiveIntervals().

Referenced by preProcess().

◆ getAntiRegister()

◆ getEstimatedII()

◆ getIssueOrder()

Get the final issue order of all scheduled MIs including phis.

Definition at line 569 of file WindowScheduler.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), getOriCycle(), getOriMI(), getScheduleRange(), II, MBB, MI, llvm::Offset, Range, and SchedInstrNum.

Referenced by updateScheduleResult().

◆ getOriCycle()

int WindowScheduler::getOriCycle ( MachineInstr * NewMI) protected

◆ getOriMI()

◆ getOriStage()

◆ getScheduleRange()

◆ getSearchIndexes()

◆ initialize()

bool WindowScheduler::initialize ( ) protectedvirtual

Initializes the algorithm and determines if it can be executed.

Definition at line 174 of file WindowScheduler.cpp.

References BaseII, BestII, BestOffset, Context, llvm::SmallSet< T, N, C >::count(), llvm::dbgs(), I, llvm::SmallSet< T, N, C >::insert(), LLVM_DEBUG, MBB, MF, MI, OriMIs, OriToCycle, SchedInstrNum, SchedPhiNum, SchedResult, Subtarget, TII, TriMIs, and TriToOri.

Referenced by run().

◆ isScheduleValid()

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

◆ postProcess()

void WindowScheduler::postProcess ( ) protectedvirtual

◆ preProcess()

void WindowScheduler::preProcess ( ) protectedvirtual

◆ restoreMBB()

void WindowScheduler::restoreMBB ( ) protected

◆ restoreTripleMBB()

void WindowScheduler::restoreTripleMBB ( ) protectedvirtual

◆ run()

bool WindowScheduler::run ( )

Definition at line 112 of file WindowScheduler.cpp.

References analyseII(), BestII, BestOffset, createMachineScheduler(), llvm::dbgs(), expand(), getScheduleRange(), getSearchIndexes(), II, initialize(), isScheduleValid(), LLVM_DEBUG, MBB, llvm::Offset, OriToCycle, postProcess(), preProcess(), Range, restoreTripleMBB(), SchedInstrNum, SchedPhiNum, schedulePhi(), updateScheduleResult(), and WindowIILimit.

◆ schedulePhi()

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

Phis are scheduled separately after each list scheduling.

Definition at line 533 of file WindowScheduler.cpp.

References llvm::SDep::Data, llvm::dbgs(), getAntiRegister(), getOriCycle(), getOriMI(), getOriStage(), II, LLVM_DEBUG, MBB, MRI, llvm::Offset, OriToCycle, and TripleDAG.

Referenced by run().

◆ updateLiveIntervals()

void WindowScheduler::updateLiveIntervals ( ) protectedvirtual

◆ updateScheduleResult()

Update the scheduling result after each list scheduling.

Definition at line 593 of file WindowScheduler.cpp.

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

Referenced by run().

◆ BaseII

unsigned llvm::WindowScheduler::BaseII = 0 protected

◆ BestII

unsigned llvm::WindowScheduler::BestII = UINT_MAX protected

◆ BestOffset

unsigned llvm::WindowScheduler::BestOffset = 0 protected

◆ Context

◆ Loop

◆ MBB

Definition at line 65 of file WindowScheduler.h.

Referenced by backupMBB(), generateTripleMBB(), getAntiRegister(), getIssueOrder(), getScheduleRange(), initialize(), preProcess(), restoreMBB(), restoreTripleMBB(), run(), schedulePhi(), updateLiveIntervals(), and WindowScheduler().

◆ MF

◆ MRI

◆ OriMIs

◆ OriToCycle

◆ SchedInstrNum

unsigned llvm::WindowScheduler::SchedInstrNum = 0 protected

◆ SchedPhiNum

unsigned llvm::WindowScheduler::SchedPhiNum = 0 protected

◆ SchedResult

◆ Subtarget

◆ TII

◆ TRI

◆ TriMIs

◆ TripleDAG

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

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