LLVM
15.0.0git
|
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< 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. 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 |
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.
typedef std::vector<int>::const_iterator llvm::ScheduleDAGTopologicalSort::const_iterator |
Definition at line 771 of file ScheduleDAG.h.
typedef std::vector<int>::const_reverse_iterator llvm::ScheduleDAGTopologicalSort::const_reverse_iterator |
Definition at line 778 of file ScheduleDAG.h.
typedef std::vector<int>::iterator llvm::ScheduleDAGTopologicalSort::iterator |
Definition at line 770 of file ScheduleDAG.h.
typedef std::vector<int>::reverse_iterator llvm::ScheduleDAGTopologicalSort::reverse_iterator |
Definition at line 777 of file ScheduleDAG.h.
ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort | ( | std::vector< SUnit > & | SUnits, |
SUnit * | ExitSU | ||
) |
Definition at line 747 of file ScheduleDAG.cpp.
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.
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 715 of file ScheduleDAG.cpp.
References assert(), llvm::SUnit::NodeNum, llvm::SUnit::NumPreds, and llvm::BitVector::resize().
|
inline |
Definition at line 772 of file ScheduleDAG.h.
|
inline |
Definition at line 773 of file ScheduleDAG.h.
|
inline |
Definition at line 774 of file ScheduleDAG.h.
|
inline |
Definition at line 775 of file ScheduleDAG.h.
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 597 of file ScheduleDAG.cpp.
References assert(), llvm::SUnit::isBoundaryNode(), llvm::SUnit::NodeNum, llvm::SUnit::Preds, llvm::BitVector::push_back(), llvm::BitVector::reset(), llvm::BitVector::resize(), llvm::reverse(), s, llvm::BitVector::set(), Success, llvm::SUnit::Succs, and llvm::BitVector::test().
void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting | ( | ) |
Creates the initial topological ordering from the DAG to be scheduled.
Definition at line 438 of file ScheduleDAG.cpp.
References assert(), llvm::SDep::getSUnit(), llvm::SUnit::NodeNum, llvm::X86II::PD, llvm::SUnit::Preds, llvm::SmallVectorImpl< T >::reserve(), and llvm::BitVector::resize().
Referenced by llvm::GCNIterativeScheduler::BuildDAG::BuildDAG(), llvm::VLIWMachineScheduler::schedule(), and llvm::SwingSchedulerDAG::schedule().
Checks if SU
is reachable from TargetSU
.
Definition at line 723 of file ScheduleDAG.cpp.
References llvm::SUnit::NodeNum, and llvm::BitVector::reset().
Referenced by llvm::ScheduleDAGInstrs::IsReachable(), and WillCreateCycle().
|
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().
|
inline |
Definition at line 779 of file ScheduleDAG.h.
|
inline |
Definition at line 780 of file ScheduleDAG.h.
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.
|
inline |
Definition at line 781 of file ScheduleDAG.h.
|
inline |
Definition at line 782 of file ScheduleDAG.h.
Returns true if addPred(TargetSU, SU) creates a cycle.
Definition at line 703 of file ScheduleDAG.cpp.
References llvm::SDep::getSUnit(), llvm::SDep::isAssignedRegDep(), IsReachable(), and llvm::SUnit::Preds.