Movatterモバイル変換

Go to the documentation of this file.

1//===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector --*- 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 defines the SparseBitVector class. See the doxygen comment for

11/// SparseBitVector for more details on the algorithm used.

12///

13//===----------------------------------------------------------------------===//

15#ifndef LLVM_ADT_SPARSEBITVECTOR_H

16#define LLVM_ADT_SPARSEBITVECTOR_H

18#include "llvm/ADT/bit.h"

19#include "llvm/Support/ErrorHandling.h"

20#include "llvm/Support/raw_ostream.h"

21#include <cassert>

22#include <climits>

23#include <cstring>

24#include <iterator>

25#include <list>

27namespacellvm {

29/// SparseBitVector is an implementation of a bitvector that is sparse by only

30/// storing the elements that have non-zero bits set. In order to make this

31/// fast for the most common cases, SparseBitVector is implemented as a linked

32/// list of SparseBitVectorElements. We maintain a pointer to the last

33/// SparseBitVectorElement accessed (in the form of a list iterator), in order

34/// to make multiple in-order test/set constant time after the first one is

35/// executed. Note that using vectors to store SparseBitVectorElement's does

36/// not work out very well because it causes insertion in the middle to take

37/// enormous amounts of time with a large amount of bits. Other structures that

38/// have better worst cases for insertion in the middle (various balanced trees,

39/// etc) do not perform as well in practice as a linked list with this iterator

40/// kept up to date. They are also significantly more memory intensive.

42template <unsigned ElementSize = 128>structSparseBitVectorElement {

43public:

44usingBitWord =unsigned long;

45usingsize_type =unsigned;

46enum {

47BITWORD_SIZE =sizeof(BitWord) * CHAR_BIT,

48BITWORDS_PER_ELEMENT = (ElementSize +BITWORD_SIZE - 1) /BITWORD_SIZE,

49BITS_PER_ELEMENT = ElementSize

50 };

52private:

53// Index of Element in terms of where first bit starts.

54unsigned ElementIndex;

55BitWord Bits[BITWORDS_PER_ELEMENT];

57SparseBitVectorElement() {

58 ElementIndex = ~0U;

59 memset(&Bits[0], 0,sizeof (BitWord) *BITWORDS_PER_ELEMENT);

60 }

62public:

63explicitSparseBitVectorElement(unsignedIdx) {

64 ElementIndex =Idx;

65 memset(&Bits[0], 0,sizeof (BitWord) *BITWORDS_PER_ELEMENT);

66 }

68// Comparison.

69booloperator==(constSparseBitVectorElement &RHS) const{

70if (ElementIndex !=RHS.ElementIndex)

71returnfalse;

72for (unsigned i = 0; i <BITWORDS_PER_ELEMENT; ++i)

73if (Bits[i] !=RHS.Bits[i])

74returnfalse;

75returntrue;

76 }

78booloperator!=(constSparseBitVectorElement &RHS) const{

79return !(*this ==RHS);

80 }

82// Return the bits that make up word Idx in our element.

83BitWord word(unsignedIdx) const{

84assert(Idx <BITWORDS_PER_ELEMENT);

85return Bits[Idx];

86 }

88unsignedindex() const{

89return ElementIndex;

90 }

92boolempty() const{

93for (unsigned i = 0; i <BITWORDS_PER_ELEMENT; ++i)

94if (Bits[i])

95returnfalse;

96returntrue;

97 }

99voidset(unsignedIdx) {

100 Bits[Idx /BITWORD_SIZE] |= 1L << (Idx %BITWORD_SIZE);

101 }

102

103booltest_and_set(unsignedIdx) {

104bool old =test(Idx);

105if (!old) {

106set(Idx);

107returntrue;

108 }

109returnfalse;

110 }

111

112voidreset(unsignedIdx) {

113 Bits[Idx /BITWORD_SIZE] &= ~(1L << (Idx %BITWORD_SIZE));

114 }

115

116booltest(unsignedIdx) const{

117return Bits[Idx /BITWORD_SIZE] & (1L << (Idx %BITWORD_SIZE));

118 }

119

120size_type count() const{

121unsigned NumBits = 0;

122for (unsigned i = 0; i <BITWORDS_PER_ELEMENT; ++i)

123 NumBits +=llvm::popcount(Bits[i]);

124return NumBits;

125 }

126

127 /// find_first - Returns the index of the first set bit.

128intfind_first() const{

129for (unsigned i = 0; i <BITWORDS_PER_ELEMENT; ++i)

130if (Bits[i] != 0)

131return i *BITWORD_SIZE +llvm::countr_zero(Bits[i]);

132llvm_unreachable("Illegal empty element");

133 }

134

135 /// find_last - Returns the index of the last set bit.

136intfind_last() const{

137for (unsignedI = 0;I <BITWORDS_PER_ELEMENT; ++I) {

138unsignedIdx =BITWORDS_PER_ELEMENT -I - 1;

139if (Bits[Idx] != 0)

140returnIdx *BITWORD_SIZE +BITWORD_SIZE -

141llvm::countl_zero(Bits[Idx]) - 1;

142 }

143llvm_unreachable("Illegal empty element");

144 }

145

146 /// find_next - Returns the index of the next set bit starting from the

147 /// "Curr" bit. Returns -1 if the next set bit is not found.

148intfind_next(unsigned Curr) const{

149if (Curr >=BITS_PER_ELEMENT)

150return -1;

151

152unsigned WordPos = Curr /BITWORD_SIZE;

153unsigned BitPos = Curr %BITWORD_SIZE;

154BitWord Copy = Bits[WordPos];

155assert(WordPos <=BITWORDS_PER_ELEMENT

156 &&"Word Position outside of element");

157

158// Mask off previous bits.

159 Copy &= ~0UL << BitPos;

160

161if (Copy != 0)

162return WordPos *BITWORD_SIZE +llvm::countr_zero(Copy);

163

164// Check subsequent words.

165for (unsigned i = WordPos+1; i <BITWORDS_PER_ELEMENT; ++i)

166if (Bits[i] != 0)

167return i *BITWORD_SIZE +llvm::countr_zero(Bits[i]);

168return -1;

169 }

170

171// Union this element with RHS and return true if this one changed.

172boolunionWith(constSparseBitVectorElement &RHS) {

173bool changed =false;

174for (unsigned i = 0; i <BITWORDS_PER_ELEMENT; ++i) {

175BitWord old = changed ? 0 : Bits[i];

176

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

178if (!changed && old != Bits[i])

179 changed =true;

180 }

181return changed;

182 }

183

184// Return true if we have any bits in common with RHS

185boolintersects(constSparseBitVectorElement &RHS) const{

186for (unsigned i = 0; i <BITWORDS_PER_ELEMENT; ++i) {

187if (RHS.Bits[i] & Bits[i])

188returntrue;

189 }

190returnfalse;

191 }

192

193// Intersect this Element with RHS and return true if this one changed.

194// BecameZero is set to true if this element became all-zero bits.

195boolintersectWith(constSparseBitVectorElement &RHS,

196bool &BecameZero) {

197bool changed =false;

198bool allzero =true;

199

200 BecameZero =false;

201for (unsigned i = 0; i <BITWORDS_PER_ELEMENT; ++i) {

202BitWord old = changed ? 0 : Bits[i];

203

204 Bits[i] &=RHS.Bits[i];

205if (Bits[i] != 0)

206 allzero =false;

207

208if (!changed && old != Bits[i])

209 changed =true;

210 }

211 BecameZero = allzero;

212return changed;

213 }

214

215// Intersect this Element with the complement of RHS and return true if this

216// one changed. BecameZero is set to true if this element became all-zero

217// bits.

218boolintersectWithComplement(constSparseBitVectorElement &RHS,

219bool &BecameZero) {

220bool changed =false;

221bool allzero =true;

222

223 BecameZero =false;

224for (unsigned i = 0; i <BITWORDS_PER_ELEMENT; ++i) {

225BitWord old = changed ? 0 : Bits[i];

226

227 Bits[i] &= ~RHS.Bits[i];

228if (Bits[i] != 0)

229 allzero =false;

230

231if (!changed && old != Bits[i])

232 changed =true;

233 }

234 BecameZero = allzero;

235return changed;

236 }

237

238// Three argument version of intersectWithComplement that intersects

239// RHS1 & ~RHS2 into this element

240voidintersectWithComplement(constSparseBitVectorElement &RHS1,

241constSparseBitVectorElement &RHS2,

242bool &BecameZero) {

243bool allzero =true;

244

245 BecameZero =false;

246for (unsigned i = 0; i <BITWORDS_PER_ELEMENT; ++i) {

247 Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];

248if (Bits[i] != 0)

249 allzero =false;

250 }

251 BecameZero = allzero;

252 }

253};

