Loading [MathJax]/extensions/tex2jax.js
CIRCT 22.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
NPNClass.cpp
Go to the documentation of this file.
1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements NPN (Negation-Permutation-Negation) canonical forms
10// and binary truth tables for boolean function representation and equivalence
11// checking in combinational logic optimization.
12//
13//===----------------------------------------------------------------------===//
14
16
17#include "llvm/ADT/STLExtras.h"
18#include <algorithm>
19#include <cassert>
20
21using namespace circt;
22
23//===----------------------------------------------------------------------===//
24// BinaryTruthTable
25//===----------------------------------------------------------------------===//
26
27llvm::APInt BinaryTruthTable::getOutput(const llvm::APInt &input) const {
28 assert(input.getBitWidth() == numInputs && "Input width mismatch");
29 return table.extractBits(numOutputs, input.getZExtValue() * numOutputs);
30}
31
32void BinaryTruthTable::setOutput(const llvm::APInt &input,
33 const llvm::APInt &output) {
34 assert(input.getBitWidth() == numInputs && "Input width mismatch");
35 assert(output.getBitWidth() == numOutputs && "Output width mismatch");
36 assert(input.getBitWidth() < 32 && "Input width too large");
37 unsigned offset = input.getZExtValue() * numOutputs;
38 for (unsigned i = 0; i < numOutputs; ++i)
39 table.setBitVal(offset + i, output[i]);
40}
41
43BinaryTruthTable::applyPermutation(ArrayRef<unsigned> permutation) const {
44 assert(permutation.size() == numInputs && "Permutation size mismatch");
46
47 for (unsigned i = 0; i < (1u << numInputs); ++i) {
48 llvm::APInt input(numInputs, i);
49 llvm::APInt permutedInput = input;
50
51 // Apply permutation
52 for (unsigned j = 0; j < numInputs; ++j) {
53 if (permutation[j] != j)
54 permutedInput.setBitVal(j, input[permutation[j]]);
55 }
56
57 result.setOutput(permutedInput, getOutput(input));
58 }
59
60 return result;
61}
62
65
66 for (unsigned i = 0; i < (1u << numInputs); ++i) {
67 llvm::APInt input(numInputs, i);
68
69 // Apply negation using bitwise XOR
70 llvm::APInt negatedInput = input ^ llvm::APInt(numInputs, mask);
71
72 result.setOutput(negatedInput, getOutput(input));
73 }
74
75 return result;
76}
77
79BinaryTruthTable::applyOutputNegation(unsigned negation) const {
81
82 for (unsigned i = 0; i < (1u << numInputs); ++i) {
83 llvm::APInt input(numInputs, i);
84 llvm::APInt output = getOutput(input);
85
86 // Apply negation using bitwise XOR
87 llvm::APInt negatedOutput = output ^ llvm::APInt(numOutputs, negation);
88
89 result.setOutput(input, negatedOutput);
90 }
91
92 return result;
93}
94
96 const BinaryTruthTable &other) const {
97 assert(numInputs == other.numInputs && numOutputs == other.numOutputs);
98 return table.ult(other.table);
99}
100
102 return numInputs == other.numInputs && numOutputs == other.numOutputs &&
103 table == other.table;
104}
105
106void BinaryTruthTable::dump(llvm::raw_ostream &os) const {
107 os << "TruthTable(" << numInputs << " inputs, " << numOutputs << " outputs, "
108 << "value=";
109 os << table << ")\n";
110
111 // Print header
112 for (unsigned i = 0; i < numInputs; ++i) {
113 os << "i" << i << " ";
114 }
115 for (unsigned i = 0; i < numOutputs; ++i) {
116 os << "o" << i << " ";
117 }
118 os << "\n";
119
120 // Print separator
121 for (unsigned i = 0; i < numInputs + numOutputs; ++i) {
122 os << "---";
123 }
124 os << "\n";
125
126 // Print truth table rows
127 for (unsigned i = 0; i < (1u << numInputs); ++i) {
128 // Print input values
129 for (unsigned j = 0; j < numInputs; ++j) {
130 os << ((i >> j) & 1) << " ";
131 }
132
133 // Print output values
134 llvm::APInt input(numInputs, i);
135 llvm::APInt output = getOutput(input);
136 os << "|";
137 for (unsigned j = 0; j < numOutputs; ++j) {
138 os << output[j] << " ";
139 }
140 os << "\n";
141 }
142}
143
144//===----------------------------------------------------------------------===//
145// NPNClass
146//===----------------------------------------------------------------------===//
147
148namespace {
149// Helper functions for permutation manipulation - kept as implementation
150// details
151
152/// Create an identity permutation of the given size.
153/// Result[i] = i for all i in [0, size).
154llvm::SmallVector<unsigned> identityPermutation(unsigned size) {
155 llvm::SmallVector<unsigned> identity(size);
156 for (unsigned i = 0; i < size; ++i)
157 identity[i] = i;
158 return identity;
159}
160
161/// Apply a permutation to a negation mask.
162/// Given a negation mask and a permutation, returns a new mask where
163/// the negation bits are reordered according to the permutation.
164unsigned permuteNegationMask(unsigned negationMask,
165 ArrayRef<unsigned> permutation) {
166 unsigned result = 0;
167 for (unsigned i = 0; i < permutation.size(); ++i) {
168 if (negationMask & (1u << i)) {
169 result |= (1u << permutation[i]);
170 }
171 }
172 return result;
173}
174
175/// Create the inverse of a permutation.
176/// If permutation[i] = j, then inverse[j] = 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;
181 }
182 return inverse;
183}
184
185} // anonymous namespace
186
188 const NPNClass &targetNPN,
189 llvm::SmallVectorImpl<unsigned> &permutation) const {
190 assert(inputPermutation.size() == targetNPN.inputPermutation.size() &&
191 "NPN classes must have the same number of inputs");
193 "NPN classes must be equivalent for input mapping");
194
195 // Create inverse permutation for this NPN class
196 auto thisInverse = invertPermutation(inputPermutation);
197
198 // For each input position in the target NPN class, find the corresponding
199 // input position in this NPN class
200 permutation.reserve(targetNPN.inputPermutation.size());
201 for (unsigned i = 0; i < targetNPN.inputPermutation.size(); ++i) {
202 // Target input i maps to canonical position targetNPN.inputPermutation[i]
203 // We need the input in this NPN class that maps to the same canonical
204 // position
205 unsigned canonicalPos = targetNPN.inputPermutation[i];
206 permutation.push_back(thisInverse[canonicalPos]);
207 }
208}
209
211 NPNClass canonical(tt);
212 // Initialize permutation with identity
213 canonical.inputPermutation = identityPermutation(tt.numInputs);
214 assert(tt.numInputs <= 8 && "Inputs are too large");
215 // Try all possible tables and pick the lexicographically smallest.
216 // FIXME: The time complexity is O(n! * 2^(n + m)) where n is the number
217 // of inputs and m is the number of outputs. This is not scalable so
218 // semi-canonical forms should be used instead.
219 for (uint32_t negMask = 0; negMask < (1u << tt.numInputs); ++negMask) {
220 BinaryTruthTable negatedTT = tt.applyInputNegation(negMask);
221
222 // Try all possible permutations
223 auto permutation = identityPermutation(tt.numInputs);
224
225 do {
226 BinaryTruthTable permutedTT = negatedTT.applyPermutation(permutation);
227
228 // Permute the negation mask according to the permutation
229 unsigned currentNegMask = permuteNegationMask(negMask, permutation);
230
231 // Try all negation masks for the output
232 for (unsigned outputNegMask = 0; outputNegMask < (1u << tt.numOutputs);
233 ++outputNegMask) {
234 // Apply output negation
235 BinaryTruthTable candidateTT =
236 permutedTT.applyOutputNegation(outputNegMask);
237
238 // Create a new NPN class for the candidate
239 NPNClass candidate(candidateTT, permutation, currentNegMask,
240 outputNegMask);
241
242 // Check if this candidate is lexicographically smaller than the
243 // current canonical form
244 if (candidate.isLexicographicallySmaller(canonical))
245 canonical = std::move(candidate);
246 }
247 } while (std::next_permutation(permutation.begin(), permutation.end()));
248 }
249
250 return canonical;
251}
252
253void NPNClass::dump(llvm::raw_ostream &os) const {
254 os << "NPNClass:\n";
255 os << " Input permutation: [";
256 for (unsigned i = 0; i < inputPermutation.size(); ++i) {
257 if (i > 0)
258 os << ", ";
259 os << inputPermutation[i];
260 }
261 os << "]\n";
262 os << " Input negation: 0b";
263 for (int i = truthTable.numInputs - 1; i >= 0; --i) {
264 os << ((inputNegation >> i) & 1);
265 }
266 os << "\n";
267 os << " Output negation: 0b";
268 for (int i = truthTable.numOutputs - 1; i >= 0; --i) {
269 os << ((outputNegation >> i) & 1);
270 }
271 os << "\n";
272 os << " Canonical truth table:\n";
273 truthTable.dump(os);
274}
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.
Definition NPNClass.h:38
BinaryTruthTable applyOutputNegation(unsigned negation) const
Apply output negation to create a new truth table.
Definition NPNClass.cpp:79
llvm::APInt table
Truth table data as a packed bit vector.
Definition NPNClass.h:41
BinaryTruthTable applyInputNegation(unsigned mask) const
Apply input negation to create a new truth table.
Definition NPNClass.cpp:63
unsigned numInputs
Number of inputs for this boolean function.
Definition NPNClass.h:39
void dump(llvm::raw_ostream &os=llvm::errs()) const
Debug dump method for truth tables.
Definition NPNClass.cpp:106
bool isLexicographicallySmaller(const BinaryTruthTable &other) const
Check if this truth table is lexicographically smaller than another.
Definition NPNClass.cpp:95
bool operator==(const BinaryTruthTable &other) const
Equality comparison for truth tables.
Definition NPNClass.cpp:101
llvm::APInt getOutput(const llvm::APInt &input) const
Get the output value for a given input combination.
Definition NPNClass.cpp:27
BinaryTruthTable applyPermutation(ArrayRef< unsigned > permutation) const
Apply input permutation to create a new truth table.
Definition NPNClass.cpp:43
void setOutput(const llvm::APInt &input, const llvm::APInt &output)
Set the output value for a given input combination.
Definition NPNClass.cpp:32
unsigned numOutputs
Number of outputs for this boolean function.
Definition NPNClass.h:40
Represents the canonical form of a boolean function under NPN equivalence.
Definition NPNClass.h:103
unsigned outputNegation
Output negation mask.
Definition NPNClass.h:107
static NPNClass computeNPNCanonicalForm(const BinaryTruthTable &tt)
Compute the canonical NPN form for a given truth table.
Definition NPNClass.cpp:210
void getInputPermutation(const NPNClass &targetNPN, llvm::SmallVectorImpl< unsigned > &permutation) const
Get input permutation from this NPN class to another equivalent NPN class.
Definition NPNClass.cpp:187
BinaryTruthTable truthTable
Canonical truth table.
Definition NPNClass.h:104
void dump(llvm::raw_ostream &os=llvm::errs()) const
Debug dump method for NPN classes.
Definition NPNClass.cpp:253
bool equivalentOtherThanPermutation(const NPNClass &other) const
Equality comparison for NPN classes.
Definition NPNClass.h:146
llvm::SmallVector< unsigned > inputPermutation
Input permutation applied.
Definition NPNClass.h:105
unsigned inputNegation
Input negation mask.
Definition NPNClass.h:106
bool isLexicographicallySmaller(const NPNClass &other) const
Definition NPNClass.h:152