1111519Sdavidxu//===- llvm/ADT/PointerEmbeddedInt.h ----------------------------*- C++ -*-===// 2111519Sdavidxu// 3111519Sdavidxu// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4111519Sdavidxu// See https://llvm.org/LICENSE.txt for license information. 5111519Sdavidxu// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6111519Sdavidxu// 7111519Sdavidxu//===----------------------------------------------------------------------===// 8111519Sdavidxu 9111519Sdavidxu#ifndef LLVM_ADT_POINTEREMBEDDEDINT_H 10111519Sdavidxu#define LLVM_ADT_POINTEREMBEDDEDINT_H 11111519Sdavidxu 12111519Sdavidxu#include "llvm/ADT/DenseMapInfo.h" 13111519Sdavidxu#include "llvm/Support/MathExtras.h" 14111519Sdavidxu#include "llvm/Support/PointerLikeTypeTraits.h" 15111519Sdavidxu#include <cassert> 16111519Sdavidxu#include <climits> 17111519Sdavidxu#include <cstdint> 18111519Sdavidxu#include <type_traits> 19111519Sdavidxu 20111519Sdavidxunamespace llvm { 21111519Sdavidxu 22111519Sdavidxu/// Utility to embed an integer into a pointer-like type. This is specifically 23111519Sdavidxu/// intended to allow embedding integers where fewer bits are required than 24111519Sdavidxu/// exist in a pointer, and the integer can participate in abstractions along 25111519Sdavidxu/// side other pointer-like types. For example it can be placed into a \c 26111519Sdavidxu/// PointerSumType or \c PointerUnion. 27111519Sdavidxu/// 28111519Sdavidxu/// Note that much like pointers, an integer value of zero has special utility 29111519Sdavidxu/// due to boolean conversions. For example, a non-null value can be tested for 30111519Sdavidxu/// in the above abstractions without testing the particular active member. 31111519Sdavidxu/// Also, the default constructed value zero initializes the integer. 32111519Sdavidxutemplate <typename IntT, int Bits = sizeof(IntT) * CHAR_BIT> 33111519Sdavidxuclass PointerEmbeddedInt { 34111519Sdavidxu uintptr_t Value = 0; 35111519Sdavidxu 36111519Sdavidxu // Note: This '<' is correct; using '<=' would result in some shifts 37111519Sdavidxu // overflowing their storage types. 38111519Sdavidxu static_assert(Bits < sizeof(uintptr_t) * CHAR_BIT, 39111519Sdavidxu "Cannot embed more bits than we have in a pointer!"); 40111519Sdavidxu 41111519Sdavidxu enum : uintptr_t { 42111519Sdavidxu // We shift as many zeros into the value as we can while preserving the 43111519Sdavidxu // number of bits desired for the integer. 44111519Sdavidxu Shift = sizeof(uintptr_t) * CHAR_BIT - Bits, 45111519Sdavidxu 46111519Sdavidxu // We also want to be able to mask out the preserved bits for asserts. 47111519Sdavidxu Mask = static_cast<uintptr_t>(-1) << Bits 48111519Sdavidxu }; 49111519Sdavidxu 50111519Sdavidxu struct RawValueTag { 51111519Sdavidxu explicit RawValueTag() = default; 52111519Sdavidxu }; 53111519Sdavidxu 54111519Sdavidxu friend struct PointerLikeTypeTraits<PointerEmbeddedInt>; 55111519Sdavidxu 56111519Sdavidxu explicit PointerEmbeddedInt(uintptr_t Value, RawValueTag) : Value(Value) {} 57111519Sdavidxu 58111519Sdavidxupublic: 59111519Sdavidxu PointerEmbeddedInt() = default; 60111519Sdavidxu 61111519Sdavidxu PointerEmbeddedInt(IntT I) { *this = I; } 62111519Sdavidxu 63111519Sdavidxu PointerEmbeddedInt &operator=(IntT I) { 64111519Sdavidxu assert((std::is_signed<IntT>::value ? isInt<Bits>(I) : isUInt<Bits>(I)) && 65111519Sdavidxu "Integer has bits outside those preserved!"); 66111519Sdavidxu Value = static_cast<uintptr_t>(I) << Shift; 67111519Sdavidxu return *this; 68111519Sdavidxu } 69111519Sdavidxu 70111519Sdavidxu // Note that this implicit conversion additionally allows all of the basic 71111519Sdavidxu // comparison operators to work transparently, etc. 72111519Sdavidxu operator IntT() const { 73111519Sdavidxu if (std::is_signed<IntT>::value) 74111519Sdavidxu return static_cast<IntT>(static_cast<intptr_t>(Value) >> Shift); 75111519Sdavidxu return static_cast<IntT>(Value >> Shift); 76111519Sdavidxu } 77111519Sdavidxu}; 78111519Sdavidxu 79111519Sdavidxu// Provide pointer like traits to support use with pointer unions and sum 80111519Sdavidxu// types. 81111519Sdavidxutemplate <typename IntT, int Bits> 82111519Sdavidxustruct PointerLikeTypeTraits<PointerEmbeddedInt<IntT, Bits>> { 83111519Sdavidxu using T = PointerEmbeddedInt<IntT, Bits>; 84111519Sdavidxu 85111519Sdavidxu static inline void *getAsVoidPointer(const T &P) { 86111519Sdavidxu return reinterpret_cast<void *>(P.Value); 87111519Sdavidxu } 88111519Sdavidxu 89111519Sdavidxu static inline T getFromVoidPointer(void *P) { 90111519Sdavidxu return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag()); 91111519Sdavidxu } 92111519Sdavidxu 93111519Sdavidxu static inline T getFromVoidPointer(const void *P) { 94111519Sdavidxu return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag()); 95111519Sdavidxu } 96111519Sdavidxu 97111519Sdavidxu enum { NumLowBitsAvailable = T::Shift }; 98111519Sdavidxu}; 99111519Sdavidxu 100111519Sdavidxu// Teach DenseMap how to use PointerEmbeddedInt objects as keys if the Int type 101111519Sdavidxu// itself can be a key. 102111519Sdavidxutemplate <typename IntT, int Bits> 103111519Sdavidxustruct DenseMapInfo<PointerEmbeddedInt<IntT, Bits>> { 104111519Sdavidxu using T = PointerEmbeddedInt<IntT, Bits>; 105111519Sdavidxu using IntInfo = DenseMapInfo<IntT>; 106111519Sdavidxu 107111519Sdavidxu static inline T getEmptyKey() { return IntInfo::getEmptyKey(); } 108111519Sdavidxu static inline T getTombstoneKey() { return IntInfo::getTombstoneKey(); } 109111519Sdavidxu 110111519Sdavidxu static unsigned getHashValue(const T &Arg) { 111111519Sdavidxu return IntInfo::getHashValue(Arg); 112111519Sdavidxu } 113111519Sdavidxu 114111519Sdavidxu static bool isEqual(const T &LHS, const T &RHS) { return LHS == RHS; } 115111519Sdavidxu}; 116111519Sdavidxu 117111519Sdavidxu} // end namespace llvm 118111519Sdavidxu 119111519Sdavidxu#endif // LLVM_ADT_POINTEREMBEDDEDINT_H 120111519Sdavidxu