include/llvm/ADT/PointerEmbeddedInt.h

   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
  20 namespace 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.
  32 template <typename IntT, int Bits = sizeof(IntT) * CHAR_BIT>
  33 class 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
  58 public:
  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.
  81 template <typename IntT, int Bits>
  82 struct 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   enum { 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.
 102 template <typename IntT, int Bits>
 103 struct 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