Debian Codegraph @

visa/iga/IGALibrary/IR/BitSet.hpp

raw
1 /*========================== begin_copyright_notice ============================
2
3 Copyright (C) 2017-2021 Intel Corporation
4
5 SPDX-License-Identifier: MIT
6
7 ============================= end_copyright_notice ===========================*/
8
9 #ifndef _IGA_BITSET_HPP
10 #define _IGA_BITSET_HPP
11
12 #include "../asserts.hpp"
13 #include "common/secure_mem.h"
14
15 #include <algorithm>
16 #include <bitset>
17 #include <cstdint>
18 #include <cstring>
19 #include <ostream>
20 #include <sstream>
21 #include <string>
22 #include <utility>
23
24 // Align N up to the nearest multiple of A
25 #define ALIGN_UP_TO(A, N) ((N + (A)-1) - (N + (A)-1) % (A))
26
27 namespace iga {
28
29 // I so badly wanted to just use std::bitset and then drink beer with my free
30 // time. Alas this lacks some of the APIs that I need to efficiently
31 // perform data flow. Specifically, I need efficient testAny/testAll
32 // predicates.
33 template <typename I = uint32_t> class BitSet {
34 public:
35 static const size_t BITS_PER_WORD = 8 * sizeof(I);
36
37 // allocate and zero bits
38 BitSet(size_t numBits)
39 : N(numBits),
40 wordsSize(ALIGN_UP_TO(BITS_PER_WORD, numBits) / BITS_PER_WORD) {
41 words = new I[wordsSize];
42 reset();
43 }
44 BitSet(const BitSet<I> &rhs)
45 : N(rhs.N), wordsSize(ALIGN_UP_TO(BITS_PER_WORD, rhs.N) / BITS_PER_WORD)
46
47 {
48 words = new I[wordsSize];
49 memcpy_s(words, wordsSize * sizeof(I), rhs.words, wordsSize * sizeof(I));
50 }
51
52 BitSet(BitSet<I> &&copy) noexcept
53 : N(copy.N), wordsSize(copy.wordsSize), words(copy.words) {
54 copy.words = nullptr;
55 copy.N = copy.wordsSize = 0;
56 }
57
58 BitSet<I> &operator=(const BitSet<I> &rhs) {
59 if (this == &rhs) {
60 return *this;
61 }
62 if (rhs.N != N) {
63 // resize
64 if (words)
65 delete[] words;
66 N = rhs.N;
67 wordsSize = rhs.wordsSize;
68 words = new I[wordsSize];
69 }
70 memcpy_s(words, wordsSize * sizeof(I), rhs.words, wordsSize * sizeof(I));
71 return *this;
72 }
73
74 BitSet<I> &operator=(BitSet<I> &&rhs) {
75 if (this == &rhs) {
76 return *this;
77 }
78 if (words) {
79 delete[] words;
80 }
81
82 N = rhs.N;
83 wordsSize = rhs.wordsSize;
84 words = rhs.words;
85
86 rhs.words = nullptr;
87
88 return *this;
89 }
90
91 ~BitSet() {
92 if (words) {
93 delete[] words;
94 words = nullptr;
95 }
96 }
97
98 // TODO: remove
99 void reset() { clear(); }
100
101 void clear() { memset(words, 0, wordsSize * sizeof(I)); }
102 bool set(size_t off, size_t len = 1, bool val = true); // sets/clears range
103 bool test(size_t off) const { return testAny(off, 1); }
104 bool testAny(size_t off, size_t len) const;
105 bool testAll(size_t off, size_t len) const;
106 void containsAll(const BitSet<I> &rhs) const;
107 bool empty() const { return !testAny(0, N); }
108
109 bool intersects(const BitSet<I> &rhs) const;
110
111 // If the bitSets have intersects in given range, start from off and with
112 // legnth len off: bit offset len: range length in bits
113 bool intersects(const BitSet<I> &rhs, size_t off, size_t len) const;
114
115 // if the given rhs is completely the same as itself
116 bool equal(const BitSet<I> &rhs) const;
117
118 // THERE EXISTS WORD w such that ((w & mask) == eq)
119 // bool testAnyEq(size_t off, size_t len, const I &mask, const I &eq) const;
120 // FOR ALL ...
121 // bool testAllEq(size_t off, size_t len, const I &mask, const I &eq) const;
122
123 // BitSet& operator ~() const;
124 bool andNot(const BitSet<I> &rhs); // set subtraction
125 bool add(const BitSet<I> &rhs); // set union
126 bool intersectInto(const BitSet<I> &rhs, BitSet<I> &into)
127 const; // set intersection (returns true if result non-empty)
128
129 bool operator[](const size_t &ix) const { return test(ix); }
130 bool operator==(const BitSet<I> &bs) const;
131 bool operator!=(const BitSet<I> &bs) const { return !(*this == bs); }
132 std::string str() const {
133 std::stringstream ss;
134 str(ss);
135 return ss.str();
136 }
137 void str(std::ostream &os) const;
138 size_t cardinality() const;
139
140 static BitSet<I> intersection(const BitSet<I> &bs1, const BitSet<I> &bs2) {
141 BitSet<I> bsI(bs1.N);
142 bs1.intersectInto(bs2, bsI);
143 return bsI;
144 }
145
146 private:
147 size_t N;
148 size_t wordsSize;
149 I *words;
150
151 static I makeMask(size_t len) {
152 IGA_ASSERT(len <= BITS_PER_WORD,
153 "BitSet::makeMask: length too large for mask");
154 if (len == BITS_PER_WORD) {
155 return (I)-1;
156 }
157 return (1 << len) - 1;
158 }
159 };
160
161 template <typename I>
162 inline bool BitSet<I>::set(size_t off, size_t len, bool val) {
163 IGA_ASSERT(off >= 0 && off + len <= N, "BitSet::set: index out of bounds");
164
165 // check the first word (misaligned mask)
166 auto w_ix = off / BITS_PER_WORD;
167 auto w_off = off % BITS_PER_WORD;
168 auto misaligned_len = std::min<size_t>(BITS_PER_WORD - w_off, len);
169 auto misaligned_mask = makeMask(misaligned_len) << w_off;
170 auto oldWord0 = words[w_ix];
171 if (val) {
172 words[w_ix] |= misaligned_mask;
173 } else {
174 words[w_ix] &= ~misaligned_mask;
175 }
176 bool changed = oldWord0 != words[w_ix];
177
178 // check successive words (all aligned now)
179 len -= misaligned_len;
180 off += misaligned_len;
181 while (len > 0) {
182 w_ix++; // next word
183
184 auto aligned_len = len >= 32 ? 32 : len % BITS_PER_WORD; // last will be <32
185 auto aligned_mask = makeMask(aligned_len);
186 auto oldWord = words[w_ix];
187 if (val) {
188 words[w_ix] |= aligned_mask;
189 } else {
190 words[w_ix] &= ~aligned_mask;
191 }
192 changed |= words[w_ix] != oldWord;
193
194 len -= aligned_len;
195 off += aligned_len;
196 }
197
198 return changed;
199 }
200
201 template <typename I>
202 inline bool BitSet<I>::intersects(const BitSet<I> &rhs) const {
203 for (size_t i = 0; i < wordsSize; i++) {
204 if (words[i] & rhs.words[i]) {
205 return true;
206 }
207 }
208 return false;
209 }
210
211 template <typename I>
212 inline bool BitSet<I>::intersects(const BitSet<I> &rhs, size_t off,
213 size_t len) const {
214
215 IGA_ASSERT(off >= 0 && off + len <= N,
216 "BitSet::intersects: index out of bounds");
217
218 // check the first word (may misaligned)
219 auto w_ix = off / BITS_PER_WORD; // idx of the first word
220 auto w_off = off % BITS_PER_WORD; // length from w_ix to off
221 size_t misaligned_len = std::min<size_t>(BITS_PER_WORD - w_off, len);
222 I misaligned_mask = makeMask(misaligned_len);
223 if (((words[w_ix] >> w_off) & misaligned_mask) &
224 ((rhs.words[w_ix] >> w_off) & misaligned_mask)) {
225 return true;
226 }
227
228 // check successive words (all aligned now)
229 len -= misaligned_len;
230 off += misaligned_len;
231 while (len > 0) {
232 w_ix++; // next word
233
234 auto aligned_len = len >= 32 ? 32 : len % BITS_PER_WORD; // last will be <32
235 auto aligned_mask = makeMask(aligned_len);
236 if ((words[w_ix] & aligned_mask) & (rhs.words[w_ix] & aligned_mask)) {
237 return true;
238 }
239 len -= aligned_len;
240 off += aligned_len;
241 }
242 return false;
243 }
244
245 template <typename I> inline bool BitSet<I>::equal(const BitSet<I> &rhs) const {
246 bool result = true;
247 for (size_t i = 0; i < wordsSize; i++) {
248 result = (words[i] == rhs.words[i]) ? true : false;
249 if (!result)
250 break;
251 }
252 // padding will remain 0 since both padding are 0's
253 // 0 & 0 is 0 so no need special handling on padding
254 return result;
255 }
256
257 template <typename I> inline bool BitSet<I>::andNot(const BitSet<I> &rhs) {
258 bool changed = false;
259 for (size_t i = 0; i < wordsSize; i++) {
260 auto old = words[i];
261 words[i] &= ~rhs.words[i];
262 changed |= (words[i] != old);
263 }
264 // padding will remain 0 since padding is already 0's
265 // ((0x...000 & 0x...FFF) == 0x...000)
266 // this rhs
267 return changed;
268 }
269
270 template <typename I> inline bool BitSet<I>::add(const BitSet<I> &rhs) {
271 bool changed = false;
272 for (size_t i = 0; i < wordsSize; i++) {
273 auto old = words[i];
274 words[i] |= rhs.words[i];
275 changed |= (words[i] != old);
276 }
277 // padding will remain 0 since both padding are 0's
278 // ((0x...000 & 0x...FFF) == 0x...000)
279 // this rhs
280 return changed;
281 }
282
283 template <typename I>
284 inline bool BitSet<I>::intersectInto(const BitSet<I> &rhs,
285 BitSet<I> &into) const {
286 bool notEmpty = false;
287 for (size_t i = 0; i < wordsSize; i++) {
288 into.words[i] = words[i] & rhs.words[i];
289 notEmpty |= (into.words[i] != 0);
290 }
291 // doesn't matter if the padding matches (it'll be correct either way)
292 return notEmpty;
293 }
294
295 template <typename I>
296 inline bool BitSet<I>::testAny(size_t off, size_t len) const {
297 IGA_ASSERT(off >= 0 && off + len <= N,
298 "BitSet::testAll: index out of bounds");
299
300 // check the first word (misaligned mask)
301 auto w_ix = off / BITS_PER_WORD;
302 auto w_off = off % BITS_PER_WORD;
303 size_t misaligned_len = std::min<size_t>(BITS_PER_WORD - w_off, len);
304 I misaligned_mask = makeMask(misaligned_len);
305 if ((words[w_ix] >> w_off) & misaligned_mask) {
306 return true;
307 }
308
309 // check successive words (all aligned now)
310 len -= misaligned_len;
311 off += misaligned_len;
312 while (len > 0) {
313 w_ix++; // next word
314
315 auto aligned_len = len >= 32 ? 32 : len % BITS_PER_WORD; // last will be <32
316 auto aligned_mask = makeMask(aligned_len);
317 if (words[w_ix] & aligned_mask) {
318 return true;
319 }
320 len -= aligned_len;
321 off += aligned_len;
322 }
323 return false;
324 }
325
326 template <typename I>
327 inline bool BitSet<I>::testAll(size_t off, size_t len) const {
328 IGA_ASSERT(off >= 0 && off + len <= N,
329 "BitSet::testAll: index out of bounds");
330
331 // check the first word (misaligned mask)
332 auto w_ix = off / BITS_PER_WORD;
333 auto w_off = off % BITS_PER_WORD;
334 auto misaligned_len = std::min<size_t>(BITS_PER_WORD - w_off, len);
335 auto misaligned_mask = makeMask(misaligned_len);
336 if (((words[w_ix] >> w_off) & misaligned_mask) != misaligned_mask) {
337 return false;
338 }
339
340 // check successive words (all aligned now)
341 len -= misaligned_len;
342 off += misaligned_len;
343 while (len > 0) {
344 w_ix++; // next word
345
346 auto aligned_len = len >= 32 ? 32 : len % BITS_PER_WORD; // last will be <32
347 auto aligned_mask = makeMask(aligned_len);
348 if ((words[w_ix] & aligned_mask) != aligned_mask) {
349 return false;
350 }
351 len -= aligned_len;
352 off += aligned_len;
353 }
354 return true;
355 }
356
357 template <typename I> bool BitSet<I>::operator==(const BitSet<I> &bs) const {
358 // do we have to worry about the ragged padding.
359 // e.g. given 32b words if the bitset is 31 bits long, we have to
360 // worry about the trailing bit
361 if (N != bs.N) { // We should not compare BitSets of different size
362 return false;
363 }
364 return memcmp(&words[0], &bs.words[0], wordsSize * sizeof(I)) == 0;
365 }
366
367 // C++20 gets std::popcount
368 // until then, provide a couple instances of likely uses and call it a day
369 static inline size_t bsPopcount(uint32_t i) {
370 // this should end up as __popcountsi2
371 return std::bitset<32>(i).count();
372 }
373 static inline size_t bsPopcount(uint64_t i) {
374 if (sizeof(unsigned long) == 8) {
375 // __popcountti2
376 return std::bitset<64>(i).count();
377 } else {
378 // __popcountsi2; __popcountsi2
379 return bsPopcount((uint32_t)i) + bsPopcount((uint32_t)(i >> 32));
380 }
381 }
382 static inline size_t bsPopcount(uint16_t i) { return bsPopcount((uint32_t)i); }
383
384 template <typename I> inline size_t BitSet<I>::cardinality() const {
385 size_t n = 0;
386 for (size_t i = 0; i < wordsSize; i++) {
387 n += bsPopcount(words[i]);
388 }
389 return n;
390 }
391
392 template <typename I> inline void BitSet<I>::str(std::ostream &os) const {
393 int i = 0;
394 bool first = false;
395 os << "{";
396 while (i < N) {
397 if (test(i)) {
398 if (first)
399 first = false;
400 else
401 os << ",";
402 int start = i + 1;
403 while (i < N && test(i)) {
404 i++;
405 }
406 os << start;
407 if (i != start + 1) {
408 os << "-";
409 os << i + start - 1;
410 }
411 } else {
412 i++;
413 }
414 }
415 os << "}";
416 }
417
418 } // namespace iga
419
420 #endif // _IGA_BITSET_HPP