Home | History | Annotate | Line # | Download | only in ADT 
      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   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.
    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
    120