LLVM  6.0.0svn
PointerSumType.h
Go to the documentation of this file.
1 //===- llvm/ADT/PointerSumType.h --------------------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef LLVM_ADT_POINTERSUMTYPE_H
11 #define LLVM_ADT_POINTERSUMTYPE_H
12 
13 #include "llvm/ADT/DenseMapInfo.h"
15 #include <cassert>
16 #include <cstdint>
17 #include <type_traits>
18 
19 namespace llvm {
20 
21 /// A compile time pair of an integer tag and the pointer-like type which it
22 /// indexes within a sum type. Also allows the user to specify a particular
23 /// traits class for pointer types with custom behavior such as over-aligned
24 /// allocation.
25 template <uintptr_t N, typename PointerArgT,
26  typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>>
28  enum { Tag = N };
29  using PointerT = PointerArgT;
30  using TraitsT = TraitsArgT;
31 };
32 
33 namespace detail {
34 
35 template <typename TagT, typename... MemberTs> struct PointerSumTypeHelper;
36 
37 } // end namespace detail
38 
39 /// A sum type over pointer-like types.
40 ///
41 /// This is a normal tagged union across pointer-like types that uses the low
42 /// bits of the pointers to store the tag.
43 ///
44 /// Each member of the sum type is specified by passing a \c
45 /// PointerSumTypeMember specialization in the variadic member argument list.
46 /// This allows the user to control the particular tag value associated with
47 /// a particular type, use the same type for multiple different tags, and
48 /// customize the pointer-like traits used for a particular member. Note that
49 /// these *must* be specializations of \c PointerSumTypeMember, no other type
50 /// will suffice, even if it provides a compatible interface.
51 ///
52 /// This type implements all of the comparison operators and even hash table
53 /// support by comparing the underlying storage of the pointer values. It
54 /// doesn't support delegating to particular members for comparisons.
55 ///
56 /// It also default constructs to a zero tag with a null pointer, whatever that
57 /// would be. This means that the zero value for the tag type is significant
58 /// and may be desirable to set to a state that is particularly desirable to
59 /// default construct.
60 ///
61 /// There is no support for constructing or accessing with a dynamic tag as
62 /// that would fundamentally violate the type safety provided by the sum type.
63 template <typename TagT, typename... MemberTs> class PointerSumType {
64  uintptr_t Value = 0;
65 
67 
68 public:
69  constexpr PointerSumType() = default;
70 
71  /// A typed constructor for a specific tagged member of the sum type.
72  template <TagT N>
73  static PointerSumType
74  create(typename HelperT::template Lookup<N>::PointerT Pointer) {
75  PointerSumType Result;
76  void *V = HelperT::template Lookup<N>::TraitsT::getAsVoidPointer(Pointer);
77  assert((reinterpret_cast<uintptr_t>(V) & HelperT::TagMask) == 0 &&
78  "Pointer is insufficiently aligned to store the discriminant!");
79  Result.Value = reinterpret_cast<uintptr_t>(V) | N;
80  return Result;
81  }
82 
83  TagT getTag() const { return static_cast<TagT>(Value & HelperT::TagMask); }
84 
85  template <TagT N> bool is() const { return N == getTag(); }
86 
87  template <TagT N> typename HelperT::template Lookup<N>::PointerT get() const {
88  void *P = is<N>() ? getImpl() : nullptr;
89  return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(P);
90  }
91 
92  template <TagT N>
93  typename HelperT::template Lookup<N>::PointerT cast() const {
94  assert(is<N>() && "This instance has a different active member.");
95  return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(getImpl());
96  }
97 
98  explicit operator bool() const { return Value & HelperT::PointerMask; }
99  bool operator==(const PointerSumType &R) const { return Value == R.Value; }
100  bool operator!=(const PointerSumType &R) const { return Value != R.Value; }
101  bool operator<(const PointerSumType &R) const { return Value < R.Value; }
102  bool operator>(const PointerSumType &R) const { return Value > R.Value; }
103  bool operator<=(const PointerSumType &R) const { return Value <= R.Value; }
104  bool operator>=(const PointerSumType &R) const { return Value >= R.Value; }
105 
106  uintptr_t getOpaqueValue() const { return Value; }
107 
108 protected:
109  void *getImpl() const {
110  return reinterpret_cast<void *>(Value & HelperT::PointerMask);
111  }
112 };
113 
114 namespace detail {
115 
116 /// A helper template for implementing \c PointerSumType. It provides fast
117 /// compile-time lookup of the member from a particular tag value, along with
118 /// useful constants and compile time checking infrastructure..
119 template <typename TagT, typename... MemberTs>
120 struct PointerSumTypeHelper : MemberTs... {
121  // First we use a trick to allow quickly looking up information about
122  // a particular member of the sum type. This works because we arranged to
123  // have this type derive from all of the member type templates. We can select
124  // the matching member for a tag using type deduction during overload
125  // resolution.
126  template <TagT N, typename PointerT, typename TraitsT>
129  template <TagT N> static void LookupOverload(...);
130  template <TagT N> struct Lookup {
131  // Compute a particular member type by resolving the lookup helper ovorload.
132  using MemberT = decltype(
133  LookupOverload<N>(static_cast<PointerSumTypeHelper *>(nullptr)));
134 
135  /// The Nth member's pointer type.
136  using PointerT = typename MemberT::PointerT;
137 
138  /// The Nth member's traits type.
139  using TraitsT = typename MemberT::TraitsT;
140  };
141 
142  // Next we need to compute the number of bits available for the discriminant
143  // by taking the min of the bits available for each member. Much of this
144  // would be amazingly easier with good constexpr support.
145  template <uintptr_t V, uintptr_t... Vs>
146  struct Min : std::integral_constant<
147  uintptr_t, (V < Min<Vs...>::value ? V : Min<Vs...>::value)> {
148  };
149  template <uintptr_t V>
150  struct Min<V> : std::integral_constant<uintptr_t, V> {};
151  enum { NumTagBits = Min<MemberTs::TraitsT::NumLowBitsAvailable...>::value };
152 
153  // Also compute the smallest discriminant and various masks for convenience.
154  enum : uint64_t {
155  MinTag = Min<MemberTs::Tag...>::value,
156  PointerMask = static_cast<uint64_t>(-1) << NumTagBits,
157  TagMask = ~PointerMask
158  };
159 
160  // Finally we need a recursive template to do static checks of each
161  // member.
162  template <typename MemberT, typename... InnerMemberTs>
163  struct Checker : Checker<InnerMemberTs...> {
164  static_assert(MemberT::Tag < (1 << NumTagBits),
165  "This discriminant value requires too many bits!");
166  };
167  template <typename MemberT> struct Checker<MemberT> : std::true_type {
168  static_assert(MemberT::Tag < (1 << NumTagBits),
169  "This discriminant value requires too many bits!");
170  };
171  static_assert(Checker<MemberTs...>::value,
172  "Each member must pass the checker.");
173 };
174 
175 } // end namespace detail
176 
177 // Teach DenseMap how to use PointerSumTypes as keys.
178 template <typename TagT, typename... MemberTs>
179 struct DenseMapInfo<PointerSumType<TagT, MemberTs...>> {
180  using SumType = PointerSumType<TagT, MemberTs...>;
181  using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
182  enum { SomeTag = HelperT::MinTag };
183  using SomePointerT =
184  typename HelperT::template Lookup<HelperT::MinTag>::PointerT;
185  using SomePointerInfo = DenseMapInfo<SomePointerT>;
186 
187  static inline SumType getEmptyKey() {
188  return SumType::create<SomeTag>(SomePointerInfo::getEmptyKey());
189  }
190 
191  static inline SumType getTombstoneKey() {
192  return SumType::create<SomeTag>(SomePointerInfo::getTombstoneKey());
193  }
194 
195  static unsigned getHashValue(const SumType &Arg) {
196  uintptr_t OpaqueValue = Arg.getOpaqueValue();
197  return DenseMapInfo<uintptr_t>::getHashValue(OpaqueValue);
198  }
199 
200  static bool isEqual(const SumType &LHS, const SumType &RHS) {
201  return LHS == RHS;
202  }
203 };
204 
205 } // end namespace llvm
206 
207 #endif // LLVM_ADT_POINTERSUMTYPE_H
bool operator==(const PointerSumType &R) const
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A compile time pair of an integer tag and the pointer-like type which it indexes within a sum type...
bool operator>(const PointerSumType &R) const
typename MemberT::TraitsT TraitsT
The Nth member&#39;s traits type.
uintptr_t getOpaqueValue() const
decltype(LookupOverload< N >(static_cast< PointerSumTypeHelper * >(nullptr))) MemberT
static PointerSumType create(typename HelperT::template Lookup< N >::PointerT Pointer)
A typed constructor for a specific tagged member of the sum type.
bool operator>=(const PointerSumType &R) const
#define P(N)
void * getImpl() const
bool operator<=(const PointerSumType &R) const
HelperT::template Lookup< N >::PointerT cast() const
bool operator!=(const PointerSumType &R) const
static Optional< unsigned > getTag(const TargetRegisterInfo *TRI, const MachineInstr &MI, const LoadInfo &LI)
A sum type over pointer-like types.
#define N
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
static LazyValueInfoImpl & getImpl(void *&PImpl, AssumptionCache *AC, const DataLayout *DL, DominatorTree *DT=nullptr)
This lazily constructs the LazyValueInfoImpl.
A helper template for implementing PointerSumType.
bool operator<(const PointerSumType &R) const
typename MemberT::PointerT PointerT
The Nth member&#39;s pointer type.