#include <ScheduleDAG.h>

Public Types
typedef std::vector< int > ::iterator	iterator
typedef std::vector< int > ::const_iterator	const_iterator
typedef std::vector< int > ::reverse_iterator	reverse_iterator
typedef std::vector< int > ::const_reverse_iterator	const_reverse_iterator
Public Member Functions
	ScheduleDAGTopologicalSort (std::vector< SUnit > &SUnits, SUnit *ExitSU)
void	InitDAGTopologicalSorting ()
bool	IsReachable (const SUnit SU, const SUnit TargetSU)
	IsReachable - Checks if SU is reachable from TargetSU.
bool	WillCreateCycle (SUnit TargetSU, SUnit SU)
	WillCreateCycle - Return true if addPred(TargetSU, SU) creates a cycle.
void	AddPred (SUnit Y, SUnit X)
void	RemovePred (SUnit M, SUnit N)
iterator	begin ()
const_iterator	begin () const
iterator	end ()
const_iterator	end () const
reverse_iterator	rbegin ()
const_reverse_iterator	rbegin () const
reverse_iterator	rend ()
const_reverse_iterator	rend () const

Detailed Description

ScheduleDAGTopologicalSort is a class that computes a topological ordering for SUnits and provides methods for dynamically updating the ordering as new edges are added.

This allows a very fast implementation of IsReachable, for example.

Definition at line 691 of file ScheduleDAG.h.

Member Typedef Documentation

typedef std::vector<int>::const_iterator llvm::ScheduleDAGTopologicalSort::const_iterator

Definition at line 738 of file ScheduleDAG.h.

typedef std::vector<int>::const_reverse_iterator llvm::ScheduleDAGTopologicalSort::const_reverse_iterator

Definition at line 745 of file ScheduleDAG.h.

typedef std::vector<int>::iterator llvm::ScheduleDAGTopologicalSort::iterator

Definition at line 737 of file ScheduleDAG.h.

typedef std::vector<int>::reverse_iterator llvm::ScheduleDAGTopologicalSort::reverse_iterator

Definition at line 744 of file ScheduleDAG.h.

Constructor & Destructor Documentation

ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort	(	std::vector< SUnit > &	SUnits,
		SUnit *	ExitSU
	)

Definition at line 639 of file ScheduleDAG.cpp.

Member Function Documentation

void ScheduleDAGTopologicalSort::AddPred	(	SUnit *	Y,
		SUnit *	X
	)

AddPred - Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y.

Definition at line 519 of file ScheduleDAG.cpp.

References llvm::SUnit::NodeNum, and llvm::BitVector::reset().

Referenced by llvm::ScheduleDAGMI::addEdge().

iterator llvm::ScheduleDAGTopologicalSort::begin ( ) [inline]

Definition at line 739 of file ScheduleDAG.h.

const_iterator llvm::ScheduleDAGTopologicalSort::begin ( ) const [inline]

Definition at line 740 of file ScheduleDAG.h.

iterator llvm::ScheduleDAGTopologicalSort::end ( ) [inline]

Definition at line 741 of file ScheduleDAG.h.

const_iterator llvm::ScheduleDAGTopologicalSort::end ( ) const [inline]

Definition at line 742 of file ScheduleDAG.h.

void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting ( )

InitDAGTopologicalSorting - create the initial topological ordering from the DAG to be scheduled.

The idea of the algorithm is taken from "Online algorithms for managing the topological order of a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly This is the MNR algorithm, which was first introduced by A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in "Maintaining a topological order under edge insertions".

Short description of the algorithm:

Topological ordering, ord, of a DAG maps each node to a topological index so that for all edges X->Y it is the case that ord(X) < ord(Y).

This means that if there is a path from the node X to the node Z, then ord(X) < ord(Z).

This property can be used to check for reachability of nodes: if Z is reachable from X, then an insertion of the edge Z->X would create a cycle.

The algorithm first computes a topological ordering for the DAG by initializing the Index2Node and Node2Index arrays and then tries to keep the ordering up-to-date after edge insertions by reordering the DAG.

On insertion of the edge X->Y, the algorithm first marks by calling DFS the nodes reachable from Y, and then shifts them using Shift to lie immediately after X in Index2Node.

Definition at line 460 of file ScheduleDAG.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), I, llvm::tgtok::Id, llvm::SUnit::NodeNum, llvm::SUnit::Preds, llvm::SmallVectorImpl< T >::reserve(), llvm::BitVector::resize(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and llvm::SUnit::Succs.

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

bool ScheduleDAGTopologicalSort::IsReachable	(	const SUnit *	SU,
		const SUnit *	TargetSU
	)

IsReachable - Checks if SU is reachable from TargetSU.

Definition at line 615 of file ScheduleDAG.cpp.

References llvm::SUnit::NodeNum, and llvm::BitVector::reset().

Referenced by llvm::ScheduleDAGMI::addEdge(), llvm::ScheduleDAGMI::canAddEdge(), and WillCreateCycle().

reverse_iterator llvm::ScheduleDAGTopologicalSort::rbegin ( ) [inline]

Definition at line 746 of file ScheduleDAG.h.

const_reverse_iterator llvm::ScheduleDAGTopologicalSort::rbegin ( ) const [inline]

Definition at line 747 of file ScheduleDAG.h.

void ScheduleDAGTopologicalSort::RemovePred	(	SUnit *	M,
		SUnit *	N
	)

RemovePred - Updates the topological ordering to accommodate an an edge to be removed from the specified node N from the predecessors of the current node M.

Definition at line 538 of file ScheduleDAG.cpp.

reverse_iterator llvm::ScheduleDAGTopologicalSort::rend ( ) [inline]

Definition at line 748 of file ScheduleDAG.h.

const_reverse_iterator llvm::ScheduleDAGTopologicalSort::rend ( ) const [inline]

Definition at line 749 of file ScheduleDAG.h.

bool ScheduleDAGTopologicalSort::WillCreateCycle	(	SUnit *	TargetSU,
		SUnit *	SU
	)

WillCreateCycle - Return true if addPred(TargetSU, SU) creates a cycle.

WillCreateCycle - Returns true if adding an edge to TargetSU from SU will create a cycle. If so, it is not safe to call AddPred(TargetSU, SU).

Definition at line 602 of file ScheduleDAG.cpp.

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

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

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation