Iterative Tarjan SCC analysis on a sparse subgraph of MLIR operations. More...

#include <SparseOpSCC.h>

Collaboration diagram for circt::SparseOpSCC< Direction, NumInlineElts >:

[legend]

Classes
struct	BackwardFrame

struct	ForwardFrame

Public Member Functions
	SparseOpSCC (OpSCCFilter shouldTraverseFn={})

void	reset ()
	Clear all accumulated state.

void	visit (mlir::Operation *op)
	Seed `op` into the DFS if it has not already been discovered.

void	visit (llvm::ArrayRef< mlir::Operation * > ops)
	Visit each operation in `ops`, skipping already-discovered ones.

bool	hasDiscovered (mlir::Operation *op) const
	Return true if `op` was discovered (as a seed or transitively) by any previous visit() call.

OpSCC	getSCC (mlir::Operation *op) const
	Return the SCC that `op` belongs to.

unsigned	getNumDiscovered () const
	Number of operations discovered so far across all visit() calls.

unsigned	getNumSCCs () const
	Total number of SCC entries emitted (trivial ops + cyclic groups).

unsigned	getNumCyclicSCCs () const
	Number of cyclic SCC groups (excludes trivial ops).

auto	topological () const
	Iterate over SCCs in topological order (sources/seeds first, leaves last).

auto	topological_begin () const

auto	topological_end () const

auto	reverseTopological () const
	Iterate over SCCs in reverse topological order (leaves first).

auto	reverseTopological_begin () const

auto	reverseTopological_end () const

Private Types
using	FrameT = std::conditional_t< Direction==OpSCCDirection::Forward, ForwardFrame, BackwardFrame >

Private Member Functions
void	tarjanImpl (mlir::Operation *startOp)

Private Attributes
OpSCCFilter	shouldTraverseFn
	Optional edge filter supplied at construction time.

llvm::SmallDenseMap< mlir::Operation *, unsigned, NumInlineElts >	opToSccIndex
	Maps each visited op to the index of its SCC in `sccs`.

llvm::SmallVector< detail::OpOrIndex, NumInlineElts >	sccs
	Flat list of SCC entries emitted by Tarjan, in emission order.

llvm::SmallVector< detail::CyclicOpSCCStorage, 0 >	cyclicSccs
	Backing storage for cyclic SCCs; CyclicOpSCC holds a pointer into here.

Detailed Description

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>
class circt::SparseOpSCC< Direction, NumInlineElts >

Iterative Tarjan SCC analysis on a sparse subgraph of MLIR operations.

Call visit() with one or more seed operations to trigger the DFS. Results accumulate across multiple visit() calls, so the discovered subgraph can be expanded incrementally.

The optional filter passed to the constructor is applied to every discovered edge before it is traversed. An edge that fails the filter is treated as if it did not exist in the graph.

Iterators obtained from topological() and reverseTopological() hold a reference into this object and are invalidated by calling visit() or

Definition at line 270 of file SparseOpSCC.h.

Member Typedef Documentation

◆ FrameT

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

using circt::SparseOpSCC< Direction, NumInlineElts >::FrameT = std::conditional_t<Direction == OpSCCDirection::Forward, ForwardFrame, BackwardFrame>

private

Definition at line 425 of file SparseOpSCC.h.

Constructor & Destructor Documentation

◆ SparseOpSCC()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

circt::SparseOpSCC< Direction, NumInlineElts >::SparseOpSCC ( OpSCCFilter shouldTraverseFn = {} )

inlineexplicit

Definition at line 272 of file SparseOpSCC.h.

Member Function Documentation

◆ getNumCyclicSCCs()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

unsigned circt::SparseOpSCC< Direction, NumInlineElts >::getNumCyclicSCCs ( ) const

inline

Number of cyclic SCC groups (excludes trivial ops).

Definition at line 318 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::cyclicSccs.

◆ getNumDiscovered()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

unsigned circt::SparseOpSCC< Direction, NumInlineElts >::getNumDiscovered ( ) const

inline

Number of operations discovered so far across all visit() calls.

