LLVM API Documentation
00001 //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the PointerIntPair class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ADT_POINTERINTPAIR_H 00015 #define LLVM_ADT_POINTERINTPAIR_H 00016 00017 #include "llvm/Support/PointerLikeTypeTraits.h" 00018 #include <cassert> 00019 00020 namespace llvm { 00021 00022 template<typename T> 00023 struct DenseMapInfo; 00024 00025 /// PointerIntPair - This class implements a pair of a pointer and small 00026 /// integer. It is designed to represent this in the space required by one 00027 /// pointer by bitmangling the integer into the low part of the pointer. This 00028 /// can only be done for small integers: typically up to 3 bits, but it depends 00029 /// on the number of bits available according to PointerLikeTypeTraits for the 00030 /// type. 00031 /// 00032 /// Note that PointerIntPair always puts the Int part in the highest bits 00033 /// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for 00034 /// the bool into bit #2, not bit #0, which allows the low two bits to be used 00035 /// for something else. For example, this allows: 00036 /// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool> 00037 /// ... and the two bools will land in different bits. 00038 /// 00039 template <typename PointerTy, unsigned IntBits, typename IntType=unsigned, 00040 typename PtrTraits = PointerLikeTypeTraits<PointerTy> > 00041 class PointerIntPair { 00042 intptr_t Value; 00043 enum { 00044 /// PointerBitMask - The bits that come from the pointer. 00045 PointerBitMask = 00046 ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable)-1), 00047 00048 /// IntShift - The number of low bits that we reserve for other uses, and 00049 /// keep zero. 00050 IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable-IntBits, 00051 00052 /// IntMask - This is the unshifted mask for valid bits of the int type. 00053 IntMask = (uintptr_t)(((intptr_t)1 << IntBits)-1), 00054 00055 // ShiftedIntMask - This is the bits for the integer shifted in place. 00056 ShiftedIntMask = (uintptr_t)(IntMask << IntShift) 00057 }; 00058 public: 00059 PointerIntPair() : Value(0) {} 00060 PointerIntPair(PointerTy Ptr, IntType Int) : Value(0) { 00061 assert(IntBits <= PtrTraits::NumLowBitsAvailable && 00062 "PointerIntPair formed with integer size too large for pointer"); 00063 setPointer(Ptr); 00064 setInt(Int); 00065 } 00066 00067 PointerTy getPointer() const { 00068 return reinterpret_cast<PointerTy>(Value & PointerBitMask); 00069 } 00070 00071 IntType getInt() const { 00072 return (IntType)((Value >> IntShift) & IntMask); 00073 } 00074 00075 void setPointer(PointerTy Ptr) { 00076 intptr_t PtrVal = reinterpret_cast<intptr_t>(Ptr); 00077 assert((PtrVal & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 && 00078 "Pointer is not sufficiently aligned"); 00079 // Preserve all low bits, just update the pointer. 00080 Value = PtrVal | (Value & ~PointerBitMask); 00081 } 00082 00083 void setInt(IntType Int) { 00084 intptr_t IntVal = Int; 00085 assert(IntVal < (1 << IntBits) && "Integer too large for field"); 00086 00087 // Preserve all bits other than the ones we are updating. 00088 Value &= ~ShiftedIntMask; // Remove integer field. 00089 Value |= IntVal << IntShift; // Set new integer. 00090 } 00091 00092 void *getOpaqueValue() const { return reinterpret_cast<void*>(Value); } 00093 void setFromOpaqueValue(void *Val) { Value = reinterpret_cast<intptr_t>(Val);} 00094 00095 static PointerIntPair getFromOpaqueValue(void *V) { 00096 PointerIntPair P; P.setFromOpaqueValue(V); return P; 00097 } 00098 00099 bool operator==(const PointerIntPair &RHS) const {return Value == RHS.Value;} 00100 bool operator!=(const PointerIntPair &RHS) const {return Value != RHS.Value;} 00101 bool operator<(const PointerIntPair &RHS) const {return Value < RHS.Value;} 00102 bool operator>(const PointerIntPair &RHS) const {return Value > RHS.Value;} 00103 bool operator<=(const PointerIntPair &RHS) const {return Value <= RHS.Value;} 00104 bool operator>=(const PointerIntPair &RHS) const {return Value >= RHS.Value;} 00105 }; 00106 00107 // Provide specialization of DenseMapInfo for PointerIntPair. 00108 template<typename PointerTy, unsigned IntBits, typename IntType> 00109 struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType> > { 00110 typedef PointerIntPair<PointerTy, IntBits, IntType> Ty; 00111 static Ty getEmptyKey() { 00112 intptr_t Val = -1; 00113 Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable; 00114 return Ty(reinterpret_cast<PointerTy>(Val), IntType((1 << IntBits)-1)); 00115 } 00116 static Ty getTombstoneKey() { 00117 intptr_t Val = -2; 00118 Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable; 00119 return Ty(reinterpret_cast<PointerTy>(Val), IntType(0)); 00120 } 00121 static unsigned getHashValue(Ty V) { 00122 uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue()); 00123 return unsigned(IV) ^ unsigned(IV >> 9); 00124 } 00125 static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; } 00126 static bool isPod() { return true; } 00127 }; 00128 00129 // Teach SmallPtrSet that PointerIntPair is "basically a pointer". 00130 template<typename PointerTy, unsigned IntBits, typename IntType, 00131 typename PtrTraits> 00132 class PointerLikeTypeTraits<PointerIntPair<PointerTy, IntBits, IntType, 00133 PtrTraits> > { 00134 public: 00135 static inline void * 00136 getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) { 00137 return P.getOpaqueValue(); 00138 } 00139 static inline PointerIntPair<PointerTy, IntBits, IntType> 00140 getFromVoidPointer(void *P) { 00141 return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); 00142 } 00143 enum { 00144 NumLowBitsAvailable = 00145 PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable - IntBits 00146 }; 00147 }; 00148 00149 } // end namespace llvm 00150 #endif