[ADT] Add an abstraction for embedding an integer within a pointer-like

type.

This makes it easy and safe to use a set of flags as one elmenet of
a tagged union with pointers. There is quite a bit of code that has
historically done this by casting arbitrary integers to "pointers" and
assuming that this was safe and reliable. It is neither, and has started
to rear its head by triggering safety asserts in various abstractions
like PointerLikeTypeTraits when the integers chosen are invariably poor
choices for *some* platform and *some* situation. Not to mention the
(hopefully unlikely) prospect of one of these integers actually getting
allocated!

With this, it will be straightforward to build type safe abstractions
like this without being error prone. The abstraction itself is also
remarkably simple thanks to the implicit conversion.

This use case and pattern was also independently created by the folks
working on Swift, and they're going to incrementally add any missing
functionality they find.

Differential Revision: http://reviews.llvm.org/D15844

llvm-svn: 257284

3 files changed, 150 insertions, 0 deletions

diff --git a/llvm/include/llvm/ADT/PointerEmbeddedInt.h b/llvm/include/llvm/ADT/PointerEmbeddedInt.h
new file mode 100644
index 00000000000..9386c42350b
--- /dev/null
+++ b/llvm/include/llvm/ADT/PointerEmbeddedInt.h
@@ -0,0 +1,103 @@
+//===- llvm/ADT/PointerEmbeddedInt.h ----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_POINTEREMBEDDEDINT_H
+#define LLVM_ADT_POINTEREMBEDDEDINT_H
+
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/Support/PointerLikeTypeTraits.h"
+#include <climits>
+
+namespace llvm {
+
+/// Utility to embed an integer into a pointer-like type. This is specifically
+/// intended to allow embedding integers where fewer bits are required than
+/// exist in a pointer, and the integer can participate in abstractions along
+/// side other pointer-like types. For example it can be placed into a \c
+/// PointerSumType or \c PointerUnion.
+///
+/// Note that much like pointers, an integer value of zero has special utility
+/// due to boolean conversions. For example, a non-null value can be tested for
+/// in the above abstractions without testing the particular active member.
+/// Also, the default constructed value zero initializes the integer.
+template <typename IntT, int Bits = sizeof(IntT) * CHAR_BIT>
+class PointerEmbeddedInt {
+  uintptr_t Value;
+
+  static_assert(Bits < sizeof(Value) * CHAR_BIT,
+                "Cannot embed more bits than we have in a pointer!");
+
+  enum : uintptr_t {
+    // We shift as many zeros into the value as we can while preserving the
+    // number of bits desired for the integer.
+    Shift = sizeof(Value) * CHAR_BIT - Bits,
+
+    // We also want to be able to mask out the preserved bits for asserts.
+    Mask = static_cast<uintptr_t>(-1) << Bits
+  };
+
+  friend class PointerLikeTypeTraits<PointerEmbeddedInt>;
+
+  explicit PointerEmbeddedInt(uintptr_t Value) : Value(Value) {}
+
+public:
+  PointerEmbeddedInt() : Value(0) {}
+
+  PointerEmbeddedInt(IntT I) : Value(static_cast<uintptr_t>(I) << Shift) {
+    assert((I & Mask) == 0 && "Integer has bits outside those preserved!");
+  }
+
+  PointerEmbeddedInt &operator=(IntT I) {
+    assert((I & Mask) == 0 && "Integer has bits outside those preserved!");
+    Value = static_cast<uintptr_t>(I) << Shift;
+  }
+
+  // Note that this imilict conversion additionally allows all of the basic
+  // comparison operators to work transparently, etc.
+  operator IntT() const { return static_cast<IntT>(Value >> Shift); }
+};
+
+// Provide pointer like traits to support use with pointer unions and sum
+// types.
+template <typename IntT, int Bits>
+class PointerLikeTypeTraits<PointerEmbeddedInt<IntT, Bits>> {
+  typedef PointerEmbeddedInt<IntT, Bits> T;
+
+public:
+  static inline void *getAsVoidPointer(const T &P) {
+    return reinterpret_cast<void *>(P.Value);
+  }
+  static inline T getFromVoidPointer(void *P) {
+    return T(reinterpret_cast<uintptr_t>(P));
+  }
+  static inline T getFromVoidPointer(const void *P) {
+    return T(reinterpret_cast<uintptr_t>(P));
+  }
+
+  enum { NumLowBitsAvailable = T::Shift };
+};
+
+// Teach DenseMap how to use PointerEmbeddedInt objects as keys if the Int type
+// itself can be a key.
+template <typename IntT, int Bits>
+struct DenseMapInfo<PointerEmbeddedInt<IntT, Bits>> {
+  typedef PointerEmbeddedInt<IntT, Bits> T;
+
+  typedef DenseMapInfo<IntT> IntInfo;
+
+  static inline T getEmptyKey() { return IntInfo::getEmptyKey(); }
+  static inline T getTombstoneKey() { return IntInfo::getTombstoneKey(); }
+  static unsigned getHashValue(const T &Arg) {
+    return IntInfo::getHashValue(Arg);
+  }
+  static bool isEqual(const T &LHS, const T &RHS) { return LHS == RHS; }
+};
+}
+
+#endif
diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt
index 5eb477aceac..bce1bf93a33 100644
--- a/llvm/unittests/ADT/CMakeLists.txt
+++ b/llvm/unittests/ADT/CMakeLists.txt
@@ -25,6 +25,7 @@ set(ADTSources
   MapVectorTest.cpp
   OptionalTest.cpp
   PackedVectorTest.cpp
+  PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp
   PointerSumTypeTest.cpp
   PointerUnionTest.cpp
diff --git a/llvm/unittests/ADT/PointerEmbeddedIntTest.cpp b/llvm/unittests/ADT/PointerEmbeddedIntTest.cpp
new file mode 100644
index 00000000000..b10365a2f61
--- /dev/null
+++ b/llvm/unittests/ADT/PointerEmbeddedIntTest.cpp
@@ -0,0 +1,46 @@
+//===- llvm/unittest/ADT/PointerEmbeddedIntTest.cpp -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/PointerEmbeddedInt.h"
+using namespace llvm;
+
+namespace {
+
+TEST(PointerEmbeddedIntTest, Basic) {
+  PointerEmbeddedInt<int, CHAR_BIT> I = 42, J = 43;
+
+  EXPECT_EQ(42, I);
+  EXPECT_EQ(43, I + 1);
+  EXPECT_EQ(sizeof(uintptr_t) * CHAR_BIT - CHAR_BIT,
+            PointerLikeTypeTraits<decltype(I)>::NumLowBitsAvailable);
+
+  EXPECT_FALSE(I == J);
+  EXPECT_TRUE(I != J);
+  EXPECT_TRUE(I < J);
+  EXPECT_FALSE(I > J);
+  EXPECT_TRUE(I <= J);
+  EXPECT_FALSE(I >= J);
+
+  EXPECT_FALSE(I == 43);
+  EXPECT_TRUE(I != 43);
+  EXPECT_TRUE(I < 43);
+  EXPECT_FALSE(I > 43);
+  EXPECT_TRUE(I <= 43);
+  EXPECT_FALSE(I >= 43);
+
+  EXPECT_FALSE(42 == J);
+  EXPECT_TRUE(42 != J);
+  EXPECT_TRUE(42 < J);
+  EXPECT_FALSE(42 > J);
+  EXPECT_TRUE(42 <= J);
+  EXPECT_FALSE(42 >= J);
+}
+
+} // end anonymous namespace