1 | //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===// |
---|---|

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 | // This file implements the BitVector class. |

10 | // |

11 | //===----------------------------------------------------------------------===// |

12 | |

13 | #ifndef LLVM_ADT_BITVECTOR_H |

14 | #define LLVM_ADT_BITVECTOR_H |

15 | |

16 | #include "llvm/ADT/ArrayRef.h" |

17 | #include "llvm/ADT/DenseMapInfo.h" |

18 | #include "llvm/ADT/iterator_range.h" |

19 | #include "llvm/Support/MathExtras.h" |

20 | #include <algorithm> |

21 | #include <cassert> |

22 | #include <climits> |

23 | #include <cstdint> |

24 | #include <cstdlib> |

25 | #include <cstring> |

26 | #include <utility> |

27 | |

28 | namespace llvm { |

29 | |

30 | /// ForwardIterator for the bits that are set. |

31 | /// Iterators get invalidated when resize / reserve is called. |

32 | template <typename BitVectorT> class const_set_bits_iterator_impl { |

33 | const BitVectorT &Parent; |

34 | int Current = 0; |

35 | |

36 | void advance() { |

37 | assert(Current != -1 && "Trying to advance past end."); |

38 | Current = Parent.find_next(Current); |

39 | } |

40 | |

41 | public: |

42 | const_set_bits_iterator_impl(const BitVectorT &Parent, int Current) |

43 | : Parent(Parent), Current(Current) {} |

44 | explicit const_set_bits_iterator_impl(const BitVectorT &Parent) |

45 | : const_set_bits_iterator_impl(Parent, Parent.find_first()) {} |

46 | const_set_bits_iterator_impl(const const_set_bits_iterator_impl &) = default; |

47 | |

48 | const_set_bits_iterator_impl operator++(int) { |

49 | auto Prev = *this; |

50 | advance(); |

51 | return Prev; |

52 | } |

53 | |

54 | const_set_bits_iterator_impl &operator++() { |

55 | advance(); |

56 | return *this; |

57 | } |

58 | |

59 | unsigned operator*() const { return Current; } |

60 | |

61 | bool operator==(const const_set_bits_iterator_impl &Other) const { |

62 | assert(&Parent == &Other.Parent && |

63 | "Comparing iterators from different BitVectors"); |

64 | return Current == Other.Current; |

65 | } |

66 | |

67 | bool operator!=(const const_set_bits_iterator_impl &Other) const { |

68 | assert(&Parent == &Other.Parent && |

69 | "Comparing iterators from different BitVectors"); |

70 | return Current != Other.Current; |

71 | } |

72 | }; |

73 | |

74 | class BitVector { |

75 | typedef uintptr_t BitWord; |

76 | |

77 | enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; |

78 | |

79 | static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32, |

80 | "Unsupported word size"); |

81 | |

82 | using Storage = SmallVector<BitWord>; |

83 | |

84 | Storage Bits; // Actual bits. |

85 | unsigned Size; // Size of bitvector in bits. |

86 | |

87 | public: |

88 | typedef unsigned size_type; |

89 | |

90 | // Encapsulation of a single bit. |

91 | class reference { |

92 | |

93 | BitWord *WordRef; |

94 | unsigned BitPos; |

95 | |

96 | public: |

97 | reference(BitVector &b, unsigned Idx) { |

98 | WordRef = &b.Bits[Idx / BITWORD_SIZE]; |

99 | BitPos = Idx % BITWORD_SIZE; |

100 | } |

101 | |

102 | reference() = delete; |

103 | reference(const reference&) = default; |

104 | |

105 | reference &operator=(reference t) { |

106 | *this = bool(t); |

107 | return *this; |

108 | } |

109 | |

110 | reference& operator=(bool t) { |

111 | if (t) |

112 | *WordRef |= BitWord(1) << BitPos; |

113 | else |

114 | *WordRef &= ~(BitWord(1) << BitPos); |

115 | return *this; |

116 | } |

117 | |

118 | operator bool() const { |

119 | return ((*WordRef) & (BitWord(1) << BitPos)) != 0; |

120 | } |

121 | }; |

122 | |

123 | typedef const_set_bits_iterator_impl<BitVector> const_set_bits_iterator; |

124 | typedef const_set_bits_iterator set_iterator; |

125 | |

126 | const_set_bits_iterator set_bits_begin() const { |

127 | return const_set_bits_iterator(*this); |

128 | } |

129 | const_set_bits_iterator set_bits_end() const { |

130 | return const_set_bits_iterator(*this, -1); |

131 | } |

132 | iterator_range<const_set_bits_iterator> set_bits() const { |

133 | return make_range(set_bits_begin(), set_bits_end()); |

134 | } |

135 | |

136 | /// BitVector default ctor - Creates an empty bitvector. |

137 | BitVector() : Size(0) {} |

138 | |

139 | /// BitVector ctor - Creates a bitvector of specified number of bits. All |

140 | /// bits are initialized to the specified value. |

141 | explicit BitVector(unsigned s, bool t = false) |

142 | : Bits(NumBitWords(s), 0 - (BitWord)t), Size(s) { |

143 | if (t) |

144 | clear_unused_bits(); |

145 | } |

146 | |

147 | /// empty - Tests whether there are no bits in this bitvector. |

148 | bool empty() const { return Size == 0; } |

149 | |

150 | /// size - Returns the number of bits in this bitvector. |

151 | size_type size() const { return Size; } |

152 | |

153 | /// count - Returns the number of bits which are set. |

154 | size_type count() const { |

155 | unsigned NumBits = 0; |

156 | for (auto Bit : Bits) |

157 | NumBits += countPopulation(Bit); |

158 | return NumBits; |

159 | } |

160 | |

161 | /// any - Returns true if any bit is set. |

162 | bool any() const { |

163 | return any_of(Bits, [](BitWord Bit) { return Bit != 0; }); |

164 | } |

165 | |

166 | /// all - Returns true if all bits are set. |

167 | bool all() const { |

168 | for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i) |

169 | if (Bits[i] != ~BitWord(0)) |

170 | return false; |

171 | |

172 | // If bits remain check that they are ones. The unused bits are always zero. |

173 | if (unsigned Remainder = Size % BITWORD_SIZE) |

174 | return Bits[Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1; |

175 | |

176 | return true; |

177 | } |

178 | |

179 | /// none - Returns true if none of the bits are set. |

180 | bool none() const { |

181 | return !any(); |

182 | } |

183 | |

184 | /// find_first_in - Returns the index of the first set / unset bit, |

185 | /// depending on \p Set, in the range [Begin, End). |

186 | /// Returns -1 if all bits in the range are unset / set. |

187 | int find_first_in(unsigned Begin, unsigned End, bool Set = true) const { |

188 | assert(Begin <= End && End <= Size); |

189 | if (Begin == End) |

190 | return -1; |

191 | |

192 | unsigned FirstWord = Begin / BITWORD_SIZE; |

193 | unsigned LastWord = (End - 1) / BITWORD_SIZE; |

194 | |

195 | // Check subsequent words. |

196 | // The code below is based on search for the first _set_ bit. If |

197 | // we're searching for the first _unset_, we just take the |

198 | // complement of each word before we use it and apply |

199 | // the same method. |

200 | for (unsigned i = FirstWord; i <= LastWord; ++i) { |

201 | BitWord Copy = Bits[i]; |

202 | if (!Set) |

203 | Copy = ~Copy; |

204 | |

205 | if (i == FirstWord) { |

206 | unsigned FirstBit = Begin % BITWORD_SIZE; |

207 | Copy &= maskTrailingZeros<BitWord>(FirstBit); |

208 | } |

209 | |

210 | if (i == LastWord) { |

211 | unsigned LastBit = (End - 1) % BITWORD_SIZE; |

212 | Copy &= maskTrailingOnes<BitWord>(LastBit + 1); |

213 | } |

214 | if (Copy != 0) |

215 | return i * BITWORD_SIZE + countTrailingZeros(Copy); |

216 | } |

217 | return -1; |

218 | } |

219 | |

220 | /// find_last_in - Returns the index of the last set bit in the range |

221 | /// [Begin, End). Returns -1 if all bits in the range are unset. |

222 | int find_last_in(unsigned Begin, unsigned End) const { |

223 | assert(Begin <= End && End <= Size); |

224 | if (Begin == End) |

225 | return -1; |

226 | |

227 | unsigned LastWord = (End - 1) / BITWORD_SIZE; |

228 | unsigned FirstWord = Begin / BITWORD_SIZE; |

229 | |

230 | for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) { |

231 | unsigned CurrentWord = i - 1; |

232 | |

233 | BitWord Copy = Bits[CurrentWord]; |

234 | if (CurrentWord == LastWord) { |

235 | unsigned LastBit = (End - 1) % BITWORD_SIZE; |

236 | Copy &= maskTrailingOnes<BitWord>(LastBit + 1); |

237 | } |

238 | |

239 | if (CurrentWord == FirstWord) { |

240 | unsigned FirstBit = Begin % BITWORD_SIZE; |

241 | Copy &= maskTrailingZeros<BitWord>(FirstBit); |

242 | } |

243 | |

244 | if (Copy != 0) |

245 | return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1; |

246 | } |

247 | |

248 | return -1; |

249 | } |

