Loading [MathJax]/jax/output/HTML-CSS/config.js
CIRCT 21.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
DeseqUtils.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#include "DeseqUtils.h"
10#include "mlir/IR/OperationSupport.h"
11
12using namespace mlir;
13using namespace circt;
14using namespace llhd;
15using namespace deseq;
16using llvm::SmallMapVector;
17
18//===----------------------------------------------------------------------===//
19// Disjunctive Normal Form
20//===----------------------------------------------------------------------===//
21
22llvm::raw_ostream &deseq::operator<<(llvm::raw_ostream &os,
23 const DNFTerm &term) {
24 if (term.isTrue()) {
25 os << "(true)";
26 } else if (term.isFalse()) {
27 os << "(false)";
28 } else {
29 bool needsSeparator = false;
30 uint64_t rest = term.andTerms;
31 while (rest != 0) {
32 auto bit = llvm::countr_zero(rest);
33 rest &= ~(1UL << bit);
34 auto termIdx = bit >> 1;
35 auto negative = bit & 1;
36 if (needsSeparator)
37 os << "&";
38 if (negative)
39 os << "!";
40 if (termIdx == 0)
41 os << "x";
42 else
43 os << "a" << termIdx;
44 needsSeparator = true;
45 }
46 }
47 return os;
48}
49
50llvm::raw_ostream &deseq::operator<<(llvm::raw_ostream &os, const DNF &dnf) {
51 if (dnf.isPoison())
52 os << "poison";
53 else if (dnf.isTrue())
54 os << "true";
55 else if (dnf.isFalse())
56 os << "false";
57 else
58 llvm::interleave(dnf.orTerms, os, " | ");
59 return os;
60}
61
62//===----------------------------------------------------------------------===//
63// Truth Table
64//===----------------------------------------------------------------------===//
65
67 auto z = *this;
68 z.invert();
69 return z;
70}
71
73 auto z = *this;
74 z &= other;
75 return z;
76}
77
79 auto z = *this;
80 z |= other;
81 return z;
82}
83
85 auto z = *this;
86 z ^= other;
87 return z;
88}
89
91 if (!isPoison()) {
92 bits.flipAllBits();
94 }
95 return *this;
96}
97
99 if (!isPoison()) {
100 if (other.isPoison())
101 *this = getPoison();
102 else
103 bits &= other.bits;
104 }
105 return *this;
106}
107
109 if (!isPoison()) {
110 if (other.isPoison())
111 *this = getPoison();
112 else
113 bits |= other.bits;
114 }
115 return *this;
116}
117
119 if (isPoison()) {
120 // no-op
121 } else if (other.isPoison()) {
122 *this = getPoison();
123 } else if (isTrue()) {
124 *this = other;
125 invert();
126 } else if (isFalse()) {
127 *this = other;
128 } else if (other.isTrue()) {
129 invert();
130 } else if (other.isFalse()) {
131 // no-op
132 } else {
133 auto rhs = ~*this;
134 rhs &= other; // ~a & b
135 *this &= ~other; // a & ~b
136 *this |= rhs; // (a & ~b) | (~a & b)
137 }
138 return *this;
139}
140
142 // Handle the trivial cases.
143 if (isPoison())
144 return DNF{{DNFTerm{UINT32_MAX}}};
145 if (isTrue())
146 return DNF{{DNFTerm{0}}};
147 if (isFalse())
148 return DNF{{}};
149
150 // Otherwise add terms to the DNF iteratively until there are no more ones
151 // remaining in the truth table.
152 unsigned numTerms = getNumTerms();
153 DNF dnf;
154 auto remainingBits = bits;
155 while (!remainingBits.isZero()) {
156 // Find the index of the next 1 in the truth table. Coincidentally, the
157 // binary digits of this index correspond to the assignment of 0s and 1s
158 // to the expression terms at this row of the truth table.
159 unsigned nextIdx = remainingBits.countTrailingZeros();
160
161 // We want to generate a DNF with the fewest terms possible. To do so,
162 // iterate over all possible combinations of which expression terms to
163 // add. We do this by iterating the `keeps` variable through all possible
164 // bit combinations where each bit corresponds to an expression term being
165 // present or not. 0b0000 would not add any terms, 0b0011 would add the
166 // terms `t0&t1`, 0b1111 would add the terms `t0&t1&t2&t3`. The fewer
167 // terms we add, the more 1s in the truth table are covered. We try to
168 // find the largest number of such 1s that are a subset of our truth
169 // table, and we remember the exact combination of kept terms for it.
170 unsigned bestKeeps = -1;
171 auto bestMask = APInt::getZero(bits.getBitWidth());
172 for (unsigned keeps = 0; keeps < bits.getBitWidth(); ++keeps) {
173 auto mask = APInt::getAllOnes(bits.getBitWidth());
174 for (unsigned termIdx = 0; termIdx < numTerms; ++termIdx)
175 if (keeps & (1 << termIdx))
176 mask &= (nextIdx & (1 << termIdx)) ? getTermMask(termIdx)
177 : ~getTermMask(termIdx);
178 if ((bits & mask) == mask &&
179 llvm::popcount(keeps) < llvm::popcount(bestKeeps)) {
180 bestKeeps = keeps;
181 bestMask = mask;
182 }
183 }
184
185 // At this point, `bestKeeps` corresponds to a bit mask indicating which
186 // of the expression terms to incorporate in the AND operation we are
187 // about to add to the DNF. `bestMask` corresponds to the 1s in the truth
188 // table covered by these terms. Now populate an AND operation with these
189 // terms.
190 DNFTerm orTerm;
191 for (unsigned termIdx = 0; termIdx < numTerms; ++termIdx) {
192 if (~bestKeeps & (1 << termIdx))
193 continue;
194 bool invert = (~nextIdx & (1 << termIdx));
195 orTerm.andTerms |= (1 << (termIdx * 2 + invert));
196 }
197 dnf.orTerms.push_back(orTerm);
198
199 // Clear the bits that we have covered with this term. This causes the
200 // next iteration to work towards covering the next 1 in the truth table
201 // that has not been covered by any term thus far.
202 remainingBits &= ~bestMask;
203 }
204 return dnf;
205}
206
208 auto mask = bits ^ (bits << 1);
209 mask &= getTermMask(0);
210 bits |= mask;
211 mask.lshrInPlace(1);
212 mask.flipAllBits();
213 bits &= mask;
214}
215
216llvm::raw_ostream &deseq::operator<<(llvm::raw_ostream &os,
217 const TruthTable &table) {
218 return os << table.canonicalize();
219}
220
221//===----------------------------------------------------------------------===//
222// Value Table
223//===----------------------------------------------------------------------===//
224
226 if (isPoison() || other.isPoison()) {
227 *this = getPoison();
228 return;
229 }
230 if (value == other.value)
231 return;
232 if (!isUnknown() && !other.isUnknown()) {
233 auto result = dyn_cast<OpResult>(value);
234 auto otherResult = dyn_cast<OpResult>(other.value);
235 if (result && otherResult &&
236 result.getResultNumber() == otherResult.getResultNumber() &&
237 mlir::OperationEquivalence::isEquivalentTo(
238 result.getOwner(), otherResult.getOwner(),
239 mlir::OperationEquivalence::Flags::IgnoreLocations))
240 return;
241 }
242 *this = getUnknown();
243}
244
246 for (auto &entry : entries)
247 entry.first &= condition;
248 minimize();
249}
250
251void ValueTable::merge(const ValueTable &other) {
252 entries.append(other.entries.begin(), other.entries.end());
253 minimize();
254}
255
257 if (entries.empty())
258 return;
259 auto seenBits = APInt::getZero(entries[0].first.bits.getBitWidth());
260
261 for (unsigned idx = 0; idx < entries.size(); ++idx) {
262 // Remove entries where the condition is trivially false.
263 auto &condition = entries[idx].first;
264 if (condition.isFalse()) {
265 if (idx != entries.size() - 1)
266 std::swap(entries[idx], entries.back());
267 entries.pop_back();
268 --idx;
269 continue;
270 }
271
272 // Check if the condition of this entry overlaps with an earlier one.
273 auto bits = condition.bits;
274 if ((seenBits & bits).isZero()) {
275 seenBits |= bits;
276 continue;
277 }
278
279 // Find the earliest entry in the table that overlaps.
280 unsigned mergeIdx = 0;
281 for (; mergeIdx < entries.size(); ++mergeIdx)
282 if (!(entries[mergeIdx].first.bits & bits).isZero())
283 break;
284 assert(mergeIdx < idx && "should have found an overlapping entry");
285 bits |= entries[mergeIdx].first.bits;
286
287 // Merge all overlapping entries into this first one.
288 for (unsigned otherIdx = mergeIdx + 1; otherIdx <= idx; ++otherIdx) {
289 auto &otherBits = entries[otherIdx].first.bits;
290 if ((otherBits & bits).isZero())
291 continue;
292 bits |= otherBits;
293 entries[mergeIdx].first |= entries[otherIdx].first;
294 entries[mergeIdx].second.merge(entries[otherIdx].second);
295 if (otherIdx != entries.size() - 1)
296 std::swap(entries[otherIdx], entries.back());
297 entries.pop_back();
298 --otherIdx;
299 --idx;
300 }
301 }
302}
303
304llvm::raw_ostream &deseq::operator<<(llvm::raw_ostream &os,
305 const ValueEntry &entry) {
306 if (entry.isPoison())
307 os << "poison";
308 else if (entry.isUnknown())
309 os << "x";
310 else
311 entry.value.printAsOperand(os, mlir::OpPrintingFlags());
312 return os;
313}
314
315llvm::raw_ostream &
316deseq::operator<<(llvm::raw_ostream &os,
317 const std::pair<TruthTable, ValueEntry> &pair) {
318 return os << pair.first << " -> " << pair.second;
319}
320
321llvm::raw_ostream &deseq::operator<<(llvm::raw_ostream &os,
322 const ValueTable &table) {
323 os << "ValueTable(";
324 llvm::interleaveComma(table.entries, os);
325 os << ")";
326 return os;
327}
assert(baseType &&"element must be base type")
llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const DNFTerm &term)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
A single AND operation within a DNF.
Definition DeseqUtils.h:25
uint32_t andTerms
A mask with two bits for each possible term that may be present.
Definition DeseqUtils.h:29
A boolean function expressed in canonical disjunctive normal form.
Definition DeseqUtils.h:44
bool isPoison() const
Definition DeseqUtils.h:46
SmallVector< DNFTerm, 2 > orTerms
Definition DeseqUtils.h:45
A boolean function expressed as a truth table.
Definition DeseqUtils.h:62
static APInt getTermMask(unsigned bitWidth, unsigned term)
Return a mask that has a 1 in all truth table rows where term is 1, and a 0 otherwise.
Definition DeseqUtils.h:118
DNF canonicalize() const
Convert the truth table into its canonical disjunctive normal form.
static TruthTable getPoison()
Definition DeseqUtils.h:78
APInt bits
The value of the boolean function for each possible combination of input term assignments.
Definition DeseqUtils.h:67
TruthTable operator~() const
unsigned getNumTerms() const
Get the number of terms in the truth table.
Definition DeseqUtils.h:72
TruthTable operator&(const TruthTable &other) const
TruthTable operator^(const TruthTable &other) const
TruthTable operator|(const TruthTable &other) const
TruthTable & operator|=(const TruthTable &other)
TruthTable & operator&=(const TruthTable &other)
TruthTable & operator^=(const TruthTable &other)
A single entry in a value table.
Definition DeseqUtils.h:138
static ValueEntry getUnknown()
Definition DeseqUtils.h:149
static ValueEntry getPoison()
Definition DeseqUtils.h:146
void merge(ValueEntry other)
A table of SSA values and the conditions under which they appear.
Definition DeseqUtils.h:160
SmallVector< std::pair< TruthTable, ValueEntry >, 1 > entries
Definition DeseqUtils.h:161
void addCondition(TruthTable condition)
void merge(const ValueTable &other)