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

#include <CutRewriter.h>

Collaboration diagram for circt::synth::Cut:

[legend]

Public Member Functions
	Cut ()=default

	Cut (uint32_t rootIndex, ArrayRef< uint32_t > inputs, uint64_t signature, ArrayRef< const Cut * > operandCuts={}, std::optional< BinaryTruthTable > truthTable=std::nullopt)

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

uint32_t	getRootIndex () const
	Get the root index in the LogicNetwork.

void	setRootIndex (uint32_t idx)
	Set the root index of this cut.

uint64_t	getSignature () const
	Get the signature of this cut.

void	setSignature (uint64_t sig)
	Set the signature of this cut.

bool	dominates (const Cut &other) const
	Check if this cut dominates another (i.e., this cut's inputs are a subset of the other's inputs).

bool	dominates (ArrayRef< uint32_t > otherInputs, uint64_t otherSig) const
	Check if this cut dominates a set of sorted inputs with the given signature.

void	dump (llvm::raw_ostream &os, const LogicNetwork &network) const

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

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

const std::optional< BinaryTruthTable > &	getTruthTable () const
	Get the truth table for this cut.

void	computeTruthTableFromOperands (const LogicNetwork &network)
	Compute truth table using fast incremental method from operand cuts.

void	setTruthTable (BinaryTruthTable tt)
	Set the truth table directly (used for incremental computation).

void	setOperandCuts (ArrayRef< const Cut * > cuts)
	Set operand cuts for lazy truth table computation.

ArrayRef< const Cut * >	getOperandCuts () const
	Get operand cuts (for fast TT computation).

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

const NPNClass &	getNPNClass (const NPNTable *npnTable) const

void	getPermutatedInputIndices (const NPNTable *npnTable, const NPNClass &patternNPN, SmallVectorImpl< unsigned > &permutedIndices) const
	Get the permutated inputs for this cut based on the given pattern NPN.

LogicalResult	getInputArrivalTimes (CutEnumerator &enumerator, SmallVectorImpl< DelayType > &results) const
	Get arrival times for each input of this cut.

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

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

Static Public Member Functions
static Cut	getTrivialCut (uint32_t index)
	Create a trivial cut for a value.

Public Attributes
llvm::SmallVector< uint32_t, 6 >	inputs
	External inputs to this cut (cut boundary).

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

uint32_t	rootIndex = 0
	Root index in LogicNetwork (0 indicates no root for a trivial cut).

uint64_t	signature = 0
	Signature bitset for fast cut size estimation.

llvm::SmallVector< const Cut *, 3 >	operandCuts
	Operand cuts used to create this cut (for lazy TT computation).

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

Constructor & Destructor Documentation

◆ Cut() [1/2]

circt::synth::Cut::Cut ( )

default

◆ Cut() [2/2]

circt::synth::Cut::Cut	(	uint32_t	rootIndex,
		ArrayRef< uint32_t >	inputs,
		uint64_t	signature,
		ArrayRef< const Cut * >	operandCuts = `{}`,
		std::optional< BinaryTruthTable >	truthTable = `std::nullopt`
	)

inline

Definition at line 416 of file CutRewriter.h.

Member Function Documentation

◆ computeTruthTableFromOperands()

void Cut::computeTruthTableFromOperands ( const LogicNetwork & network )

Compute truth table using fast incremental method from operand cuts.

Trivial cuts are handled directly; non-trivial cuts require that operand cuts have already been set via setOperandCuts.

Definition at line 604 of file CutRewriter.cpp.

References assert(), circt::synth::LogicNetwork::getGate(), inputs, isTrivialCut(), operandCuts, rootIndex, and truthTable.

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

◆ dominates() [1/2]

bool Cut::dominates	(	ArrayRef< uint32_t >	otherInputs,
		uint64_t	otherSig
	)		const

Check if this cut dominates a set of sorted inputs with the given signature.

Definition at line 622 of file CutRewriter.cpp.

References getInputSize(), inputs, and signature.

◆ dominates() [2/2]

bool Cut::dominates ( const Cut & other ) const

Check if this cut dominates another (i.e., this cut's inputs are a subset of the other's inputs).

Uses signature pre-filtering for speed. Both cuts must have sorted inputs.

Definition at line 618 of file CutRewriter.cpp.

References dominates(), inputs, and signature.

Referenced by dominates().

◆ dump()

