diff --git a/llvm/include/llvm/Support/Alignment.h b/llvm/include/llvm/Support/Alignment.h --- a/llvm/include/llvm/Support/Alignment.h +++ b/llvm/include/llvm/Support/Alignment.h @@ -21,6 +21,7 @@ #ifndef LLVM_SUPPORT_ALIGNMENT_H_ #define LLVM_SUPPORT_ALIGNMENT_H_ +#include "llvm/Support/BasicTypes.h" #include "llvm/Support/MathExtras.h" #include #include @@ -33,80 +34,6 @@ #define ALIGN_CHECK_ISPOSITIVE(decl) \ assert(decl > 0 && (#decl " should be defined")) -/// This struct is a compact representation of a valid (non-zero power of two) -/// alignment. -/// It is suitable for use as static global constants. -struct Align { -private: - uint8_t ShiftValue = 0; /// The log2 of the required alignment. - /// ShiftValue is less than 64 by construction. - - friend struct MaybeAlign; - friend unsigned Log2(Align); - friend bool operator==(Align Lhs, Align Rhs); - friend bool operator!=(Align Lhs, Align Rhs); - friend bool operator<=(Align Lhs, Align Rhs); - friend bool operator>=(Align Lhs, Align Rhs); - friend bool operator<(Align Lhs, Align Rhs); - friend bool operator>(Align Lhs, Align Rhs); - friend unsigned encode(struct MaybeAlign A); - friend struct MaybeAlign decodeMaybeAlign(unsigned Value); - - /// A trivial type to allow construction of constexpr Align. - /// This is currently needed to workaround a bug in GCC 5.3 which prevents - /// definition of constexpr assign operators. - /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic - /// FIXME: Remove this, make all assign operators constexpr and introduce user - /// defined literals when we don't have to support GCC 5.3 anymore. - /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain - struct LogValue { - uint8_t Log; - }; - -public: - /// Default is byte-aligned. - constexpr Align() = default; - /// Do not perform checks in case of copy/move construct/assign, because the - /// checks have been performed when building `Other`. - constexpr Align(const Align &Other) = default; - constexpr Align(Align &&Other) = default; - Align &operator=(const Align &Other) = default; - Align &operator=(Align &&Other) = default; - - explicit Align(uint64_t Value) { - assert(Value > 0 && "Value must not be 0"); - assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2"); - ShiftValue = Log2_64(Value); - assert(ShiftValue < 64 && "Broken invariant"); - } - - /// This is a hole in the type system and should not be abused. - /// Needed to interact with C for instance. - uint64_t value() const { return uint64_t(1) << ShiftValue; } - - // Returns the previous alignment. - Align previous() const { - assert(ShiftValue != 0 && "Undefined operation"); - Align Out; - Out.ShiftValue = ShiftValue - 1; - return Out; - } - - /// Allow constructions of constexpr Align. - template constexpr static Align Constant() { - return LogValue{static_cast(CTLog2())}; - } - - /// Allow constructions of constexpr Align from types. - /// Compile time equivalent to Align(alignof(T)). - template constexpr static Align Of() { - return Constant::value>(); - } - - /// Constexpr constructor from LogValue type. - constexpr Align(LogValue CA) : ShiftValue(CA.Log) {} -}; - /// Treats the value 0 as a 1, so Align is always at least 1. inline Align assumeAligned(uint64_t Value) { return Value ? Align(Value) : Align(); @@ -143,27 +70,17 @@ /// Checks that SizeInBytes is a multiple of the alignment. inline bool isAligned(Align Lhs, uint64_t SizeInBytes) { - return SizeInBytes % Lhs.value() == 0; + return hostAddress(SizeInBytes).isAligned(Lhs); } /// Checks that Addr is a multiple of the alignment. inline bool isAddrAligned(Align Lhs, const void *Addr) { - return isAligned(Lhs, reinterpret_cast(Addr)); + return hostAddress(Addr).isAligned(Lhs); } /// Returns a multiple of A needed to store `Size` bytes. inline uint64_t alignTo(uint64_t Size, Align A) { - const uint64_t Value = A.value(); - // The following line is equivalent to `(Size + Value - 1) / Value * Value`. - - // The division followed by a multiplication can be thought of as a right - // shift followed by a left shift which zeros out the extra bits produced in - // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out - // are just zero. - - // Most compilers can generate this code but the pattern may be missed when - // multiple functions gets inlined. - return (Size + Value - 1) & ~(Value - 1U); + return hostAddress(Size).alignUp(A); } /// If non-zero \p Skew is specified, the return value will be a minimal integer @@ -178,34 +95,29 @@ /// alignTo(~0LL, Align(8), 3) = 3 /// \endcode inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) { - const uint64_t Value = A.value(); - Skew %= Value; - return alignTo(Size - Skew, A) + Skew; + Skew %= A.value(); + return hostAddress(Size - Skew).alignUp(A) + Skew; } /// Aligns `Addr` to `Alignment` bytes, rounding up. inline uintptr_t alignAddr(const void *Addr, Align Alignment) { - uintptr_t ArithAddr = reinterpret_cast(Addr); - assert(static_cast(ArithAddr + Alignment.value() - 1) >= - ArithAddr && - "Overflow"); - return alignTo(ArithAddr, Alignment); + return reinterpret_cast(hostAddress(Addr).alignUp(Alignment)); } /// Returns the offset to the next integer (mod 2**64) that is greater than /// or equal to \p Value and is a multiple of \p Align. inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) { - return alignTo(Value, Alignment) - Value; + return getUnsafeRawQuantity(hostAddress(Value).bytesToNextAlign(Alignment)); } /// Returns the necessary adjustment for aligning `Addr` to `Alignment` /// bytes, rounding up. inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) { - return offsetToAlignment(reinterpret_cast(Addr), Alignment); + return getUnsafeRawQuantity(hostAddress(Addr).bytesToNextAlign(Alignment)); } /// Returns the log2 of the alignment. -inline unsigned Log2(Align A) { return A.ShiftValue; } +inline unsigned Log2(Align A) { return A.getPowerOf2Bytes().getLogValue(); } /// Returns the alignment that satisfies both alignments. /// Same semantic as MinAlign. @@ -214,15 +126,13 @@ } /// Returns a representation of the alignment that encodes undefined as 0. -inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; } +inline unsigned encode(MaybeAlign A) { return A ? Log2(*A) + 1 : 0; } /// Dual operation of the encode function above. inline MaybeAlign decodeMaybeAlign(unsigned Value) { if (Value == 0) return MaybeAlign(); - Align Out; - Out.ShiftValue = Value - 1; - return Out; + return Align(PowerOf2::fromLogValue(Value - 1)); } /// Returns a representation of the alignment, the encoded value is positive by @@ -232,47 +142,27 @@ /// Comparisons between Align and scalars. Rhs must be positive. inline bool operator==(Align Lhs, uint64_t Rhs) { ALIGN_CHECK_ISPOSITIVE(Rhs); - return Lhs.value() == Rhs; + return Lhs.getBytes() == Bytes(Rhs); } inline bool operator!=(Align Lhs, uint64_t Rhs) { ALIGN_CHECK_ISPOSITIVE(Rhs); - return Lhs.value() != Rhs; + return Lhs.getBytes() != Bytes(Rhs); } inline bool operator<=(Align Lhs, uint64_t Rhs) { ALIGN_CHECK_ISPOSITIVE(Rhs); - return Lhs.value() <= Rhs; + return Lhs.getBytes() <= Bytes(Rhs); } inline bool operator>=(Align Lhs, uint64_t Rhs) { ALIGN_CHECK_ISPOSITIVE(Rhs); - return Lhs.value() >= Rhs; + return Lhs.getBytes() >= Bytes(Rhs); } inline bool operator<(Align Lhs, uint64_t Rhs) { ALIGN_CHECK_ISPOSITIVE(Rhs); - return Lhs.value() < Rhs; + return Lhs.getBytes() < Bytes(Rhs); } inline bool operator>(Align Lhs, uint64_t Rhs) { ALIGN_CHECK_ISPOSITIVE(Rhs); - return Lhs.value() > Rhs; -} - -/// Comparisons operators between Align. -inline bool operator==(Align Lhs, Align Rhs) { - return Lhs.ShiftValue == Rhs.ShiftValue; -} -inline bool operator!=(Align Lhs, Align Rhs) { - return Lhs.ShiftValue != Rhs.ShiftValue; -} -inline bool operator<=(Align Lhs, Align Rhs) { - return Lhs.ShiftValue <= Rhs.ShiftValue; -} -inline bool operator>=(Align Lhs, Align Rhs) { - return Lhs.ShiftValue >= Rhs.ShiftValue; -} -inline bool operator<(Align Lhs, Align Rhs) { - return Lhs.ShiftValue < Rhs.ShiftValue; -} -inline bool operator>(Align Lhs, Align Rhs) { - return Lhs.ShiftValue > Rhs.ShiftValue; + return Lhs.getBytes() > Bytes(Rhs); } // Don't allow relational comparisons with MaybeAlign. diff --git a/llvm/include/llvm/Support/BasicTypes.h b/llvm/include/llvm/Support/BasicTypes.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Support/BasicTypes.h @@ -0,0 +1,524 @@ +//===- llvm/Support/BasicTypes.h - low level abstractions ------*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Concepts +// -------- +// +// - Size : a null or positive value with a unit. +// - Offset : a relative value with a unit. +// +// This file defines the following set of basic types: +// - Bits : A Size with the Bit unit. +// - Bytes : A Size with the Byte unit. +// - BitsOffset : An Offset with the Bit unit. +// - BytesOffset : An Offset with the Byte unit. +// - PowerOf2 : A number of bits that is a power of two. +// - PowerOf2 : A number of bytes that is a power of two. +// - MultipleOf : A number of bits that is a multiple of a given value. +// - MultipleOf : A number of bytes that is a multiple of a given value. +// - Align : An alignment number expressed in Bytes (internally represented as a +// PowerOf2) +// - HostAddress : An address represented as an uintptr_t +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_BASIC_TYPES_H +#define LLVM_SUPPORT_BASIC_TYPES_H + +#include +#include +#include +#include + +#include "llvm/Support/MathExtras.h" + +namespace llvm { + +namespace details { + +struct ByteTag {}; +struct BitTag {}; + +template struct BaseImpl { + static_assert(std::is_integral_v); + using raw_type = ScalarType; + + /// Default constructor initializing to 0. + constexpr explicit BaseImpl() = default; + /// Explicit constructor initializing to provided Quantity. + constexpr explicit BaseImpl(raw_type Quantity) : Quantity(Quantity) {} + + /// Returns true if value is zero. + bool isZero() const { return Quantity == 0; } + /// Returns true if value is one. + bool isOne() const { return Quantity == 1; } + /// Returns true if value is strictly positive. + bool isPositive() const { return Quantity > 0; } + + // Comparison operators. + bool operator==(ConcreteT Rhs) const { return Quantity == Rhs.Quantity; } + bool operator!=(ConcreteT Rhs) const { return Quantity != Rhs.Quantity; } + + // Relational operators. + bool operator<(ConcreteT Rhs) const { return Quantity < Rhs.Quantity; } + bool operator<=(ConcreteT Rhs) const { return Quantity <= Rhs.Quantity; } + bool operator>(ConcreteT Rhs) const { return Quantity > Rhs.Quantity; } + bool operator>=(ConcreteT Rhs) const { return Quantity >= Rhs.Quantity; } + + // Arithmetic operators. + ConcreteT operator+(ConcreteT Rhs) const { + return ConcreteT(Quantity + Rhs.Quantity); + } + ConcreteT operator*(raw_type N) const { return ConcreteT(Quantity * N); } + void operator*=(raw_type N) { Quantity *= N; } + ConcreteT operator/(raw_type N) const { return ConcreteT(Quantity / N); } + void operator/=(raw_type N) { Quantity /= N; } + raw_type operator/(ConcreteT Rhs) const { return Quantity / Rhs.Quantity; } + +protected: + ScalarType Quantity = 0; +}; + +/// A Size is a null or positive value with a unit. +/// It serves as a base class for Bits and Bytes below. +template +struct Size : public BaseImpl { + static_assert(std::is_unsigned::value, "Unexpected ScalarType"); + static constexpr bool is_size = true; + + using UP = BaseImpl; + using UP::UP; // Inherit constructors. + + /// Returns whether the value is a power of two. + bool isPowerOfTwo() const { return llvm::has_single_bit(UP::Quantity); } + + /// Returns whether this value is a multiple of another value. + bool isMultipleOf(ConcreteT Rhs) const { + assert(!Rhs.isZero() && "isMultipleOf(0) is undefined"); + return (*this % Rhs) == 0; + } + + /// Modulo operator with a scalar value, returns the same type. + ConcreteT operator%(ScalarType N) const { + assert(N != 0 && "Modulo operator is undefined for 0"); + return ConcreteT(UP::Quantity % N); + } + + /// Modulo operator, returns a scalar value. + ScalarType operator%(ConcreteT Rhs) const { + assert(!Rhs.isZero() && "Modulo operator is undefined for 0"); + return UP::Quantity % Rhs.Quantity; + } + + ConcreteT operator-(ConcreteT Rhs) const { + assert(UP::Quantity >= Rhs.Quantity && "Substraction underflows"); + return ConcreteT(UP::Quantity - Rhs.Quantity); + } + + // Allow construction from Offset type. + template friend struct Offset; +}; + +/// An Offset is a relative value with a unit. +/// It serves as a base class for BitsOffset and BytesOffset below. +template +struct Offset : public BaseImpl { + static_assert(std::is_signed::value, "Unexpected ScalarType"); + + using UP = BaseImpl; + using UP::UP; // Inherit constructors. + + /// Constructor from a Size type of the same unit. + /// Asserts when overflow occurs. + constexpr Offset(DualT Value) + : Offset(static_cast(Value.Quantity)) { + assert(Value.Quantity <= typename DualT::raw_type( + std::numeric_limits::max()) && + "Overflow"); + } + + /// Returns whether this value is stricly negative. + bool isNegative() const { return UP::Quantity < 0; } + + ConcreteT operator-(ConcreteT Rhs) const { + return ConcreteT(UP::Quantity - Rhs.Quantity); + } + ConcreteT operator-() const { return ConcreteT(-UP::Quantity); } +}; + +} // namespace details + +/// Represents a positive of null number of bytes. +struct Bytes : public details::Size { + using UP = details::Size; + using UP::UP; + + friend struct Bits; + friend struct Address; + friend struct Align; + + friend auto getUnsafeRawQuantity(Bytes); + template friend struct PowerOf2; +}; +/// Escape hatch to read the Bytes underlying value. +inline auto getUnsafeRawQuantity(Bytes Value) { return Value.Quantity; } + +/// Represents a positive of null number of bits. +struct Bits : public details::Size { + using UP = details::Size; + using UP::UP; + + constexpr Bits(Bytes B) : UP(B.Quantity * 8) {} + constexpr Bits(decltype(Quantity) B) : UP(B) {} + + /// Returns this value as Bytes if possible or std::nullopt otherwise. + std::optional asBytes() const { + if (isMultipleOf(Bits(8))) + return Bytes(Quantity / 8); + return {}; + } + + /// Returns the number of bytes needed to hold this many bits. + Bytes getCoveringBytes() const { return Bytes((Quantity + 7) / 8); } + + friend auto getUnsafeRawQuantity(Bits); + template friend struct PowerOf2; +}; +/// Escape hatch to read the Bits underlying value. +inline auto getUnsafeRawQuantity(Bits Value) { return Value.Quantity; } + +struct BytesOffset + : public details::Offset { + using UP = details::Offset; + using UP::UP; + + friend auto getUnsafeRawQuantity(BytesOffset); + // friend struct Address; +}; +/// Escape hatch to read the BytesOffset underlying value. +inline auto getUnsafeRawQuantity(BytesOffset Value) { return Value.Quantity; } + +struct BitsOffset + : public details::Offset { + using UP = details::Offset; + using UP::UP; + + friend auto getUnsafeRawQuantity(BitsOffset); +}; +/// Escape hatch to read the BitsOffset underlying value. +inline auto getUnsafeRawQuantity(BitsOffset Value) { return Value.Quantity; } + +/// Represents a Size (Bits or Bytes) that is a power of 2. +template struct PowerOf2 { + static_assert(UnitT::is_size, "Provided unit must be a Size"); + + /// Default constructor initializing to one. + constexpr PowerOf2() {} + + /// Constructor initializing to provided value. + /// Asserts when value is not a power of two. + constexpr PowerOf2(UnitT Value) : PowerOf2(validate(Value)) {} + + // Comparison operators. + bool operator==(PowerOf2 Value) const { return LogValue == Value.LogValue; } + bool operator!=(PowerOf2 Value) const { return LogValue != Value.LogValue; } + + // Relational operators. + bool operator<(PowerOf2 Value) const { return LogValue < Value.LogValue; } + bool operator<=(PowerOf2 Value) const { return LogValue <= Value.LogValue; } + bool operator>(PowerOf2 Value) const { return LogValue > Value.LogValue; } + bool operator>=(PowerOf2 Value) const { return LogValue >= Value.LogValue; } + + /// Returns true if value is one. + bool isOne() const { return LogValue == 0; } + + /// Returns the value. + UnitT getValue() const { return UnitT(1ULL << LogValue); } + + /// Returns the log2 of the value. + /// This is guaranteed to be a number in [0, 63]. + /// e.g. PowerOf2(256).getLogValue() == 8 + auto getLogValue() const { return LogValue; } + + /// Returns the next power of two. + /// Asserts if value becomes greater or equal to 2^64. + auto next() const { return PowerOf2(LogValue + 1); } + + /// Returns the previous power of two. + /// Asserts if current value is one. + auto previous() const { + assert(LogValue != 0 && "Undefined operation"); + return PowerOf2(LogValue - 1); + } + + /// Creates a PowerOf2 object from a log quantity. + /// e.g. PowerOf2::fromLogValue(8) == Bytes(256) + /// Asserts if value is greater or equal to 64. + static constexpr PowerOf2 fromLogValue(uint8_t LogValue) { + return PowerOf2(LogValue); + } + + /// Returns the the largest PowerOf2 not greater than value. + /// e.g. PowerOf2::floor(Bits(2)) == PowerOf2(Bits(2)) + /// e.g. PowerOf2::floor(Bits(3)) == PowerOf2(Bits(2)) + static PowerOf2 floor(UnitT Value) { + assert(Value.isPositive() && "Value must be strictly positive"); + return PowerOf2(llvm::Log2_64(Value.Quantity)); + } + + /// Returns the smallest PowerOf2 not less than value. + /// e.g. PowerOf2::ceil(Bits(2)) == PowerOf2(Bits(2)) + /// e.g. PowerOf2::ceil(Bits(3)) == PowerOf2(Bits(4)) + static PowerOf2 ceil(UnitT Value) { + assert(Value.isPositive() && "Value must be strictly positive"); + return floor(Value + UnitT(1)); + } + +private: + // Makes sure the provided value is a power of two and returns its log2 value. + static uint64_t validate(UnitT Value) { + assert(Value.isPositive() && "Value must be strictly positive"); + assert(Value.isPowerOfTwo() && "Value is not a power of 2"); + return llvm::Log2_64(Value.Quantity); + } + + // Internal construtor to build from a log value. + // Asserts if log value is greater of equals to 64. + constexpr PowerOf2(uint8_t LogValue) : LogValue(LogValue) { + assert(LogValue < 64 && "Exponent too big"); + } + + uint8_t LogValue = 0; // Compact storage. +}; + +/// Represents a Size (Bits or Bytes) that is a multiple of the provided value. +/// This is useful to represent scalable components. +template struct MultipleOf { + static_assert(UnitT::is_size && + std::is_unsigned::value, + "Provided unit must be Bytes or Bits"); + + /// Default constructor initializing to 1. + constexpr MultipleOf() {} + + /// Constructor initializing to provided value. + constexpr MultipleOf(UnitT Divisor) : MultipleOf(Divisor) { + assert(Divisor.isPositive() && "MultipleOf cannot be 0"); + } + + // Comparison operators. + bool operator==(MultipleOf Rhs) const { return Divisor == Rhs.Divisor; } + bool operator!=(MultipleOf Rhs) const { return Divisor != Rhs.Divisor; } + + /// Returns the value. + UnitT getDivisorValue() const { return Divisor; } + +private: + UnitT Divisor = UnitT(1); +}; + +/// Align represents an alignment in Bytes, it is always set and always a valid +/// power of two, its minimum value is 1 which means no alignment requirements. +struct Align { + constexpr Align() : Value() {} + constexpr Align(PowerOf2 Pow) : Value(Pow) {} + constexpr Align(Bytes Value) : Value(Value) {} + constexpr Align(uint64_t Value) : Align(Bytes(Value)) {} + + /// Returns true if value is one. + bool isOne() const { return Value.isOne(); } + + // Comparison operators. + bool operator==(Align Other) const { return Value == Other.Value; } + bool operator!=(Align Other) const { return Value != Other.Value; } + + // Relational operators. + bool operator<(Align Other) const { return Value < Other.Value; } + bool operator<=(Align Other) const { return Value <= Other.Value; } + bool operator>(Align Other) const { return Value > Other.Value; } + bool operator>=(Align Other) const { return Value >= Other.Value; } + + // Returns the previous alignment. + // i.e. Align(32).previous() == Align(16) + Align previous() const { + assert(Value != PowerOf2() && "Undefined operation"); + return Value.previous(); + } + + // Returns the alignment as bytes. + Bytes getBytes() const { return Value.getValue(); } + + // Returns the number of trailing zero bits. + Bits getTrailingZeroBits() const { return Value.getLogValue(); } + + // Returns the alignment as a power of two of bytes. + PowerOf2 getPowerOf2Bytes() const { return Value; } + + /// Allow constructions of constexpr Align. + template constexpr static Align Constant() { + return PowerOf2::fromLogValue(CTLog2()); + } + + /// Allow constructions of constexpr Align from types. + /// Compile time equivalent to Align(alignof(T)). + template constexpr static Align Of() { + return Constant::value>(); + } + + ///////////////////////////////////////////////////////////////////////////// + // Functions to ease transition to new types - Remove ASAP + ///////////////////////////////////////////////////////////////////////////// + + /// This is a hole in the type system and should not be abused. + /// Needed to interact with C for instance. + uint64_t value() const { return getUnsafeRawQuantity(getBytes()); } + +private: + PowerOf2 Value; +}; + +namespace details { + +struct PointerTag {}; +struct UnsignedTag {}; + +template struct UnderlyingUnsignedType {}; + +template struct UnderlyingUnsignedType { + using type = uintptr_t; + static type in(T Value) { return reinterpret_cast(Value); } + static T out(type Value) { return reinterpret_cast(Value); } +}; + +template struct UnderlyingUnsignedType { + using type = T; + static type in(T Value) { return Value; } + static T out(type Value) { return Value; } +}; + +template struct UnderlyingUnsignedType { + using type = Bytes::raw_type; + static type in(T Value) { return getUnsafeRawQuantity(Value); } + static T out(type Value) { return Bytes(Value); } +}; + +template struct BitwiseOp { + static_assert(std::is_unsigned::value, "Expected unsigned type"); + + static T clearLowBits(T Value, Bits Count) { + if (Count.isZero()) + return 0; + assert(Count < getMaxBits()); + uint8_t Shift = getUnsafeRawQuantity(Count); + Value >>= Shift; + Value <<= Shift; + return Value; + } + + static T clearHighBits(T Value, Bits Count) { + if (Count.isZero()) + return Value; + assert(Count < getMaxBits()); + uint8_t Shift = getUnsafeRawQuantity(Count); + Value <<= Shift; + Value >>= Shift; + return Value; + } + + static T keepLowBits(T Value, Bits Count) { + if (Count.isZero()) + return 0; + assert(Count < getMaxBits()); + return clearHighBits(Value, getMaxBits() - Count); + } + + static T keepHighBits(T Value, Bits Count) { + if (Count.isZero()) + return Value; + assert(Count < getMaxBits()); + return clearLowBits(Value, getMaxBits() - Count); + } + +protected: + static Bits getMaxBits() { return Bytes(sizeof(T)); } +}; + +} // namespace details + +template struct HostAddress { + using type_tag = std::conditional_t< + std::is_pointer::value, details::PointerTag, + std::conditional_t<(std::is_unsigned::value && + !std::is_same::value), + details::UnsignedTag, + std::conditional_t::value, + details::ByteTag, void>>>; + static_assert(!std::is_same::value, + "HostAddress can only be constructed from pointers, unsigned " + "integer or Bytes"); + using UUT = details::UnderlyingUnsignedType; + using unsigned_type = typename UUT::type; + using BO = details::BitwiseOp; + + HostAddress(T Value) : Value(UUT::in(Value)) {} + + /// Returns whether the address is aligned to the provided alignment. + bool isAligned(Align A) const { + return BO::keepLowBits(Value, A.getTrailingZeroBits()) == 0; + } + + /// If already aligned returns the same Address, otherwise returns the aligned + /// Address before this one. + T alignDown(Align A) const { return UUT::out(alignDownInternal(A)); } + + /// If already aligned returns the same Address, otherwise returns the aligned + /// Address after this one. + T alignUp(Align A) const { return UUT::out(alignUpInternal(A)); } + + Bytes bytesToNextAlign(Align A) const { + return Bytes(alignUpInternal(A) - Value); + } + + Bytes bytesFromPrevAlign(Align A) const { + return Bytes(Value - alignDownInternal(A)); + } + +private: + unsigned_type alignDownInternal(Align A) const { + return BO::clearLowBits(Value, A.getTrailingZeroBits()); + } + + unsigned_type alignUpInternal(Align A) const { + // The following code is equivalent to + // `(Value + Align - 1) / (Align * Align)`. + + // The division followed by a multiplication can be thought of as a right + // shift followed by a left shift which zeros out the extra bits produced in + // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out + // are just zero. + + // Most compilers can generate this code but the pattern may be missed when + // multiple functions gets inlined. + unsigned_type Mask = getUnsafeRawQuantity(A.getBytes()) - 1; + return (Value + Mask) & ~Mask; + } + unsigned_type Value; +}; + +// Convenient helper to construct a HostAddress from the right type. +template static inline auto hostAddress(T Value) { + return HostAddress(Value); +} + +inline Bytes operator""_bytes(unsigned long long int v) { return Bytes(v); } +inline Bits operator""_bits(unsigned long long int v) { return Bits(v); } + +} // namespace llvm + +#endif /* LLVM_SUPPORT_BASIC_TYPES_H */ diff --git a/llvm/unittests/Support/AlignmentTest.cpp b/llvm/unittests/Support/AlignmentTest.cpp --- a/llvm/unittests/Support/AlignmentTest.cpp +++ b/llvm/unittests/Support/AlignmentTest.cpp @@ -46,7 +46,7 @@ std::vector getValidAlignments() { std::vector Out; - for (size_t Shift = 0; Shift < 64; ++Shift) + for (size_t Shift = 0; Shift < 63; ++Shift) Out.push_back(1ULL << Shift); return Out; } @@ -235,9 +235,9 @@ std::vector getNonPowerOfTwo() { return {3, 10, 15}; } TEST(AlignmentDeathTest, InvalidCTors) { - EXPECT_DEATH((Align(0)), "Value must not be 0"); + EXPECT_DEATH((Align(0)), "Value must be strictly positive"); for (uint64_t Value : getNonPowerOfTwo()) { - EXPECT_DEATH((Align(Value)), "Alignment is not a power of 2"); + EXPECT_DEATH((Align(Value)), "Value is not a power of 2"); EXPECT_DEATH((MaybeAlign(Value)), "Alignment is neither 0 nor a power of 2"); } @@ -254,12 +254,6 @@ } } -TEST(AlignmentDeathTest, AlignAddr) { - const void *const unaligned_high_ptr = - reinterpret_cast(std::numeric_limits::max() - 1); - EXPECT_DEATH(alignAddr(unaligned_high_ptr, Align(16)), "Overflow"); -} - #endif // NDEBUG } // end anonymous namespace diff --git a/llvm/unittests/Support/BasicTypesTest.cpp b/llvm/unittests/Support/BasicTypesTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/Support/BasicTypesTest.cpp @@ -0,0 +1,303 @@ +//===- BasicTypesTest.cpp -------------------------------------------------===// +// +// 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/BasicTypes.h" +#include "gtest/gtest.h" + +namespace llvm { + +using QuantityTypes = + ::testing::Types; +template class BasicTypes_QuantitiesTest : public testing::Test {}; +TYPED_TEST_SUITE(BasicTypes_QuantitiesTest, QuantityTypes); +TYPED_TEST(BasicTypes_QuantitiesTest, Comparison) { + const auto A = TypeParam(1); + const auto B = TypeParam(2); + + EXPECT_EQ(A, A); + EXPECT_NE(A, B); + + EXPECT_LT(A, B); + EXPECT_GT(B, A); + + EXPECT_LE(A, B); + EXPECT_GE(B, A); + EXPECT_LE(A, A); + EXPECT_GE(A, A); +} + +using EscapableTypes = + ::testing::Types; +template +class BasicTypes_EscapableTypesTest : public testing::Test {}; +TYPED_TEST_SUITE(BasicTypes_EscapableTypesTest, EscapableTypes); +TYPED_TEST(BasicTypes_EscapableTypesTest, DefaultConstructibleAndEscapeHatch) { + using raw_type = typename TypeParam::raw_type; + const TypeParam DefaultValue; + EXPECT_EQ(getUnsafeRawQuantity(DefaultValue), raw_type(0)); +} + +using SizeTypes = ::testing::Types; +template class BasicTypes_Sizes : public testing::Test {}; +TYPED_TEST_SUITE(BasicTypes_Sizes, SizeTypes); + +using OffsetTypes = ::testing::Types; +template class BasicTypes_OffsetTypes : public testing::Test {}; +TYPED_TEST_SUITE(BasicTypes_OffsetTypes, OffsetTypes); + +using AllUnitTypes = ::testing::Types; +template +class BasicTypes_SizesAndOffsets : public testing::Test {}; +TYPED_TEST_SUITE(BasicTypes_SizesAndOffsets, AllUnitTypes); + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoComparison) { + const auto A = PowerOf2(TypeParam(1)); + const auto B = PowerOf2(TypeParam(2)); + + EXPECT_EQ(A, A); + EXPECT_NE(A, B); + + EXPECT_LT(A, B); + EXPECT_GT(B, A); + + EXPECT_LE(A, B); + EXPECT_GE(B, A); + EXPECT_LE(A, A); + EXPECT_GE(A, A); +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoLogValue) { + for (int64_t I = 0; I < 8; ++I) { + auto Value = TypeParam(1ULL << I); + EXPECT_EQ(PowerOf2(Value).getLogValue(), I); + } +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoValue) { + for (int64_t I = 0; I < 8; ++I) { + auto Value = TypeParam(1ULL << I); + EXPECT_EQ(PowerOf2(Value).getValue(), Value); + } +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoNext) { + for (int64_t I = 0; I < 8; ++I) { + auto Value = TypeParam(1ULL << I); + auto Next = TypeParam(1ULL << (I + 1)); + EXPECT_EQ(PowerOf2(Value).next(), Next); + } +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoPrevious) { + for (int64_t I = 0; I < 8; ++I) { + auto Previous = TypeParam(1ULL << I); + auto Value = TypeParam(1ULL << (I + 1)); + EXPECT_EQ(PowerOf2(Value).previous(), Previous); + } +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoFloor) { + EXPECT_EQ(PowerOf2::floor(TypeParam(2)), + PowerOf2(TypeParam(2))); + EXPECT_EQ(PowerOf2::floor(TypeParam(3)), + PowerOf2(TypeParam(2))); + EXPECT_EQ(PowerOf2::floor(TypeParam(4)), + PowerOf2(TypeParam(4))); +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoCeil) { + EXPECT_EQ(PowerOf2::ceil(TypeParam(2)), + PowerOf2(TypeParam(2))); + EXPECT_EQ(PowerOf2::ceil(TypeParam(3)), + PowerOf2(TypeParam(4))); + EXPECT_EQ(PowerOf2::ceil(TypeParam(4)), + PowerOf2(TypeParam(4))); +} + +TYPED_TEST(BasicTypes_Sizes, MultipleOf) { + MultipleOf A; + A.getDivisorValue(); +} + +TYPED_TEST(BasicTypes_SizesAndOffsets, Arithmetic) { + using raw_type = typename TypeParam::raw_type; + EXPECT_EQ(TypeParam(1) + TypeParam(2), TypeParam(3)); + EXPECT_EQ(TypeParam(8) - TypeParam(2), TypeParam(6)); + EXPECT_EQ(TypeParam(2) - TypeParam(2), TypeParam(0)); + + EXPECT_EQ(TypeParam(1) * 2, TypeParam(2)); + EXPECT_EQ(TypeParam(2) / TypeParam(2), raw_type(1)); + EXPECT_EQ(TypeParam(2) / 2, TypeParam(1)); + + auto Value = TypeParam(1); + Value *= 6; + EXPECT_EQ(Value, TypeParam(6)); + Value /= 2; + EXPECT_EQ(Value, TypeParam(3)); +} + +TYPED_TEST(BasicTypes_Sizes, Arithmetic) { + EXPECT_EQ(TypeParam(8) % 2, TypeParam(0)); + EXPECT_EQ(TypeParam(8) % TypeParam(2), 0UL); +} + +TYPED_TEST(BasicTypes_OffsetTypes, SignedArithmetic) { + EXPECT_EQ(TypeParam(1) - TypeParam(2), TypeParam(-1)); + EXPECT_EQ(-TypeParam(1), TypeParam(-1)); +} + +TYPED_TEST(BasicTypes_Sizes, Attributes) { + const auto Zero = TypeParam(0); + const auto One = TypeParam(1); + + EXPECT_TRUE(Zero.isZero()); + EXPECT_FALSE(One.isZero()); + + EXPECT_FALSE(Zero.isOne()); + EXPECT_TRUE(One.isOne()); + + EXPECT_TRUE(One.isPositive()); + EXPECT_FALSE(Zero.isPositive()); + + EXPECT_FALSE(Zero.isPowerOfTwo()); + EXPECT_TRUE(One.isPowerOfTwo()); + + EXPECT_TRUE(One.isMultipleOf(One)); + EXPECT_TRUE(Zero.isMultipleOf(One)); + + EXPECT_TRUE(TypeParam(4).isMultipleOf(TypeParam(2))); + EXPECT_FALSE(TypeParam(2).isMultipleOf(TypeParam(4))); +} + +TYPED_TEST(BasicTypes_OffsetTypes, Attributes) { + const auto Zero = TypeParam(0); + const auto One = TypeParam(1); + const auto Negative = TypeParam(-4); + + EXPECT_TRUE(Zero.isZero()); + EXPECT_FALSE(One.isZero()); + + EXPECT_FALSE(Zero.isOne()); + EXPECT_TRUE(One.isOne()); + + EXPECT_TRUE(One.isPositive()); + EXPECT_FALSE(Zero.isPositive()); + EXPECT_FALSE(Negative.isPositive()); + + EXPECT_TRUE(Negative.isNegative()); + EXPECT_FALSE(Zero.isNegative()); + EXPECT_FALSE(One.isNegative()); + + EXPECT_EQ(Negative - One, TypeParam(-5)); +} + +TEST(BasicTypes_BitsAndBytes, Literals) { + EXPECT_EQ(2_bits, Bits(2)); + EXPECT_EQ(16_bytes, Bytes(16)); +} + +TEST(BasicTypes_Bits, BitsOperations) { + EXPECT_EQ(Bits(1).asBytes(), std::nullopt); + EXPECT_EQ(Bits(8).asBytes(), std::optional(Bytes(1))); + EXPECT_EQ(Bits(1).getCoveringBytes(), Bytes(1)); +} + +TEST(BasicTypes_AddressTest_DEATH, Align) { + EXPECT_DEATH_IF_SUPPORTED(Align().previous(), "Undefined operation"); + EXPECT_DEATH_IF_SUPPORTED(Align(1).previous(), "Undefined operation"); +} + +using HostAddressTypes = + ::testing::Types; +template +class BasicTypes_HostAddressTypesTest : public testing::Test {}; +TYPED_TEST_SUITE(BasicTypes_HostAddressTypesTest, HostAddressTypes); + +TYPED_TEST(BasicTypes_HostAddressTypesTest, Alignment) { + EXPECT_TRUE(hostAddress(TypeParam(12)).isAligned(Align())); + EXPECT_TRUE(hostAddress(TypeParam(12)).isAligned(1)); + EXPECT_FALSE(hostAddress(TypeParam(12)).isAligned(32)); + + EXPECT_EQ(hostAddress(TypeParam(0)).alignDown(2), TypeParam(0)); + EXPECT_EQ(hostAddress(TypeParam(2)).alignDown(2), TypeParam(2)); + EXPECT_EQ(hostAddress(TypeParam(3)).alignDown(2), TypeParam(2)); + EXPECT_EQ(hostAddress(TypeParam(4)).alignDown(2), TypeParam(4)); + EXPECT_EQ(hostAddress(TypeParam(15)).alignDown(8), TypeParam(8)); + + EXPECT_EQ(hostAddress(TypeParam(0)).bytesFromPrevAlign(2), Bytes(0)); + EXPECT_EQ(hostAddress(TypeParam(2)).bytesFromPrevAlign(2), Bytes(0)); + EXPECT_EQ(hostAddress(TypeParam(3)).bytesFromPrevAlign(2), Bytes(1)); + EXPECT_EQ(hostAddress(TypeParam(4)).bytesFromPrevAlign(2), Bytes(0)); + EXPECT_EQ(hostAddress(TypeParam(15)).bytesFromPrevAlign(8), Bytes(7)); + + EXPECT_EQ(hostAddress(TypeParam(0)).alignUp(2), TypeParam(0)); + EXPECT_EQ(hostAddress(TypeParam(2)).alignUp(2), TypeParam(2)); + EXPECT_EQ(hostAddress(TypeParam(3)).alignUp(2), TypeParam(4)); + EXPECT_EQ(hostAddress(TypeParam(4)).alignUp(2), TypeParam(4)); + EXPECT_EQ(hostAddress(TypeParam(15)).alignUp(8), TypeParam(16)); + + EXPECT_EQ(hostAddress(TypeParam(0)).bytesToNextAlign(2), Bytes(0)); + EXPECT_EQ(hostAddress(TypeParam(2)).bytesToNextAlign(2), Bytes(0)); + EXPECT_EQ(hostAddress(TypeParam(3)).bytesToNextAlign(2), Bytes(1)); + EXPECT_EQ(hostAddress(TypeParam(4)).bytesToNextAlign(2), Bytes(0)); + EXPECT_EQ(hostAddress(TypeParam(15)).bytesToNextAlign(8), Bytes(1)); +} + +TEST(BasicTypes_HostAddressTest, Types) { + HostAddress(nullptr); + HostAddress(nullptr); + HostAddress(nullptr); + HostAddress(0U); + HostAddress(0U); + HostAddress(0U); + HostAddress(0U); + HostAddress(Bytes(0)); +} + +template +class BasicTypes_TypedTest_DEATH : public testing::Test {}; +TYPED_TEST_SUITE(BasicTypes_TypedTest_DEATH, SizeTypes); + +TYPED_TEST(BasicTypes_TypedTest_DEATH, Units) { + EXPECT_DEATH_IF_SUPPORTED(TypeParam(1).isMultipleOf(TypeParam(0)), + "isMultipleOf\\(0\\) is undefined"); + EXPECT_DEATH_IF_SUPPORTED(TypeParam(1) % 0, + "Modulo operator is undefined for 0"); + EXPECT_DEATH_IF_SUPPORTED(TypeParam(1) % TypeParam(0), + "Modulo operator is undefined for 0"); + EXPECT_DEATH_IF_SUPPORTED(TypeParam(1) - TypeParam(2), + "Substraction underflows"); +} + +TYPED_TEST(BasicTypes_TypedTest_DEATH, PowerOfTwo) { + EXPECT_DEATH_IF_SUPPORTED(PowerOf2(TypeParam(0)), + "Value must be strictly positive"); + EXPECT_DEATH_IF_SUPPORTED(PowerOf2(TypeParam(3)), + "Value is not a power of 2"); + EXPECT_DEATH_IF_SUPPORTED(PowerOf2::ceil(TypeParam(0)), + "Value must be strictly positive"); + EXPECT_DEATH_IF_SUPPORTED(PowerOf2::floor(TypeParam(0)), + "Value must be strictly positive"); + EXPECT_DEATH_IF_SUPPORTED(PowerOf2::fromLogValue(64), + "Exponent too big"); + EXPECT_DEATH_IF_SUPPORTED(PowerOf2(TypeParam(1)).previous(), + "Undefined operation"); + EXPECT_DEATH_IF_SUPPORTED(PowerOf2::fromLogValue(63).next(), + "Exponent too big"); +} + +TEST(BasicTypes_OffsetType_DEATH, ConstructionOverflows) { + constexpr uint64_t MaxAllowed = std::numeric_limits::max(); + EXPECT_EQ(BytesOffset(Bytes(MaxAllowed)), BytesOffset(MaxAllowed)); + EXPECT_EQ(BitsOffset(Bits(MaxAllowed)), BitsOffset(MaxAllowed)); + EXPECT_DEATH_IF_SUPPORTED(BytesOffset(Bytes(MaxAllowed + 1ULL)), "Overflow"); + EXPECT_DEATH_IF_SUPPORTED(BitsOffset(Bits(MaxAllowed + 1ULL)), "Overflow"); +} + +} // namespace llvm diff --git a/llvm/unittests/Support/CMakeLists.txt b/llvm/unittests/Support/CMakeLists.txt --- a/llvm/unittests/Support/CMakeLists.txt +++ b/llvm/unittests/Support/CMakeLists.txt @@ -11,6 +11,7 @@ ARMAttributeParser.cpp ArrayRecyclerTest.cpp Base64Test.cpp + BasicTypesTest.cpp BinaryStreamTest.cpp BLAKE3Test.cpp BlockFrequencyTest.cpp