134b763694e74ee16e68fd85488bfe0443c51170dChris Lattner//===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===// 234b763694e74ee16e68fd85488bfe0443c51170dChris Lattner// 334b763694e74ee16e68fd85488bfe0443c51170dChris Lattner// The LLVM Compiler Infrastructure 434b763694e74ee16e68fd85488bfe0443c51170dChris Lattner// 534b763694e74ee16e68fd85488bfe0443c51170dChris Lattner// This file is distributed under the University of Illinois Open Source 634b763694e74ee16e68fd85488bfe0443c51170dChris Lattner// License. See LICENSE.TXT for details. 734b763694e74ee16e68fd85488bfe0443c51170dChris Lattner// 834b763694e74ee16e68fd85488bfe0443c51170dChris Lattner//===----------------------------------------------------------------------===// 934b763694e74ee16e68fd85488bfe0443c51170dChris Lattner// 1034b763694e74ee16e68fd85488bfe0443c51170dChris Lattner// This file defines the PointerIntPair class. 1134b763694e74ee16e68fd85488bfe0443c51170dChris Lattner// 1234b763694e74ee16e68fd85488bfe0443c51170dChris Lattner//===----------------------------------------------------------------------===// 1334b763694e74ee16e68fd85488bfe0443c51170dChris Lattner 1434b763694e74ee16e68fd85488bfe0443c51170dChris Lattner#ifndef LLVM_ADT_POINTERINTPAIR_H 1534b763694e74ee16e68fd85488bfe0443c51170dChris Lattner#define LLVM_ADT_POINTERINTPAIR_H 1634b763694e74ee16e68fd85488bfe0443c51170dChris Lattner 17e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner#include "llvm/Support/PointerLikeTypeTraits.h" 1834b763694e74ee16e68fd85488bfe0443c51170dChris Lattner#include <cassert> 1934b763694e74ee16e68fd85488bfe0443c51170dChris Lattner 2034b763694e74ee16e68fd85488bfe0443c51170dChris Lattnernamespace llvm { 213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 229ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattnertemplate<typename T> 239ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattnerstruct DenseMapInfo; 243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2534b763694e74ee16e68fd85488bfe0443c51170dChris Lattner/// PointerIntPair - This class implements a pair of a pointer and small 26d55da4de048684e3791dbae8018666e5b7549506Chris Lattner/// integer. It is designed to represent this in the space required by one 2734b763694e74ee16e68fd85488bfe0443c51170dChris Lattner/// pointer by bitmangling the integer into the low part of the pointer. This 2834b763694e74ee16e68fd85488bfe0443c51170dChris Lattner/// can only be done for small integers: typically up to 3 bits, but it depends 29e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner/// on the number of bits available according to PointerLikeTypeTraits for the 30e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner/// type. 31e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner/// 32e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner/// Note that PointerIntPair always puts the Int part in the highest bits 3354e01d06db7c04208a684e34cb82b0847a077261Chris Lattner/// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for 34e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner/// the bool into bit #2, not bit #0, which allows the low two bits to be used 35e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner/// for something else. For example, this allows: 3654e01d06db7c04208a684e34cb82b0847a077261Chris Lattner/// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool> 37e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner/// ... and the two bools will land in different bits. 3834b763694e74ee16e68fd85488bfe0443c51170dChris Lattner/// 39540db8bcb8d7dae55456d8564c1d54071ec6ed50Chris Lattnertemplate <typename PointerTy, unsigned IntBits, typename IntType=unsigned, 40540db8bcb8d7dae55456d8564c1d54071ec6ed50Chris Lattner typename PtrTraits = PointerLikeTypeTraits<PointerTy> > 4134b763694e74ee16e68fd85488bfe0443c51170dChris Lattnerclass PointerIntPair { 4234b763694e74ee16e68fd85488bfe0443c51170dChris Lattner intptr_t Value; 43e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner enum { 44e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner /// PointerBitMask - The bits that come from the pointer. 45b14a495c3682a9804e81326691f039ab2e15738fBill Wendling PointerBitMask = 463485d25a0e3355a13a9fe073fa5cd98838431ef0Bill Wendling ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable)-1), 47b14a495c3682a9804e81326691f039ab2e15738fBill Wendling 48e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner /// IntShift - The number of low bits that we reserve for other uses, and 49e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner /// keep zero. 503485d25a0e3355a13a9fe073fa5cd98838431ef0Bill Wendling IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable-IntBits, 51e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner 52e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner /// IntMask - This is the unshifted mask for valid bits of the int type. 533485d25a0e3355a13a9fe073fa5cd98838431ef0Bill Wendling IntMask = (uintptr_t)(((intptr_t)1 << IntBits)-1), 54e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner 55e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner // ShiftedIntMask - This is the bits for the integer shifted in place. 563485d25a0e3355a13a9fe073fa5cd98838431ef0Bill Wendling ShiftedIntMask = (uintptr_t)(IntMask << IntShift) 57e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner }; 5834b763694e74ee16e68fd85488bfe0443c51170dChris Lattnerpublic: 5934b763694e74ee16e68fd85488bfe0443c51170dChris Lattner PointerIntPair() : Value(0) {} 6034b763694e74ee16e68fd85488bfe0443c51170dChris Lattner PointerIntPair(PointerTy Ptr, IntType Int) : Value(0) { 61e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner assert(IntBits <= PtrTraits::NumLowBitsAvailable && 62e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner "PointerIntPair formed with integer size too large for pointer"); 6334b763694e74ee16e68fd85488bfe0443c51170dChris Lattner setPointer(Ptr); 6434b763694e74ee16e68fd85488bfe0443c51170dChris Lattner setInt(Int); 6534b763694e74ee16e68fd85488bfe0443c51170dChris Lattner } 6634b763694e74ee16e68fd85488bfe0443c51170dChris Lattner 6734b763694e74ee16e68fd85488bfe0443c51170dChris Lattner PointerTy getPointer() const { 682fed70daaf6cf77ec62166041fef11ba7cf68173John McCall return PtrTraits::getFromVoidPointer( 692fed70daaf6cf77ec62166041fef11ba7cf68173John McCall reinterpret_cast<void*>(Value & PointerBitMask)); 7034b763694e74ee16e68fd85488bfe0443c51170dChris Lattner } 713a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7234b763694e74ee16e68fd85488bfe0443c51170dChris Lattner IntType getInt() const { 73e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner return (IntType)((Value >> IntShift) & IntMask); 7434b763694e74ee16e68fd85488bfe0443c51170dChris Lattner } 753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7634b763694e74ee16e68fd85488bfe0443c51170dChris Lattner void setPointer(PointerTy Ptr) { 772fed70daaf6cf77ec62166041fef11ba7cf68173John McCall intptr_t PtrVal 782fed70daaf6cf77ec62166041fef11ba7cf68173John McCall = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr)); 79e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner assert((PtrVal & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 && 803f7dba7b1738bd433a1dea0142e0844a106b782aDuncan Sands "Pointer is not sufficiently aligned"); 81e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner // Preserve all low bits, just update the pointer. 82e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner Value = PtrVal | (Value & ~PointerBitMask); 8334b763694e74ee16e68fd85488bfe0443c51170dChris Lattner } 843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 8534b763694e74ee16e68fd85488bfe0443c51170dChris Lattner void setInt(IntType Int) { 86b79a01111d1ed14ec92b969fb995906268733c12Dan Gohman intptr_t IntVal = Int; 87b79a01111d1ed14ec92b969fb995906268733c12Dan Gohman assert(IntVal < (1 << IntBits) && "Integer too large for field"); 88e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner 89e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner // Preserve all bits other than the ones we are updating. 90e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner Value &= ~ShiftedIntMask; // Remove integer field. 91e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner Value |= IntVal << IntShift; // Set new integer. 9234b763694e74ee16e68fd85488bfe0443c51170dChris Lattner } 933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9438297f5f760de604258aaa9000e5aadb43c78921Argyrios Kyrtzidis PointerTy const *getAddrOfPointer() const { 950db235a2b0ed6ae5c3c870012061906054b6dbc4Argyrios Kyrtzidis return const_cast<PointerIntPair *>(this)->getAddrOfPointer(); 960db235a2b0ed6ae5c3c870012061906054b6dbc4Argyrios Kyrtzidis } 970db235a2b0ed6ae5c3c870012061906054b6dbc4Argyrios Kyrtzidis 980db235a2b0ed6ae5c3c870012061906054b6dbc4Argyrios Kyrtzidis PointerTy *getAddrOfPointer() { 9938297f5f760de604258aaa9000e5aadb43c78921Argyrios Kyrtzidis assert(Value == reinterpret_cast<intptr_t>(getPointer()) && 10038297f5f760de604258aaa9000e5aadb43c78921Argyrios Kyrtzidis "Can only return the address if IntBits is cleared and " 10138297f5f760de604258aaa9000e5aadb43c78921Argyrios Kyrtzidis "PtrTraits doesn't change the pointer"); 1020db235a2b0ed6ae5c3c870012061906054b6dbc4Argyrios Kyrtzidis return reinterpret_cast<PointerTy *>(&Value); 10338297f5f760de604258aaa9000e5aadb43c78921Argyrios Kyrtzidis } 10438297f5f760de604258aaa9000e5aadb43c78921Argyrios Kyrtzidis 10534b763694e74ee16e68fd85488bfe0443c51170dChris Lattner void *getOpaqueValue() const { return reinterpret_cast<void*>(Value); } 10634b763694e74ee16e68fd85488bfe0443c51170dChris Lattner void setFromOpaqueValue(void *Val) { Value = reinterpret_cast<intptr_t>(Val);} 1073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1084d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner static PointerIntPair getFromOpaqueValue(void *V) { 1094d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner PointerIntPair P; P.setFromOpaqueValue(V); return P; 1104d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner } 1116ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose 1126ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose // Allow PointerIntPairs to be created from const void * if and only if the 1136ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose // pointer type could be created from a const void *. 1146ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose static PointerIntPair getFromOpaqueValue(const void *V) { 1156ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose (void)PtrTraits::getFromVoidPointer(V); 1166ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose return getFromOpaqueValue(const_cast<void *>(V)); 1176ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose } 1186ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose 119012618f0fc4df0664e6d7ad6b443173d89820213Chris Lattner bool operator==(const PointerIntPair &RHS) const {return Value == RHS.Value;} 120012618f0fc4df0664e6d7ad6b443173d89820213Chris Lattner bool operator!=(const PointerIntPair &RHS) const {return Value != RHS.Value;} 121012618f0fc4df0664e6d7ad6b443173d89820213Chris Lattner bool operator<(const PointerIntPair &RHS) const {return Value < RHS.Value;} 122012618f0fc4df0664e6d7ad6b443173d89820213Chris Lattner bool operator>(const PointerIntPair &RHS) const {return Value > RHS.Value;} 123012618f0fc4df0664e6d7ad6b443173d89820213Chris Lattner bool operator<=(const PointerIntPair &RHS) const {return Value <= RHS.Value;} 124012618f0fc4df0664e6d7ad6b443173d89820213Chris Lattner bool operator>=(const PointerIntPair &RHS) const {return Value >= RHS.Value;} 12534b763694e74ee16e68fd85488bfe0443c51170dChris Lattner}; 12634b763694e74ee16e68fd85488bfe0443c51170dChris Lattner 1274bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattnertemplate <typename T> struct isPodLike; 1284bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattnertemplate<typename PointerTy, unsigned IntBits, typename IntType> 1294bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattnerstruct isPodLike<PointerIntPair<PointerTy, IntBits, IntType> > { 1304bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattner static const bool value = true; 1314bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattner}; 1324bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattner 1339ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner// Provide specialization of DenseMapInfo for PointerIntPair. 1349ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattnertemplate<typename PointerTy, unsigned IntBits, typename IntType> 1359ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattnerstruct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType> > { 1369ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner typedef PointerIntPair<PointerTy, IntBits, IntType> Ty; 1379ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner static Ty getEmptyKey() { 1381144af3c9b4da48cd581156e05b24261c8de366aRichard Smith uintptr_t Val = static_cast<uintptr_t>(-1); 139f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable; 140f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner return Ty(reinterpret_cast<PointerTy>(Val), IntType((1 << IntBits)-1)); 1419ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner } 1429ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner static Ty getTombstoneKey() { 1431144af3c9b4da48cd581156e05b24261c8de366aRichard Smith uintptr_t Val = static_cast<uintptr_t>(-2); 144f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable; 145f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner return Ty(reinterpret_cast<PointerTy>(Val), IntType(0)); 1469ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner } 1479ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner static unsigned getHashValue(Ty V) { 1489ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue()); 1499ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner return unsigned(IV) ^ unsigned(IV >> 9); 1509ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner } 1519ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; } 1529ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner}; 1539ac30537aa3c201b6950bc708e02b1885c288c8dChris Lattner 1544d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner// Teach SmallPtrSet that PointerIntPair is "basically a pointer". 155c6a4b6b78b9262ad6a343a4edae88611ef970669Chris Lattnertemplate<typename PointerTy, unsigned IntBits, typename IntType, 156c6a4b6b78b9262ad6a343a4edae88611ef970669Chris Lattner typename PtrTraits> 157c6a4b6b78b9262ad6a343a4edae88611ef970669Chris Lattnerclass PointerLikeTypeTraits<PointerIntPair<PointerTy, IntBits, IntType, 158c6a4b6b78b9262ad6a343a4edae88611ef970669Chris Lattner PtrTraits> > { 1594d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattnerpublic: 1604d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner static inline void * 1614d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) { 1624d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner return P.getOpaqueValue(); 1634d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner } 1644d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner static inline PointerIntPair<PointerTy, IntBits, IntType> 1654d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner getFromVoidPointer(void *P) { 1664d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); 1674d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner } 1686ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose static inline PointerIntPair<PointerTy, IntBits, IntType> 1696ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose getFromVoidPointer(const void *P) { 1706ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); 1716ef4996b095ef6c0d902798d2455716a79bd0a3dJordan Rose } 172e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner enum { 1732fed70daaf6cf77ec62166041fef11ba7cf68173John McCall NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits 174e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattner }; 1754d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner}; 1764d4177b9b3ab634e852be1c0a7565a4ec1c7df93Chris Lattner 17734b763694e74ee16e68fd85488bfe0443c51170dChris Lattner} // end namespace llvm 17834b763694e74ee16e68fd85488bfe0443c51170dChris Lattner#endif 179