250 | |

251 | /// find_first_unset_in - Returns the index of the first unset bit in the |

252 | /// range [Begin, End). Returns -1 if all bits in the range are set. |

253 | int find_first_unset_in(unsigned Begin, unsigned End) const { |

254 | return find_first_in(Begin, End, /* Set = */ false); |

255 | } |

256 | |

257 | /// find_last_unset_in - Returns the index of the last unset bit in the |

258 | /// range [Begin, End). Returns -1 if all bits in the range are set. |

259 | int find_last_unset_in(unsigned Begin, unsigned End) const { |

260 | assert(Begin <= End && End <= Size); |

261 | if (Begin == End) |

262 | return -1; |

263 | |

264 | unsigned LastWord = (End - 1) / BITWORD_SIZE; |

265 | unsigned FirstWord = Begin / BITWORD_SIZE; |

266 | |

267 | for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) { |

268 | unsigned CurrentWord = i - 1; |

269 | |

270 | BitWord Copy = Bits[CurrentWord]; |

271 | if (CurrentWord == LastWord) { |

272 | unsigned LastBit = (End - 1) % BITWORD_SIZE; |

273 | Copy |= maskTrailingZeros<BitWord>(LastBit + 1); |

274 | } |

275 | |

276 | if (CurrentWord == FirstWord) { |

277 | unsigned FirstBit = Begin % BITWORD_SIZE; |

278 | Copy |= maskTrailingOnes<BitWord>(FirstBit); |

279 | } |

280 | |

281 | if (Copy != ~BitWord(0)) { |

282 | unsigned Result = |

283 | (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1; |

284 | return Result < Size ? Result : -1; |

285 | } |

286 | } |

287 | return -1; |

288 | } |

