1 | //===- llvm/ADT/PointerUnion.h - Discriminated Union of 2 Ptrs --*- C++ -*-===// |
---|---|

2 | // |

3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |

4 | // See https://llvm.org/LICENSE.txt for license information. |

5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |

6 | // |

7 | //===----------------------------------------------------------------------===// |

8 | // |

9 | // This file defines the PointerUnion class, which is a discriminated union of |

10 | // pointer types. |

11 | // |

12 | //===----------------------------------------------------------------------===// |

13 | |

14 | #ifndef LLVM_ADT_POINTERUNION_H |

15 | #define LLVM_ADT_POINTERUNION_H |

16 | |

17 | #include "llvm/ADT/DenseMapInfo.h" |

18 | #include "llvm/ADT/PointerIntPair.h" |

19 | #include "llvm/Support/PointerLikeTypeTraits.h" |

20 | #include <cassert> |

21 | #include <cstddef> |

22 | #include <cstdint> |

23 | |

24 | namespace llvm { |

25 | |

26 | template <typename T> struct PointerUnionTypeSelectorReturn { |

27 | using Return = T; |

28 | }; |

29 | |

30 | /// Get a type based on whether two types are the same or not. |

31 | /// |

32 | /// For: |

33 | /// |

34 | /// \code |

35 | /// using Ret = typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return; |

36 | /// \endcode |

37 | /// |

38 | /// Ret will be EQ type if T1 is same as T2 or NE type otherwise. |

39 | template <typename T1, typename T2, typename RET_EQ, typename RET_NE> |

40 | struct PointerUnionTypeSelector { |

41 | using Return = typename PointerUnionTypeSelectorReturn<RET_NE>::Return; |

42 | }; |

43 | |

44 | template <typename T, typename RET_EQ, typename RET_NE> |

45 | struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> { |

46 | using Return = typename PointerUnionTypeSelectorReturn<RET_EQ>::Return; |

47 | }; |

48 | |

49 | template <typename T1, typename T2, typename RET_EQ, typename RET_NE> |

50 | struct PointerUnionTypeSelectorReturn< |

51 | PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>> { |

52 | using Return = |

53 | typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::Return; |

54 | }; |

55 | |

56 | namespace pointer_union_detail { |

57 | /// Determine the number of bits required to store integers with values < n. |

58 | /// This is ceil(log2(n)). |

59 | constexpr int bitsRequired(unsigned n) { |

60 | return n > 1 ? 1 + bitsRequired((n + 1) / 2) : 0; |

61 | } |

62 | |

63 | template <typename... Ts> constexpr int lowBitsAvailable() { |

64 | return std::min<int>({PointerLikeTypeTraits<Ts>::NumLowBitsAvailable...}); |

65 | } |

66 | |

67 | /// Find the index of a type in a list of types. TypeIndex<T, Us...>::Index |

68 | /// is the index of T in Us, or sizeof...(Us) if T does not appear in the |

69 | /// list. |

70 | template <typename T, typename ...Us> struct TypeIndex; |

71 | template <typename T, typename ...Us> struct TypeIndex<T, T, Us...> { |

72 | static constexpr int Index = 0; |

73 | }; |

74 | template <typename T, typename U, typename... Us> |

75 | struct TypeIndex<T, U, Us...> { |

76 | static constexpr int Index = 1 + TypeIndex<T, Us...>::Index; |

77 | }; |

78 | template <typename T> struct TypeIndex<T> { |

79 | static constexpr int Index = 0; |

80 | }; |

81 | |

82 | /// Find the first type in a list of types. |

83 | template <typename T, typename...> struct GetFirstType { |

84 | using type = T; |

85 | }; |

86 | |

87 | /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion |

88 | /// for the template arguments. |

89 | template <typename ...PTs> class PointerUnionUIntTraits { |

90 | public: |

91 | static inline void *getAsVoidPointer(void *P) { return P; } |

92 | static inline void *getFromVoidPointer(void *P) { return P; } |

93 | static constexpr int NumLowBitsAvailable = lowBitsAvailable<PTs...>(); |

94 | }; |

95 | |

96 | template <typename Derived, typename ValTy, int I, typename ...Types> |

97 | class PointerUnionMembers; |

98 | |

99 | template <typename Derived, typename ValTy, int I> |

100 | class PointerUnionMembers<Derived, ValTy, I> { |

101 | protected: |

102 | ValTy Val; |

103 | PointerUnionMembers() = default; |

104 | PointerUnionMembers(ValTy Val) : Val(Val) {} |

105 | |

106 | friend struct PointerLikeTypeTraits<Derived>; |

107 | }; |

108 | |

109 | template <typename Derived, typename ValTy, int I, typename Type, |

110 | typename ...Types> |

111 | class PointerUnionMembers<Derived, ValTy, I, Type, Types...> |

112 | : public PointerUnionMembers<Derived, ValTy, I + 1, Types...> { |

113 | using Base = PointerUnionMembers<Derived, ValTy, I + 1, Types...>; |

114 | public: |

115 | using Base::Base; |

116 | PointerUnionMembers() = default; |

117 | PointerUnionMembers(Type V) |

118 | : Base(ValTy(const_cast<void *>( |

119 | PointerLikeTypeTraits<Type>::getAsVoidPointer(V)), |

120 | I)) {} |

121 | |

122 | using Base::operator=; |

123 | Derived &operator=(Type V) { |

124 | this->Val = ValTy( |

125 | const_cast<void *>(PointerLikeTypeTraits<Type>::getAsVoidPointer(V)), |

126 | I); |

127 | return static_cast<Derived &>(*this); |

128 | }; |

129 | }; |

130 | } |

131 | |

132 | /// A discriminated union of two or more pointer types, with the discriminator |

133 | /// in the low bit of the pointer. |

134 | /// |

135 | /// This implementation is extremely efficient in space due to leveraging the |

136 | /// low bits of the pointer, while exposing a natural and type-safe API. |

137 | /// |

138 | /// Common use patterns would be something like this: |

139 | /// PointerUnion<int*, float*> P; |

140 | /// P = (int*)0; |

141 | /// printf("%d %d", P.is<int*>(), P.is<float*>()); // prints "1 0" |

142 | /// X = P.get<int*>(); // ok. |

143 | /// Y = P.get<float*>(); // runtime assertion failure. |

144 | /// Z = P.get<double*>(); // compile time failure. |

145 | /// P = (float*)0; |

146 | /// Y = P.get<float*>(); // ok. |

147 | /// X = P.get<int*>(); // runtime assertion failure. |

148 | template <typename... PTs> |

149 | class PointerUnion |

150 | : public pointer_union_detail::PointerUnionMembers< |

151 | PointerUnion<PTs...>, |

152 | PointerIntPair< |

153 | void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int, |

154 | pointer_union_detail::PointerUnionUIntTraits<PTs...>>, |

155 | 0, PTs...> { |

156 | // The first type is special because we want to directly cast a pointer to a |

157 | // default-initialized union to a pointer to the first type. But we don't |

158 | // want PointerUnion to be a 'template <typename First, typename ...Rest>' |

159 | // because it's much more convenient to have a name for the whole pack. So |

160 | // split off the first type here. |

161 | using First = typename pointer_union_detail::GetFirstType<PTs...>::type; |

162 | using Base = typename PointerUnion::PointerUnionMembers; |

163 | |

164 | public: |

165 | PointerUnion() = default; |

166 | |

167 | PointerUnion(std::nullptr_t) : PointerUnion() {} |

168 | using Base::Base; |

169 | |

170 | /// Test if the pointer held in the union is null, regardless of |

171 | /// which type it is. |

172 | bool isNull() const { return !this->Val.getPointer(); } |

173 | |

174 | explicit operator bool() const { return !isNull(); } |

175 | |

176 | /// Test if the Union currently holds the type matching T. |

177 | template <typename T> bool is() const { |

178 | constexpr int Index = pointer_union_detail::TypeIndex<T, PTs...>::Index; |

179 | static_assert(Index < sizeof...(PTs), |

180 | "PointerUnion::is<T> given type not in the union"); |

181 | return this->Val.getInt() == Index; |

182 | } |

183 | |

184 | /// Returns the value of the specified pointer type. |

185 | /// |

186 | /// If the specified pointer type is incorrect, assert. |

187 | template <typename T> T get() const { |

188 | assert(is<T>() && "Invalid accessor called"); |

189 | return PointerLikeTypeTraits<T>::getFromVoidPointer(this->Val.getPointer()); |

190 | } |

191 | |

192 | /// Returns the current pointer if it is of the specified pointer type, |

193 | /// otherwise returns null. |

194 | template <typename T> T dyn_cast() const { |

195 | if (is<T>()) |

196 | return get<T>(); |

197 | return T(); |

198 | } |

199 | |

200 | /// If the union is set to the first pointer type get an address pointing to |

201 | /// it. |

202 | First const *getAddrOfPtr1() const { |

203 | return const_cast<PointerUnion *>(this)->getAddrOfPtr1(); |

204 | } |

205 | |

206 | /// If the union is set to the first pointer type get an address pointing to |

207 | /// it. |

208 | First *getAddrOfPtr1() { |

209 | assert(is<First>() && "Val is not the first pointer"); |

210 | assert( |

211 | PointerLikeTypeTraits<First>::getAsVoidPointer(get<First>()) == |

212 | this->Val.getPointer() && |

213 | "Can't get the address because PointerLikeTypeTraits changes the ptr"); |

214 | return const_cast<First *>( |

215 | reinterpret_cast<const First *>(this->Val.getAddrOfPointer())); |

216 | } |

217 | |

218 | /// Assignment from nullptr which just clears the union. |

219 | const PointerUnion &operator=(std::nullptr_t) { |

220 | this->Val.initWithPointer(nullptr); |

221 | return *this; |

222 | } |

223 | |

224 | /// Assignment from elements of the union. |

225 | using Base::operator=; |

226 | |

227 | void *getOpaqueValue() const { return this->Val.getOpaqueValue(); } |

228 | static inline PointerUnion getFromOpaqueValue(void *VP) { |

229 | PointerUnion V; |

230 | V.Val = decltype(V.Val)::getFromOpaqueValue(VP); |

231 | return V; |

232 | } |

233 | }; |

234 | |

235 | template <typename ...PTs> |

236 | bool operator==(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) { |

237 | return lhs.getOpaqueValue() == rhs.getOpaqueValue(); |

238 | } |

239 | |

240 | template <typename ...PTs> |

241 | bool operator!=(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) { |

242 | return lhs.getOpaqueValue() != rhs.getOpaqueValue(); |

243 | } |

244 | |

245 | template <typename ...PTs> |

246 | bool operator<(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) { |

247 | return lhs.getOpaqueValue() < rhs.getOpaqueValue(); |

248 | } |

249 | |

250 | // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has |

251 | // # low bits available = min(PT1bits,PT2bits)-1. |

252 | template <typename ...PTs> |

253 | struct PointerLikeTypeTraits<PointerUnion<PTs...>> { |

254 | static inline void *getAsVoidPointer(const PointerUnion<PTs...> &P) { |

255 | return P.getOpaqueValue(); |

256 | } |

257 | |

258 | static inline PointerUnion<PTs...> getFromVoidPointer(void *P) { |

259 | return PointerUnion<PTs...>::getFromOpaqueValue(P); |

260 | } |

261 | |

262 | // The number of bits available are the min of the pointer types minus the |

263 | // bits needed for the discriminator. |

264 | static constexpr int NumLowBitsAvailable = PointerLikeTypeTraits<decltype( |

265 | PointerUnion<PTs...>::Val)>::NumLowBitsAvailable; |

266 | }; |

267 | |

268 | // Teach DenseMap how to use PointerUnions as keys. |

269 | template <typename ...PTs> struct DenseMapInfo<PointerUnion<PTs...>> { |

270 | using Union = PointerUnion<PTs...>; |

271 | using FirstInfo = |

272 | DenseMapInfo<typename pointer_union_detail::GetFirstType<PTs...>::type>; |

273 | |

274 | static inline Union getEmptyKey() { return Union(FirstInfo::getEmptyKey()); } |

275 | |

276 | static inline Union getTombstoneKey() { |

277 | return Union(FirstInfo::getTombstoneKey()); |

278 | } |

279 | |

280 | static unsigned getHashValue(const Union &UnionVal) { |

281 | intptr_t key = (intptr_t)UnionVal.getOpaqueValue(); |

282 | return DenseMapInfo<intptr_t>::getHashValue(key); |

283 | } |

284 | |

285 | static bool isEqual(const Union &LHS, const Union &RHS) { |

286 | return LHS == RHS; |

287 | } |

288 | }; |

289 | |

290 | } // end namespace llvm |

291 | |

292 | #endif // LLVM_ADT_POINTERUNION_H |

293 |