From 30b148e81a570c4d741fe23a4c222960aaaabe51 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Tue, 20 Aug 2019 23:29:28 +0000 Subject: [PATCH] Add TinyPtrVector support for general pointer-like things. In particular, make TinyPtrVector> 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@369473 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/PointerUnion.h | 19 +++++----- include/llvm/ADT/TinyPtrVector.h | 38 +++++++++++--------- unittests/ADT/PointerUnionTest.cpp | 55 +++++++++++++++++++++++++++-- unittests/ADT/TinyPtrVectorTest.cpp | 25 +++++++++---- 4 files changed, 101 insertions(+), 36 deletions(-) diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h index 93533de776b..98c905775a7 100644 --- a/include/llvm/ADT/PointerUnion.h +++ b/include/llvm/ADT/PointerUnion.h @@ -160,10 +160,11 @@ class PointerUnion void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int, pointer_union_detail::PointerUnionUIntTraits>, 0, PTs...> { - // The first type is special in some ways, but we don't want PointerUnion to - // be a 'template ' 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 ' + // 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::type; using Base = typename PointerUnion::PointerUnionMembers; @@ -175,12 +176,7 @@ public: /// 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::getFromVoidPointer( - this->Val.getPointer()); - } + bool isNull() const { return !this->Val.getPointer(); } explicit operator bool() const { return !isNull(); } @@ -219,7 +215,8 @@ public: First *getAddrOfPtr1() { assert(is() && "Val is not the first pointer"); assert( - get() == this->Val.getPointer() && + PointerLikeTypeTraits::getAsVoidPointer(get()) == + this->Val.getPointer() && "Can't get the address because PointerLikeTypeTraits changes the ptr"); return const_cast( reinterpret_cast(this->Val.getAddrOfPointer())); diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h index ac82451a9b2..6b76d35d4e9 100644 --- a/include/llvm/ADT/TinyPtrVector.h +++ b/include/llvm/ADT/TinyPtrVector.h @@ -31,6 +31,10 @@ class TinyPtrVector { public: using VecTy = SmallVector; using value_type = typename VecTy::value_type; + // EltTy must be the first pointer type so that is 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; private: @@ -96,14 +100,14 @@ public: if (RHS.Val.template is()) { 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; } @@ -213,9 +217,9 @@ public: EltTy operator[](unsigned i) const { assert(!Val.isNull() && "can't index into an empty vector"); - if (EltTy V = Val.template dyn_cast()) { + if (Val.template is()) { assert(i == 0 && "tinyvector index out of range"); - return V; + return Val.template get(); } assert(i < Val.template get()->size() && @@ -225,29 +229,29 @@ public: EltTy front() const { assert(!empty() && "vector empty"); - if (EltTy V = Val.template dyn_cast()) - return V; + if (Val.template is()) + return Val.template get(); return Val.template get()->front(); } EltTy back() const { assert(!empty() && "vector empty"); - if (EltTy V = Val.template dyn_cast()) - return V; + if (Val.template is()) + return Val.template get(); return Val.template get()->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()) { + if (Val.template is()) { + EltTy V = Val.template get(); Val = new VecTy(); Val.template get()->push_back(V); } @@ -267,7 +271,7 @@ public: void clear() { // If we have a single value, convert to empty. if (Val.template is()) { - Val = (EltTy)nullptr; + Val = EltTy(); } else if (VecTy *Vec = Val.template dyn_cast()) { // If we have a vector form, just clear it. Vec->clear(); @@ -282,7 +286,7 @@ public: // If we have a single value, convert to empty. if (Val.template is()) { if (I == begin()) - Val = (EltTy)nullptr; + Val = EltTy(); } else if (VecTy *Vec = Val.template dyn_cast()) { // multiple items in a vector; just do the erase, there is no // benefit to collapsing back to a pointer @@ -298,7 +302,7 @@ public: if (Val.template is()) { if (S == begin() && S != E) - Val = (EltTy)nullptr; + Val = EltTy(); } else if (VecTy *Vec = Val.template dyn_cast()) { return Vec->erase(S, E); } @@ -313,7 +317,8 @@ public: return std::prev(end()); } assert(!Val.isNull() && "Null value with non-end insert iterator."); - if (EltTy V = Val.template dyn_cast()) { + if (Val.template is()) { + EltTy V = Val.template get(); assert(I == begin()); Val = Elt; push_back(V); @@ -339,7 +344,8 @@ public: } Val = new VecTy(); - } else if (EltTy V = Val.template dyn_cast()) { + } else if (Val.template is()) { + EltTy V = Val.template get(); Val = new VecTy(); Val.template get()->push_back(V); } diff --git a/unittests/ADT/PointerUnionTest.cpp b/unittests/ADT/PointerUnionTest.cpp index cd6e980e9a2..0a88114ede8 100644 --- a/unittests/ADT/PointerUnionTest.cpp +++ b/unittests/ADT/PointerUnionTest.cpp @@ -13,14 +13,25 @@ using namespace llvm; namespace { typedef PointerUnion PU; +typedef PointerUnion3 PU3; +typedef PointerUnion4 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) { @@ -32,6 +43,19 @@ TEST_F(PointerUnionTest, Comparison) { 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) { @@ -51,6 +75,17 @@ TEST_F(PointerUnionTest, Null) { 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) { @@ -60,6 +95,17 @@ TEST_F(PointerUnionTest, Is) { EXPECT_FALSE(b.is()); EXPECT_TRUE(n.is()); EXPECT_FALSE(n.is()); + EXPECT_TRUE(i3.is()); + EXPECT_TRUE(f3.is()); + EXPECT_TRUE(l3.is()); + EXPECT_TRUE(i4.is()); + EXPECT_TRUE(f4.is()); + EXPECT_TRUE(l4.is()); + EXPECT_TRUE(d4.is()); + EXPECT_TRUE(i4null.is()); + EXPECT_TRUE(f4null.is()); + EXPECT_TRUE(l4null.is()); + EXPECT_TRUE(d4null.is()); } TEST_F(PointerUnionTest, Get) { @@ -105,4 +151,9 @@ TEST_F(PointerUnionTest, ManyElements) { 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 diff --git a/unittests/ADT/TinyPtrVectorTest.cpp b/unittests/ADT/TinyPtrVectorTest.cpp index c8c00d94736..f88534787c9 100644 --- a/unittests/ADT/TinyPtrVectorTest.cpp +++ b/unittests/ADT/TinyPtrVectorTest.cpp @@ -22,12 +22,21 @@ using namespace llvm; namespace { +template struct RemovePointer : std::remove_pointer {}; + +template +struct RemovePointer< + PointerIntPair> { + typedef typename RemovePointer::type type; +}; template class TinyPtrVectorTest : public testing::Test { protected: typedef typename VectorT::value_type PtrT; - typedef typename std::remove_pointer::type ValueT; + typedef typename RemovePointer::type ValueT; + using PtrTraits = PointerLikeTypeTraits; VectorT V; VectorT V2; @@ -37,11 +46,13 @@ protected: 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 testArray(size_t N) { return makeArrayRef(&TestPtrs[0], N); } @@ -69,9 +80,9 @@ protected: } }; -typedef ::testing::Types, - TinyPtrVector - > TinyPtrVectorTestTypes; +typedef ::testing::Types, TinyPtrVector, + TinyPtrVector>> + TinyPtrVectorTestTypes; TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes); TYPED_TEST(TinyPtrVectorTest, EmptyTest) { @@ -95,8 +106,8 @@ TYPED_TEST(TinyPtrVectorTest, PushPopBack) { 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]); -- 2.40.0