• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- llvm/ADT/PointerEmbeddedInt.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_POINTEREMBEDDEDINT_H
11 #define LLVM_ADT_POINTEREMBEDDEDINT_H
12 
13 #include "llvm/ADT/DenseMapInfo.h"
14 #include "llvm/Support/MathExtras.h"
15 #include "llvm/Support/PointerLikeTypeTraits.h"
16 #include <climits>
17 
18 namespace llvm {
19 
20 /// Utility to embed an integer into a pointer-like type. This is specifically
21 /// intended to allow embedding integers where fewer bits are required than
22 /// exist in a pointer, and the integer can participate in abstractions along
23 /// side other pointer-like types. For example it can be placed into a \c
24 /// PointerSumType or \c PointerUnion.
25 ///
26 /// Note that much like pointers, an integer value of zero has special utility
27 /// due to boolean conversions. For example, a non-null value can be tested for
28 /// in the above abstractions without testing the particular active member.
29 /// Also, the default constructed value zero initializes the integer.
30 template <typename IntT, int Bits = sizeof(IntT) * CHAR_BIT>
31 class PointerEmbeddedInt {
32   uintptr_t Value;
33 
34   // Note: This '<' is correct; using '<=' would result in some shifts
35   // overflowing their storage types.
36   static_assert(Bits < sizeof(uintptr_t) * CHAR_BIT,
37                 "Cannot embed more bits than we have in a pointer!");
38 
39   enum : uintptr_t {
40     // We shift as many zeros into the value as we can while preserving the
41     // number of bits desired for the integer.
42     Shift = sizeof(uintptr_t) * CHAR_BIT - Bits,
43 
44     // We also want to be able to mask out the preserved bits for asserts.
45     Mask = static_cast<uintptr_t>(-1) << Bits
46   };
47 
48   struct RawValueTag {
49     explicit RawValueTag() = default;
50   };
51 
52   friend class PointerLikeTypeTraits<PointerEmbeddedInt>;
53 
PointerEmbeddedInt(uintptr_t Value,RawValueTag)54   explicit PointerEmbeddedInt(uintptr_t Value, RawValueTag) : Value(Value) {}
55 
56 public:
PointerEmbeddedInt()57   PointerEmbeddedInt() : Value(0) {}
58 
PointerEmbeddedInt(IntT I)59   PointerEmbeddedInt(IntT I) {
60     *this = I;
61   }
62 
63   PointerEmbeddedInt &operator=(IntT I) {
64     assert((std::is_signed<IntT>::value ? llvm::isInt<Bits>(I)
65                                         : llvm::isUInt<Bits>(I)) &&
66            "Integer has bits outside those preserved!");
67     Value = static_cast<uintptr_t>(I) << Shift;
68     return *this;
69   }
70 
71   // Note that this implicit conversion additionally allows all of the basic
72   // comparison operators to work transparently, etc.
IntT()73   operator IntT() const {
74     if (std::is_signed<IntT>::value)
75       return static_cast<IntT>(static_cast<intptr_t>(Value) >> Shift);
76     return static_cast<IntT>(Value >> Shift);
77   }
78 };
79 
80 // Provide pointer like traits to support use with pointer unions and sum
81 // types.
82 template <typename IntT, int Bits>
83 class PointerLikeTypeTraits<PointerEmbeddedInt<IntT, Bits>> {
84   typedef PointerEmbeddedInt<IntT, Bits> T;
85 
86 public:
getAsVoidPointer(const T & P)87   static inline void *getAsVoidPointer(const T &P) {
88     return reinterpret_cast<void *>(P.Value);
89   }
getFromVoidPointer(void * P)90   static inline T getFromVoidPointer(void *P) {
91     return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag());
92   }
getFromVoidPointer(const void * P)93   static inline T getFromVoidPointer(const void *P) {
94     return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag());
95   }
96 
97   enum { NumLowBitsAvailable = T::Shift };
98 };
99 
100 // Teach DenseMap how to use PointerEmbeddedInt objects as keys if the Int type
101 // itself can be a key.
102 template <typename IntT, int Bits>
103 struct DenseMapInfo<PointerEmbeddedInt<IntT, Bits>> {
104   typedef PointerEmbeddedInt<IntT, Bits> T;
105 
106   typedef DenseMapInfo<IntT> IntInfo;
107 
108   static inline T getEmptyKey() { return IntInfo::getEmptyKey(); }
109   static inline T getTombstoneKey() { return IntInfo::getTombstoneKey(); }
110   static unsigned getHashValue(const T &Arg) {
111     return IntInfo::getHashValue(Arg);
112   }
113   static bool isEqual(const T &LHS, const T &RHS) { return LHS == RHS; }
114 };
115 }
116 
117 #endif
118