289 | |

290 | /// find_first - Returns the index of the first set bit, -1 if none |

291 | /// of the bits are set. |

292 | int find_first() const { return find_first_in(0, Size); } |

293 | |

294 | /// find_last - Returns the index of the last set bit, -1 if none of the bits |

295 | /// are set. |

296 | int find_last() const { return find_last_in(0, Size); } |

297 | |

298 | /// find_next - Returns the index of the next set bit following the |

299 | /// "Prev" bit. Returns -1 if the next set bit is not found. |

300 | int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); } |

301 | |

302 | /// find_prev - Returns the index of the first set bit that precedes the |

303 | /// the bit at \p PriorTo. Returns -1 if all previous bits are unset. |

304 | int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); } |

305 | |

306 | /// find_first_unset - Returns the index of the first unset bit, -1 if all |

307 | /// of the bits are set. |

308 | int find_first_unset() const { return find_first_unset_in(0, Size); } |

309 | |

310 | /// find_next_unset - Returns the index of the next unset bit following the |

311 | /// "Prev" bit. Returns -1 if all remaining bits are set. |

312 | int find_next_unset(unsigned Prev) const { |

313 | return find_first_unset_in(Prev + 1, Size); |

314 | } |

315 | |

316 | /// find_last_unset - Returns the index of the last unset bit, -1 if all of |

317 | /// the bits are set. |

318 | int find_last_unset() const { return find_last_unset_in(0, Size); } |

319 | |

320 | /// find_prev_unset - Returns the index of the first unset bit that precedes |

321 | /// the bit at \p PriorTo. Returns -1 if all previous bits are set. |

