SparseBitVector.h Source File (original) (raw)

15#ifndef LLVM_ADT_SPARSEBITVECTOR_H

16#define LLVM_ADT_SPARSEBITVECTOR_H

21#include

22#include

23#include

24#include

25#include

27namespace llvm {

42template struct SparseBitVectorElement {

43public:

46 enum {

50 };

52private:

54 unsigned ElementIndex;

58 ElementIndex = ~0U;

60 }

62public:

64 ElementIndex = Idx;

66 }

69 bool operator==(const SparseBitVectorElement &RHS) const {

70 if (ElementIndex != RHS.ElementIndex)

71 return false;

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

74 return false;

75 return true;

76 }

78 bool operator!=(const SparseBitVectorElement &RHS) const {

79 return !(*this == RHS);

80 }

85 return Bits[Idx];

86 }

89 return ElementIndex;

90 }

94 if (Bits[i])

95 return false;

96 return true;

97 }

99 void set(unsigned Idx) {

101 }

102

104 bool old = test(Idx);

105 if (!old) {

106 set(Idx);

107 return true;

108 }

109 return false;

110 }

111

115

116 bool test(unsigned Idx) const {

118 }

119

121 unsigned NumBits = 0;

124 return NumBits;

125 }

126

127

130 if (Bits[i] != 0)

133 }

134

135

139 if (Bits[Idx] != 0)

142 }

144 }

145

146

147

150 return -1;

151

154 BitWord Copy = Bits[WordPos];

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

157

158

159 Copy &= ~0UL << BitPos;

160

161 if (Copy != 0)

163

164

166 if (Bits[i] != 0)

168 return -1;

169 }

170

171

173 bool changed = false;

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

176

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

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

179 changed = true;

180 }

181 return changed;

182 }

183

184

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

188 return true;

189 }

190 return false;

191 }

192

193

194

196 bool &BecameZero) {

197 bool changed = false;

198 bool allzero = true;

199

200 BecameZero = false;

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

203

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

205 if (Bits[i] != 0)

206 allzero = false;

207

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

209 changed = true;

210 }

211 BecameZero = allzero;

212 return changed;

213 }

214

215

216

217

219 bool &BecameZero) {

220 bool changed = false;

221 bool allzero = true;

222

223 BecameZero = false;

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

226

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

228 if (Bits[i] != 0)

229 allzero = false;

230

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

232 changed = true;

233 }

234 BecameZero = allzero;

235 return changed;

236 }

237

238

239

241 const SparseBitVectorElement &RHS2,

242 bool &BecameZero) {

243 bool allzero = true;

244

245 BecameZero = false;

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

248 if (Bits[i] != 0)

249 allzero = false;

250 }

251 BecameZero = allzero;

252 }

253};

254

255template

257 using ElementList = std::list<SparseBitVectorElement>;

258 using ElementListIter = typename ElementList::iterator;

259 using ElementListConstIter = typename ElementList::const_iterator;

260 enum {

262 };

263

264 ElementList Elements;

265

266

267

268 mutable ElementListIter CurrElementIter;

269

270

271

272 ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const {

273

274

275

276

277

278

279 ElementListIter Begin =

281 ElementListIter End =

283

284 if (Elements.empty()) {

285 CurrElementIter = Begin;

286 return CurrElementIter;

287 }

288

289

290 if (CurrElementIter == End)

291 --CurrElementIter;

292

293

294

295 ElementListIter ElementIter = CurrElementIter;

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

297 return ElementIter;

298 } else if (CurrElementIter->index() > ElementIndex) {

299 while (ElementIter != Begin

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

301 --ElementIter;

302 } else {

303 while (ElementIter != End &&

304 ElementIter->index() < ElementIndex)

305 ++ElementIter;

306 }

307 CurrElementIter = ElementIter;

308 return ElementIter;

309 }

310 ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const {

311 return FindLowerBoundImpl(ElementIndex);

312 }

