From aa365b2fcd975064234b0859d0881702789b6c40 Mon Sep 17 00:00:00 2001 From: James Y Knight Date: Wed, 5 Aug 2015 22:57:34 +0000 Subject: [PATCH] Add a TrailingObjects template class. This is intended to help support the idiom of a class that has some other objects (or multiple arrays of different types of objects) appended on the end, which is used quite heavily in clang. Differential Revision: http://reviews.llvm.org/D11272 llvm-svn: 244164 --- llvm/include/llvm/Support/TrailingObjects.h | 231 +++++++++++++++++++++++++ llvm/include/llvm/Support/type_traits.h | 9 + llvm/lib/IR/AttributeImpl.h | 37 ++-- llvm/lib/IR/Attributes.cpp | 13 +- llvm/unittests/Support/CMakeLists.txt | 1 + llvm/unittests/Support/TrailingObjectsTest.cpp | 147 ++++++++++++++++ 6 files changed, 412 insertions(+), 26 deletions(-) create mode 100644 llvm/include/llvm/Support/TrailingObjects.h create mode 100644 llvm/unittests/Support/TrailingObjectsTest.cpp diff --git a/llvm/include/llvm/Support/TrailingObjects.h b/llvm/include/llvm/Support/TrailingObjects.h new file mode 100644 index 0000000..a8a9bb2 --- /dev/null +++ b/llvm/include/llvm/Support/TrailingObjects.h @@ -0,0 +1,231 @@ +//===--- TrailingObjects.h - Variable-length classes ------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This header defines support for implementing classes that have +/// some trailing object (or arrays of objects) appended to them. The +/// main purpose is to make it obvious where this idiom is being used, +/// and to make the usage more idiomatic and more difficult to get +/// wrong. +/// +/// The TrailingObject template abstracts away the reinterpret_cast, +/// pointer arithmetic, and size calculations used for the allocation +/// and access of appended arrays of objects, as well as asserts that +/// the alignment of the classes involved are appropriate for the +/// usage. Additionally, it ensures that the base type is final -- +/// deriving from a class that expects data appended immediately after +/// it is typically not safe. +/// +/// Users are expected to derive from this template, and provide +/// numTrailingObjects implementations for each trailing type, +/// e.g. like this sample: +/// +/// \code +/// class VarLengthObj : private TrailingObjects { +/// friend TrailingObjects; +/// +/// unsigned NumInts, NumDoubles; +/// size_t numTrailingObjects(OverloadToken) const { return NumInts; } +/// size_t numTrailingObjects(OverloadToken) const { +/// return NumDoubles; +/// } +/// }; +/// \endcode +/// +/// You can access the appended arrays via 'getTrailingObjects', and +/// determine the size needed for allocation via +/// 'additionalSizeToAlloc' and 'totalSizeToAlloc'. +/// +/// All the methods implemented by this class are are intended for use +/// by the implementation of the class, not as part of its interface +/// (thus, private inheritance is suggested). +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_TRAILINGOBJECTS_H +#define LLVM_SUPPORT_TRAILINGOBJECTS_H + +#include +#include +#include "llvm/Support/AlignOf.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/type_traits.h" + +namespace llvm { + +/// The base class for TrailingObjects* classes. +class TrailingObjectsBase { +protected: + /// OverloadToken's purpose is to allow specifying function overloads + /// for different types, without actually taking the types as + /// parameters. (Necessary because member function templates cannot + /// be specialized, so overloads must be used instead of + /// specialization.) + template struct OverloadToken {}; +}; + +// Internally used to indicate that the user didn't supply this value, +// so the explicit-specialization for fewer args will be used. +class NoTrailingTypeArg {}; + +// TODO: Consider using a single variadic implementation instead of +// multiple copies of the TrailingObjects template? [but, variadic +// template recursive implementations are annoying...] + +/// This is the two-type version of the TrailingObjects template; see +/// file docstring for details. +template +class TrailingObjects : public TrailingObjectsBase { +private: + // Contains static_assert statements for the alignment of the + // types. Must not be at class-level, because BaseTy isn't complete + // at class instantiation time, but will be by the time this + // function is instantiated. + static void verifyTrailingObjectsAssertions() { + static_assert(llvm::AlignOf::Alignment >= + llvm::AlignOf::Alignment, + "TrailingTy1 requires more alignment than BaseTy provides"); + static_assert( + llvm::AlignOf::Alignment >= + llvm::AlignOf::Alignment, + "TrailingTy2 requires more alignment than TrailingTy1 provides"); + +#ifdef LLVM_IS_FINAL + static_assert(LLVM_IS_FINAL(BaseTy), "BaseTy must be final."); +#endif + } + + // The next four functions are internal helpers for getTrailingObjects. + static const TrailingTy1 *getTrailingObjectsImpl(const BaseTy *Obj, + OverloadToken) { + return reinterpret_cast(Obj + 1); + } + + static TrailingTy1 *getTrailingObjectsImpl(BaseTy *Obj, + OverloadToken) { + return reinterpret_cast(Obj + 1); + } + + static const TrailingTy2 *getTrailingObjectsImpl(const BaseTy *Obj, + OverloadToken) { + return reinterpret_cast( + getTrailingObjectsImpl(Obj, OverloadToken()) + + Obj->numTrailingObjects(OverloadToken())); + } + + static TrailingTy2 *getTrailingObjectsImpl(BaseTy *Obj, + OverloadToken) { + return reinterpret_cast( + getTrailingObjectsImpl(Obj, OverloadToken()) + + Obj->numTrailingObjects(OverloadToken())); + } + +protected: + /// Returns a pointer to the trailing object array of the given type + /// (which must be one of those specified in the class template). The + /// array may have zero or more elements in it. + template const T *getTrailingObjects() const { + verifyTrailingObjectsAssertions(); + // Forwards to an impl function with overloads, since member + // function templates can't be specialized. + return getTrailingObjectsImpl(static_cast(this), + OverloadToken()); + } + + /// Returns a pointer to the trailing object array of the given type + /// (which must be one of those specified in the class template). The + /// array may have zero or more elements in it. + template T *getTrailingObjects() { + verifyTrailingObjectsAssertions(); + // Forwards to an impl function with overloads, since member + // function templates can't be specialized. + return getTrailingObjectsImpl(static_cast(this), + OverloadToken()); + } + + /// Returns the size of the trailing data, if an object were + /// allocated with the given counts (The counts are in the same order + /// as the template arguments). This does not include the size of the + /// base object. The template arguments must be the same as those + /// used in the class; they are supplied here redundantly only so + /// that it's clear what the counts are counting in callers. + template ::value && + std::is_same::value, + int>::type = 0> + static LLVM_CONSTEXPR size_t additionalSizeToAlloc(size_t Count1, size_t Count2) { + return sizeof(TrailingTy1) * Count1 + sizeof(TrailingTy2) * Count2; + } + + /// Returns the total size of an object if it were allocated with the + /// given trailing object counts. This is the same as + /// additionalSizeToAlloc, except it *does* include the size of the base + /// object. + template + static LLVM_CONSTEXPR size_t totalSizeToAlloc(size_t Count1, size_t Count2) { + return sizeof(BaseTy) + additionalSizeToAlloc(Count1, Count2); + } +}; + +/// This is the one-type version of the TrailingObjects template. See +/// the two-type version for more documentation. +template +class TrailingObjects + : public TrailingObjectsBase { +private: + static void verifyTrailingObjectsAssertions() { + static_assert(llvm::AlignOf::Alignment >= + llvm::AlignOf::Alignment, + "TrailingTy1 requires more alignment than BaseTy provides"); + +#ifdef LLVM_IS_FINAL + static_assert(LLVM_IS_FINAL(BaseTy), "BaseTy must be final."); +#endif + } + + static const TrailingTy1 *getTrailingObjectsImpl(const BaseTy *Obj, + OverloadToken) { + return reinterpret_cast(Obj + 1); + } + + static TrailingTy1 *getTrailingObjectsImpl(BaseTy *Obj, + OverloadToken) { + return reinterpret_cast(Obj + 1); + } + +protected: + template const T *getTrailingObjects() const { + verifyTrailingObjectsAssertions(); + return getTrailingObjectsImpl(static_cast(this), + OverloadToken()); + } + + template T *getTrailingObjects() { + verifyTrailingObjectsAssertions(); + return getTrailingObjectsImpl(static_cast(this), + OverloadToken()); + } + + template ::value, + int>::type = 0> + static LLVM_CONSTEXPR size_t additionalSizeToAlloc(size_t Count1) { + return sizeof(TrailingTy1) * Count1; + } + + template + static LLVM_CONSTEXPR size_t totalSizeToAlloc(size_t Count1) { + return sizeof(BaseTy) + additionalSizeToAlloc(Count1); + } +}; + +} // end namespace llvm + +#endif diff --git a/llvm/include/llvm/Support/type_traits.h b/llvm/include/llvm/Support/type_traits.h index 45465ae..88385c3 100644 --- a/llvm/include/llvm/Support/type_traits.h +++ b/llvm/include/llvm/Support/type_traits.h @@ -93,6 +93,15 @@ struct add_const_past_pointer< } +// If the compiler supports detecting whether a class is final, define +// an LLVM_IS_FINAL macro. If it cannot be defined properly, this +// macro will be left undefined. +#if __cplusplus >= 201402L +#define LLVM_IS_FINAL(Ty) std::is_final() +#elif __has_feature(is_final) || LLVM_GNUC_PREREQ(4, 7, 0) +#define LLVM_IS_FINAL(Ty) __is_final(Ty) +#endif + #ifdef LLVM_DEFINED_HAS_FEATURE #undef __has_feature #endif diff --git a/llvm/lib/IR/AttributeImpl.h b/llvm/lib/IR/AttributeImpl.h index 6f338ae..d545658 100644 --- a/llvm/lib/IR/AttributeImpl.h +++ b/llvm/lib/IR/AttributeImpl.h @@ -18,6 +18,7 @@ #include "llvm/ADT/FoldingSet.h" #include "llvm/IR/Attributes.h" +#include "llvm/Support/TrailingObjects.h" #include namespace llvm { @@ -141,13 +142,16 @@ public: /// \class /// \brief This class represents a group of attributes that apply to one /// element: function, return type, or parameter. -class AttributeSetNode : public FoldingSetNode { +class AttributeSetNode final + : public FoldingSetNode, + private TrailingObjects { + friend TrailingObjects; + unsigned NumAttrs; ///< Number of attributes in this node. AttributeSetNode(ArrayRef Attrs) : NumAttrs(Attrs.size()) { // There's memory after the node where we can store the entries in. - std::copy(Attrs.begin(), Attrs.end(), - reinterpret_cast(this + 1)); + std::copy(Attrs.begin(), Attrs.end(), getTrailingObjects()); } // AttributesSetNode is uniqued, these should not be publicly available. @@ -170,7 +174,7 @@ public: std::string getAsString(bool InAttrGrp) const; typedef const Attribute *iterator; - iterator begin() const { return reinterpret_cast(this + 1); } + iterator begin() const { return getTrailingObjects(); } iterator end() const { return begin() + NumAttrs; } void Profile(FoldingSetNodeID &ID) const { @@ -181,27 +185,29 @@ public: AttrList[I].Profile(ID); } }; -static_assert( - AlignOf::Alignment >= AlignOf::Alignment, - "Alignment is insufficient for objects appended to AttributeSetNode"); //===----------------------------------------------------------------------===// /// \class /// \brief This class represents a set of attributes that apply to the function, /// return type, and parameters. -class AttributeSetImpl : public FoldingSetNode { - friend class AttributeSet; +typedef std::pair IndexAttrPair; -public: - typedef std::pair IndexAttrPair; +class AttributeSetImpl final + : public FoldingSetNode, + private TrailingObjects { + friend class AttributeSet; + friend TrailingObjects; private: LLVMContext &Context; unsigned NumAttrs; ///< Number of entries in this set. + // Helper fn for TrailingObjects class. + size_t numTrailingObjects(OverloadToken) { return NumAttrs; } + /// \brief Return a pointer to the IndexAttrPair for the specified slot. const IndexAttrPair *getNode(unsigned Slot) const { - return reinterpret_cast(this + 1) + Slot; + return getTrailingObjects() + Slot; } // AttributesSet is uniqued, these should not be publicly available. @@ -222,8 +228,7 @@ public: } #endif // There's memory after the node where we can store the entries in. - std::copy(Attrs.begin(), Attrs.end(), - reinterpret_cast(this + 1)); + std::copy(Attrs.begin(), Attrs.end(), getTrailingObjects()); } /// \brief Get the context that created this AttributeSetImpl. @@ -273,10 +278,6 @@ public: void dump() const; }; -static_assert( - AlignOf::Alignment >= - AlignOf::Alignment, - "Alignment is insufficient for objects appended to AttributeSetImpl"); } // end llvm namespace diff --git a/llvm/lib/IR/Attributes.cpp b/llvm/lib/IR/Attributes.cpp index 0d89d12..d909f7b8 100644 --- a/llvm/lib/IR/Attributes.cpp +++ b/llvm/lib/IR/Attributes.cpp @@ -484,8 +484,7 @@ AttributeSetNode *AttributeSetNode::get(LLVMContext &C, // new one and insert it. if (!PA) { // Coallocate entries after the AttributeSetNode itself. - void *Mem = ::operator new(sizeof(AttributeSetNode) + - sizeof(Attribute) * SortedAttrs.size()); + void *Mem = ::operator new(totalSizeToAlloc(SortedAttrs.size())); PA = new (Mem) AttributeSetNode(SortedAttrs); pImpl->AttrsSetNodes.InsertNode(PA, InsertPoint); } @@ -617,9 +616,8 @@ AttributeSet::getImpl(LLVMContext &C, // create a new one and insert it. if (!PA) { // Coallocate entries after the AttributeSetImpl itself. - void *Mem = ::operator new(sizeof(AttributeSetImpl) + - sizeof(std::pair) * - Attrs.size()); + void *Mem = ::operator new( + AttributeSetImpl::totalSizeToAlloc(Attrs.size())); PA = new (Mem) AttributeSetImpl(C, Attrs); pImpl->AttrsLists.InsertNode(PA, InsertPoint); } @@ -736,9 +734,8 @@ AttributeSet AttributeSet::get(LLVMContext &C, ArrayRef Attrs) { if (!AS) continue; SmallVector, 8>::iterator ANVI = AttrNodeVec.begin(), ANVE; - for (const AttributeSetImpl::IndexAttrPair - *AI = AS->getNode(0), - *AE = AS->getNode(AS->getNumAttributes()); + for (const IndexAttrPair *AI = AS->getNode(0), + *AE = AS->getNode(AS->getNumAttributes()); AI != AE; ++AI) { ANVE = AttrNodeVec.end(); while (ANVI != ANVE && ANVI->first <= AI->first) diff --git a/llvm/unittests/Support/CMakeLists.txt b/llvm/unittests/Support/CMakeLists.txt index 564d189..9c2aab4 100644 --- a/llvm/unittests/Support/CMakeLists.txt +++ b/llvm/unittests/Support/CMakeLists.txt @@ -41,6 +41,7 @@ add_llvm_unittest(SupportTests TargetRegistry.cpp ThreadLocalTest.cpp TimeValueTest.cpp + TrailingObjectsTest.cpp UnicodeTest.cpp YAMLIOTest.cpp YAMLParserTest.cpp diff --git a/llvm/unittests/Support/TrailingObjectsTest.cpp b/llvm/unittests/Support/TrailingObjectsTest.cpp new file mode 100644 index 0000000..fe1fbf1 --- /dev/null +++ b/llvm/unittests/Support/TrailingObjectsTest.cpp @@ -0,0 +1,147 @@ +//=== - llvm/unittest/Support/TrailingObjectsTest.cpp ---------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Support/TrailingObjects.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { +// This class, beyond being used by the test case, a nice +// demonstration of the intended usage of TrailingObjects, with a +// single trailing array. +class Class1 final : private TrailingObjects { + friend TrailingObjects; + + unsigned NumShorts; + +protected: + size_t numTrailingObjects(OverloadToken) const { return NumShorts; } + + Class1(int *ShortArray, unsigned NumShorts) : NumShorts(NumShorts) { + std::uninitialized_copy(ShortArray, ShortArray + NumShorts, + getTrailingObjects()); + } + +public: + static Class1 *create(int *ShortArray, unsigned NumShorts) { + void *Mem = ::operator new(totalSizeToAlloc(NumShorts)); + return new (Mem) Class1(ShortArray, NumShorts); + } + + short get(unsigned Num) const { return getTrailingObjects()[Num]; } + + unsigned numShorts() const { return NumShorts; } + + // Pull some protected members in as public, for testability. + using TrailingObjects::totalSizeToAlloc; + using TrailingObjects::additionalSizeToAlloc; + using TrailingObjects::getTrailingObjects; +}; + +// Here, there are two singular optional object types appended. +// Note that it fails to compile without the alignment spec. +class LLVM_ALIGNAS(8) Class2 final : private TrailingObjects { + friend TrailingObjects; + + bool HasShort, HasDouble; + +protected: + size_t numTrailingObjects(OverloadToken) const { + return HasShort ? 1 : 0; + } + size_t numTrailingObjects(OverloadToken) const { + return HasDouble ? 1 : 0; + } + + Class2(bool HasShort, bool HasDouble) + : HasShort(HasShort), HasDouble(HasDouble) {} + +public: + static Class2 *create(short S = 0, double D = 0.0) { + bool HasShort = S != 0; + bool HasDouble = D != 0.0; + + void *Mem = + ::operator new(totalSizeToAlloc(HasDouble, HasShort)); + Class2 *C = new (Mem) Class2(HasShort, HasDouble); + if (HasShort) + *C->getTrailingObjects() = S; + if (HasDouble) + *C->getTrailingObjects() = D; + return C; + } + + short getShort() const { + if (!HasShort) + return 0; + return *getTrailingObjects(); + } + + double getDouble() const { + if (!HasDouble) + return 0.0; + return *getTrailingObjects(); + } + + // Pull some protected members in as public, for testability. + using TrailingObjects::totalSizeToAlloc; + using TrailingObjects::additionalSizeToAlloc; + using TrailingObjects::getTrailingObjects; +}; + +TEST(TrailingObjects, OneArg) { + int arr[] = {1, 2, 3}; + Class1 *C = Class1::create(arr, 3); + EXPECT_EQ(sizeof(Class1), sizeof(unsigned)); + EXPECT_EQ(Class1::additionalSizeToAlloc(1), sizeof(short)); + EXPECT_EQ(Class1::additionalSizeToAlloc(3), sizeof(short) * 3); + + EXPECT_EQ(Class1::totalSizeToAlloc(1), sizeof(Class1) + sizeof(short)); + EXPECT_EQ(Class1::totalSizeToAlloc(3), + sizeof(Class1) + sizeof(short) * 3); + + EXPECT_EQ(C->getTrailingObjects(), reinterpret_cast(C + 1)); + EXPECT_EQ(C->get(0), 1); + EXPECT_EQ(C->get(2), 3); + delete C; +} + +TEST(TrailingObjects, TwoArg) { + Class2 *C1 = Class2::create(4); + Class2 *C2 = Class2::create(0, 4.2); + + EXPECT_EQ(sizeof(Class2), 8u); // due to alignment + + EXPECT_EQ((Class2::additionalSizeToAlloc(1, 0)), + sizeof(double)); + EXPECT_EQ((Class2::additionalSizeToAlloc(0, 1)), + sizeof(short)); + EXPECT_EQ((Class2::additionalSizeToAlloc(3, 1)), + sizeof(double) * 3 + sizeof(short)); + + EXPECT_EQ((Class2::totalSizeToAlloc(1, 1)), + sizeof(Class2) + sizeof(double) + sizeof(short)); + + EXPECT_EQ(C1->getDouble(), 0); + EXPECT_EQ(C1->getShort(), 4); + EXPECT_EQ(C1->getTrailingObjects(), + reinterpret_cast(C1 + 1)); + EXPECT_EQ(C1->getTrailingObjects(), reinterpret_cast(C1 + 1)); + + EXPECT_EQ(C2->getDouble(), 4.2); + EXPECT_EQ(C2->getShort(), 0); + EXPECT_EQ(C2->getTrailingObjects(), + reinterpret_cast(C2 + 1)); + EXPECT_EQ(C2->getTrailingObjects(), + reinterpret_cast(reinterpret_cast(C2 + 1) + 1)); + delete C1; + delete C2; +} +} -- 2.7.4