322 | int find_prev_unset(unsigned PriorTo) { |

323 | return find_last_unset_in(0, PriorTo); |

324 | } |

325 | |

326 | /// clear - Removes all bits from the bitvector. |

327 | void clear() { |

328 | Size = 0; |

329 | Bits.clear(); |

330 | } |

331 | |

332 | /// resize - Grow or shrink the bitvector. |

333 | void resize(unsigned N, bool t = false) { |

334 | set_unused_bits(t); |

335 | Size = N; |

336 | Bits.resize(NumBitWords(N), 0 - BitWord(t)); |

337 | clear_unused_bits(); |

338 | } |

339 | |

340 | void reserve(unsigned N) { Bits.reserve(NumBitWords(N)); } |

341 | |

342 | // Set, reset, flip |

343 | BitVector &set() { |

344 | init_words(true); |

345 | clear_unused_bits(); |

346 | return *this; |

347 | } |

348 | |

349 | BitVector &set(unsigned Idx) { |

350 | assert(Idx < Size && "access in bound"); |

351 | Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE); |

352 | return *this; |

353 | } |

354 | |

355 | /// set - Efficiently set a range of bits in [I, E) |

356 | BitVector &set(unsigned I, unsigned E) { |

357 | assert(I <= E && "Attempted to set backwards range!"); |

358 | assert(E <= size() && "Attempted to set out-of-bounds range!"); |

359 | |

360 | if (I == E) return *this; |

361 | |

362 | if (I / BITWORD_SIZE == E / BITWORD_SIZE) { |

363 | BitWord EMask = BitWord(1) << (E % BITWORD_SIZE); |

364 | BitWord IMask = BitWord(1) << (I % BITWORD_SIZE); |

365 | BitWord Mask = EMask - IMask; |

366 | Bits[I / BITWORD_SIZE] |= Mask; |

367 | return *this; |

368 | } |

369 | |

370 | BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE); |

371 | Bits[I / BITWORD_SIZE] |= PrefixMask; |

372 | I = alignTo(I, BITWORD_SIZE); |

373 | |

374 | for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) |

375 | Bits[I / BITWORD_SIZE] = ~BitWord(0); |

376 | |

377 | BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1; |

378 | if (I < E) |

379 | Bits[I / BITWORD_SIZE] |= PostfixMask; |

380 | |

381 | return *this; |

382 | } |

383 | |

384 | BitVector &reset() { |

385 | init_words(false); |

386 | return *this; |

387 | } |

388 | |

389 | BitVector &reset(unsigned Idx) { |

390 | Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE)); |

391 | return *this; |

392 | } |

393 | |

394 | /// reset - Efficiently reset a range of bits in [I, E) |

395 | BitVector &reset(unsigned I, unsigned E) { |

396 | assert(I <= E && "Attempted to reset backwards range!"); |

397 | assert(E <= size() && "Attempted to reset out-of-bounds range!"); |

398 | |

399 | if (I == E) return *this; |

400 | |

401 | if (I / BITWORD_SIZE == E / BITWORD_SIZE) { |

402 | BitWord EMask = BitWord(1) << (E % BITWORD_SIZE); |

403 | BitWord IMask = BitWord(1) << (I % BITWORD_SIZE); |

404 | BitWord Mask = EMask - IMask; |

405 | Bits[I / BITWORD_SIZE] &= ~Mask; |

406 | return *this; |

407 | } |

408 | |

409 | BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE); |

410 | Bits[I / BITWORD_SIZE] &= ~PrefixMask; |

411 | I = alignTo(I, BITWORD_SIZE); |

412 | |

413 | for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) |

414 | Bits[I / BITWORD_SIZE] = BitWord(0); |

415 | |

416 | BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1; |

417 | if (I < E) |

418 | Bits[I / BITWORD_SIZE] &= ~PostfixMask; |

419 | |

420 | return *this; |

421 | } |

422 | |

423 | BitVector &flip() { |

424 | for (auto &Bit : Bits) |

425 | Bit = ~Bit; |

426 | clear_unused_bits(); |

427 | return *this; |

428 | } |

429 | |

430 | BitVector &flip(unsigned Idx) { |

431 | Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE); |

432 | return *this; |

433 | } |

434 | |

435 | // Indexing. |

