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,33 +70,23 @@ /// 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); +/// Returns a multiple of A needed to store `SizeIn` bytes. +inline uint64_t alignTo(uint64_t SizeIn, Align A) { + return hostAddress(SizeIn).alignUp(A); } /// If non-zero \p Skew is specified, the return value will be a minimal integer -/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for -/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p -/// Skew mod \p A'. +/// that is greater than or equal to \p SizeIn and equal to \p A * N + \p Skew +/// for some integer N. If \p Skew is larger than \p A, its value is adjusted to +/// '\p Skew mod \p A'. /// /// Examples: /// \code @@ -177,35 +94,34 @@ /// alignTo(17, Align(8), 1) = 17 /// 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; +inline uint64_t alignTo(uint64_t SizeIn, Align A, uint64_t Skew) { + Skew %= A.value(); + return hostAddress(SizeIn - 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 hostAddress(Value) + .bytesToNextAlign(Alignment) + .getUnsafeQuantityRepresentation(); } /// 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 hostAddress(Addr) + .bytesToNextAlign(Alignment) + .getUnsafeQuantityRepresentation(); } /// 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 +130,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(PowOf2Bytes::fromLogValue(Value - 1)); } /// Returns a representation of the alignment, the encoded value is positive by @@ -232,47 +146,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,535 @@ +//===- 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 +// +//===----------------------------------------------------------------------===// +// +// Definitions +// ----------- +// +// - bit : the smallest unit of information. +// - byte : the smallest addressable unit of data storage. +// +// Although it is common to have 8-bit bytes (octet), this file does not define +// an absolute byte width. Conversions between bits and bytes are possible +// through a BitsPerByte type. +// +// Concepts +// -------- +// +// - Quantity : multiplicity or magnitude of a measure. +// - Unit : A C++ struct tag to identify a physical unit. +// - BitUnit +// - ByteUnit +// - Measure : the composition of a Quantity and a Unit. +// - SizeIn : A zero or more number of UnitT (count or size). +// - OffsetIn : A relative quantity of UnitT. +// - PowOf2In : A number of UnitT that is a power of two. +// +// We provide the following aliases and user-defined literals support: +// - Bytes = SizeIn, e.g. 16_bytes or Bytes(16), +// - Bits = SizeIn, e.g. 16_bits or Bits(16), +// - BytesOffset = OffsetIn, e.g. 16_bytes_offset or BytesOffset(16), +// - BitsOffset = OffsetIn, e.g. 16_bits_offset or BitsOffset(16), +// - PowOf2Bytes = PowOf2In, e.g. 16_bytes_pow2 or PowOf2Bytes(16), +// - PowOf2Bits = PowOf2In, e.g. 16_bits_pow2 or PowOf2BitsO(16), +// +// Additionally this file defines the following types: +// - Align : An alignment in bytes represented as a PowOf2Bytes. +// - HostAddress : An address abstraction to align or test for alignment of +// host addresses. T can be a pointer, an unsigned integral or +// SizeIn. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_BASIC_TYPES_H +#define LLVM_SUPPORT_BASIC_TYPES_H + +#include +#include +#include +#include + +#include "llvm/Support/MathExtras.h" + +namespace llvm { + +struct ByteUnit {}; +struct BitUnit {}; + +template struct is_unit : std::false_type {}; +template <> struct is_unit : std::true_type {}; +template <> struct is_unit : std::true_type {}; +template inline constexpr bool is_unit_v = is_unit::value; + +namespace details { + +template struct RawQuantity { + static_assert(std::is_integral_v); + using raw_type = ScalarType; + + /// Default constructor initializing to 0. + constexpr explicit RawQuantity() = default; + /// Explicit constructor initializing to provided Quantity. + constexpr explicit RawQuantity(raw_type Quantity) : Quantity(Quantity) {} + + // Comparison operators. + bool operator==(const RawQuantity &Rhs) const { + return Quantity == Rhs.Quantity; + } + bool operator!=(const RawQuantity &Rhs) const { + return Quantity != Rhs.Quantity; + } + + // Relational operators. + bool operator<(const RawQuantity &Rhs) const { + return Quantity < Rhs.Quantity; + } + bool operator<=(const RawQuantity &Rhs) const { + return Quantity <= Rhs.Quantity; + } + bool operator>(const RawQuantity &Rhs) const { + return Quantity > Rhs.Quantity; + } + bool operator>=(const RawQuantity &Rhs) const { + return Quantity >= Rhs.Quantity; + } + + /// Escape hatch to read the underlying quantity representation. + ScalarType getUnsafeQuantityRepresentation() const { return Quantity; } + +protected: + ScalarType Quantity = 0; +}; + +template +struct ArithmeticQuantity : RawQuantity { + using UP = RawQuantity; + using UP::UP; + using raw_type = typename UP::raw_type; + + /// Returns true if value is zero. + constexpr bool isZero() const { return UP::Quantity == 0; } + /// Returns true if value is one. + constexpr bool isOne() const { return UP::Quantity == 1; } + /// Returns true if value is strictly positive. + constexpr bool isPositive() const { return UP::Quantity > 0; } + /// Returns true if value is strictly negative. + constexpr bool isNegative() const { return UP::Quantity < 0; } + + // Arithmetic operators. + ConcreteT operator+(ConcreteT Rhs) const { + return ConcreteT(UP::Quantity + Rhs.Quantity); + } + ConcreteT operator*(raw_type N) const { return ConcreteT(UP::Quantity * N); } + ConcreteT operator/(raw_type N) const { return ConcreteT(UP::Quantity / N); } + raw_type operator/(ConcreteT Rhs) const { + return UP::Quantity / Rhs.Quantity; + } + void operator+=(raw_type N) { UP::Quantity += N; } + void operator*=(raw_type N) { UP::Quantity *= N; } + void operator/=(raw_type N) { UP::Quantity /= N; } +}; + +} // namespace details + +// BitsPerByte allows conversion between bits and bytes. +struct BitsPerByte : public details::RawQuantity { + using UP = details::RawQuantity; + using UP::UP; + + template friend struct SizeIn; + template friend struct OffsetIn; + template friend struct PowOf2In; +}; + +template +struct SizeIn : public details::ArithmeticQuantity, uint64_t> { + static_assert(is_unit_v, "Invalid Unit"); + using UP = details::ArithmeticQuantity, uint64_t>; + using UP::UP; + using unit_type = UnitT; + using raw_type = typename UP::raw_type; + + /// 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(SizeIn Rhs) const { + assert(!Rhs.isZero() && "isMultipleOf(0) is undefined"); + return (*this % Rhs) == 0; + } + + /// Modulo operator with a scalar value, returns the same type. + SizeIn operator%(raw_type N) const { + assert(N != 0 && "Modulo operator is undefined for 0"); + return SizeIn(UP::Quantity % N); + } + + /// Modulo operator, returns a scalar value. + raw_type operator%(SizeIn Rhs) const { + assert(!Rhs.isZero() && "Modulo operator is undefined for 0"); + return UP::Quantity % Rhs.Quantity; + } + + /// Substract operator between sizes with underflow checking. + SizeIn operator-(SizeIn Rhs) const { + assert(UP::Quantity >= Rhs.Quantity && "Substraction underflows"); + return SizeIn(UP::Quantity - Rhs.Quantity); + } + + /// Converts this value into Bits according to the BitsPerByte argument. + SizeIn asBits(BitsPerByte BPB) const { + static_assert(std::is_same_v); + return SizeIn(UP::Quantity * BPB.Quantity); + } + /// Convert this value in Bytes according to the BitsPerByte argument iff this + /// Quantity is a multiple of BitsPerByte. Returns nullopt otherwise. + std::optional> getWholeBytes(BitsPerByte BPB) const { + static_assert(std::is_same_v); + if (UP::Quantity % BPB.Quantity == 0) + return SizeIn(UP::Quantity / BPB.Quantity); + return std::nullopt; + } + /// Returns the number of Bytes needed to store this number of Bits. + SizeIn getCoveringBytes(BitsPerByte BPB) const { + static_assert(std::is_same_v); + return SizeIn((UP::Quantity + BPB.Quantity - 1) / BPB.Quantity); + } + + template friend struct PowOf2In; + template friend struct OffsetIn; +}; + +using Bits = SizeIn; +using Bytes = SizeIn; + +template +struct OffsetIn : public details::ArithmeticQuantity, int64_t> { + static_assert(is_unit_v, "Invalid Unit"); + using UP = details::ArithmeticQuantity, int64_t>; + using UP::UP; + using unit_type = UnitT; + using raw_type = typename UP::raw_type; + + OffsetIn(const SizeIn &Other) : UP(Other.Quantity) { + assert(Other.Quantity <= + typename SizeIn::raw_type( + std::numeric_limits::max()) && + "Overflow"); + } + + // Substract operator. + OffsetIn operator-(OffsetIn Rhs) const { + return OffsetIn(UP::Quantity - Rhs.Quantity); + } + // Negate operator. + OffsetIn operator-() const { return OffsetIn(-UP::Quantity); } + + /// Converts this value into BitsOffset according to the BitsPerByte argument. + OffsetIn asBits(BitsPerByte BPB) const { + static_assert(std::is_same_v); + return OffsetIn(UP::Quantity * BPB.Quantity); + } + /// Convert this value in BytesOffset according to the BitsPerByte argument + /// iff this Quantity is a multiple of BitsPerByte. Returns nullopt otherwise. + std::optional> getWholeBytes(BitsPerByte BPB) const { + static_assert(std::is_same_v); + if (UP::Quantity % BPB.Quantity == 0) + return OffsetIn(UP::Quantity / BPB.Quantity); + return std::nullopt; + } + /// Returns the offset in Bytes needed to cover this many bits offset. + OffsetIn getCoveringBytes(BitsPerByte BPB) const { + static_assert(std::is_same_v); + const auto Offset = BPB.Quantity - 1; + const auto Adjusted = UP::Quantity + (UP::isNegative() ? -Offset : Offset); + return OffsetIn(Adjusted / BPB.Quantity); + } +}; + +using BitsOffset = OffsetIn; +using BytesOffset = OffsetIn; + +/// Represents a Quantity that is a power of 2. +template struct PowOf2In : details::RawQuantity { + static_assert(is_unit_v, "Invalid Unit"); + using UP = details::RawQuantity; + using unit_type = UnitT; + + /// Default constructor initializing to one. + constexpr PowOf2In() {} + + /// Constructor initializing to provided value. + /// Asserts when value is not a power of two. + constexpr PowOf2In(SizeIn Value) : UP(validate(Value)) {} + + /// Returns true if value is one. + bool isOne() const { return UP::Quantity == 0; } + + /// Returns the value. + SizeIn getValue() const { return SizeIn(1ULL << UP::Quantity); } + + /// Returns the log2 of the value. + /// This is guaranteed to be a number in [0, 63]. + /// e.g. PowOf2In(256).getLogValue() == 8 + auto getLogValue() const { return UP::Quantity; } + + /// Returns the next power of two. + /// Asserts if value becomes greater or equal to 2^64. + auto next() const { return PowOf2In(UP::Quantity + 1); } + + /// Returns the previous power of two. + /// Asserts if current value is one. + auto previous() const { + assert(UP::Quantity != 0 && "Undefined operation"); + return PowOf2In(UP::Quantity - 1); + } + + /// Creates a PowOf2In object from a log quantity. + /// e.g. PowOf2In::fromLogValue(8) == Bytes(256) + /// Asserts if value is greater or equal to 64. + static constexpr PowOf2In fromLogValue(uint8_t LogValue) { + return PowOf2In(LogValue); + } + + /// Returns the the largest PowOf2In not greater than value. + /// e.g. PowOf2In::floor(Bits(2)) == PowOf2In(Bits(2)) + /// e.g. PowOf2In::floor(Bits(3)) == PowOf2In(Bits(2)) + static PowOf2In floor(SizeIn Value) { + assert(Value.isPositive() && "Value must be strictly positive"); + return PowOf2In(llvm::Log2_64(Value.Quantity)); + } + + /// Returns the smallest PowOf2In not less than value. + /// e.g. PowOf2In::ceil(Bits(2)) == PowOf2In(Bits(2)) + /// e.g. PowOf2In::ceil(Bits(3)) == PowOf2In(Bits(4)) + static PowOf2In ceil(SizeIn Value) { + assert(Value.isPositive() && "Value must be strictly positive"); + return floor(Value + SizeIn(1)); + } + +private: + // Makes sure the provided value is a power of two and returns its log2 value. + static uint64_t validate(SizeIn 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 PowOf2In(uint8_t LogValue) : UP(LogValue) { + assert(LogValue < 64 && "Exponent too big"); + } +}; + +using PowOf2Bits = PowOf2In; +using PowOf2Bytes = PowOf2In; + +/// 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() : Pow2Bytes() {} + constexpr Align(PowOf2Bytes Pow) : Pow2Bytes(Pow) {} + constexpr Align(Bytes Value) : Align(PowOf2Bytes(Value)) {} + constexpr Align(uint64_t Value) : Align(Bytes(Value)) {} + + /// Returns true if value is one. + bool isOne() const { return Pow2Bytes.isOne(); } + + // Comparison operators. + bool operator==(Align Other) const { return Pow2Bytes == Other.Pow2Bytes; } + bool operator!=(Align Other) const { return Pow2Bytes != Other.Pow2Bytes; } + + // Relational operators. + bool operator<(Align Other) const { return Pow2Bytes < Other.Pow2Bytes; } + bool operator<=(Align Other) const { return Pow2Bytes <= Other.Pow2Bytes; } + bool operator>(Align Other) const { return Pow2Bytes > Other.Pow2Bytes; } + bool operator>=(Align Other) const { return Pow2Bytes >= Other.Pow2Bytes; } + + // Returns the previous alignment. + // i.e. Align(32).previous() == Align(16) + Align previous() const { + assert(Pow2Bytes != PowOf2Bytes() && "Undefined operation"); + return Pow2Bytes.previous(); + } + + // Returns the alignment as bytes. + Bytes getBytes() const { return Pow2Bytes.getValue(); } + + // Returns the number of trailing zero bits. + Bits getTrailingZeroBits() const { return Bits(Pow2Bytes.getLogValue()); } + + // Returns the alignment as a power of two of bytes. + PowOf2Bytes getPowerOf2Bytes() const { return Pow2Bytes; } + + /// Allow constructions of constexpr Align. + template constexpr static Align Constant() { + return PowOf2Bytes::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 getBytes().getUnsafeQuantityRepresentation(); + } + +private: + PowOf2Bytes Pow2Bytes; +}; + +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 Value.getUnsafeQuantityRepresentation(); } + static T out(type Value) { return Bytes(Value); } +}; + +template struct BitwiseOp { + static_assert(std::is_unsigned::value, "Expected unsigned type"); + static constexpr Bits kBits = Bits(sizeof(T) * CHAR_BIT); + + static T clearLowBits(T Value, Bits Count) { + if (Count >= kBits) + return T(0); + Value &= maskTrailingZeros(Count.getUnsafeQuantityRepresentation()); + return Value; + } + + static T clearHighBits(T Value, Bits Count) { + if (Count >= kBits) + return T(0); + Value &= maskLeadingZeros(Count.getUnsafeQuantityRepresentation()); + return Value; + } + + static T keepLowBits(T Value, Bits Count) { + if (Count < kBits) + Value &= maskTrailingOnes(Count.getUnsafeQuantityRepresentation()); + return Value; + } + + static T keepHighBits(T Value, Bits Count) { + if (Count < kBits) + Value &= maskLeadingOnes(Count.getUnsafeQuantityRepresentation()); + return Value; + } +}; + +} // 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, ByteUnit, + void>>>; + static_assert(!std::is_same::value, + "HostAddress can only be constructed from pointers, unsigned " + "integer or SizeIn"); + 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 = A.getBytes().getUnsafeQuantityRepresentation() - 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); } +inline BytesOffset operator""_bytes_offset(unsigned long long int v) { + return BytesOffset(v); +} +inline BitsOffset operator""_bits_offset(unsigned long long int v) { + return BitsOffset(v); +} +inline PowOf2Bytes operator""_bytes_powof2(unsigned long long int v) { + return PowOf2Bytes(SizeIn(v)); +} +inline PowOf2Bits operator""_bits_powof2(unsigned long long int v) { + return PowOf2Bits(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,325 @@ +//===- 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(DefaultValue.getUnsafeQuantityRepresentation(), 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) { + using unit_type = typename TypeParam::unit_type; + const auto A = PowOf2In(TypeParam(1)); + const auto B = PowOf2In(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) { + using unit_type = typename TypeParam::unit_type; + for (int64_t I = 0; I < 8; ++I) { + auto Value = TypeParam(1ULL << I); + EXPECT_EQ(PowOf2In(Value).getLogValue(), I); + } +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoValue) { + using unit_type = typename TypeParam::unit_type; + for (int64_t I = 0; I < 8; ++I) { + auto Value = TypeParam(1ULL << I); + EXPECT_EQ(PowOf2In(Value).getValue(), Value); + } +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoNext) { + using unit_type = typename TypeParam::unit_type; + for (int64_t I = 0; I < 8; ++I) { + auto Value = TypeParam(1ULL << I); + auto Next = TypeParam(1ULL << (I + 1)); + EXPECT_EQ(PowOf2In(Value).next().getValue(), Next); + } +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoPrevious) { + using unit_type = typename TypeParam::unit_type; + for (int64_t I = 0; I < 8; ++I) { + auto Previous = TypeParam(1ULL << I); + auto Value = TypeParam(1ULL << (I + 1)); + EXPECT_EQ(PowOf2In(Value).previous().getValue(), Previous); + } +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoFloor) { + using unit_type = typename TypeParam::unit_type; + EXPECT_EQ(PowOf2In::floor(TypeParam(2)), + PowOf2In(TypeParam(2))); + EXPECT_EQ(PowOf2In::floor(TypeParam(3)), + PowOf2In(TypeParam(2))); + EXPECT_EQ(PowOf2In::floor(TypeParam(4)), + PowOf2In(TypeParam(4))); +} + +TYPED_TEST(BasicTypes_Sizes, PowerOfTwoCeil) { + using unit_type = typename TypeParam::unit_type; + EXPECT_EQ(PowOf2In::ceil(TypeParam(2)), + PowOf2In(TypeParam(2))); + EXPECT_EQ(PowOf2In::ceil(TypeParam(3)), + PowOf2In(TypeParam(4))); + EXPECT_EQ(PowOf2In::ceil(TypeParam(4)), + PowOf2In(TypeParam(4))); +} + +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, Arithmetic) { + EXPECT_EQ(TypeParam(1) - TypeParam(2), TypeParam(-1)); + EXPECT_EQ(-TypeParam(1), TypeParam(-1)); +} + +TYPED_TEST(BasicTypes_SizesAndOffsets, 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_FALSE(Zero.isPositive()); + EXPECT_TRUE(One.isPositive()); + + EXPECT_FALSE(Zero.isNegative()); + EXPECT_FALSE(One.isNegative()); +} + +TYPED_TEST(BasicTypes_Sizes, Attributes) { + const auto Zero = TypeParam(0); + const auto One = TypeParam(1); + + 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(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) { + const BitsPerByte BPB(8); + // Size + EXPECT_EQ(Bytes(0).asBits(BPB), Bits(0)); + EXPECT_EQ(Bytes(1).asBits(BPB), Bits(8)); + EXPECT_EQ(Bytes(2).asBits(BPB), Bits(16)); + EXPECT_EQ(Bits(0).getWholeBytes(BPB), std::make_optional(Bytes(0))); + EXPECT_EQ(Bits(1).getWholeBytes(BPB), std::nullopt); + EXPECT_EQ(Bits(8).getWholeBytes(BPB), std::make_optional(Bytes(1))); + EXPECT_EQ(Bits(0).getCoveringBytes(BPB), Bytes(0)); + EXPECT_EQ(Bits(1).getCoveringBytes(BPB), Bytes(1)); + EXPECT_EQ(Bits(8).getCoveringBytes(BPB), Bytes(1)); + EXPECT_EQ(Bits(9).getCoveringBytes(BPB), Bytes(2)); + // Offset + EXPECT_EQ(BytesOffset(0).asBits(BPB), BitsOffset(0)); + EXPECT_EQ(BytesOffset(1).asBits(BPB), BitsOffset(8)); + EXPECT_EQ(BytesOffset(-1).asBits(BPB), BitsOffset(-8)); + EXPECT_EQ(BitsOffset(1).getWholeBytes(BPB), std::nullopt); + EXPECT_EQ(BitsOffset(-8).getWholeBytes(BPB), + std::make_optional(BytesOffset(-1))); + EXPECT_EQ(BitsOffset(0).getCoveringBytes(BPB), BytesOffset(0)); + EXPECT_EQ(BitsOffset(1).getCoveringBytes(BPB), BytesOffset(1)); + EXPECT_EQ(BitsOffset(8).getCoveringBytes(BPB), BytesOffset(1)); + EXPECT_EQ(BitsOffset(-1).getCoveringBytes(BPB), BytesOffset(-1)); + EXPECT_EQ(BitsOffset(-9).getCoveringBytes(BPB), BytesOffset(-2)); +} + +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) { + using unit_type = typename TypeParam::unit_type; + EXPECT_DEATH_IF_SUPPORTED(PowOf2In(TypeParam(0)), + "Value must be strictly positive"); + EXPECT_DEATH_IF_SUPPORTED(PowOf2In(TypeParam(3)), + "Value is not a power of 2"); + EXPECT_DEATH_IF_SUPPORTED(PowOf2In::ceil(TypeParam(0)), + "Value must be strictly positive"); + EXPECT_DEATH_IF_SUPPORTED(PowOf2In::floor(TypeParam(0)), + "Value must be strictly positive"); + EXPECT_DEATH_IF_SUPPORTED(PowOf2In::fromLogValue(64), + "Exponent too big"); + EXPECT_DEATH_IF_SUPPORTED(PowOf2In(TypeParam(1)).previous(), + "Undefined operation"); + EXPECT_DEATH_IF_SUPPORTED(PowOf2In::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 @@ -12,6 +12,7 @@ ARMAttributeParser.cpp ArrayRecyclerTest.cpp Base64Test.cpp + BasicTypesTest.cpp BinaryStreamTest.cpp BLAKE3Test.cpp BlockFrequencyTest.cpp