diff options
Diffstat (limited to 'include/llvm/ADT/PointerUnion.h')
| -rw-r--r-- | include/llvm/ADT/PointerUnion.h | 482 |
1 files changed, 155 insertions, 327 deletions
diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h index 315e58336cba..2bcdf546c6e4 100644 --- a/include/llvm/ADT/PointerUnion.h +++ b/include/llvm/ADT/PointerUnion.h @@ -1,9 +1,8 @@ //===- llvm/ADT/PointerUnion.h - Discriminated Union of 2 Ptrs --*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// 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 // //===----------------------------------------------------------------------===// // @@ -54,22 +53,98 @@ struct PointerUnionTypeSelectorReturn< typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::Return; }; -/// Provide PointerLikeTypeTraits for void* that is used by PointerUnion -/// for the two template arguments. -template <typename PT1, typename PT2> class PointerUnionUIntTraits { -public: - static inline void *getAsVoidPointer(void *P) { return P; } - static inline void *getFromVoidPointer(void *P) { return P; } +namespace pointer_union_detail { + constexpr int constexprMin(int a, int b) { return a < b ? a : b; } + /// Determine the number of bits required to store integers with values < n. + /// This is ceil(log2(n)). + constexpr int bitsRequired(unsigned n) { + return n > 1 ? 1 + bitsRequired((n + 1) / 2) : 0; + } + + // FIXME: In C++14, replace this with + // std::min({PointerLikeTypeTraits<Ts>::NumLowBitsAvailable...}) + template <typename T> constexpr int lowBitsAvailable() { + return PointerLikeTypeTraits<T>::NumLowBitsAvailable; + } + template <typename T1, typename T2, typename... Ts> + constexpr int lowBitsAvailable() { + return constexprMin(lowBitsAvailable<T1>(), lowBitsAvailable<T2, Ts...>()); + } - enum { - PT1BitsAv = (int)(PointerLikeTypeTraits<PT1>::NumLowBitsAvailable), - PT2BitsAv = (int)(PointerLikeTypeTraits<PT2>::NumLowBitsAvailable), - NumLowBitsAvailable = PT1BitsAv < PT2BitsAv ? PT1BitsAv : PT2BitsAv + /// Find the index of a type in a list of types. TypeIndex<T, Us...>::Index + /// is the index of T in Us, or sizeof...(Us) if T does not appear in the + /// list. + template <typename T, typename ...Us> struct TypeIndex; + template <typename T, typename ...Us> struct TypeIndex<T, T, Us...> { + static constexpr int Index = 0; }; -}; + template <typename T, typename U, typename... Us> + struct TypeIndex<T, U, Us...> { + static constexpr int Index = 1 + TypeIndex<T, Us...>::Index; + }; + template <typename T> struct TypeIndex<T> { + static constexpr int Index = 0; + }; + + /// Find the first type in a list of types. + template <typename T, typename...> struct GetFirstType { + using type = T; + }; + + /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion + /// for the template arguments. + template <typename ...PTs> class PointerUnionUIntTraits { + public: + static inline void *getAsVoidPointer(void *P) { return P; } + static inline void *getFromVoidPointer(void *P) { return P; } + static constexpr int NumLowBitsAvailable = lowBitsAvailable<PTs...>(); + }; + + /// Implement assigment in terms of construction. + template <typename Derived, typename T> struct AssignableFrom { + Derived &operator=(T t) { + return static_cast<Derived &>(*this) = Derived(t); + } + }; + + template <typename Derived, typename ValTy, int I, typename ...Types> + class PointerUnionMembers; -/// A discriminated union of two pointer types, with the discriminator in the -/// low bit of the pointer. + template <typename Derived, typename ValTy, int I> + class PointerUnionMembers<Derived, ValTy, I> { + protected: + ValTy Val; + PointerUnionMembers() = default; + PointerUnionMembers(ValTy Val) : Val(Val) {} + + friend struct PointerLikeTypeTraits<Derived>; + }; + + template <typename Derived, typename ValTy, int I, typename Type, + typename ...Types> + class PointerUnionMembers<Derived, ValTy, I, Type, Types...> + : public PointerUnionMembers<Derived, ValTy, I + 1, Types...> { + using Base = PointerUnionMembers<Derived, ValTy, I + 1, Types...>; + public: + using Base::Base; + PointerUnionMembers() = default; + PointerUnionMembers(Type V) + : Base(ValTy(const_cast<void *>( + PointerLikeTypeTraits<Type>::getAsVoidPointer(V)), + I)) {} + + using Base::operator=; + Derived &operator=(Type V) { + this->Val = ValTy( + const_cast<void *>(PointerLikeTypeTraits<Type>::getAsVoidPointer(V)), + I); + return static_cast<Derived &>(*this); + }; + }; +} + +/// A discriminated union of two or more pointer types, with the discriminator +/// in the low bit of the pointer. /// /// This implementation is extremely efficient in space due to leveraging the /// low bits of the pointer, while exposing a natural and type-safe API. @@ -84,49 +159,44 @@ public: /// P = (float*)0; /// Y = P.get<float*>(); // ok. /// X = P.get<int*>(); // runtime assertion failure. -template <typename PT1, typename PT2> class PointerUnion { -public: - using ValTy = - PointerIntPair<void *, 1, bool, PointerUnionUIntTraits<PT1, PT2>>; - -private: - ValTy Val; - - struct IsPT1 { - static const int Num = 0; - }; - struct IsPT2 { - static const int Num = 1; - }; - template <typename T> struct UNION_DOESNT_CONTAIN_TYPE {}; +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. + using First = typename pointer_union_detail::GetFirstType<PTs...>::type; + using Base = typename PointerUnion::PointerUnionMembers; public: PointerUnion() = default; - PointerUnion(PT1 V) - : Val(const_cast<void *>( - PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) {} - PointerUnion(PT2 V) - : Val(const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)), - 1) {} + + 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<PT1>::getFromVoidPointer(Val.getPointer()); + return !PointerLikeTypeTraits<First>::getFromVoidPointer( + 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 { - using Ty = typename ::llvm::PointerUnionTypeSelector< - PT1, T, IsPT1, - ::llvm::PointerUnionTypeSelector<PT2, T, IsPT2, - UNION_DOESNT_CONTAIN_TYPE<T>>>::Return; - int TyNo = Ty::Num; - return static_cast<int>(Val.getInt()) == TyNo; + constexpr int Index = pointer_union_detail::TypeIndex<T, PTs...>::Index; + static_assert(Index < sizeof...(PTs), + "PointerUnion::is<T> given type not in the union"); + return this->Val.getInt() == Index; } /// Returns the value of the specified pointer type. @@ -134,7 +204,7 @@ public: /// If the specified pointer type is incorrect, assert. template <typename T> T get() const { assert(is<T>() && "Invalid accessor called"); - return PointerLikeTypeTraits<T>::getFromVoidPointer(Val.getPointer()); + return PointerLikeTypeTraits<T>::getFromVoidPointer(this->Val.getPointer()); } /// Returns the current pointer if it is of the specified pointer type, @@ -147,342 +217,100 @@ public: /// If the union is set to the first pointer type get an address pointing to /// it. - PT1 const *getAddrOfPtr1() const { + 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. - PT1 *getAddrOfPtr1() { - assert(is<PT1>() && "Val is not the first pointer"); + First *getAddrOfPtr1() { + assert(is<First>() && "Val is not the first pointer"); assert( - get<PT1>() == Val.getPointer() && + get<First>() == this->Val.getPointer() && "Can't get the address because PointerLikeTypeTraits changes the ptr"); - return const_cast<PT1 *>( - reinterpret_cast<const PT1 *>(Val.getAddrOfPointer())); + 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) { - Val.initWithPointer(nullptr); + this->Val.initWithPointer(nullptr); return *this; } - /// Assignment operators - Allow assigning into this union from either - /// pointer type, setting the discriminator to remember what it came from. - const PointerUnion &operator=(const PT1 &RHS) { - Val.initWithPointer( - const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(RHS))); - return *this; - } - const PointerUnion &operator=(const PT2 &RHS) { - Val.setPointerAndInt( - const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS)), - 1); - return *this; - } + /// Assignment from elements of the union. + using Base::operator=; - void *getOpaqueValue() const { return Val.getOpaqueValue(); } + void *getOpaqueValue() const { return this->Val.getOpaqueValue(); } static inline PointerUnion getFromOpaqueValue(void *VP) { PointerUnion V; - V.Val = ValTy::getFromOpaqueValue(VP); + V.Val = decltype(V.Val)::getFromOpaqueValue(VP); return V; } }; -template <typename PT1, typename PT2> -bool operator==(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { +template <typename ...PTs> +bool operator==(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) { return lhs.getOpaqueValue() == rhs.getOpaqueValue(); } -template <typename PT1, typename PT2> -bool operator!=(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { +template <typename ...PTs> +bool operator!=(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) { return lhs.getOpaqueValue() != rhs.getOpaqueValue(); } -template <typename PT1, typename PT2> -bool operator<(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { +template <typename ...PTs> +bool operator<(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) { return lhs.getOpaqueValue() < rhs.getOpaqueValue(); } // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has // # low bits available = min(PT1bits,PT2bits)-1. -template <typename PT1, typename PT2> -struct PointerLikeTypeTraits<PointerUnion<PT1, PT2>> { - static inline void *getAsVoidPointer(const PointerUnion<PT1, PT2> &P) { +template <typename ...PTs> +struct PointerLikeTypeTraits<PointerUnion<PTs...>> { + static inline void *getAsVoidPointer(const PointerUnion<PTs...> &P) { return P.getOpaqueValue(); } - static inline PointerUnion<PT1, PT2> getFromVoidPointer(void *P) { - return PointerUnion<PT1, PT2>::getFromOpaqueValue(P); + static inline PointerUnion<PTs...> getFromVoidPointer(void *P) { + return PointerUnion<PTs...>::getFromOpaqueValue(P); } - // The number of bits available are the min of the two pointer types. - enum { - NumLowBitsAvailable = PointerLikeTypeTraits< - typename PointerUnion<PT1, PT2>::ValTy>::NumLowBitsAvailable - }; + // The number of bits available are the min of the pointer types minus the + // bits needed for the discriminator. + static constexpr int NumLowBitsAvailable = PointerLikeTypeTraits<decltype( + PointerUnion<PTs...>::Val)>::NumLowBitsAvailable; }; /// A pointer union of three pointer types. See documentation for PointerUnion /// for usage. -template <typename PT1, typename PT2, typename PT3> class PointerUnion3 { -public: - using InnerUnion = PointerUnion<PT1, PT2>; - using ValTy = PointerUnion<InnerUnion, PT3>; - -private: - ValTy Val; - - struct IsInnerUnion { - ValTy Val; - - IsInnerUnion(ValTy val) : Val(val) {} - - template <typename T> int is() const { - return Val.template is<InnerUnion>() && - Val.template get<InnerUnion>().template is<T>(); - } - - template <typename T> T get() const { - return Val.template get<InnerUnion>().template get<T>(); - } - }; - - struct IsPT3 { - ValTy Val; - - IsPT3(ValTy val) : Val(val) {} - - template <typename T> int is() const { return Val.template is<T>(); } - template <typename T> T get() const { return Val.template get<T>(); } - }; - -public: - PointerUnion3() = default; - PointerUnion3(PT1 V) { Val = InnerUnion(V); } - PointerUnion3(PT2 V) { Val = InnerUnion(V); } - PointerUnion3(PT3 V) { Val = V; } - - /// Test if the pointer held in the union is null, regardless of - /// which type it is. - bool isNull() const { return Val.isNull(); } - explicit operator bool() const { return !isNull(); } - - /// Test if the Union currently holds the type matching T. - template <typename T> int is() const { - // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3. - using Ty = typename ::llvm::PointerUnionTypeSelector< - PT1, T, IsInnerUnion, - ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return; - return Ty(Val).template is<T>(); - } - - /// Returns the value of the specified pointer type. - /// - /// If the specified pointer type is incorrect, assert. - template <typename T> T get() const { - assert(is<T>() && "Invalid accessor called"); - // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3. - using Ty = typename ::llvm::PointerUnionTypeSelector< - PT1, T, IsInnerUnion, - ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return; - return Ty(Val).template get<T>(); - } - - /// Returns the current pointer if it is of the specified pointer type, - /// otherwises returns null. - template <typename T> T dyn_cast() const { - if (is<T>()) - return get<T>(); - return T(); - } - - /// Assignment from nullptr which just clears the union. - const PointerUnion3 &operator=(std::nullptr_t) { - Val = nullptr; - return *this; - } - - /// Assignment operators - Allow assigning into this union from either - /// pointer type, setting the discriminator to remember what it came from. - const PointerUnion3 &operator=(const PT1 &RHS) { - Val = InnerUnion(RHS); - return *this; - } - const PointerUnion3 &operator=(const PT2 &RHS) { - Val = InnerUnion(RHS); - return *this; - } - const PointerUnion3 &operator=(const PT3 &RHS) { - Val = RHS; - return *this; - } - - void *getOpaqueValue() const { return Val.getOpaqueValue(); } - static inline PointerUnion3 getFromOpaqueValue(void *VP) { - PointerUnion3 V; - V.Val = ValTy::getFromOpaqueValue(VP); - return V; - } -}; - -// Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has -// # low bits available = min(PT1bits,PT2bits,PT2bits)-2. template <typename PT1, typename PT2, typename PT3> -struct PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3>> { - static inline void *getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) { - return P.getOpaqueValue(); - } - - static inline PointerUnion3<PT1, PT2, PT3> getFromVoidPointer(void *P) { - return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P); - } - - // The number of bits available are the min of the two pointer types. - enum { - NumLowBitsAvailable = PointerLikeTypeTraits< - typename PointerUnion3<PT1, PT2, PT3>::ValTy>::NumLowBitsAvailable - }; -}; - -template <typename PT1, typename PT2, typename PT3> -bool operator<(PointerUnion3<PT1, PT2, PT3> lhs, - PointerUnion3<PT1, PT2, PT3> rhs) { - return lhs.getOpaqueValue() < rhs.getOpaqueValue(); -} +using PointerUnion3 = PointerUnion<PT1, PT2, PT3>; /// A pointer union of four pointer types. See documentation for PointerUnion /// for usage. template <typename PT1, typename PT2, typename PT3, typename PT4> -class PointerUnion4 { -public: - using InnerUnion1 = PointerUnion<PT1, PT2>; - using InnerUnion2 = PointerUnion<PT3, PT4>; - using ValTy = PointerUnion<InnerUnion1, InnerUnion2>; - -private: - ValTy Val; - -public: - PointerUnion4() = default; - PointerUnion4(PT1 V) { Val = InnerUnion1(V); } - PointerUnion4(PT2 V) { Val = InnerUnion1(V); } - PointerUnion4(PT3 V) { Val = InnerUnion2(V); } - PointerUnion4(PT4 V) { Val = InnerUnion2(V); } - - /// Test if the pointer held in the union is null, regardless of - /// which type it is. - bool isNull() const { return Val.isNull(); } - explicit operator bool() const { return !isNull(); } - - /// Test if the Union currently holds the type matching T. - template <typename T> int is() const { - // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2. - using Ty = typename ::llvm::PointerUnionTypeSelector< - PT1, T, InnerUnion1, - ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, - InnerUnion2>>::Return; - return Val.template is<Ty>() && Val.template get<Ty>().template is<T>(); - } - - /// Returns the value of the specified pointer type. - /// - /// If the specified pointer type is incorrect, assert. - template <typename T> T get() const { - assert(is<T>() && "Invalid accessor called"); - // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2. - using Ty = typename ::llvm::PointerUnionTypeSelector< - PT1, T, InnerUnion1, - ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, - InnerUnion2>>::Return; - return Val.template get<Ty>().template get<T>(); - } - - /// Returns the current pointer if it is of the specified pointer type, - /// otherwises returns null. - template <typename T> T dyn_cast() const { - if (is<T>()) - return get<T>(); - return T(); - } - - /// Assignment from nullptr which just clears the union. - const PointerUnion4 &operator=(std::nullptr_t) { - Val = nullptr; - return *this; - } - - /// Assignment operators - Allow assigning into this union from either - /// pointer type, setting the discriminator to remember what it came from. - const PointerUnion4 &operator=(const PT1 &RHS) { - Val = InnerUnion1(RHS); - return *this; - } - const PointerUnion4 &operator=(const PT2 &RHS) { - Val = InnerUnion1(RHS); - return *this; - } - const PointerUnion4 &operator=(const PT3 &RHS) { - Val = InnerUnion2(RHS); - return *this; - } - const PointerUnion4 &operator=(const PT4 &RHS) { - Val = InnerUnion2(RHS); - return *this; - } - - void *getOpaqueValue() const { return Val.getOpaqueValue(); } - static inline PointerUnion4 getFromOpaqueValue(void *VP) { - PointerUnion4 V; - V.Val = ValTy::getFromOpaqueValue(VP); - return V; - } -}; - -// Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has -// # low bits available = min(PT1bits,PT2bits,PT2bits)-2. -template <typename PT1, typename PT2, typename PT3, typename PT4> -struct PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4>> { - static inline void * - getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) { - return P.getOpaqueValue(); - } - - static inline PointerUnion4<PT1, PT2, PT3, PT4> getFromVoidPointer(void *P) { - return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P); - } - - // The number of bits available are the min of the two pointer types. - enum { - NumLowBitsAvailable = PointerLikeTypeTraits< - typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy>::NumLowBitsAvailable - }; -}; +using PointerUnion4 = PointerUnion<PT1, PT2, PT3, PT4>; // Teach DenseMap how to use PointerUnions as keys. -template <typename T, typename U> struct DenseMapInfo<PointerUnion<T, U>> { - using Pair = PointerUnion<T, U>; - using FirstInfo = DenseMapInfo<T>; - using SecondInfo = DenseMapInfo<U>; +template <typename ...PTs> struct DenseMapInfo<PointerUnion<PTs...>> { + using Union = PointerUnion<PTs...>; + using FirstInfo = + DenseMapInfo<typename pointer_union_detail::GetFirstType<PTs...>::type>; - static inline Pair getEmptyKey() { return Pair(FirstInfo::getEmptyKey()); } + static inline Union getEmptyKey() { return Union(FirstInfo::getEmptyKey()); } - static inline Pair getTombstoneKey() { - return Pair(FirstInfo::getTombstoneKey()); + static inline Union getTombstoneKey() { + return Union(FirstInfo::getTombstoneKey()); } - static unsigned getHashValue(const Pair &PairVal) { - intptr_t key = (intptr_t)PairVal.getOpaqueValue(); + static unsigned getHashValue(const Union &UnionVal) { + intptr_t key = (intptr_t)UnionVal.getOpaqueValue(); return DenseMapInfo<intptr_t>::getHashValue(key); } - static bool isEqual(const Pair &LHS, const Pair &RHS) { - return LHS.template is<T>() == RHS.template is<T>() && - (LHS.template is<T>() ? FirstInfo::isEqual(LHS.template get<T>(), - RHS.template get<T>()) - : SecondInfo::isEqual(LHS.template get<U>(), - RHS.template get<U>())); + static bool isEqual(const Union &LHS, const Union &RHS) { + return LHS == RHS; } }; |