10#include "mlir/IR/OperationSupport.h"
16using llvm::SmallMapVector;
29 bool needsSeparator =
false;
32 auto bit = llvm::countr_zero(rest);
33 rest &= ~(1UL << bit);
34 auto termIdx = bit >> 1;
35 auto negative = bit & 1;
44 needsSeparator =
true;
58 llvm::interleave(dnf.
orTerms, os,
" | ");
128 }
else if (other.
isTrue()) {
154 auto remainingBits =
bits;
155 while (!remainingBits.isZero()) {
159 unsigned nextIdx = remainingBits.countTrailingZeros();
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)) {
191 for (
unsigned termIdx = 0; termIdx < numTerms; ++termIdx) {
192 if (~bestKeeps & (1 << termIdx))
194 bool invert = (~nextIdx & (1 << termIdx));
202 remainingBits &= ~bestMask;
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))
247 entry.first &= condition;
259 auto seenBits = APInt::getZero(
entries[0].first.bits.getBitWidth());
261 for (
unsigned idx = 0; idx <
entries.size(); ++idx) {
263 auto &condition =
entries[idx].first;
264 if (condition.isFalse()) {
273 auto bits = condition.bits;
274 if ((seenBits & bits).isZero()) {
280 unsigned mergeIdx = 0;
281 for (; mergeIdx <
entries.size(); ++mergeIdx)
282 if (!(
entries[mergeIdx].first.bits & bits).isZero())
284 assert(mergeIdx < idx &&
"should have found an overlapping entry");
285 bits |=
entries[mergeIdx].first.bits;
288 for (
unsigned otherIdx = mergeIdx + 1; otherIdx <= idx; ++otherIdx) {
289 auto &otherBits =
entries[otherIdx].first.bits;
290 if ((otherBits & bits).isZero())
295 if (otherIdx !=
entries.size() - 1)
311 entry.
value.printAsOperand(os, mlir::OpPrintingFlags());
317 const std::pair<TruthTable, ValueEntry> &pair) {
318 return os << pair.first <<
" -> " << pair.second;
315llvm::raw_ostream & {
…}
324 llvm::interleaveComma(table.
entries, os);
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.
uint32_t andTerms
A mask with two bits for each possible term that may be present.
A boolean function expressed in canonical disjunctive normal form.
SmallVector< DNFTerm, 2 > orTerms
A boolean function expressed as a truth table.
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.
DNF canonicalize() const
Convert the truth table into its canonical disjunctive normal form.
static TruthTable getPoison()
APInt bits
The value of the boolean function for each possible combination of input term assignments.
TruthTable operator~() const
unsigned getNumTerms() const
Get the number of terms in the truth table.
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.
static ValueEntry getUnknown()
static ValueEntry getPoison()
void merge(ValueEntry other)
A table of SSA values and the conditions under which they appear.
SmallVector< std::pair< TruthTable, ValueEntry >, 1 > entries
void addCondition(TruthTable condition)
void merge(const ValueTable &other)