SmallBitVector.h Source File (original) (raw)

14#ifndef LLVM_ADT_SMALLBITVECTOR_H

15#define LLVM_ADT_SMALLBITVECTOR_H

20#include

21#include

22#include

23#include

24#include

25#include

26#include

28namespace llvm {

39 uintptr_t X = 1;

41 enum {

43 NumBaseBits = sizeof(uintptr_t) * CHAR_BIT,

47 SmallNumRawBits = NumBaseBits - 1,

52 SmallNumSizeBits = (NumBaseBits == 32 ? 5 :

53 NumBaseBits == 64 ? 6 :

54 SmallNumRawBits),

57 SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits

58 };

60 static_assert(NumBaseBits == 64 || NumBaseBits == 32,

61 "Unsupported word size");

63public:

69 unsigned BitPos;

71 public:

77 *this = bool(t);

78 return *this;

79 }

82 if (t)

83 TheVector.set(BitPos);

84 else

85 TheVector.reset(BitPos);

86 return *this;

87 }

89 operator bool() const {

90 return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);

91 }

92 };

94private:

97 return reinterpret_cast<BitVector *>(X);

98 }

100 void switchToSmall(uintptr_t NewSmallBits, size_type NewSize) {

101 X = 1;

102 setSmallSize(NewSize);

103 setSmallBits(NewSmallBits);

104 }

105

106 void switchToLarge(BitVector *BV) {

107 X = reinterpret_cast<uintptr_t>(BV);

108 assert( isSmall () && "Tried to use an unaligned pointer");

109 }

110

111

112

113 uintptr_t getSmallRawBits() const {

115 return X >> 1;

116 }

117

118 void setSmallRawBits(uintptr_t NewRawBits) {

120 X = (NewRawBits << 1) | uintptr_t(1);

121 }

122

123

125 return getSmallRawBits() >> SmallNumDataBits;

126 }

127

129 setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));

130 }

131

132

133 uintptr_t getSmallBits() const {

134 return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());

135 }

136

137 void setSmallBits(uintptr_t NewBits) {

138 setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |

139 (getSmallSize() << SmallNumDataBits));

140 }

141

142public:

143

145

146

147

149 if (s <= SmallNumDataBits)

150 switchToSmall(t ? ~uintptr_t(0) : 0, s);

151 else

152 switchToLarge(new BitVector(s, t));

153 }

154

155

157 if (RHS.isSmall())

158 X = RHS.X;

159 else

160 switchToLarge(new BitVector(*RHS.getPointer()));

161 }

162

164 RHS.X = 1;

165 }

166

169 delete getPointer();

170 }

171

174

177 }

178

181 }

182

185 }

186

187 bool isSmall() const { return X & uintptr_t(1); }

188

189

191 return isSmall() ? getSmallSize() == 0 : getPointer()->empty();

192 }

193

194

196 return isSmall() ? getSmallSize() : getPointer()->size();

197 }

198

199

202 uintptr_t Bits = getSmallBits();

204 }

205 return getPointer()->count();

206 }

207

208

211 return getSmallBits() != 0;

212 return getPointer()->any();

213 }

214

215

218 return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;

219 return getPointer()->all();

220 }

221

222

225 return getSmallBits() == 0;

226 return getPointer()->none();

227 }

228

229

232 uintptr_t Bits = getSmallBits();

233 if (Bits == 0)

234 return -1;

236 }

238 }

239

242 uintptr_t Bits = getSmallBits();

243 if (Bits == 0)

244 return -1;

246 }

247 return getPointer()->find_last();

248 }

249

250

253 if (count() == getSmallSize())

254 return -1;

255

256 uintptr_t Bits = getSmallBits();

258 }

260 }

261

264 if (count() == getSmallSize())

265 return -1;

266

267 uintptr_t Bits = getSmallBits();

268

269 Bits |= ~uintptr_t(0) << getSmallSize();

271 }

273 }

274

275

276

279 uintptr_t Bits = getSmallBits();

280

281 Bits &= ~uintptr_t(0) << (Prev + 1);

282 if (Bits == 0 || Prev + 1 >= getSmallSize())

283 return -1;

285 }

286 return getPointer()->find_next(Prev);

287 }

288

289

290

293 uintptr_t Bits = getSmallBits();

294

295 Bits |= (uintptr_t(1) << (Prev + 1)) - 1;

296

297 Bits |= ~uintptr_t(0) << getSmallSize();

298

299 if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())

300 return -1;

