LLVM 20.0.0git
|
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 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.
WindowScheduler::WindowScheduler | ( | MachineSchedContext * | C, |
MachineLoop & | ML | ||
) |
Definition at line 103 of file WindowScheduler.cpp.
References createMachineScheduler(), and TripleDAG.
|
inlinevirtual |
Definition at line 108 of file WindowScheduler.h.
|
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().
|
protected |
Back up the MIs in the original MBB and remove them from MBB.
Definition at line 268 of file WindowScheduler.cpp.
References Context, llvm::LiveIntervals::getSlotIndexes(), llvm::MachineBasicBlock::instrs(), llvm::MachineSchedContext::LIS, llvm::make_early_inc_range(), MBB, MI, OriMIs, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::MachineBasicBlock::remove(), and llvm::SlotIndexes::removeMachineInstrFromMaps().
Referenced by preProcess().
|
protectedvirtual |
Calculate MIs execution cycle after list scheduling.
Definition at line 422 of file WindowScheduler.cpp.
References llvm::dbgs(), getEstimatedII(), llvm::SUnit::getInstr(), getOriCycle(), getOriMI(), getOriStage(), getScheduleRange(), llvm::ScheduleDAGInstrs::getSUnit(), llvm::TargetInstrInfo::isZeroCost(), LLVM_DEBUG, MI, llvm::Offset, OriToCycle, Range, SchedInstrNum, Subtarget, TII, and WindowIILimit.
Referenced by analyseII().
|
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().
|
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().
|
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().
|
protectedvirtual |
Make three copies of the original MBB to generate a new TripleMBB.
Definition at line 290 of file WindowScheduler.cpp.
References assert(), llvm::SmallVectorImpl< T >::clear(), llvm::MachineFunction::CloneMachineInstr(), llvm::MachineRegisterInfo::createVirtualRegister(), getAntiRegister(), llvm::MachineRegisterInfo::getRegClass(), MBB, MF, MI, MRI, OriMIs, llvm::MachineBasicBlock::phis(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::MachineBasicBlock::push_back(), llvm::SmallVectorBase< Size_T >::size(), TRI, TriMIs, TriToOri, and updateLiveIntervals().
Referenced by preProcess().
|
protected |
Gets the register in phi which is generated from the current MBB.
Definition at line 699 of file WindowScheduler.cpp.
Referenced by generateTripleMBB(), and schedulePhi().
|
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().
|
protected |
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 >::count(), getOriCycle(), getOriMI(), getScheduleRange(), II, MBB, MI, llvm::Offset, llvm::MachineBasicBlock::phis(), Range, and SchedInstrNum.
Referenced by updateScheduleResult().
|
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().
|
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().
|
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().
|
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().
|
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().
|
protectedvirtual |
Initializes the algorithm and determines if it can be executed.
Definition at line 173 of file WindowScheduler.cpp.
References llvm::TargetInstrInfo::analyzeLoopForPipelining(), BaseII, BestII, BestOffset, llvm::SmallVectorImpl< T >::clear(), Context, llvm::SmallSet< T, N, C >::count(), llvm::dbgs(), llvm::TargetSubtargetInfo::enableWindowScheduler(), I, llvm::SmallSet< T, N, C >::insert(), llvm::TargetInstrInfo::isSchedulingBoundary(), llvm::MachineSchedContext::LIS, LLVM_DEBUG, MBB, MF, MI, OriMIs, OriToCycle, SchedInstrNum, SchedPhiNum, SchedResult, Subtarget, TII, TriMIs, and TriToOri.
Referenced by run().
|
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().
|
protectedvirtual |
Add some related processing after running window scheduling.
Definition at line 260 of file WindowScheduler.cpp.
References restoreMBB(), and TripleDAG.
Referenced by run().
|
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().
|
protected |
Erase the MIs in current MBB and restore the original MIs.
Definition at line 278 of file WindowScheduler.cpp.
References Context, llvm::LiveIntervals::getSlotIndexes(), llvm::MachineSchedContext::LIS, llvm::make_early_inc_range(), MBB, MI, OriMIs, llvm::MachineBasicBlock::push_back(), llvm::SlotIndexes::removeMachineInstrFromMaps(), and updateLiveIntervals().
Referenced by postProcess().
|
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().
bool WindowScheduler::run | ( | ) |
Definition at line 111 of file WindowScheduler.cpp.
References analyseII(), BestII, BestOffset, createMachineScheduler(), llvm::dbgs(), expand(), getScheduleRange(), getSearchIndexes(), Idx, II, initialize(), isScheduleValid(), LLVM_DEBUG, MBB, llvm::Offset, OriToCycle, postProcess(), preProcess(), Range, restoreTripleMBB(), SchedInstrNum, SchedPhiNum, schedulePhi(), updateScheduleResult(), and WindowIILimit.
|
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(), llvm::MachineRegisterInfo::getVRegDef(), II, LLVM_DEBUG, MBB, MRI, llvm::Offset, OriToCycle, llvm::MachineBasicBlock::phis(), and TripleDAG.
Referenced by run().
|
protectedvirtual |
Update the live intervals for all registers used within MBB.
Definition at line 646 of file WindowScheduler.cpp.
References llvm::MachineBasicBlock::begin(), Context, llvm::MachineBasicBlock::end(), llvm::is_contained(), llvm::MachineSchedContext::LIS, MBB, MI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::LiveIntervals::repairIntervalsInRange().
Referenced by generateTripleMBB(), and restoreMBB().
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().
|
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().
|
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().
|
protected |
Definition at line 101 of file WindowScheduler.h.
Referenced by initialize(), isScheduleValid(), run(), and updateScheduleResult().
|
protected |
Definition at line 63 of file WindowScheduler.h.
Referenced by backupMBB(), createMachineScheduler(), expand(), initialize(), preProcess(), restoreMBB(), restoreTripleMBB(), and updateLiveIntervals().
|
protected |
Definition at line 66 of file WindowScheduler.h.
|
protected |
Definition at line 65 of file WindowScheduler.h.
Referenced by backupMBB(), generateTripleMBB(), getAntiRegister(), getIssueOrder(), getScheduleRange(), initialize(), preProcess(), restoreMBB(), restoreTripleMBB(), run(), schedulePhi(), and updateLiveIntervals().
|
protected |
Definition at line 64 of file WindowScheduler.h.
Referenced by expand(), generateTripleMBB(), and initialize().
|
protected |
Definition at line 70 of file WindowScheduler.h.
Referenced by generateTripleMBB(), and schedulePhi().
|
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().
|
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().
|
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().
|
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().
|
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().
|
protected |
Definition at line 67 of file WindowScheduler.h.
Referenced by calculateMaxCycle(), and initialize().
|
protected |
Definition at line 68 of file WindowScheduler.h.
Referenced by calculateMaxCycle(), and initialize().
|
protected |
Definition at line 69 of file WindowScheduler.h.
Referenced by generateTripleMBB().
|
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().
|
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().
|
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().