313 ElementListIter FindLowerBound(unsigned ElementIndex) {

314 return FindLowerBoundImpl(ElementIndex);

315 }

316

317

318

319 class SparseBitVectorIterator {

320 private:

321 bool AtEnd;

322

324

325

326 ElementListConstIter Iter;

327

328

329 unsigned BitNumber;

330

331

332 unsigned WordNumber;

333

334

336

337

338 void AdvanceToFirstNonZero() {

339 if (AtEnd)

340 return;

342 AtEnd = true;

343 return;

344 }

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

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

347 unsigned 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

355 void AdvanceToNextNonZero() {

356 if (AtEnd)

357 return;

358

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

360 Bits >>= 1;

361 BitNumber += 1;

362 }

363

364

365 if (!Bits) {

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

367

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

369 ++Iter;

370 WordNumber = 0;

371

372

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

374 AtEnd = true;

375 return;

376 }

377

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

394 public:

395 SparseBitVectorIterator() = default;

396

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

400 BitNumber = 0;

401 Bits = 0;

402 WordNumber = ~0;

403 AtEnd = end;

404 AdvanceToFirstNonZero();

405 }

406

407

408 inline SparseBitVectorIterator& operator++() {

409 ++BitNumber;

410 Bits >>= 1;

411 AdvanceToNextNonZero();

412 return *this;

413 }

414

415

416 inline SparseBitVectorIterator operator++(int) {

417 SparseBitVectorIterator tmp = *this;

418 ++*this;

419 return tmp;

420 }

421

422

424 return BitNumber;

425 }

426

427 bool operator==(const SparseBitVectorIterator &RHS) const {

428

429 if (AtEnd && RHS.AtEnd)

430 return true;

431

432

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

434 }

435

436 bool operator!=(const SparseBitVectorIterator &RHS) const {

437 return !(*this == RHS);

438 }

439 };

440

441public:

442 using iterator = SparseBitVectorIterator;

443

445

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

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

450

451

453 Elements.clear();

454 }

455

456

458 if (this == &RHS)

459 return *this;

460

461 Elements = RHS.Elements;

462 CurrElementIter = Elements.begin();

463 return *this;

464 }

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

467 CurrElementIter = Elements.begin();

468 return *this;

469 }

470

471

472 bool test(unsigned Idx) const {

473 if (Elements.empty())

474 return false;

475

476 unsigned ElementIndex = Idx / ElementSize;

477 ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);

478

479

480

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

482 ElementIter->index() != ElementIndex)

483 return false;

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

485 }

486

488 if (Elements.empty())

489 return;

490

491 unsigned ElementIndex = Idx / ElementSize;

492 ElementListIter ElementIter = FindLowerBound(ElementIndex);

493

494

495

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

497 ElementIter->index() != ElementIndex)

498 return;

499 ElementIter->reset(Idx % ElementSize);

500

501

502 if (ElementIter->empty()) {

503 ++CurrElementIter;

504 Elements.erase(ElementIter);

505 }

506 }

507

508 void set(unsigned Idx) {

509 unsigned ElementIndex = Idx / ElementSize;

510 ElementListIter ElementIter;

511 if (Elements.empty()) {

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

513 } else {

514 ElementIter = FindLowerBound(ElementIndex);

515

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

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

518

519

520

521 if (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

533 bool old = test(Idx);

534 if (!old) {

535 set(Idx);

536 return true;

537 }

538 return false;

539 }

540

542 return !(*this == RHS);

543 }

544

546 ElementListConstIter Iter1 = Elements.begin();

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

548

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

550 ++Iter1, ++Iter2) {

551 if (*Iter1 != *Iter2)

552 return false;

553 }

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

555 }

556

557

559 if (this == &RHS)

560 return false;

561

562 bool changed = false;

563 ElementListIter Iter1 = Elements.begin();

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

565

566

567 if (RHS.Elements.empty())

568 return false;

569

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

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

