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,277 @@ +//===- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_UNITS_H +#define LLVM_SUPPORT_UNITS_H + +#include +#include +#include + +#include "llvm/ADT/Optional.h" +#include "llvm/Support/MathExtras.h" + +namespace llvm { + +struct UnitTag { + static constexpr bool is_unit_tag = true; +}; +struct ByteTag : public UnitTag {}; +struct BitTag : public UnitTag {}; + +// Bits and Bytes base implementation. +template struct Quantity { + static_assert(UnitTagType::is_unit_tag, "Unexpected UnitTagType"); + static constexpr bool is_quantity = true; + + constexpr explicit Quantity(ScalarType value) : value(value) {} + + bool isZero() const { return value == 0; } + bool isOne() const { return value == 1; } + bool isPositive() const { return value > 0; } + bool isNegative() const { return value < 0; } + bool isPowerOfTwo() const { return value && (value & -value) == value; } + bool isMultipleOf(Quantity Q) const { + assert(!Q.isZero() && "isMultipleOf(0) is undefined"); + return (*this % Q) == 0; + } + + // Comparison operators. + bool operator==(Quantity Q) const { return value == Q.value; } + bool operator!=(Quantity Q) const { return value != Q.value; } + + // Relational operators. + bool operator<(Quantity Q) const { return value < Q.value; } + bool operator<=(Quantity Q) const { return value <= Q.value; } + bool operator>(Quantity Q) const { return value > Q.value; } + bool operator>=(Quantity Q) const { return value >= Q.value; } + + // Arithmetic operators. + Quantity operator+(Quantity Q) const { return Quantity(value + Q.value); } + Quantity operator-(Quantity Q) const { return Quantity(value - Q.value); } + Quantity operator-() const { return Quantity(-value); } + Quantity operator*(ScalarType N) const { return Quantity(value * N); } + Quantity &operator*=(ScalarType N) { + value *= N; + return *this; + } + Quantity operator/(ScalarType N) const { return Quantity(value / N); } + Quantity &operator/=(ScalarType N) { + value /= N; + return *this; + } + ScalarType operator/(Quantity Q) const { return value / Q.value; } + + Quantity operator%(ScalarType N) const { + assert(N != 0 && "Modulo operator is undefined for 0"); + return Quantity(value % N); + } + ScalarType operator%(Quantity Q) const { + assert(!Q.isZero() && "Modulo operator is undefined for 0"); + return value % Q.value; + } + +protected: + ScalarType value = 0; +}; + +template struct PowerOf2 { + static_assert(Quantity::is_quantity, "Unexpected Quantity"); + + constexpr PowerOf2(Quantity Q) : PowerOf2(validate(Q)) {} + + // Comparison operators. + bool operator==(PowerOf2 Q) const { return logValue == Q.logValue; } + bool operator!=(PowerOf2 Q) const { return logValue != Q.logValue; } + + // Relational operators. + bool operator<(PowerOf2 Q) const { return logValue < Q.logValue; } + bool operator<=(PowerOf2 Q) const { return logValue <= Q.logValue; } + bool operator>(PowerOf2 Q) const { return logValue > Q.logValue; } + bool operator>=(PowerOf2 Q) const { return logValue >= Q.logValue; } + + // Cast operator to recover the underlying Quantity. + operator Quantity() const { return Quantity(1ULL << logValue); } + + // Returns the log valus of this power of two. + // e.g. PowerOfTwo(256).logValue() == 8 + auto getLogValue() const { return logValue; } + + // Returns the next power of two. + auto next() const { return PowerOf2(logValue + 1); } + + // Returns the previous power of two. + auto previous() const { + assert(logValue != 0 && "Undefined operation"); + return PowerOf2(logValue - 1); + } + + // Creates a PowerOfTwo object from a log value. + // e.g. PowerOfTwo::fromLogValue(8) == Bytes(256) + static PowerOf2 fromLogValue(uint8_t logValue) { return PowerOf2(logValue); } + + // Returns a PowerOfTwo object that covers the given quantity. + // e.g. PowerOfTwo::getCovering(Bits(3)) == PowerOfTwo(Bits(4)) + static PowerOf2 getCovering(Quantity Q) { + assert(Q.isPositive() && "Quantity must be strictly positive"); + return PowerOf2(llvm::Log2_64(Q.value)).next(); + } + +private: + static uint64_t validate(Quantity Q) { + assert(Q.isPositive() && "Quantity must be strictly positive"); + assert(Q.isPowerOfTwo() && "Quantity is not a power of 2"); + return llvm::Log2_64(Q.value); + } + + constexpr PowerOf2() {} + constexpr PowerOf2(uint8_t logValue) : logValue(logValue) { + assert(logValue < 64 && "Exponent too big"); + } + + uint8_t logValue = 0; + + friend struct Align; +}; + +struct Bytes : public Quantity { + using Quantity::Quantity; + friend struct Bits; + friend struct Address; + friend struct Align; + + friend Bytes operator+(Bytes a, Bytes b); + friend auto getUnsafeRawQuantity(Bytes); + template friend struct PowerOf2; +}; + +struct Bits : public Quantity { + constexpr Bits(Bytes B) : Quantity(B.value * 8) {} + constexpr Bits(decltype(value) B) : Quantity(B) {} + + llvm::Optional asBytes() const { + if (isMultipleOf(Bits(8))) + return Bytes(value / 8); + return {}; + } + + Bytes getCoveringBytes() const { return Bytes((value + 7) / 8); } + + friend Bits operator+(Bits a, Bits b); + friend auto getUnsafeRawQuantity(Bits); + template friend struct PowerOf2; +}; + +inline Bytes operator+(Bytes a, Bytes b) { return Bytes(a.value + b.value); } +inline Bits operator+(Bits a, Bits b) { return Bits(a.value + b.value); } + +inline auto getUnsafeRawQuantity(Bits bits) { return bits.value; } +inline auto getUnsafeRawQuantity(Bytes bytes) { return bytes.value; } + +struct Align : public PowerOf2 { + constexpr Align() : PowerOf2() {} + constexpr Align(Bytes Q) : PowerOf2(Q) {} + constexpr Align(uint64_t Value) : Align(Bytes(Value)) {} +}; + +struct Address; // Forward declaration for friendship declaration in Mask. + +namespace internal { + +// For now, we keep Mask as an implementation detail but if it deems useful for +// the codebase it can be exposed. + +template +struct Mask : private Quantity { + static_assert(std::is_integral::value && + std::is_unsigned::value, + "ScalarType must be an unsigned integral type"); + Mask() : Quantity(0) {} + Mask(ScalarType value) : Quantity(value) {} + + static Mask allOnes() { return Mask(~0); } + static Mask from(Align AL) { + if (AL.getLogValue() == 0) + return {}; + return allOnes() >> (max_bits - AL.getLogValue()); + } + + Mask operator>>(size_t shift) const { + assert(shift < max_bits && "Shift operand too large is undefined behavior"); + return Mask(this->value >> shift); + } + Mask operator<<(size_t shift) const { + assert(shift < max_bits && "Shift operand too large is undefined behavior"); + return Mask(this->value << shift); + } + Mask operator~() const { return Mask(~this->value); } + + // Comparison operators. + bool operator==(Mask M) const { return this->value == M.value; } + bool operator!=(Mask M) const { return this->value != M.value; } + +private: + static constexpr size_t max_bits = sizeof(ScalarType) * 8; + friend struct llvm::Address; + friend auto getUnsafeRawQuantity(Mask); +}; + +} // namespace internal + +struct Address : private Quantity { + using Mask = internal::Mask; + + Address() : Quantity(0) {} + Address(uintptr_t ptr) : Quantity(ptr) {} + Address(Bytes byte) : Quantity(byte.value) {} + + bool isAligned(Align AL) const { + return isMultipleOf(Address(static_cast(AL))); + } + Address alignDown(Align AL) const { return *this & ~Mask::from(AL); } + Address alignUp(Align AL) const { return alignDown(AL) + AL; } + + Address operator+(Bytes offset) const { + return Address(value + offset.value); + } + Address operator-(Bytes offset) const { + return Address(value - offset.value); + } + Address operator+=(Bytes offset) { + value += offset.value; + return *this; + } + Address operator-=(Bytes offset) { + value -= offset.value; + return *this; + } + + // Comparison operators. + bool operator==(Address Q) const { return value == Q.value; } + bool operator!=(Address Q) const { return value != Q.value; } + + // Relational operators. + bool operator<(Address Q) const { return value < Q.value; } + bool operator<=(Address Q) const { return value <= Q.value; } + bool operator>(Address Q) const { return value > Q.value; } + bool operator>=(Address Q) const { return value >= Q.value; } + +private: + Address operator&(Mask mask) const { return Address(value & mask.value); } + Address operator|(Mask mask) const { return Address(value | mask.value); } + friend auto getUnsafeRawQuantity(Address); +}; + +inline auto getUnsafeRawQuantity(Address address) { return address.value; } + +inline Bytes operator""_bytes(unsigned long long v) { return Bytes(v); } +inline Bits operator""_bits(unsigned long long v) { return Bits(v); } + +} // namespace llvm + +#endif /* LLVM_SUPPORT_UNITS_H */ 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,267 @@ +//===- 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 UnitTypes = ::testing::Types; +template class BasicTypes_TypedTest : public testing::Test {}; +TYPED_TEST_SUITE(BasicTypes_TypedTest, UnitTypes); + +TYPED_TEST(BasicTypes_TypedTest, 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_TypedTest, PowerOfTwoLogValue) { + for (int64_t I = 0; I < 8; ++I) { + auto Value = TypeParam(1ULL << I); + EXPECT_EQ(PowerOf2(Value).getLogValue(), I); + } +} + +TYPED_TEST(BasicTypes_TypedTest, PowerOfTwoCast) { + for (int64_t I = 0; I < 8; ++I) { + auto Value = TypeParam(1ULL << I); + EXPECT_EQ(static_cast(PowerOf2(Value)), Value); + } +} + +TYPED_TEST(BasicTypes_TypedTest, 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_TypedTest, 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_TypedTest, getCovering) { + EXPECT_EQ(PowerOf2::getCovering(TypeParam(3)), + PowerOf2(TypeParam(4))); +} + +TYPED_TEST(BasicTypes_TypedTest, Arithmetic) { + EXPECT_EQ(TypeParam(1) + TypeParam(2), TypeParam(3)); + EXPECT_EQ(TypeParam(1) - TypeParam(2), TypeParam(-1)); + EXPECT_EQ(-TypeParam(1), TypeParam(-1)); + + EXPECT_EQ(TypeParam(1) * 2, TypeParam(2)); + EXPECT_EQ(TypeParam(1) *= 2, TypeParam(2)); + + EXPECT_EQ(TypeParam(2) / 2, TypeParam(1)); + EXPECT_EQ(TypeParam(2) /= 2, TypeParam(1)); + EXPECT_EQ(TypeParam(2) / TypeParam(2), 1); + + EXPECT_EQ(TypeParam(8) % 2, TypeParam(0)); + EXPECT_EQ(TypeParam(8) % TypeParam(2), 0); +} + +TYPED_TEST(BasicTypes_TypedTest, Attributes) { + const auto Zero = TypeParam(0); + const auto One = TypeParam(1); + const auto Negative = TypeParam(-5); + + 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_FALSE(Negative.isPowerOfTwo()); + 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))); +} + +TEST(BasicTypes_BitsAndBytes, Literals) { + EXPECT_EQ(2_bits, Bits(2)); + EXPECT_EQ(16_bytes, Bytes(16)); +} + +TEST(BasicTypes_BitsAndBytes, MixedTypeAddition) { + EXPECT_EQ(Bytes(1) + Bits(1), Bits(9)); + EXPECT_EQ(Bits(1) + Bytes(1), Bits(9)); +} + +TEST(BasicTypes_Bits, BitsOperations) { + EXPECT_EQ(Bits(1).asBytes(), llvm::None); + EXPECT_EQ(Bits(8).asBytes(), llvm::Optional(Bytes(1))); + EXPECT_EQ(Bits(1).getCoveringBytes(), Bytes(1)); +} + +template using Mask = internal::Mask; + +TEST(BasicTypes_MaskTest, ShiftZero) { + EXPECT_EQ(Mask(0b1) >> 0, Mask(0b1)); + EXPECT_EQ(Mask(0b1) << 0, Mask(0b1)); +} + +TEST(BasicTypes_MaskTest, ShiftOne) { + EXPECT_EQ(Mask(0b10) >> 1, Mask(0b1)); + EXPECT_EQ(Mask(0b10) << 1, Mask(0b100)); +} + +TEST(BasicTypes_MaskTest, ShiftNegate) { + EXPECT_EQ(~Mask(0x02), Mask(0xFD)); + EXPECT_EQ(~Mask(0x02), Mask(0xFFFD)); + EXPECT_EQ(~Mask(0x02), Mask(0xFFFFFFFD)); + EXPECT_EQ(~Mask(0x02), Mask(0xFFFFFFFFFFFFFFFD)); +} + +TEST(BasicTypes_MaskTest, FromAlign) { + EXPECT_EQ(Mask::from(Align(Bytes(32))), Mask(0b11111)); + EXPECT_EQ(Mask::from(Align(Bytes(8))), Mask(0b111)); + EXPECT_EQ(Mask::from(Align(Bytes(1))), Mask(0b0)); +} + +TEST(BasicTypes_MaskTest_DEATH, UndefinedShifts) { + EXPECT_DEATH_IF_SUPPORTED(Mask() << 8, + "Shift operand too large is undefined behavior"); + EXPECT_DEATH_IF_SUPPORTED(Mask() >> 8, + "Shift operand too large is undefined behavior"); + EXPECT_DEATH_IF_SUPPORTED(Mask() << 16, + "Shift operand too large is undefined behavior"); + EXPECT_DEATH_IF_SUPPORTED(Mask() >> 16, + "Shift operand too large is undefined behavior"); + EXPECT_DEATH_IF_SUPPORTED(Mask() << 32, + "Shift operand too large is undefined behavior"); + EXPECT_DEATH_IF_SUPPORTED(Mask() >> 32, + "Shift operand too large is undefined behavior"); + EXPECT_DEATH_IF_SUPPORTED(Mask() << 64, + "Shift operand too large is undefined behavior"); + EXPECT_DEATH_IF_SUPPORTED(Mask() >> 64, + "Shift operand too large is undefined behavior"); +} + +TEST(BasicTypes_AddressTest, Initialization) { + EXPECT_EQ(Address(), Address(uintptr_t(0))); + EXPECT_EQ(Address() + 1_bytes, Address(1)); +} + +TEST(BasicTypes_AddressTest, Arithmetic) { + uintptr_t NullUintPtr = 0; + + EXPECT_EQ(Address(NullUintPtr) + 1_bytes, Address(1)); + EXPECT_EQ(Address(NullUintPtr) - 1_bytes, Address(uintptr_t(~0))); + + EXPECT_EQ(Address(NullUintPtr) += 1_bytes, Address(1)); + EXPECT_EQ(Address(NullUintPtr) -= 1_bytes, Address(uintptr_t(~0))); +} + +TEST(BasicTypes_AddressTest, Alignment) { + const auto Addr0 = Address(uintptr_t(0)); + EXPECT_EQ(Addr0.alignDown(Bytes(8)), Addr0); + EXPECT_EQ(Addr0.alignUp(Bytes(8)), Address(uintptr_t(8))); + + const auto Addr12 = Address(uintptr_t(12)); + EXPECT_TRUE(Addr12.isAligned(Align())); + + // Align is implictly constructible from Bytes. + EXPECT_TRUE(Addr12.isAligned(Bytes(1))); + EXPECT_FALSE(Addr12.isAligned(Bytes(32))); + + EXPECT_EQ(Addr12.alignDown(Bytes(32)), Addr0); + EXPECT_EQ(Addr12.alignUp(Bytes(32)), Address(uintptr_t(32))); + + EXPECT_EQ(Addr12.alignDown(Bytes(8)), Address(uintptr_t(8))); + EXPECT_EQ(Addr12.alignUp(Bytes(8)), Address(uintptr_t(16))); + + // Align is implictly constructible from integral uint64_t so all of the above + // can be simplified. + EXPECT_TRUE(Addr12.isAligned(1)); + EXPECT_FALSE(Addr12.isAligned(32)); + EXPECT_EQ(Addr12.alignDown(32), Addr0); + EXPECT_EQ(Addr12.alignUp(32), Address(32ULL)); + EXPECT_EQ(Addr12.alignDown(8), Address(8ULL)); + EXPECT_EQ(Addr12.alignUp(8), Address(16ULL)); +} + +template +class BasicTypes_TypedTest_DEATH : public testing::Test {}; +TYPED_TEST_SUITE(BasicTypes_TypedTest_DEATH, UnitTypes); + +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"); +} + +TYPED_TEST(BasicTypes_TypedTest_DEATH, PowerOfTwo) { + EXPECT_DEATH_IF_SUPPORTED(PowerOf2(TypeParam(-1)), + "Quantity must be strictly positive"); + EXPECT_DEATH_IF_SUPPORTED(PowerOf2(TypeParam(0)), + "Quantity must be strictly positive"); + EXPECT_DEATH_IF_SUPPORTED(PowerOf2(TypeParam(3)), + "Quantity is not a power of 2"); + EXPECT_DEATH_IF_SUPPORTED(PowerOf2::getCovering(TypeParam(0)), + "Quantity 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"); +} + +} // namespace llvm \ No newline at end of file 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