254

255template <unsigned ElementSize = 128>

256classSparseBitVector {

257usingElementList = std::list<SparseBitVectorElement<ElementSize>>;

258usingElementListIter =typename ElementList::iterator;

259usingElementListConstIter =typename ElementList::const_iterator;

260enum {

261 BITWORD_SIZE =SparseBitVectorElement<ElementSize>::BITWORD_SIZE

262 };

263

264 ElementList Elements;

265// Pointer to our current Element. This has no visible effect on the external

266// state of a SparseBitVector, it's just used to improve performance in the

267// common case of testing/modifying bits with similar indices.

268mutable ElementListIter CurrElementIter;

269

270// This is like std::lower_bound, except we do linear searching from the

271// current position.

272 ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const{

273

274// We cache a non-const iterator so we're forced to resort to const_cast to

275// get the begin/end in the case where 'this' is const. To avoid duplication

276// of code with the only difference being whether the const cast is present

277// 'this' is always const in this particular function and we sort out the

278// difference in FindLowerBound and FindLowerBoundConst.

279 ElementListIter Begin =

280const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();

281 ElementListIterEnd =

282const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();

283

284if (Elements.empty()) {

285 CurrElementIter = Begin;

286return CurrElementIter;

287 }

288

289// Make sure our current iterator is valid.

290if (CurrElementIter ==End)

291 --CurrElementIter;

292

293// Search from our current iterator, either backwards or forwards,

294// depending on what element we are looking for.

295 ElementListIter ElementIter = CurrElementIter;

296if (CurrElementIter->index() == ElementIndex) {

297return ElementIter;

298 }elseif (CurrElementIter->index() > ElementIndex) {

299while (ElementIter != Begin

300 && ElementIter->index() > ElementIndex)

301 --ElementIter;

302 }else {

303while (ElementIter !=End &&

304 ElementIter->index() < ElementIndex)

305 ++ElementIter;

306 }

307 CurrElementIter = ElementIter;

308return ElementIter;

309 }

310 ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const{

311return FindLowerBoundImpl(ElementIndex);

312 }

313 ElementListIter FindLowerBound(unsigned ElementIndex) {

314return FindLowerBoundImpl(ElementIndex);

315 }

316

317// Iterator to walk set bits in the bitmap. This iterator is a lot uglier

318// than it would be, in order to be efficient.

319classSparseBitVectorIterator {

320private:

321bool AtEnd;

322

323constSparseBitVector<ElementSize> *BitVector =nullptr;

324

325// Current element inside of bitmap.

326 ElementListConstIter Iter;

327

328// Current bit number inside of our bitmap.

329unsigned BitNumber;

330

331// Current word number inside of our element.

332unsigned WordNumber;

333

334// Current bits from the element.

335typenameSparseBitVectorElement<ElementSize>::BitWord Bits;

336

337// Move our iterator to the first non-zero bit in the bitmap.

338void AdvanceToFirstNonZero() {

339if (AtEnd)

340return;

341if (BitVector->Elements.empty()) {

342 AtEnd =true;

343return;

344 }

345 Iter =BitVector->Elements.begin();

346 BitNumber = Iter->index() * ElementSize;

347unsigned BitPos = Iter->find_first();

348 BitNumber += BitPos;

349 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;

350 Bits = Iter->word(WordNumber);

351 Bits >>= BitPos % BITWORD_SIZE;

352 }

353

354// Move our iterator to the next non-zero bit.

355void AdvanceToNextNonZero() {

356if (AtEnd)

357return;

358

359while (Bits && !(Bits & 1)) {

360 Bits >>= 1;

361 BitNumber += 1;

362 }

363

364// See if we ran out of Bits in this word.

365if (!Bits) {

366int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;

367// If we ran out of set bits in this element, move to next element.

368if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {

369 ++Iter;

370 WordNumber = 0;

371

372// We may run out of elements in the bitmap.

373if (Iter ==BitVector->Elements.end()) {

374 AtEnd =true;

375return;

376 }

377// Set up for next non-zero word in bitmap.

378 BitNumber = Iter->index() * ElementSize;

379 NextSetBitNumber = Iter->find_first();

380 BitNumber += NextSetBitNumber;

381 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;

382 Bits = Iter->word(WordNumber);

383 Bits >>= NextSetBitNumber % BITWORD_SIZE;

384 }else {

385 WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;

386 Bits = Iter->word(WordNumber);

387 Bits >>= NextSetBitNumber % BITWORD_SIZE;

388 BitNumber = Iter->index() * ElementSize;

389 BitNumber += NextSetBitNumber;

390 }

391 }

392 }

393

394public:

395 SparseBitVectorIterator() =default;

396

397 SparseBitVectorIterator(constSparseBitVector<ElementSize> *RHS,

398boolend =false):BitVector(RHS) {

399 Iter =BitVector->Elements.begin();

400 BitNumber = 0;

401 Bits = 0;

402 WordNumber = ~0;

403 AtEnd =end;

404 AdvanceToFirstNonZero();

405 }

406

407// Preincrement.

408inline SparseBitVectorIterator& operator++() {

409 ++BitNumber;

410 Bits >>= 1;

411 AdvanceToNextNonZero();

412return *this;

413 }

414

415// Postincrement.

416inline SparseBitVectorIterator operator++(int) {

417 SparseBitVectorIterator tmp = *this;

418 ++*this;

419return tmp;

420 }

421

422// Return the current set bit number.

423unsignedoperator*() const{

424return BitNumber;

425 }

426

427booloperator==(const SparseBitVectorIterator &RHS) const{

428// If they are both at the end, ignore the rest of the fields.

429if (AtEnd &&RHS.AtEnd)

430returntrue;

431// Otherwise they are the same if they have the same bit number and

432// bitmap.

433return AtEnd ==RHS.AtEnd &&RHS.BitNumber == BitNumber;

434 }

435

436booloperator!=(const SparseBitVectorIterator &RHS) const{

437return !(*this ==RHS);

438 }

439 };

440

441public:

442usingiterator = SparseBitVectorIterator;

443

444SparseBitVector() : Elements(), CurrElementIter(Elements.begin()) {}

445

446SparseBitVector(constSparseBitVector &RHS)

447 : Elements(RHS.Elements), CurrElementIter(Elements.begin()) {}

448SparseBitVector(SparseBitVector &&RHS)

449 : Elements(std::move(RHS.Elements)), CurrElementIter(Elements.begin()) {}

450

451// Clear.

452voidclear() {

453 Elements.clear();

454 }

455

456// Assignment

457SparseBitVector&operator=(constSparseBitVector&RHS) {

458if (this == &RHS)

459return *this;

460

461 Elements =RHS.Elements;

462 CurrElementIter = Elements.begin();

463return *this;

464 }

465SparseBitVector &operator=(SparseBitVector &&RHS) {

466 Elements = std::move(RHS.Elements);

467 CurrElementIter = Elements.begin();

468return *this;

469 }

470

471// Test, Reset, and Set a bit in the bitmap.

472booltest(unsignedIdx) const{

473if (Elements.empty())

474returnfalse;

475

476unsigned ElementIndex =Idx / ElementSize;

477 ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);

478

479// If we can't find an element that is supposed to contain this bit, there

480// is nothing more to do.

481if (ElementIter == Elements.end() ||

482 ElementIter->index() != ElementIndex)

483returnfalse;

484return ElementIter->test(Idx % ElementSize);

485 }