436 | reference operator[](unsigned Idx) { |

437 | assert (Idx < Size && "Out-of-bounds Bit access."); |

438 | return reference(*this, Idx); |

439 | } |

440 | |

441 | bool operator[](unsigned Idx) const { |

442 | assert (Idx < Size && "Out-of-bounds Bit access."); |

443 | BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE); |

444 | return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; |

445 | } |

446 | |

447 | bool test(unsigned Idx) const { |

448 | return (*this)[Idx]; |

449 | } |

450 | |

451 | // Push single bit to end of vector. |

452 | void push_back(bool Val) { |

453 | unsigned OldSize = Size; |

454 | unsigned NewSize = Size + 1; |

455 | |

456 | // Resize, which will insert zeros. |

457 | // If we already fit then the unused bits will be already zero. |

458 | if (NewSize > getBitCapacity()) |

459 | resize(NewSize, false); |

460 | else |

461 | Size = NewSize; |

462 | |

463 | // If true, set single bit. |

464 | if (Val) |

465 | set(OldSize); |

466 | } |

467 | |

468 | /// Test if any common bits are set. |

469 | bool anyCommon(const BitVector &RHS) const { |

470 | unsigned ThisWords = Bits.size(); |

471 | unsigned RHSWords = RHS.Bits.size(); |

472 | for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) |

473 | if (Bits[i] & RHS.Bits[i]) |

474 | return true; |

475 | return false; |

476 | } |

477 | |

478 | // Comparison operators. |

479 | bool operator==(const BitVector &RHS) const { |

480 | if (size() != RHS.size()) |

481 | return false; |

482 | unsigned NumWords = Bits.size(); |

483 | return std::equal(Bits.begin(), Bits.begin() + NumWords, RHS.Bits.begin()); |

484 | } |

485 | |

486 | bool operator!=(const BitVector &RHS) const { return !(*this == RHS); } |

487 | |

488 | /// Intersection, union, disjoint union. |

489 | BitVector &operator&=(const BitVector &RHS) { |

490 | unsigned ThisWords = Bits.size(); |

491 | unsigned RHSWords = RHS.Bits.size(); |

492 | unsigned i; |

493 | for (i = 0; i != std::min(ThisWords, RHSWords); ++i) |

494 | Bits[i] &= RHS.Bits[i]; |

495 | |

496 | // Any bits that are just in this bitvector become zero, because they aren't |

497 | // in the RHS bit vector. Any words only in RHS are ignored because they |

498 | // are already zero in the LHS. |

499 | for (; i != ThisWords; ++i) |

500 | Bits[i] = 0; |

501 | |

502 | return *this; |

503 | } |

504 | |

505 | /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. |

506 | BitVector &reset(const BitVector &RHS) { |

507 | unsigned ThisWords = Bits.size(); |

508 | unsigned RHSWords = RHS.Bits.size(); |

509 | for (unsigned i = 0; i != std::min(ThisWords, RHSWords); ++i) |

510 | Bits[i] &= ~RHS.Bits[i]; |

511 | return *this; |

512 | } |

513 | |

514 | /// test - Check if (This - RHS) is zero. |

515 | /// This is the same as reset(RHS) and any(). |

516 | bool test(const BitVector &RHS) const { |

517 | unsigned ThisWords = Bits.size(); |

518 | unsigned RHSWords = RHS.Bits.size(); |

519 | unsigned i; |

520 | for (i = 0; i != std::min(ThisWords, RHSWords); ++i) |

521 | if ((Bits[i] & ~RHS.Bits[i]) != 0) |

522 | return true; |

523 | |

524 | for (; i != ThisWords ; ++i) |

525 | if (Bits[i] != 0) |

526 | return true; |

527 | |

528 | return false; |

529 | } |

530 | |

531 | template <class F, class... ArgTys> |

532 | static BitVector &apply(F &&f, BitVector &Out, BitVector const &Arg, |

533 | ArgTys const &...Args) { |

534 | assert(llvm::all_of( |

535 | std::initializer_list<unsigned>{Args.size()...}, |

536 | [&Arg](auto const &BV) { return Arg.size() == BV; }) && |

537 | "consistent sizes"); |

538 | Out.resize(Arg.size()); |

539 | for (size_t i = 0, e = Arg.Bits.size(); i != e; ++i) |

540 | Out.Bits[i] = f(Arg.Bits[i], Args.Bits[i]...); |

541 | Out.clear_unused_bits(); |

542 | return Out; |

543 | } |