572 Elements.insert(Iter1, *Iter2);

573 ++Iter2;

574 changed = true;

575 } else if (Iter1->index() == Iter2->index()) {

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

577 ++Iter1;

578 ++Iter2;

579 } else {

580 ++Iter1;

581 }

582 }

583 CurrElementIter = Elements.begin();

584 return changed;

585 }

586

587

589 if (this == &RHS)

590 return false;

591

592 bool changed = false;

593 ElementListIter Iter1 = Elements.begin();

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

595

596

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

598 return false;

599

600

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

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

603 CurrElementIter = Elements.begin();

604 return changed;

605 }

606

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

608 ++Iter2;

609 } else if (Iter1->index() == Iter2->index()) {

610 bool BecameZero;

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

612 if (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 }

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

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

629 changed = true;

630 }

631 CurrElementIter = Elements.begin();

632 return changed;

633 }

634

635

636

638 if (this == &RHS) {

641 return true;

642 }

643 return false;

644 }

645

646 bool changed = false;

647 ElementListIter Iter1 = Elements.begin();

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

649

650

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

652 return false;

653

654

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

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

657 CurrElementIter = Elements.begin();

658 return changed;

659 }

660

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

662 ++Iter2;

663 } else if (Iter1->index() == Iter2->index()) {

664 bool BecameZero;

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

666 if (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();

679 return changed;

680 }

681

685

686

687

690 {

691 if (this == &RHS1) {

693 return;

694 } else if (this == &RHS2) {

697 return;

698 }

699

700 Elements.clear();

701 CurrElementIter = Elements.begin();

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

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

704

705

706

707 if (RHS1.Elements.empty())

708 return;

709

710

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

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

713 return;

714

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

716 ++Iter2;

717 } else if (Iter1->index() == Iter2->index()) {

718 bool BecameZero = false;

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

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

721 if (BecameZero)

722 Elements.pop_back();

723 ++Iter1;

724 ++Iter2;

725 } else {

726 Elements.push_back(*Iter1++);

727 }

728 }

729

730

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

732 }

733

738

742

743

745 ElementListConstIter Iter1 = Elements.begin();

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

747

748

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

750 return false;

751

752

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

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

755 return false;

756

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

758 ++Iter2;

759 } else if (Iter1->index() == Iter2->index()) {

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

761 return true;

762 ++Iter1;

763 ++Iter2;

764 } else {

765 ++Iter1;

766 }

767 }

768 return false;

769 }

770

771

772

775 Result &= RHS;

776 return (Result == RHS);

777 }

778

779

781 if (Elements.empty())

782 return -1;

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

785 }

786

787

789 if (Elements.empty())

790 return -1;

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

793 }

794

795

797 return Elements.empty();

798 }

799

801 unsigned BitCount = 0;

803 BitCount += Elem.count();

804 return BitCount;

805 }

806

810

814};

815

816

817

818

819template

824

825template

828 return LHS->operator|=(RHS);

829}

830

831template

834 return LHS->operator&=(RHS);

835}

836

837template

842

843

844

845template

846inline SparseBitVector

850 Result |= RHS;

851 return Result;

852}

853

854template

855inline SparseBitVector

859 Result &= RHS;

860 return Result;

861}

862

863template

864inline SparseBitVector

868 Result.intersectWithComplement(LHS, RHS);

869 return Result;

870}

871

872

873template

875 out << "[";

876

878 be = LHS.end();

879 if (bi != be) {

880 out << *bi;

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

882 out << " " << *bi;

883 }

884 }

885 out << "]\n";

886}

887

888}

889

890#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file implements the C++20 header.

bool empty() const

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

Definition SparseBitVector.h:256

bool operator!=(const SparseBitVector &RHS) const

Definition SparseBitVector.h:541

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

Definition SparseBitVector.h:744

SparseBitVector()

Definition SparseBitVector.h:444

int find_first() const

Definition SparseBitVector.h:780

bool operator==(const SparseBitVector &RHS) const

