14 #ifndef LLVM_ADT_SPARSEBITVECTOR_H 15 #define LLVM_ADT_SPARSEBITVECTOR_H 53 unsigned ElementIndex;
69 if (ElementIndex != RHS.ElementIndex)
72 if (Bits[i] != RHS.Bits[i])
78 return !(*
this == RHS);
98 void set(
unsigned Idx) {
103 bool old =
test(Idx);
115 bool test(
unsigned Idx)
const {
120 unsigned NumBits = 0;
137 unsigned Idx = BITWORDS_PER_ELEMENT -
I - 1;
155 &&
"Word Position outside of element");
158 Copy &= ~0UL << BitPos;
172 bool changed =
false;
174 BitWord old = changed ? 0 : Bits[i];
176 Bits[i] |= RHS.Bits[i];
177 if (!changed && old != Bits[i])
186 if (RHS.Bits[i] & Bits[i])
196 bool changed =
false;
201 BitWord old = changed ? 0 : Bits[i];
203 Bits[i] &= RHS.Bits[i];
207 if (!changed && old != Bits[i])
210 BecameZero = allzero;
219 bool changed =
false;
224 BitWord old = changed ? 0 : Bits[i];
226 Bits[i] &= ~RHS.Bits[i];
230 if (!changed && old != Bits[i])
233 BecameZero = allzero;
246 Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
250 BecameZero = allzero;
254 template <
unsigned ElementSize = 128>
256 using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
257 using ElementListIter =
typename ElementList::iterator;
258 using ElementListConstIter =
typename ElementList::const_iterator;
263 ElementList Elements;
267 mutable ElementListIter CurrElementIter;
271 ElementListIter FindLowerBoundImpl(
unsigned ElementIndex)
const {
278 ElementListIter Begin =
280 ElementListIter End =
283 if (Elements.empty()) {
284 CurrElementIter = Begin;
285 return CurrElementIter;
289 if (CurrElementIter == End)
294 ElementListIter ElementIter = CurrElementIter;
295 if (CurrElementIter->index() == ElementIndex) {
297 }
else if (CurrElementIter->index() > ElementIndex) {
298 while (ElementIter != Begin
299 && ElementIter->index() > ElementIndex)
302 while (ElementIter != End &&
303 ElementIter->index() < ElementIndex)
306 CurrElementIter = ElementIter;
309 ElementListConstIter FindLowerBoundConst(
unsigned ElementIndex)
const {
310 return FindLowerBoundImpl(ElementIndex);
312 ElementListIter FindLowerBound(
unsigned ElementIndex) {
313 return FindLowerBoundImpl(ElementIndex);
318 class SparseBitVectorIterator {
325 ElementListConstIter Iter;
337 void AdvanceToFirstNonZero() {
340 if (BitVector->Elements.empty()) {
344 Iter = BitVector->Elements.begin();
345 BitNumber = Iter->index() * ElementSize;
346 unsigned BitPos = Iter->find_first();
349 Bits = Iter->
word(WordNumber);
354 void AdvanceToNextNonZero() {
358 while (Bits && !(Bits & 1)) {
365 int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
367 if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
372 if (Iter == BitVector->Elements.end()) {
377 BitNumber = Iter->index() * ElementSize;
378 NextSetBitNumber = Iter->find_first();
379 BitNumber += NextSetBitNumber;
381 Bits = Iter->
word(WordNumber);
384 WordNumber = (NextSetBitNumber % ElementSize) /
BITWORD_SIZE;
385 Bits = Iter->
word(WordNumber);
387 BitNumber = Iter->index() * ElementSize;
388 BitNumber += NextSetBitNumber;
394 SparseBitVectorIterator() =
default;
397 bool end =
false):BitVector(RHS) {
398 Iter = BitVector->Elements.begin();
403 AdvanceToFirstNonZero();
407 inline SparseBitVectorIterator& operator++() {
410 AdvanceToNextNonZero();
415 inline SparseBitVectorIterator operator++(
int) {
416 SparseBitVectorIterator tmp = *
this;
426 bool operator==(
const SparseBitVectorIterator &RHS)
const {
428 if (AtEnd && RHS.AtEnd)
432 return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
435 bool operator!=(
const SparseBitVectorIterator &RHS)
const {
436 return !(*
this == RHS);
446 : Elements(RHS.Elements), CurrElementIter(Elements.
begin()) {}
448 : Elements(
std::move(RHS.Elements)), CurrElementIter(Elements.
begin()) {}
460 Elements = RHS.Elements;
461 CurrElementIter = Elements.begin();
465 Elements = std::move(RHS.Elements);
466 CurrElementIter = Elements.begin();
471 bool test(
unsigned Idx)
const {
472 if (Elements.empty())
475 unsigned ElementIndex = Idx / ElementSize;
476 ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);
480 if (ElementIter == Elements.end() ||
481 ElementIter->index() != ElementIndex)
483 return ElementIter->test(Idx % ElementSize);
487 if (Elements.empty())
490 unsigned ElementIndex = Idx / ElementSize;
491 ElementListIter ElementIter = FindLowerBound(ElementIndex);
495 if (ElementIter == Elements.end() ||
496 ElementIter->index() != ElementIndex)
498 ElementIter->reset(Idx % ElementSize);
501 if (ElementIter->empty()) {
503 Elements.erase(ElementIter);
507 void set(
unsigned Idx) {
508 unsigned ElementIndex = Idx / ElementSize;
509 ElementListIter ElementIter;
510 if (Elements.empty()) {
511 ElementIter = Elements.emplace(Elements.end(), ElementIndex);
513 ElementIter = FindLowerBound(ElementIndex);
515 if (ElementIter == Elements.end() ||
516 ElementIter->index() != ElementIndex) {
520 if (ElementIter != Elements.end() &&
521 ElementIter->index() < ElementIndex)
523 ElementIter = Elements.emplace(ElementIter, ElementIndex);
526 CurrElementIter = ElementIter;
528 ElementIter->set(Idx % ElementSize);
532 bool old =
test(Idx);
541 return !(*
this == RHS);
545 ElementListConstIter Iter1 = Elements.begin();
546 ElementListConstIter Iter2 = RHS.Elements.begin();
548 for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
550 if (*Iter1 != *Iter2)
553 return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
561 bool changed =
false;
562 ElementListIter Iter1 = Elements.begin();
563 ElementListConstIter Iter2 = RHS.Elements.begin();
566 if (RHS.Elements.empty())
569 while (Iter2 != RHS.Elements.end()) {
570 if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
571 Elements.insert(Iter1, *Iter2);
574 }
else if (Iter1->index() == Iter2->index()) {
575 changed |= Iter1->unionWith(*Iter2);
582 CurrElementIter = Elements.begin();
591 bool changed =
false;
592 ElementListIter Iter1 = Elements.begin();
593 ElementListConstIter Iter2 = RHS.Elements.begin();
596 if (Elements.empty() && RHS.Elements.empty())
600 while (Iter2 != RHS.Elements.end()) {
601 if (Iter1 == Elements.end()) {
602 CurrElementIter = Elements.begin();
606 if (Iter1->index() > Iter2->index()) {
608 }
else if (Iter1->index() == Iter2->index()) {
610 changed |= Iter1->intersectWith(*Iter2, BecameZero);
612 ElementListIter IterTmp = Iter1;
614 Elements.erase(IterTmp);
620 ElementListIter IterTmp = Iter1;
622 Elements.erase(IterTmp);
626 if (Iter1 != Elements.end()) {
627 Elements.erase(Iter1, Elements.end());
630 CurrElementIter = Elements.begin();
645 bool changed =
false;
646 ElementListIter Iter1 = Elements.begin();
647 ElementListConstIter Iter2 = RHS.Elements.begin();
650 if (Elements.empty() || RHS.Elements.empty())
654 while (Iter2 != RHS.Elements.end()) {
655 if (Iter1 == Elements.end()) {
656 CurrElementIter = Elements.begin();
660 if (Iter1->index() > Iter2->index()) {
662 }
else if (Iter1->index() == Iter2->index()) {
664 changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
666 ElementListIter IterTmp = Iter1;
668 Elements.erase(IterTmp);
677 CurrElementIter = Elements.begin();
693 }
else if (
this == &RHS2) {
700 CurrElementIter = Elements.begin();
701 ElementListConstIter Iter1 = RHS1.Elements.begin();
702 ElementListConstIter Iter2 = RHS2.Elements.begin();
706 if (RHS1.Elements.empty())
710 while (Iter2 != RHS2.Elements.end()) {
711 if (Iter1 == RHS1.Elements.end())
714 if (Iter1->index() > Iter2->index()) {
716 }
else if (Iter1->index() == Iter2->index()) {
717 bool BecameZero =
false;
718 Elements.emplace_back(Iter1->index());
719 Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
725 Elements.push_back(*Iter1++);
730 std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
744 ElementListConstIter Iter1 = Elements.begin();
745 ElementListConstIter Iter2 = RHS.Elements.begin();
748 if (Elements.empty() && RHS.Elements.empty())
752 while (Iter2 != RHS.Elements.end()) {
753 if (Iter1 == Elements.end())
756 if (Iter1->index() > Iter2->index()) {
758 }
else if (Iter1->index() == Iter2->index()) {
759 if (Iter1->intersects(*Iter2))
775 return (Result == RHS);
780 if (Elements.empty())
788 if (Elements.empty())
796 return Elements.empty();
800 unsigned BitCount = 0;
801 for (ElementListConstIter Iter = Elements.begin();
802 Iter != Elements.end();
804 BitCount += Iter->count();
821 template <
unsigned ElementSize>
827 template <
unsigned ElementSize>
830 return LHS->operator|=(RHS);
833 template <
unsigned ElementSize>
836 return LHS->operator&=(RHS);
839 template <
unsigned ElementSize>
847 template <
unsigned ElementSize>
856 template <
unsigned ElementSize>
865 template <
unsigned ElementSize>
875 template <
unsigned ElementSize>
883 for (++bi; bi != be; ++bi) {
892 #endif // LLVM_ADT_SPARSEBITVECTOR_H
const_iterator end(StringRef path)
Get end iterator over path.
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
This class represents lattice values for constants.
bool operator!=(const SparseBitVector &RHS) const
bool intersects(const SparseBitVector< ElementSize > &RHS) const
SparseBitVector & operator=(const SparseBitVector &RHS)
void intersectWithComplement(const SparseBitVector< ElementSize > &RHS1, const SparseBitVector< ElementSize > &RHS2)
int find_next(unsigned Curr) const
find_next - Returns the index of the next set bit starting from the "Curr" bit.
APInt operator &(APInt a, const APInt &b)
bool operator==(const SparseBitVector &RHS) const
SparseBitVectorElement(unsigned Idx)
bool unionWith(const SparseBitVectorElement &RHS)
BitWord word(unsigned Idx) const
bool operator|=(const SparseBitVector &RHS)
bool operator==(const SparseBitVectorElement &RHS) const
unsigned countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the least significant bit to the most stopping at the first 1...
bool test(unsigned Idx) const
bool intersectWithComplement(const SparseBitVectorElement &RHS, bool &BecameZero)
void intersectWithComplement(const SparseBitVector< ElementSize > *RHS1, const SparseBitVector< ElementSize > *RHS2)
APInt operator*(APInt a, uint64_t RHS)
bool intersectWithComplement(const SparseBitVector< ElementSize > *RHS) const
bool operator!=(const SparseBitVectorElement &RHS) const
bool operator|=(SparseBitVector< ElementSize > &LHS, const SparseBitVector< ElementSize > *RHS)
int find_first() const
find_first - Returns the index of the first set bit.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool test_and_set(unsigned Idx)
SparseBitVector(SparseBitVector &&RHS)
unsigned countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the most significant bit to the least stopping at the first 1...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool intersectWith(const SparseBitVectorElement &RHS, bool &BecameZero)
bool intersects(const SparseBitVectorElement &RHS) const
unsigned countPopulation(T Value)
Count the number of set bits in a value.
void intersectWithComplement(const SparseBitVectorElement &RHS1, const SparseBitVectorElement &RHS2, bool &BecameZero)
SparseBitVector is an implementation of a bitvector that is sparse by only storing the elements that ...
static void clear(coro::Shape &Shape)
int find_last() const
find_last - Returns the index of the last set bit.
bool intersectWithComplement(const SparseBitVector &RHS)
bool test_and_set(unsigned Idx)
SparseBitVector(const SparseBitVector &RHS)
SparseBitVector & operator=(SparseBitVector &&RHS)
bool contains(const SparseBitVector< ElementSize > &RHS) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
E & operator &=(E &LHS, E RHS)
SparseBitVectorIterator iterator
This class implements an extremely fast bulk output stream that can only output to a stream...
APInt operator|(APInt a, const APInt &b)
OutputIt copy(R &&Range, OutputIt Out)
bool intersects(const SparseBitVector< ElementSize > *RHS) const
bool test(unsigned Idx) const