//===- llvm/ADT/PointerUnion.h - Discriminated Union of 2 Ptrs --*- C++ -*-===// // // 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 // //===----------------------------------------------------------------------===// // // This file defines the PointerUnion class, which is a discriminated union of // pointer types. // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_POINTERUNION_H #define LLVM_ADT_POINTERUNION_H #include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include #include #include namespace llvm { template struct PointerUnionTypeSelectorReturn { using Return = T; }; /// Get a type based on whether two types are the same or not. /// /// For: /// /// \code /// using Ret = typename PointerUnionTypeSelector::Return; /// \endcode /// /// Ret will be EQ type if T1 is same as T2 or NE type otherwise. template struct PointerUnionTypeSelector { using Return = typename PointerUnionTypeSelectorReturn::Return; }; template struct PointerUnionTypeSelector { using Return = typename PointerUnionTypeSelectorReturn::Return; }; template struct PointerUnionTypeSelectorReturn< PointerUnionTypeSelector> { using Return = typename PointerUnionTypeSelector::Return; }; namespace pointer_union_detail { /// 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; } template constexpr int lowBitsAvailable() { return std::min({PointerLikeTypeTraits::NumLowBitsAvailable...}); } /// Find the index of a type in a list of types. TypeIndex::Index /// is the index of T in Us, or sizeof...(Us) if T does not appear in the /// list. template struct TypeIndex; template struct TypeIndex { static constexpr int Index = 0; }; template struct TypeIndex { static constexpr int Index = 1 + TypeIndex::Index; }; template struct TypeIndex { static constexpr int Index = 0; }; /// Find the first type in a list of types. template struct GetFirstType { using type = T; }; /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion /// for the template arguments. template class PointerUnionUIntTraits { public: static inline void *getAsVoidPointer(void *P) { return P; } static inline void *getFromVoidPointer(void *P) { return P; } static constexpr int NumLowBitsAvailable = lowBitsAvailable(); }; /// Implement assigment in terms of construction. template struct AssignableFrom { Derived &operator=(T t) { return static_cast(*this) = Derived(t); } }; template class PointerUnionMembers; template class PointerUnionMembers { protected: ValTy Val; PointerUnionMembers() = default; PointerUnionMembers(ValTy Val) : Val(Val) {} friend struct PointerLikeTypeTraits; }; template class PointerUnionMembers : public PointerUnionMembers { using Base = PointerUnionMembers; public: using Base::Base; PointerUnionMembers() = default; PointerUnionMembers(Type V) : Base(ValTy(const_cast( PointerLikeTypeTraits::getAsVoidPointer(V)), I)) {} using Base::operator=; Derived &operator=(Type V) { this->Val = ValTy( const_cast(PointerLikeTypeTraits::getAsVoidPointer(V)), I); return static_cast(*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. /// /// Common use patterns would be something like this: /// PointerUnion P; /// P = (int*)0; /// printf("%d %d", P.is(), P.is()); // prints "1 0" /// X = P.get(); // ok. /// Y = P.get(); // runtime assertion failure. /// Z = P.get(); // compile time failure. /// P = (float*)0; /// Y = P.get(); // ok. /// X = P.get(); // runtime assertion failure. template class PointerUnion : public pointer_union_detail::PointerUnionMembers< PointerUnion, PointerIntPair< void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int, pointer_union_detail::PointerUnionUIntTraits>, 0, PTs...> { // 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; 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 { return !this->Val.getPointer(); } explicit operator bool() const { return !isNull(); } /// Test if the Union currently holds the type matching T. template int is() const { constexpr int Index = pointer_union_detail::TypeIndex::Index; static_assert(Index < sizeof...(PTs), "PointerUnion::is given type not in the union"); return this->Val.getInt() == Index; } /// Returns the value of the specified pointer type. /// /// If the specified pointer type is incorrect, assert. template T get() const { assert(is() && "Invalid accessor called"); return PointerLikeTypeTraits::getFromVoidPointer(this->Val.getPointer()); } /// Returns the current pointer if it is of the specified pointer type, /// otherwises returns null. template T dyn_cast() const { if (is()) return get(); return T(); } /// If the union is set to the first pointer type get an address pointing to /// it. First const *getAddrOfPtr1() const { return const_cast(this)->getAddrOfPtr1(); } /// If the union is set to the first pointer type get an address pointing to /// it. First *getAddrOfPtr1() { assert(is() && "Val is not the first pointer"); assert( PointerLikeTypeTraits::getAsVoidPointer(get()) == this->Val.getPointer() && "Can't get the address because PointerLikeTypeTraits changes the ptr"); return const_cast( reinterpret_cast(this->Val.getAddrOfPointer())); } /// Assignment from nullptr which just clears the union. const PointerUnion &operator=(std::nullptr_t) { this->Val.initWithPointer(nullptr); return *this; } /// Assignment from elements of the union. using Base::operator=; void *getOpaqueValue() const { return this->Val.getOpaqueValue(); } static inline PointerUnion getFromOpaqueValue(void *VP) { PointerUnion V; V.Val = decltype(V.Val)::getFromOpaqueValue(VP); return V; } }; template bool operator==(PointerUnion lhs, PointerUnion rhs) { return lhs.getOpaqueValue() == rhs.getOpaqueValue(); } template bool operator!=(PointerUnion lhs, PointerUnion rhs) { return lhs.getOpaqueValue() != rhs.getOpaqueValue(); } template bool operator<(PointerUnion lhs, PointerUnion rhs) { return lhs.getOpaqueValue() < rhs.getOpaqueValue(); } // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has // # low bits available = min(PT1bits,PT2bits)-1. template struct PointerLikeTypeTraits> { static inline void *getAsVoidPointer(const PointerUnion &P) { return P.getOpaqueValue(); } static inline PointerUnion getFromVoidPointer(void *P) { return PointerUnion::getFromOpaqueValue(P); } // The number of bits available are the min of the pointer types minus the // bits needed for the discriminator. static constexpr int NumLowBitsAvailable = PointerLikeTypeTraits::Val)>::NumLowBitsAvailable; }; /// A pointer union of three pointer types. See documentation for PointerUnion /// for usage. template using PointerUnion3 = PointerUnion; /// A pointer union of four pointer types. See documentation for PointerUnion /// for usage. template using PointerUnion4 = PointerUnion; // Teach DenseMap how to use PointerUnions as keys. template struct DenseMapInfo> { using Union = PointerUnion; using FirstInfo = DenseMapInfo::type>; static inline Union getEmptyKey() { return Union(FirstInfo::getEmptyKey()); } static inline Union getTombstoneKey() { return Union(FirstInfo::getTombstoneKey()); } static unsigned getHashValue(const Union &UnionVal) { intptr_t key = (intptr_t)UnionVal.getOpaqueValue(); return DenseMapInfo::getHashValue(key); } static bool isEqual(const Union &LHS, const Union &RHS) { return LHS == RHS; } }; } // end namespace llvm #endif // LLVM_ADT_POINTERUNION_H