[libc][mem*] Introduce Sized/Backends for new mem framework

[gchatelet]

Summary

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

The SizedOp struct represents operations to be performed on a certain number of bytes.
It is responsible for breaking them down into platform types and forwarded to the Backend.

The Backend struct represents a lower level abstraction that works only on types (uint8_t, __m128i, ...).
It is similar to instruction selection.

[gchatelet]

• rebase

[courbet]

As a very high level, design comment, I would like to note that I think we should strive to get into a state where the lowering of a SizedOp is done via a instrinsic call for all operation type (right now, this is only the case for memcpy).

The idea is that there are currently two places where we know how to lower a memory operation: the Backend, and the compiler (through the __builtin_memxxx_inline). In the future, any improvement to the Backend will only impact the codegen for memxxx, but not the expansion of a memxxx(p, q, constant_size). One way to ensure non-divergence between the Backend implementations and the builtins is to actually use the builtins for lowering (at least in the "normal", non-temporal case).

So eventually, all implementations should look like the one for copy:

 if constexpr (LLVM_LIBC_USE_BUILTIN_MEMXXX_INLINE && /*is normal*/) {
     // delegate optimized operation to compiler.
     __builtin_memxxx_inline(dst.ptr(), src.ptr(), Size);
     return;
   }
   // Fancy c++ implementation.
}

This is especially true for memcmp (I'm not sure how much love the ExpandMemcmp pass has had wrt aarch64), and memset (for example, __builtin_memset does not currently know to use zva: https://godbolt.org/z/6noee3Y6c).

[courbet]

libc/src/string/memory_utils/backend_aarch64.h

17–21

It's not clear what this does:

• if T scalar type, it delegates to the scalar backend, i.e. a noop.
• if not, the compiler will select the implementation in ScalarBackend, which will assert that T is a scalar type.

What am I missing ?

24

fix comment ?

libc/src/string/memory_utils/backend_scalar.h

15–16

is that true of all architectures ?

22

is that true of all architectures ?

36

It's not immediately obvious that this works for uint64_t. What about ~T(0) / T(0xFF) ?

[gchatelet]

• Address comments

[courbet]

libc/src/string/memory_utils/backend_x86.h

44

"unspecialized case". And the function should have a comment saying something like:

// This function is specialized below.

And specialize it for non-temporal loads if you want a better user message.

57

ditto

60

// Forwarding to base class because c++ does not allow specializing base class methods.

70

I've just noticed that all functions in this patch should be using threeWayCmp case...

82

doc?

128

why not _mm_cmpeq_epi8 instead ?

149

why not _mm256_cmpeq_epi8 instead ?

[courbet]

libc/src/string/memory_utils/backend_x86.h

2

Missing header (same above).

libc/src/string/memory_utils/backends.h

13

"native loads and stores", right ?

37

[Nit]sentences.

libc/src/string/memory_utils/sized_op.h

12

whose

38

[nit] The mix of cases makes this difficult to read, please use SIZE (or better still, change the style guide for llvm-libc :) )

40

What about overlapping operations ?

48

The naming is confusing to me: loadType wants to read as "load the given type". Maybe typedLoad. or loadFrom ?

48

doc ?

56

ditto

63

doc ?

100

is_different or differs ?

103

> 0

104

The non-short-circuiting | warrants a comment.

117

?

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

14

Looks like the ISO/IEC 9899 LCG seeded with 123456789. Can you add a link ?

[gchatelet]

libc/src/string/memory_utils/backend_aarch64.h

17–21

For now we don't have any special types to handle for aarch64 so I've removed this backend.

24

It really is an implementation of the SizedOp abstraction but it only provides the set method.
I've updated the comment, I hope it's clearer now.

libc/src/string/memory_utils/backend_scalar.h

15–16

As discussed, I've renamed the backend so it's explicit we only consider 64bit implementation for now.

36

As discussed offline, let's go with return (T(~0ULL) / T(0xFF)) * T(value); since the ~ operator would promote uint8_t and uint16_t to int.

libc/src/string/memory_utils/backend_x86.h

128

I would need _mm_cmpneq_epi8 and it's cumbersome to express with Intel intrinsics. The instruction exists for _mm512 though.

149

ditto

libc/src/string/memory_utils/sized_op.h

40

That's another design point that I've tested previously and that doesn't bring any benefits for fixed size operations so I kept the simpler design.

The generic algorithms are usually considering fixed-sized operations up to 3 or 4 and then rely on dynamically overlapping operations to cover sizes from N to 2xN.

So this design point only has a concrete impact for size 3.

48

I went with nativeLoad/nativeStore as discussed offline

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

14

Added documentation and used the C++ "recommended" settings.

[gchatelet]

• Address comments

[gchatelet]

• Rename backend

[courbet]

libc/src/string/memory_utils/sized_op.h

137

?

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

1

Header ?

[gchatelet]

• Address comments

libc/src/string/memory_utils/backend_aarch64.h