486

487voidreset(unsignedIdx) {

488if (Elements.empty())

489return;

490

491unsigned ElementIndex =Idx / ElementSize;

492 ElementListIter ElementIter = FindLowerBound(ElementIndex);

493

494// If we can't find an element that is supposed to contain this bit, there

495// is nothing more to do.

496if (ElementIter == Elements.end() ||

497 ElementIter->index() != ElementIndex)

498return;

499 ElementIter->reset(Idx % ElementSize);

500

501// When the element is zeroed out, delete it.

502if (ElementIter->empty()) {

503 ++CurrElementIter;

504 Elements.erase(ElementIter);

505 }

506 }

507

508voidset(unsignedIdx) {

509unsigned ElementIndex =Idx / ElementSize;

510 ElementListIter ElementIter;

511if (Elements.empty()) {

512 ElementIter = Elements.emplace(Elements.end(), ElementIndex);

513 }else {

514 ElementIter = FindLowerBound(ElementIndex);

515

516if (ElementIter == Elements.end() ||

517 ElementIter->index() != ElementIndex) {

518// We may have hit the beginning of our SparseBitVector, in which case,

519// we may need to insert right after this element, which requires moving

520// the current iterator forward one, because insert does insert before.

521if (ElementIter != Elements.end() &&

522 ElementIter->index() < ElementIndex)

523 ++ElementIter;

524 ElementIter = Elements.emplace(ElementIter, ElementIndex);

525 }

526 }

527 CurrElementIter = ElementIter;

528

529 ElementIter->set(Idx % ElementSize);

530 }

