LLVM  13.0.0git
Public Types | Public Member Functions | List of all members
llvm::ScheduleDAGTopologicalSort Class Reference

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

 ScheduleDAGTopologicalSort (std::vector< SUnit > &SUnits, SUnit *ExitSU)
 
void AddSUnitWithoutPredecessors (const SUnit *SU)
 Add a SUnit without predecessors to the end of the topological order. More...
 
void InitDAGTopologicalSorting ()
 Creates the initial topological ordering from the DAG to be scheduled. More...
 
std::vector< intGetSubGraph (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. More...
 
bool IsReachable (const SUnit *SU, const SUnit *TargetSU)
 Checks if SU is reachable from TargetSU. More...
 
bool WillCreateCycle (SUnit *TargetSU, SUnit *SU)
 Returns true if addPred(TargetSU, SU) creates a cycle. More...
 
void AddPred (SUnit *Y, SUnit *X)
 Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y. More...
 
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. More...
 
void RemovePred (SUnit *M, SUnit *N)
 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. More...
 
void MarkDirty ()
 Mark the ordering as temporarily broken, after a new node has been added. More...
 
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 694 of file ScheduleDAG.h.

Member Typedef Documentation

◆ const_iterator

Definition at line 771 of file ScheduleDAG.h.

◆ const_reverse_iterator

Definition at line 778 of file ScheduleDAG.h.

◆ iterator

Definition at line 770 of file ScheduleDAG.h.

◆ reverse_iterator

Definition at line 777 of file ScheduleDAG.h.

Constructor & Destructor Documentation

◆ ScheduleDAGTopologicalSort()

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

Definition at line 748 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 548 of file ScheduleDAG.cpp.

References assert(), llvm::BitVector::reset(), 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 536 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 716 of file ScheduleDAG.cpp.

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

◆ begin() [1/2]

iterator llvm::ScheduleDAGTopologicalSort::begin ( )
inline

Definition at line 772 of file ScheduleDAG.h.

◆ begin() [2/2]

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

Definition at line 773 of file ScheduleDAG.h.

◆ end() [1/2]

iterator llvm::ScheduleDAGTopologicalSort::end ( )
inline

Definition at line 774 of file ScheduleDAG.h.

◆ end() [2/2]

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

Definition at line 775 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 598 of file ScheduleDAG.cpp.

References assert(), I, llvm::SUnit::isBoundaryNode(), llvm::SUnit::NodeNum, llvm::SUnit::Preds, llvm::BitVector::push_back(), llvm::BitVector::reset(), llvm::BitVector::resize(), s, llvm::BitVector::set(), Success, llvm::SUnit::Succs, and llvm::BitVector::test().

◆ InitDAGTopologicalSorting()

void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting ( )

◆ IsReachable()

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

Checks if SU is reachable from TargetSU.

Definition at line 724 of file ScheduleDAG.cpp.

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

Referenced by llvm::ScheduleDAGInstrs::IsReachable(), and WillCreateCycle().

◆ MarkDirty()

void llvm::ScheduleDAGTopologicalSort::MarkDirty ( )
inline

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

Definition at line 768 of file ScheduleDAG.h.

Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph().

◆ rbegin() [1/2]

reverse_iterator llvm::ScheduleDAGTopologicalSort::rbegin ( )
inline

Definition at line 779 of file ScheduleDAG.h.

◆ rbegin() [2/2]

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

Definition at line 780 of file ScheduleDAG.h.

◆ RemovePred()

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

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

◆ rend() [1/2]

reverse_iterator llvm::ScheduleDAGTopologicalSort::rend ( )
inline

Definition at line 781 of file ScheduleDAG.h.

◆ rend() [2/2]

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

Definition at line 782 of file ScheduleDAG.h.

◆ WillCreateCycle()

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

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

Definition at line 704 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: