BitVector.h Source File (original) (raw)

14#ifndef LLVM_ADT_BITVECTOR_H

15#define LLVM_ADT_BITVECTOR_H

21#include

22#include

23#include

24#include

25#include

26#include

27#include

28#include

30namespace llvm {

35 const BitVectorT &Parent;

36 int Current = 0;

38 void advance() {

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

40 Current = Parent.find_next(Current);

41 }

43public:

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

57 auto Prev = *this;

58 advance();

59 return Prev;

60 }

63 advance();

64 return *this;

65 }

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

71 "Comparing iterators from different BitVectors");

72 return Current == Other.Current;

73 }

77 "Comparing iterators from different BitVectors");

78 return Current != Other.Current;

79 }

80};

83 typedef uintptr_t BitWord;

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

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

88 "Unsupported word size");

92 Storage Bits;

93 unsigned Size = 0;

95public:

100

101 BitWord *WordRef;

102 unsigned BitPos;

103

104 public:

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

107 BitPos = Idx % BITWORD_SIZE;

108 }

109

112

114 *this = bool(t);

115 return *this;

116 }

117

119 if (t)

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

121 else

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

123 return *this;

124 }

125

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

128 }

129 };

130

133

136 }

139 }

142 }

143

144

146

147

148

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

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

151 if (t)

152 clear_unused_bits();

153 }

154

155

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

157

158

160

161

163 unsigned NumBits = 0;

164 for (auto Bit : Bits)

166 return NumBits;

167 }

168

169

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

172 }

173

174

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

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

178 return false;

179

180

181 if (unsigned Remainder = Size % BITWORD_SIZE)

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

183

184 return true;

185 }

186

187

189 return any ();

190 }

191

192

193

194

197 if (Begin == End)

198 return -1;

199

200 unsigned FirstWord = Begin / BITWORD_SIZE;

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

202

203

204

205

206

207

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(FirstBit);

216 }

217

218 if (i == LastWord) {

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

220 Copy &= maskTrailingOnes(LastBit + 1);

221 }

222 if (Copy != 0)

224 }

225 return -1;

226 }

227

228

229

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(LastBit + 1);

245 }

246

247 if (CurrentWord == FirstWord) {

248 unsigned FirstBit = Begin % BITWORD_SIZE;

249 Copy &= maskTrailingZeros(FirstBit);

250 }

251

252 if (Copy != 0)

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

254 }

255

256 return -1;

257 }

258

259

260

263 }

264

265

266

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(LastBit + 1);

282 }

283

284 if (CurrentWord == FirstWord) {

285 unsigned FirstBit = Begin % BITWORD_SIZE;

286 Copy |= maskTrailingOnes(FirstBit);

287 }

288

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

290 unsigned Result =

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

292 return Result < Size ? Result : -1;

293 }

294 }

295 return -1;

296 }

297

298

299

301

302

303

305

306

307

309

310

311

313

314

315

317

318

319

322 }

323

324

325

327

328

329

332 }

333

334

336 Size = 0;

337 Bits.clear();

338 }

339

340

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

342 set_unused_bits(t);

343 Size = N;

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

345 clear_unused_bits();

346 }

347

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

349

350

352 init_words(true);

353 clear_unused_bits();

354 return *this;

355 }

356

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

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

360 return *this;

361 }

362

363

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;

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

393 init_words(false);

394 return *this;

395 }

396

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

399 return *this;

400 }

401

402

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;

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

432 for (auto &Bit : Bits)

433 Bit = ~Bit;

434 clear_unused_bits();

435 return *this;

436 }

437

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

440 return *this;

441 }

442

443

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

447 }

448

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

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

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

459 }

460

462 return (*this)[Idx];

463 }

464

465

467 unsigned OldSize = Size;

468 unsigned NewSize = Size + 1;

469

470

471

473 resize(NewSize, false);

474 else

475 Size = NewSize;

476

477

478 if (Val)

479 set(OldSize);

480 }

481

482

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

486 }

487

488

490 unsigned ThisWords = Bits.size();

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

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

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

494 return true;

495 return false;

496 }

497

498

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

501 return false;

502 unsigned NumWords = Bits.size();

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

504 }

505

507

508

510 unsigned ThisWords = Bits.size();

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

512 unsigned i;

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

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

515

516

517

518

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

520 Bits[i] = 0;

521

522 return *this;

523 }

524

525

527 unsigned ThisWords = Bits.size();

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

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

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

531 return *this;

532 }

533

534

535

537 unsigned ThisWords = Bits.size();

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

539 unsigned i;

540 for (i = 0; i != std::min(ThisWords, 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>

553 ArgTys const &...Args) {

555 std::initializer_list{Args.size()...},

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

557 "consistent sizes");

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

561 Out.clear_unused_bits();

562 return Out;

563 }

564

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

570 return *this;

571 }

572

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

578 return *this;

579 }

580

584 return *this;

585

586 unsigned NumWords = Bits.size();

587 assert(NumWords >= 1);

588

589 wordShr(N / BITWORD_SIZE);

590

591 unsigned BitDistance = N % BITWORD_SIZE;

592 if (BitDistance == 0)

593 return *this;

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617 const BitWord Mask = maskTrailingOnes(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

633 return *this;

634

635 unsigned NumWords = Bits.size();

636 assert(NumWords >= 1);

637

638 wordShl(N / BITWORD_SIZE);

639

640 unsigned BitDistance = N % BITWORD_SIZE;

641 if (BitDistance == 0)

642 return *this;

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667 const BitWord Mask = maskLeadingOnes(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

683 }

684

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

688 }

