Represents a cut in the combinational logic network. More...

#include <CutRewriter.h>

Collaboration diagram for circt::synth::Cut:

[legend]

Public Member Functions
bool	isTrivialCut () const
	Check if this cut represents a trivial cut.

mlir::Operation *	getRoot () const
	Get the root operation of this cut.

void	dump (llvm::raw_ostream &os) const

Cut	mergeWith (const Cut &other, Operation *root) const
	Merge this cut with another cut to form a new cut.

Cut	reRoot (Operation *root) const

unsigned	getInputSize () const
	Get the number of inputs to this cut.

unsigned	getCutSize () const
	Get the number of operations in this cut.

unsigned	getOutputSize () const
	Get the number of outputs from root operation.

const BinaryTruthTable &	getTruthTable () const
	Get the truth table for this cut.

const NPNClass &	getNPNClass () const
	Get the NPN canonical form for this cut.

void	getPermutatedInputs (const NPNClass &patternNPN, SmallVectorImpl< Value > &permutedInputs) const
	Get the permutated inputs for this cut based on the given pattern NPN.

void	setMatchedPattern (MatchedPattern pattern)
	Matched pattern for this cut.

const std::optional< MatchedPattern > &	getMatchedPattern () const
	Get the matched pattern for this cut.

Public Attributes
llvm::SmallSetVector< mlir::Value, 4 >	inputs
	External inputs to this cut (cut boundary).

llvm::SmallSetVector< mlir::Operation *, 4 >	operations
	Operations contained within this cut.

Private Attributes
std::optional< BinaryTruthTable >	truthTable
	Cached truth table for this cut.

std::optional< NPNClass >	npnClass
	Cached NPN canonical form for this cut.

std::optional< MatchedPattern >	matchedPattern

Detailed Description

Represents a cut in the combinational logic network.

A cut is a subset of nodes in the combinational logic that forms a complete subgraph with a single output. It represents a portion of the circuit that can potentially be replaced with a single library gate or pattern.

The cut contains:

Input values: The boundary between the cut and the rest of the circuit
Operations: The logic operations within the cut boundary
Root operation: The output-driving operation of the cut

Cuts are used in combinational logic optimization to identify regions that can be optimized and replaced with more efficient implementations.

Definition at line 110 of file CutRewriter.h.

Member Function Documentation

◆ dump()

void Cut::dump ( llvm::raw_ostream & os ) const

Definition at line 248 of file CutRewriter.cpp.

References getInputSize(), getNPNClass(), inputs, isTrivialCut(), npnClass, and operations.

Referenced by circt::synth::CutRewriter::patternMatchCut(), and GenericLUT::rewrite().

◆ getCutSize()

unsigned circt::synth::Cut::getCutSize ( ) const

Get the number of operations in this cut.

◆ getInputSize()

unsigned Cut::getInputSize ( ) const

Get the number of inputs to this cut.

Definition at line 272 of file CutRewriter.cpp.

References inputs.

Referenced by dump(), GenericLUT::match(), circt::synth::CutRewriter::patternMatchCut(), GenericLUT::rewrite(), and circt::synth::CutEnumerator::visitLogicOp().

◆ getMatchedPattern()

const std::optional< MatchedPattern > & circt::synth::Cut::getMatchedPattern ( ) const

inline

Get the matched pattern for this cut.

Definition at line 172 of file CutRewriter.h.

References matchedPattern.

Referenced by circt::synth::CutSet::finalize().

◆ getNPNClass()

const NPNClass & Cut::getNPNClass ( ) const

Get the NPN canonical form for this cut.

This is used for efficient pattern matching against library components.

Definition at line 222 of file CutRewriter.cpp.

References circt::NPNClass::computeNPNCanonicalForm(), getTruthTable(), npnClass, and truthTable.

Referenced by dump(), circt::synth::CutRewriter::getMatchingPatternsFromTruthTable(), getPermutatedInputs(), TechLibraryPattern::match(), and circt::synth::CutRewriter::patternMatchCut().

◆ getOutputSize()

unsigned Cut::getOutputSize ( ) const

Get the number of outputs from root operation.

Definition at line 274 of file CutRewriter.cpp.

