#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. More...

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

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 677 of file ScheduleDAG.h.

Member Typedef Documentation

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

Definition at line 724 of file ScheduleDAG.h.

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

Definition at line 731 of file ScheduleDAG.h.

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

Definition at line 723 of file ScheduleDAG.h.

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

Definition at line 730 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 725 of file ScheduleDAG.h.

const_iterator llvm::ScheduleDAGTopologicalSort::begin ( ) const

inline

Definition at line 726 of file ScheduleDAG.h.

iterator llvm::ScheduleDAGTopologicalSort::end ( )

inline

Definition at line 727 of file ScheduleDAG.h.

const_iterator llvm::ScheduleDAGTopologicalSort::end ( ) const

inline

Definition at line 728 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 I, llvm::tgtok::Id, llvm::SUnit::NodeNum, llvm::SUnit::Preds, llvm::SmallVectorImpl< T >::reserve(), llvm::BitVector::resize(), and llvm::SUnit::Succs.

Referenced by llvm::ScheduleDAGMI::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 732 of file ScheduleDAG.h.

const_reverse_iterator llvm::ScheduleDAGTopologicalSort::rbegin ( ) const

inline

Definition at line 733 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 734 of file ScheduleDAG.h.

const_reverse_iterator llvm::ScheduleDAGTopologicalSort::rend ( ) const

inline

Definition at line 735 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 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