Definition at line 314 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::opToSccIndex.

◆ getNumSCCs()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

unsigned circt::SparseOpSCC< Direction, NumInlineElts >::getNumSCCs ( ) const

inline

Total number of SCC entries emitted (trivial ops + cyclic groups).

Definition at line 316 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::sccs.

◆ getSCC()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

OpSCC circt::SparseOpSCC< Direction, NumInlineElts >::getSCC ( mlir::Operation * op ) const

inline

Return the SCC that op belongs to.

If the operation has not been discovered, it returns a nullptr sentinel.

Definition at line 302 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::cyclicSccs, circt::SparseOpSCC< Direction, NumInlineElts >::opToSccIndex, and circt::SparseOpSCC< Direction, NumInlineElts >::sccs.

◆ hasDiscovered()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

bool circt::SparseOpSCC< Direction, NumInlineElts >::hasDiscovered ( mlir::Operation * op ) const

inline

Return true if op was discovered (as a seed or transitively) by any previous visit() call.

Definition at line 296 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::opToSccIndex.

◆ reset()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

void circt::SparseOpSCC< Direction, NumInlineElts >::reset ( )

inline

Clear all accumulated state.

Definition at line 276 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::cyclicSccs, circt::SparseOpSCC< Direction, NumInlineElts >::opToSccIndex, and circt::SparseOpSCC< Direction, NumInlineElts >::sccs.

◆ reverseTopological()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

auto circt::SparseOpSCC< Direction, NumInlineElts >::reverseTopological ( ) const

inline

Iterate over SCCs in reverse topological order (leaves first).

Definition at line 348 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::reverseTopological_begin(), and circt::SparseOpSCC< Direction, NumInlineElts >::reverseTopological_end().

◆ reverseTopological_begin()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

auto circt::SparseOpSCC< Direction, NumInlineElts >::reverseTopological_begin ( ) const

inline

Definition at line 354 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::cyclicSccs, circt::Forward, and circt::SparseOpSCC< Direction, NumInlineElts >::sccs.

Referenced by circt::SparseOpSCC< Direction, NumInlineElts >::reverseTopological().

◆ reverseTopological_end()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

auto circt::SparseOpSCC< Direction, NumInlineElts >::reverseTopological_end ( ) const

inline

Definition at line 365 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::cyclicSccs, circt::Forward, and circt::SparseOpSCC< Direction, NumInlineElts >::sccs.

Referenced by circt::SparseOpSCC< Direction, NumInlineElts >::reverseTopological().

◆ tarjanImpl()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

void circt::SparseOpSCC< Direction, NumInlineElts >::tarjanImpl ( mlir::Operation * startOp )

inlineprivate

Definition at line 428 of file SparseOpSCC.h.

References assert(), circt::SparseOpSCC< Direction, NumInlineElts >::cyclicSccs, circt::SparseOpSCC< Direction, NumInlineElts >::opToSccIndex, circt::SparseOpSCC< Direction, NumInlineElts >::sccs, and circt::SparseOpSCC< Direction, NumInlineElts >::shouldTraverseFn.

Referenced by circt::SparseOpSCC< Direction, NumInlineElts >::visit().

◆ topological()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

auto circt::SparseOpSCC< Direction, NumInlineElts >::topological ( ) const

inline

Iterate over SCCs in topological order (sources/seeds first, leaves last).

Definition at line 321 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::topological_begin(), and circt::SparseOpSCC< Direction, NumInlineElts >::topological_end().

◆ topological_begin()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

auto circt::SparseOpSCC< Direction, NumInlineElts >::topological_begin ( ) const

inline

Definition at line 326 of file SparseOpSCC.h.

References circt::Backward, circt::SparseOpSCC< Direction, NumInlineElts >::cyclicSccs, and circt::SparseOpSCC< Direction, NumInlineElts >::sccs.

Referenced by circt::SparseOpSCC< Direction, NumInlineElts >::topological().

◆ topological_end()

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

auto circt::SparseOpSCC< Direction, NumInlineElts >::topological_end ( ) const

inline

Definition at line 337 of file SparseOpSCC.h.

