Index: llvm/include/llvm/Support/TypeSize.h =================================================================== --- llvm/include/llvm/Support/TypeSize.h +++ llvm/include/llvm/Support/TypeSize.h @@ -15,69 +15,214 @@ #ifndef LLVM_SUPPORT_TYPESIZE_H #define LLVM_SUPPORT_TYPESIZE_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/WithColor.h" -#include +#include #include +#include +#include namespace llvm { template struct DenseMapInfo; -// TODO: This class will be redesigned in a later patch that introduces full -// polynomial behaviour, i.e. the ability to have composites made up of both -// fixed and scalable sizes. -template class PolySize { +/// LinearPolyBaseOperators provides a set of overloaded operators +/// for common arithmetic on derived classes of LinearPolyBase using +/// the corresponding (protected) member functions in the parent class, +/// yet returning the type of the derived class. +template class LinearPolyBaseOperators { + friend Ty &operator+=(Ty &LHS, const Ty &RHS) { + return static_cast(add(LHS, RHS)); + } + friend Ty &operator-=(Ty &LHS, const Ty &RHS) { + return static_cast(sub(LHS, RHS)); + } + friend Ty &operator*=(Ty &LHS, const ScalarTy &RHS) { + return static_cast(scale(LHS, RHS)); + } + + friend Ty operator+(const Ty &LHS, const Ty &RHS) { + Ty Copy = LHS; + return Copy += RHS; + } + friend Ty operator-(const Ty &LHS, const Ty &RHS) { + Ty Copy = LHS; + return Copy -= RHS; + } + friend Ty operator*(const Ty &LHS, ScalarTy RHS) { + Ty Copy = LHS; + return Copy *= RHS; + } + + template + friend typename std::enable_if::value, Ty>::type & + operator-(const Ty &LHS) { + Ty Copy = LHS; + return Copy *= -1; + } +}; + +/// LinearPolyBase is a base class for ElementCount, TypeSize and StackOffset. +/// It tries to represent a linear polynomial, e.g. +/// c0 * scale0 + c1 * scale1 + ... + cK * scaleK +/// where the scale is implicit. Only the coefficients are encoded. +/// +/// is the type of the coefficients. +/// are the number of dimensions of the linear polynomial. +/// lets LinearPolyBase represent a linear polynomial with +/// coefficients for only a single dimension when true, or multiple coefficients +/// when false. +template +class LinearPolyBase { protected: - T MinVal; // The minimum value that it could be. - bool IsScalable; // If true, the total value is determined by multiplying - // 'MinVal' by a runtime determinded quantity, 'vscale'. + std::array Coefficients; + unsigned UnivariateDim; + + // Create a LinearPolyBase for multiple dimensions. + template + LinearPolyBase(ArrayRef::type> Values) + : UnivariateDim(std::numeric_limits::max()) { + assert(Values.size() == Dimensions && "Incorrect number of values"); + for (unsigned I = 0; I < Dimensions; ++I) + Coefficients[I] = Values[I]; + } + + // Create a LinearPolyBase for a single dimension. + template + LinearPolyBase(const typename std::enable_if<(U), T>::type &Val, + unsigned UnivariateDim) + : UnivariateDim(UnivariateDim) { + assert(UnivariateDim < Dimensions && "Incorrect dimension"); + Coefficients.fill(0); + Coefficients[UnivariateDim] = Val; + } - constexpr PolySize(T MinVal, bool IsScalable) - : MinVal(MinVal), IsScalable(IsScalable) {} + friend LinearPolyBase &add(LinearPolyBase &LHS, const LinearPolyBase &RHS) { + assert((!IsUnivariate || LHS.UnivariateDim == RHS.UnivariateDim) && + "Invalid dimensions"); + for (unsigned I = 0; I < Dimensions; ++I) + LHS.Coefficients[I] += RHS.Coefficients[I]; + return LHS; + } -public: + friend LinearPolyBase &sub(LinearPolyBase &LHS, const LinearPolyBase &RHS) { + assert((!IsUnivariate || LHS.UnivariateDim == RHS.UnivariateDim) && + "Invalid dimensions"); + for (unsigned I = 0; I < Dimensions; ++I) + LHS.Coefficients[I] -= RHS.Coefficients[I]; + return LHS; + } + + friend LinearPolyBase &scale(LinearPolyBase &LHS, const T &RHS) { + for (unsigned I = 0; I < Dimensions; ++I) + LHS.Coefficients[I] *= RHS; + return LHS; + } - static constexpr PolySize getFixed(T MinVal) { return {MinVal, false}; } - static constexpr PolySize getScalable(T MinVal) { return {MinVal, true}; } - static constexpr PolySize get(T MinVal, bool IsScalable) { - return {MinVal, IsScalable}; +public: + bool operator==(const LinearPolyBase &RHS) const { + return std::equal(&Coefficients[0], &Coefficients[Dimensions], + &RHS.Coefficients[0]); } - static constexpr PolySize getNull() { return {0, false}; } + bool operator!=(const LinearPolyBase &RHS) const { return !(*this == RHS); } + + bool isZero() const { + return std::all_of(Coefficients.begin(), Coefficients.end(), + [](const T &C) { return C == 0; }); + } /// Counting predicates. /// ///@{ No elements.. - bool isZero() const { return MinVal == 0; } - /// At least one element. bool isNonZero() const { return !isZero(); } + + /// At least one element. + explicit operator bool() const { return isNonZero(); } + + T getValue(unsigned Dim) const { return Coefficients[Dim]; } + + template + typename std::enable_if<(U), T>::type getExclusiveValue() const { + return Coefficients[UnivariateDim]; + } +}; + +using StackOffsetBase = + LinearPolyBase; + +/// NewStackOffset is a class to represent an offset with 2 dimensions, +/// named fixed and scalable, respectively. This class allows a value for both +/// dimensions to depict e.g. "8 bytes and 16 scalable bytes", which is needed +/// to represent stack offsets. +class NewStackOffset : public StackOffsetBase, + public LinearPolyBaseOperators { +protected: + NewStackOffset(int64_t Fixed, int64_t Scalable) + : StackOffsetBase({Fixed, Scalable}) {} + +public: + NewStackOffset() : NewStackOffset({0, 0}) {} + NewStackOffset(const StackOffsetBase &Other) : StackOffsetBase(Other) {} + static NewStackOffset getFixed(int64_t Fixed) { return {Fixed, 0}; } + static NewStackOffset getScalable(int64_t Scalable) { return {0, Scalable}; } + static NewStackOffset get(int64_t Fixed, int64_t Scalable) { + return {Fixed, Scalable}; + } + + int64_t getFixed() const { return this->getValue(0); } + int64_t getScalable() const { return this->getValue(1); } + std::pair getMixed() const { + return {this->getValue(0), this->getValue(1)}; + } +}; + +template +using LinearPolySizeBase = + LinearPolyBase; + +/// LinearPolySize is a base class to represent 2 dimensions, where the +/// base class can only represent 1 dimension exclusively at a time, i.e. it is +/// either fixed-sized or it is scalable-sized, but it cannot be both. +template +class LinearPolySize : public LinearPolySizeBase, + public LinearPolyBaseOperators, T> { +protected: + LinearPolySize(T MinVal, bool IsScalable) + : LinearPolySizeBase(MinVal, !IsScalable ? 0 : 1) {} + +public: + LinearPolySize(const LinearPolySizeBase &Other) + : LinearPolySizeBase(Other) {} + static LinearPolySize getFixed(T MinVal) { return {MinVal, false}; } + static LinearPolySize getScalable(T MinVal) { return {MinVal, true}; } + static LinearPolySize get(T MinVal, bool Scalable) { + return {MinVal, Scalable}; + } + + /// Returns the minimum value this size can represent. + T getKnownMinValue() const { return this->getExclusiveValue(); } + /// Returns whether the size is scaled by a runtime quantity (vscale). + bool isScalable() const { return this->UnivariateDim == 1; } /// A return value of true indicates we know at compile time that the number /// of elements (vscale * Min) is definitely even. However, returning false /// does not guarantee that the total number of elements is odd. - bool isKnownEven() const { return (MinVal & 0x1) == 0; } - ///@} - - T getKnownMinValue() const { return MinVal; } + bool isKnownEven() const { return (getKnownMinValue() & 0x1) == 0; } + /// This function tells the caller whether the element count is known at + /// compile time to be a multiple of the scalar value RHS. + bool isKnownMultipleOf(T RHS) const { return getKnownMinValue() % RHS == 0; } // Return the minimum value with the assumption that the count is exact. // Use in places where a scalable count doesn't make sense (e.g. non-vector // types, or vectors in backends which don't support scalable vectors). T getFixedValue() const { - assert(!IsScalable && + assert(!isScalable() && "Request for a fixed element count on a scalable object"); - return MinVal; - } - - bool isScalable() const { return IsScalable; } - - bool operator==(const PolySize &RHS) const { - return MinVal == RHS.MinVal && IsScalable == RHS.IsScalable; + return getKnownMinValue(); } - bool operator!=(const PolySize &RHS) const { return !(*this == RHS); } - // For some cases, size ordering between scalable and fixed size types cannot // be determined at compile time, so such comparisons aren't allowed. // @@ -88,55 +233,30 @@ // All the functions below make use of the fact vscale is always >= 1, which // means that is guaranteed to be >= <4 x i32>, etc. - static bool isKnownLT(const PolySize &LHS, const PolySize &RHS) { - if (!LHS.IsScalable || RHS.IsScalable) - return LHS.MinVal < RHS.MinVal; - - // LHS.IsScalable = true, RHS.IsScalable = false + static bool isKnownLT(const LinearPolySize &LHS, const LinearPolySize &RHS) { + if (!LHS.isScalable() || RHS.isScalable()) + return LHS.getKnownMinValue() < RHS.getKnownMinValue(); return false; } - static bool isKnownGT(const PolySize &LHS, const PolySize &RHS) { - if (LHS.IsScalable || !RHS.IsScalable) - return LHS.MinVal > RHS.MinVal; - - // LHS.IsScalable = false, RHS.IsScalable = true + static bool isKnownGT(const LinearPolySize &LHS, const LinearPolySize &RHS) { + if (LHS.isScalable() || !RHS.isScalable()) + return LHS.getKnownMinValue() > RHS.getKnownMinValue(); return false; } - static bool isKnownLE(const PolySize &LHS, const PolySize &RHS) { - if (!LHS.IsScalable || RHS.IsScalable) - return LHS.MinVal <= RHS.MinVal; - - // LHS.IsScalable = true, RHS.IsScalable = false + static bool isKnownLE(const LinearPolySize &LHS, const LinearPolySize &RHS) { + if (!LHS.isScalable() || RHS.isScalable()) + return LHS.getKnownMinValue() <= RHS.getKnownMinValue(); return false; } - static bool isKnownGE(const PolySize &LHS, const PolySize &RHS) { - if (LHS.IsScalable || !RHS.IsScalable) - return LHS.MinVal >= RHS.MinVal; - - // LHS.IsScalable = false, RHS.IsScalable = true + static bool isKnownGE(const LinearPolySize &LHS, const LinearPolySize &RHS) { + if (LHS.isScalable() || !RHS.isScalable()) + return LHS.getKnownMinValue() >= RHS.getKnownMinValue(); return false; } - PolySize operator*(T RHS) { return {MinVal * RHS, IsScalable}; } - - PolySize &operator*=(T RHS) { - MinVal *= RHS; - return *this; - } - - friend PolySize operator-(const PolySize &LHS, const PolySize &RHS) { - assert(LHS.IsScalable == RHS.IsScalable && - "Arithmetic using mixed scalable and fixed types"); - return {LHS.MinVal - RHS.MinVal, LHS.IsScalable}; - } - - /// This function tells the caller whether the element count is known at - /// compile time to be a multiple of the scalar value RHS. - bool isKnownMultipleOf(T RHS) const { return MinVal % RHS == 0; } - /// We do not provide the '/' operator here because division for polynomial /// types does not work in the same way as for normal integer types. We can /// only divide the minimum value (or coefficient) by RHS, which is not the @@ -145,72 +265,75 @@ /// The caller is recommended to use this function in combination with /// isKnownMultipleOf(RHS), which lets the caller know if it's possible to /// perform a lossless divide by RHS. - PolySize divideCoefficientBy(T RHS) const { - return PolySize(MinVal / RHS, IsScalable); + LinearPolySize divideCoefficientBy(T RHS) const { + return LinearPolySize(getKnownMinValue() / RHS, isScalable()); } - PolySize coefficientNextPowerOf2() const { - return PolySize(static_cast(llvm::NextPowerOf2(MinVal)), IsScalable); + LinearPolySize coefficientNextPowerOf2() const { + return LinearPolySize( + static_cast(llvm::NextPowerOf2(getKnownMinValue())), isScalable()); } /// Printing function. void print(raw_ostream &OS) const { - if (IsScalable) + if (isScalable()) OS << "vscale x "; - OS << MinVal; + OS << getKnownMinValue(); } }; -/// Stream operator function for `PolySize`. +/// Stream operator function for `LinearPolySize`. template -inline raw_ostream &operator<<(raw_ostream &OS, const PolySize &PS) { +inline raw_ostream &operator<<(raw_ostream &OS, const LinearPolySize &PS) { PS.print(OS); return OS; } -class ElementCount : public PolySize { +class ElementCount : public LinearPolySize, + public LinearPolyBaseOperators { public: - - constexpr ElementCount(PolySize V) : PolySize(V) {} + ElementCount(const LinearPolySize &V) : LinearPolySize(V) {} /// Counting predicates. /// - /// Notice that MinVal = 1 and IsScalable = true is considered more than - /// one element. - /// - ///@{ No elements.. + ///@{ Number of elements.. /// Exactly one element. - bool isScalar() const { return !IsScalable && MinVal == 1; } + bool isScalar() const { return !isScalable() && getKnownMinValue() == 1; } /// One or more elements. - bool isVector() const { return (IsScalable && MinVal != 0) || MinVal > 1; } + bool isVector() const { + return (isScalable() && getKnownMinValue() != 0) || getKnownMinValue() > 1; + } ///@} }; -// This class is used to represent the size of types. If the type is of fixed +// TODO: Most functionality in this class will gradually be phased out +// so it will resemble LinearPolySize as much as possible. +// +// TypeSize is used to represent the size of types. If the type is of fixed // size, it will represent the exact size. If the type is a scalable vector, // it will represent the known minimum size. -class TypeSize : public PolySize { +class TypeSize : public LinearPolySize, + public LinearPolyBaseOperators { public: - constexpr TypeSize(PolySize V) : PolySize(V) {} + TypeSize(const LinearPolySize &V) : LinearPolySize(V) {} - constexpr TypeSize(uint64_t MinVal, bool IsScalable) - : PolySize(MinVal, IsScalable) {} + TypeSize(uint64_t MinVal, bool IsScalable) + : LinearPolySize(MinVal, IsScalable) {} - static constexpr TypeSize Fixed(uint64_t MinVal) { - return TypeSize(MinVal, false); - } - static constexpr TypeSize Scalable(uint64_t MinVal) { - return TypeSize(MinVal, true); - } + static TypeSize Fixed(uint64_t MinVal) { return TypeSize(MinVal, false); } + static TypeSize Scalable(uint64_t MinVal) { return TypeSize(MinVal, true); } uint64_t getFixedSize() const { return getFixedValue(); } uint64_t getKnownMinSize() const { return getKnownMinValue(); } + // The comparison operators are in the process of being phased out + // in favour of isKnownLT/isKnownLE of its parent class. + friend bool operator<(const TypeSize &LHS, const TypeSize &RHS) { - assert(LHS.IsScalable == RHS.IsScalable && + assert(LHS.isScalable() == RHS.isScalable() && "Ordering comparison of scalable and fixed types"); - return LHS.MinVal < RHS.MinVal; + return LHS.getKnownMinValue() < RHS.getKnownMinValue(); } friend bool operator>(const TypeSize &LHS, const TypeSize &RHS) { @@ -221,29 +344,15 @@ return !(RHS < LHS); } - friend bool operator>=(const TypeSize &LHS, const TypeSize& RHS) { + friend bool operator>=(const TypeSize &LHS, const TypeSize &RHS) { return !(LHS < RHS); } - TypeSize &operator-=(TypeSize RHS) { - assert(IsScalable == RHS.IsScalable && - "Subtraction using mixed scalable and fixed types"); - MinVal -= RHS.MinVal; - return *this; - } - - TypeSize &operator+=(TypeSize RHS) { - assert(IsScalable == RHS.IsScalable && - "Addition using mixed scalable and fixed types"); - MinVal += RHS.MinVal; - return *this; - } - - friend TypeSize operator-(const TypeSize &LHS, const TypeSize &RHS) { - assert(LHS.IsScalable == RHS.IsScalable && - "Arithmetic using mixed scalable and fixed types"); - return {LHS.MinVal - RHS.MinVal, LHS.IsScalable}; - } + // All code for this class below this point is needed because of the + // temporary implicit conversion to uint64_t. The operator overloads are + // needed because otherwise the conversion of the parent class LinearPolyBase + // -> TypeSize is ambiguous. + // TODO: Remove the implicit conversion. // Casts to a uint64_t if this is a fixed-width size. // @@ -275,32 +384,28 @@ #endif } - // Convenience operators to obtain relative sizes independently of - // the scalable flag. - TypeSize operator*(unsigned RHS) const { return {MinVal * RHS, IsScalable}; } - - friend TypeSize operator*(const unsigned LHS, const TypeSize &RHS) { - return {LHS * RHS.MinVal, RHS.IsScalable}; + // Additional operators needed to avoid ambiguous parses + // because of the implicit conversion hack. + friend TypeSize operator*(const TypeSize &LHS, const int RHS) { + return LHS * (uint64_t)RHS; } - - // Additional convenience operators needed to avoid ambiguous parses. - // TODO: Make uint64_t the default operator? - TypeSize operator*(uint64_t RHS) const { return {MinVal * RHS, IsScalable}; } - - TypeSize operator*(int RHS) const { return {MinVal * RHS, IsScalable}; } - - TypeSize operator*(int64_t RHS) const { return {MinVal * RHS, IsScalable}; } - - friend TypeSize operator*(const uint64_t LHS, const TypeSize &RHS) { - return {LHS * RHS.MinVal, RHS.IsScalable}; + friend TypeSize operator*(const TypeSize &LHS, const unsigned RHS) { + return LHS * (uint64_t)RHS; + } + friend TypeSize operator*(const TypeSize &LHS, const int64_t RHS) { + return LHS * (uint64_t)RHS; } - friend TypeSize operator*(const int LHS, const TypeSize &RHS) { - return {LHS * RHS.MinVal, RHS.IsScalable}; + return RHS * LHS; + } + friend TypeSize operator*(const unsigned LHS, const TypeSize &RHS) { + return RHS * LHS; } - friend TypeSize operator*(const int64_t LHS, const TypeSize &RHS) { - return {LHS * RHS.MinVal, RHS.IsScalable}; + return RHS * LHS; + } + friend TypeSize operator*(const uint64_t LHS, const TypeSize &RHS) { + return RHS * LHS; } }; @@ -322,7 +427,7 @@ static inline ElementCount getTombstoneKey() { return ElementCount::getFixed(~0U - 1); } - static unsigned getHashValue(const ElementCount& EltCnt) { + static unsigned getHashValue(const ElementCount &EltCnt) { unsigned HashVal = EltCnt.getKnownMinValue() * 37U; if (EltCnt.isScalable()) return (HashVal - 1U); @@ -330,7 +435,7 @@ return HashVal; } - static bool isEqual(const ElementCount& LHS, const ElementCount& RHS) { + static bool isEqual(const ElementCount &LHS, const ElementCount &RHS) { return LHS == RHS; } }; Index: llvm/unittests/Support/CMakeLists.txt =================================================================== --- llvm/unittests/Support/CMakeLists.txt +++ llvm/unittests/Support/CMakeLists.txt @@ -71,6 +71,7 @@ TarWriterTest.cpp TargetParserTest.cpp TaskQueueTest.cpp + StackOffsetTest.cpp ThreadLocalTest.cpp ThreadPool.cpp Threading.cpp Index: llvm/unittests/Support/StackOffsetTest.cpp =================================================================== --- /dev/null +++ llvm/unittests/Support/StackOffsetTest.cpp @@ -0,0 +1,98 @@ +//===- TestNewStackOffset.cpp - NewStackOffset unit tests------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Support/TypeSize.h" +#include "gtest/gtest.h" + +using namespace llvm; + +TEST(NewStackOffset, MixedSize) { + NewStackOffset A = NewStackOffset::getFixed(42); + EXPECT_EQ(42, A.getFixed()); + EXPECT_EQ(0, A.getScalable()); + + NewStackOffset B = NewStackOffset::getScalable(42); + EXPECT_EQ(0, B.getFixed()); + EXPECT_EQ(42, B.getScalable()); + + NewStackOffset C = NewStackOffset::get(4, 8); + EXPECT_EQ(4, C.getFixed()); + EXPECT_EQ(8, C.getScalable()); +} + +TEST(NewStackOffset, Add) { + NewStackOffset A = NewStackOffset::getFixed(4); + NewStackOffset B = NewStackOffset::getFixed(8); + NewStackOffset C = A + B; + EXPECT_EQ(12, C.getFixed()); + EXPECT_EQ(0, C.getScalable()); + + NewStackOffset D = NewStackOffset::getScalable(4); + NewStackOffset E = NewStackOffset::getScalable(8); + NewStackOffset F = D + E; + EXPECT_EQ(0, F.getFixed()); + EXPECT_EQ(12, F.getScalable()); + + NewStackOffset G = A + E; + EXPECT_EQ(4, G.getFixed()); + EXPECT_EQ(8, G.getScalable()); + + G += C + F; + EXPECT_EQ(16, G.getFixed()); + EXPECT_EQ(20, G.getScalable()); +} + +TEST(NewStackOffset, Sub) { + NewStackOffset A = NewStackOffset::getFixed(4); + NewStackOffset B = NewStackOffset::getFixed(8); + NewStackOffset C = A - B; + EXPECT_EQ(-4, C.getFixed()); + EXPECT_EQ(0, C.getScalable()); + + NewStackOffset D = NewStackOffset::getScalable(4); + NewStackOffset E = NewStackOffset::getScalable(8); + NewStackOffset F = D - E; + EXPECT_EQ(0, F.getFixed()); + EXPECT_EQ(-4, F.getScalable()); + + NewStackOffset G = A - E; + EXPECT_EQ(4, G.getFixed()); + EXPECT_EQ(-8, G.getScalable()); + + G -= C - F; + EXPECT_EQ(8, G.getFixed()); + EXPECT_EQ(-12, G.getScalable()); +} + +TEST(NewStackOffset, Scale) { + NewStackOffset A = NewStackOffset::get(4, 8); + + NewStackOffset B = A * 3; + EXPECT_EQ(12, B.getFixed()); + EXPECT_EQ(24, B.getScalable()); + + B *= 2; + EXPECT_EQ(24, B.getFixed()); + EXPECT_EQ(48, B.getScalable()); +} + +TEST(NewStackOffset, Negate) { + NewStackOffset A = NewStackOffset::get(4, 8); + NewStackOffset B = -A; + EXPECT_EQ(-4, B.getFixed()); + EXPECT_EQ(-8, B.getScalable()); +} + +TEST(NewStackOffset, isNonZero) { + EXPECT_FALSE(NewStackOffset::getFixed(0)); + EXPECT_FALSE(NewStackOffset::getScalable(0)); + + EXPECT_TRUE(NewStackOffset::getFixed(1)); + EXPECT_TRUE(NewStackOffset::getScalable(1)); + EXPECT_TRUE(NewStackOffset::get(1, 1)); +}