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 | /// \file |

10 | /// This file implements the BitVector class. |

11 | /// |

12 | //===----------------------------------------------------------------------===// |

13 | |

14 | #ifndef LLVM_ADT_BITVECTOR_H |

15 | #define LLVM_ADT_BITVECTOR_H |

16 | |

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

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

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

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

21 | #include <algorithm> |

22 | #include <cassert> |

23 | #include <climits> |

24 | #include <cstdint> |

25 | #include <cstdlib> |

26 | #include <cstring> |

27 | #include <iterator> |

28 | #include <utility> |

29 | |

30 | namespace llvm { |

31 | |

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

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

34 | template <typename BitVectorT> class const_set_bits_iterator_impl { |

35 | const BitVectorT &Parent; |

36 | int Current = 0; |

37 | |

38 | void advance() { |

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

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

41 | } |

42 | |

43 | public: |

44 | using iterator_category = std::forward_iterator_tag; |

45 | using difference_type = std::ptrdiff_t; |

46 | using value_type = int; |

47 | using pointer = value_type*; |

48 | using reference = value_type&; |

49 | |

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

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

52 | explicit const_set_bits_iterator_impl(const BitVectorT &Parent) |

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

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

55 | |

56 | const_set_bits_iterator_impl operator++(int) { |

57 | auto Prev = *this; |

58 | advance(); |

59 | return Prev; |

60 | } |

61 | |

62 | const_set_bits_iterator_impl &operator++() { |

63 | advance(); |

64 | return *this; |

65 | } |

66 | |

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

68 | |

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

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

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

72 | return Current == Other.Current; |

73 | } |

74 | |

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

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

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

78 | return Current != Other.Current; |

79 | } |

80 | }; |

81 | |

82 | class BitVector { |

83 | typedef uintptr_t BitWord; |

84 | |

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

86 | |

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

88 | "Unsupported word size"); |

89 | |

90 | using Storage = SmallVector<BitWord>; |

91 | |

92 | Storage Bits; // Actual bits. |

93 | unsigned Size = 0; // Size of bitvector in bits. |

94 | |

95 | public: |

96 | using size_type = unsigned; |

97 | |

98 | // Encapsulation of a single bit. |

99 | class reference { |

100 | |

101 | BitWord *WordRef; |

102 | unsigned BitPos; |

103 | |

104 | public: |

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

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

107 | BitPos = Idx % BITWORD_SIZE; |

108 | } |

109 | |

110 | reference() = delete; |

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

112 | |

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

114 | *this = bool(t); |

115 | return *this; |

116 | } |

117 | |

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

119 | if (t) |

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

121 | else |

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

123 | return *this; |

124 | } |

125 | |

126 | operator bool() const { |

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

128 | } |

129 | }; |

130 | |

131 | typedef const_set_bits_iterator_impl<BitVector> const_set_bits_iterator; |

132 | typedef const_set_bits_iterator set_iterator; |

133 | |

134 | const_set_bits_iterator set_bits_begin() const { |

135 | return const_set_bits_iterator(*this); |

136 | } |

137 | const_set_bits_iterator set_bits_end() const { |

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

139 | } |

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

141 | return make_range(x: set_bits_begin(), y: set_bits_end()); |

142 | } |

143 | |

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

145 | BitVector() = default; |

146 | |

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

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

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

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

151 | if (t) |

152 | clear_unused_bits(); |

153 | } |

154 | |

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

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

157 | |

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

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

160 | |

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

162 | size_type count() const { |

163 | unsigned NumBits = 0; |

164 | for (auto Bit : Bits) |

165 | NumBits += llvm::popcount(Value: Bit); |

166 | return NumBits; |

167 | } |

168 | |

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

170 | bool any() const { |

171 | return any_of(Range: Bits, P: [](BitWord Bit) { return Bit != 0; }); |

172 | } |

173 | |

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

175 | bool all() const { |

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

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

178 | return false; |

179 | |

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

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

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

183 | |

184 | return true; |

185 | } |

186 | |

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

188 | bool none() const { |

189 | return !any(); |

190 | } |

191 | |

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

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

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

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

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

197 | if (Begin == End) |

198 | return -1; |

199 | |

200 | unsigned FirstWord = Begin / BITWORD_SIZE; |

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

202 | |

203 | // Check subsequent words. |

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

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

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

207 | // the same method. |

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

209 | BitWord Copy = Bits[i]; |

210 | if (!Set) |

211 | Copy = ~Copy; |

212 | |

213 | if (i == FirstWord) { |

214 | unsigned FirstBit = Begin % BITWORD_SIZE; |

215 | Copy &= maskTrailingZeros<BitWord>(N: FirstBit); |

216 | } |

217 | |