References circt::Backward, circt::SparseOpSCC< Direction, NumInlineElts >::cyclicSccs, and circt::SparseOpSCC< Direction, NumInlineElts >::sccs.

Referenced by circt::SparseOpSCC< Direction, NumInlineElts >::topological().

◆ visit() [1/2]

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

void circt::SparseOpSCC< Direction, NumInlineElts >::visit ( llvm::ArrayRef< mlir::Operation * > ops )

inline

Visit each operation in ops, skipping already-discovered ones.

Definition at line 289 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::visit().

◆ visit() [2/2]

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

void circt::SparseOpSCC< Direction, NumInlineElts >::visit ( mlir::Operation * op )

inline

Seed op into the DFS if it has not already been discovered.

Definition at line 283 of file SparseOpSCC.h.

References circt::SparseOpSCC< Direction, NumInlineElts >::opToSccIndex, and circt::SparseOpSCC< Direction, NumInlineElts >::tarjanImpl().

Referenced by circt::SparseOpSCC< Direction, NumInlineElts >::visit().

Member Data Documentation

◆ cyclicSccs

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

llvm::SmallVector<detail::CyclicOpSCCStorage, 0> circt::SparseOpSCC< Direction, NumInlineElts >::cyclicSccs

private

Backing storage for cyclic SCCs; CyclicOpSCC holds a pointer into here.

Definition at line 519 of file SparseOpSCC.h.

◆ opToSccIndex

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

llvm::SmallDenseMap<mlir::Operation *, unsigned, NumInlineElts> circt::SparseOpSCC< Direction, NumInlineElts >::opToSccIndex

private

Maps each visited op to the index of its SCC in sccs.

Persists across visit() calls and is the authoritative "already visited" guard.

Definition at line 513 of file SparseOpSCC.h.

Referenced by circt::SparseOpSCC< Direction, NumInlineElts >::getNumDiscovered(), circt::SparseOpSCC< Direction, NumInlineElts >::getSCC(), circt::SparseOpSCC< Direction, NumInlineElts >::hasDiscovered(), circt::SparseOpSCC< Direction, NumInlineElts >::reset(), circt::SparseOpSCC< Direction, NumInlineElts >::tarjanImpl(), and circt::SparseOpSCC< Direction, NumInlineElts >::visit().

◆ sccs

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

llvm::SmallVector<detail::OpOrIndex, NumInlineElts> circt::SparseOpSCC< Direction, NumInlineElts >::sccs

private

Flat list of SCC entries emitted by Tarjan, in emission order.

Trivial SCCs are stored directly. Cyclic SCCs are stored as index into the cyclicSccs vector.

Definition at line 517 of file SparseOpSCC.h.

◆ shouldTraverseFn

template<OpSCCDirection Direction, unsigned NumInlineElts = 32>

OpSCCFilter circt::SparseOpSCC< Direction, NumInlineElts >::shouldTraverseFn

private

Optional edge filter supplied at construction time.

Definition at line 509 of file SparseOpSCC.h.

Referenced by circt::SparseOpSCC< Direction, NumInlineElts >::ForwardFrame::nextChild(), circt::SparseOpSCC< Direction, NumInlineElts >::BackwardFrame::nextChild(), and circt::SparseOpSCC< Direction, NumInlineElts >::tarjanImpl().

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

/home/runner/work/circt-www/circt-www/circt_src/include/circt/Support/SparseOpSCC.h

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ FrameT

Constructor & Destructor Documentation

◆ SparseOpSCC()

Member Function Documentation

◆ getNumCyclicSCCs()

◆ getNumDiscovered()

◆ getNumSCCs()

◆ getSCC()

◆ hasDiscovered()

◆ reset()

◆ reverseTopological()

◆ reverseTopological_begin()

◆ reverseTopological_end()

◆ tarjanImpl()

◆ topological()

◆ topological_begin()

◆ topological_end()

◆ visit() [1/2]

◆ visit() [2/2]

Member Data Documentation

◆ cyclicSccs

◆ opToSccIndex

◆ sccs

◆ shouldTraverseFn