[llvm][ADT] Implement `BitVector::make`

[jansvoboda11]

Summary

LLVM Programmer’s Manual strongly discourages the use of std::vector<bool> and suggests llvm::BitVector as a possible replacement.

Currently, there's no easy way to create llvm::BitVector with statically known bit pattern. Absence of convenient functionality like this may sway people to use std::vector<bool> instead.

This patch adds new std::initializer_list-based named constructor that can serve this purpose.

[dexonsmith]

It might be awkward to add this new ambiguity. I wonder if we really want to copy that from std::vector<bool>, which doesn't have a great API for bitsets anyway. @dblaikie, any thoughts?

I'm curious which current users of std::vector<bool> (if any) need this. An alternative would be to add a static function with a good name:

class BitVector {
  static BitVector getBits(std::initializer_list<bool> Values);
};
// later:
BitVector BV = BitVector::getBits({false, true});

Or maybe getFromInitializerList() would be more clear.

llvm/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

419–422

I assume this (and other changes here) are because there's a new constructor ambiguity?

[dblaikie]

In D117114#3238494, @dexonsmith wrote:

It might be awkward to add this new ambiguity. I wonder if we really want to copy that from std::vector<bool>, which doesn't have a great API for bitsets anyway. @dblaikie, any thoughts?

Re: the ambiguity: We could pre-empt that in a separate commit by making the ctor "explicit" - honestly I think we shouldn't be using {} to call user-defined ctors that aren't representative of/"Feel like" conversions. (wouldn't mind that as a broad style statement for LLVM and/or in the form of "mark multi-arg ctors explicit unless they're intentionally converting/structural constructors".

What aspect of "not greatness" API design do you mean - having both the (unsigned bool) and init list ctors at the same time? I think with the former being marked as explicit it's /probably/ OK to me? () does "interesting" things, {} represents the value in some sense.

I wouldn't object to a named ctor either, though. (for either case - though I sort of feel like the existing (unsigned, bool) is the one that could use a name moreso than the new one (if the new one is only via init list, at least - if you could spell the new one as "SV(true, false, true, true, ...)" yeah, maybe having a name would be good))

[jansvoboda11]

In D117114#3238494, @dexonsmith wrote:

It might be awkward to add this new ambiguity. I wonder if we really want to copy that from std::vector<bool>, which doesn't have a great API for bitsets anyway. @dblaikie, any thoughts?

Since people are used to such constructors from the standard library and ADT as well (e.g. SmallVector), I think it would be good to maintain consistency.

Though I'm okay with static factory function... I like BitVector::make({true, false, true}).

I'm curious which current users of std::vector<bool> (if any) need this.

From a quick search, I can see two users at this moment: clang/unittests/Lex/HeaderSearchTest.cpp and flang/unittests/Runtime/Reduction.cpp. Yes, those are "only" unit tests, but I can see myself choosing std::vector<bool> over llvm::BitVector just because it's much easier to match/compare in tests. The last thing I want to do in unit tests is to fight with the API of some container.

In D117114#3239411, @dblaikie wrote:

Re: the ambiguity: We could pre-empt that in a separate commit by making the ctor "explicit" - honestly I think we shouldn't be using {} to call user-defined ctors that aren't representative of/"Feel like" conversions. (wouldn't mind that as a broad style statement for LLVM and/or in the form of "mark multi-arg ctors explicit unless they're intentionally converting/structural constructors".

Maybe I'm misunderstanding you, but the existing constructor already is marked as explicit and that doesn't make brace initialization invalid. Did you have something else in mind?

llvm/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

419–422

That's correct. Without these changes, the new constructor would be called instead, implicitly converting the unsigned argument to bool.

[dexonsmith]

In D117114#3240161, @jansvoboda11 wrote:

In D117114#3238494, @dexonsmith wrote:

It might be awkward to add this new ambiguity. I wonder if we really want to copy that from std::vector<bool>, which doesn't have a great API for bitsets anyway. @dblaikie, any thoughts?

Since people are used to such constructors from the standard library and ADT as well (e.g. SmallVector), I think it would be good to maintain consistency.

My general point is that for a bitset data structure, std::bitset and boost::dynamic_bitset are more compelling data structures for matching APIs than is std::vector<bool>. (BTW, I agree supporting unit tests well is important; wasn't intending to argue otherwise.)

In D117114#3239411, @dblaikie wrote:

In D117114#3238494, @dexonsmith wrote:

What aspect of "not greatness" API design do you mean - having both the (unsigned bool) and init list ctors at the same time? I think with the former being marked as explicit it's /probably/ OK to me? () does "interesting" things, {} represents the value in some sense.

Yeah, it's the ambiguity on {} that seemed awkward to me; and maybe it's not that bad after all. As long as the interesting behaviour on () is not going to change the meaning of existing code then probably it's okay as-is.

llvm/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

419–422

Does this simpler change also work?

[dblaikie]

In D117114#3239411, @dblaikie wrote:

Re: the ambiguity: We could pre-empt that in a separate commit by making the ctor "explicit" - honestly I think we shouldn't be using {} to call user-defined ctors that aren't representative of/"Feel like" conversions. (wouldn't mind that as a broad style statement for LLVM and/or in the form of "mark multi-arg ctors explicit unless they're intentionally converting/structural constructors".

Maybe I'm misunderstanding you, but the existing constructor already is marked as explicit and that doesn't make brace initialization invalid. Did you have something else in mind?

Right right - nevermind me there. Not sure what I was thinking. Thanks for the correction.

I don't have super strong feelings here - but yeah, does seem a bit close. What're the other APIs like by comparison that @dexonsmith has in mind/is suggesting as alternatives? Maybe a quick summary of how similar operations are spelled with different APIs might be good to consider what way we should go.

[jansvoboda11]

In D117114#3249405, @dblaikie wrote:

What're the other APIs like by comparison that @dexonsmith has in mind/is suggesting as alternatives? Maybe a quick summary of how similar operations are spelled with different APIs might be good to consider what way we should go.

I didn't find any data structures in LLVM/Clang with static member functions that take std::initializer_list and create new instance.

---

Both std::bitset and boost::dynamic_bitset have constructors that take std::string:

std::bitset<8> x(std::string("01010101"))

Even if we used StringRef instead, I don't like that: it requires extra input validation.

---

Additionally, std::bitset supports unsigned constructor:

std::bitset<8> x(0b01010101)

That conflicts with our existing (unsigned s, bool t = false) constructor though.

---

Another alternative would be a free factory function, similar to make_pair, make_optional, makeIntrusiveRefCnt etc.:

auto x = makeBitVector({true, false, true, false, true})

---

I'm starting to think the most sensible approach would be either llvm::BitVector::make({true, false, true}) or llvm::makeBitVector({true, false, true}).
While I was able to resolve the constructor ambiguity upstream, downstream projects that call llvm::BitVector{unsigned, bool} might get into trouble (i.e. hard to track down bugs) when they update to newer LLVM versions.

llvm/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

419–422

No, this is a default member initializer, which can only be brace or equals initializer.

[dblaikie]

In D117114#3254316, @jansvoboda11 wrote:

In D117114#3249405, @dblaikie wrote:

What're the other APIs like by comparison that @dexonsmith has in mind/is suggesting as alternatives? Maybe a quick summary of how similar operations are spelled with different APIs might be good to consider what way we should go.

I didn't find any data structures in LLVM/Clang with static member functions that take std::initializer_list and create new instance.

---

Both std::bitset and boost::dynamic_bitset have constructors that take std::string:

std::bitset<8> x(std::string("01010101"))

Even if we used StringRef instead, I don't like that: it requires extra input validation.

---

Additionally, std::bitset supports unsigned constructor:

std::bitset<8> x(0b01010101)

That conflicts with our existing (unsigned s, bool t = false) constructor though.

---

Another alternative would be a free factory function, similar to make_pair, make_optional, makeIntrusiveRefCnt etc.:

auto x = makeBitVector({true, false, true, false, true})

---

I'm starting to think the most sensible approach would be either llvm::BitVector::make({true, false, true}) or llvm::makeBitVector({true, false, true}).
While I was able to resolve the constructor ambiguity upstream, downstream projects that call llvm::BitVector{unsigned, bool} might get into trouble (i.e. hard to track down bugs) when they update to newer LLVM versions.

Yeah, thanks for the summary!

Yeah, seems there's enough existing users of the (unsigned, bool) API that without making it invalid it'd be hard to restructure things to get in a better state, so probably a "named constructor"/factory function would be the best thing at the moment.

[dexonsmith]

Thanks for doing the legwork; SGTM too.

[jansvoboda11]

Use named constructor instead

[dblaikie]

Looks like this addresses @dexonsmith's concerns & sounds good to me.

[dexonsmith]

LGTM too.

llvm/include/llvm/ADT/BitVector.h

 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
+#include <initializer_list>
 #include <utility>
 
 namespace llvm {
 
 /// ForwardIterator for the bits that are set.
 /// Iterators get invalidated when resize / reserve is called.
 template <typename BitVectorT> class const_set_bits_iterator_impl {
   const BitVectorT &Parent;
public:
   /// BitVector ctor - Creates a bitvector of specified number of bits. All
   /// bits are initialized to the specified value.
   explicit BitVector(unsigned s, bool t = false)
       : Bits(NumBitWords(s), 0 - (BitWord)t), Size(s) {
     if (t)
       clear_unused_bits();
   }
 
+  /// Creates a bitvector with the specified values.
+  BitVector(std::initializer_list<bool> Values) : BitVector(Values.size()) {
+    unsigned Idx = 0;
+    for (bool Value : Values)
+      (*this)[Idx++] = Value;
+  }
+
   /// empty - Tests whether there are no bits in this bitvector.
   bool empty() const { return Size == 0; }
 
   /// size - Returns the number of bits in this bitvector.
   size_type size() const { return Size; }
 
   /// count - Returns the number of bits which are set.
   size_type count() const {

llvm/include/llvm/ADT/SmallBitVector.h

 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>
 #include <cstddef>
 #include <cstdint>
+#include <initializer_list>
 #include <limits>
 #include <utility>
 
 namespace llvm {
 
 /// This is a 'bitvector' (really, a variable-sized bit array), optimized for
 /// the case when the array is small. It contains one pointer-sized field, which
 /// is directly used as a plain collection of bits when possible, or as a
public:
   /// to the specified value.
   explicit SmallBitVector(unsigned s, bool t = false) {
     if (s <= SmallNumDataBits)
       switchToSmall(t ? ~uintptr_t(0) : 0, s);
     else
       switchToLarge(new BitVector(s, t));
   }
 
+  /// Creates a bitvector with the specified values.
+  SmallBitVector(std::initializer_list<bool> Values)
+      : SmallBitVector(Values.size()) {
+    unsigned Idx = 0;
+    for (bool Value : Values)
+      (*this)[Idx++] = Value;
+  }
+
   /// SmallBitVector copy ctor.
   SmallBitVector(const SmallBitVector &RHS) {
     if (RHS.isSmall())
       X = RHS.X;
     else
       switchToLarge(new BitVector(*RHS.getPointer()));
   }
 

llvm/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

 #ifndef NDEBUG
   /// If bit I is set, this rule set contains a rule that may handle (predicate
   /// or perform an action upon (or both)) the type index I. The uncertainty
   /// comes from free-form rules executing user-provided lambda functions. We
   /// conservatively assume such rules do the right thing and cover all type
   /// indices. The bitset is intentionally 1 bit wider than it absolutely needs
   /// to be to distinguish such cases from the cases where all type indices are
   /// individually handled.
-  SmallBitVector TypeIdxsCovered{MCOI::OPERAND_LAST_GENERIC -
-                                 MCOI::OPERAND_FIRST_GENERIC + 2};
-  SmallBitVector ImmIdxsCovered{MCOI::OPERAND_LAST_GENERIC_IMM -
-                                MCOI::OPERAND_FIRST_GENERIC_IMM + 2};
+  SmallBitVector TypeIdxsCovered = SmallBitVector(
+      MCOI::OPERAND_LAST_GENERIC - MCOI::OPERAND_FIRST_GENERIC + 2);
+  SmallBitVector ImmIdxsCovered = SmallBitVector(
+      MCOI::OPERAND_LAST_GENERIC_IMM - MCOI::OPERAND_FIRST_GENERIC_IMM + 2);
 #endif
 
   unsigned typeIdx(unsigned TypeIdx) {
     assert(TypeIdx <=
                (MCOI::OPERAND_LAST_GENERIC - MCOI::OPERAND_FIRST_GENERIC) &&
            "Type Index is out of bounds");
 #ifndef NDEBUG
     TypeIdxsCovered.set(TypeIdx);

llvm/lib/CodeGen/MachineCheckDebugify.cpp

bool runOnModule(Module &M) override {
     auto getDebugifyOperand = [&](unsigned Idx) -> unsigned {
       return mdconst::extract<ConstantInt>(NMD->getOperand(Idx)->getOperand(0))
           ->getZExtValue();
     };
     assert(NMD->getNumOperands() == 2 &&
            "llvm.mir.debugify should have exactly 2 operands!");
     unsigned NumLines = getDebugifyOperand(0);
     unsigned NumVars = getDebugifyOperand(1);
-    BitVector MissingLines{NumLines, true};
-    BitVector MissingVars{NumVars, true};
+    BitVector MissingLines(NumLines, true);
+    BitVector MissingVars(NumVars, true);
 
     for (Function &F : M.functions()) {
       MachineFunction *MF = MMI.getMachineFunction(F);
       if (!MF)
         continue;
       for (MachineBasicBlock &MBB : *MF) {
         // Find missing lines.
         // TODO: Avoid meta instructions other than dbg_val.

llvm/lib/Target/X86/ImmutableGraph.h

public:
 
   // FIXME: Could NodeSet and EdgeSet be templated to share code?
   class NodeSet {
     const ImmutableGraph &G;
     BitVector V;
 
   public:
     NodeSet(const ImmutableGraph &G, bool ContainsAll = false)
-        : G{G}, V{static_cast<unsigned>(G.nodes_size()), ContainsAll} {}
+        : G{G}, V(static_cast<unsigned>(G.nodes_size()), ContainsAll) {}
     bool insert(const Node &N) {
       size_type Idx = G.getNodeIndex(N);
       bool AlreadyExists = V.test(Idx);
       V.set(Idx);
       return !AlreadyExists;
     }
     void erase(const Node &N) {
       size_type Idx = G.getNodeIndex(N);
public:
   };
 
   class EdgeSet {
     const ImmutableGraph &G;
     BitVector V;
 
   public:
     EdgeSet(const ImmutableGraph &G, bool ContainsAll = false)
-        : G{G}, V{static_cast<unsigned>(G.edges_size()), ContainsAll} {}
+        : G{G}, V(static_cast<unsigned>(G.edges_size()), ContainsAll) {}
     bool insert(const Edge &E) {
       size_type Idx = G.getEdgeIndex(E);
       bool AlreadyExists = V.test(Idx);
       V.set(Idx);
       return !AlreadyExists;
     }
     void erase(const Edge &E) {
       size_type Idx = G.getEdgeIndex(E);

llvm/lib/Transforms/Utils/Debugify.cpp

bool checkDebugifyMetadata(Module &M,
   unsigned OriginalNumVars = getDebugifyOperand(1);
   bool HasErrors = false;
 
   // Track debug info loss statistics if able.
   DebugifyStatistics *Stats = nullptr;
   if (StatsMap && !NameOfWrappedPass.empty())
     Stats = &StatsMap->operator[](NameOfWrappedPass);
 
-  BitVector MissingLines{OriginalNumLines, true};
-  BitVector MissingVars{OriginalNumVars, true};
+  BitVector MissingLines(OriginalNumLines, true);
+  BitVector MissingVars(OriginalNumVars, true);
   for (Function &F : Functions) {
     if (isFunctionSkipped(F))
       continue;
 
     // Find missing lines.
     for (Instruction &I : instructions(F)) {
       if (isa<DbgValueInst>(&I))
         continue;

llvm/unittests/ADT/BitVectorTest.cpp

 // Test fixture
 template <typename T>
 class BitVectorTest : public ::testing::Test { };
 
 // Test both BitVector and SmallBitVector with the same suite of tests.
 typedef ::testing::Types<BitVector, SmallBitVector> BitVectorTestTypes;
 TYPED_TEST_SUITE(BitVectorTest, BitVectorTestTypes, );
 
+TYPED_TEST(BitVectorTest, InitializerListCtor) {
+  TypeParam Vec{true, false, true, true};
+  EXPECT_EQ(4U, Vec.size());
+  EXPECT_EQ(true, Vec[0]);
+  EXPECT_EQ(false, Vec[1]);
+  EXPECT_EQ(true, Vec[2]);
+  EXPECT_EQ(true, Vec[3]);
+}
+
 TYPED_TEST(BitVectorTest, TrivialOperation) {
   TypeParam Vec;
   EXPECT_EQ(0U, Vec.count());
   EXPECT_EQ(0U, Vec.size());
   EXPECT_FALSE(Vec.any());
   EXPECT_TRUE(Vec.all());
   EXPECT_TRUE(Vec.none());
   EXPECT_TRUE(Vec.empty());