218 | if (i == LastWord) { |

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

220 | Copy &= maskTrailingOnes<BitWord>(N: LastBit + 1); |

221 | } |

222 | if (Copy != 0) |

223 | return i * BITWORD_SIZE + llvm::countr_zero(Val: Copy); |

224 | } |

225 | return -1; |

226 | } |

227 | |

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

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

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

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

232 | if (Begin == End) |

233 | return -1; |

234 | |

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

236 | unsigned FirstWord = Begin / BITWORD_SIZE; |

237 | |

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

239 | unsigned CurrentWord = i - 1; |

240 | |

241 | BitWord Copy = Bits[CurrentWord]; |

242 | if (CurrentWord == LastWord) { |

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

244 | Copy &= maskTrailingOnes<BitWord>(N: LastBit + 1); |

245 | } |

246 | |

247 | if (CurrentWord == FirstWord) { |

248 | unsigned FirstBit = Begin % BITWORD_SIZE; |

249 | Copy &= maskTrailingZeros<BitWord>(N: FirstBit); |

250 | } |

251 | |

252 | if (Copy != 0) |

253 | return (CurrentWord + 1) * BITWORD_SIZE - llvm::countl_zero(Val: Copy) - 1; |

254 | } |

255 | |

256 | return -1; |

257 | } |

258 | |

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

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

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

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

263 | } |

264 | |

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

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

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

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

269 | if (Begin == End) |

270 | return -1; |

271 | |

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

273 | unsigned FirstWord = Begin / BITWORD_SIZE; |

274 | |

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

276 | unsigned CurrentWord = i - 1; |

277 | |

278 | BitWord Copy = Bits[CurrentWord]; |

279 | if (CurrentWord == LastWord) { |

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

281 | Copy |= maskTrailingZeros<BitWord>(N: LastBit + 1); |

282 | } |

283 | |

284 | if (CurrentWord == FirstWord) { |

285 | unsigned FirstBit = Begin % BITWORD_SIZE; |

286 | Copy |= maskTrailingOnes<BitWord>(N: FirstBit); |

287 | } |

288 | |

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

290 | unsigned Result = |

291 | (CurrentWord + 1) * BITWORD_SIZE - llvm::countl_one(Value: Copy) - 1; |

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

293 | } |

294 | } |

295 | return -1; |

296 | } |

297 | |

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

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

300 | int find_first() const { return find_first_in(Begin: 0, End: Size); } |

301 | |

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

303 | /// are set. |

304 | int find_last() const { return find_last_in(Begin: 0, End: Size); } |

305 | |

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

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

308 | int find_next(unsigned Prev) const { return find_first_in(Begin: Prev + 1, End: Size); } |

309 | |

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

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

312 | int find_prev(unsigned PriorTo) const { return find_last_in(Begin: 0, End: PriorTo); } |

313 | |

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

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

316 | int find_first_unset() const { return find_first_unset_in(Begin: 0, End: Size); } |

317 | |

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

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

320 | int find_next_unset(unsigned Prev) const { |

321 | return find_first_unset_in(Begin: Prev + 1, End: Size); |

322 | } |

323 | |

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

325 | /// the bits are set. |

326 | int find_last_unset() const { return find_last_unset_in(Begin: 0, End: Size); } |

327 | |

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

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

330 | int find_prev_unset(unsigned PriorTo) { |

331 | return find_last_unset_in(Begin: 0, End: PriorTo); |

332 | } |

333 | |

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

335 | void clear() { |

336 | Size = 0; |

337 | Bits.clear(); |

338 | } |

339 | |

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

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

342 | set_unused_bits(t); |

343 | Size = N; |

344 | Bits.resize(N: NumBitWords(S: N), NV: 0 - BitWord(t)); |

345 | clear_unused_bits(); |

346 | } |

347 | |

348 | void reserve(unsigned N) { Bits.reserve(N: NumBitWords(S: N)); } |

349 | |

350 | // Set, reset, flip |

351 | BitVector &set() { |

352 | init_words(t: true); |

353 | clear_unused_bits(); |

354 | return *this; |

355 | } |

356 | |

357 | BitVector &set(unsigned Idx) { |

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

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

360 | return *this; |

361 | } |

362 | |

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

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

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

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

367 | |

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

369 | |

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

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

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

373 | BitWord Mask = EMask - IMask; |

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

375 | return *this; |

376 | } |

377 | |

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

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

380 | I = alignTo(Value: I, Align: BITWORD_SIZE); |

381 | |

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

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

384 | |

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

386 | if (I < E) |

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

388 | |

389 | return *this; |

390 | } |

391 | |

392 | BitVector &reset() { |

393 | init_words(t: false); |

394 | return *this; |

395 | } |

396 | |

397 | BitVector &reset(unsigned Idx) { |

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

399 | return *this; |

400 | } |

