[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

1

Missing header (same above).

libc/src/string/memory_utils/backends.h

12

"native loads and stores", right ?

36

[Nit]sentences.

libc/src/string/memory_utils/sized_op.h

11

whose

37

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

39

What about overlapping operations ?

47

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

47

doc ?

55

ditto

62

doc ?

99

is_different or differs ?

102

> 0

103

The non-short-circuiting | warrants a comment.

116

?

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

13

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

39

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.

47

I went with nativeLoad/nativeStore as discussed offline

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

13

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

[gchatelet]

• Address comments

[gchatelet]

• Rename backend

[courbet]

libc/src/string/memory_utils/sized_op.h

138

?

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

2

Header ?

[gchatelet]

• Address comments

libc/src/string/memory_utils/backend_aarch64.h

+#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 {
+
+// Specific implementation of the SizedOp abstraction for the set operation
+// using `dc zva`. A runtime check with `hasZva` is necessary before using this
+// operation.
+struct Zva64 {
+  static constexpr size_t SIZE = 64;
+
+  template <typename DstAddrT>
+  static inline void set(DstAddrT dst, ubyte value) {
+    static_assert(DstAddrT::ALIGNMENT >= 64);
+    void *const dst_ptr = as<void>(dst);
+#if __SIZEOF_POINTER__ == 4
+    asm("dc zva, %w[dst]" : : [dst] "r"(dst_ptr) : "memory");
+#else
+    asm("dc zva, %[dst]" : : [dst] "r"(dst_ptr) : "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 lines check whether the instruction is permitted and block size
+  // is 16 words (i.e. 64 bytes).
+  constexpr uint64_t dzp_mask = 0b1'0000;
+  constexpr uint64_t dzp_permitted = 0b0'0000;
+  constexpr uint64_t bs_mask = 0b1111;
+  constexpr uint64_t bs_is_64b = 0b100;
+  const uint64_t dzp_value = zva_val & dzp_mask;
+  const uint64_t bs_value = zva_val & bs_mask;
+  return (dzp_value == dzp_permitted) && (bs_value == bs_is_64b);
+}
+
+namespace aarch64 {
+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 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

+#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 not_equals(T v1, T v2) {
+    static_assert(IsScalarType<T>);
+    return v1 ^ v2;
+  }
+
+  template <typename T> static inline int32_t three_way_cmp(T v1, T v2) {
+    DeferredStaticAssert("not implemented");
+  }
+
+  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::three_way_cmp<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::three_way_cmp<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::three_way_cmp<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::three_way_cmp<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

+#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;
+
+  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);
+  }
+
+  template <
+      typename T, Temporality TS, Aligned AS,
+      cpp::EnableIfType<!Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline T load(const T *src) {
+    DeferredStaticAssert("X86 non-temporal load needs aligned access");
+    return {};
+  }
+
+  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);
+  }
+
+  template <
+      typename T, Temporality TS, Aligned AS,
+      cpp::EnableIfType<!Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline void store(T *dst, T value) {
+    DeferredStaticAssert("X86 non-temporal store needs aligned access");
+  }
+
+  template <typename T> static inline T splat(ubyte value) {
+    return Scalar64BitBackend::template splat<T>(value);
+  }
+
+  template <typename T> static inline uint64_t not_equals(T v1, T v2) {
+    return Scalar64BitBackend::template not_equals<T>(v1, v2);
+  }
+
+  template <typename T,
+            cpp::EnableIfType<Scalar64BitBackend::IsScalarType<T>, bool> = true>
+  static inline int32_t three_way_cmp(T v1, T v2) {
+    return Scalar64BitBackend::template three_way_cmp<T>(v1, v2);
+  }
+
+  template <typename T, cpp::EnableIfType<!Scalar64BitBackend::IsScalarType<T>,
+                                          bool> = true>
+  static inline int32_t three_way_cmp(T v1, T v2) {
+    return char_diff(reinterpret_cast<char *>(&v1),
+                     reinterpret_cast<char *>(&v2), not_equals(v1, v2));
+  }
+
+  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 = __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)
+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)
+template <> inline __m128i X86Backend::splat<__m128i>(ubyte value) {
+  return _mm_set1_epi8(__builtin_bit_cast(char, value));
+}
+template <>
+inline uint64_t X86Backend::not_equals<__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)
+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)
+template <> inline __m256i X86Backend::splat<__m256i>(ubyte value) {
+  return _mm256_set1_epi8(__builtin_bit_cast(char, value));
+}
+template <>
+inline uint64_t X86Backend::not_equals<__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)
+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)
+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::not_equals<__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 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"  // ubyte, 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;
+  // load
+  template <typename T, Temporality, Aligned> static T load(const T *src);
+
+  // store
+  template <typename T, Temporality, Aligned>
+  static void store(T *dst, T value);
+
+  // return a T filled with `value`
+  template <typename T> static T splat(ubyte value);
+
+  // returns zero iff v1 == v2
+  template <typename T> static uint64_t not_equals(T v1, T v2);
+
+  // returns zero iff v1 == v2, -1 if v1 < v2 and 1 otherwise.
+  template <typename T> static int32_t three_way_diff(T v1, T v2);
+
+  // returns which type should be used to consume Size bytes.
+  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 which 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
+
+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>;
+
+  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;
+  }
+
+  template <typename SrcAddrT> static inline auto loadType(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));
+  }
+
+  template <typename DstAddrT>
+  static inline void storeType(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);
+  }
+
+  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;
+    }
+    storeType(loadType(src), dst);
+    if constexpr (NEXT_SIZE)
+      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 = loadType(src);
+    if constexpr (NEXT_SIZE)
+      NextBlock::move(offsetAddr<TYPE_SIZE>(dst), offsetAddr<TYPE_SIZE>(src));
+    storeType(payload, dst);
+  }
+
+  template <typename DstAddrT>
+  static inline void set(DstAddrT dst, ubyte value) {
+    storeType(Backend::template splat<type>(value), dst);
+    if constexpr (NEXT_SIZE)
+      NextBlock::set(offsetAddr<TYPE_SIZE>(dst), value);
+  }
+
+  template <typename SrcAddrT1, typename SrcAddrT2>
+  static inline uint64_t different(SrcAddrT1 src1, SrcAddrT2 src2) {
+    const uint64_t current =
+        Backend::template not_equals<type>(loadType(src1), loadType(src2));
+    if constexpr (NEXT_SIZE) {
+      return current | (NextBlock::different(offsetAddr<TYPE_SIZE>(src1),
+                                             offsetAddr<TYPE_SIZE>(src2)));
+    } else {
+      return current;
+    }
+  }
+
+  template <typename SrcAddrT1, typename SrcAddrT2>
+  static inline int32_t three_way_cmp(SrcAddrT1 src1, SrcAddrT2 src2) {
+    const auto a = loadType(src1);
+    const auto b = loadType(src2);
+    if (Backend::template not_equals<type>(a, b))
+      return Backend::template three_way_cmp<type>(a, b);
+    // if (int32_t res = three_way_cmp<T>(a, b)) {
+    //   return res;
+    // }
+    if constexpr (NEXT_SIZE)
+      return NextBlock::three_way_cmp(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() {
+  static constexpr const uint64_t a = 1103515245;
+  static constexpr const uint64_t c = 12345;
+  static constexpr const uint64_t m = 1ULL << 31;
+  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 TestBackend {
+  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;
+
+  // returns the splatted type as a BufferT.
+  static BufferT splat(ubyte value) {
+    return bit_cast<BufferT>(Backend::template splat<T>(value));
+  }
+
+  // Turns BufferT into T and delegates to Backend::not_equals.
+  static uint64_t not_equals(const BufferT &v1, const BufferT &v2) {
+    return Backend::template not_equals<T>(bit_cast<T>(v1), bit_cast<T>(v2));
+  }
+
+  // Turns BufferT into T and delegates to Backend::three_way_cmp.
+  static int32_t three_way_cmp(const BufferT &v1, const BufferT &v2) {
+    return Backend::template three_way_cmp<T>(bit_cast<T>(v1), bit_cast<T>(v2));
+  }
+};
+
+using BackendTypes = testing::TypeList< //
+#if defined(LLVM_LIBC_ARCH_AARCH64)
+    TestBackend<Aarch64Backend, 1>, //
+    TestBackend<Aarch64Backend, 2>, //
+    TestBackend<Aarch64Backend, 4>, //
+    TestBackend<Aarch64Backend, 8>, //
+#endif
+#if defined(LLVM_LIBC_ARCH_X86) //
+    TestBackend<X86Backend, 1>, //
+    TestBackend<X86Backend, 2>, //
+    TestBackend<X86Backend, 4>, //
+    TestBackend<X86Backend, 8>, //
+#if HAS_M128
+    TestBackend<X86Backend, 16>, //
+#endif
+#if HAS_M256
+    TestBackend<X86Backend, 32>, //
+#endif
+#if HAS_M512
+    TestBackend<X86Backend, 64>, //
+#endif
+#endif                             // defined(LLVM_LIBC_ARCH_X86)
+    TestBackend<Scalar64BitBackend, 1>, //
+    TestBackend<Scalar64BitBackend, 2>, //
+    TestBackend<Scalar64BitBackend, 4>, //
+    TestBackend<Scalar64BitBackend, 8>  //
+    >;
+
+TYPED_TEST(LlvmLibcMemoryBackend, splat, BackendTypes) {
+  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, not_equals, BackendTypes) {
+  alignas(64) const auto a = GetRandomBuffer<ParamType::SIZE>();
+  EXPECT_EQ(ParamType::not_equals(a, a), 0UL);
+  for (size_t i = 0; i < a.size(); ++i) {
+    alignas(64) auto b = a;
+    ++b[i];
+    EXPECT_NE(ParamType::not_equals(a, b), 0UL);
+    EXPECT_NE(ParamType::not_equals(b, a), 0UL);
+  }
+}
+
+TYPED_TEST(LlvmLibcMemoryBackend, three_way_cmp, BackendTypes) {
+  alignas(64) const auto a = GetRandomBuffer<ParamType::SIZE>();
+  EXPECT_EQ(ParamType::three_way_cmp(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::three_way_cmp(a, b), 0);
+      EXPECT_LT(ParamType::three_way_cmp(b, a), 0);
+    } else {
+      EXPECT_LT(ParamType::three_way_cmp(a, b), 0);
+      EXPECT_GT(ParamType::three_way_cmp(b, a), 0);
+    }
+  }
+}
+
+template <typename Backend, size_t Size, Temporality TS, Aligned AS>
+struct LdStBackend {
+  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 LoadStoreBackends = testing::TypeList<                         //
+#if defined(LLVM_LIBC_ARCH_X86)                                      //
+    LdStBackend<X86Backend, 1, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<X86Backend, 1, Temporality::TEMPORAL, Aligned::YES>, //
+    LdStBackend<X86Backend, 2, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<X86Backend, 2, Temporality::TEMPORAL, Aligned::YES>, //
+    LdStBackend<X86Backend, 4, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<X86Backend, 4, Temporality::TEMPORAL, Aligned::YES>, //
+    LdStBackend<X86Backend, 8, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<X86Backend, 8, Temporality::TEMPORAL, Aligned::YES>, //
+#if HAS_M128
+    LdStBackend<X86Backend, 16, Temporality::TEMPORAL, Aligned::NO>,      //
+    LdStBackend<X86Backend, 16, Temporality::TEMPORAL, Aligned::YES>,     //
+    LdStBackend<X86Backend, 16, Temporality::NON_TEMPORAL, Aligned::YES>, //
+#endif
+#if HAS_M256
+    LdStBackend<X86Backend, 32, Temporality::TEMPORAL, Aligned::NO>,      //
+    LdStBackend<X86Backend, 32, Temporality::TEMPORAL, Aligned::YES>,     //
+    LdStBackend<X86Backend, 32, Temporality::NON_TEMPORAL, Aligned::YES>, //
+#endif
+#if HAS_M512
+    LdStBackend<X86Backend, 64, Temporality::TEMPORAL, Aligned::NO>,      //
+    LdStBackend<X86Backend, 64, Temporality::TEMPORAL, Aligned::YES>,     //
+    LdStBackend<X86Backend, 64, Temporality::NON_TEMPORAL, Aligned::YES>, //
+#endif
+#endif // defined(LLVM_LIBC_ARCH_X86)
+#if defined(LLVM_LIBC_ARCH_AARCH64)
+    LdStBackend<Aarch64Backend, 1, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<Aarch64Backend, 1, Temporality::TEMPORAL, Aligned::YES>, //
+    LdStBackend<Aarch64Backend, 2, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<Aarch64Backend, 2, Temporality::TEMPORAL, Aligned::YES>, //
+    LdStBackend<Aarch64Backend, 4, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<Aarch64Backend, 4, Temporality::TEMPORAL, Aligned::YES>, //
+    LdStBackend<Aarch64Backend, 8, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<Aarch64Backend, 8, Temporality::TEMPORAL, Aligned::YES>, //
+#endif
+    LdStBackend<Scalar64BitBackend, 1, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<Scalar64BitBackend, 1, Temporality::TEMPORAL, Aligned::YES>, //
+    LdStBackend<Scalar64BitBackend, 2, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<Scalar64BitBackend, 2, Temporality::TEMPORAL, Aligned::YES>, //
+    LdStBackend<Scalar64BitBackend, 4, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<Scalar64BitBackend, 4, Temporality::TEMPORAL, Aligned::YES>, //
+    LdStBackend<Scalar64BitBackend, 8, Temporality::TEMPORAL, Aligned::NO>,  //
+    LdStBackend<Scalar64BitBackend, 8, Temporality::TEMPORAL, Aligned::YES>  //
+    >;
+
+TYPED_TEST(LlvmLibcMemoryBackend, load, LoadStoreBackends) {
+  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, LoadStoreBackends) {
+  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