17#include "llvm/ADT/STLExtras.h"
33 const llvm::APInt &output) {
36 assert(input.getBitWidth() < 32 &&
"Input width too large");
37 unsigned offset = input.getZExtValue() *
numOutputs;
39 table.setBitVal(offset + i, output[i]);
47 for (
unsigned i = 0; i < (1u <<
numInputs); ++i) {
49 llvm::APInt permutedInput = input;
52 for (
unsigned j = 0; j <
numInputs; ++j) {
53 if (permutation[j] != j)
54 permutedInput.setBitVal(j, input[permutation[j]]);
66 for (
unsigned i = 0; i < (1u <<
numInputs); ++i) {
70 llvm::APInt negatedInput = input ^ llvm::APInt(
numInputs, mask);
82 for (
unsigned i = 0; i < (1u <<
numInputs); ++i) {
87 llvm::APInt negatedOutput = output ^ llvm::APInt(
numOutputs, negation);
109 os <<
table <<
")\n";
112 for (
unsigned i = 0; i <
numInputs; ++i) {
113 os <<
"i" << i <<
" ";
116 os <<
"o" << i <<
" ";
127 for (
unsigned i = 0; i < (1u <<
numInputs); ++i) {
129 for (
unsigned j = 0; j <
numInputs; ++j) {
130 os << ((i >> j) & 1) <<
" ";
138 os << output[j] <<
" ";
154llvm::SmallVector<unsigned> identityPermutation(
unsigned size) {
155 llvm::SmallVector<unsigned> identity(size);
156 for (
unsigned i = 0; i < size; ++i)
164unsigned permuteNegationMask(
unsigned negationMask,
165 ArrayRef<unsigned> permutation) {
167 for (
unsigned i = 0; i < permutation.size(); ++i) {
168 if (negationMask & (1u << i)) {
169 result |= (1u << permutation[i]);
177llvm::SmallVector<unsigned> invertPermutation(ArrayRef<unsigned> permutation) {
178 llvm::SmallVector<unsigned> inverse(permutation.size());
179 for (
unsigned i = 0; i < permutation.size(); ++i) {
180 inverse[permutation[i]] = i;
189 llvm::SmallVectorImpl<unsigned> &permutation)
const {
191 "NPN classes must have the same number of inputs");
193 "NPN classes must be equivalent for input mapping");
206 permutation.push_back(thisInverse[canonicalPos]);
219 for (uint32_t negMask = 0; negMask < (1u << tt.
numInputs); ++negMask) {
223 auto permutation = identityPermutation(tt.
numInputs);
229 unsigned currentNegMask = permuteNegationMask(negMask, permutation);
232 for (
unsigned outputNegMask = 0; outputNegMask < (1u << tt.
numOutputs);
239 NPNClass candidate(candidateTT, permutation, currentNegMask,
245 canonical = std::move(candidate);
247 }
while (std::next_permutation(permutation.begin(), permutation.end()));
255 os <<
" Input permutation: [";
262 os <<
" Input negation: 0b";
267 os <<
" Output negation: 0b";
272 os <<
" Canonical truth table:\n";
assert(baseType &&"element must be base type")
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Represents a boolean function as a truth table.
BinaryTruthTable applyOutputNegation(unsigned negation) const
Apply output negation to create a new truth table.
llvm::APInt table
Truth table data as a packed bit vector.
BinaryTruthTable applyInputNegation(unsigned mask) const
Apply input negation to create a new truth table.
unsigned numInputs
Number of inputs for this boolean function.
void dump(llvm::raw_ostream &os=llvm::errs()) const
Debug dump method for truth tables.
bool isLexicographicallySmaller(const BinaryTruthTable &other) const
Check if this truth table is lexicographically smaller than another.
bool operator==(const BinaryTruthTable &other) const
Equality comparison for truth tables.
llvm::APInt getOutput(const llvm::APInt &input) const
Get the output value for a given input combination.
BinaryTruthTable applyPermutation(ArrayRef< unsigned > permutation) const
Apply input permutation to create a new truth table.
void setOutput(const llvm::APInt &input, const llvm::APInt &output)
Set the output value for a given input combination.
unsigned numOutputs
Number of outputs for this boolean function.
Represents the canonical form of a boolean function under NPN equivalence.
unsigned outputNegation
Output negation mask.
static NPNClass computeNPNCanonicalForm(const BinaryTruthTable &tt)
Compute the canonical NPN form for a given truth table.
void getInputPermutation(const NPNClass &targetNPN, llvm::SmallVectorImpl< unsigned > &permutation) const
Get input permutation from this NPN class to another equivalent NPN class.
BinaryTruthTable truthTable
Canonical truth table.
void dump(llvm::raw_ostream &os=llvm::errs()) const
Debug dump method for NPN classes.
bool equivalentOtherThanPermutation(const NPNClass &other) const
Equality comparison for NPN classes.
llvm::SmallVector< unsigned > inputPermutation
Input permutation applied.
unsigned inputNegation
Input negation mask.
bool isLexicographicallySmaller(const NPNClass &other) const