Definition SparseBitVector.h:545

SparseBitVector & operator=(const SparseBitVector &RHS)

Definition SparseBitVector.h:457

void clear()

Definition SparseBitVector.h:452

iterator begin() const

Definition SparseBitVector.h:807

void set(unsigned Idx)

Definition SparseBitVector.h:508

unsigned count() const

Definition SparseBitVector.h:800

bool test_and_set(unsigned Idx)

Definition SparseBitVector.h:532

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

Definition SparseBitVector.h:734

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

Definition SparseBitVector.h:773

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

Definition SparseBitVector.h:688

SparseBitVector(const SparseBitVector &RHS)

Definition SparseBitVector.h:446

bool operator|=(const SparseBitVector &RHS)

Definition SparseBitVector.h:558

iterator end() const

Definition SparseBitVector.h:811

bool test(unsigned Idx) const

Definition SparseBitVector.h:472

void reset(unsigned Idx)

Definition SparseBitVector.h:487

bool operator&=(const SparseBitVector &RHS)

Definition SparseBitVector.h:588

SparseBitVector & operator=(SparseBitVector &&RHS)

Definition SparseBitVector.h:465

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

Definition SparseBitVector.h:682

int find_last() const

Definition SparseBitVector.h:788

bool intersectWithComplement(const SparseBitVector &RHS)

Definition SparseBitVector.h:637

bool empty() const

Definition SparseBitVector.h:796

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

Definition SparseBitVector.h:739

SparseBitVectorIterator iterator

Definition SparseBitVector.h:442

SparseBitVector(SparseBitVector &&RHS)

Definition SparseBitVector.h:448

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

#define llvm_unreachable(msg)

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

This is an optimization pass for GlobalISel generic memory operations.

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

Definition SparseBitVector.h:874

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

APInt operator*(APInt a, uint64_t RHS)

constexpr int popcount(T Value) noexcept

Count the number of set bits in a value.

int countr_zero(T Val)

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

int countl_zero(T Val)

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

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

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

Definition SparseBitVector.h:832

OutputIt move(R &&Range, OutputIt Out)

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

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

Definition SparseBitVector.h:820

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

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

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

Definition SparseBitVector.h:42

bool operator==(const SparseBitVectorElement &RHS) const

Definition SparseBitVector.h:69

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

bool unionWith(const SparseBitVectorElement &RHS)

Definition SparseBitVector.h:172

int find_last() const

find_last - Returns the index of the last set bit.

Definition SparseBitVector.h:136

unsigned index() const

Definition SparseBitVector.h:88

SparseBitVectorElement(unsigned Idx)

Definition SparseBitVector.h:63

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

Definition SparseBitVector.h:240

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

Definition SparseBitVector.h:195

unsigned long BitWord

Definition SparseBitVector.h:44

bool operator!=(const SparseBitVectorElement &RHS) const

Definition SparseBitVector.h:78

void reset(unsigned Idx)

Definition SparseBitVector.h:112

bool test_and_set(unsigned Idx)

Definition SparseBitVector.h:103

BitWord word(unsigned Idx) const

Definition SparseBitVector.h:83

unsigned size_type

Definition SparseBitVector.h:45

void set(unsigned Idx)

Definition SparseBitVector.h:99

bool test(unsigned Idx) const

Definition SparseBitVector.h:116

bool empty() const

Definition SparseBitVector.h:92

@ BITWORDS_PER_ELEMENT

Definition SparseBitVector.h:48

@ BITS_PER_ELEMENT

Definition SparseBitVector.h:49

@ BITWORD_SIZE

Definition SparseBitVector.h:47

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

Definition SparseBitVector.h:218

size_type count() const

Definition SparseBitVector.h:120

int find_first() const

find_first - Returns the index of the first set bit.

Definition SparseBitVector.h:128

bool intersects(const SparseBitVectorElement &RHS) const

Definition SparseBitVector.h:185