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.

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

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

bool	dominates (const Cut &other) const
	Check if this cut dominates another cut.

bool	dominates (ArrayRef< uint32_t > otherInputs) const
	Check if this cut dominates another sorted input set.

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	computeTruthTable (const LogicNetwork &network)
	Compute and cache the truth table for this cut using the LogicNetwork.

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.

void	getPermutatedInputIndices (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.

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

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

Member Function Documentation

◆ computeTruthTable()

void Cut::computeTruthTable ( const LogicNetwork & network )

Compute and cache the truth table for this cut using the LogicNetwork.

Definition at line 560 of file CutRewriter.cpp.

References circt::createVarMask(), inputs, isTrivialCut(), circt::synth::maxTruthTableInputs, rootIndex, simulateGate(), and truthTable.

Referenced by computeTruthTableFromOperands(), and getAsTrivialCut().

◆ computeTruthTableFromOperands()

void Cut::computeTruthTableFromOperands ( const LogicNetwork & network )

Compute truth table using fast incremental method from operand cuts.

This is much faster than simulation-based computation. Requires that operand cuts have already been set via setOperandCuts.

Definition at line 585 of file CutRewriter.cpp.

References computeTruthTable().

◆ dominates() [1/2]

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

Check if this cut dominates another sorted input set.

Definition at line 591 of file CutRewriter.cpp.

References getInputSize(), and inputs.

◆ dominates() [2/2]

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

Check if this cut dominates another cut.

Definition at line 589 of file CutRewriter.cpp.

References dominates(), and inputs.

Referenced by dominates().

◆ dump()

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

Definition at line 420 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 386 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 456 of file CutRewriter.cpp.

References inputs.

Referenced by dominates(), dump(), getInputArrivalTimes(), GenericLUT::match(), circt::synth::CutRewriter::patternMatchCut(), removeDuplicateAndNonMinimalCuts(), and GenericLUT::rewrite().

◆ getMatchedPattern()

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

inline

Get the matched pattern for this cut.

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

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

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

◆ getOperandCuts()

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

inline

Get operand cuts (for fast TT computation).

Definition at line 457 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 458 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 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 378 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 415 of file CutRewriter.h.

References rootIndex.

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

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

References 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 root operation and exactly one input.

Definition at line 358 of file CutRewriter.cpp.

References inputs, and rootIndex.

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

◆ setMatchedPattern()

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

inline

Matched pattern for this cut.

Definition at line 475 of file CutRewriter.h.

References matchedPattern, and pattern.

◆ setOperandCuts()

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

inline

Set operand cuts for lazy truth table computation.

Definition at line 452 of file CutRewriter.h.

References operandCuts.

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

◆ setRootIndex()

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

inline

Set the root index of this cut.

Definition at line 418 of file CutRewriter.h.

References rootIndex.

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

◆ setTruthTable()

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

inline

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

Definition at line 449 of file CutRewriter.h.

References truthTable.

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

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

◆ matchedPattern

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

private

Definition at line 393 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 391 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 403 of file CutRewriter.h.

Referenced by 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 397 of file CutRewriter.h.

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

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

Referenced by computeTruthTable(), 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

Public Attributes

Private Attributes

Detailed Description

Member Function Documentation

◆ computeTruthTable()

◆ computeTruthTableFromOperands()

◆ dominates() [1/2]

◆ dominates() [2/2]

◆ dump()

◆ getInputArrivalTimes()

◆ getInputSize()

◆ getMatchedPattern()

◆ getNPNClass()

◆ getOperandCuts()

◆ getOutputSize()

◆ getPermutatedInputIndices()

◆ getRootIndex()

◆ getTruthTable()

◆ isTrivialCut()

◆ setMatchedPattern()

◆ setOperandCuts()

◆ setRootIndex()

◆ setTruthTable()

Member Data Documentation

◆ inputs

◆ matchedPattern

◆ npnClass

◆ operandCuts

◆ rootIndex

◆ truthTable