Add TinyPtrVector support for general pointer-like things.

[atrick]

Summary

In particular, make TinyPtrVector<PtrIntPair<T *, 1>> work. Remove all
unnecessary assumptions that the element type has a formal "null"
representation. The important property to maintain is that
default-constructed element type has the same internal representation
as the default-constructed PointerUnion (all zero bits).

Remove the incorrect recursive behavior from
PointerUnion::isNull. This was never generally correct because it only
recursed over the first type parameter. With variadic templates it's
completely unnecessary.

[atrick]

@rsmith, you were the last developer to make salient changes here. Since you're already familiar, any chance you can review this? If not, I'll broadcast a plea.

[dexonsmith]

LGTM, with a minor suggestion inline.

llvm/include/llvm/ADT/TinyPtrVector.h

350–351

I think this can still be else if; no need for the extra nesting.

[atrick]

I removed the extra if-block that I accidentally created.
I added a cast to fix a type mismatch that I meant to include in the last patch.

     assert(
-        get<First>() == this->Val.getPointer() &&
+        PointerLikeTypeTraits<First>::getAsVoidPointer(get<First>())
+        == this->Val.getPointer() &&

[atrick]

For the record, I see two failures after updating LLVM
Failing Tests (2):

LLVM :: CodeGen/PowerPC/aix-xcoff-basic.ll
LLVM :: CodeGen/PowerPC/aix-xcoff-common.ll

But they occur with or without these changes.

[atrick]

I forgot to link the commit message back to this review.
Closing with commit 861b371e1386b6ac1069c9aa3050f7074fb64516

llvm/include/llvm/ADT/PointerUnion.h

 template <typename... PTs>
 class PointerUnion
     : public pointer_union_detail::PointerUnionMembers<
           PointerUnion<PTs...>,
           PointerIntPair<
               void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int,
               pointer_union_detail::PointerUnionUIntTraits<PTs...>>,
           0, PTs...> {
-  // The first type is special in some ways, but we don't want PointerUnion to
-  // be a 'template <typename First, typename ...Rest>' because it's much more
-  // convenient to have a name for the whole pack. So split off the first type
-  // here.
+  // The first type is special because we want to directly cast a pointer to a
+  // default-initialized union to a pointer to the first type. But we don't
+  // want PointerUnion to be a 'template <typename First, typename ...Rest>'
+  // because it's much more convenient to have a name for the whole pack. So
+  // split off the first type here.
   using First = typename pointer_union_detail::GetFirstType<PTs...>::type;
   using Base = typename PointerUnion::PointerUnionMembers;
 
 public:
   PointerUnion() = default;
 
   PointerUnion(std::nullptr_t) : PointerUnion() {}
   using Base::Base;
 
   /// Test if the pointer held in the union is null, regardless of
   /// which type it is.
-  bool isNull() const {
-    // Convert from the void* to one of the pointer types, to make sure that
-    // we recursively strip off low bits if we have a nested PointerUnion.
-    return !PointerLikeTypeTraits<First>::getFromVoidPointer(
-        this->Val.getPointer());
-  }
+  bool isNull() const { return !this->Val.getPointer(); }
 
   explicit operator bool() const { return !isNull(); }
 
   /// Test if the Union currently holds the type matching T.
   template <typename T> int is() const {
     constexpr int Index = pointer_union_detail::TypeIndex<T, PTs...>::Index;
     static_assert(Index < sizeof...(PTs),
                   "PointerUnion::is<T> given type not in the union");
First const *getAddrOfPtr1() const {
     return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
   }
 
   /// If the union is set to the first pointer type get an address pointing to
   /// it.
   First *getAddrOfPtr1() {
     assert(is<First>() && "Val is not the first pointer");
     assert(
-        get<First>() == this->Val.getPointer() &&
+        PointerLikeTypeTraits<First>::getAsVoidPointer(get<First>())
+        == this->Val.getPointer() &&
         "Can't get the address because PointerLikeTypeTraits changes the ptr");
     return const_cast<First *>(
         reinterpret_cast<const First *>(this->Val.getAddrOfPointer()));
   }
 
   /// Assignment from nullptr which just clears the union.
   const PointerUnion &operator=(std::nullptr_t) {
     this->Val.initWithPointer(nullptr);

llvm/include/llvm/ADT/TinyPtrVector.h

 ///
 /// NOTE: This container doesn't allow you to store a null pointer into it.
 ///
 template <typename EltTy>
 class TinyPtrVector {
 public:
   using VecTy = SmallVector<EltTy, 4>;
   using value_type = typename VecTy::value_type;
+  // EltTy must be the first pointer type so that is<EltTy> is true for the
+  // default-constructed PtrUnion. This allows an empty TinyPtrVector to
+  // naturally vend a begin/end iterator of type EltTy* without an additional
+  // check for the empty state.
   using PtrUnion = PointerUnion<EltTy, VecTy *>;
 
 private:
   PtrUnion Val;
 
 public:
   TinyPtrVector() = default;
 
TinyPtrVector &operator=(TinyPtrVector &&RHS) {
 
     // If this vector has been allocated on the heap, re-use it if cheap. If it
     // would require more copying, just delete it and we'll steal the other
     // side.
     if (VecTy *V = Val.template dyn_cast<VecTy*>()) {
       if (RHS.Val.template is<EltTy>()) {
         V->clear();
         V->push_back(RHS.front());
-        RHS.Val = (EltTy)nullptr;
+        RHS.Val = EltTy();
         return *this;
       }
       delete V;
     }
 
     Val = RHS.Val;
-    RHS.Val = (EltTy)nullptr;
+    RHS.Val = EltTy();
     return *this;
   }
 
   TinyPtrVector(std::initializer_list<EltTy> IL)
       : Val(IL.size() == 0
                 ? PtrUnion()
                 : IL.size() == 1 ? PtrUnion(*IL.begin())
                                  : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
public:
   }
 
   const_reverse_iterator rend() const {
     return const_reverse_iterator(begin());
   }
 
   EltTy operator[](unsigned i) const {
     assert(!Val.isNull() && "can't index into an empty vector");
-    if (EltTy V = Val.template dyn_cast<EltTy>()) {
+    if (Val.template is<EltTy>()) {
       assert(i == 0 && "tinyvector index out of range");
-      return V;
+      return Val.template get<EltTy>();
     }
 
     assert(i < Val.template get<VecTy*>()->size() &&
            "tinyvector index out of range");
     return (*Val.template get<VecTy*>())[i];
   }
 
   EltTy front() const {
     assert(!empty() && "vector empty");
-    if (EltTy V = Val.template dyn_cast<EltTy>())
-      return V;
+    if (Val.template is<EltTy>())
+      return Val.template get<EltTy>();
     return Val.template get<VecTy*>()->front();
   }
 
   EltTy back() const {
     assert(!empty() && "vector empty");
-    if (EltTy V = Val.template dyn_cast<EltTy>())
-      return V;
+    if (Val.template is<EltTy>())
+      return Val.template get<EltTy>();
     return Val.template get<VecTy*>()->back();
   }
 
   void push_back(EltTy NewVal) {
-    assert(NewVal && "Can't add a null value");
-
     // If we have nothing, add something.
     if (Val.isNull()) {
       Val = NewVal;
+      assert(!Val.isNull() && "Can't add a null value");
       return;
     }
 
     // If we have a single value, convert to a vector.
-    if (EltTy V = Val.template dyn_cast<EltTy>()) {
+    if (Val.template is<EltTy>()) {
+      EltTy V = Val.template get<EltTy>();
       Val = new VecTy();
       Val.template get<VecTy*>()->push_back(V);
     }
 
     // Add the new value, we know we have a vector.
     Val.template get<VecTy*>()->push_back(NewVal);
   }
 
   void pop_back() {
     // If we have a single value, convert to empty.
     if (Val.template is<EltTy>())
       Val = (EltTy)nullptr;
     else if (VecTy *Vec = Val.template get<VecTy*>())
       Vec->pop_back();
   }
 
   void clear() {
     // If we have a single value, convert to empty.
     if (Val.template is<EltTy>()) {
-      Val = (EltTy)nullptr;
+      Val = EltTy();
     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
       // If we have a vector form, just clear it.
       Vec->clear();
     }
     // Otherwise, we're already empty.
   }
 
   iterator erase(iterator I) {
     assert(I >= begin() && "Iterator to erase is out of bounds.");
     assert(I < end() && "Erasing at past-the-end iterator.");
 
     // If we have a single value, convert to empty.
     if (Val.template is<EltTy>()) {
       if (I == begin())
-        Val = (EltTy)nullptr;
+        Val = EltTy();
     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
       // multiple items in a vector; just do the erase, there is no
       // benefit to collapsing back to a pointer
       return Vec->erase(I);
     }
     return end();
   }
 
   iterator erase(iterator S, iterator E) {
     assert(S >= begin() && "Range to erase is out of bounds.");
     assert(S <= E && "Trying to erase invalid range.");
     assert(E <= end() && "Trying to erase past the end.");
 
     if (Val.template is<EltTy>()) {
       if (S == begin() && S != E)
-        Val = (EltTy)nullptr;
+        Val = EltTy();
     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
       return Vec->erase(S, E);
     }
     return end();
   }
 
   iterator insert(iterator I, const EltTy &Elt) {
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
     if (I == end()) {
       push_back(Elt);
       return std::prev(end());
     }
     assert(!Val.isNull() && "Null value with non-end insert iterator.");
-    if (EltTy V = Val.template dyn_cast<EltTy>()) {
+    if (Val.template is<EltTy>()) {
+      EltTy V = Val.template get<EltTy>();
       assert(I == begin());
       Val = Elt;
       push_back(V);
       return begin();
     }
 
     return Val.template get<VecTy*>()->insert(I, Elt);
   }
iterator insert(iterator I, ItTy From, ItTy To) {
     ptrdiff_t Offset = I - begin();
     if (Val.isNull()) {
       if (std::next(From) == To) {
         Val = *From;
         return begin();
       }
 
       Val = new VecTy();
-    } else if (EltTy V = Val.template dyn_cast<EltTy>()) {
+    } else if (Val.template is<EltTy>()) {
+      EltTy V = Val.template get<EltTy>();
       Val = new VecTy();
       Val.template get<VecTy*>()->push_back(V);
     }
     return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
   }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_TINYPTRVECTOR_H

llvm/unittests/ADT/PointerUnionTest.cpp

 //===- llvm/unittest/ADT/PointerUnionTest.cpp - Optional unit tests -------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/PointerUnion.h"
 #include "gtest/gtest.h"
 using namespace llvm;
 
 namespace {
 
 typedef PointerUnion<int *, float *> PU;
+typedef PointerUnion3<int *, float *, long long *> PU3;
+typedef PointerUnion4<int *, float *, long long *, double *> PU4;
 
 struct PointerUnionTest : public testing::Test {
   float f;
   int i;
+  double d;
+  long long l;
 
   PU a, b, c, n;
-
-  PointerUnionTest() : f(3.14f), i(42), a(&f), b(&i), c(&i), n() {}
+  PU3 i3, f3, l3;
+  PU4 i4, f4, l4, d4;
+  PU4 i4null, f4null, l4null, d4null;
+
+  PointerUnionTest() : f(3.14f), i(42), d(3.14), l(42),
+                       a(&f), b(&i), c(&i), n(),
+                       i3(&i), f3(&f), l3(&l),
+                       i4(&i), f4(&f), l4(&l), d4(&d),
+                       i4null((int *)nullptr), f4null((float *)nullptr),
+                       l4null((long long *) nullptr),
+                       d4null((double *)nullptr)
+  {}
 };
 
 TEST_F(PointerUnionTest, Comparison) {
   EXPECT_TRUE(a == a);
   EXPECT_FALSE(a != a);
   EXPECT_TRUE(a != b);
   EXPECT_FALSE(a == b);
   EXPECT_TRUE(b == c);
   EXPECT_FALSE(b != c);
   EXPECT_TRUE(b != n);
   EXPECT_FALSE(b == n);
+  EXPECT_TRUE(i3 == i3);
+  EXPECT_FALSE(i3 != i3);
+  EXPECT_TRUE(i3 != f3);
+  EXPECT_TRUE(f3 != l3);
+  EXPECT_TRUE(i4 == i4);
+  EXPECT_FALSE(i4 != i4);
+  EXPECT_TRUE(i4 != f4);
+  EXPECT_TRUE(i4 != l4);
+  EXPECT_TRUE(f4 != l4);
+  EXPECT_TRUE(l4 != d4);
+  EXPECT_TRUE(i4null != f4null);
+  EXPECT_TRUE(i4null != l4null);
+  EXPECT_TRUE(i4null != d4null);
 }
 
 TEST_F(PointerUnionTest, Null) {
   EXPECT_FALSE(a.isNull());
   EXPECT_FALSE(b.isNull());
   EXPECT_TRUE(n.isNull());
   EXPECT_FALSE(!a);
   EXPECT_FALSE(!b);
   EXPECT_TRUE(!n);
   // workaround an issue with EXPECT macros and explicit bool
   EXPECT_TRUE((bool)a);
   EXPECT_TRUE((bool)b);
   EXPECT_FALSE(n);
 
   EXPECT_NE(n, b);
   EXPECT_EQ(b, c);
   b = nullptr;
   EXPECT_EQ(n, b);
   EXPECT_NE(b, c);
+  EXPECT_FALSE(i3.isNull());
+  EXPECT_FALSE(f3.isNull());
+  EXPECT_FALSE(l3.isNull());
+  EXPECT_FALSE(i4.isNull());
+  EXPECT_FALSE(f4.isNull());
+  EXPECT_FALSE(l4.isNull());
+  EXPECT_FALSE(d4.isNull());
+  EXPECT_TRUE(i4null.isNull());
+  EXPECT_TRUE(f4null.isNull());
+  EXPECT_TRUE(l4null.isNull());
+  EXPECT_TRUE(d4null.isNull());
 }
 
 TEST_F(PointerUnionTest, Is) {
   EXPECT_FALSE(a.is<int *>());
   EXPECT_TRUE(a.is<float *>());
   EXPECT_TRUE(b.is<int *>());
   EXPECT_FALSE(b.is<float *>());
   EXPECT_TRUE(n.is<int *>());
   EXPECT_FALSE(n.is<float *>());
+  EXPECT_TRUE(i3.is<int *>());
+  EXPECT_TRUE(f3.is<float *>());
+  EXPECT_TRUE(l3.is<long long *>());
+  EXPECT_TRUE(i4.is<int *>());
+  EXPECT_TRUE(f4.is<float *>());
+  EXPECT_TRUE(l4.is<long long *>());
+  EXPECT_TRUE(d4.is<double *>());
+  EXPECT_TRUE(i4null.is<int *>());
+  EXPECT_TRUE(f4null.is<float *>());
+  EXPECT_TRUE(l4null.is<long long *>());
+  EXPECT_TRUE(d4null.is<double *>());
 }
 
 TEST_F(PointerUnionTest, Get) {
   EXPECT_EQ(a.get<float *>(), &f);
   EXPECT_EQ(b.get<int *>(), &i);
   EXPECT_EQ(n.get<int *>(), (int *)nullptr);
 }
 
TEST_F(PointerUnionTest, ManyElements) {
   EXPECT_FALSE(a.is<Aligned<6>*>());
   EXPECT_TRUE(a.is<Aligned<7>*>());
   EXPECT_EQ(a.dyn_cast<Aligned<7>*>(), &a7);
 
   EXPECT_TRUE(a == PU8(&a7));
   EXPECT_TRUE(a != PU8(&a0));
 }
 
+TEST_F(PointerUnionTest, GetAddrOfPtr1) {
+  EXPECT_TRUE((void *)b.getAddrOfPtr1() == (void *)&b);
+  EXPECT_TRUE((void *)n.getAddrOfPtr1() == (void *)&n);
+}
+
 } // end anonymous namespace

llvm/unittests/ADT/TinyPtrVectorTest.cpp

 #include "gtest/gtest.h"
 #include <algorithm>
 #include <random>
 #include <vector>
 
 using namespace llvm;
 
 namespace {
+template <typename T> struct RemovePointer : std::remove_pointer<T> {};
+
+template <typename PointerTy, unsigned IntBits, typename IntType,
+          typename PtrTraits, typename Info>
+struct RemovePointer<
+    PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>> {
+  typedef typename RemovePointer<PointerTy>::type type;
+};
 
 template <typename VectorT>
 class TinyPtrVectorTest : public testing::Test {
 protected:
   typedef typename VectorT::value_type PtrT;
-  typedef typename std::remove_pointer<PtrT>::type ValueT;
+  typedef typename RemovePointer<PtrT>::type ValueT;
+  using PtrTraits = PointerLikeTypeTraits<PtrT>;
 
   VectorT V;
   VectorT V2;
 
   ValueT TestValues[1024];
   std::vector<PtrT> TestPtrs;
 
   TinyPtrVectorTest() {
     for (size_t i = 0, e = array_lengthof(TestValues); i != e; ++i)
-      TestPtrs.push_back(&TestValues[i]);
+      TestPtrs.push_back(PtrT(&TestValues[i]));
 
     std::shuffle(TestPtrs.begin(), TestPtrs.end(), std::mt19937{});
   }
 
+  PtrT makePtr(ValueT *V) { return PtrT(V); }
+
   ArrayRef<PtrT> testArray(size_t N) {
     return makeArrayRef(&TestPtrs[0], N);
   }
 
   void appendValues(VectorT &V, ArrayRef<PtrT> Values) {
     for (size_t i = 0, e = Values.size(); i != e; ++i)
       V.push_back(Values[i]);
   }
for (size_t i = 0, e = Values.size(); i != e; ++i) {
       EXPECT_EQ(Values[i], V[i]);
       EXPECT_EQ(Values[i], *std::next(V.begin(), i));
     }
     EXPECT_EQ(V.end(), std::next(V.begin(), Values.size()));
   }
 };
 
 typedef ::testing::Types<TinyPtrVector<int*>,
-                         TinyPtrVector<double*>
+                         TinyPtrVector<double*>,
+                         TinyPtrVector<PointerIntPair<int *, 1>>
                          > TinyPtrVectorTestTypes;
 TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes);
 
 TYPED_TEST(TinyPtrVectorTest, EmptyTest) {
   this->expectValues(this->V, this->testArray(0));
 }
 
 TYPED_TEST(TinyPtrVectorTest, PushPopBack) {
   this->V.push_back(this->TestPtrs[0]);
   this->expectValues(this->V, this->testArray(1));
   this->V.push_back(this->TestPtrs[1]);
   this->expectValues(this->V, this->testArray(2));
   this->V.push_back(this->TestPtrs[2]);
   this->expectValues(this->V, this->testArray(3));
   this->V.push_back(this->TestPtrs[3]);
   this->expectValues(this->V, this->testArray(4));
   this->V.push_back(this->TestPtrs[4]);
   this->expectValues(this->V, this->testArray(5));
 
   // Pop and clobber a few values to keep things interesting.
   this->V.pop_back();
   this->expectValues(this->V, this->testArray(4));
   this->V.pop_back();
   this->expectValues(this->V, this->testArray(3));
-  this->TestPtrs[3] = &this->TestValues[42];
-  this->TestPtrs[4] = &this->TestValues[43];
+  this->TestPtrs[3] = this->makePtr(&this->TestValues[42]);
+  this->TestPtrs[4] = this->makePtr(&this->TestValues[43]);
   this->V.push_back(this->TestPtrs[3]);
   this->expectValues(this->V, this->testArray(4));
   this->V.push_back(this->TestPtrs[4]);
   this->expectValues(this->V, this->testArray(5));
 
   this->V.pop_back();
   this->expectValues(this->V, this->testArray(4));
   this->V.pop_back();