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:693

Member Variables

private std::vector<SUnit>& SUnits

A reference to the ScheduleDAG's SUnits.

private llvm::SUnit* ExitSU

private bool Dirty = false

private SmallVector<std::pair<SUnit*, SUnit*>, 16> Updates

private std::vector<int> Index2Node

Maps topological index to the node number.

private std::vector<int> Node2Index

Maps the node number to its topological index.

private llvm::BitVector Visited

a set of nodes visited during a DFS traversal.

Method Overview

• public void AddPred(llvm::SUnit * Y, llvm::SUnit * X)
• public void AddPredQueued(llvm::SUnit * Y, llvm::SUnit * X)
• public void AddSUnitWithoutPredecessors(const llvm::SUnit * SU)
• private void Allocate(int n, int index)
• private void DFS(const llvm::SUnit * SU, int UpperBound, bool & HasLoop)
• private void FixOrder()
• 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)
• private void Shift(llvm::BitVector & Visited, int LowerBound, int UpperBound)
• 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:754

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:758

Parameters

llvm::SUnit* Y

llvm::SUnit* X

¶void AddSUnitWithoutPredecessors(
    const llvm::SUnit* SU)

Description

Add a SUnit without predecessors to the end of the topological order. It also must be the first new node added to the DAG.

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

Parameters

const llvm::SUnit* SU

¶void Allocate(int n, int index)

Description

Assigns the topological index to the node n.

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

Parameters

int n

int index

¶void DFS(const llvm::SUnit* SU,
         int UpperBound,
         bool& HasLoop)

Description

Makes a DFS traversal and mark all nodes affected by the edge insertion. These nodes will later get new topological indexes by means of the Shift method.

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

Parameters

const llvm::SUnit* SU

int UpperBound

bool& HasLoop

¶void FixOrder()

Description

Fix the ordering, by either recomputing from scratch or by applying any outstanding updates. Uses a heuristic to estimate what will be cheaper.

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

¶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:743

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:736

¶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:747

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:767

¶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:763

Parameters

llvm::SUnit* M

llvm::SUnit* N

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

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

Parameters

std::vector<SUnit>& SUnits

llvm::SUnit* ExitSU

¶void Shift(llvm::BitVector& Visited,
           int LowerBound,
           int UpperBound)

Description

Reassigns topological indexes for the nodes in the DAG to preserve the topological ordering.

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

Parameters

llvm::BitVector& Visited

int LowerBound

int UpperBound

¶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:750

Parameters

llvm::SUnit* TargetSU

llvm::SUnit* SU

¶llvm::ScheduleDAGTopologicalSort::iterator begin()

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

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

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

¶llvm::ScheduleDAGTopologicalSort::iterator end()

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

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

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

¶llvm::ScheduleDAGTopologicalSort::reverse_iterator
rbegin()

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

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

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

¶llvm::ScheduleDAGTopologicalSort::reverse_iterator
rend()

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

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

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