Cut enumeration engine for combinational logic networks. More...

#include <CutRewriter.h>

Collaboration diagram for circt::synth::CutEnumerator:

[legend]

Public Member Functions
	CutEnumerator (const CutRewriterOptions &options)
	Constructor for cut enumerator.

LogicalResult	enumerateCuts (Operation *topOp, llvm::function_ref< std::optional< MatchedPattern >(const Cut &)> matchCut=[](const Cut &) { return std::nullopt;})
	Enumerate cuts for all nodes in the given module.

CutSet *	createNewCutSet (uint32_t index)
	Create a new cut set for an index.

const CutSet *	getCutSet (uint32_t index)
	Get the cut set for a specific index.

void	clear ()
	Clear all cut sets and reset the enumerator.

void	noteCutRewritten ()
	Record that one cut was successfully rewritten.

void	dump () const

const llvm::DenseMap< uint32_t, CutSet * > &	getCutSets () const
	Get cut sets (indexed by LogicNetwork index).

ArrayRef< uint32_t >	getProcessingOrder () const
	Get the processing order.

const LogicNetwork &	getLogicNetwork () const
	Get the logic network (read-only).

LogicNetwork &	getLogicNetwork ()
	Get the logic network (mutable).

const CutEnumeratorStats &	getStats () const
	Get enumeration statistics.

Private Member Functions
LogicalResult	visitLogicOp (uint32_t nodeIndex)
	Visit a combinational logic operation and generate cuts.

Private Attributes
llvm::DenseMap< uint32_t, CutSet * >	cutSets
	Maps indices to their associated cut sets.

TrackedSpecificBumpPtrAllocator< Cut >	cutAllocator
	Typed bump allocators for fast allocation with destructors.

TrackedSpecificBumpPtrAllocator< CutSet >	cutSetAllocator

llvm::SmallVector< uint32_t >	processingOrder
	Indices in processing order.

const CutRewriterOptions &	options
	Configuration options for cut enumeration.

llvm::function_ref< std::optional< MatchedPattern >(const Cut &)>	matchCut
	Function to match cuts against available patterns.

LogicNetwork	logicNetwork
	Flat logic network representation used during enumeration/rewrite.

CutEnumeratorStats	stats
	Statistics for cut enumeration (number of cuts allocated, etc.).

Detailed Description

Cut enumeration engine for combinational logic networks.

The CutEnumerator is responsible for generating cuts for each node in a combinational logic network. It uses a priority cuts algorithm to maintain a bounded set of promising cuts while avoiding exponential explosion.

The enumeration process works by:

Visiting nodes in topological order
For each node, combining cuts from its inputs
Matching generated cuts against available patterns
Maintaining only the most promising cuts per node

Definition at line 595 of file CutRewriter.h.

Constructor & Destructor Documentation

◆ CutEnumerator()

CutEnumerator::CutEnumerator ( const CutRewriterOptions & options )

explicit

Constructor for cut enumerator.

Definition at line 835 of file CutRewriter.cpp.

Member Function Documentation

◆ clear()

void CutEnumerator::clear ( )

Clear all cut sets and reset the enumerator.

Definition at line 846 of file CutRewriter.cpp.

References circt::synth::LogicNetwork::clear(), cutAllocator, cutSetAllocator, cutSets, logicNetwork, and processingOrder.

Referenced by circt::synth::CutRewriter::runBottomUpRewrite().

◆ createNewCutSet()

CutSet * CutEnumerator::createNewCutSet ( uint32_t index )

Create a new cut set for an index.

The index must not already have a cut set.

Definition at line 839 of file CutRewriter.cpp.

References assert(), cutSetAllocator, and cutSets.

Referenced by visitLogicOp().

◆ dump()

void CutEnumerator::dump ( ) const

Definition at line 1119 of file CutRewriter.cpp.

References cutSets, getTestVariableName(), circt::synth::LogicNetwork::getValue(), logicNetwork, pattern, and processingOrder.

Referenced by circt::synth::CutRewriter::run().

◆ enumerateCuts()

LogicalResult CutEnumerator::enumerateCuts	(	Operation *	topOp,
		llvm::function_ref< std::optional< MatchedPattern >(const Cut &)>	matchCut = `[](const Cut &) { return std::nullopt; }`
	)

Enumerate cuts for all nodes in the given module.

This is the main entry point that orchestrates the cut enumeration process. It visits all operations in the module and generates cuts for combinational logic operations.

Definition at line 1028 of file CutRewriter.cpp.

References circt::synth::LogicNetwork::buildFromBlock(), circt::synth::LogicNetwork::getGates(), logicNetwork, matchCut, circt::synth::topologicallySortLogicNetwork(), and visitLogicOp().

Referenced by circt::synth::CutRewriter::enumerateCuts().

◆ getCutSet()

const CutSet * CutEnumerator::getCutSet ( uint32_t index )

Get the cut set for a specific index.

If not found, it means no cuts have been generated for this value yet. In that case return a trivial cut set.

Definition at line 1059 of file CutRewriter.cpp.

References circt::synth::CutSet::addCut(), assert(), cutAllocator, cutSetAllocator, cutSets, getAsTrivialCut(), and logicNetwork.

Referenced by circt::synth::Cut::getInputArrivalTimes(), and visitLogicOp().

◆ getCutSets()

const llvm::DenseMap< uint32_t, CutSet * > & circt::synth::CutEnumerator::getCutSets ( ) const

inline

Get cut sets (indexed by LogicNetwork index).

Definition at line 628 of file CutRewriter.h.

References cutSets.

Referenced by circt::synth::CutRewriter::runBottomUpRewrite().

◆ getLogicNetwork() [1/2]

LogicNetwork & circt::synth::CutEnumerator::getLogicNetwork ( )