401 | |

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

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

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

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

406 | |

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

408 | |

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

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

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

412 | BitWord Mask = EMask - IMask; |

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

414 | return *this; |

415 | } |

416 | |

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

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

419 | I = alignTo(Value: I, Align: BITWORD_SIZE); |

420 | |

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

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

423 | |

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

425 | if (I < E) |

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

427 | |

428 | return *this; |

429 | } |

430 | |

431 | BitVector &flip() { |

432 | for (auto &Bit : Bits) |

433 | Bit = ~Bit; |

434 | clear_unused_bits(); |

435 | return *this; |

436 | } |

437 | |

438 | BitVector &flip(unsigned Idx) { |

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

440 | return *this; |

441 | } |

442 | |

443 | // Indexing. |

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

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

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

447 | } |

448 | |

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

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

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

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

453 | } |

454 | |

455 | /// Return the last element in the vector. |

456 | bool back() const { |

457 | assert(!empty() && "Getting last element of empty vector."); |

458 | return (*this)[size() - 1]; |

459 | } |

460 | |

461 | bool test(unsigned Idx) const { |

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

463 | } |

464 | |

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

466 | void push_back(bool Val) { |

467 | unsigned OldSize = Size; |

468 | unsigned NewSize = Size + 1; |

469 | |

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

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

472 | if (NewSize > getBitCapacity()) |

473 | resize(N: NewSize, t: false); |

474 | else |

475 | Size = NewSize; |

476 | |

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

478 | if (Val) |

479 | set(OldSize); |

480 | } |

481 | |

482 | /// Pop one bit from the end of the vector. |

483 | void pop_back() { |

484 | assert(!empty() && "Empty vector has no element to pop."); |

485 | resize(N: size() - 1); |

486 | } |

487 | |

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

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

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

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

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

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

494 | return true; |

495 | return false; |

496 | } |

497 | |

498 | // Comparison operators. |

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

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

501 | return false; |

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

503 | return std::equal(first1: Bits.begin(), last1: Bits.begin() + NumWords, first2: RHS.Bits.begin()); |

504 | } |

505 | |

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

507 | |

508 | /// Intersection, union, disjoint union. |

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

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

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

512 | unsigned i; |

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

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

515 | |

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

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

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

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

520 | Bits[i] = 0; |

521 | |

522 | return *this; |

523 | } |

524 | |

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

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

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

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

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

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

531 | return *this; |

532 | } |

533 | |

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

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

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

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

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

539 | unsigned i; |

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

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

542 | return true; |

543 | |

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

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

546 | return true; |

547 | |

548 | return false; |

549 | } |

550 | |

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

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

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

554 | assert(llvm::all_of( |

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

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

557 | "consistent sizes"); |

558 | Out.resize(N: Arg.size()); |

559 | for (size_type I = 0, E = Arg.Bits.size(); I != E; ++I) |

560 | Out.Bits[I] = f(Arg.Bits[I], Args.Bits[I]...); |

561 | Out.clear_unused_bits(); |

562 | return Out; |

563 | } |

564 | |

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

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

567 | resize(N: RHS.size()); |

568 | for (size_type I = 0, E = RHS.Bits.size(); I != E; ++I) |

569 | Bits[I] |= RHS.Bits[I]; |

570 | return *this; |

571 | } |

572 | |

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

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

575 | resize(N: RHS.size()); |

576 | for (size_type I = 0, E = RHS.Bits.size(); I != E; ++I) |

577 | Bits[I] ^= RHS.Bits[I]; |

578 | return *this; |

579 | } |

580 | |

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

582 | assert(N <= Size); |

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

584 | return *this; |

585 | |

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

587 | assert(NumWords >= 1); |

588 | |

589 | wordShr(Count: N / BITWORD_SIZE); |

590 | |

591 | unsigned BitDistance = N % BITWORD_SIZE; |

592 | if (BitDistance == 0) |

593 | return *this; |

594 | |

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

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

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

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

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

600 | |

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

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

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

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

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

606 | // the current word. |

607 | |

608 | // Example: |

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

610 | // by 4 bits. |

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

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

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

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

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

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

617 | const BitWord Mask = maskTrailingOnes<BitWord>(N: BitDistance); |

618 | const unsigned LSH = BITWORD_SIZE - BitDistance; |

619 | |

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

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

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

623 | } |

624 | |

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

626 | |

627 | return *this; |

628 | } |

629 | |

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

631 | assert(N <= Size); |

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

633 | return *this; |

634 | |

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

636 | assert(NumWords >= 1); |

637 | |

638 | wordShl(Count: N / BITWORD_SIZE); |

639 | |

640 | unsigned BitDistance = N % BITWORD_SIZE; |

641 | if (BitDistance == 0) |

