Loading [MathJax]/extensions/tex2jax.js
CIRCT 21.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
DNF.h
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
10#include "mlir/IR/Value.h"
11#include "llvm/ADT/SmallVector.h"
12#include "llvm/Support/raw_ostream.h"
13#include <bitset>
14
15namespace circt {
16namespace llhd {
17
18/// An individual term of an AND expression in a DNF. This struct represents all
19/// terms of the same `Value`.
20struct AndTerm {
21 /// An integer indicating one use of the value in this term. There are four
22 /// different uses, which means there are a total of 2^4 different
23 /// combinations each of which has its own bit in the `uses` mask.
24 enum Use {
25 /// The plain value `x`.
26 Id = 0b00,
27 /// The past value `@x`.
28 Past = 0b01,
29 /// The bit that indicates inversion.
30 Not = 0b10,
31 /// The inverted value `!x`.
33 /// The inverted past value `!@x`.
35 };
36 /// The set of uses of this value as a bit mask.
37 using Uses = std::bitset<4>;
38
39 /// The set of uses that indicates a posedge.
40 static constexpr Uses PosEdgeUses = (1 << Id) | (1 << NotPast);
41 /// The set of uses that indicates a negedge.
42 static constexpr Uses NegEdgeUses = (1 << NotId) | (1 << Past);
43 /// The set of present uses.
44 static constexpr Uses IdUses = (1 << Id) | (1 << NotId);
45 /// The set of past uses.
46 static constexpr Uses PastUses = (1 << Past) | (1 << NotPast);
47
48 /// The value.
49 Value value;
50 /// The different uses of this value.
52
53 /// Create a null term.
55 /// Create a term with a value and a set of uses.
57 /// Create a term with a plain value.
58 static AndTerm id(Value value) { return AndTerm(value, 1 << Id); }
59 /// Create a term with a past value.
60 static AndTerm past(Value value) { return AndTerm(value, 1 << Past); }
61 /// Create a term representing a posedge on a value.
62 static AndTerm posEdge(Value value) { return AndTerm(value, PosEdgeUses); }
63 /// Create a term representing a negedge on a value.
64 static AndTerm negEdge(Value value) { return AndTerm(value, NegEdgeUses); }
65
66 /// Check if this term is trivially false. This is the case if it contains
67 /// complementary uses, such as `Id & !Id`.
68 bool isFalse() const { return (uses & (uses >> 2)).any(); }
69 /// Check if this term is trivially true. This is the case if there are no
70 /// uses.
71 bool isTrue() const { return uses.none(); }
72 /// If this AND term has a single use, return it.
73 std::optional<std::pair<Value, AndTerm::Use>> getSingleTerm() const {
74 if (getNumUses() == 1)
75 return std::make_pair(value, Use(llvm::countr_zero(uses.to_ulong())));
76 return {};
77 }
78
79 /// Compare against another term.
80 int compare(const AndTerm other) const;
81 bool operator==(const AndTerm other) const { return compare(other) == 0; }
82 bool operator!=(const AndTerm other) const { return compare(other) != 0; }
83 bool operator<(const AndTerm other) const { return compare(other) < 0; }
84 bool operator>(const AndTerm other) const { return compare(other) > 0; }
85 bool operator<=(const AndTerm other) const { return compare(other) <= 0; }
86 bool operator>=(const AndTerm other) const { return compare(other) >= 0; }
87
88 /// Get the number of uses.
89 unsigned getNumUses() const { return llvm::popcount(uses.to_ulong()); }
90
91 /// Add a single use.
92 void addUse(Use u) { uses.set(u); }
93 /// Add multiple uses.
94 void addUses(Uses u) { uses |= u; }
95 /// Remove a single use.
96 void removeUse(Use u) { uses.reset(u); }
97 /// Remove multiple uses.
98 void removeUses(Uses u) { uses &= ~u; }
99
100 /// Check if this term has a specific use of the term's value.
101 bool hasUse(Use u) const { return uses.test(u); }
102 /// Check if this term has all of the specified uses of the term's value.
103 bool hasAllUses(Uses u) const { return (uses & u) == u; }
104 /// Check if this term has any of the specified uses of the term's value.
105 bool hasAnyUses(Uses u) const { return (uses & u).any(); }
106
107 /// Check if this term is a subset of another term. For example, `a & @a` is
108 /// considered a subset of `a`.
109 bool isSubsetOf(const AndTerm &other) const;
110
111 /// Check if this term is a subset of another term modulo a single flipped
112 /// term. Returns 0 if this term is a subset of the other without any flips;
113 /// returns 1 if there is a single flip, with `flippedUse` set to indicate the
114 /// flipped term; or returns 2 if this term is no subset or there are more
115 /// than one flips.
116 unsigned isSubsetOfModuloSingleFlip(const AndTerm &other,
117 Use &flippedUse) const;
118
119 /// Print this term to `os`, using the given callback to print the value.
120 void print(llvm::raw_ostream &os,
121 llvm::function_ref<void(Value)> printValue = {}) const;
122};
123
124/// An individual term of an OR expression in a DNF. Consists of multiple terms
125/// AND-ed together. A `true` value is represented as an empty list of AND
126/// terms, since the neutral element of the AND operation is `true`.
127struct OrTerm {
128 using AndTerms = SmallVector<AndTerm, 1>;
130
131 /// Create a constant `true` term.
133 /// Create a term with a single element.
134 OrTerm(AndTerm singleTerm) { andTerms.push_back(singleTerm); }
135 /// Create a term with multiple elements. The terms must be sorted.
139
140 /// Check if this term is trivially true.
141 bool isTrue() const { return andTerms.empty(); }
142 /// Check if this term is trivially false.
143 bool isFalse() const {
144 return llvm::any_of(andTerms, [](auto term) { return term.isFalse(); });
145 }
146 /// If this OR term consists of a single term, return it.
147 std::optional<std::pair<Value, AndTerm::Use>> getSingleTerm() const {
148 if (andTerms.size() == 1)
149 return andTerms[0].getSingleTerm();
150 return {};
151 }
152 /// Check if this OR term contains a specific AND term.
153 bool contains(const AndTerm &andTerm) const;
154
155 /// Compare against another term.
156 int compare(const OrTerm &other) const;
157 bool operator==(const OrTerm &other) const { return compare(other) == 0; }
158 bool operator!=(const OrTerm &other) const { return compare(other) != 0; }
159 bool operator<(const OrTerm &other) const { return compare(other) < 0; }
160 bool operator>(const OrTerm &other) const { return compare(other) > 0; }
161 bool operator<=(const OrTerm &other) const { return compare(other) <= 0; }
162 bool operator>=(const OrTerm &other) const { return compare(other) >= 0; }
163
164 /// Check if this term is a subset of another term. `a & b & c` is considered
165 /// a subset of `a & b`.
166 bool isSubsetOf(const OrTerm &other) const;
167
168 /// Check if this term is a subset of another term modulo a single flipped
169 /// term. If it is, `flippedIdx` and `flippedUse` are set to indicate the
170 /// flipped term. `a & b & c` is considered a subset of `!a & b` with a single
171 /// flipped term `a`.
172 bool isSubsetOfModuloSingleFlip(const OrTerm &other, unsigned &flippedIdx,
173 AndTerm::Use &flippedUse) const;
174
175 /// Return a hash code for this term that is invariant to inversion of
176 /// individual terms.
177 llvm::hash_code flipInvariantHash() const;
178
179 /// Add an `AndTerm`. Returns false if adding the `AndTerm` has made this
180 /// `OrTerm` trivially false.
181 bool addTerm(AndTerm term);
182 /// Add multiple `AndTerm`s. Returns false if adding the terms has made this
183 /// `OrTerm` trivially false.
184 bool addTerms(ArrayRef<AndTerm> terms);
185
186 /// Check that all terms in this `OrTerm` are sorted. This is an invariant we
187 /// want to check in builds with asserts enabled.
188 bool isSortedAndUnique() const;
189
190 /// Try to evaluate this term to a constant true or false value.
191 std::optional<bool>
192 evaluate(llvm::function_ref<std::optional<bool>(Value, bool)> evaluateTerm);
193
194 /// Print this term to `os`, using the given callback to print the value.
195 void print(llvm::raw_ostream &os,
196 llvm::function_ref<void(Value)> printValue = {}) const;
197};
198
199struct DNF {
200 using OrTerms = SmallVector<OrTerm, 1>;
202
203 /// Construct a null DNF.
204 DNF() : DNF(AndTerm::id(Value{})) {}
205 /// Construct a constant `true` or `false`.
206 explicit DNF(bool value) {
207 if (value)
208 orTerms.push_back(OrTerm());
209 }
210 /// Construct a DNF with a single opaque `Value`.
211 explicit DNF(Value value) : DNF(AndTerm::id(value)) {}
212 /// Construct a DNF with a given AND term inside a single OR term.
213 explicit DNF(AndTerm value) : DNF(OrTerm(value)) {}
214 /// Construct a DNF with a given OR term.
215 explicit DNF(OrTerm value) { orTerms.push_back(value); }
216 /// Construct a DNF with a multiple OR terms. The terms must be sorted.
217 explicit DNF(OrTerms terms) : orTerms(terms) { assert(isSortedAndUnique()); }
218 /// Construct a DNF with a single opaque past `Value`.
219 static DNF withPastValue(Value value) { return DNF(AndTerm::past(value)); }
220
221 /// Check whether this DNF is null.
222 bool isNull() const {
223 return orTerms.size() == 1 && orTerms[0].andTerms.size() == 1 &&
224 !orTerms[0].andTerms[0].value &&
225 orTerms[0].andTerms[0].uses == (1 << AndTerm::Id);
226 }
227 explicit operator bool() const { return !isNull(); }
228 /// Check whether this DNF is trivially false.
229 bool isFalse() const { return orTerms.empty(); }
230 /// Check whether this DNF is trivially true.
231 bool isTrue() const { return orTerms.size() == 1 && orTerms[0].isTrue(); }
232 /// If this DNF consists of a single term, return it.
233 std::optional<std::pair<Value, AndTerm::Use>> getSingleTerm() const {
234 if (!isNull() && orTerms.size() == 1)
235 return orTerms[0].getSingleTerm();
236 return {};
237 }
238 /// Check if this DNF contains a specific OR term.
239 bool contains(const OrTerm &orTerm) const;
240 /// Check if this DNF contains a specific AND term.
241 bool contains(const AndTerm &andTerm) const;
242
243 /// Compare against another DNF.
244 int compare(const DNF &other) const;
245 bool operator==(const DNF &other) const { return compare(other) == 0; }
246 bool operator!=(const DNF &other) const { return compare(other) != 0; }
247 bool operator<(const DNF &other) const { return compare(other) < 0; }
248 bool operator>(const DNF &other) const { return compare(other) > 0; }
249 bool operator>=(const DNF &other) const { return compare(other) >= 0; }
250 bool operator<=(const DNF &other) const { return compare(other) <= 0; }
251
252 /// Compute the boolean OR of this and another DNF.
253 DNF operator|(const DNF &other) const;
254 /// Compute the boolean AND of this and another DNF.
255 DNF operator&(const DNF &other) const;
256 /// Compute the boolean XOR of this and another DNF.
257 DNF operator^(const DNF &other) const;
258 /// Compute the boolean NOT of this DNF.
259 DNF operator~() const;
260
261 DNF &operator|=(const DNF &other) { return *this = *this | other; }
262 DNF &operator&=(const DNF &other) { return *this = *this & other; }
263 DNF &operator^=(const DNF &other) { return *this = *this ^ other; }
264 DNF &negate() { return *this = ~*this; }
265
266 /// Check that all terms in the DNF are sorted. This is an invariant we want
267 /// to check in builds with asserts enabled.
268 bool isSortedAndUnique() const;
269
270 /// Removes redundant terms as follows:
271 /// - a&x | !a&x -> x (eliminate complements)
272 /// - a&x | x -> x (eliminate supersets)
273 void optimize();
274
275 /// Try to evaluate this DNF to a constant true or false value.
276 std::optional<bool>
277 evaluate(llvm::function_ref<std::optional<bool>(Value, bool)> evaluateTerm);
278
279 /// Print this DNF to `os`, using the given callback to print the value.
280 void print(llvm::raw_ostream &os,
281 llvm::function_ref<void(Value)> printValue = {}) const;
282 /// Print this DNF to `os`, followed by a list of the concrete values used.
283 void printWithValues(llvm::raw_ostream &os) const;
284};
285
286} // namespace llhd
287} // namespace circt
assert(baseType &&"element must be base type")
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
An individual term of an AND expression in a DNF.
Definition DNF.h:20
static constexpr Uses PastUses
The set of past uses.
Definition DNF.h:46
bool hasAllUses(Uses u) const
Check if this term has all of the specified uses of the term's value.
Definition DNF.h:103
void removeUses(Uses u)
Remove multiple uses.
Definition DNF.h:98
Use
An integer indicating one use of the value in this term.
Definition DNF.h:24
@ NotPast
The inverted past value !@x.
Definition DNF.h:34
@ Past
The past value @x.
Definition DNF.h:28
@ Id
The plain value x.
Definition DNF.h:26
@ NotId
The inverted value !x.
Definition DNF.h:32
@ Not
The bit that indicates inversion.
Definition DNF.h:30
bool isTrue() const
Check if this term is trivially true.
Definition DNF.h:71
static AndTerm past(Value value)
Create a term with a past value.
Definition DNF.h:60
AndTerm(Value value, Uses uses)
Create a term with a value and a set of uses.
Definition DNF.h:56
bool operator==(const AndTerm other) const
Definition DNF.h:81
bool hasAnyUses(Uses u) const
Check if this term has any of the specified uses of the term's value.
Definition DNF.h:105
std::optional< std::pair< Value, AndTerm::Use > > getSingleTerm() const
If this AND term has a single use, return it.
Definition DNF.h:73
bool hasUse(Use u) const
Check if this term has a specific use of the term's value.
Definition DNF.h:101
static AndTerm negEdge(Value value)
Create a term representing a negedge on a value.
Definition DNF.h:64
bool operator>=(const AndTerm other) const
Definition DNF.h:86
static constexpr Uses PosEdgeUses
The set of uses that indicates a posedge.
Definition DNF.h:40
std::bitset< 4 > Uses
The set of uses of this value as a bit mask.
Definition DNF.h:37
void addUse(Use u)
Add a single use.
Definition DNF.h:92
static AndTerm posEdge(Value value)
Create a term representing a posedge on a value.
Definition DNF.h:62
Uses uses
The different uses of this value.
Definition DNF.h:51
bool isSubsetOf(const AndTerm &other) const
Check if this term is a subset of another term.
Definition DNF.cpp:62
unsigned isSubsetOfModuloSingleFlip(const AndTerm &other, Use &flippedUse) const
Check if this term is a subset of another term modulo a single flipped term.
Definition DNF.cpp:68
unsigned getNumUses() const
Get the number of uses.
Definition DNF.h:89
bool operator!=(const AndTerm other) const
Definition DNF.h:82
bool operator>(const AndTerm other) const
Definition DNF.h:84
void removeUse(Use u)
Remove a single use.
Definition DNF.h:96
bool operator<(const AndTerm other) const
Definition DNF.h:83
bool operator<=(const AndTerm other) const
Definition DNF.h:85
Value value
The value.
Definition DNF.h:49
static constexpr Uses NegEdgeUses
The set of uses that indicates a negedge.
Definition DNF.h:42
int compare(const AndTerm other) const
Compare against another term.
Definition DNF.cpp:50
bool isFalse() const
Check if this term is trivially false.
Definition DNF.h:68
AndTerm()
Create a null term.
Definition DNF.h:54
void addUses(Uses u)
Add multiple uses.
Definition DNF.h:94
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.
Definition DNF.cpp:98
static AndTerm id(Value value)
Create a term with a plain value.
Definition DNF.h:58
static constexpr Uses IdUses
The set of present uses.
Definition DNF.h:44
OrTerms orTerms
Definition DNF.h:201
DNF operator~() const
Compute the boolean NOT of this DNF.
Definition DNF.cpp:640
DNF & negate()
Definition DNF.h:264
SmallVector< OrTerm, 1 > OrTerms
Definition DNF.h:200
bool operator<=(const DNF &other) const
Definition DNF.h:250
bool operator!=(const DNF &other) const
Definition DNF.h:246
bool operator>(const DNF &other) const
Definition DNF.h:248
DNF()
Construct a null DNF.
Definition DNF.h:204
bool operator==(const DNF &other) const
Definition DNF.h:245
DNF operator&(const DNF &other) const
Compute the boolean AND of this and another DNF.
Definition DNF.cpp:574
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.
Definition DNF.cpp:449
DNF operator|(const DNF &other) const
Compute the boolean OR of this and another DNF.
Definition DNF.cpp:521
DNF(bool value)
Construct a constant true or false.
Definition DNF.h:206
DNF & operator|=(const DNF &other)
Definition DNF.h:261
DNF(AndTerm value)
Construct a DNF with a given AND term inside a single OR term.
Definition DNF.h:213
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.
Definition DNF.cpp:466
DNF(OrTerms terms)
Construct a DNF with a multiple OR terms. The terms must be sorted.
Definition DNF.h:217
bool operator>=(const DNF &other) const
Definition DNF.h:249
int compare(const DNF &other) const
Compare against another DNF.
Definition DNF.cpp:336
bool contains(const OrTerm &orTerm) const
Check if this DNF contains a specific OR term.
Definition DNF.cpp:324
DNF & operator&=(const DNF &other)
Definition DNF.h:262
void printWithValues(llvm::raw_ostream &os) const
Print this DNF to os, followed by a list of the concrete values used.
Definition DNF.cpp:495
void optimize()
Removes redundant terms as follows:
Definition DNF.cpp:359
DNF operator^(const DNF &other) const
Compute the boolean XOR of this and another DNF.
Definition DNF.cpp:612
DNF & operator^=(const DNF &other)
Definition DNF.h:263
static DNF withPastValue(Value value)
Construct a DNF with a single opaque past Value.
Definition DNF.h:219
DNF(Value value)
Construct a DNF with a single opaque Value.
Definition DNF.h:211
bool operator<(const DNF &other) const
Definition DNF.h:247
bool isTrue() const
Check whether this DNF is trivially true.
Definition DNF.h:231
std::optional< std::pair< Value, AndTerm::Use > > getSingleTerm() const
If this DNF consists of a single term, return it.
Definition DNF.h:233
bool isNull() const
Check whether this DNF is null.
Definition DNF.h:222
bool isFalse() const
Check whether this DNF is trivially false.
Definition DNF.h:229
bool isSortedAndUnique() const
Check that all terms in the DNF are sorted.
Definition DNF.cpp:349
DNF(OrTerm value)
Construct a DNF with a given OR term.
Definition DNF.h:215
An individual term of an OR expression in a DNF.
Definition DNF.h:127
bool operator==(const OrTerm &other) const
Definition DNF.h:157
bool operator>=(const OrTerm &other) const
Definition DNF.h:162
llvm::hash_code flipInvariantHash() const
Return a hash code for this term that is invariant to inversion of individual terms.
Definition DNF.cpp:230
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.
Definition DNF.cpp:299
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.
Definition DNF.cpp:163
bool contains(const AndTerm &andTerm) const
Check if this OR term contains a specific AND term.
Definition DNF.cpp:145
bool isTrue() const
Check if this term is trivially true.
Definition DNF.h:141
AndTerms andTerms
Definition DNF.h:129
OrTerm(AndTerm singleTerm)
Create a term with a single element.
Definition DNF.h:134
SmallVector< AndTerm, 1 > AndTerms
Definition DNF.h:128
bool isFalse() const
Check if this term is trivially false.
Definition DNF.h:143
std::optional< std::pair< Value, AndTerm::Use > > getSingleTerm() const
If this OR term consists of a single term, return it.
Definition DNF.h:147
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.
Definition DNF.cpp:275
OrTerm(AndTerms andTerms)
Create a term with multiple elements. The terms must be sorted.
Definition DNF.h:136
OrTerm()
Create a constant true term.
Definition DNF.h:132
bool isSubsetOf(const OrTerm &other) const
Check if this term is a subset of another term.
Definition DNF.cpp:203
bool operator>(const OrTerm &other) const
Definition DNF.h:160
bool addTerm(AndTerm term)
Add an AndTerm.
Definition DNF.cpp:245
bool operator<=(const OrTerm &other) const
Definition DNF.h:161
int compare(const OrTerm &other) const
Compare against another term.
Definition DNF.cpp:150
bool operator<(const OrTerm &other) const
Definition DNF.h:159
bool isSortedAndUnique() const
Check that all terms in this OrTerm are sorted.
Definition DNF.cpp:265
bool operator!=(const OrTerm &other) const
Definition DNF.h:158
bool addTerms(ArrayRef< AndTerm > terms)
Add multiple AndTerms.
Definition DNF.cpp:258