Represents the canonical form of a boolean function under NPN equivalence. More...
#include <NPNClass.h>
Public Member Functions | |
| NPNClass ()=default | |
| Default constructor creates an empty NPN class. | |
| NPNClass (const BinaryTruthTable &tt) | |
| Constructor from a truth table. | |
| NPNClass (const BinaryTruthTable &tt, llvm::SmallVector< unsigned > inputPerm, unsigned inputNeg, unsigned outputNeg) | |
| void | getInputPermutation (const NPNClass &targetNPN, llvm::SmallVectorImpl< unsigned > &permutation) const |
| Get input permutation from this NPN class to another equivalent NPN class. | |
| bool | equivalentOtherThanPermutation (const NPNClass &other) const |
| Equality comparison for NPN classes. | |
| bool | isLexicographicallySmaller (const NPNClass &other) const |
| void | dump (llvm::raw_ostream &os=llvm::errs()) const |
| Debug dump method for NPN classes. | |
Static Public Member Functions | |
| static NPNClass | computeNPNCanonicalForm (const BinaryTruthTable &tt) |
| Compute the canonical NPN form for a given truth table. | |
Public Attributes | |
| BinaryTruthTable | truthTable |
| Canonical truth table. | |
| llvm::SmallVector< unsigned > | inputPermutation |
| Input permutation applied. | |
| unsigned | inputNegation = 0 |
| Input negation mask. | |
| unsigned | outputNegation = 0 |
| Output negation mask. | |
Detailed Description
Represents the canonical form of a boolean function under NPN equivalence.
NPN (Negation-Permutation-Negation) equivalence considers two boolean functions equivalent if one can be obtained from the other by:
- Negating some inputs (pre-negation)
- Permuting the inputs
- Negating some outputs (post-negation)
Example: The function ab+c is NPN equivalent to !a + b(!c) since we can transform the first function into the second by negating inputs 'a' and 'c', then reordering the inputs appropriately.
This canonical form is used to efficiently match cuts against library patterns, as functions in the same NPN class can be implemented by the same circuit with appropriate input/output inversions.
Definition at line 103 of file NPNClass.h.
Constructor & Destructor Documentation
◆ NPNClass() [1/3]
|
default |
Default constructor creates an empty NPN class.
◆ NPNClass() [2/3]
|
inline |
Constructor from a truth table.
Definition at line 113 of file NPNClass.h.
◆ NPNClass() [3/3]
|
inline |
Definition at line 115 of file NPNClass.h.
Member Function Documentation
◆ computeNPNCanonicalForm()
|
static |
Compute the canonical NPN form for a given truth table.
This method exhaustively tries all possible input permutations and negations to find the lexicographically smallest canonical form.
FIXME: Currently we are using exact canonicalization which doesn't scale well. For larger truth tables, semi-canonical forms should be used instead.
Definition at line 210 of file NPNClass.cpp.
References circt::BinaryTruthTable::applyInputNegation(), circt::BinaryTruthTable::applyOutputNegation(), circt::BinaryTruthTable::applyPermutation(), assert(), inputPermutation, isLexicographicallySmaller(), circt::BinaryTruthTable::numInputs, and circt::BinaryTruthTable::numOutputs.
Referenced by circt::synth::Cut::getNPNClass(), and getNPNClassFromModule().
◆ dump()
| void NPNClass::dump | ( | llvm::raw_ostream & | os = llvm::errs() | ) | const |
Debug dump method for NPN classes.
Definition at line 253 of file NPNClass.cpp.
References circt::BinaryTruthTable::dump(), inputNegation, inputPermutation, circt::BinaryTruthTable::numInputs, circt::BinaryTruthTable::numOutputs, outputNegation, and truthTable.
◆ equivalentOtherThanPermutation()
|
inline |
Equality comparison for NPN classes.
Definition at line 146 of file NPNClass.h.
References inputNegation, outputNegation, and truthTable.
Referenced by getInputPermutation(), and TechLibraryPattern::match().
◆ getInputPermutation()
| void NPNClass::getInputPermutation | ( | const NPNClass & | targetNPN, |
| llvm::SmallVectorImpl< unsigned > & | permutation | ||
| ) | const |
Get input permutation from this NPN class to another equivalent NPN class.
When two NPN classes are equivalent, they may have different input permutations. This function computes a permutation that allows transforming input indices from the target NPN class to input indices of this NPN class.
Returns a permutation vector where result[i] gives the input index in this NPN class that corresponds to input i in the target NPN class.
Example: If this has permutation [2,0,1] and target has [1,2,0], the mapping allows connecting target inputs to this inputs correctly.
Definition at line 187 of file NPNClass.cpp.
References assert(), equivalentOtherThanPermutation(), and inputPermutation.
Referenced by circt::synth::CutRewriter::patternMatchCut().
◆ isLexicographicallySmaller()
|
inline |
Definition at line 152 of file NPNClass.h.
References inputNegation, circt::BinaryTruthTable::isLexicographicallySmaller(), outputNegation, circt::BinaryTruthTable::table, and truthTable.
Referenced by computeNPNCanonicalForm().
Member Data Documentation
◆ inputNegation
| unsigned circt::NPNClass::inputNegation = 0 |
Input negation mask.
Definition at line 106 of file NPNClass.h.
Referenced by dump(), equivalentOtherThanPermutation(), and isLexicographicallySmaller().
◆ inputPermutation
| llvm::SmallVector<unsigned> circt::NPNClass::inputPermutation |
Input permutation applied.
Definition at line 105 of file NPNClass.h.
Referenced by computeNPNCanonicalForm(), dump(), and getInputPermutation().
◆ outputNegation
| unsigned circt::NPNClass::outputNegation = 0 |
Output negation mask.
Definition at line 107 of file NPNClass.h.
Referenced by dump(), equivalentOtherThanPermutation(), and isLexicographicallySmaller().
◆ truthTable
| BinaryTruthTable circt::NPNClass::truthTable |
Canonical truth table.
Definition at line 104 of file NPNClass.h.
Referenced by dump(), equivalentOtherThanPermutation(), and isLexicographicallySmaller().
The documentation for this struct was generated from the following files:
- /home/runner/work/circt-www/circt-www/circt_src/include/circt/Support/NPNClass.h
- /home/runner/work/circt-www/circt-www/circt_src/lib/Support/NPNClass.cpp