642 | return *this; |

643 | |

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

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

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

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

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

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

650 | |

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

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

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

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

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

656 | // current word. |

657 | |

658 | // Example: |

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

660 | // by 4 bits. |

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

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

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

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

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

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

667 | const BitWord Mask = maskLeadingOnes<BitWord>(N: BitDistance); |

668 | const unsigned RSH = BITWORD_SIZE - BitDistance; |

669 | |

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

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

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

673 | } |

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

675 | clear_unused_bits(); |

676 | |

677 | return *this; |

678 | } |

679 | |

680 | void swap(BitVector &RHS) { |

681 | std::swap(LHS&: Bits, RHS&: RHS.Bits); |

682 | std::swap(a&: Size, b&: RHS.Size); |

683 | } |

684 | |

685 | void invalid() { |

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

687 | Size = (unsigned)-1; |

688 | } |

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

690 | |

691 | ArrayRef<BitWord> getData() const { return {Bits.data(), Bits.size()}; } |

692 | |

693 | //===--------------------------------------------------------------------===// |

694 | // Portable bit mask operations. |

695 | //===--------------------------------------------------------------------===// |

696 | // |

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

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

699 | // in portable code. |

700 | // |

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

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

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

704 | |

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

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

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

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

709 | } |

710 | |

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

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

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

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

715 | } |

716 | |

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

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

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

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

721 | } |

722 | |

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

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

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

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

727 | } |

728 | |

729 | private: |

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

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

732 | /// |

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

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

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

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

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

738 | /// Example: |

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

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

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

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

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

744 | void wordShl(uint32_t Count) { |

745 | if (Count == 0) |

746 | return; |

747 | |

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

749 | |

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

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

752 | // here. |

753 | std::copy(first: Bits.begin(), last: Bits.begin() + NumWords - Count, |

754 | result: Bits.begin() + Count); |

755 | std::fill(first: Bits.begin(), last: Bits.begin() + Count, value: 0); |

756 | clear_unused_bits(); |

757 | } |

758 | |

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

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

761 | /// |

762 | void wordShr(uint32_t Count) { |

763 | if (Count == 0) |

764 | return; |

765 | |

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

767 | |

768 | std::copy(first: Bits.begin() + Count, last: Bits.begin() + NumWords, result: Bits.begin()); |

769 | std::fill(first: Bits.begin() + NumWords - Count, last: Bits.begin() + NumWords, value: 0); |

770 | } |

771 | |

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

773 | unsigned Result = WordIndex * BITWORD_SIZE + llvm::countr_one(Value: Word); |

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

775 | } |

776 | |

777 | unsigned NumBitWords(unsigned S) const { |

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

779 | } |

780 | |

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

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

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

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

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

786 | if (t) |

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

788 | else |

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

790 | } |

791 | } |

792 | |

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

794 | void clear_unused_bits() { |

795 | set_unused_bits(false); |

796 | } |

797 | |

798 | void init_words(bool t) { |

799 | std::fill(first: Bits.begin(), last: Bits.end(), value: 0 - (BitWord)t); |

800 | } |

801 | |

802 | template<bool AddBits, bool InvertMask> |

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

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

805 | MaskWords = std::min(a: MaskWords, b: (size() + 31) / 32); |

806 | const unsigned Scale = BITWORD_SIZE / 32; |

807 | unsigned i; |

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

809 | BitWord BW = Bits[i]; |

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

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

812 | uint32_t M = *Mask++; |

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

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

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

816 | } |

817 | Bits[i] = BW; |

818 | } |

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

820 | uint32_t M = *Mask++; |

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

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

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

824 | } |

825 | if (AddBits) |

826 | clear_unused_bits(); |

827 | } |

828 | |

829 | public: |

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

831 | size_type getMemorySize() const { return Bits.size() * sizeof(BitWord); } |

832 | size_type getBitCapacity() const { return Bits.size() * BITWORD_SIZE; } |

833 | }; |

834 | |

835 | inline BitVector::size_type capacity_in_bytes(const BitVector &X) { |

836 | return X.getMemorySize(); |

837 | } |

838 | |

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

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

841 | static inline BitVector getTombstoneKey() { |

842 | BitVector V; |

843 | V.invalid(); |

844 | return V; |

845 | } |

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

847 | return DenseMapInfo<std::pair<BitVector::size_type, ArrayRef<uintptr_t>>>:: |

848 | getHashValue(PairVal: std::make_pair(x: V.size(), y: V.getData())); |

849 | } |

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

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

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

853 | return LHS == RHS; |

854 | } |

855 | }; |

856 | } // end namespace llvm |

857 | |

858 | namespace std { |

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

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

861 | } // end namespace std |

862 | |

863 | #endif // LLVM_ADT_BITVECTOR_H |

864 |