531

532booltest_and_set(unsignedIdx) {

533bool old =test(Idx);

534if (!old) {

535set(Idx);

536returntrue;

537 }

538returnfalse;

539 }

540

541booloperator!=(constSparseBitVector &RHS) const{

542return !(*this ==RHS);

543 }

544

545booloperator==(constSparseBitVector &RHS) const{

546 ElementListConstIter Iter1 = Elements.begin();

547 ElementListConstIter Iter2 =RHS.Elements.begin();

548

549for (; Iter1 != Elements.end() && Iter2 !=RHS.Elements.end();

550 ++Iter1, ++Iter2) {

551if (*Iter1 != *Iter2)

552returnfalse;

553 }

554return Iter1 == Elements.end() && Iter2 ==RHS.Elements.end();

555 }

556

557// Union our bitmap with the RHS and return true if we changed.

558booloperator|=(constSparseBitVector &RHS) {

559if (this == &RHS)

560returnfalse;

561

562bool changed =false;

563 ElementListIter Iter1 = Elements.begin();

564 ElementListConstIter Iter2 =RHS.Elements.begin();

565

566// If RHS is empty, we are done

567if (RHS.Elements.empty())

568returnfalse;

569

570while (Iter2 !=RHS.Elements.end()) {

571if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {

572 Elements.insert(Iter1, *Iter2);

573 ++Iter2;

574 changed =true;

575 }elseif (Iter1->index() == Iter2->index()) {

576 changed |= Iter1->unionWith(*Iter2);

577 ++Iter1;

578 ++Iter2;

579 }else {

580 ++Iter1;

581 }

582 }

583 CurrElementIter = Elements.begin();

584return changed;

585 }

586

587// Intersect our bitmap with the RHS and return true if ours changed.

588booloperator&=(constSparseBitVector &RHS) {

589if (this == &RHS)

590returnfalse;

591

592bool changed =false;

593 ElementListIter Iter1 = Elements.begin();

594 ElementListConstIter Iter2 =RHS.Elements.begin();

595

596// Check if both bitmaps are empty.

597if (Elements.empty() &&RHS.Elements.empty())

598returnfalse;

599

600// Loop through, intersecting as we go, erasing elements when necessary.

601while (Iter2 !=RHS.Elements.end()) {

602if (Iter1 == Elements.end()) {

603 CurrElementIter = Elements.begin();

604return changed;

605 }

606

607if (Iter1->index() > Iter2->index()) {

608 ++Iter2;

609 }elseif (Iter1->index() == Iter2->index()) {

610bool BecameZero;

611 changed |= Iter1->intersectWith(*Iter2, BecameZero);

612if (BecameZero) {

613 ElementListIter IterTmp = Iter1;

614 ++Iter1;

615 Elements.erase(IterTmp);

616 }else {

617 ++Iter1;

618 }

619 ++Iter2;

620 }else {

621 ElementListIter IterTmp = Iter1;

622 ++Iter1;

623 Elements.erase(IterTmp);

624 changed =true;

625 }

626 }

627if (Iter1 != Elements.end()) {

628 Elements.erase(Iter1, Elements.end());

629 changed =true;

630 }

631 CurrElementIter = Elements.begin();

632return changed;

633 }

634

635// Intersect our bitmap with the complement of the RHS and return true

636// if ours changed.

637boolintersectWithComplement(constSparseBitVector &RHS) {

638if (this == &RHS) {

639if (!empty()) {

640clear();

641returntrue;

642 }

643returnfalse;

644 }

645

646bool changed =false;

647 ElementListIter Iter1 = Elements.begin();

648 ElementListConstIter Iter2 =RHS.Elements.begin();

649

650// If either our bitmap or RHS is empty, we are done

651if (Elements.empty() ||RHS.Elements.empty())

652returnfalse;

653

654// Loop through, intersecting as we go, erasing elements when necessary.

655while (Iter2 !=RHS.Elements.end()) {

656if (Iter1 == Elements.end()) {

657 CurrElementIter = Elements.begin();

658return changed;

659 }

660

661if (Iter1->index() > Iter2->index()) {

662 ++Iter2;

663 }elseif (Iter1->index() == Iter2->index()) {

664bool BecameZero;

665 changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);

666if (BecameZero) {

667 ElementListIter IterTmp = Iter1;

668 ++Iter1;

669 Elements.erase(IterTmp);

670 }else {

671 ++Iter1;

672 }

673 ++Iter2;

674 }else {

675 ++Iter1;

676 }

677 }

678 CurrElementIter = Elements.begin();

679return changed;

680 }

681

682boolintersectWithComplement(constSparseBitVector<ElementSize> *RHS) const{

683returnintersectWithComplement(*RHS);

684 }

685

686// Three argument version of intersectWithComplement.

687// Result of RHS1 & ~RHS2 is stored into this bitmap.

688voidintersectWithComplement(constSparseBitVector<ElementSize> &RHS1,

689constSparseBitVector<ElementSize> &RHS2)

690 {

691if (this == &RHS1) {

692intersectWithComplement(RHS2);

693return;

694 }elseif (this == &RHS2) {

695SparseBitVector RHS2Copy(RHS2);

696intersectWithComplement(RHS1, RHS2Copy);

697return;

698 }

699

700 Elements.clear();

701 CurrElementIter = Elements.begin();

702 ElementListConstIter Iter1 = RHS1.Elements.begin();

703 ElementListConstIter Iter2 = RHS2.Elements.begin();

704

705// If RHS1 is empty, we are done

706// If RHS2 is empty, we still have to copy RHS1

707if (RHS1.Elements.empty())

708return;

709

710// Loop through, intersecting as we go, erasing elements when necessary.

711while (Iter2 != RHS2.Elements.end()) {

712if (Iter1 == RHS1.Elements.end())

713return;

714

715if (Iter1->index() > Iter2->index()) {

716 ++Iter2;

717 }elseif (Iter1->index() == Iter2->index()) {

718bool BecameZero =false;

719 Elements.emplace_back(Iter1->index());

720 Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);

721if (BecameZero)

722 Elements.pop_back();

723 ++Iter1;

724 ++Iter2;

725 }else {

726 Elements.push_back(*Iter1++);

727 }

728 }

729

730// copy the remaining elements

731 std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));

732 }

733

734voidintersectWithComplement(constSparseBitVector<ElementSize> *RHS1,

735constSparseBitVector<ElementSize> *RHS2) {

736intersectWithComplement(*RHS1, *RHS2);

737 }

738

739boolintersects(constSparseBitVector<ElementSize> *RHS) const{

740returnintersects(*RHS);

741 }

742

743// Return true if we share any bits in common with RHS

744boolintersects(constSparseBitVector<ElementSize> &RHS) const{

745 ElementListConstIter Iter1 = Elements.begin();

746 ElementListConstIter Iter2 =RHS.Elements.begin();

747

748// Check if both bitmaps are empty.

749if (Elements.empty() &&RHS.Elements.empty())

750returnfalse;

751

752// Loop through, intersecting stopping when we hit bits in common.

753while (Iter2 !=RHS.Elements.end()) {

754if (Iter1 == Elements.end())

755returnfalse;

756

757if (Iter1->index() > Iter2->index()) {

758 ++Iter2;

759 }elseif (Iter1->index() == Iter2->index()) {

760if (Iter1->intersects(*Iter2))

761returntrue;

762 ++Iter1;

763 ++Iter2;

764 }else {

765 ++Iter1;

766 }

767 }

768returnfalse;

769 }

770

771// Return true iff all bits set in this SparseBitVector are

772// also set in RHS.

773boolcontains(constSparseBitVector<ElementSize> &RHS) const{

774SparseBitVector<ElementSize> Result(*this);

775 Result &=RHS;

776return (Result ==RHS);

777 }

778

779// Return the first set bit in the bitmap. Return -1 if no bits are set.

780intfind_first() const{

781if (Elements.empty())

782return -1;

783constSparseBitVectorElement<ElementSize> &First = *(Elements.begin());

784return (First.index() * ElementSize) +First.find_first();

785 }

786

787// Return the last set bit in the bitmap. Return -1 if no bits are set.

788intfind_last() const{

789if (Elements.empty())

790return -1;

791constSparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());

792return (Last.index() * ElementSize) +Last.find_last();

793 }

794

795// Return true if the SparseBitVector is empty

796boolempty() const{

797return Elements.empty();

798 }

799

800unsignedcount() const{

801unsigned BitCount = 0;

802for (ElementListConstIter Iter = Elements.begin();

803 Iter != Elements.end();

804 ++Iter)

805 BitCount += Iter->count();

806

807return BitCount;

808 }

809

810iterator begin() const{

811returniterator(this);

812 }

813

814iterator end() const{

815returniterator(this,true);

816 }

817};

818

819// Convenience functions to allow Or and And without dereferencing in the user

820// code.

821

822template <unsigned ElementSize>

823inlinebooloperator |=(SparseBitVector<ElementSize> &LHS,

824constSparseBitVector<ElementSize> *RHS) {

825returnLHS |= *RHS;

826}

827

828template <unsigned ElementSize>

829inlinebooloperator |=(SparseBitVector<ElementSize> *LHS,

830constSparseBitVector<ElementSize> &RHS) {

831returnLHS->operator|=(RHS);

832}

833

834template <unsigned ElementSize>

835inlinebooloperator &=(SparseBitVector<ElementSize> *LHS,

836constSparseBitVector<ElementSize> &RHS) {

837returnLHS->operator&=(RHS);

838}

839

840template <unsigned ElementSize>

841inlinebooloperator &=(SparseBitVector<ElementSize> &LHS,

842constSparseBitVector<ElementSize> *RHS) {

843returnLHS &= *RHS;

844}

845

846// Convenience functions for infix union, intersection, difference operators.

847

848template <unsigned ElementSize>

849inline SparseBitVector<ElementSize>

850operator|(constSparseBitVector<ElementSize> &LHS,

851constSparseBitVector<ElementSize> &RHS) {

852SparseBitVector<ElementSize> Result(LHS);

853 Result |=RHS;

854return Result;

855}

856

857template <unsigned ElementSize>

858inline SparseBitVector<ElementSize>

859operator&(constSparseBitVector<ElementSize> &LHS,

860constSparseBitVector<ElementSize> &RHS) {

861SparseBitVector<ElementSize> Result(LHS);

862 Result &=RHS;

863return Result;

864}

865

866template <unsigned ElementSize>

867inline SparseBitVector<ElementSize>

868operator-(constSparseBitVector<ElementSize> &LHS,

869constSparseBitVector<ElementSize> &RHS) {

870SparseBitVector<ElementSize> Result;

871 Result.intersectWithComplement(LHS,RHS);

872return Result;

873}

874

875// Dump a SparseBitVector to a stream

876template <unsigned ElementSize>

877voiddump(constSparseBitVector<ElementSize> &LHS,raw_ostream &out) {

878 out <<"[";

879

880typenameSparseBitVector<ElementSize>::iterator bi =LHS.begin(),

881 be =LHS.end();

882if (bi != be) {

883 out << *bi;

884for (++bi; bi != be; ++bi) {

885 out <<" " << *bi;

886 }

887 }

888 out <<"]\n";

889}