690

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

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

709 }

710

711

712

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

715 }

716

717

718

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

721 }

722

723

724

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

727 }

728

729private:

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744 void wordShl(uint32_t Count) {

745 if (Count == 0)

746 return;

747

748 uint32_t NumWords = Bits.size();

749

750

751

752

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

754 Bits.begin() + Count);

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

756 clear_unused_bits();

757 }

758

759

760

761

762 void wordShr(uint32_t Count) {

763 if (Count == 0)

764 return;

765

766 uint32_t NumWords = Bits.size();

767

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

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

770 }

771

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

775 }

776

777 unsigned NumBitWords(unsigned S) const {

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

779 }

780

781

782 void set_unused_bits(bool t = true) {

783

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

794 void clear_unused_bits() {

795 set_unused_bits(false);

796 }

797

798 void init_words(bool t) {

799 std::fill(Bits.begin(), Bits.end(), 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(MaskWords, (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

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

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) {

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

829public:

830

833};

834

836 return X.getMemorySize();

837}

838

843 V.invalid();

844 return V;

845 }

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

849 }

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

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

854 }

855};

856}

857

859

861}

862

863#endif

for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))

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

#define LLVM_UNLIKELY(EXPR)

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

This file defines DenseMapInfo traits for DenseMap.

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

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

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

reference & operator=(bool t)

reference(BitVector &b, unsigned Idx)

reference & operator=(reference t)

reference(const reference &)=default

BitVector & operator>>=(unsigned N)

bool test(unsigned Idx) const

void swap(BitVector &RHS)

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 clear()

clear - Removes all bits from the bitvector.

bool test(const BitVector &RHS) const

test - Check if (This - RHS) is zero.

BitVector()=default

BitVector default ctor - Creates an empty bitvector.

bool back() const

Return the last element in the vector.

bool operator!=(const BitVector &RHS) const

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.

int find_first_unset_in(unsigned Begin, unsigned End) const

find_first_unset_in - Returns the index of the first unset bit in the range [Begin,...

size_type count() const

count - Returns the number of bits which are set.

BitVector & operator<<=(unsigned N)

ArrayRef< BitWord > getData() const

const_set_bits_iterator set_bits_end() const

BitVector & reset(unsigned Idx)

const_set_bits_iterator set_iterator

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.

int find_prev_unset(unsigned PriorTo)

find_prev_unset - Returns the index of the first unset bit that precedes the bit at PriorTo.

bool all() const

all - Returns true if all bits are set.

BitVector(unsigned s, bool t=false)

BitVector ctor - Creates a bitvector of specified number of bits.

BitVector & reset(const BitVector &RHS)

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

BitVector & operator|=(const BitVector &RHS)

void pop_back()

Pop one bit from the end of the vector.

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.

int find_last_in(unsigned Begin, unsigned End) const

find_last_in - Returns the index of the last set bit in the range [Begin, End).

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

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

BitVector & reset(unsigned I, unsigned E)

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

bool operator==(const BitVector &RHS) const

int find_next(unsigned Prev) const

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

const_set_bits_iterator_impl< BitVector > const_set_bits_iterator

bool none() const

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

const_set_bits_iterator set_bits_begin() const

iterator_range< const_set_bits_iterator > set_bits() const

BitVector & set(unsigned I, unsigned E)

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

size_type getBitCapacity() const

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

find_first_in - Returns the index of the first set / unset bit, depending on Set, in the range [Begin...

size_type size() const

size - Returns the number of bits in this bitvector.

BitVector & operator^=(const BitVector &RHS)

BitVector & flip(unsigned Idx)

size_type getMemorySize() const

Return the size (in bytes) of the bit vector.

static BitVector & apply(F &&f, BitVector &Out, BitVector const &Arg, ArgTys const &...Args)

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.

BitVector & set(unsigned Idx)

BitVector & operator&=(const BitVector &RHS)

Intersection, union, disjoint union.

int find_first_unset() const

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

int find_last_unset_in(unsigned Begin, unsigned End) const

find_last_unset_in - Returns the index of the last unset bit in the range [Begin, End).

bool operator[](unsigned Idx) const

reference operator[](unsigned Idx)

ForwardIterator for the bits that are set.

const_set_bits_iterator_impl(const BitVectorT &Parent)

bool operator==(const const_set_bits_iterator_impl &Other) const

const_set_bits_iterator_impl(const const_set_bits_iterator_impl &)=default

const_set_bits_iterator_impl & operator++()

const_set_bits_iterator_impl operator++(int)

std::ptrdiff_t difference_type

const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)

bool operator!=(const const_set_bits_iterator_impl &Other) const

std::forward_iterator_tag iterator_category

unsigned operator*() const

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.

constexpr std::underlying_type_t< E > Mask()

Get a bitmask with 1s in all places up to the high-order bit of E's largest value.

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

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

int popcount(T Value) noexcept

Count the number of set bits in a value.

int countr_one(T Value)

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

BitVector::size_type capacity_in_bytes(const BitVector &X)

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.

bool any_of(R &&range, UnaryPredicate P)

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

int countl_zero(T Val)

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

int countl_one(T Value)

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

uint64_t alignTo(uint64_t Size, Align A)

Returns a multiple of A needed to store Size bytes.

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 BitVector getEmptyKey()

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

static unsigned getHashValue(const BitVector &V)

static BitVector getTombstoneKey()

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