302 }

304 }

305

306

307

310 if (PriorTo == 0)

311 return -1;

312

313 --PriorTo;

314 uintptr_t Bits = getSmallBits();

315 Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);

316 if (Bits == 0)

317 return -1;

318

320 }

321 return getPointer()->find_prev(PriorTo);

322 }

323

324

327 delete getPointer();

328 switchToSmall(0, 0);

329 }

330

331

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

334 getPointer()->resize(N, t);

335 } else if (SmallNumDataBits >= N) {

336 uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;

337 setSmallSize(N);

338 setSmallBits(NewBits | getSmallBits());

339 } else {

341 uintptr_t OldBits = getSmallBits();

342 for (size_type I = 0, E = getSmallSize(); I != E; ++I)

343 (*BV)[I] = (OldBits >> I) & 1;

344 switchToLarge(BV);

345 }

346 }

347

350 if (N > SmallNumDataBits) {

351 uintptr_t OldBits = getSmallRawBits();

352 size_type SmallSize = getSmallSize();

355 if ((OldBits >> I) & 1)

358 switchToLarge(BV);

359 }

360 } else {

362 }

363 }

364

365

368 setSmallBits(~uintptr_t(0));

369 else

370 getPointer()->set();

371 return *this;

372 }

373

376 assert(Idx <= static_cast<unsigned>(

377 std::numeric_limits<uintptr_t>::digits) &&

378 "undefined behavior");

379 setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));

380 }

381 else

382 getPointer()->set(Idx);

383 return *this;

384 }

385

386

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

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

390 if (I == E) return *this;

392 uintptr_t EMask = ((uintptr_t)1) << E;

393 uintptr_t IMask = ((uintptr_t)1) << I;

394 uintptr_t Mask = EMask - IMask;

395 setSmallBits(getSmallBits() | Mask);

396 } else

397 getPointer()->set(I, E);

398 return *this;

399 }

400

403 setSmallBits(0);

404 else

405 getPointer()->reset();

406 return *this;

407 }

408

411 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));

412 else

414 return *this;

415 }

416

417

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

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

421 if (I == E) return *this;

423 uintptr_t EMask = ((uintptr_t)1) << E;

424 uintptr_t IMask = ((uintptr_t)1) << I;

425 uintptr_t Mask = EMask - IMask;

426 setSmallBits(getSmallBits() & ~Mask);

427 } else

428 getPointer()->reset(I, E);

429 return *this;

430 }

431

434 setSmallBits(~getSmallBits());

435 else

436 getPointer()->flip();

437 return *this;

438 }

439

442 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));

443 else

445 return *this;

446 }

447

448

451 }

452

453

455 assert(Idx < size() && "Out-of-bounds Bit access.");

457 }

458

460 assert(Idx < size() && "Out-of-bounds Bit access.");

462 return ((getSmallBits() >> Idx) & 1) != 0;

463 return getPointer()->operator[](Idx);

464 }

465

466

468 assert( empty () && "Getting last element of empty vector.");

469 return (*this)[size() - 1];

470 }

471

473 return (*this)[Idx];

474 }

475

476

479 }

480

481

483 assert( empty () && "Empty vector has no element to pop.");

485 }

486

487

490 return (getSmallBits() & RHS.getSmallBits()) != 0;

492 return getPointer()->anyCommon(*RHS.getPointer());

493

494 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)

495 if (test(i) && RHS.test(i))

496 return true;

497 return false;

498 }

499

500

502 if (size() != RHS.size())

503 return false;

505 return getSmallBits() == RHS.getSmallBits();

506 else if ( isSmall () && RHS .isSmall())

507 return *getPointer() == *RHS.getPointer();

508 else {

510 if ((*this)[I] != RHS[I])

511 return false;

512 }

513 return true;

514 }

515 }

516

518 return !(*this == RHS);

519 }

520

521

522

526 setSmallBits(getSmallBits() & RHS.getSmallBits());

527 else if ( isSmall () && RHS .isSmall())

528 getPointer()->operator&=(*RHS.getPointer());

529 else {

531 for (I = 0, E = std::min(size(), RHS.size()); I != E; ++I)

533 for (E = size(); I != E; ++I)

535 }

536 return *this;

537 }

538

539

542 setSmallBits(getSmallBits() & ~RHS.getSmallBits());

543 else if ( isSmall () && RHS .isSmall())

544 getPointer()->reset(*RHS.getPointer());

545 else

546 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)