890

891}// end namespace llvm

892

893#endif// LLVM_ADT_SPARSEBITVECTOR_H

Idx

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

Definition:DeadArgumentElimination.cpp:353

End

bool End

Definition:ELF_riscv.cpp:480

#define I(x, y, z)

Definition:MD5.cpp:58

test

modulo schedule test

Definition:ModuloSchedule.cpp:2781

assert

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

bit.h

This file implements the C++20 <bit> header.

llvm::BitVector

Definition:BitVector.h:82

llvm::BitVector::empty

bool empty() const

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

Definition:BitVector.h:156

llvm::SparseBitVector

Definition:SparseBitVector.h:256

llvm::SparseBitVector::operator!=

bool operator!=(const SparseBitVector &RHS) const

Definition:SparseBitVector.h:541

llvm::SparseBitVector::intersects

bool intersects(const SparseBitVector< ElementSize > &RHS) const

Definition:SparseBitVector.h:744

llvm::SparseBitVector::SparseBitVector

SparseBitVector()

Definition:SparseBitVector.h:444

llvm::SparseBitVector::find_first

int find_first() const

Definition:SparseBitVector.h:780

llvm::SparseBitVector::operator==

bool operator==(const SparseBitVector &RHS) const

Definition:SparseBitVector.h:545

llvm::SparseBitVector::operator=

SparseBitVector & operator=(const SparseBitVector &RHS)

Definition:SparseBitVector.h:457

llvm::SparseBitVector::clear

void clear()

Definition:SparseBitVector.h:452

llvm::SparseBitVector::begin

iterator begin() const

Definition:SparseBitVector.h:810

llvm::SparseBitVector::set

void set(unsigned Idx)

Definition:SparseBitVector.h:508

llvm::SparseBitVector::count

unsigned count() const

Definition:SparseBitVector.h:800

llvm::SparseBitVector::test_and_set

bool test_and_set(unsigned Idx)

Definition:SparseBitVector.h:532

llvm::SparseBitVector::intersectWithComplement

void intersectWithComplement(const SparseBitVector< ElementSize > *RHS1, const SparseBitVector< ElementSize > *RHS2)

Definition:SparseBitVector.h:734

llvm::SparseBitVector::contains

bool contains(const SparseBitVector< ElementSize > &RHS) const

Definition:SparseBitVector.h:773

llvm::SparseBitVector::intersectWithComplement

void intersectWithComplement(const SparseBitVector< ElementSize > &RHS1, const SparseBitVector< ElementSize > &RHS2)

Definition:SparseBitVector.h:688

llvm::SparseBitVector::SparseBitVector

SparseBitVector(const SparseBitVector &RHS)

Definition:SparseBitVector.h:446

llvm::SparseBitVector::operator|=

bool operator|=(const SparseBitVector &RHS)

Definition:SparseBitVector.h:558

llvm::SparseBitVector::end

iterator end() const

Definition:SparseBitVector.h:814

llvm::SparseBitVector::test

bool test(unsigned Idx) const

Definition:SparseBitVector.h:472

llvm::SparseBitVector::reset

void reset(unsigned Idx)

Definition:SparseBitVector.h:487

llvm::SparseBitVector::operator&=

bool operator&=(const SparseBitVector &RHS)

Definition:SparseBitVector.h:588

llvm::SparseBitVector::operator=

SparseBitVector & operator=(SparseBitVector &&RHS)

Definition:SparseBitVector.h:465

llvm::SparseBitVector::intersectWithComplement

bool intersectWithComplement(const SparseBitVector< ElementSize > *RHS) const

Definition:SparseBitVector.h:682

llvm::SparseBitVector::find_last

int find_last() const

Definition:SparseBitVector.h:788

llvm::SparseBitVector::intersectWithComplement

bool intersectWithComplement(const SparseBitVector &RHS)

Definition:SparseBitVector.h:637

llvm::SparseBitVector::empty

bool empty() const

Definition:SparseBitVector.h:796

llvm::SparseBitVector::intersects

bool intersects(const SparseBitVector< ElementSize > *RHS) const

Definition:SparseBitVector.h:739

llvm::SparseBitVector::iterator

SparseBitVectorIterator iterator

Definition:SparseBitVector.h:442

llvm::SparseBitVector::SparseBitVector

SparseBitVector(SparseBitVector &&RHS)

Definition:SparseBitVector.h:448

llvm::raw_ostream

This class implements an extremely fast bulk output stream that can only output to a stream.

Definition:raw_ostream.h:52

unsigned

ErrorHandling.h

llvm_unreachable

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Definition:ErrorHandling.h:143

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::dump

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

Definition:SparseBitVector.h:877

llvm::popcount

int popcount(T Value) noexcept

Count the number of set bits in a value.

