CIRCT 24.0.0git
Loading...
Searching...
No Matches
Classes | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
circt::SparseOpSCC< Direction, NumInlineElts > Class Template Reference

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

#include <SparseOpSCC.h>

Collaboration diagram for circt::SparseOpSCC< Direction, NumInlineElts >:
Collaboration graph
[legend]

Classes

struct  ForwardFrame
struct  BackwardFrame

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

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
private
Initial value:
std::conditional_t<Direction == OpSCCDirection::Forward,
ForwardFrame, BackwardFrame>

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.

References shouldTraverseFn.

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 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 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 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 cyclicSccs, opToSccIndex, and 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 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 cyclicSccs, opToSccIndex, and 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 reverseTopological_begin(), and 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 cyclicSccs, circt::Forward, and sccs.

Referenced by 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 cyclicSccs, circt::Forward, and sccs.

Referenced by 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(), cyclicSccs, opToSccIndex, sccs, and shouldTraverseFn.

Referenced by 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 topological_begin(), and 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, cyclicSccs, and sccs.

Referenced by 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, cyclicSccs, and sccs.

Referenced by 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 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 opToSccIndex, and tarjanImpl().

Referenced by 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.

Referenced by getNumCyclicSCCs(), getSCC(), reset(), reverseTopological_begin(), reverseTopological_end(), tarjanImpl(), topological_begin(), and topological_end().

◆ 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 getNumDiscovered(), getSCC(), hasDiscovered(), reset(), tarjanImpl(), and 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.

Referenced by getNumSCCs(), getSCC(), reset(), reverseTopological_begin(), reverseTopological_end(), tarjanImpl(), topological_begin(), and topological_end().

◆ 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 >::BackwardFrame::nextChild(), circt::SparseOpSCC< Direction, NumInlineElts >::ForwardFrame::nextChild(), SparseOpSCC(), and tarjanImpl().

The documentation for this class was generated from the following file:
Generated on for CIRCT by doxygen 1.15.0