544 | |

545 | BitVector &operator|=(const BitVector &RHS) { |

546 | if (size() < RHS.size()) |

547 | resize(RHS.size()); |

548 | for (size_t i = 0, e = RHS.Bits.size(); i != e; ++i) |

549 | Bits[i] |= RHS.Bits[i]; |

550 | return *this; |

551 | } |

552 | |

553 | BitVector &operator^=(const BitVector &RHS) { |

554 | if (size() < RHS.size()) |

555 | resize(RHS.size()); |

556 | for (size_t i = 0, e = RHS.Bits.size(); i != e; ++i) |

557 | Bits[i] ^= RHS.Bits[i]; |

558 | return *this; |

559 | } |

560 | |

561 | BitVector &operator>>=(unsigned N) { |

562 | assert(N <= Size); |

563 | if (LLVM_UNLIKELY(empty() || N == 0)) |

564 | return *this; |

565 | |

566 | unsigned NumWords = Bits.size(); |

567 | assert(NumWords >= 1); |

568 | |

569 | wordShr(N / BITWORD_SIZE); |

570 | |

571 | unsigned BitDistance = N % BITWORD_SIZE; |

572 | if (BitDistance == 0) |

573 | return *this; |

574 | |

575 | // When the shift size is not a multiple of the word size, then we have |

576 | // a tricky situation where each word in succession needs to extract some |

577 | // of the bits from the next word and or them into this word while |

578 | // shifting this word to make room for the new bits. This has to be done |

579 | // for every word in the array. |

580 | |

581 | // Since we're shifting each word right, some bits will fall off the end |

582 | // of each word to the right, and empty space will be created on the left. |

583 | // The final word in the array will lose bits permanently, so starting at |

584 | // the beginning, work forwards shifting each word to the right, and |

585 | // OR'ing in the bits from the end of the next word to the beginning of |

586 | // the current word. |

587 | |

588 | // Example: |

589 | // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right |

590 | // by 4 bits. |

591 | // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD |

592 | // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD |

593 | // Step 3: Word[1] >>= 4 ; 0x0EEFF001 |

594 | // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001 |

595 | // Step 5: Word[2] >>= 4 ; 0x02334455 |

596 | // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 } |

597 | const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance); |

598 | const unsigned LSH = BITWORD_SIZE - BitDistance; |

599 | |

600 | for (unsigned I = 0; I < NumWords - 1; ++I) { |

601 | Bits[I] >>= BitDistance; |

602 | Bits[I] |= (Bits[I + 1] & Mask) << LSH; |

603 | } |

604 | |

605 | Bits[NumWords - 1] >>= BitDistance; |

606 | |

607 | return *this; |

608 | } |

609 | |

610 | BitVector &operator<<=(unsigned N) { |

611 | assert(N <= Size); |

612 | if (LLVM_UNLIKELY(empty() || N == 0)) |

613 | return *this; |

614 | |

615 | unsigned NumWords = Bits.size(); |

616 | assert(NumWords >= 1); |

617 | |

618 | wordShl(N / BITWORD_SIZE); |

619 | |

620 | unsigned BitDistance = N % BITWORD_SIZE; |

621 | if (BitDistance == 0) |

622 | return *this; |

623 | |

624 | // When the shift size is not a multiple of the word size, then we have |

625 | // a tricky situation where each word in succession needs to extract some |

626 | // of the bits from the previous word and or them into this word while |

627 | // shifting this word to make room for the new bits. This has to be done |

628 | // for every word in the array. This is similar to the algorithm outlined |

629 | // in operator>>=, but backwards. |

630 | |

631 | // Since we're shifting each word left, some bits will fall off the end |

632 | // of each word to the left, and empty space will be created on the right. |

633 | // The first word in the array will lose bits permanently, so starting at |

634 | // the end, work backwards shifting each word to the left, and OR'ing |

635 | // in the bits from the end of the next word to the beginning of the |

636 | // current word. |

637 | |

638 | // Example: |

639 | // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left |

640 | // by 4 bits. |

641 | // Step 1: Word[2] <<= 4 ; 0x23344550 |

642 | // Step 2: Word[2] |= 0x0000000E ; 0x2334455E |

643 | // Step 3: Word[1] <<= 4 ; 0xEFF00110 |

644 | // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A |

645 | // Step 5: Word[0] <<= 4 ; 0xABBCCDD0 |

646 | // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E } |

647 | const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance); |