547 if (RHS.test(i))

549

550 return *this;

551 }

552

553

556 return (getSmallBits() & ~RHS.getSmallBits()) != 0;

558 return getPointer()->test(*RHS.getPointer());

559

560 unsigned i, e;

561 for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)

562 if (test(i) && RHS .test(i))

563 return true;

564

565 for (e = size(); i != e; ++i)

567 return true;

568

569 return false;

570 }

571

575 setSmallBits(getSmallBits() | RHS.getSmallBits());

576 else if ( isSmall () && RHS .isSmall())

577 getPointer()->operator|=(*RHS.getPointer());

578 else {

581 }

582 return *this;

583 }

584

588 setSmallBits(getSmallBits() ^ RHS.getSmallBits());

589 else if ( isSmall () && RHS .isSmall())

590 getPointer()->operator^=(*RHS.getPointer());

591 else {

594 }

595 return *this;

596 }

597

600 setSmallBits(getSmallBits() << N);

601 else

602 getPointer()->operator<<=(N);

603 return *this;

604 }

605

608 setSmallBits(getSmallBits() >> N);

609 else

610 getPointer()->operator>>=(N);

611 return *this;

612 }

613

614

617 if (RHS.isSmall())

618 X = RHS.X;

619 else

620 switchToLarge(new BitVector(*RHS.getPointer()));

621 } else {

622 if ( RHS .isSmall())

623 *getPointer() = *RHS.getPointer();

624 else {

625 delete getPointer();

626 X = RHS.X;

627 }

628 }

629 return *this;

630 }

631

633 if (this != &RHS) {

636 }

637 return *this;

638 }

639

642 }

643

644

645

648 applyMask<true, false>(Mask, MaskWords);

649 else

651 }

652

653

654

657 applyMask<false, false>(Mask, MaskWords);

658 else

660 }

661

662

663

666 applyMask<true, true>(Mask, MaskWords);

667 else

669 }

670

671

672

675 applyMask<false, true>(Mask, MaskWords);

676 else

678 }

679

682 X = (uintptr_t)-1;

683 }

684 bool isInvalid() const { return X == (uintptr_t)-1; }

685

688 return getPointer()->getData();

689 Store = getSmallBits();

690 return Store;

691 }

692

693private:

694 template <bool AddBits, bool InvertMask>

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

696 assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");

697 uintptr_t M = Mask[0];

698 if (NumBaseBits == 64)

699 M |= uint64_t(Mask[1]) << 32;

700 if (InvertMask)

701 M = ~M;

702 if (AddBits)

703 setSmallBits(getSmallBits() | M);

704 else

705 setSmallBits(getSmallBits() & ~M);

706 }

707};

708

709inline SmallBitVector

712 Result &= RHS;

713 return Result;

714}

715

716inline SmallBitVector

719 Result |= RHS;

720 return Result;

721}

722

723inline SmallBitVector

726 Result ^= RHS;

727 return Result;

728}

729

734 V.invalid();

735 return V;

736 }

738 uintptr_t Store;

740 std::pair<SmallBitVector::size_type, ArrayRef<uintptr_t>>>::

741 getHashValue(std::make_pair(V.size(), V.getData(Store)));

742 }

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

745 return LHS.isInvalid() == RHS.isInvalid();

747 }

748};

749}

750

751namespace std {

752

753

754inline void

757}

758

759}

760

761#endif

This file implements the BitVector class.

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

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

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

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

bool test(unsigned Idx) const

int find_first() const

find_first - Returns the index of the first set bit, -1 if none of the bits are set.

void resize(unsigned N, bool t=false)

resize - Grow or shrink the bitvector.

bool anyCommon(const BitVector &RHS) const

Test if any common bits are set.

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

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

int find_last() const

find_last - Returns the index of the last set bit, -1 if none of the bits are set.

size_type count() const

count - Returns the number of bits which are set.

ArrayRef< BitWord > getData() const

int find_last_unset() const

find_last_unset - Returns the index of the last unset bit, -1 if all of the bits are set.

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

setBitsInMask - Add '1' bits from Mask to this vector.

bool any() const

any - Returns true if any bit is set.

bool all() const

all - Returns true if all bits are set.

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

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

int find_prev(unsigned PriorTo) const

find_prev - Returns the index of the first set bit that precedes the the bit at PriorTo.

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

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

int find_next(unsigned Prev) const

find_next - Returns the index of the next set bit following the "Prev" bit.

bool none() const

