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