648 | const unsigned RSH = BITWORD_SIZE - BitDistance; |

649 | |

650 | for (int I = NumWords - 1; I > 0; --I) { |

651 | Bits[I] <<= BitDistance; |

652 | Bits[I] |= (Bits[I - 1] & Mask) >> RSH; |

653 | } |

654 | Bits[0] <<= BitDistance; |

655 | clear_unused_bits(); |

656 | |

657 | return *this; |

658 | } |

659 | |

660 | void swap(BitVector &RHS) { |

661 | std::swap(Bits, RHS.Bits); |

662 | std::swap(Size, RHS.Size); |

663 | } |

664 | |

665 | void invalid() { |

666 | assert(!Size && Bits.empty()); |

667 | Size = (unsigned)-1; |

668 | } |

669 | bool isInvalid() const { return Size == (unsigned)-1; } |

670 | |

671 | ArrayRef<BitWord> getData() const { return {&Bits[0], Bits.size()}; } |

672 | |

673 | //===--------------------------------------------------------------------===// |

674 | // Portable bit mask operations. |

675 | //===--------------------------------------------------------------------===// |

676 | // |

677 | // These methods all operate on arrays of uint32_t, each holding 32 bits. The |

678 | // fixed word size makes it easier to work with literal bit vector constants |

679 | // in portable code. |

680 | // |

681 | // The LSB in each word is the lowest numbered bit. The size of a portable |

682 | // bit mask is always a whole multiple of 32 bits. If no bit mask size is |

683 | // given, the bit mask is assumed to cover the entire BitVector. |

684 | |

685 | /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. |

686 | /// This computes "*this |= Mask". |

687 | void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |

688 | applyMask<true, false>(Mask, MaskWords); |

689 | } |

690 | |

691 | /// clearBitsInMask - Clear any bits in this vector that are set in Mask. |

692 | /// Don't resize. This computes "*this &= ~Mask". |

693 | void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |

694 | applyMask<false, false>(Mask, MaskWords); |

695 | } |

696 | |

697 | /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. |

698 | /// Don't resize. This computes "*this |= ~Mask". |

699 | void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |

700 | applyMask<true, true>(Mask, MaskWords); |

701 | } |

702 | |

703 | /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. |

704 | /// Don't resize. This computes "*this &= Mask". |

705 | void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |

706 | applyMask<false, true>(Mask, MaskWords); |

707 | } |

708 | |

709 | private: |

710 | /// Perform a logical left shift of \p Count words by moving everything |

711 | /// \p Count words to the right in memory. |

712 | /// |

713 | /// While confusing, words are stored from least significant at Bits[0] to |

714 | /// most significant at Bits[NumWords-1]. A logical shift left, however, |

715 | /// moves the current least significant bit to a higher logical index, and |

716 | /// fills the previous least significant bits with 0. Thus, we actually |

717 | /// need to move the bytes of the memory to the right, not to the left. |

718 | /// Example: |

719 | /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000] |

720 | /// represents a BitVector where 0xBBBBAAAA contain the least significant |

721 | /// bits. So if we want to shift the BitVector left by 2 words, we need |

722 | /// to turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a |

723 | /// memmove which moves right, not left. |

724 | void wordShl(uint32_t Count) { |

725 | if (Count == 0) |

726 | return; |

727 | |

728 | uint32_t NumWords = Bits.size(); |

729 | |

730 | // Since we always move Word-sized chunks of data with src and dest both |

731 | // aligned to a word-boundary, we don't need to worry about endianness |

732 | // here. |

733 | std::copy(Bits.begin(), Bits.begin() + NumWords - Count, |

734 | Bits.begin() + Count); |

735 | std::fill(Bits.begin(), Bits.begin() + Count, 0); |

736 | clear_unused_bits(); |

737 | } |

738 | |

739 | /// Perform a logical right shift of \p Count words by moving those |

740 | /// words to the left in memory. See wordShl for more information. |

741 | /// |

