LLVM: llvm::ScheduleDAGTopologicalSort Class Reference (original) (raw)

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](ScheduleDAG%5F8h%5Fsource.html)"

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

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.

◆ const_iterator

◆ const_reverse_iterator

typedef std::vector::const_reverse_iterator llvm::ScheduleDAGTopologicalSort::const_reverse_iterator

◆ iterator

typedef std::vector::iterator llvm::ScheduleDAGTopologicalSort::iterator

◆ reverse_iterator

typedef std::vector::reverse_iterator llvm::ScheduleDAGTopologicalSort::reverse_iterator

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

◆ AddPred()

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

◆ 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 )

◆ begin() [1/2]

iterator llvm::ScheduleDAGTopologicalSort::begin ( ) inline

◆ begin() [2/2]

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

◆ end() [1/2]

iterator llvm::ScheduleDAGTopologicalSort::end ( ) inline

◆ end() [2/2]

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

◆ 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 ( )

◆ IsReachable()

◆ 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

◆ rbegin() [2/2]

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

◆ 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

◆ rend() [2/2]

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

◆ WillCreateCycle()

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

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