[ADT] fix PackedVector crash for long bits

[tuoxie007]

Summary

I noticed that the class PackedVector doesn't work like what it's name says. e.g.

PackedVector<signed, 4> vec(2);

will use 16 bits.

PackedVector<signed, 8> vec(2);

will use 256 bits.

Event when I created a longer bits vector, e.g.

PackedVector<signed, 30> Vec2(8);

There would be a out of index error. Beacause the size which is an unsigned type calculated with 8<<(30-1) is 0.

llvm/include/llvm/ADT/PackedVector.h

 // This won't be necessary if we can specialize members without specializing
 // the parent template.
 template <typename T, unsigned BitNum, typename BitVectorTy>
 class PackedVectorBase<T, BitNum, BitVectorTy, false> {
 protected:
   static T getValue(const BitVectorTy &Bits, unsigned Idx) {
     T val = T();
     for (unsigned i = 0; i != BitNum; ++i)
-      val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
+      val = T(val | ((Bits[(Idx * BitNum) + i] ? 1UL : 0UL) << i));
     return val;
   }
 
   static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
     assert((val >> BitNum) == 0 && "value is too big");
     for (unsigned i = 0; i != BitNum; ++i)
-      Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
+      Bits[(Idx * BitNum) + i] = val & (T(1) << i);
   }
 };
 
 template <typename T, unsigned BitNum, typename BitVectorTy>
 class PackedVectorBase<T, BitNum, BitVectorTy, true> {
 protected:
   static T getValue(const BitVectorTy &Bits, unsigned Idx) {
     T val = T();
     for (unsigned i = 0; i != BitNum-1; ++i)
-      val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
-    if (Bits[(Idx << (BitNum-1)) + BitNum-1])
+      val = T(val | ((Bits[(Idx * BitNum) + i] ? 1UL : 0UL) << i));
+    if (Bits[(Idx * BitNum) + BitNum - 1])
       val = ~val;
     return val;
   }
 
   static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
     if (val < 0) {
       val = ~val;
-      Bits.set((Idx << (BitNum-1)) + BitNum-1);
+      Bits.set((Idx * BitNum) + BitNum - 1);
     }
     assert((val >> (BitNum-1)) == 0 && "value is too big");
     for (unsigned i = 0; i != BitNum-1; ++i)
-      Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
+      Bits[(Idx * BitNum) + i] = val & (T(1) << i);
   }
 };
 
 /// Store a vector of values using a specific number of bits for each
 /// value. Both signed and unsigned types can be used, e.g
 /// @code
 ///   PackedVector<signed, 2> vec;
 /// @endcode
public:
     }
 
     operator T() const {
       return Vec.getValue(Vec.Bits, Idx);
     }
   };
 
   PackedVector() = default;
-  explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) {}
+  explicit PackedVector(unsigned size) : Bits(size * BitNum) {}
 
   bool empty() const { return Bits.empty(); }
 
-  unsigned size() const { return Bits.size() >> (BitNum - 1); }
+  unsigned size() const { return Bits.size() / BitNum; }
 
   void clear() { Bits.clear(); }
 
-  void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); }
+  void resize(unsigned N) { Bits.resize(N * BitNum); }
 
-  void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
+  void reserve(unsigned N) { Bits.reserve(N * BitNum); }
 
   PackedVector &reset() {
     Bits.reset();
     return *this;
   }
 
   void push_back(T val) {
     resize(size()+1);

llvm/unittests/ADT/PackedVectorTest.cpp

TEST(PackedVectorTest, Operation) {
   EXPECT_FALSE(Vec != Vec2);
 
   Vec[1] = 1;
   Vec2[1] = 2;
   Vec |= Vec2;
   EXPECT_EQ(3U, Vec[1]);
 }
 
+TEST(PackedVectorTest, LongBits) {
+  PackedVector<unsigned, 30> Vec1(8);
+  Vec1[0] = 100;
+  EXPECT_EQ(Vec1[0], 100);
+  Vec1[1] = 0x40000000 - 100;
+  EXPECT_EQ(Vec1[1], 0x40000000 - 100);
+
+  PackedVector<signed, 30> Vec2(8);
+  Vec2[7] = -100;
+  EXPECT_EQ(Vec2[7], -100);
+  Vec2[6] = 100 - 0x20000000;
+  EXPECT_EQ(Vec2[6], 100 - 0x20000000);
+}
+
 #ifdef EXPECT_DEBUG_DEATH
 
 TEST(PackedVectorTest, UnsignedValues) {
   PackedVector<unsigned, 2> Vec(1);
   Vec[0] = 0;
   Vec[0] = 1;
   Vec[0] = 2;
   Vec[0] = 3;