void Cut::dump	(	llvm::raw_ostream &	os,
		const LogicNetwork &	network
	)		const

Definition at line 413 of file CutRewriter.cpp.

References circt::synth::LogicNetwork::getGate(), getInputSize(), getNPNClass(), circt::synth::LogicNetworkGate::getOperation(), circt::synth::LogicNetwork::getValue(), inputs, isTrivialCut(), npnClass, and rootIndex.

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

◆ getInputArrivalTimes()

LogicalResult Cut::getInputArrivalTimes	(	CutEnumerator &	enumerator,
		SmallVectorImpl< DelayType > &	results
	)		const

Get arrival times for each input of this cut.

Returns failure if any input doesn't have a valid matched pattern.

Definition at line 379 of file CutRewriter.cpp.

References assert(), circt::synth::CutEnumerator::getCutSet(), getInputSize(), circt::synth::CutEnumerator::getLogicNetwork(), inputs, isAlwaysCutInput(), and matchedPattern.

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

◆ getInputSize()

unsigned Cut::getInputSize ( ) const

Get the number of inputs to this cut.

Definition at line 449 of file CutRewriter.cpp.

References inputs.

Referenced by dominates(), dump(), circt::synth::CutSet::finalize(), getInputArrivalTimes(), GenericLUT::match(), circt::synth::CutRewriter::patternMatchCut(), removeDuplicateAndNonMinimalCuts(), 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 509 of file CutRewriter.h.

References matchedPattern.

Referenced by circt::synth::CutEnumerator::dump(), and circt::synth::CutSet::finalize().

◆ getNPNClass() [1/2]

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 356 of file CutRewriter.cpp.

References getNPNClass().

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

◆ getNPNClass() [2/2]

const NPNClass & Cut::getNPNClass ( const NPNTable * npnTable ) const

Definition at line 358 of file CutRewriter.cpp.

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

◆ getOperandCuts()

ArrayRef< const Cut * > circt::synth::Cut::getOperandCuts ( ) const

inline

Get operand cuts (for fast TT computation).

Definition at line 484 of file CutRewriter.h.

References operandCuts.

◆ getOutputSize()

unsigned Cut::getOutputSize ( const LogicNetwork & network ) const

Get the number of outputs from root operation.

Definition at line 451 of file CutRewriter.cpp.

References circt::synth::LogicNetwork::getGate(), circt::synth::LogicNetworkGate::getOperation(), and rootIndex.

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

◆ getPermutatedInputIndices()

void Cut::getPermutatedInputIndices	(	const NPNTable *	npnTable,
		const NPNClass &	patternNPN,
		SmallVectorImpl< unsigned > &	permutedIndices
	)		const

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

Returns indices into the inputs vector.

Definition at line 371 of file CutRewriter.cpp.

References getNPNClass(), and npnClass.

Referenced by TechLibraryPattern::rewrite().

◆ getRootIndex()

uint32_t circt::synth::Cut::getRootIndex ( ) const

inline

Get the root index in the LogicNetwork.

Definition at line 436 of file CutRewriter.h.

References rootIndex.

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

◆ getSignature()

uint64_t circt::synth::Cut::getSignature ( ) const

inline

Get the signature of this cut.

Definition at line 442 of file CutRewriter.h.

References signature.

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

◆ getTrivialCut()

Cut Cut::getTrivialCut ( uint32_t index )

static

Create a trivial cut for a value.

Definition at line 634 of file CutRewriter.cpp.

References inputs, setSignature(), and setTruthTable().

Referenced by circt::synth::CutEnumerator::getCutSet(), and circt::synth::CutEnumerator::visitLogicOp().

◆ getTruthTable()

const std::optional< BinaryTruthTable > & circt::synth::Cut::getTruthTable ( ) const

inline

Get the truth table for this cut.

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

Definition at line 466 of file CutRewriter.h.

References truthTable.

Referenced by circt::synth::CutEnumerator::dump(), circt::synth::CutSet::finalize(), getNPNClass(), and GenericLUT::rewrite().

◆ isTrivialCut()

bool Cut::isTrivialCut ( ) const

Check if this cut represents a trivial cut.

A trivial cut has no root operation and exactly one input.

Definition at line 350 of file CutRewriter.cpp.

References inputs, and rootIndex.

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

◆ setMatchedPattern()

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

inline

Matched pattern for this cut.