inline

Get the logic network (mutable).

Definition at line 670 of file CutRewriter.h.

References logicNetwork.

◆ getLogicNetwork() [2/2]

const LogicNetwork & circt::synth::CutEnumerator::getLogicNetwork ( ) const

inline

Get the logic network (read-only).

Definition at line 667 of file CutRewriter.h.

References logicNetwork.

Referenced by circt::synth::Cut::getInputArrivalTimes(), GenericLUT::match(), circt::synth::CutRewriter::patternMatchCut(), TechLibraryPattern::rewrite(), GenericLUT::rewrite(), and circt::synth::CutRewriter::runBottomUpRewrite().

◆ getProcessingOrder()

ArrayRef< uint32_t > circt::synth::CutEnumerator::getProcessingOrder ( ) const

inline

Get the processing order.

Definition at line 633 of file CutRewriter.h.

References processingOrder.

Referenced by circt::synth::CutRewriter::runBottomUpRewrite().

◆ getStats()

const CutEnumeratorStats & circt::synth::CutEnumerator::getStats ( ) const

inline

Get enumeration statistics.

Definition at line 673 of file CutRewriter.h.

References stats.

Referenced by circt::synth::CutRewriter::getStats().

◆ noteCutRewritten()

void circt::synth::CutEnumerator::noteCutRewritten ( )

inline

Record that one cut was successfully rewritten.

Definition at line 623 of file CutRewriter.h.

References circt::synth::CutEnumeratorStats::numCutsRewritten, and stats.

Referenced by circt::synth::CutRewriter::runBottomUpRewrite().

◆ visitLogicOp()

LogicalResult CutEnumerator::visitLogicOp ( uint32_t nodeIndex )

private

Visit a combinational logic operation and generate cuts.

This handles the core cut enumeration logic for operations like AND, OR, XOR, etc.

Definition at line 854 of file CutRewriter.cpp.

References assert(), createNewCutSet(), cutAllocator, getAsTrivialCut(), circt::synth::CutSet::getCuts(), getCutSet(), circt::synth::LogicNetwork::getGate(), circt::synth::LogicNetworkGate::getOperation(), circt::synth::Cut::inputs, circt::synth::LogicNetwork::kConstant0, circt::synth::LogicNetwork::kConstant1, logicNetwork, matchCut, circt::synth::CutRewriterOptions::maxCutInputSize, options, processingOrder, circt::synth::Cut::setOperandCuts(), and circt::synth::Cut::setRootIndex().

Referenced by enumerateCuts().

Member Data Documentation

◆ cutAllocator

TrackedSpecificBumpPtrAllocator<Cut> circt::synth::CutEnumerator::cutAllocator

private

Typed bump allocators for fast allocation with destructors.

Definition at line 646 of file CutRewriter.h.

Referenced by clear(), getCutSet(), and visitLogicOp().

◆ cutSetAllocator

TrackedSpecificBumpPtrAllocator<CutSet> circt::synth::CutEnumerator::cutSetAllocator

private

Definition at line 647 of file CutRewriter.h.

Referenced by clear(), createNewCutSet(), and getCutSet().

◆ cutSets

llvm::DenseMap<uint32_t, CutSet *> circt::synth::CutEnumerator::cutSets

private

Maps indices to their associated cut sets.

CutSets are allocated from the bump allocator.

Definition at line 643 of file CutRewriter.h.

Referenced by clear(), createNewCutSet(), dump(), getCutSet(), and getCutSets().

◆ logicNetwork

LogicNetwork circt::synth::CutEnumerator::logicNetwork

private

Flat logic network representation used during enumeration/rewrite.

Definition at line 660 of file CutRewriter.h.

Referenced by clear(), dump(), enumerateCuts(), getCutSet(), getLogicNetwork(), getLogicNetwork(), and visitLogicOp().

◆ matchCut

llvm::function_ref<std::optional<MatchedPattern>(const Cut &)> circt::synth::CutEnumerator::matchCut

private

Function to match cuts against available patterns.

Set during enumeration and used when finalizing cut sets.

Definition at line 657 of file CutRewriter.h.

Referenced by enumerateCuts(), and visitLogicOp().

◆ options

const CutRewriterOptions& circt::synth::CutEnumerator::options

private

Configuration options for cut enumeration.

Definition at line 653 of file CutRewriter.h.

Referenced by visitLogicOp().

◆ processingOrder

llvm::SmallVector<uint32_t> circt::synth::CutEnumerator::processingOrder

private

Indices in processing order.

Definition at line 650 of file CutRewriter.h.

Referenced by clear(), dump(), getProcessingOrder(), and visitLogicOp().

◆ stats

CutEnumeratorStats circt::synth::CutEnumerator::stats

private

Statistics for cut enumeration (number of cuts allocated, etc.).

Definition at line 663 of file CutRewriter.h.

Referenced by getStats(), and noteCutRewritten().

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

/home/runner/work/circt-www/circt-www/circt_src/include/circt/Dialect/Synth/Transforms/CutRewriter.h
/home/runner/work/circt-www/circt-www/circt_src/lib/Dialect/Synth/Transforms/CutRewriter.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ CutEnumerator()

Member Function Documentation

◆ clear()

◆ createNewCutSet()

◆ dump()

◆ enumerateCuts()

◆ getCutSet()

◆ getCutSets()

◆ getLogicNetwork() [1/2]

◆ getLogicNetwork() [2/2]

◆ getProcessingOrder()

◆ getStats()

◆ noteCutRewritten()

◆ visitLogicOp()

Member Data Documentation

◆ cutAllocator

◆ cutSetAllocator

◆ cutSets

◆ logicNetwork

◆ matchCut

◆ options

◆ processingOrder

◆ stats