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.

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 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 ( )

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

Back up the MIs in the original MBB and remove them from MBB.

Definition at line 269 of file WindowScheduler.cpp.

References Context, llvm::make_early_inc_range(), MBB, MI, and OriMIs.

Referenced by preProcess().

◆ calculateMaxCycle()

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

protectedvirtual

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

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 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()

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 llvm::ScheduleDAG::SUnits.

Referenced by calculateMaxCycle().

◆ getIssueOrder()

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

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 >::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

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

Definition at line 669 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 676 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 681 of file WindowScheduler.cpp.

References assert(), llvm::is_contained(), 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 661 of file WindowScheduler.cpp.

References 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(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and SchedInstrNum.

Referenced by run().

◆ 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

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

References backupMBB(), Context, generateTripleMBB(), MBB, and TripleDAG.

Referenced by run().

◆ restoreMBB()

void WindowScheduler::restoreMBB ( )

protected

Erase the MIs in current MBB and restore the original MIs.

Definition at line 279 of file WindowScheduler.cpp.

References llvm::append_range(), Context, llvm::make_early_inc_range(), MBB, MI, OriMIs, and updateLiveIntervals().

Referenced by postProcess().

◆ 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 Context, I, MBB, MI, and TriMIs.

Referenced by run().

◆ 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

Update the live intervals for all registers used within MBB.

Definition at line 647 of file WindowScheduler.cpp.

References Context, llvm::is_contained(), MBB, MI, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by generateTripleMBB(), and restoreMBB().

◆ updateScheduleResult()

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

protectedvirtual

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().

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

Definition at line 63 of file WindowScheduler.h.

Referenced by backupMBB(), createMachineScheduler(), expand(), initialize(), preProcess(), restoreMBB(), restoreTripleMBB(), updateLiveIntervals(), and WindowScheduler().

◆ Loop

MachineLoop& llvm::WindowScheduler::Loop

protected

Definition at line 66 of file WindowScheduler.h.

Referenced by expand(), and WindowScheduler().

◆ MBB

MachineBasicBlock* llvm::WindowScheduler::MBB = nullptr

protected

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

MachineFunction* llvm::WindowScheduler::MF = nullptr

protected

Definition at line 64 of file WindowScheduler.h.

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

◆ MRI

MachineRegisterInfo* llvm::WindowScheduler::MRI = nullptr

protected

Definition at line 70 of file WindowScheduler.h.

Referenced by generateTripleMBB(), schedulePhi(), and WindowScheduler().

◆ 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(), initialize(), and WindowScheduler().

◆ TII

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

protected

Definition at line 68 of file WindowScheduler.h.

Referenced by calculateMaxCycle(), initialize(), and WindowScheduler().

◆ TRI

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

protected

Definition at line 69 of file WindowScheduler.h.

Referenced by generateTripleMBB(), and WindowScheduler().

◆ 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:

include/llvm/CodeGen/WindowScheduler.h
lib/CodeGen/WindowScheduler.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ WindowScheduler()

◆ ~WindowScheduler()

Member Function Documentation

◆ analyseII()

◆ backupMBB()

◆ calculateMaxCycle()

◆ calculateStallCycle()

◆ createMachineScheduler()

◆ expand()

◆ generateTripleMBB()

◆ getAntiRegister()

◆ getEstimatedII()

◆ getIssueOrder()

◆ getOriCycle()

◆ getOriMI()

◆ getOriStage()

◆ getScheduleRange()

◆ getSearchIndexes()

◆ initialize()

◆ isScheduleValid()

◆ postProcess()

◆ preProcess()

◆ restoreMBB()

◆ restoreTripleMBB()

◆ run()

◆ schedulePhi()

◆ updateLiveIntervals()

◆ updateScheduleResult()

Member Data Documentation

◆ BaseII

◆ BestII

◆ BestOffset

◆ Context

◆ Loop

◆ MBB

◆ MF

◆ MRI

◆ OriMIs

◆ OriToCycle

◆ SchedInstrNum

◆ SchedPhiNum

◆ SchedResult

◆ Subtarget

◆ TII

◆ TRI

◆ TriMIs

◆ TripleDAG

◆ TriToOri