Introduce BitSet: A BitVector based class behaving like std::set/DenseSet

[dblaikie]

Test cases?
Got a usage in mind?

[MatzeB]

Implement insert() and erase() in SmallBitVector as well and add tests.

[MatzeB]

In D18578#386549, @dblaikie wrote:

Test cases?
Got a usage in mind?

The concrete usage I have in mind is using a BitVector for Set type parameter of a SetVector. This is in the context of http://reviews.llvm.org/D18427.

And if you think about it: Even though the class is called a BitVector most of the time you really use it more like a set where you insert and remove elements from and not like a vector there is no BitVector::push_back() or iterators after all. So having operations compatible with std::set and DenseSet makes sense.

[MatzeB]

Also added the count(X) method. count(X) is another operand from std::set/DenseSet and was required to get all of SetVector<> working.

[MatzeB]

New revision introducing a new proxy class acting like a set but backed by a BitVector.

Also comes with more extensive unittests for set classes.

[dblaikie]

This seems to have strange behavior - returning the size/empty status of
the BitVector for the BitSets operations is probably wrong, no? (the
BitVector's length is the length of the field, not the number of set (1)
bits in it)

[MatzeB]

In D18578#400148, @dblaikie wrote:

This seems to have strange behavior - returning the size/empty status of
the BitVector for the BitSets operations is probably wrong, no? (the
BitVector's length is the length of the field, not the number of set (1)
bits in it)

BitSet::size() should return the number of elements in the set which corresponds to the number of set bits in the bitvector which should be BitVector::count().

empty() checks BitSet::size() against 0 which should be equivalent to BitVector::count() == 0.

[MatzeB]

Address review comments.

[MatzeB]

Address review comments.

[mehdi_amini]

It is nice to have a separate BitSet instead of adding the API to the BitVector, but at the same time I wonder about some inefficiencies due the wrapping here? See inline for instance.

include/llvm/ADT/BitSet.h

111 ↗

(On Diff #53819)

Again that's 3 queries to the vector instead of one, I wonder if the compiler CSE perfectly the generated code.

57 ↗

(On Diff #53816)

This is requerying the Vector uselessly here (or post-increment is not good anyway but still).

64 ↗

(On Diff #53816)

Could the iterator be lazy and not do anything on creation? (that would solve the point above by the way)

[MatzeB]

Address review comments.

include/llvm/ADT/BitSet.h

111 ↗

(On Diff #53819)

The new version of the code should avoid the advance() calls in the iterator. This is just the way the STL set APIs work, unfortunately this is will always be an extra load and pair<> creation even if most users don't need the return value. You can only hope the compiler inlines properly and throws the return value and extra queries away.

[MatzeB]

ping

[MatzeB]

Abandoning for lack of progress and use case. The motivating pass simply uses a combination of BitVector+Set instead of a SetVector now.

include/llvm/ADT/BitVector.h

BitVector &reset(unsigned I, unsigned E) {
 
     BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
     if (I < E)
       Bits[I / BITWORD_SIZE] &= ~PostfixMask;
 
     return *this;
   }
 
+  /// Set bit \p Idx to true. This function allows BitVector to be used in
+  /// contexts expecting std::set/DenseSet like API.
+  std::pair<reference, bool> insert(unsigned Idx) {
+    reference ref(*this, Idx);
+    bool Res = !ref;
+    ref = true;
+    return std::make_pair(ref, Res);
+  }
+
+  /// Clear bit \p Idx. This function allows BitVector to be used in contexts
+  /// expecting std::set/DenseSet like API.
+  bool erase(unsigned Idx) {
+    bool Res = test(Idx);
+    reset(Idx);
+    return Res;
+  }
+
   BitVector &flip() {
     for (unsigned i = 0; i < NumBitWords(size()); ++i)
       Bits[i] = ~Bits[i];
     clear_unused_bits();
     return *this;
   }
 
   BitVector &flip(unsigned Idx) {