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	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).

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.

llvm::SpecificBumpPtrAllocator< Cut >	cutAllocator
	Typed bump allocators for fast allocation with destructors.

llvm::SpecificBumpPtrAllocator< 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.

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 570 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 845 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 838 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 1027 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 1058 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 600 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 639 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 636 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 605 of file CutRewriter.h.

References processingOrder.

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 853 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

llvm::SpecificBumpPtrAllocator<Cut> circt::synth::CutEnumerator::cutAllocator

private

Typed bump allocators for fast allocation with destructors.

Definition at line 618 of file CutRewriter.h.

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

◆ cutSetAllocator

llvm::SpecificBumpPtrAllocator<CutSet> circt::synth::CutEnumerator::cutSetAllocator

private

Definition at line 619 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 615 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 632 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 629 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 625 of file CutRewriter.h.

Referenced by visitLogicOp().

◆ processingOrder

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

private

Indices in processing order.

Definition at line 622 of file CutRewriter.h.

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

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()

◆ visitLogicOp()

Member Data Documentation

◆ cutAllocator

◆ cutSetAllocator

◆ cutSets

◆ logicNetwork

◆ matchCut

◆ options

◆ processingOrder