Definition at line 504 of file CutRewriter.h.

References matchedPattern, and pattern.

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

◆ setOperandCuts()

void circt::synth::Cut::setOperandCuts ( ArrayRef< const Cut * > cuts )

inline

Set operand cuts for lazy truth table computation.

Definition at line 479 of file CutRewriter.h.

References operandCuts.

◆ setRootIndex()

void circt::synth::Cut::setRootIndex ( uint32_t idx )

inline

Set the root index of this cut.

Definition at line 439 of file CutRewriter.h.

References rootIndex.

◆ setSignature()

void circt::synth::Cut::setSignature ( uint64_t sig )

inline

Set the signature of this cut.

Definition at line 445 of file CutRewriter.h.

References signature.

Referenced by getTrivialCut().

◆ setTruthTable()

void circt::synth::Cut::setTruthTable ( BinaryTruthTable tt )

inline

Set the truth table directly (used for incremental computation).

Definition at line 476 of file CutRewriter.h.

References truthTable.

Referenced by getTrivialCut().

Member Data Documentation

◆ inputs

llvm::SmallVector<uint32_t, 6> circt::synth::Cut::inputs

External inputs to this cut (cut boundary).

Stored as LogicNetwork indices for efficient operations.

Definition at line 429 of file CutRewriter.h.

Referenced by computeTruthTableFromOperands(), dominates(), dominates(), circt::synth::CutEnumerator::dump(), dump(), getInputArrivalTimes(), getInputSize(), getTrivialCut(), isTrivialCut(), removeDuplicateAndNonMinimalCuts(), TechLibraryPattern::rewrite(), GenericLUT::rewrite(), and circt::synth::CutEnumerator::visitLogicOp().

◆ matchedPattern

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

private

Definition at line 397 of file CutRewriter.h.

Referenced by getInputArrivalTimes(), 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 395 of file CutRewriter.h.

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

◆ operandCuts

llvm::SmallVector<const Cut *, 3> circt::synth::Cut::operandCuts

private

Operand cuts used to create this cut (for lazy TT computation).

Stored to enable fast incremental truth table computation after duplicate removal. Using raw pointers is safe since cuts are allocated via bump allocator and live for the duration of enumeration.

Definition at line 412 of file CutRewriter.h.

Referenced by computeTruthTableFromOperands(), getOperandCuts(), and setOperandCuts().

◆ rootIndex

uint32_t circt::synth::Cut::rootIndex = 0

private

Root index in LogicNetwork (0 indicates no root for a trivial cut).

The root node produces the output of the cut.

Definition at line 401 of file CutRewriter.h.

Referenced by computeTruthTableFromOperands(), dump(), getOutputSize(), getRootIndex(), isTrivialCut(), and setRootIndex().

◆ signature

uint64_t circt::synth::Cut::signature = 0

private

Signature bitset for fast cut size estimation.

Bit i is set if value with index i is in the cut's inputs. This enables O(1) estimation of merged cut size using popcount.

Definition at line 406 of file CutRewriter.h.

Referenced by dominates(), dominates(), getSignature(), and setSignature().

◆ truthTable

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

mutableprivate

Cached truth table for this cut.

Computed lazily when first accessed to avoid unnecessary computation.

Definition at line 391 of file CutRewriter.h.

Referenced by computeTruthTableFromOperands(), getNPNClass(), getTruthTable(), and setTruthTable().

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

Static Public Member Functions

Public Attributes

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Cut() [1/2]

◆ Cut() [2/2]

Member Function Documentation

◆ computeTruthTableFromOperands()

◆ dominates() [1/2]

◆ dominates() [2/2]

◆ dump()

◆ getInputArrivalTimes()

◆ getInputSize()

◆ getMatchedPattern()

◆ getNPNClass() [1/2]

◆ getNPNClass() [2/2]

◆ getOperandCuts()

◆ getOutputSize()

◆ getPermutatedInputIndices()

◆ getRootIndex()

◆ getSignature()

◆ getTrivialCut()

◆ getTruthTable()

◆ isTrivialCut()

◆ setMatchedPattern()

◆ setOperandCuts()

◆ setRootIndex()

◆ setSignature()

◆ setTruthTable()

Member Data Documentation

◆ inputs

◆ matchedPattern

◆ npnClass

◆ operandCuts

◆ rootIndex

◆ signature

◆ truthTable