This class can compute a topological ordering for SUnits and provides methods for dynamically updating the ordering as new edges are added. More...

#include "llvm/CodeGen/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
LLVM_ABI	ScheduleDAGTopologicalSort (std::vector< SUnit > &SUnits, SUnit *ExitSU)
LLVM_ABI void	AddSUnitWithoutPredecessors (const SUnit *SU)
	Add a SUnit without predecessors to the end of the topological order.
LLVM_ABI void	InitDAGTopologicalSorting ()
	Creates the initial topological ordering from the DAG to be scheduled.
LLVM_ABI std::vector< int >	GetSubGraph (const SUnit &StartSU, const SUnit &TargetSU, bool &Success)
	Returns an array of SUs that are both in the successor subtree of StartSU and in the predecessor subtree of TargetSU.
LLVM_ABI bool	IsReachable (const SUnit SU, const SUnit TargetSU)
	Checks if `SU` is reachable from `TargetSU`.
LLVM_ABI bool	WillCreateCycle (SUnit TargetSU, SUnit SU)
	Returns true if addPred(TargetSU, SU) creates a cycle.
LLVM_ABI void	AddPred (SUnit Y, SUnit X)
	Updates the topological ordering to accommodate an edge to be added from SUnit `X` to SUnit `Y`.
LLVM_ABI void	AddPredQueued (SUnit Y, SUnit X)
	Queues an update to the topological ordering to accommodate an edge to be added from SUnit `X` to SUnit `Y`.
LLVM_ABI void	RemovePred (SUnit M, SUnit N)
	Updates the topological ordering to accommodate an edge to be removed from the specified node `N` from the predecessors of the current node `M`.
void	MarkDirty ()
	Mark the ordering as temporarily broken, after a new node has been added.
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

This class can compute 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 729 of file ScheduleDAG.h.

Member Typedef Documentation

◆ const_iterator

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

Definition at line 807 of file ScheduleDAG.h.

◆ const_reverse_iterator

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

Definition at line 814 of file ScheduleDAG.h.

◆ iterator

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

Definition at line 806 of file ScheduleDAG.h.

◆ reverse_iterator

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

Definition at line 813 of file ScheduleDAG.h.

Constructor & Destructor Documentation

◆ ScheduleDAGTopologicalSort()

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

Definition at line 753 of file ScheduleDAG.cpp.

Member Function Documentation

◆ AddPred()

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

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

Definition at line 553 of file ScheduleDAG.cpp.

References assert(), X, and Y.

◆ AddPredQueued()

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

Queues an update to the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y.

Definition at line 541 of file ScheduleDAG.cpp.

References X, and Y.

◆ AddSUnitWithoutPredecessors()

void ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors ( const SUnit * SU )

Add a SUnit without predecessors to the end of the topological order.

It also must be the first new node added to the DAG.

Definition at line 720 of file ScheduleDAG.cpp.

References assert(), llvm::SUnit::NodeNum, and llvm::SUnit::NumPreds.

◆ begin() [1/2]

iterator llvm::ScheduleDAGTopologicalSort::begin ( )

inline

Definition at line 808 of file ScheduleDAG.h.

◆ begin() [2/2]

const_iterator llvm::ScheduleDAGTopologicalSort::begin ( ) const

inline

Definition at line 809 of file ScheduleDAG.h.

◆ end() [1/2]

iterator llvm::ScheduleDAGTopologicalSort::end ( )

inline

Definition at line 810 of file ScheduleDAG.h.

◆ end() [2/2]

const_iterator llvm::ScheduleDAGTopologicalSort::end ( ) const

inline

Definition at line 811 of file ScheduleDAG.h.

◆ GetSubGraph()

std::vector< int > ScheduleDAGTopologicalSort::GetSubGraph	(	const SUnit &	StartSU,
		const SUnit &	TargetSU,
		bool &	Success )

Returns an array of SUs that are both in the successor subtree of StartSU and in the predecessor subtree of TargetSU.

StartSU and TargetSU are not in the array. Success is false if TargetSU is not in the successor subtree of StartSU, else it is true.

Definition at line 602 of file ScheduleDAG.cpp.

References assert(), llvm::SUnit::isBoundaryNode(), llvm::SUnit::NodeNum, llvm::SUnit::Preds, llvm::BitVector::resize(), llvm::reverse(), llvm::BitVector::set(), llvm::Success, llvm::SUnit::Succs, and llvm::BitVector::test().

◆ InitDAGTopologicalSorting()

void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting ( )

Creates the initial topological ordering from the DAG to be scheduled.

Definition at line 443 of file ScheduleDAG.cpp.

References assert(), llvm::SDep::getSUnit(), llvm::SUnit::NodeNum, and llvm::SUnit::Preds.

◆ IsReachable()

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

Checks if SU is reachable from TargetSU.

Definition at line 728 of file ScheduleDAG.cpp.

References assert(), and llvm::SUnit::NodeNum.

Referenced by WillCreateCycle().

◆ MarkDirty()

void llvm::ScheduleDAGTopologicalSort::MarkDirty ( )

inline

Mark the ordering as temporarily broken, after a new node has been added.

Definition at line 804 of file ScheduleDAG.h.

◆ rbegin() [1/2]

reverse_iterator llvm::ScheduleDAGTopologicalSort::rbegin ( )

inline

Definition at line 815 of file ScheduleDAG.h.

◆ rbegin() [2/2]

const_reverse_iterator llvm::ScheduleDAGTopologicalSort::rbegin ( ) const

inline

Definition at line 816 of file ScheduleDAG.h.

◆ RemovePred()

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

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

Definition at line 571 of file ScheduleDAG.cpp.

References N.

◆ rend() [1/2]

reverse_iterator llvm::ScheduleDAGTopologicalSort::rend ( )

inline

Definition at line 817 of file ScheduleDAG.h.

◆ rend() [2/2]

const_reverse_iterator llvm::ScheduleDAGTopologicalSort::rend ( ) const

inline

Definition at line 818 of file ScheduleDAG.h.

◆ WillCreateCycle()

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

Returns true if addPred(TargetSU, SU) creates a cycle.

Definition at line 708 of file ScheduleDAG.cpp.

References llvm::SDep::getSUnit(), llvm::SDep::isAssignedRegDep(), IsReachable(), and llvm::SUnit::Preds.

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

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

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ reverse_iterator

Constructor & Destructor Documentation

◆ ScheduleDAGTopologicalSort()

Member Function Documentation

◆ AddPred()

◆ AddPredQueued()

◆ AddSUnitWithoutPredecessors()

◆ begin() [1/2]

◆ begin() [2/2]

◆ end() [1/2]

◆ end() [2/2]

◆ GetSubGraph()

◆ InitDAGTopologicalSorting()

◆ IsReachable()

◆ MarkDirty()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ RemovePred()

◆ rend() [1/2]

◆ rend() [2/2]

◆ WillCreateCycle()