References getRoot().

Referenced by GenericLUT::match(), and circt::synth::CutRewriter::patternMatchCut().

◆ getPermutatedInputs()

void Cut::getPermutatedInputs	(	const NPNClass &	patternNPN,
		SmallVectorImpl< Value > &	permutedInputs
	)		const

Get the permutated inputs for this cut based on the given pattern NPN.

Definition at line 236 of file CutRewriter.cpp.

References assert(), getNPNClass(), inputs, and npnClass.

Referenced by TechLibraryPattern::rewrite().

◆ getRoot()

mlir::Operation * Cut::getRoot ( ) const

Get the root operation of this cut.

The root operation produces the output of the cut.

Definition at line 216 of file CutRewriter.cpp.

References operations.

Referenced by getOutputSize(), getTruthTable(), isCutDerivedFromOperand(), TechLibraryPattern::rewrite(), and GenericLUT::rewrite().

◆ getTruthTable()

const BinaryTruthTable & Cut::getTruthTable ( ) const

Get the truth table for this cut.

The truth table represents the boolean function computed by this cut.

Definition at line 276 of file CutRewriter.cpp.

References computeTruthTable(), getRoot(), inputs, isTrivialCut(), operations, and truthTable.

Referenced by getNPNClass(), and GenericLUT::rewrite().

◆ isTrivialCut()

bool Cut::isTrivialCut ( ) const

Check if this cut represents a trivial cut.

A trivial cut has no internal operations and exactly one input.

Definition at line 211 of file CutRewriter.cpp.

References inputs, and operations.

Referenced by dump(), getTruthTable(), isCutDerivedFromOperand(), and circt::synth::CutRewriter::patternMatchCut().

◆ mergeWith()

Cut Cut::mergeWith	(	const Cut &	other,
		Operation *	root
	)		const

Merge this cut with another cut to form a new cut.

The new cut combines the operations from both cuts with the given root.

Definition at line 317 of file CutRewriter.cpp.

References assert(), inputs, isAlwaysCutInput(), isCutDerivedFromOperand(), and operations.

Referenced by circt::synth::CutEnumerator::visitLogicOp().

◆ reRoot()

Cut Cut::reRoot ( Operation * root ) const

Definition at line 393 of file CutRewriter.cpp.

References assert(), inputs, isCutDerivedFromOperand(), and operations.

Referenced by circt::synth::CutEnumerator::visitLogicOp().

◆ setMatchedPattern()

void circt::synth::Cut::setMatchedPattern ( MatchedPattern pattern )

inline

Matched pattern for this cut.

Definition at line 167 of file CutRewriter.h.

References matchedPattern, and pattern.

Member Data Documentation

◆ inputs

llvm::SmallSetVector<mlir::Value, 4> circt::synth::Cut::inputs

External inputs to this cut (cut boundary).

These are the values that flow into the cut from outside.

Definition at line 124 of file CutRewriter.h.

Referenced by dump(), getAsTrivialCut(), getInputSize(), getPermutatedInputs(), getTruthTable(), isCutDerivedFromOperand(), isTrivialCut(), mergeWith(), circt::synth::CutRewriter::patternMatchCut(), reRoot(), and GenericLUT::rewrite().

◆ matchedPattern

std::optional<MatchedPattern> circt::synth::Cut::matchedPattern

private

Definition at line 119 of file CutRewriter.h.

Referenced by getMatchedPattern(), and setMatchedPattern().

◆ npnClass

std::optional<NPNClass> circt::synth::Cut::npnClass

mutableprivate

Cached NPN canonical form for this cut.

Computed lazily from the truth table when first accessed.

Definition at line 117 of file CutRewriter.h.

Referenced by dump(), getNPNClass(), and getPermutatedInputs().

◆ operations

llvm::SmallSetVector<mlir::Operation *, 4> circt::synth::Cut::operations

Operations contained within this cut.

Stored in topological order with the root operation at the end.

Definition at line 128 of file CutRewriter.h.

Referenced by dump(), getRoot(), getTruthTable(), isTrivialCut(), mergeWith(), and reRoot().

◆ truthTable

std::optional<BinaryTruthTable> circt::synth::Cut::truthTable