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

[chandlerc]

Summary

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.

[chandlerc]

You can see an example usage in http://reviews.llvm.org/D15845

[jordan_rose]

Ha, I wrote the same thing, but it's only used for Swift-Clang's "API notes" feature that hasn't been upstreamed, so it's still sitting in our repository. I called it Fixnum. Sorry about that.

Differences:

• when stored outside a PointerIntPair, it uses the smallest storage possible
• safe upcasting is implicitly allowed
• assignment/construction between bit widths is permitted but checked
• I hadn't written special DenseMapInfo (because we never used it in a DenseMap)

I'm fine switching ours over to yours, or you taking ours as is. I really thought we had tests for it too but I can't find them.

[chandlerc]

In D15844#322318, @jordan_rose wrote:

Ha, I wrote the same thing, but it's only used for Swift-Clang's "API notes" feature that hasn't been upstreamed, so it's still sitting in our repository. I called it Fixnum. Sorry about that.

No problem, seems like this is going in the right direction anyways. =]

Differences:

• when stored outside a PointerIntPair, it uses the smallest storage possible
• safe upcasting is implicitly allowed
• assignment/construction between bit widths is permitted but checked
• I hadn't written special DenseMapInfo (because we never used it in a DenseMap)

I'm fine switching ours over to yours, or you taking ours as is. I really thought we had tests for it too but I can't find them.

Well, the approach I've taken (storing it as a pointer, and quickly converting it an integer type for any/all operations) is at least from the code size much simpler, so I have a bias towards that.

Let's start with the patch as I have it since it at least works for some use cases and is really boring and simple. It also has basic tests that can be extended incrementally.

So far at least, I have found it really effective to rely on the single implicit conversion to a particular integer type, and then allow promotion and normal arithmetic to take place. This seemed to work well. The typical result I expect is that the ADT type only really exists inside of a sum type or pointer union. All the other places, you just get the integer.

However, I've not used it super widely, so if you try to use this in Swift you may uncover reasons why we need to add some (or all) of the facilities from your version. If/when you do, you can post the patches to merge functionality into this (along with tests that show what usage pattern needs it) until it is sufficient for the use cases you have in Swift.

I'm going to land this as is since you seem fine with it, but just follow up with any issues you run into when it shows up on the swift side of things. Thanks!

-Chandler

llvm/trunk/include/llvm/ADT/PointerEmbeddedInt.h

+//===- 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

llvm/trunk/unittests/ADT/CMakeLists.txt

set(ADTSources
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
   IntrusiveRefCntPtrTest.cpp
   MakeUniqueTest.cpp
   MapVectorTest.cpp
   OptionalTest.cpp
   PackedVectorTest.cpp
+  PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp
   PointerSumTypeTest.cpp
   PointerUnionTest.cpp
   PostOrderIteratorTest.cpp
   RangeAdapterTest.cpp
   SCCIteratorTest.cpp
   SmallPtrSetTest.cpp
   SmallStringTest.cpp

llvm/trunk/unittests/ADT/PointerEmbeddedIntTest.cpp

+//===- 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