LLVM  6.0.0svn
PointerIntPair.h
Go to the documentation of this file.
1 //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- 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 // This file defines the PointerIntPair class.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ADT_POINTERINTPAIR_H
15 #define LLVM_ADT_POINTERINTPAIR_H
16 
18 #include <cassert>
19 #include <cstdint>
20 #include <limits>
21 
22 namespace llvm {
23 
24 template <typename T> struct DenseMapInfo;
25 template <typename PointerT, unsigned IntBits, typename PtrTraits>
27 
28 /// PointerIntPair - This class implements a pair of a pointer and small
29 /// integer. It is designed to represent this in the space required by one
30 /// pointer by bitmangling the integer into the low part of the pointer. This
31 /// can only be done for small integers: typically up to 3 bits, but it depends
32 /// on the number of bits available according to PointerLikeTypeTraits for the
33 /// type.
34 ///
35 /// Note that PointerIntPair always puts the IntVal part in the highest bits
36 /// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for
37 /// the bool into bit #2, not bit #0, which allows the low two bits to be used
38 /// for something else. For example, this allows:
39 /// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
40 /// ... and the two bools will land in different bits.
41 template <typename PointerTy, unsigned IntBits, typename IntType = unsigned,
42  typename PtrTraits = PointerLikeTypeTraits<PointerTy>,
45  intptr_t Value = 0;
46 
47 public:
48  constexpr PointerIntPair() = default;
49 
50  PointerIntPair(PointerTy PtrVal, IntType IntVal) {
51  setPointerAndInt(PtrVal, IntVal);
52  }
53 
54  explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); }
55 
56  PointerTy getPointer() const { return Info::getPointer(Value); }
57 
58  IntType getInt() const { return (IntType)Info::getInt(Value); }
59 
60  void setPointer(PointerTy PtrVal) {
61  Value = Info::updatePointer(Value, PtrVal);
62  }
63 
64  void setInt(IntType IntVal) {
65  Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal));
66  }
67 
68  void initWithPointer(PointerTy PtrVal) {
69  Value = Info::updatePointer(0, PtrVal);
70  }
71 
72  void setPointerAndInt(PointerTy PtrVal, IntType IntVal) {
73  Value = Info::updateInt(Info::updatePointer(0, PtrVal),
74  static_cast<intptr_t>(IntVal));
75  }
76 
77  PointerTy const *getAddrOfPointer() const {
78  return const_cast<PointerIntPair *>(this)->getAddrOfPointer();
79  }
80 
82  assert(Value == reinterpret_cast<intptr_t>(getPointer()) &&
83  "Can only return the address if IntBits is cleared and "
84  "PtrTraits doesn't change the pointer");
85  return reinterpret_cast<PointerTy *>(&Value);
86  }
87 
88  void *getOpaqueValue() const { return reinterpret_cast<void *>(Value); }
89 
90  void setFromOpaqueValue(void *Val) {
91  Value = reinterpret_cast<intptr_t>(Val);
92  }
93 
96  P.setFromOpaqueValue(V);
97  return P;
98  }
99 
100  // Allow PointerIntPairs to be created from const void * if and only if the
101  // pointer type could be created from a const void *.
102  static PointerIntPair getFromOpaqueValue(const void *V) {
103  (void)PtrTraits::getFromVoidPointer(V);
104  return getFromOpaqueValue(const_cast<void *>(V));
105  }
106 
107  bool operator==(const PointerIntPair &RHS) const {
108  return Value == RHS.Value;
109  }
110 
111  bool operator!=(const PointerIntPair &RHS) const {
112  return Value != RHS.Value;
113  }
114 
115  bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; }
116  bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; }
117 
118  bool operator<=(const PointerIntPair &RHS) const {
119  return Value <= RHS.Value;
120  }
121 
122  bool operator>=(const PointerIntPair &RHS) const {
123  return Value >= RHS.Value;
124  }
125 };
126 
127 template <typename PointerT, unsigned IntBits, typename PtrTraits>
128 struct PointerIntPairInfo {
129  static_assert(PtrTraits::NumLowBitsAvailable <
130  std::numeric_limits<uintptr_t>::digits,
131  "cannot use a pointer type that has all bits free");
132  static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
133  "PointerIntPair with integer size too large for pointer");
134  enum : uintptr_t {
135  /// PointerBitMask - The bits that come from the pointer.
136  PointerBitMask =
137  ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1),
138 
139  /// IntShift - The number of low bits that we reserve for other uses, and
140  /// keep zero.
141  IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits,
142 
143  /// IntMask - This is the unshifted mask for valid bits of the int type.
144  IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1),
145 
146  // ShiftedIntMask - This is the bits for the integer shifted in place.
147  ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
148  };
149 
150  static PointerT getPointer(intptr_t Value) {
151  return PtrTraits::getFromVoidPointer(
152  reinterpret_cast<void *>(Value & PointerBitMask));
153  }
154 
156  return (Value >> IntShift) & IntMask;
157  }
158 
159  static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) {
160  intptr_t PtrWord =
161  reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
162  assert((PtrWord & ~PointerBitMask) == 0 &&
163  "Pointer is not sufficiently aligned");
164  // Preserve all low bits, just update the pointer.
165  return PtrWord | (OrigValue & ~PointerBitMask);
166  }
167 
168  static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) {
169  intptr_t IntWord = static_cast<intptr_t>(Int);
170  assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
171 
172  // Preserve all bits other than the ones we are updating.
173  return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift;
174  }
175 };
176 
177 template <typename T> struct isPodLike;
178 template <typename PointerTy, unsigned IntBits, typename IntType>
179 struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType>> {
180  static const bool value = true;
181 };
182 
183 // Provide specialization of DenseMapInfo for PointerIntPair.
184 template <typename PointerTy, unsigned IntBits, typename IntType>
185 struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>> {
187 
188  static Ty getEmptyKey() {
189  uintptr_t Val = static_cast<uintptr_t>(-1);
190  Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable;
191  return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
192  }
193 
194  static Ty getTombstoneKey() {
195  uintptr_t Val = static_cast<uintptr_t>(-2);
196  Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
197  return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
198  }
199 
200  static unsigned getHashValue(Ty V) {
201  uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
202  return unsigned(IV) ^ unsigned(IV >> 9);
203  }
204 
205  static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
206 };
207 
208 // Teach SmallPtrSet that PointerIntPair is "basically a pointer".
209 template <typename PointerTy, unsigned IntBits, typename IntType,
210  typename PtrTraits>
212  PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> {
213  static inline void *
215  return P.getOpaqueValue();
216  }
217 
221  }
222 
224  getFromVoidPointer(const void *P) {
226  }
227 
228  enum { NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits };
229 };
230 
231 } // end namespace llvm
232 
233 #endif // LLVM_ADT_POINTERINTPAIR_H
bool operator!=(const PointerIntPair &RHS) const
void setInt(IntType IntVal)
bool operator>(const PointerIntPair &RHS) const
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
PointerTy getPointer() const
bool operator<=(const PointerIntPair &RHS) const
static PointerIntPair getFromOpaqueValue(const void *V)
static PointerIntPair getFromOpaqueValue(void *V)
void * PointerTy
Definition: GenericValue.h:22
void setPointer(PointerTy PtrVal)
PointerTy * getAddrOfPointer()
static unsigned getInt(StringRef R)
Get an unsigned integer, including error checks.
Definition: DataLayout.cpp:209
PointerTy const * getAddrOfPointer() const
void * getOpaqueValue() const
static intptr_t updateInt(intptr_t OrigValue, intptr_t Int)
static PointerIntPair< PointerTy, IntBits, IntType > getFromVoidPointer(const void *P)
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
void setFromOpaqueValue(void *Val)
bool operator<(const PointerIntPair &RHS) const
IntType getInt() const
#define P(N)
static void * getAsVoidPointer(const PointerIntPair< PointerTy, IntBits, IntType > &P)
PointerIntPair - This class implements a pair of a pointer and small integer.
void initWithPointer(PointerTy PtrVal)
static PointerIntPair< PointerTy, IntBits, IntType > getFromVoidPointer(void *P)
PointerIntPair(PointerTy PtrVal, IntType IntVal)
static PointerT getPointer(intptr_t Value)
static intptr_t getInt(intptr_t Value)
isPodLike - This is a type trait that is used to determine whether a given type can be copied around ...
Definition: ArrayRef.h:530
static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr)
void setPointerAndInt(PointerTy PtrVal, IntType IntVal)
constexpr PointerIntPair()=default
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator>=(const PointerIntPair &RHS) const
LLVM Value Representation.
Definition: Value.h:73
PointerIntPair(PointerTy PtrVal)
bool operator==(const PointerIntPair &RHS) const