+//===-- Elementary operations for aarch64 ---------------------------------===//
+//
+// 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_BACKEND_AARCH64_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BACKEND_AARCH64_H
+
+#if !defined(LLVM_LIBC_ARCH_AARCH64)
+#include "src/string/memory_utils/backend_scalar.h"
+
+#ifdef __ARM_NEON
+#include <arm_neon.h>
+#endif
+
+namespace __llvm_libc {
+
+struct Aarch64Backend : public Scalar64BitBackend {
+  static constexpr bool IS_BACKEND_TYPE = true;
+
+  template <typename T, Temporality TS, Aligned AS,
+            cpp::EnableIfType<Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline T load(const T *src) {
+    return Scalar64BitBackend::template load<T, TS, AS>(src);
+  }
+};
+
+// Implementation of the SizedOp abstraction for the set operation.
+struct Zva64 {
+  static constexpr size_t SIZE = 64;
+
+  template <typename DstAddrT>
+  static inline void set(DstAddrT dst, ubyte value) {
+#if __SIZEOF_POINTER__ == 4
+    asm("dc zva, %w[dst]" : : [dst] "r"(dst) : "memory");
+#else
+    asm("dc zva, %[dst]" : : [dst] "r"(dst) : "memory");
+#endif
+  }
+};
+
+inline static bool hasZva() {
+  uint64_t zva_val;
+  asm("mrs %[zva_val], dczid_el0" : [zva_val] "=r"(zva_val));
+  // DC ZVA is permitted if DZP, bit [4] is zero.
+  // BS, bits [3:0] is log2 of the block size in words.
+  // So the next line checks whether the instruction is permitted and block size
+  // is 16 words (i.e. 64 bytes).
+  return (zva_val & 0b11111) == 0b00100;
+}
+
+namespace aarch64 {
+using _1 = SizedOp<Aarch64Backend, 1>;
+using _2 = SizedOp<Aarch64Backend, 2>;
+using _3 = SizedOp<Aarch64Backend, 3>;
+using _4 = SizedOp<Aarch64Backend, 4>;
+using _8 = SizedOp<Aarch64Backend, 8>;
+using _16 = SizedOp<Aarch64Backend, 16>;
+using _32 = SizedOp<Aarch64Backend, 32>;
+using _64 = SizedOp<Aarch64Backend, 64>;
+using _128 = SizedOp<Aarch64Backend, 128>;
+} // namespace aarch64
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_ARCH_AARCH64
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BACKEND_AARCH64_H

libc/src/string/memory_utils/backend_scalar.h

+//===-- Elementary operations for native scalar types ---------------------===//
+//
+// 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_BACKEND_SCALAR_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BACKEND_SCALAR_H
+
+#include "src/__support/CPP/TypeTraits.h" // ConditionalType, EnableIfType
+#include "src/__support/endian.h"
+
+namespace __llvm_libc {
+
+struct Scalar64BitBackend {
+  static constexpr bool IS_BACKEND_TYPE = true;
+
+  template <typename T>
+  static constexpr bool IsScalarType =
+      cpp::IsSameV<T, uint8_t> || cpp::IsSameV<T, uint16_t> ||
+      cpp::IsSameV<T, uint32_t> || cpp::IsSameV<T, uint64_t>;
+
+  template <typename T, Temporality TS, Aligned AS>
+  static inline T load(const T *src) {
+    static_assert(IsScalarType<T>);
+    static_assert(TS == Temporality::TEMPORAL,
+                  "Scalar load does not support non-temporal access");
+    return *src;
+  }
+
+  template <typename T, Temporality TS, Aligned AS>
+  static inline void store(T *dst, T value) {
+    static_assert(IsScalarType<T>);
+    static_assert(TS == Temporality::TEMPORAL,
+                  "Scalar store does not support non-temporal access");
+    *dst = value;
+  }
+
+  template <typename T> static inline T splat(ubyte value) {
+    static_assert(IsScalarType<T>);
+    return (T(~0ULL) / T(0xFF)) * T(value);
+  }
+
+  template <typename T> static inline uint64_t notEquals(T v1, T v2) {
+    static_assert(IsScalarType<T>);
+    return v1 ^ v2;
+  }
+
+  template <typename T> static inline int32_t threeWayCmp(T v1, T v2) {
+    DeferredStaticAssert("not implemented");
+  }
+
+  // Returns the type to use to consume Size bytes.
+  template <size_t Size>
+  using getNextType = cpp::ConditionalType<
+      Size >= 8, uint64_t,
+      cpp::ConditionalType<Size >= 4, uint32_t,
+                           cpp::ConditionalType<Size >= 2, uint16_t, uint8_t>>>;
+};
+
+template <>
+int32_t inline Scalar64BitBackend::threeWayCmp<uint8_t>(uint8_t a, uint8_t b) {
+  const int16_t la = Endian::to_big_endian(a);
+  const int16_t lb = Endian::to_big_endian(b);
+  return la - lb;
+}
+template <>
+int32_t inline Scalar64BitBackend::threeWayCmp<uint16_t>(uint16_t a,
+                                                         uint16_t b) {
+  const int32_t la = Endian::to_big_endian(a);
+  const int32_t lb = Endian::to_big_endian(b);
+  return la - lb;
+}
+template <>
+int32_t inline Scalar64BitBackend::threeWayCmp<uint32_t>(uint32_t a,
+                                                         uint32_t b) {
+  const uint32_t la = Endian::to_big_endian(a);
+  const uint32_t lb = Endian::to_big_endian(b);
+  return la > lb ? 1 : la < lb ? -1 : 0;
+}
+template <>
+int32_t inline Scalar64BitBackend::threeWayCmp<uint64_t>(uint64_t a,
+                                                         uint64_t b) {
+  const uint64_t la = Endian::to_big_endian(a);
+  const uint64_t lb = Endian::to_big_endian(b);
+  return la > lb ? 1 : la < lb ? -1 : 0;
+}
+
+namespace scalar {
+using _1 = SizedOp<Scalar64BitBackend, 1>;
+using _2 = SizedOp<Scalar64BitBackend, 2>;
+using _3 = SizedOp<Scalar64BitBackend, 3>;
+using _4 = SizedOp<Scalar64BitBackend, 4>;
+using _8 = SizedOp<Scalar64BitBackend, 8>;
+using _16 = SizedOp<Scalar64BitBackend, 16>;
+using _32 = SizedOp<Scalar64BitBackend, 32>;
+using _64 = SizedOp<Scalar64BitBackend, 64>;
+using _128 = SizedOp<Scalar64BitBackend, 128>;
+} // namespace scalar
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BACKEND_SCALAR_H

libc/src/string/memory_utils/backend_x86.h

+//===-- Elementary operations for x86 -------------------------------------===//
+//
+// 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_BACKEND_X86_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BACKEND_X86_H
+
+#if defined(LLVM_LIBC_ARCH_X86)
+#include "src/__support/CPP/TypeTraits.h" // ConditionalType, EnableIfType
+#include "src/string/memory_utils/backend_scalar.h"
+
+#ifdef __SSE2__
+#include <immintrin.h>
+#endif //  __SSE2__
+
+#if defined(__SSE2__)
+#define HAS_M128 true
+#else
+#define HAS_M128 false
+#endif
+
+#if defined(__AVX2__)
+#define HAS_M256 true
+#else
+#define HAS_M256 false
+#endif
+
+#if defined(__AVX512F__) and defined(__AVX512BW__)
+#define HAS_M512 true
+#else
+#define HAS_M512 false
+#endif
+
+namespace __llvm_libc {
+struct X86Backend : public Scalar64BitBackend {
+  static constexpr bool IS_BACKEND_TYPE = true;
+
+  // Scalar types use base class implementations.
+  template <typename T, Temporality TS, Aligned AS,
+            cpp::EnableIfType<Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline T load(const T *src) {
+    return Scalar64BitBackend::template load<T, TS, AS>(src);
+  }
+
+  // Scalar types use base class implementations.
+  template <typename T, Temporality TS, Aligned AS,
+            cpp::EnableIfType<Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline void store(T *dst, T value) {
+    Scalar64BitBackend::template store<T, TS, AS>(dst, value);
+  }
+
+  // Scalar types use base class implementations.
+  template <typename T,
+            cpp::EnableIfType<Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline uint64_t notEquals(T v1, T v2) {
+    return Scalar64BitBackend::template notEquals<T>(v1, v2);
+  }
+
+  // Scalar types use base class implementations.
+  template <typename T,
+            cpp::EnableIfType<Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline T splat(ubyte value) {
+    return Scalar64BitBackend::template splat<T>(value);
+  }
+
+  // Scalar types use base class implementations.
+  template <typename T,
+            cpp::EnableIfType<Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline int32_t threeWayCmp(T v1, T v2) {
+    return Scalar64BitBackend::template threeWayCmp<T>(v1, v2);
+  }
+
+  // X86 types are specialized below.
+  template <
+      typename T, Temporality TS, Aligned AS,
+      cpp::EnableIfType<!Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline T load(const T *src);
+
+  // X86 types are specialized below.
+  template <
+      typename T, Temporality TS, Aligned AS,
+      cpp::EnableIfType<!Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline void store(T *dst, T value);
+
+  // X86 types are specialized below.
+  template <typename T, cpp::EnableIfType<!Scalar64BitBackend::IsScalarType<T>,
+                                          bool> = true>
+  static inline T splat(ubyte value);
+
+  // X86 types are specialized below.
+  template <typename T, cpp::EnableIfType<!Scalar64BitBackend::IsScalarType<T>,
+                                          bool> = true>
+  static inline uint64_t notEquals(T v1, T v2);
+
+  template <typename T, cpp::EnableIfType<!Scalar64BitBackend::IsScalarType<T>,
+                                          bool> = true>
+  static inline int32_t threeWayCmp(T v1, T v2) {
+    return char_diff(reinterpret_cast<char *>(&v1),
+                     reinterpret_cast<char *>(&v2), notEquals(v1, v2));
+  }
+
+  // Returns the type to use to consume Size bytes.
+  template <size_t Size>
+  using getNextType = cpp::ConditionalType<
+      (HAS_M512 && Size >= 64), __m512i,
+      cpp::ConditionalType<
+          (HAS_M256 && Size >= 32), __m256i,
+          cpp::ConditionalType<(HAS_M128 && Size >= 16), __m128i,
+                               Scalar64BitBackend::getNextType<Size>>>>;
+
+private:
+  static inline int32_t char_diff(const char *a, const char *b, uint64_t mask) {
+    const size_t diff_index = mask == 0 ? 0 : __builtin_ctzll(mask);
+    const int16_t ca = (unsigned char)a[diff_index];
+    const int16_t cb = (unsigned char)b[diff_index];
+    return ca - cb;
+  }
+};
+
+static inline void repmovsb(void *dst, const void *src, size_t runtime_size) {
+  asm volatile("rep movsb"
+               : "+D"(dst), "+S"(src), "+c"(runtime_size)
+               :
+               : "memory");
+}
+
+#define SPECIALIZE_LOAD(T, OS, AS, INTRISIC)                                   \
+  template <> inline T X86Backend::load<T, OS, AS>(const T *src) {             \
+    return INTRISIC(const_cast<T *>(src));                                     \
+  }
+#define SPECIALIZE_STORE(T, OS, AS, INTRISIC)                                  \
+  template <> inline void X86Backend::store<T, OS, AS>(T * dst, T value) {     \
+    INTRISIC(dst, value);                                                      \
+  }
+
+#if HAS_M128
+SPECIALIZE_LOAD(__m128i, Temporality::TEMPORAL, Aligned::YES, _mm_load_si128)
+SPECIALIZE_LOAD(__m128i, Temporality::TEMPORAL, Aligned::NO, _mm_loadu_si128)
+SPECIALIZE_LOAD(__m128i, Temporality::NON_TEMPORAL, Aligned::YES,
+                _mm_stream_load_si128)
+// X86 non-temporal load needs aligned access
+SPECIALIZE_STORE(__m128i, Temporality::TEMPORAL, Aligned::YES, _mm_store_si128)
+SPECIALIZE_STORE(__m128i, Temporality::TEMPORAL, Aligned::NO, _mm_storeu_si128)
+SPECIALIZE_STORE(__m128i, Temporality::NON_TEMPORAL, Aligned::YES,
+                 _mm_stream_si128)
+// X86 non-temporal store needs aligned access
+template <> inline __m128i X86Backend::splat<__m128i>(ubyte value) {
+  return _mm_set1_epi8(__builtin_bit_cast(char, value));
+}
+template <>
+inline uint64_t X86Backend::notEquals<__m128i>(__m128i a, __m128i b) {
+  using T = char __attribute__((__vector_size__(16)));
+  return _mm_movemask_epi8(T(a) != T(b));
+}
+#endif // HAS_M128
+
+#if HAS_M256
+SPECIALIZE_LOAD(__m256i, Temporality::TEMPORAL, Aligned::YES, _mm256_load_si256)
+SPECIALIZE_LOAD(__m256i, Temporality::TEMPORAL, Aligned::NO, _mm256_loadu_si256)
+SPECIALIZE_LOAD(__m256i, Temporality::NON_TEMPORAL, Aligned::YES,
+                _mm256_stream_load_si256)
+// X86 non-temporal load needs aligned access
+SPECIALIZE_STORE(__m256i, Temporality::TEMPORAL, Aligned::YES,
+                 _mm256_store_si256)
+SPECIALIZE_STORE(__m256i, Temporality::TEMPORAL, Aligned::NO,
+                 _mm256_storeu_si256)
+SPECIALIZE_STORE(__m256i, Temporality::NON_TEMPORAL, Aligned::YES,
+                 _mm256_stream_si256)
+// X86 non-temporal store needs aligned access
+template <> inline __m256i X86Backend::splat<__m256i>(ubyte value) {
+  return _mm256_set1_epi8(__builtin_bit_cast(char, value));
+}
+template <>
+inline uint64_t X86Backend::notEquals<__m256i>(__m256i a, __m256i b) {
+  using T = char __attribute__((__vector_size__(32)));
+  return _mm256_movemask_epi8(T(a) != T(b));
+}
+#endif // HAS_M256
+
+#if HAS_M512
+SPECIALIZE_LOAD(__m512i, Temporality::TEMPORAL, Aligned::YES, _mm512_load_si512)
+SPECIALIZE_LOAD(__m512i, Temporality::TEMPORAL, Aligned::NO, _mm512_loadu_si512)
+SPECIALIZE_LOAD(__m512i, Temporality::NON_TEMPORAL, Aligned::YES,
+                _mm512_stream_load_si512)
+// X86 non-temporal load needs aligned access
+SPECIALIZE_STORE(__m512i, Temporality::TEMPORAL, Aligned::YES,
+                 _mm512_store_si512)
+SPECIALIZE_STORE(__m512i, Temporality::TEMPORAL, Aligned::NO,
+                 _mm512_storeu_si512)
+SPECIALIZE_STORE(__m512i, Temporality::NON_TEMPORAL, Aligned::YES,
+                 _mm512_stream_si512)
+// X86 non-temporal store needs aligned access
+template <> inline __m512i X86Backend::splat<__m512i>(ubyte value) {
+  return _mm512_broadcastb_epi8(_mm_set1_epi8(__builtin_bit_cast(char, value)));
+}
+template <>
+inline uint64_t X86Backend::notEquals<__m512i>(__m512i a, __m512i b) {
+  return _mm512_cmpneq_epi8_mask(a, b);
+}
+#endif // HAS_M512
+
+namespace x86 {
+using _1 = SizedOp<X86Backend, 1>;
+using _2 = SizedOp<X86Backend, 2>;
+using _3 = SizedOp<X86Backend, 3>;
+using _4 = SizedOp<X86Backend, 4>;
+using _8 = SizedOp<X86Backend, 8>;
+using _16 = SizedOp<X86Backend, 16>;
+using _32 = SizedOp<X86Backend, 32>;
+using _64 = SizedOp<X86Backend, 64>;
+using _128 = SizedOp<X86Backend, 128>;
+} // namespace x86
+
+} // namespace __llvm_libc
+
+#endif // defined(LLVM_LIBC_ARCH_X86)
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BACKEND_X86_H

libc/src/string/memory_utils/backends.h

+//===-- Elementary operations to compose memory primitives ----------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the concept of a Backend.
+// It constitutes the lowest level of the framework and is akin to instruction
+// selection. It defines how to implement aligned/unaligned,
+// temporal/non-temporal native loads and stores for a particular architecture
+// as well as efficient ways to fill and compare types.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BACKENDS_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BACKENDS_H
+
+#include "src/string/memory_utils/address.h" // Temporality, Aligned
+#include "src/string/memory_utils/sized_op.h" // SizedOp
+#include <stddef.h>                           // size_t
+#include <stdint.h>                           // uint##_t
+
+namespace __llvm_libc {
+
+// Backends must implement the following interface.
+struct NoBackend {
+  static constexpr bool IS_BACKEND_TYPE = true;
+
+  // Loads a T from `src` honoring Temporality and Alignment.
+  template <typename T, Temporality, Aligned> static T load(const T *src);
+
+  // Stores a T to `dst` honoring Temporality and Alignment.
+  template <typename T, Temporality, Aligned>
+  static void store(T *dst, T value);
+
+  // Returns a T filled with `value` bytes.
+  template <typename T> static T splat(ubyte value);
+
+  // Returns zero iff v1 == v2.
+  template <typename T> static uint64_t notEquals(T v1, T v2);
+
+  // Returns zero iff v1 == v2, a negative number if v1 < v2 and a positive
+  // number otherwise.
+  template <typename T> static int32_t threeWayCmp(T v1, T v2);
+
+  // Returns the type to use to consume Size bytes.
+  // If no type handles Size bytes at once
+  template <size_t Size> using getNextType = void;
+};
+
+} // namespace __llvm_libc
+
+// We inline all backend implementations here to simplify the build system.
+// Each file need to be guarded with the appropriate LLVM_LIBC_ARCH_XXX ifdef.
+#include "src/string/memory_utils/backend_aarch64.h"
+#include "src/string/memory_utils/backend_scalar.h"
+#include "src/string/memory_utils/backend_x86.h"
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BACKENDS_H

libc/src/string/memory_utils/sized_op.h

+//===-- Sized Operations --------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the SizedOp struct that serves as the middle end of the
+// framework. It implements sized memory operations by breaking them down into
+// simpler types whose availability is described in the Backend. It also
+// provides a way to load and store sized chunks of memory (necessary for the
+// move operation). SizedOp are the building blocks of higher order algorithms
+// like HeadTail, Align or Loop.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_SIZED_OP_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_SIZED_OP_H
+
+#include <stddef.h> // size_t
+
+#ifndef LLVM_LIBC_USE_BUILTIN_MEMCPY_INLINE
+#define LLVM_LIBC_USE_BUILTIN_MEMCPY_INLINE                                    \
+  __has_builtin(__builtin_memcpy_inline)
+#endif // LLVM_LIBC_USE_BUILTIN_MEMCPY_INLINE
+
+#ifndef LLVM_LIBC_USE_BUILTIN_MEMSET_INLINE
+#define LLVM_LIBC_USE_BUILTIN_MEMSET_INLINE                                    \
+  __has_builtin(__builtin_memset_inline)
+#endif // LLVM_LIBC_USE_BUILTIN_MEMSET_INLINE
+
+namespace __llvm_libc {
+
+template <typename Backend, size_t Size> struct SizedOp {
+  static constexpr size_t SIZE = Size;
+
+private:
+  static_assert(Backend::IS_BACKEND_TYPE);
+  static_assert(SIZE > 0);
+  using type = typename Backend::template getNextType<Size>;
+  static constexpr size_t TYPE_SIZE = sizeof(type);
+  static_assert(SIZE >= TYPE_SIZE);
+  static constexpr size_t NEXT_SIZE = Size - TYPE_SIZE;
+  using NextBlock = SizedOp<Backend, NEXT_SIZE>;
+
+  // Returns whether we can use an aligned operations.
+  // This is possible because the address type carries known compile-time
+  // alignment informations.
+  template <typename T, typename AddrT> static constexpr Aligned isAligned() {
+    static_assert(IsAddressType<AddrT>::Value);
+    return AddrT::ALIGNMENT > 1 && AddrT::ALIGNMENT >= sizeof(T) ? Aligned::YES
+                                                                 : Aligned::NO;
+  }
+
+  // Loads a value of the current `type` from `src`.
+  // This function is responsible for extracting Temporality and Alignment from
+  // the Address type.
+  template <typename SrcAddrT> static inline auto nativeLoad(SrcAddrT src) {
+    static_assert(IsAddressType<SrcAddrT>::Value && SrcAddrT::IS_READ);
+    constexpr auto AS = isAligned<type, SrcAddrT>();
+    constexpr auto TS = SrcAddrT::TEMPORALITY;
+    return Backend::template load<type, TS, AS>(as<const type>(src));
+  }
+
+  // Stores a value of the current `type` to `dst`.
+  // This function is responsible for extracting Temporality and Alignment from
+  // the Address type.
+  template <typename DstAddrT>
+  static inline void nativeStore(type value, DstAddrT dst) {
+    static_assert(IsAddressType<DstAddrT>::Value && DstAddrT::IS_WRITE);
+    constexpr auto AS = isAligned<type, DstAddrT>();
+    constexpr auto TS = DstAddrT::TEMPORALITY;
+    return Backend::template store<type, TS, AS>(as<type>(dst), value);
+  }
+
+  // A well aligned POD structure to store Size bytes.
+  // This is used to implement the move operations.
+  struct Value {
+    alignas(alignof(type)) ubyte payload[Size];
+  };
+
+public:
+  template <typename DstAddrT, typename SrcAddrT>
+  static inline void copy(DstAddrT dst, SrcAddrT src) {
+    static_assert(IsAddressType<DstAddrT>::Value && DstAddrT::IS_WRITE);
+    static_assert(IsAddressType<SrcAddrT>::Value && SrcAddrT::IS_READ);
+    if constexpr (LLVM_LIBC_USE_BUILTIN_MEMCPY_INLINE &&
+                  DstAddrT::TEMPORALITY == Temporality::TEMPORAL &&
+                  SrcAddrT::TEMPORALITY == Temporality::TEMPORAL) {
+      // delegate optimized copy to compiler.
+      __builtin_memcpy_inline(dst.ptr(), src.ptr(), Size);
+      return;
+    }
+    nativeStore(nativeLoad(src), dst);
+    if constexpr (NEXT_SIZE > 0)
+      NextBlock::copy(offsetAddr<TYPE_SIZE>(dst), offsetAddr<TYPE_SIZE>(src));
+  }
+
+  template <typename DstAddrT, typename SrcAddrT>
+  static inline void move(DstAddrT dst, SrcAddrT src) {
+    const auto payload = nativeLoad(src);
+    if constexpr (NEXT_SIZE > 0)
+      NextBlock::move(offsetAddr<TYPE_SIZE>(dst), offsetAddr<TYPE_SIZE>(src));
+    nativeStore(payload, dst);
+  }
+
+  template <typename DstAddrT>
+  static inline void set(DstAddrT dst, ubyte value) {
+    if constexpr (LLVM_LIBC_USE_BUILTIN_MEMSET_INLINE &&
+                  DstAddrT::TEMPORALITY == Temporality::TEMPORAL) {
+      // delegate optimized set to compiler.
+      __builtin_memset_inline(dst.ptr(), value, Size);
+      return;
+    }
+    nativeStore(Backend::template splat<type>(value), dst);
+    if constexpr (NEXT_SIZE > 0)
+      NextBlock::set(offsetAddr<TYPE_SIZE>(dst), value);
+  }
+
+  template <typename SrcAddrT1, typename SrcAddrT2>
+  static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2) {
+    const uint64_t current =
+        Backend::template notEquals<type>(nativeLoad(src1), nativeLoad(src2));
+    if constexpr (NEXT_SIZE > 0) {
+      // In the case where we cannot handle Size with single operation (e.g.
+      // Size == 3) we can either return early if current is non zero or
+      // aggregate all the operations through the bitwise or operator.
+      // We chose the later to reduce branching.
+      return current | (NextBlock::isDifferent(offsetAddr<TYPE_SIZE>(src1),
+                                               offsetAddr<TYPE_SIZE>(src2)));
+    } else {
+      return current;
+    }
+  }
+
+  // template <typename SrcAddrT1, typename SrcAddrT2>
+  // static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2) {
+  //   const auto a = nativeLoad(src1);
+  //   const auto b = nativeLoad(src2);
+  //   if (Backend::template notEquals<type>(a, b))
+  //     return Backend::template threeWayCmp<type>(a, b);
+  //   if constexpr (NEXT_SIZE)
+  //     return NextBlock::threeWayCmp(offsetAddr<TYPE_SIZE>(src1),
+  //                                   offsetAddr<TYPE_SIZE>(src2));
+  //   return 0;
+  // }
+
+  template <typename SrcAddrT1, typename SrcAddrT2>
+  static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2) {
+    const auto a = nativeLoad(src1);
+    const auto b = nativeLoad(src2);
+    // If we cannot handle Size as a single operation we have two choices:
+    // - Either use Backend's threeWayCmp directly and return it is non
+    // zero.
+    //
+    //   if (int32_t res = Backend::template threeWayCmp<type>(a, b))
+    //     return res;
+    //
+    // - Or use Backend's notEquals first and use threeWayCmp only if
+    // different, the assumption here is that notEquals is faster than
+    // threeWayCmp and that we can save cycles when the Size needs to be
+    // decomposed in many sizes (e.g. Size == 7 => 4 + 2 + 1)
+    //
+    //   if (Backend::template notEquals<type>(a, b))
+    //     return Backend::template threeWayCmp<type>(a, b);
+    //
+    // We chose the former to reduce code bloat and branching.
+    if (int32_t res = Backend::template threeWayCmp<type>(a, b))
+      return res;
+    if constexpr (NEXT_SIZE > 0)
+      return NextBlock::threeWayCmp(offsetAddr<TYPE_SIZE>(src1),
+                                    offsetAddr<TYPE_SIZE>(src2));
+    return 0;
+  }
+
+  template <typename SrcAddrT> static Value load(SrcAddrT src) {
+    Value output;
+    copy(DstAddr<alignof(type)>(output.payload), src);
+    return output;
+  }
+
+  template <typename DstAddrT> static void store(DstAddrT dst, Value value) {
+    copy(dst, SrcAddr<alignof(type)>(value.payload));
+  }
+};
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_SIZED_OP_H

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

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

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

+
+#include "src/__support/CPP/Array.h"
+#include "src/__support/CPP/ArrayRef.h"
+#include "src/__support/CPP/Bit.h"
+#include "src/__support/architectures.h"
+#include "src/string/memory_utils/backends.h"
+#include "utils/UnitTest/Test.h"
+#include <string.h>
+
+namespace __llvm_libc {
+
+template <size_t Size> using Buffer = cpp::Array<char, Size>;
+
+static char GetRandomChar() {
+  // Implementation of C++ minstd_rand seeded with 123456789.
+  // https://en.cppreference.com/w/cpp/numeric/random
+  // "Minimum standard", recommended by Park, Miller, and Stockmeyer in 1993
+  static constexpr const uint64_t a = 48271;
+  static constexpr const uint64_t c = 0;
+  static constexpr const uint64_t m = 2147483647;
+  static uint64_t seed = 123456789;
+  seed = (a * seed + c) % m;
+  return seed;
+}
+
+static void Randomize(cpp::MutableArrayRef<char> buffer) {
+  for (auto &current : buffer)
+    current = GetRandomChar();
+}
+
+template <size_t Size> static Buffer<Size> GetRandomBuffer() {
+  Buffer<Size> buffer;
+  Randomize(buffer);
+  return buffer;
+}
+
+template <typename Backend, size_t Size> struct Conf {
+  static_assert(Backend::IS_BACKEND_TYPE);
+  using BufferT = Buffer<Size>;
+  using T = typename Backend::template getNextType<Size>;
+  static_assert(sizeof(T) == Size);
+  static constexpr size_t SIZE = Size;
+
+  static BufferT splat(ubyte value) {
+    return bit_cast<BufferT>(Backend::template splat<T>(value));
+  }
+
+  static uint64_t notEquals(const BufferT &v1, const BufferT &v2) {
+    return Backend::template notEquals<T>(bit_cast<T>(v1), bit_cast<T>(v2));
+  }
+
+  static int32_t threeWayCmp(const BufferT &v1, const BufferT &v2) {
+    return Backend::template threeWayCmp<T>(bit_cast<T>(v1), bit_cast<T>(v2));
+  }
+};
+
+using FunctionTypes = testing::TypeList< //
+#if defined(LLVM_LIBC_ARCH_X86)          //
+    Conf<X86Backend, 1>,                 //
+    Conf<X86Backend, 2>,                 //
+    Conf<X86Backend, 4>,                 //
+    Conf<X86Backend, 8>,                 //
+#if HAS_M128
+    Conf<X86Backend, 16>, //
+#endif
+#if HAS_M256
+    Conf<X86Backend, 32>, //
+#endif
+#if HAS_M512
+    Conf<X86Backend, 64>, //
+#endif
+#endif                      // defined(LLVM_LIBC_ARCH_X86)
+    Conf<Scalar64BitBackend, 1>, //
+    Conf<Scalar64BitBackend, 2>, //
+    Conf<Scalar64BitBackend, 4>, //
+    Conf<Scalar64BitBackend, 8>  //
+    >;
+
+TYPED_TEST(LlvmLibcMemoryBackend, splat, FunctionTypes) {
+  for (auto value : cpp::Array<uint8_t, 3>{0u, 1u, 255u}) {
+    alignas(64) const auto stored = ParamType::splat(bit_cast<ubyte>(value));
+    for (size_t i = 0; i < ParamType::SIZE; ++i)
+      EXPECT_EQ(bit_cast<uint8_t>(stored[i]), value);
+  }
+}
+
+TYPED_TEST(LlvmLibcMemoryBackend, notEquals, FunctionTypes) {
+  alignas(64) const auto a = GetRandomBuffer<ParamType::SIZE>();
+  EXPECT_EQ(ParamType::notEquals(a, a), 0UL);
+  for (size_t i = 0; i < a.size(); ++i) {
+    alignas(64) auto b = a;
+    ++b[i];
+    EXPECT_NE(ParamType::notEquals(a, b), 0UL);
+    EXPECT_NE(ParamType::notEquals(b, a), 0UL);
+  }
+}
+
+TYPED_TEST(LlvmLibcMemoryBackend, threeWayCmp, FunctionTypes) {
+  alignas(64) const auto a = GetRandomBuffer<ParamType::SIZE>();
+  EXPECT_EQ(ParamType::threeWayCmp(a, a), 0);
+  for (size_t i = 0; i < a.size(); ++i) {
+    alignas(64) auto b = a;
+    ++b[i];
+    const auto cmp = memcmp(&a, &b, sizeof(a));
+    ASSERT_NE(cmp, 0);
+    if (cmp > 0) {
+      EXPECT_GT(ParamType::threeWayCmp(a, b), 0);
+      EXPECT_LT(ParamType::threeWayCmp(b, a), 0);
+    } else {
+      EXPECT_LT(ParamType::threeWayCmp(a, b), 0);
+      EXPECT_GT(ParamType::threeWayCmp(b, a), 0);
+    }
+  }
+}
+
+template <typename Backend, size_t Size, Temporality TS, Aligned AS>
+struct LoadStoreConf {
+  static_assert(Backend::IS_BACKEND_TYPE);
+  using BufferT = Buffer<Size>;
+  using T = typename Backend::template getNextType<Size>;
+  static_assert(sizeof(T) == Size);
+  static constexpr size_t SIZE = Size;
+
+  static BufferT load(const BufferT &ref) {
+    const auto *ptr = bit_cast<const T *>(ref.data());
+    const T value = Backend::template load<T, TS, AS>(ptr);
+    return bit_cast<BufferT>(value);
+  }
+
+  static void store(BufferT &ref, const BufferT value) {
+    auto *ptr = bit_cast<T *>(ref.data());
+    Backend::template store<T, TS, AS>(ptr, bit_cast<T>(value));
+  }
+};
+
+using LoadStoreTypes = testing::TypeList<                              //
+#if defined(LLVM_LIBC_ARCH_X86)                                        //
+    LoadStoreConf<X86Backend, 1, Temporality::TEMPORAL, Aligned::NO>,  //
+    LoadStoreConf<X86Backend, 1, Temporality::TEMPORAL, Aligned::YES>, //
+    LoadStoreConf<X86Backend, 2, Temporality::TEMPORAL, Aligned::NO>,  //
+    LoadStoreConf<X86Backend, 2, Temporality::TEMPORAL, Aligned::YES>, //
+    LoadStoreConf<X86Backend, 4, Temporality::TEMPORAL, Aligned::NO>,  //
+    LoadStoreConf<X86Backend, 4, Temporality::TEMPORAL, Aligned::YES>, //
+    LoadStoreConf<X86Backend, 8, Temporality::TEMPORAL, Aligned::NO>,  //
+    LoadStoreConf<X86Backend, 8, Temporality::TEMPORAL, Aligned::YES>, //
+#if HAS_M128
+    LoadStoreConf<X86Backend, 16, Temporality::TEMPORAL, Aligned::NO>,      //
+    LoadStoreConf<X86Backend, 16, Temporality::TEMPORAL, Aligned::YES>,     //
+    LoadStoreConf<X86Backend, 16, Temporality::NON_TEMPORAL, Aligned::YES>, //
+#endif
+#if HAS_M256
+    LoadStoreConf<X86Backend, 32, Temporality::TEMPORAL, Aligned::NO>,      //
+    LoadStoreConf<X86Backend, 32, Temporality::TEMPORAL, Aligned::YES>,     //
+    LoadStoreConf<X86Backend, 32, Temporality::NON_TEMPORAL, Aligned::YES>, //
+#endif
+#if HAS_M512
+    LoadStoreConf<X86Backend, 64, Temporality::TEMPORAL, Aligned::NO>,      //
+    LoadStoreConf<X86Backend, 64, Temporality::TEMPORAL, Aligned::YES>,     //
+    LoadStoreConf<X86Backend, 64, Temporality::NON_TEMPORAL, Aligned::YES>, //
+#endif
+#endif // defined(LLVM_LIBC_ARCH_X86)
+    LoadStoreConf<Scalar64BitBackend, 1, Temporality::TEMPORAL, Aligned::NO>, //
+    LoadStoreConf<Scalar64BitBackend, 1, Temporality::TEMPORAL,
+                  Aligned::YES>,                                              //
+    LoadStoreConf<Scalar64BitBackend, 2, Temporality::TEMPORAL, Aligned::NO>, //
+    LoadStoreConf<Scalar64BitBackend, 2, Temporality::TEMPORAL,
+                  Aligned::YES>,                                              //
+    LoadStoreConf<Scalar64BitBackend, 4, Temporality::TEMPORAL, Aligned::NO>, //
+    LoadStoreConf<Scalar64BitBackend, 4, Temporality::TEMPORAL,
+                  Aligned::YES>,                                              //
+    LoadStoreConf<Scalar64BitBackend, 8, Temporality::TEMPORAL, Aligned::NO>, //
+    LoadStoreConf<Scalar64BitBackend, 8, Temporality::TEMPORAL, Aligned::YES> //
+    >;
+
+TYPED_TEST(LlvmLibcMemoryBackend, load, LoadStoreTypes) {
+  alignas(64) const auto expected = GetRandomBuffer<ParamType::SIZE>();
+  const auto loaded = ParamType::load(expected);
+  for (size_t i = 0; i < ParamType::SIZE; ++i)
+    EXPECT_EQ(loaded[i], expected[i]);
+}
+
+TYPED_TEST(LlvmLibcMemoryBackend, store, LoadStoreTypes) {
+  alignas(64) const auto expected = GetRandomBuffer<ParamType::SIZE>();
+  alignas(64) typename ParamType::BufferT stored;
+  ParamType::store(stored, expected);
+  for (size_t i = 0; i < ParamType::SIZE; ++i)
+    EXPECT_EQ(stored[i], expected[i]);
+}
+
+} // namespace __llvm_libc