1//===- llvm/ADT/PointerEmbeddedInt.h ----------------------------*- 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#ifndef LLVM_ADT_POINTEREMBEDDEDINT_H
10#define LLVM_ADT_POINTEREMBEDDEDINT_H
11
12#include "llvm/ADT/DenseMapInfo.h"
13#include "llvm/Support/MathExtras.h"
14#include "llvm/Support/PointerLikeTypeTraits.h"
15#include <cassert>
16#include <climits>
17#include <cstdint>
18#include <type_traits>
19
20namespace llvm {
21
22/// Utility to embed an integer into a pointer-like type. This is specifically
23/// intended to allow embedding integers where fewer bits are required than
24/// exist in a pointer, and the integer can participate in abstractions along
25/// side other pointer-like types. For example it can be placed into a \c
26/// PointerSumType or \c PointerUnion.
27///
28/// Note that much like pointers, an integer value of zero has special utility
29/// due to boolean conversions. For example, a non-null value can be tested for
30/// in the above abstractions without testing the particular active member.
31/// Also, the default constructed value zero initializes the integer.
32template <typename IntT, int Bits = sizeof(IntT) * CHAR_BIT>
33class PointerEmbeddedInt {
34 uintptr_t Value = 0;
35
36 // Note: This '<' is correct; using '<=' would result in some shifts
37 // overflowing their storage types.
38 static_assert(Bits < sizeof(uintptr_t) * CHAR_BIT,
39 "Cannot embed more bits than we have in a pointer!");
40
41 enum : uintptr_t {
42 // We shift as many zeros into the value as we can while preserving the
43 // number of bits desired for the integer.
44 Shift = sizeof(uintptr_t) * CHAR_BIT - Bits,
45
46 // We also want to be able to mask out the preserved bits for asserts.
47 Mask = static_cast<uintptr_t>(-1) << Bits
48 };
49
50 struct RawValueTag {
51 explicit RawValueTag() = default;
52 };
53
54 friend struct PointerLikeTypeTraits<PointerEmbeddedInt>;
55
56 explicit PointerEmbeddedInt(uintptr_t Value, RawValueTag) : Value(Value) {}
57
58public:
59 PointerEmbeddedInt() = default;
60
61 PointerEmbeddedInt(IntT I) { *this = I; }
62
63 PointerEmbeddedInt &operator=(IntT I) {
64 assert((std::is_signed<IntT>::value ? isInt<Bits>(I) : isUInt<Bits>(I)) &&
65 "Integer has bits outside those preserved!");
66 Value = static_cast<uintptr_t>(I) << Shift;
67 return *this;
68 }
69
70 // Note that this implicit conversion additionally allows all of the basic
71 // comparison operators to work transparently, etc.
72 operator IntT() const {
73 if (std::is_signed<IntT>::value)
74 return static_cast<IntT>(static_cast<intptr_t>(Value) >> Shift);
75 return static_cast<IntT>(Value >> Shift);
76 }
77};
78
79// Provide pointer like traits to support use with pointer unions and sum
80// types.
81template <typename IntT, int Bits>
82struct PointerLikeTypeTraits<PointerEmbeddedInt<IntT, Bits>> {
83 using T = PointerEmbeddedInt<IntT, Bits>;
84
85 static inline void *getAsVoidPointer(const T &P) {
86 return reinterpret_cast<void *>(P.Value);
87 }
88
89 static inline T getFromVoidPointer(void *P) {
90 return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag());
91 }
92
93 static inline T getFromVoidPointer(const void *P) {
94 return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag());
95 }
96
97 static constexpr int NumLowBitsAvailable = T::Shift;
98};
99
100// Teach DenseMap how to use PointerEmbeddedInt objects as keys if the Int type
101// itself can be a key.
102template <typename IntT, int Bits>
103struct DenseMapInfo<PointerEmbeddedInt<IntT, Bits>> {
104 using T = PointerEmbeddedInt<IntT, Bits>;
105 using IntInfo = DenseMapInfo<IntT>;
106
107 static inline T getEmptyKey() { return IntInfo::getEmptyKey(); }
108 static inline T getTombstoneKey() { return IntInfo::getTombstoneKey(); }
109
110 static unsigned getHashValue(const T &Arg) {
111 return IntInfo::getHashValue(Arg);
112 }
113
114 static bool isEqual(const T &LHS, const T &RHS) { return LHS == RHS; }
115};
116
117} // end namespace llvm
118
119#endif // LLVM_ADT_POINTEREMBEDDEDINT_H
120