742 | void wordShr(uint32_t Count) { |

743 | if (Count == 0) |

744 | return; |

745 | |

746 | uint32_t NumWords = Bits.size(); |

747 | |

748 | std::copy(Bits.begin() + Count, Bits.begin() + NumWords, Bits.begin()); |

749 | std::fill(Bits.begin() + NumWords - Count, Bits.begin() + NumWords, 0); |

750 | } |

751 | |

752 | int next_unset_in_word(int WordIndex, BitWord Word) const { |

753 | unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word); |

754 | return Result < size() ? Result : -1; |

755 | } |

756 | |

757 | unsigned NumBitWords(unsigned S) const { |

758 | return (S + BITWORD_SIZE-1) / BITWORD_SIZE; |

759 | } |

760 | |

761 | // Set the unused bits in the high words. |

762 | void set_unused_bits(bool t = true) { |

763 | // Then set any stray high bits of the last used word. |

764 | if (unsigned ExtraBits = Size % BITWORD_SIZE) { |

765 | BitWord ExtraBitMask = ~BitWord(0) << ExtraBits; |

766 | if (t) |

767 | Bits.back() |= ExtraBitMask; |

768 | else |

769 | Bits.back() &= ~ExtraBitMask; |

770 | } |

771 | } |

772 | |

773 | // Clear the unused bits in the high words. |

774 | void clear_unused_bits() { |

775 | set_unused_bits(false); |

776 | } |

777 | |

778 | void init_words(bool t) { |

779 | std::fill(Bits.begin(), Bits.end(), 0 - (BitWord)t); |

780 | } |

781 | |

782 | template<bool AddBits, bool InvertMask> |

783 | void applyMask(const uint32_t *Mask, unsigned MaskWords) { |

784 | static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size."); |

785 | MaskWords = std::min(MaskWords, (size() + 31) / 32); |

786 | const unsigned Scale = BITWORD_SIZE / 32; |

787 | unsigned i; |

788 | for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { |

789 | BitWord BW = Bits[i]; |

790 | // This inner loop should unroll completely when BITWORD_SIZE > 32. |

791 | for (unsigned b = 0; b != BITWORD_SIZE; b += 32) { |

792 | uint32_t M = *Mask++; |

793 | if (InvertMask) M = ~M; |

794 | if (AddBits) BW |= BitWord(M) << b; |

795 | else BW &= ~(BitWord(M) << b); |

796 | } |

797 | Bits[i] = BW; |

798 | } |

799 | for (unsigned b = 0; MaskWords; b += 32, --MaskWords) { |

800 | uint32_t M = *Mask++; |

801 | if (InvertMask) M = ~M; |

802 | if (AddBits) Bits[i] |= BitWord(M) << b; |

803 | else Bits[i] &= ~(BitWord(M) << b); |

804 | } |

805 | if (AddBits) |

806 | clear_unused_bits(); |

807 | } |

808 | |

809 | public: |

810 | /// Return the size (in bytes) of the bit vector. |

811 | size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); } |

812 | size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; } |

813 | }; |

814 | |

815 | inline size_t capacity_in_bytes(const BitVector &X) { |

816 | return X.getMemorySize(); |

817 | } |

818 | |

819 | template <> struct DenseMapInfo<BitVector> { |

820 | static inline BitVector getEmptyKey() { return {}; } |

821 | static inline BitVector getTombstoneKey() { |

822 | BitVector V; |

823 | V.invalid(); |

824 | return V; |

825 | } |

826 | static unsigned getHashValue(const BitVector &V) { |

827 | return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue( |

828 | std::make_pair(V.size(), V.getData())); |

829 | } |

830 | static bool isEqual(const BitVector &LHS, const BitVector &RHS) { |

831 | if (LHS.isInvalid() || RHS.isInvalid()) |

832 | return LHS.isInvalid() == RHS.isInvalid(); |

833 | return LHS == RHS; |

834 | } |

835 | }; |

836 | } // end namespace llvm |

837 | |

838 | namespace std { |

839 | /// Implement std::swap in terms of BitVector swap. |

840 | inline void swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { LHS.swap(RHS); } |

841 | } // end namespace std |

842 | |

843 | #endif // LLVM_ADT_BITVECTOR_H |

844 |