#include <MachineScheduler.h>

Inheritance diagram for llvm::ScheduleDAGMI:

Collaboration diagram for llvm::ScheduleDAGMI:

Public Member Functions
	ScheduleDAGMI (MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S, bool IsPostRA)
	~ScheduleDAGMI () override
virtual bool	hasVRegLiveness () const
	Return true if this DAG supports VReg liveness and RegPressure.
void	addMutation (std::unique_ptr< ScheduleDAGMutation > Mutation)
bool	canAddEdge (SUnit SuccSU, SUnit PredSU)
	True if an edge can be added from PredSU to SuccSU without creating a cycle.
bool	addEdge (SUnit *SuccSU, const SDep &PredDep)
	Add a DAG edge to the given SU with the given predecessor dependence data.
MachineBasicBlock::iterator	top () const
MachineBasicBlock::iterator	bottom () const
void	enterRegion (MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override
void	schedule () override
void	moveInstruction (MachineInstr *MI, MachineBasicBlock::iterator InsertPos)
const SUnit *	getNextClusterPred () const
const SUnit *	getNextClusterSucc () const
void	viewGraph (const Twine &Name, const Twine &Title) override
void	viewGraph () override
	Out-of-line implementation with no arguments is handy for gdb.
Protected Member Functions
void	postprocessDAG ()
	Apply each ScheduleDAGMutation step in order.
void	initQueues (ArrayRef< SUnit * > TopRoots, ArrayRef< SUnit * > BotRoots)
	Release ExitSU predecessors and setup scheduler queues.
void	updateQueues (SUnit *SU, bool IsTopNode)
	Update scheduler DAG and queues after scheduling an instruction.
void	placeDebugValues ()
	Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
void	dumpSchedule () const
	dump the scheduled Sequence.
bool	checkSchedLimit ()
void	findRootsAndBiasEdges (SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
void	releaseSucc (SUnit SU, SDep SuccEdge)
void	releaseSuccessors (SUnit *SU)
	releaseSuccessors - Call releaseSucc on each of SU's successors.
void	releasePred (SUnit SU, SDep PredEdge)
void	releasePredecessors (SUnit *SU)
	releasePredecessors - Call releasePred on each of SU's predecessors.
Protected Attributes
AliasAnalysis *	AA
std::unique_ptr < MachineSchedStrategy >	SchedImpl
ScheduleDAGTopologicalSort	Topo
std::vector< std::unique_ptr < ScheduleDAGMutation > >	Mutations
	Ordered list of DAG postprocessing steps.
MachineBasicBlock::iterator	CurrentTop
	The top of the unscheduled zone.
MachineBasicBlock::iterator	CurrentBottom
	The bottom of the unscheduled zone.
const SUnit *	NextClusterPred
	Record the next node in a scheduled cluster.
const SUnit *	NextClusterSucc
unsigned	NumInstrsScheduled

Detailed Description

ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions according to the given MachineSchedStrategy without much extra book-keeping. This is the common functionality between PreRA and PostRA MachineScheduler.

Definition at line 223 of file MachineScheduler.h.

Constructor & Destructor Documentation

llvm::ScheduleDAGMI::ScheduleDAGMI	(	MachineSchedContext *	C,
		std::unique_ptr< MachineSchedStrategy >	S,
		bool	IsPostRA
	)		`[inline]`

Definition at line 251 of file MachineScheduler.h.

References NumInstrsScheduled.

ScheduleDAGMI::~ScheduleDAGMI ( ) [override]

Definition at line 504 of file MachineScheduler.cpp.

Member Function Documentation

bool ScheduleDAGMI::addEdge	(	SUnit *	SuccSU,
		const SDep &	PredDep
	)

Add a DAG edge to the given SU with the given predecessor dependence data.

Returns:: true if the edge may be added without creating a cycle OR if an equivalent edge already existed (false indicates failure).

Definition at line 511 of file MachineScheduler.cpp.

References llvm::SUnit::addPred(), llvm::ScheduleDAGTopologicalSort::AddPred(), llvm::ScheduleDAG::ExitSU, llvm::SDep::getSUnit(), llvm::SDep::isArtificial(), llvm::ScheduleDAGTopologicalSort::IsReachable(), and Topo.

void llvm::ScheduleDAGMI::addMutation ( std::unique_ptr< ScheduleDAGMutation > Mutation ) [inline]

Add a postprocessing step to the DAG builder. Mutations are applied in the order that they are added after normal DAG building and before MachineSchedStrategy initialization.

ScheduleDAGMI takes ownership of the Mutation object.

Definition at line 273 of file MachineScheduler.h.

References Mutations.

Referenced by createGenericSchedLive().

MachineBasicBlock::iterator llvm::ScheduleDAGMI::bottom ( ) const [inline]

Definition at line 289 of file MachineScheduler.h.

References CurrentBottom.

Referenced by llvm::ConvergingVLIWScheduler::pickNode(), llvm::GenericScheduler::pickNode(), and llvm::PostGenericScheduler::pickNode().

bool ScheduleDAGMI::canAddEdge	(	SUnit *	SuccSU,
		SUnit *	PredSU
	)

True if an edge can be added from PredSU to SuccSU without creating a cycle.

Definition at line 507 of file MachineScheduler.cpp.

References llvm::ScheduleDAG::ExitSU, llvm::ScheduleDAGTopologicalSort::IsReachable(), and Topo.

bool ScheduleDAGMI::checkSchedLimit ( ) [protected]

Definition at line 636 of file MachineScheduler.cpp.

References CurrentBottom, CurrentTop, MISchedCutoff, and NumInstrsScheduled.

Referenced by llvm::VLIWMachineScheduler::schedule(), schedule(), and llvm::ScheduleDAGMILive::schedule().

void ScheduleDAGMI::dumpSchedule ( ) const [protected]

dump the scheduled Sequence.

Definition at line 814 of file MachineScheduler.cpp.

References llvm::ScheduleDAGInstrs::begin(), llvm::dbgs(), llvm::ScheduleDAGInstrs::end(), llvm::ScheduleDAGInstrs::getSUnit(), and llvm::AArch64CC::MI.

Referenced by schedule(), and llvm::ScheduleDAGMILive::schedule().

void ScheduleDAGMI::enterRegion	(	MachineBasicBlock *	bb,
		MachineBasicBlock::iterator	begin,
		MachineBasicBlock::iterator	end,
		unsigned	regioninstrs
	)		`[override, virtual]`

Implement the ScheduleDAGInstrs interface for handling the next scheduling region. This covers all instructions in a block, while schedule() may only cover a subset.

enterRegion - Called back from MachineScheduler::runOnMachineFunction after crossing a scheduling boundary. [begin, end) includes all instructions in the region, including the boundary itself and single-instruction regions that don't get scheduled.

Reimplemented from llvm::ScheduleDAGInstrs.

Reimplemented in llvm::ScheduleDAGMILive.

Definition at line 606 of file MachineScheduler.cpp.

References SchedImpl.

void ScheduleDAGMI::findRootsAndBiasEdges	(	SmallVectorImpl< SUnit * > &	TopRoots,
		SmallVectorImpl< SUnit * > &	BotRoots
	)		`[protected]`

Definition at line 728 of file MachineScheduler.cpp.

References llvm::SUnit::biasCriticalPath(), llvm::ScheduleDAG::ExitSU, I, llvm::SUnit::isBoundaryNode(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), and llvm::ScheduleDAG::SUnits.

Referenced by llvm::VLIWMachineScheduler::schedule(), schedule(), and llvm::ScheduleDAGMILive::schedule().

const SUnit* llvm::ScheduleDAGMI::getNextClusterPred ( ) const [inline]

Definition at line 307 of file MachineScheduler.h.

References NextClusterPred.

Referenced by llvm::GenericScheduler::tryCandidate().

const SUnit* llvm::ScheduleDAGMI::getNextClusterSucc ( ) const [inline]

Definition at line 309 of file MachineScheduler.h.

References NextClusterSucc.

Referenced by llvm::GenericScheduler::tryCandidate().

virtual bool llvm::ScheduleDAGMI::hasVRegLiveness ( ) const [inline, virtual]

Return true if this DAG supports VReg liveness and RegPressure.

Reimplemented in llvm::ScheduleDAGMILive.

Definition at line 266 of file MachineScheduler.h.

Referenced by llvm::DOTGraphTraits< ScheduleDAGMI * >::getNodeAttributes(), llvm::DOTGraphTraits< ScheduleDAGMI * >::getNodeLabel(), llvm::R600SchedStrategy::initialize(), and llvm::GenericScheduler::initialize().

void ScheduleDAGMI::initQueues	(	ArrayRef< SUnit * >	TopRoots,
		ArrayRef< SUnit * >	BotRoots
	)		`[protected]`

Release ExitSU predecessors and setup scheduler queues.

Identify DAG roots and setup scheduler queues.

Definition at line 749 of file MachineScheduler.cpp.

References llvm::ArrayRef< T >::begin(), CurrentBottom, CurrentTop, llvm::ArrayRef< T >::end(), llvm::ScheduleDAG::EntrySU, llvm::ScheduleDAG::ExitSU, I, NextClusterPred, NextClusterSucc, nextIfDebug(), llvm::ArrayRef< T >::rbegin(), llvm::ScheduleDAGInstrs::RegionBegin, llvm::ScheduleDAGInstrs::RegionEnd, releasePredecessors(), releaseSuccessors(), llvm::ArrayRef< T >::rend(), and SchedImpl.

Referenced by llvm::VLIWMachineScheduler::schedule(), schedule(), and llvm::ScheduleDAGMILive::schedule().

void ScheduleDAGMI::moveInstruction	(	MachineInstr *	MI,
		MachineBasicBlock::iterator	InsertPos
	)

Change the position of an instruction within the basic block and update live ranges and region boundary iterators.

This is normally called from the main scheduler loop but may also be invoked by the scheduling strategy to perform additional code motion.

Definition at line 618 of file MachineScheduler.cpp.

References llvm::ScheduleDAGInstrs::BB, llvm::AArch64CC::MI, llvm::ScheduleDAGInstrs::RegionBegin, and llvm::MachineBasicBlock::splice().

Referenced by llvm::GenericScheduler::reschedulePhysRegCopies(), schedule(), and llvm::ScheduleDAGMILive::scheduleMI().

void ScheduleDAGMI::placeDebugValues ( ) [protected]

Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.

Reinsert any remaining debug_values, just like the PostRA scheduler.

Definition at line 791 of file MachineScheduler.cpp.

References llvm::ScheduleDAGInstrs::BB, llvm::ScheduleDAGInstrs::DbgValues, llvm::ScheduleDAGInstrs::FirstDbgValue, P, llvm::ScheduleDAGInstrs::RegionBegin, llvm::ScheduleDAGInstrs::RegionEnd, and llvm::MachineBasicBlock::splice().

Referenced by llvm::VLIWMachineScheduler::schedule(), schedule(), and llvm::ScheduleDAGMILive::schedule().

void ScheduleDAGMI::postprocessDAG ( ) [protected]

Apply each ScheduleDAGMutation step in order.

Apply each ScheduleDAGMutation step in order. This allows different instances of ScheduleDAGMI to perform custom DAG postprocessing.

Reimplemented in llvm::VLIWMachineScheduler.

Definition at line 721 of file MachineScheduler.cpp.

References Mutations.

Referenced by schedule(), and llvm::ScheduleDAGMILive::schedule().

void ScheduleDAGMI::releasePred	(	SUnit *	SU,
		SDep *	PredEdge
	)		`[protected]`

ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When NumSuccsLeft reaches zero, release the predecessor node.

FIXME: Adjust PredSU height based on MinLatency.

Definition at line 567 of file MachineScheduler.cpp.

References llvm::SUnit::BotReadyCycle, llvm::dbgs(), llvm::SUnit::dump(), llvm::ScheduleDAG::EntrySU, llvm::SDep::getLatency(), llvm::SDep::getSUnit(), llvm::SDep::isCluster(), llvm::SDep::isWeak(), llvm_unreachable, NextClusterPred, llvm::SUnit::NumSuccsLeft, SchedImpl, and llvm::SUnit::WeakSuccsLeft.

Referenced by releasePredecessors().

void ScheduleDAGMI::releasePredecessors ( SUnit * SU ) [protected]

releasePredecessors - Call releasePred on each of SU's predecessors.

Definition at line 595 of file MachineScheduler.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::end(), I, llvm::SUnit::Preds, and releasePred().

Referenced by initQueues(), and updateQueues().

void ScheduleDAGMI::releaseSucc	(	SUnit *	SU,
		SDep *	SuccEdge
	)		`[protected]`

ReleaseSucc - Decrement the NumPredsLeft count of a successor. When NumPredsLeft reaches zero, release the successor node.

FIXME: Adjust SuccSU height based on MinLatency.

Definition at line 528 of file MachineScheduler.cpp.

References llvm::dbgs(), llvm::SUnit::dump(), llvm::ScheduleDAG::ExitSU, llvm::SDep::getLatency(), llvm::SDep::getSUnit(), llvm::SDep::isCluster(), llvm::SDep::isWeak(), llvm_unreachable, NextClusterSucc, llvm::SUnit::NumPredsLeft, SchedImpl, llvm::SUnit::TopReadyCycle, and llvm::SUnit::WeakPredsLeft.

Referenced by releaseSuccessors().

void ScheduleDAGMI::releaseSuccessors ( SUnit * SU ) [protected]

releaseSuccessors - Call releaseSucc on each of SU's successors.

Definition at line 556 of file MachineScheduler.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::end(), I, releaseSucc(), and llvm::SUnit::Succs.

Referenced by initQueues(), and updateQueues().

void ScheduleDAGMI::schedule ( ) [override, virtual]

Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.

Per-region scheduling driver, called back from MachineScheduler::runOnMachineFunction. This is a simplified driver that does not consider liveness or register pressure. It is useful for PostRA scheduling and potentially other custom schedulers.

Implements llvm::ScheduleDAGInstrs.

Reimplemented in llvm::ScheduleDAGMILive, and llvm::VLIWMachineScheduler.

Definition at line 651 of file MachineScheduler.cpp.

References llvm::ScheduleDAGInstrs::begin(), llvm::ScheduleDAGInstrs::buildSchedGraph(), checkSchedLimit(), CurrentBottom, CurrentTop, llvm::dbgs(), DEBUG, dumpSchedule(), findRootsAndBiasEdges(), llvm::ScheduleDAGTopologicalSort::InitDAGTopologicalSorting(), initQueues(), llvm::AArch64CC::MI, moveInstruction(), nextIfDebug(), placeDebugValues(), postprocessDAG(), priorNonDebug(), SchedImpl, llvm::ScheduleDAG::SUnits, Topo, updateQueues(), viewGraph(), and ViewMISchedDAGs.