[libc][mem*] Address facility + test enum support

[gchatelet]

Summary

This patch is a subpart of D125768 intented to make the review easier.

The Address struct represents a pointer but also adds compile time knowledge
like alignment or temporal/non-temporal that helps with downstream instruction
selection.

[courbet]

libc/src/string/memory_utils/address.h

25

DeferredStaticAssert for consistency ? Note that as duscussed offline, I would much rather prefer consistency with c++, i.e. renaming everything to cpp::conditional_t instead of cpp:ConditionalType.

32

"specifying" ? (here and below).

34

I would call this Temporality { TEMPORAL, NONTEMPORAL}. Else AddrT::TEMPORAL reads as "a temporal address" rather than "the temporality of the Address type AddrT".

48

Not a big fan of this, because this is spoofable: struct SomeOtherType { static constexpr bool IS_ADDRESS_TYPE = true; };. Is this on purpose ? Else I think template <typename T> IsAddressType { constexpr bool value = false; }; + specialization would be better.

54

PointeeType ? I could see ValueType being ubyte* or ubyte. Using Pointee makes it non-ambiguous.

55

VoidType ?

67

Maybe mention that this is not UB because value_type is a character type ? This triggers alarms in my brain :)

75

The doc should mention whether the offsets are in bytes or multiple of alignment. As of now I have to read the code to figure out.

77

I don't understand why an address offset by AddrT::ALIGNMENT+1 should be AddrT::ALIGNMENT-aligned. is this missing a static_assert(Offset <= AddrT::ALIGNMENT) ?

90

(in bytes)

95

ditto

[gchatelet]

• Address comments

[courbet]

libc/src/string/memory_utils/address.h

75

This is suboptimal for ALIGNMENT=8 and ByteOffset=6, which has ByteOffsetModuloAlignment=6, and therefore returns 1 instead of 2.

libc/test/src/string/memory_utils/address_test.cpp

48

ASSERT_EQ(offsetAddr<6>(SrcAddr<8>(nullptr)).ALIGNMENT, 2UL); ?

[gchatelet]

• Use a more principled approach to common alignment

[gchatelet]

• Simplify gcd in address

libc/src/__support/CPP/TypeTraits.h

 #define LLVM_LIBC_SRC_SUPPORT_CPP_TYPETRAITS_H
 
 #include "UInt.h"
 
 namespace __llvm_libc {
 namespace cpp {
 
 template <bool B, typename T> struct EnableIf;
-template <typename T> struct EnableIf<true, T> { typedef T Type; };
+template <typename T> struct EnableIf<true, T> {
+  typedef T Type;
+};
 
 template <bool B, typename T>
 using EnableIfType = typename EnableIf<B, T>::Type;
 
 struct TrueValue {
   static constexpr bool Value = true;
 };
 
 struct FalseValue {
   static constexpr bool Value = false;
 };
 
-template <typename T> struct TypeIdentity { typedef T Type; };
+template <typename T> struct TypeIdentity {
+  typedef T Type;
+};
 
 template <typename T1, typename T2> struct IsSame : public FalseValue {};
 template <typename T> struct IsSame<T, T> : public TrueValue {};
 template <typename T1, typename T2>
 static constexpr bool IsSameV = IsSame<T1, T2>::Value;
 
 template <typename T> struct RemoveCV : public TypeIdentity<T> {};
 template <typename T> struct RemoveCV<const T> : public TypeIdentity<T> {};
static constexpr bool Value =
       IsSameV<unsigned long long, TypeNoCV> || IsSameV<bool, TypeNoCV> ||
       IsSameV<UInt<128>, TypeNoCV>
 #ifdef __SIZEOF_INT128__
       || IsSameV<__uint128_t, TypeNoCV> || IsSameV<__int128_t, TypeNoCV>
 #endif
       ;
 };
 
+template <typename Type> struct IsEnum {
+  static constexpr bool Value = __is_enum(Type);
+};
+
 template <typename T> struct IsPointerTypeNoCV : public FalseValue {};
 template <typename T> struct IsPointerTypeNoCV<T *> : public TrueValue {};
 template <typename T> struct IsPointerType {
   static constexpr bool Value = IsPointerTypeNoCV<RemoveCVType<T>>::Value;
 };
 
 template <typename Type> struct IsFloatingPointType {
   using TypeNoCV = RemoveCVType<Type>;
   static constexpr bool Value = IsSame<float, TypeNoCV>::Value ||
                                 IsSame<double, TypeNoCV>::Value ||
                                 IsSame<long double, TypeNoCV>::Value;
 };
 
 template <typename Type> struct IsArithmetic {
   static constexpr bool Value =
       IsIntegral<Type>::Value || IsFloatingPointType<Type>::Value;
 };
 
+// Compile time type selection.
+template <bool _, class TrueT, class FalseT> struct Conditional {
+  using type = TrueT;
+};
+template <class TrueT, class FalseT> struct Conditional<false, TrueT, FalseT> {
+  using type = FalseT;
+};
+template <bool Cond, typename TrueT, typename FalseT>
+using ConditionalType = typename Conditional<Cond, TrueT, FalseT>::type;
+
 } // namespace cpp
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_SUPPORT_CPP_TYPETRAITS_H