none - Returns true if none of the bits are set.

size_type size() const

size - Returns the number of bits in this bitvector.

bool empty() const

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

int find_next_unset(unsigned Prev) const

find_next_unset - Returns the index of the next unset bit following the "Prev" bit.

int find_first_unset() const

find_first_unset - Returns the index of the first unset bit, -1 if all of the bits are set.

reference(SmallBitVector &b, unsigned Idx)

reference & operator=(bool t)

reference & operator=(reference t)

reference(const reference &)=default

This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...

reference operator[](unsigned Idx)

int find_last_unset() const

bool operator[](unsigned Idx) const

int find_first() const

Returns the index of the first set bit, -1 if none of the bits are set.

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

Clear any bits in this vector that are set in Mask.

bool test(const SmallBitVector &RHS) const

Check if (This - RHS) is zero. This is the same as reset(RHS) and any().

SmallBitVector & reset(unsigned I, unsigned E)

Efficiently reset a range of bits in [I, E)

void swap(SmallBitVector &RHS)

int find_prev(unsigned PriorTo) const

find_prev - Returns the index of the first set bit that precedes the the bit at PriorTo.

SmallBitVector & set(unsigned I, unsigned E)

Efficiently set a range of bits in [I, E)

SmallBitVector(SmallBitVector &&RHS)

bool test(unsigned Idx) const

SmallBitVector()=default

Creates an empty bitvector.

SmallBitVector & operator&=(const SmallBitVector &RHS)

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

Add '1' bits from Mask to this vector.

bool back() const

Return the last element in the vector.

const SmallBitVector & operator=(SmallBitVector &&RHS)

SmallBitVector(unsigned s, bool t=false)

Creates a bitvector of specified number of bits.

iterator_range< const_set_bits_iterator > set_bits() const

SmallBitVector(const SmallBitVector &RHS)

SmallBitVector copy ctor.

void clear()

Clear all bits.

SmallBitVector & operator<<=(unsigned N)

int find_next(unsigned Prev) const

Returns the index of the next set bit following the "Prev" bit.

SmallBitVector & reset(const SmallBitVector &RHS)

Reset bits that are set in RHS. Same as *this &= ~RHS.

SmallBitVector & reset(unsigned Idx)

const SmallBitVector & operator=(const SmallBitVector &RHS)

const_set_bits_iterator_impl< SmallBitVector > const_set_bits_iterator

bool all() const

Returns true if all bits are set.

bool operator==(const SmallBitVector &RHS) const

ArrayRef< uintptr_t > getData(uintptr_t &Store) const

SmallBitVector & operator>>=(unsigned N)

int find_first_unset() const

Returns the index of the first unset bit, -1 if all of the bits are set.

size_type size() const

Returns the number of bits in this bitvector.

void resize(unsigned N, bool t=false)

Grow or shrink the bitvector.

bool any() const

Returns true if any bit is set.

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

Add a bit to this vector for every '0' bit in Mask.

bool empty() const

Tests whether there are no bits in this bitvector.

const_set_bits_iterator set_bits_end() const

SmallBitVector & flip(unsigned Idx)

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

Clear a bit in this vector for every '0' bit in Mask.

SmallBitVector & operator|=(const SmallBitVector &RHS)

size_type count() const

Returns the number of bits which are set.

bool anyCommon(const SmallBitVector &RHS) const

Test if any common bits are set.

int find_next_unset(unsigned Prev) const

Returns the index of the next unset bit following the "Prev" bit.

const_set_bits_iterator set_bits_begin() const

void pop_back()

Pop one bit from the end of the vector.

SmallBitVector & set(unsigned Idx)

SmallBitVector operator~() const

bool none() const

Returns true if none of the bits are set.

SmallBitVector & operator^=(const SmallBitVector &RHS)

bool operator!=(const SmallBitVector &RHS) const

ForwardIterator for the bits that are set.

A range adaptor for a pair of iterators.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

This is an optimization pass for GlobalISel generic memory operations.

int popcount(T Value) noexcept

Count the number of set bits in a value.

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

int countr_one(T Value)

Count the number of ones from the least significant bit to the first zero bit.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

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.

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

int countl_one(T Value)

Count the number of ones from the most significant bit to the first zero bit.

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

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

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

static SmallBitVector getTombstoneKey()

static SmallBitVector getEmptyKey()

static unsigned getHashValue(const SmallBitVector &V)

static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS)

An information struct used to provide DenseMap with the various necessary components for a given valu...