class ScheduleDAGTopologicalSort

Declaration

class ScheduleDAGTopologicalSort { /* full declaration omitted */ };

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.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:689

Method Overview

  • public void AddPred(llvm::SUnit * Y, llvm::SUnit * X)
  • public void AddPredQueued(llvm::SUnit * Y, llvm::SUnit * X)
  • public std::vector<int> GetSubGraph(const llvm::SUnit & StartSU, const llvm::SUnit & TargetSU, bool & Success)
  • public void InitDAGTopologicalSorting()
  • public bool IsReachable(const llvm::SUnit * SU, const llvm::SUnit * TargetSU)
  • public void MarkDirty()
  • public void RemovePred(llvm::SUnit * M, llvm::SUnit * N)
  • public ScheduleDAGTopologicalSort(std::vector<SUnit> & SUnits, llvm::SUnit * ExitSU)
  • public bool WillCreateCycle(llvm::SUnit * TargetSU, llvm::SUnit * SU)
  • public llvm::ScheduleDAGTopologicalSort::iterator begin()
  • public llvm::ScheduleDAGTopologicalSort::const_iterator begin() const
  • public llvm::ScheduleDAGTopologicalSort::iterator end()
  • public llvm::ScheduleDAGTopologicalSort::const_iterator end() const
  • public llvm::ScheduleDAGTopologicalSort::reverse_iterator rbegin()
  • public llvm::ScheduleDAGTopologicalSort::const_reverse_iterator rbegin() const
  • public llvm::ScheduleDAGTopologicalSort::reverse_iterator rend()
  • public llvm::ScheduleDAGTopologicalSort::const_reverse_iterator rend() const

Methods

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

Description

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

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:746

Parameters

llvm::SUnit* Y
llvm::SUnit* X

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

Description

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

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:750

Parameters

llvm::SUnit* Y
llvm::SUnit* X

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

Description

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.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:735

Parameters

const llvm::SUnit& StartSU
const llvm::SUnit& TargetSU
bool& Success

void InitDAGTopologicalSorting()

Description

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

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:728

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

Description

Checks if \p SU is reachable from \p TargetSU.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:739

Parameters

const llvm::SUnit* SU
const llvm::SUnit* TargetSU

void MarkDirty()

Description

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

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:759

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

Description

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

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:755

Parameters

llvm::SUnit* M
llvm::SUnit* N

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

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:725

Parameters

std::vector<SUnit>& SUnits
llvm::SUnit* ExitSU

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

Description

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

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:742

Parameters

llvm::SUnit* TargetSU
llvm::SUnit* SU

llvm::ScheduleDAGTopologicalSort::iterator begin()

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:763

llvm::ScheduleDAGTopologicalSort::const_iterator
begin() const

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:764

llvm::ScheduleDAGTopologicalSort::iterator end()

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:765

llvm::ScheduleDAGTopologicalSort::const_iterator
end() const

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:766

llvm::ScheduleDAGTopologicalSort::reverse_iterator
rbegin()

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:770

llvm::ScheduleDAGTopologicalSort::
    const_reverse_iterator
    rbegin() const

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:771

llvm::ScheduleDAGTopologicalSort::reverse_iterator
rend()

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:772

llvm::ScheduleDAGTopologicalSort::
    const_reverse_iterator
    rend() const

Declared at: llvm/include/llvm/CodeGen/ScheduleDAG.h:773