From ca4af1ae34078c2b4b734e44a7d6bb6add27efed Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 10 Jan 2016 09:40:13 +0000 Subject: [PATCH] [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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@257284 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/PointerEmbeddedInt.h | 103 +++++++++++++++++++++++ unittests/ADT/CMakeLists.txt | 1 + unittests/ADT/PointerEmbeddedIntTest.cpp | 46 ++++++++++ 3 files changed, 150 insertions(+) create mode 100644 include/llvm/ADT/PointerEmbeddedInt.h create mode 100644 unittests/ADT/PointerEmbeddedIntTest.cpp diff --git a/include/llvm/ADT/PointerEmbeddedInt.h b/include/llvm/ADT/PointerEmbeddedInt.h new file mode 100644 index 00000000000..9386c42350b --- /dev/null +++ b/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 + +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 +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(-1) << Bits + }; + + friend class PointerLikeTypeTraits; + + explicit PointerEmbeddedInt(uintptr_t Value) : Value(Value) {} + +public: + PointerEmbeddedInt() : Value(0) {} + + PointerEmbeddedInt(IntT I) : Value(static_cast(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(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(Value >> Shift); } +}; + +// Provide pointer like traits to support use with pointer unions and sum +// types. +template +class PointerLikeTypeTraits> { + typedef PointerEmbeddedInt T; + +public: + static inline void *getAsVoidPointer(const T &P) { + return reinterpret_cast(P.Value); + } + static inline T getFromVoidPointer(void *P) { + return T(reinterpret_cast(P)); + } + static inline T getFromVoidPointer(const void *P) { + return T(reinterpret_cast(P)); + } + + enum { NumLowBitsAvailable = T::Shift }; +}; + +// Teach DenseMap how to use PointerEmbeddedInt objects as keys if the Int type +// itself can be a key. +template +struct DenseMapInfo> { + typedef PointerEmbeddedInt T; + + typedef DenseMapInfo 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/unittests/ADT/CMakeLists.txt b/unittests/ADT/CMakeLists.txt index 5eb477aceac..bce1bf93a33 100644 --- a/unittests/ADT/CMakeLists.txt +++ b/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/unittests/ADT/PointerEmbeddedIntTest.cpp b/unittests/ADT/PointerEmbeddedIntTest.cpp new file mode 100644 index 00000000000..b10365a2f61 --- /dev/null +++ b/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 I = 42, J = 43; + + EXPECT_EQ(42, I); + EXPECT_EQ(43, I + 1); + EXPECT_EQ(sizeof(uintptr_t) * CHAR_BIT - CHAR_BIT, + PointerLikeTypeTraits::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 -- 2.34.1