10#include "mlir/IR/OperationSupport.h"
15using llvm::SmallMapVector;
23template <
typename Container,
typename Item>
25 auto it = llvm::lower_bound(container, item);
26 if (it != container.end() && *it == item)
28 container.insert(it, std::move(item));
33template <
typename Container>
35 if (container.size() < 2)
37 auto it = container.begin();
39 auto end = container.end();
40 for (; it != end; ++it, ++prev)
51 if (
value.getAsOpaquePointer() < other.
value.getAsOpaquePointer())
53 if (
value.getAsOpaquePointer() > other.
value.getAsOpaquePointer())
55 if (
uses.to_ulong() < other.
uses.to_ulong())
57 if (
uses.to_ulong() > other.
uses.to_ulong())
69 Use &flippedUse)
const {
76 auto otherMask = (other.
uses | (other.
uses << 2) | (other.
uses >> 2));
77 auto mask = thisMask & otherMask;
78 if (mask != otherMask)
87 auto diff = (
uses & mask) ^ (other.
uses & mask);
90 auto which = diff & (diff >> 2);
91 if (llvm::popcount(diff.to_ulong()) != 2 ||
92 llvm::popcount(which.to_ulong()) != 1)
94 flippedUse =
Use(llvm::countr_zero(which.to_ulong()));
99 llvm::function_ref<
void(Value)> printValue)
const {
101 SmallMapVector<Value, unsigned, 8> valueIds;
102 auto defaultPrintValue = [&](Value
value) {
103 os <<
"v" << valueIds.insert({
value, valueIds.size()}).first->second;
106 printValue = defaultPrintValue;
111 bool needsSeparator =
false;
116 needsSeparator =
true;
124 needsSeparator =
true;
126 for (
unsigned i = 0; i < 4; ++i) {
128 if (that.hasUse(use)) {
136 needsSeparator =
true;
146 auto it = llvm::lower_bound(
andTerms, andTerm);
147 return it !=
andTerms.end() && *it == andTerm;
153 if (a.andTerms.size() < b.andTerms.size())
155 if (a.andTerms.size() > b.andTerms.size())
157 for (
auto [aTerm, bTerm] : llvm::zip(a.andTerms, b.andTerms))
158 if (
auto order = aTerm.compare(bTerm); order != 0)
164 unsigned &flippedIdx,
176 unsigned thisIdx = 0;
177 unsigned otherIdx = 0;
178 bool flipFound =
false;
181 auto otherTerm = other.
andTerms[otherIdx];
182 unsigned flips = thisTerm.isSubsetOfModuloSingleFlip(otherTerm, flippedUse);
186 }
else if (flips == 1) {
191 flippedIdx = thisIdx;
194 }
else if (thisTerm < otherTerm) {
200 return otherIdx == other.
andTerms.size() && flipFound;
213 unsigned thisIdx = 0;
214 unsigned otherIdx = 0;
217 auto otherTerm = other.
andTerms[otherIdx];
218 if (thisTerm.isSubsetOf(otherTerm)) {
221 }
else if (thisTerm < otherTerm) {
227 return otherIdx == other.
andTerms.size();
236 return llvm::hash_combine(andTerm.
value, andTerm.
uses.to_ulong());
238 return llvm::hash_combine_range(range.begin(), range.end());
242 return a.
value.getAsOpaquePointer() < b.
value.getAsOpaquePointer();
249 it->addUses(term.
uses);
250 return !it->isFalse();
254 andTerms.insert(it, std::move(term));
259 for (
auto term : terms)
266 for (
unsigned idx = 0; idx + 1 <
andTerms.size(); ++idx)
270 if (andTerm.isFalse() || andTerm.isTrue())
276 llvm::function_ref<std::optional<bool>(Value,
bool)> evaluateTerm) {
279 for (
unsigned use = 0; use < 4; ++use) {
300 llvm::function_ref<
void(Value)> printValue)
const {
308 SmallMapVector<Value, unsigned, 8> valueIds;
309 auto defaultPrintValue = [&](Value value) {
310 os <<
"v" << valueIds.insert({value, valueIds.size()}).first->second;
313 printValue = defaultPrintValue;
317 andTerms, os, [&](
auto andTerm) { andTerm.print(os, printValue); },
"&");
325 auto it = llvm::lower_bound(
orTerms, orTerm);
326 return it !=
orTerms.end() && *it == orTerm;
331 if (orTerm.contains(andTerm))
339 if (a.orTerms.size() < b.orTerms.size())
341 if (a.orTerms.size() > b.orTerms.size())
343 for (
auto [aTerm, bTerm] : llvm::zip(a.orTerms, b.orTerms))
344 if (
auto order = aTerm.compare(bTerm); order != 0)
351 if (!orTerm.isSortedAndUnique())
353 for (
unsigned idx = 0; idx + 1 <
orTerms.size(); ++idx)
361 SmallMapVector<std::pair<Value, AndTerm::Use>, uint8_t, 8> terms;
363 for (
auto &andTerm : orTerm.andTerms) {
365 terms.insert({{andTerm.value,
AndTerm::Id}, uint8_t(terms.size())});
367 terms.insert({{andTerm.value,
AndTerm::Past}, uint8_t(terms.size())});
368 if (terms.size() > 16)
372 unsigned tableSize = 1 << terms.size();
375 auto table = APInt::getZero(tableSize);
376 auto getCheckerMask = [&](
unsigned idx) {
377 return APInt::getSplat(tableSize,
378 APInt::getHighBitsSet(2 << idx, 1 << idx));
381 return getCheckerMask(terms.lookup({value, use}));
383 for (
auto &orTerm : orTerms) {
384 auto orTable = APInt::getAllOnes(tableSize);
385 for (
auto &andTerm : orTerm.andTerms) {
387 orTable &= getTermMask(andTerm.value,
AndTerm::Id);
389 orTable &= ~getTermMask(andTerm.value,
AndTerm::Id);
399 if (table.isZero()) {
403 if (table.isAllOnes()) {
405 orTerms.push_back(
OrTerm());
411 auto remainingBits = table;
412 for (
unsigned i = 0; i < 10 && !remainingBits.isZero(); ++i) {
413 unsigned nextIdx = remainingBits.countTrailingZeros();
414 unsigned bestKeeps = -1;
415 auto bestMask = APInt::getZero(tableSize);
416 for (
unsigned keeps = 0; keeps < tableSize; ++keeps) {
417 auto mask = APInt::getAllOnes(tableSize);
418 for (
unsigned termIdx = 0; termIdx < terms.size(); ++termIdx)
419 if (keeps & (1 << termIdx))
420 mask &= (nextIdx & (1 << termIdx)) ? getCheckerMask(termIdx)
421 : ~getCheckerMask(termIdx);
422 if ((table & mask) == mask &&
423 llvm::popcount(keeps) < llvm::popcount(bestKeeps)) {
429 for (
auto [term, termIdx] : terms) {
430 if (~bestKeeps & (1 << termIdx))
432 unsigned use = term.second;
433 if (~nextIdx & (1 << termIdx))
435 if (!andTerms.empty() && andTerms.back().value == term.first)
438 andTerms.push_back(
AndTerm(term.first, 1 << use));
440 llvm::sort(andTerms);
441 newTerms.push_back(
OrTerm(std::move(andTerms)));
442 remainingBits &= ~bestMask;
445 llvm::sort(newTerms);
446 orTerms = std::move(newTerms);
450 llvm::function_ref<std::optional<bool>(Value,
bool)> evaluateTerm) {
451 bool allFalse =
true;
453 auto result = orTerm.evaluate(evaluateTerm);
467 llvm::function_ref<
void(Value)> printValue)
const {
483 SmallMapVector<Value, unsigned, 8> valueIds;
484 auto defaultPrintValue = [&](Value value) {
485 os <<
"v" << valueIds.insert({value, valueIds.size()}).first->second;
488 printValue = defaultPrintValue;
492 orTerms, os, [&](
auto &orTerm) { orTerm.print(os, printValue); },
" | ");
499 SmallMapVector<Value, unsigned, 8> valueIds;
500 print(os, [&](Value value) {
501 auto id = valueIds.insert({value, valueIds.size()}).first->second;
506 if (!valueIds.empty()) {
508 llvm::interleaveComma(valueIds, os, [&](
auto valueAndId) {
509 os <<
"v" << valueAndId.second <<
" = ";
510 valueAndId.first.printAsOperand(os, OpPrintingFlags());
545 auto result =
DNF(
false);
546 unsigned thisIdx = 0;
547 unsigned otherIdx = 0;
548 while (thisIdx <
orTerms.size() && otherIdx < other.
orTerms.size()) {
552 nextTerm = std::move(
orTerms[thisIdx++]);
553 }
else if (order > 0) {
554 nextTerm = other.
orTerms[otherIdx++];
559 result.orTerms.push_back(std::move(nextTerm));
561 for (; thisIdx <
orTerms.size(); ++thisIdx)
562 result.orTerms.push_back(std::move(
orTerms[thisIdx]));
563 for (; otherIdx < other.
orTerms.size(); ++otherIdx)
564 result.orTerms.push_back(other.
orTerms[otherIdx]);
595 auto result =
DNF(
false);
596 for (
auto &thisTerm :
orTerms) {
597 for (
auto &otherTerm : other.
orTerms) {
598 auto newTerm = thisTerm;
599 if (newTerm.addTerms(otherTerm.andTerms))
603 assert(result.isSortedAndUnique());
633 return ~(*this) & other | *
this & ~other;
654 auto result =
DNF(
true);
655 auto inverted =
DNF(
false);
658 for (
auto &andTerm : orTerm.andTerms)
659 for (
unsigned i = 0; i < 4; ++i)
661 inverted.orTerms.push_back(
663 llvm::sort(inverted.orTerms);
665 inverted.orTerms.clear();
667 assert(result.isSortedAndUnique());
assert(baseType &&"element must be base type")
static bool isUniqued(Container &container)
Check whether a container is sorted and contains only unique items.
static bool insertUniqued(Container &container, Item item)
Insert an item into something like a vector, maintaining the vector in sorted order and removing any ...
static bool compareValueOnly(const AndTerm &a, const AndTerm &b)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
An individual term of an AND expression in a DNF.
Use
An integer indicating one use of the value in this term.
@ NotPast
The inverted past value !@x.
@ NotId
The inverted value !x.
@ Not
The bit that indicates inversion.
static constexpr Uses PosEdgeUses
The set of uses that indicates a posedge.
Uses uses
The different uses of this value.
bool isSubsetOf(const AndTerm &other) const
Check if this term is a subset of another term.
unsigned isSubsetOfModuloSingleFlip(const AndTerm &other, Use &flippedUse) const
Check if this term is a subset of another term modulo a single flipped term.
static constexpr Uses NegEdgeUses
The set of uses that indicates a negedge.
int compare(const AndTerm other) const
Compare against another term.
void print(llvm::raw_ostream &os, llvm::function_ref< void(Value)> printValue={}) const
Print this term to os, using the given callback to print the value.
DNF operator~() const
Compute the boolean NOT of this DNF.
DNF()
Construct a null DNF.
DNF operator&(const DNF &other) const
Compute the boolean AND of this and another DNF.
std::optional< bool > evaluate(llvm::function_ref< std::optional< bool >(Value, bool)> evaluateTerm)
Try to evaluate this DNF to a constant true or false value.
DNF operator|(const DNF &other) const
Compute the boolean OR of this and another DNF.
void print(llvm::raw_ostream &os, llvm::function_ref< void(Value)> printValue={}) const
Print this DNF to os, using the given callback to print the value.
int compare(const DNF &other) const
Compare against another DNF.
bool contains(const OrTerm &orTerm) const
Check if this DNF contains a specific OR term.
void printWithValues(llvm::raw_ostream &os) const
Print this DNF to os, followed by a list of the concrete values used.
void optimize()
Removes redundant terms as follows:
DNF operator^(const DNF &other) const
Compute the boolean XOR of this and another DNF.
bool isTrue() const
Check whether this DNF is trivially true.
bool isNull() const
Check whether this DNF is null.
bool isFalse() const
Check whether this DNF is trivially false.
bool isSortedAndUnique() const
Check that all terms in the DNF are sorted.
An individual term of an OR expression in a DNF.
llvm::hash_code flipInvariantHash() const
Return a hash code for this term that is invariant to inversion of individual terms.
void print(llvm::raw_ostream &os, llvm::function_ref< void(Value)> printValue={}) const
Print this term to os, using the given callback to print the value.
bool isSubsetOfModuloSingleFlip(const OrTerm &other, unsigned &flippedIdx, AndTerm::Use &flippedUse) const
Check if this term is a subset of another term modulo a single flipped term.
bool contains(const AndTerm &andTerm) const
Check if this OR term contains a specific AND term.
bool isTrue() const
Check if this term is trivially true.
SmallVector< AndTerm, 1 > AndTerms
std::optional< bool > evaluate(llvm::function_ref< std::optional< bool >(Value, bool)> evaluateTerm)
Try to evaluate this term to a constant true or false value.
bool isSubsetOf(const OrTerm &other) const
Check if this term is a subset of another term.
bool addTerm(AndTerm term)
Add an AndTerm.
int compare(const OrTerm &other) const
Compare against another term.
bool isSortedAndUnique() const
Check that all terms in this OrTerm are sorted.
bool addTerms(ArrayRef< AndTerm > terms)
Add multiple AndTerms.