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