Definition:bit.h:385

llvm::operator&

APInt operator&(APInt a, const APInt &b)

Definition:APInt.h:2092

llvm::operator*

APInt operator*(APInt a, uint64_t RHS)

Definition:APInt.h:2204

llvm::operator!=

bool operator!=(uint64_t V1, const APInt &V2)

Definition:APInt.h:2082

llvm::operator==

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

Definition:AddressRanges.h:153

llvm::countr_zero

int countr_zero(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

Definition:bit.h:215

llvm::countl_zero

int countl_zero(T Val)

Count number of 0's from the most significant bit to the least stopping at the first 1.

Definition:bit.h:281

llvm::IRMemLocation::First

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

llvm::operator&=

bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)

Definition:SparseBitVector.h:835

llvm::move

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

Definition:STLExtras.h:1873

llvm::PseudoProbeReservedId::Last

@ Last

llvm::operator-

APInt operator-(APInt)

Definition:APInt.h:2157

llvm::operator|=

bool operator|=(SparseBitVector< ElementSize > &LHS, const SparseBitVector< ElementSize > *RHS)

Definition:SparseBitVector.h:823

llvm::operator|

APInt operator|(APInt a, const APInt &b)

Definition:APInt.h:2112

std

Implement std::hash so that hash_code can be used in STL containers.

Definition:BitVector.h:858

raw_ostream.h

llvm::SparseBitVectorElement

SparseBitVector is an implementation of a bitvector that is sparse by only storing the elements that ...

Definition:SparseBitVector.h:42

llvm::SparseBitVectorElement::operator==

bool operator==(const SparseBitVectorElement &RHS) const

Definition:SparseBitVector.h:69

llvm::SparseBitVectorElement::find_next

int find_next(unsigned Curr) const

find_next - Returns the index of the next set bit starting from the "Curr" bit.

Definition:SparseBitVector.h:148

llvm::SparseBitVectorElement::unionWith

bool unionWith(const SparseBitVectorElement &RHS)

Definition:SparseBitVector.h:172

llvm::SparseBitVectorElement::find_last

int find_last() const

find_last - Returns the index of the last set bit.

Definition:SparseBitVector.h:136

llvm::SparseBitVectorElement::index

unsigned index() const

Definition:SparseBitVector.h:88

llvm::SparseBitVectorElement::SparseBitVectorElement

SparseBitVectorElement(unsigned Idx)

Definition:SparseBitVector.h:63

llvm::SparseBitVectorElement::intersectWithComplement

void intersectWithComplement(const SparseBitVectorElement &RHS1, const SparseBitVectorElement &RHS2, bool &BecameZero)

Definition:SparseBitVector.h:240

llvm::SparseBitVectorElement::intersectWith

bool intersectWith(const SparseBitVectorElement &RHS, bool &BecameZero)

Definition:SparseBitVector.h:195

llvm::SparseBitVectorElement::BitWord

unsigned long BitWord

Definition:SparseBitVector.h:44

llvm::SparseBitVectorElement::operator!=

bool operator!=(const SparseBitVectorElement &RHS) const

Definition:SparseBitVector.h:78

llvm::SparseBitVectorElement::reset

void reset(unsigned Idx)

Definition:SparseBitVector.h:112

llvm::SparseBitVectorElement::test_and_set

bool test_and_set(unsigned Idx)

Definition:SparseBitVector.h:103

llvm::SparseBitVectorElement::word

BitWord word(unsigned Idx) const

Definition:SparseBitVector.h:83

llvm::SparseBitVectorElement::BITWORDS_PER_ELEMENT

@ BITWORDS_PER_ELEMENT

Definition:SparseBitVector.h:48

llvm::SparseBitVectorElement::BITS_PER_ELEMENT

@ BITS_PER_ELEMENT

Definition:SparseBitVector.h:49

llvm::SparseBitVectorElement::BITWORD_SIZE

@ BITWORD_SIZE

Definition:SparseBitVector.h:47

llvm::SparseBitVectorElement::set

void set(unsigned Idx)

Definition:SparseBitVector.h:99

llvm::SparseBitVectorElement::test

bool test(unsigned Idx) const

Definition:SparseBitVector.h:116

llvm::SparseBitVectorElement::empty

bool empty() const

Definition:SparseBitVector.h:92

llvm::SparseBitVectorElement::intersectWithComplement

bool intersectWithComplement(const SparseBitVectorElement &RHS, bool &BecameZero)

Definition:SparseBitVector.h:218

llvm::SparseBitVectorElement::count

size_type count() const

Definition:SparseBitVector.h:120

llvm::SparseBitVectorElement::find_first

int find_first() const

find_first - Returns the index of the first set bit.

Definition:SparseBitVector.h:128

llvm::SparseBitVectorElement::intersects

bool intersects(const SparseBitVectorElement &RHS) const

Definition:SparseBitVector.h:185