llvm::ScheduleDAGTopologicalSort Class Reference

#include <ScheduleDAG.h>

Collaboration diagram for llvm::ScheduleDAGTopologicalSort:

List of all members.

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)

void InitDAGTopologicalSorting ()

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

IsReachable - Checks if SU is reachable from TargetSU.

bool WillCreateCycle (SUnit *SU, SUnit *TargetSU)

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

Member Typedef Documentation

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

Definition at line 638 of file ScheduleDAG.h.

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

Definition at line 639 of file ScheduleDAG.h.

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

Definition at line 645 of file ScheduleDAG.h.

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

Definition at line 646 of file ScheduleDAG.h.

Constructor & Destructor Documentation

ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort ( std::vector< SUnit > & SUnits ) [explicit]

Definition at line 569 of file ScheduleDAG.cpp.

Member Function Documentation

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 398 of file ScheduleDAG.cpp.

References E, llvm::SUnit::NodeNum, llvm::SUnit::Preds, llvm::SmallVectorImpl< T >::reserve(), llvm::BitVector::resize(), and llvm::SUnit::Succs.

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

IsReachable - Checks if SU is reachable from TargetSU.

Definition at line 546 of file ScheduleDAG.cpp.

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

Referenced by WillCreateCycle().

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

WillCreateCycle - Returns true if adding an edge from SU to TargetSU will create a cycle.

Definition at line 534 of file ScheduleDAG.cpp.

References E, IsReachable(), and llvm::SUnit::Preds.

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

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

Definition at line 454 of file ScheduleDAG.cpp.

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

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

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

Definition at line 473 of file ScheduleDAG.cpp.

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

Definition at line 640 of file ScheduleDAG.h.

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

Definition at line 641 of file ScheduleDAG.h.

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

Definition at line 642 of file ScheduleDAG.h.

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

Definition at line 643 of file ScheduleDAG.h.

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

Definition at line 647 of file ScheduleDAG.h.

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

Definition at line 648 of file ScheduleDAG.h.

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

Definition at line 649 of file ScheduleDAG.h.

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

Definition at line 650 of file ScheduleDAG.h.

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


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)
void	InitDAGTopologicalSorting ()
bool	IsReachable (const SUnit SU, const SUnit TargetSU)
	IsReachable - Checks if SU is reachable from TargetSU.
bool	WillCreateCycle (SUnit SU, SUnit TargetSU)
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