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.

const CutRewriterOptions &	getOptions () const
	Get the cut rewriter options used for this enumeration.

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 626 of file CutRewriter.h.

Constructor & Destructor Documentation

◆ CutEnumerator()

CutEnumerator::CutEnumerator ( const CutRewriterOptions & options )

explicit

Constructor for cut enumerator.

Definition at line 871 of file CutRewriter.cpp.

Member Function Documentation

◆ clear()

void CutEnumerator::clear ( )

Clear all cut sets and reset the enumerator.

Definition at line 882 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 875 of file CutRewriter.cpp.

References assert(), cutSetAllocator, and cutSets.

Referenced by visitLogicOp().

◆ dump()

void CutEnumerator::dump ( ) const

Definition at line 1198 of file CutRewriter.cpp.

References cutSets, circt::synth::Cut::getMatchedPattern(), getTestVariableName(), circt::synth::Cut::getTruthTable(), circt::synth::LogicNetwork::getValue(), circt::synth::Cut::inputs, 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 1107 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 1138 of file CutRewriter.cpp.

References circt::synth::CutSet::addCut(), assert(), cutAllocator, cutSetAllocator, cutSets, and circt::synth::Cut::getTrivialCut().

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 662 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 704 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 701 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().

◆ getOptions()

const CutRewriterOptions & circt::synth::CutEnumerator::getOptions ( ) const

inline

Get the cut rewriter options used for this enumeration.

Definition at line 654 of file CutRewriter.h.

References options.

Referenced by TechLibraryPattern::match(), and TechLibraryPattern::rewrite().

◆ getProcessingOrder()

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

inline

Get the processing order.

Definition at line 667 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 707 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 657 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 890 of file CutRewriter.cpp.

References assert(), circt::synth::LogicNetworkGate::Choice, createNewCutSet(), cutAllocator, circt::synth::CutSet::getCuts(), getCutSet(), circt::synth::LogicNetwork::getGate(), circt::synth::LogicNetwork::getIndex(), circt::synth::Cut::getInputSize(), circt::synth::LogicNetworkGate::getOperation(), circt::synth::Cut::getSignature(), circt::synth::Cut::getTrivialCut(), circt::synth::Cut::inputs, circt::synth::LogicNetwork::kConstant0, circt::synth::LogicNetwork::kConstant1, logicNetwork, matchCut, circt::synth::CutRewriterOptions::maxCutInputSize, options, and processingOrder.

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 680 of file CutRewriter.h.

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

◆ cutSetAllocator

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

private

Definition at line 681 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 677 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 694 of file CutRewriter.h.

Referenced by clear(), dump(), enumerateCuts(), 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 691 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 687 of file CutRewriter.h.

Referenced by getOptions(), and visitLogicOp().

◆ processingOrder

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

private

Indices in processing order.

Definition at line 684 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 697 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]

◆ getOptions()

◆ getProcessingOrder()

◆ getStats()

◆ noteCutRewritten()

◆ visitLogicOp()

Member Data Documentation

◆ cutAllocator

◆ cutSetAllocator

◆ cutSets

◆ logicNetwork

◆ matchCut

◆ options

◆ processingOrder

◆ stats