Fix assertion in SmallDenseMap constructor with reserve from non-power-of-2 buckets count

[ivafanas]

Summary

SmallDenseMap constructor with reserve gets an arbitrary NumInitBuckets value and passes it below to init method.

If NumInitBuckets is greater then InlineBuckets, then SmallDenseMap initializes to large representation passing NumInitBuckets below to DenseMap initialization. DenseMap::initEmpty method asserts that initial buckets count must be a power of 2.

Proposed solution is to update NumInitBuckets value in SmallDenseMap constructor till the next power of 2. It should satisfy both DenseMap preconditions and required minimum buckets count for reservation.

[atrick]

LGTM. I don't understand how no one has hit the assert. Or maybe they have and just changed their code to workaround it.

It's a little strange that the power-of-2 fix isn't handled directly in SmallDenseMap::init.

Someone might think it's strange that the initial size heuristic does not match DenseMap--but I don't think that matters here.

[ivafanas]

In D129825#3653972, @atrick wrote:

LGTM ...

Could you please help me to commit this?
I do not have commit access to the repo.
Sorry for that :)

[atrick]

In D129825#3654081, @ivafanas wrote:

In D129825#3653972, @atrick wrote:

LGTM ...

Could you please help me to commit this?
I do not have commit access to the repo.
Sorry for that :)

Yeah, but I don't work on LLVM main. It'll take me some time to set things up--not even sure of the current process. Can another reviewer do this quickly?

[dblaikie]

In D129825#3656339, @atrick wrote:

In D129825#3654081, @ivafanas wrote:

In D129825#3653972, @atrick wrote:

LGTM ...

Could you please help me to commit this?
I do not have commit access to the repo.
Sorry for that :)

Yeah, but I don't work on LLVM main. It'll take me some time to set things up--not even sure of the current process. Can another reviewer do this quickly?

Sure, I'll get it

[dzhidzhoev]

Buildbot failure report https://lab.llvm.org/buildbot/#/builders/92/builds/30361

llvm/include/llvm/ADT/DenseMap.h

class SmallDenseMap
   };
 
   /// A "union" of an inline bucket array and the struct representing
   /// a large bucket. This union will be discriminated by the 'Small' bit.
   AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;
 
 public:
   explicit SmallDenseMap(unsigned NumInitBuckets = 0) {
+    if (NumInitBuckets > InlineBuckets)
+      NumInitBuckets = NextPowerOf2(NumInitBuckets - 1);
     init(NumInitBuckets);
   }
 
   SmallDenseMap(const SmallDenseMap &other) : BaseT() {
     init(0);
     copyFrom(other);
   }
 

llvm/unittests/ADT/DenseMapTest.cpp

for (unsigned i = 95; i < 128; ++i)
     map[i] = i;
 
   EXPECT_EQ(33u, map.size());
   // Similar to the previous test, check for a non-existing element, as an
   // indirect check that tombstones have been removed.
   EXPECT_TRUE(map.find(0) == map.end());
 }
 
+TEST(DenseMapCustomTest, SmallDenseMapWithNumBucketsNonPowerOf2) {
+  // Is not power of 2.
+  const unsigned NumInitBuckets = 33;
+  // Power of 2 less then NumInitBuckets.
+  constexpr unsigned InlineBuckets = 4;
+  // Constructor should not trigger assert.
+  SmallDenseMap<int, int, InlineBuckets> map(NumInitBuckets);
+}
+
 TEST(DenseMapCustomTest, TryEmplaceTest) {
   DenseMap<int, std::unique_ptr<int>> Map;
   std::unique_ptr<int> P(new int(2));
   auto Try1 = Map.try_emplace(0, new int(1));
   EXPECT_TRUE(Try1.second);
   auto Try2 = Map.try_emplace(0, std::move(P));
   EXPECT_FALSE(Try2.second);
   EXPECT_EQ(Try1.first, Try2.first);