LLVM  10.0.0svn
PointerIntPair.h
Go to the documentation of this file.
1 //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- 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 PointerIntPair class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_POINTERINTPAIR_H
14 #define LLVM_ADT_POINTERINTPAIR_H
15 
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  // Used by MSVC visualizer and generally helpful for debugging/visualizing.
46  using InfoTy = Info;
47  intptr_t Value = 0;
48 
49 public:
50  constexpr PointerIntPair() = default;
51 
52  PointerIntPair(PointerTy PtrVal, IntType IntVal) {
53  setPointerAndInt(PtrVal, IntVal);
54  }
55 
56  explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); }
57 
58  PointerTy getPointer() const { return Info::getPointer(Value); }
59 
60  IntType getInt() const { return (IntType)Info::getInt(Value); }
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 
92  void setFromOpaqueValue(void *Val) {
93  Value = reinterpret_cast<intptr_t>(Val);
94  }
95 
98  P.setFromOpaqueValue(V);
99  return P;
100  }
101 
102  // Allow PointerIntPairs to be created from const void * if and only if the
103  // pointer type could be created from a const void *.
104  static PointerIntPair getFromOpaqueValue(const void *V) {
105  (void)PtrTraits::getFromVoidPointer(V);
106  return getFromOpaqueValue(const_cast<void *>(V));
107  }
108 
109  bool operator==(const PointerIntPair &RHS) const {
110  return Value == RHS.Value;
111  }
112 
113  bool operator!=(const PointerIntPair &RHS) const {
114  return Value != RHS.Value;
115  }
116 
117  bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; }
118  bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; }
119 
120  bool operator<=(const PointerIntPair &RHS) const {
121  return Value <= RHS.Value;
122  }
123 
124  bool operator>=(const PointerIntPair &RHS) const {
125  return Value >= RHS.Value;
126  }
127 };
128 
129 // Specialize is_trivially_copyable to avoid limitation of llvm::is_trivially_copyable
130 // when compiled with gcc 4.9.
131 template <typename PointerTy, unsigned IntBits, typename IntType,
132  typename PtrTraits,
133  typename Info>
134 struct is_trivially_copyable<PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>> : std::true_type {
135 #ifdef HAVE_STD_IS_TRIVIALLY_COPYABLE
136  static_assert(std::is_trivially_copyable<PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>>::value,
137  "inconsistent behavior between llvm:: and std:: implementation of is_trivially_copyable");
138 #endif
139 };
140 
141 
142 template <typename PointerT, unsigned IntBits, typename PtrTraits>
143 struct PointerIntPairInfo {
144  static_assert(PtrTraits::NumLowBitsAvailable <
145  std::numeric_limits<uintptr_t>::digits,
146  "cannot use a pointer type that has all bits free");
147  static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
148  "PointerIntPair with integer size too large for pointer");
149  enum : uintptr_t {
150  /// PointerBitMask - The bits that come from the pointer.
151  PointerBitMask =
152  ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1),
153 
154  /// IntShift - The number of low bits that we reserve for other uses, and
155  /// keep zero.
156  IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits,
157 
158  /// IntMask - This is the unshifted mask for valid bits of the int type.
159  IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1),
160 
161  // ShiftedIntMask - This is the bits for the integer shifted in place.
162  ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
163  };
164 
165  static PointerT getPointer(intptr_t Value) {
166  return PtrTraits::getFromVoidPointer(
167  reinterpret_cast<void *>(Value & PointerBitMask));
168  }
169 
171  return (Value >> IntShift) & IntMask;
172  }
173 
174  static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) {
175  intptr_t PtrWord =
176  reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
177  assert((PtrWord & ~PointerBitMask) == 0 &&
178  "Pointer is not sufficiently aligned");
179  // Preserve all low bits, just update the pointer.
180  return PtrWord | (OrigValue & ~PointerBitMask);
181  }
182 
183  static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) {
184  intptr_t IntWord = static_cast<intptr_t>(Int);
185  assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
186 
187  // Preserve all bits other than the ones we are updating.
188  return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift;
189  }
190 };
191 
192 // Provide specialization of DenseMapInfo for PointerIntPair.
193 template <typename PointerTy, unsigned IntBits, typename IntType>
194 struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>> {
196 
197  static Ty getEmptyKey() {
198  uintptr_t Val = static_cast<uintptr_t>(-1);
199  Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable;
200  return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
201  }
202 
203  static Ty getTombstoneKey() {
204  uintptr_t Val = static_cast<uintptr_t>(-2);
205  Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
206  return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
207  }
208 
209  static unsigned getHashValue(Ty V) {
210  uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
211  return unsigned(IV) ^ unsigned(IV >> 9);
212  }
213 
214  static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
215 };
216 
217 // Teach SmallPtrSet that PointerIntPair is "basically a pointer".
218 template <typename PointerTy, unsigned IntBits, typename IntType,
219  typename PtrTraits>
221  PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> {
222  static inline void *
224  return P.getOpaqueValue();
225  }
226 
230  }
231 
233  getFromVoidPointer(const void *P) {
235  }
236 
237  enum { NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits };
238 };
239 
240 } // end namespace llvm
241 
242 #endif // LLVM_ADT_POINTERINTPAIR_H
bool operator!=(const PointerIntPair &RHS) const
void setInt(IntType IntVal)
bool operator>(const PointerIntPair &RHS) const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:21
void setPointer(PointerTy PtrVal)
PointerTy * getAddrOfPointer()
static unsigned getInt(StringRef R)
Get an unsigned integer, including error checks.
Definition: DataLayout.cpp:214
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
Analysis containing CSE Info
Definition: CSEInfo.cpp:20
#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)
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