libc/src/string/memory_utils/address.h

+//===-- Strongly typed address with alignment and access semantics --------===//
+//
+// 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_LIBC_SRC_STRING_MEMORY_UTILS_COMMON_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_COMMON_H
+
+#include "src/__support/CPP/TypeTraits.h"  // cpp::ConditionalType
+#include "src/string/memory_utils/utils.h" // is_power2
+#include <stddef.h>                        // size_t
+#include <stdint.h> // uint8_t, uint16_t, uint32_t, uint64_t
+
+namespace __llvm_libc {
+
+// Utility to enable static_assert(false) in templates.
+template <bool flag = false> static void DeferredStaticAssert(const char *msg) {
+  static_assert(flag, "compilation error");
+}
+
+// A non-coercible type to represent raw data.
+enum class ubyte : unsigned char { ZERO = 0 };
+
+// Address attribute specifying whether the underlying load / store operations
+// are temporal or non-temporal.
+enum class Temporality { TEMPORAL, NON_TEMPORAL };
+
+// Address attribute specifying whether the underlying load / store operations
+// are aligned or unaligned.
+enum class Aligned { NO, YES };
+
+// Address attribute to discriminate between readable and writable addresses.
+enum class Permission { Read, Write };
+
+// Address is semantically equivalent to a pointer but also conveys compile time
+// information that helps with instructions selection (aligned/unaligned,
+// temporal/non-temporal).
+template <size_t Alignment, Permission P, Temporality TS> struct Address {
+  static_assert(is_power2(Alignment));
+  static constexpr size_t ALIGNMENT = Alignment;
+  static constexpr Permission PERMISSION = P;
+  static constexpr Temporality TEMPORALITY = TS;
+  static constexpr bool IS_READ = P == Permission::Read;
+  static constexpr bool IS_WRITE = P == Permission::Write;
+  using PointeeType = cpp::ConditionalType<!IS_WRITE, const ubyte, ubyte>;
+  using VoidType = cpp::ConditionalType<!IS_WRITE, const void, void>;
+
+  Address(VoidType *ptr) : ptr_(reinterpret_cast<PointeeType *>(ptr)) {}
+
+  PointeeType *ptr() const {
+    return reinterpret_cast<PointeeType *>(
+        __builtin_assume_aligned(ptr_, ALIGNMENT));
+  }
+
+  PointeeType *const ptr_;
+
+  template <size_t ByteOffset> auto offset(size_t byte_offset) const {
+    static constexpr size_t NewAlignment = commonAlign<ByteOffset>();
+    return Address<NewAlignment, PERMISSION, TEMPORALITY>(ptr_ + byte_offset);
+  }
+
+private:
+  template <size_t ByteOffset> static constexpr size_t commonAlign() {
+    constexpr size_t GCD = gcd<ByteOffset, ALIGNMENT>();
+    if constexpr (is_power2(GCD))
+      return GCD;
+    else
+      return 1;
+  }
+
+  template <size_t A, size_t B> static constexpr size_t gcd() {
+    if constexpr (B == 0)
+      return A;
+    else
+      return gcd<B, A % B>();
+  }
+};
+
+template <typename T> struct IsAddressType : public cpp::FalseValue {};
+template <size_t Alignment, Permission P, Temporality TS>
+struct IsAddressType<Address<Alignment, P, TS>> : public cpp::TrueValue {};
+
+// Reinterpret the address as a pointer to T.
+// This is not UB since the underlying pointer always refers to a `char` in a
+// buffer of raw data.
+template <typename T, typename AddrT> static T *as(AddrT addr) {
+  static_assert(IsAddressType<AddrT>::Value);
+  return reinterpret_cast<T *>(addr.ptr());
+}
+
+// Offsets the address by a compile time amount, this allows propagating
+// alignment whenever possible.
+template <size_t ByteOffset, typename AddrT>
+static auto offsetAddr(AddrT addr) {
+  static_assert(IsAddressType<AddrT>::Value);
+  return addr.template offset<ByteOffset>(ByteOffset);
+}
+
+// Offsets the address by a runtime amount but assuming that the resulting
+// address will be Alignment aligned.
+template <size_t Alignment, typename AddrT>
+static auto offsetAddrAssumeAligned(AddrT addr, size_t byte_offset) {
+  static_assert(IsAddressType<AddrT>::Value);
+  return Address<Alignment, AddrT::PERMISSION, AddrT::TEMPORALITY>(addr.ptr_ +
+                                                                   byte_offset);
+}
+
+// Offsets the address by a runtime amount that is assumed to be a multiple of
+// ByteOffset. This allows to propagate the address alignment whenever possible.
+template <size_t ByteOffset, typename AddrT>
+static auto offsetAddrMultiplesOf(AddrT addr, ptrdiff_t byte_offset) {
+  static_assert(IsAddressType<AddrT>::Value);
+  return addr.template offset<ByteOffset>(byte_offset);
+}
+
+// User friendly aliases for common address types.
+template <size_t Alignment>
+using SrcAddr = Address<Alignment, Permission::Read, Temporality::TEMPORAL>;
+template <size_t Alignment>
+using DstAddr = Address<Alignment, Permission::Write, Temporality::TEMPORAL>;
+template <size_t Alignment>
+using NtSrcAddr =
+    Address<Alignment, Permission::Read, Temporality::NON_TEMPORAL>;
+template <size_t Alignment>
+using NtDstAddr =
+    Address<Alignment, Permission::Write, Temporality::NON_TEMPORAL>;
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_COMMON_H

libc/test/src/string/memory_utils/CMakeLists.txt

 add_libc_unittest(
   utils_test
   SUITE
     libc_string_unittests
   SRCS
+    address_test.cpp
     elements_test.cpp
     memory_access_test.cpp
     utils_test.cpp
   DEPENDS
     libc.src.string.memory_utils.memory_utils
     libc.src.__support.CPP.array
     libc.src.__support.CPP.array_ref
   COMPILE_OPTIONS
     ${LIBC_COMPILE_OPTIONS_NATIVE}
     -ffreestanding
 )

libc/test/src/string/memory_utils/address_test.cpp

+#include "utils/UnitTest/Test.h"
+#include <src/string/memory_utils/address.h>
+
+namespace __llvm_libc {
+
+TEST(LlvmLibcAddress, AliasAreAddresses) {
+  ASSERT_TRUE(IsAddressType<SrcAddr<1>>::Value);
+  ASSERT_TRUE(IsAddressType<DstAddr<1>>::Value);
+  ASSERT_TRUE(IsAddressType<NtSrcAddr<1>>::Value);
+  ASSERT_TRUE(IsAddressType<NtDstAddr<1>>::Value);
+}
+
+TEST(LlvmLibcAddress, AliasHaveRightPermissions) {
+  ASSERT_TRUE(SrcAddr<1>::IS_READ);
+  ASSERT_TRUE(NtSrcAddr<1>::IS_READ);
+  ASSERT_TRUE(DstAddr<1>::IS_WRITE);
+  ASSERT_TRUE(NtDstAddr<1>::IS_WRITE);
+}
+
+TEST(LlvmLibcAddress, AliasHaveRightSemantic) {
+  ASSERT_EQ(SrcAddr<1>::TEMPORALITY, Temporality::TEMPORAL);
+  ASSERT_EQ(DstAddr<1>::TEMPORALITY, Temporality::TEMPORAL);
+  ASSERT_EQ(NtSrcAddr<1>::TEMPORALITY, Temporality::NON_TEMPORAL);
+  ASSERT_EQ(NtDstAddr<1>::TEMPORALITY, Temporality::NON_TEMPORAL);
+}
+
+TEST(LlvmLibcAddress, AliasHaveRightAlignment) {
+  ASSERT_EQ(SrcAddr<1>::ALIGNMENT, size_t(1));
+  ASSERT_EQ(SrcAddr<4>::ALIGNMENT, size_t(4));
+}
+
+TEST(LlvmLibcAddress, NarrowAlignment) {
+  // Address 8-byte aligned, offset by 8.
+  ASSERT_EQ(offsetAddr<8>(SrcAddr<8>(nullptr)).ALIGNMENT, 8UL);
+  // Address 16-byte aligned, offset by 4.
+  ASSERT_EQ(offsetAddr<4>(SrcAddr<16>(nullptr)).ALIGNMENT, 4UL);
+  // Address 4-byte aligned, offset by 16.
+  ASSERT_EQ(offsetAddr<16>(SrcAddr<4>(nullptr)).ALIGNMENT, 4UL);
+  // Address 4-byte aligned, offset by 1.
+  ASSERT_EQ(offsetAddr<1>(SrcAddr<4>(nullptr)).ALIGNMENT, 1UL);
+  // Address 4-byte aligned, offset by 2.
+  ASSERT_EQ(offsetAddr<2>(SrcAddr<4>(nullptr)).ALIGNMENT, 2UL);
+  // Address 4-byte aligned, offset by 6.
+  ASSERT_EQ(offsetAddr<6>(SrcAddr<4>(nullptr)).ALIGNMENT, 2UL);
+  // Address 4-byte aligned, offset by 10.
+  ASSERT_EQ(offsetAddr<10>(SrcAddr<4>(nullptr)).ALIGNMENT, 2UL);
+  // Address 8-byte aligned, offset by 6.
+  ASSERT_EQ(offsetAddr<6>(SrcAddr<8>(nullptr)).ALIGNMENT, 2UL);
+}
+
+TEST(LlvmLibcAddress, OffsetAddr) {
+  ubyte a;
+  SrcAddr<1> addr(&a);
+  ASSERT_EQ((const void *)offsetAddr<4>(addr).ptr(), (const void *)(&a + 4));
+  ASSERT_EQ((const void *)offsetAddr<32>(addr).ptr(), (const void *)(&a + 32));
+}
+
+TEST(LlvmLibcAddress, AssumeAligned) {
+  SrcAddr<16> addr(nullptr);
+  ASSERT_EQ(offsetAddrAssumeAligned<8>(addr, 0).ALIGNMENT, 8UL);
+  ASSERT_EQ(offsetAddrAssumeAligned<1>(addr, 0).ALIGNMENT, 1UL);
+  ASSERT_EQ(offsetAddrMultiplesOf<4>(addr, 0).ALIGNMENT, 4UL);
+  ASSERT_EQ(offsetAddrMultiplesOf<32>(addr, 0).ALIGNMENT, 16UL);
+}
+
+TEST(LlvmLibcAddress, offsetAddrAssumeAligned) {
+  ubyte a;
+  SrcAddr<1> addr(&a);
+  ASSERT_EQ((const void *)offsetAddrAssumeAligned<1>(addr, 17).ptr(),
+            (const void *)(&a + 17));
+}
+
+TEST(LlvmLibcAddress, offsetAddrMultiplesOf) {
+  ubyte a;
+  SrcAddr<1> addr(&a);
+  ASSERT_EQ((const void *)offsetAddrMultiplesOf<4>(addr, 16).ptr(),
+            (const void *)(&a + 16));
+}
+
+} // namespace __llvm_libc

libc/utils/UnitTest/LibcTest.h

protected:
   // of type promotion.
   template <typename ValType,
             cpp::EnableIfType<cpp::IsIntegral<ValType>::Value, int> = 0>
   bool test(TestCondition Cond, ValType LHS, ValType RHS, const char *LHSStr,
             const char *RHSStr, const char *File, unsigned long Line) {
     return internal::test(Ctx, Cond, LHS, RHS, LHSStr, RHSStr, File, Line);
   }
 
+  template <typename ValType,
+            cpp::EnableIfType<cpp::IsEnum<ValType>::Value, int> = 0>
+  bool test(TestCondition Cond, ValType LHS, ValType RHS, const char *LHSStr,
+            const char *RHSStr, const char *File, unsigned long Line) {
+    return internal::test(Ctx, Cond, (long long)LHS, (long long)RHS, LHSStr,
+                          RHSStr, File, Line);
+  }
+
   template <
       typename ValType,
       cpp::EnableIfType<cpp::IsPointerType<ValType>::Value, ValType> = nullptr>
   bool test(TestCondition Cond, ValType LHS, ValType RHS, const char *LHSStr,
             const char *RHSStr, const char *File, unsigned long Line) {
     return internal::test(Ctx, Cond, (unsigned long long)LHS,
                           (unsigned long long)RHS, LHSStr, RHSStr, File, Line);
   }