[libc] Add a set of elementary operations

[gchatelet]

Summary

Each of these elementary operations can be assembled to support higher order constructs (Overlapping access, Loop, Aligned Loop).
The patch does not compile yet as it depends on other ones (D100571, D100631) but it allows to get the conversation started.

A self-contained version of this code is available at https://godbolt.org/z/e1x6xdaxM

[gchatelet]

libc/src/string/memory_utils/elements.h

155–167

@avieira the generated code is not that bad but maybe you can come up with a better idea?

The challenge here is to keep the semantic of the 3-way comparison that fits in an int while working on types which diff is larger than int.

Generated code:
intel : https://godbolt.org/z/Khxv6b3r9
arm : https://godbolt.org/z/YTah338hY

190–206

@avieira for the vector version of the three way compare we compute the byte-wise not equal mask, convert this mask to GPR and look at the number of trailing zeros (X86 is LittleEndian), this number is the index of the mismatching byte.

After trying to work on the vector directly to extract this byte I figured out it's easier to just reload it, it should be fast and probably faster than a bunch of vector operations.

i suspect the same approach will work for ARM as well, WDYT?

[gchatelet]

• Added Tail/HeadTail strategies and tests

Once the Loop strategies are added the framework will be useable.

[gchatelet]

• Added Tail/HeadTail strategies and tests
• Added Loop and AlignedLoop

[avieira]

libc/src/string/memory_utils/elements.h

155–167

@gchatelet Avoiding the subtraction and comparing the 'la' and 'lb' variables directly lead to better codegen on AArch64.

190–206

@gchatelet I did not look at using NEON. The problem with the mask approach is that NEON does not have movemask-like instructions, so finding the first mismatched byte on a vector would require more work than it is worth it I think. SVE2 might help us here in the future though.

[avieira]

I'm going to try to rewrite my memcmp implementation using these now and report findings as I go through it :).

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

13

AArch64 doesn't support -march=native, we use -mcpu=native instead, so it would be good to specify the correct option per target.

[gchatelet]

In D100646#2712200, @avieira wrote:

I'm going to try to rewrite my memcmp implementation using these now and report findings as I go through it :).

FYI I'll upload a new version in a few minutes that showcase the API. Nothing radically different but it may help to wait a bit.

Keep the comments coming!

[avieira]

Alright I'll give it a wait, I was currently trying to figure out why I can't build the libc_string_unittests, getting a build error around elements_test.cpp saying there's an issue with the 'cstring' header file 'no member named 'strcmp' in the global namespace' which is an odd one ... What libc++ library do you use to build this normally?

[gchatelet]

• Use new API with memset and memcpy, more tests and addition of an element relying on builtins.

[gchatelet]

In D100646#2712262, @avieira wrote:

Alright I'll give it a wait, I was currently trying to figure out why I can't build the libc_string_unittests, getting a build error around elements_test.cpp saying there's an issue with the 'cstring' header file 'no member named 'strcmp' in the global namespace' which is an odd one ... What libc++ library do you use to build this normally?

hmm this is weird, elements_test.cpp does not rely on strcmp. That said it shouldn't even depend on "cstring", I'll update the patch to remove it.

[gchatelet]

• Remove unneeded cstring header from elements_test.cpp

[gchatelet]

• Better selection of buffer alignment for AlignedLoop

[gchatelet]

• Align on destination buffer for x86 and use 32 byte alignment.

[gchatelet]

• Changed AlignedLoop to Align::Then<Loop>
• Updated 3-way cmp for scalar 32/64 bits
• Added disclaimer for builtin operations
• Updated tests and implementations

[gchatelet]

libc/src/string/memory_utils/elements.h

155–167

Indeed it's better, thank you.

190–206

We can add an arm specialization as I did for x86 if needed, let's keep it as-is for now.

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

13

Thx I wasn't aware of this. I found this article, it's helpful and confusing at the same time :-D
https://community.arm.com/developer/tools-software/tools/b/tools-software-ides-blog/posts/compiler-flags-across-architectures-march-mtune-and-mcpu

@sivachandra should we define a new CMake macro or do you think this should be part of add_libc_unittest?
The aim is to use whatever is available on the host machine when performing the tests.

[sivachandra]

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

13

@sivachandra should we define a new CMake macro or do you think this should be part of add_libc_unittest?
The aim is to use whatever is available on the host machine when performing the tests.

I suppose you are asking about adding -march=native and -mcpu=native? If yes, then I think we should add a top-level var like LLVM_LIBC_COMMON_COMPILE_OPTIONS which get set to the appropriate value based on the target machine. And then, both add_entrypoint_object and add_libc_unittest should use it.

[avieira]

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

13

@gchatelet I didn't quite understand why only use -march/-mcpu during the tests and not for the benchmarking for instance. @sivachandra approach sounds better to me.

As for the options, I think the simple (but maybe somewhat naive) explanation is '-march': determines what features are available, '-mtune': sets the micro-architecture tuning strategy and '-mcpu' set's both for the micro-architecture you pass it. When you pass native it tries to autodetect the micro-architecture.

[gchatelet]

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

13

@gchatelet I didn't quite understand why only use -march/-mcpu during the tests and not for the benchmarking for instance.

We should. All of this is work in progress. I'll start a patch to address this.

1. If llvm-libc source code is part of the code base being compiled it definitely makes sense to set the micro-architecture and leverage available features.
2. In the case of shared library though we may have to provide several implementations and do runtime dispatch, if so, the tests must run all configurations up to what's available on the host.

I believe that we can stick to 1 for now. WDYT @sivachandra ?

[gchatelet]

• rebase and reorder a few lines

[gchatelet]

• Remove explicit -march from unittests

[gchatelet]

I think this is ready to land.
Concerns about march/mcpu have been addressed as separate patches D101524, D101991, D102233.

Let me know if you have any other questions/suggestions before I submit.

[gchatelet]

• Fix missing namespace qualifiers

[lebedev.ri]

libc/src/string/CMakeLists.txt

197

Passing-by comment: why is this here?
This enforces clang/LLVM as the compiler used to build this library.

[gchatelet]

libc/src/string/CMakeLists.txt

197

Passing-by comment: why is this here?
This enforces clang/LLVM as the compiler used to build this library.

Thx for the comment, yes this should be guarded somehow. It's in my TODO list.

libc/src/string/CMakeLists.txt

cmake_parse_arguments(
     "" # Single value arguments
     "REQUIRE;SRCS;HDRS;DEPENDS;COMPILE_OPTIONS" # Multi value arguments
     ${ARGN})
   add_entrypoint_object(${impl_name}
     NAME ${name}
     SRCS ${ADD_IMPL_SRCS}
     HDRS ${ADD_IMPL_HDRS}
     DEPENDS ${ADD_IMPL_DEPENDS}
-    COMPILE_OPTIONS ${ADD_IMPL_COMPILE_OPTIONS}
+    COMPILE_OPTIONS ${ADD_IMPL_COMPILE_OPTIONS} "SHELL:-mllvm -combiner-global-alias-analysis"
   )
   get_fq_target_name(${impl_name} fq_target_name)
   set_target_properties(${fq_target_name} PROPERTIES REQUIRE_CPU_FEATURES "${ADD_IMPL_REQUIRE}")
   set_property(GLOBAL APPEND PROPERTY "${name}_implementations" "${fq_target_name}")
 endfunction()
 
 # ------------------------------------------------------------------------------
 # memcpy

libc/src/string/aarch64/memcpy.cpp

 //===-- Implementation of memcpy ------------------------------------------===//
 //
 // 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 "src/string/memcpy.h"
 #include "src/__support/common.h"
-#include "src/string/memory_utils/memcpy_utils.h"
+#include "src/string/memory_utils/elements.h"
 
 namespace __llvm_libc {
 
+using _1 = scalar::UINT8;
+using _2 = scalar::UINT16;
+using _3 = Chained<scalar::UINT16, scalar::UINT8>;
+using _4 = scalar::UINT32;
+using _8 = scalar::UINT64;
+using _16 = Repeated<scalar::UINT64, 2>;
+using _32 = Repeated<scalar::UINT64, 4>;
+using _64 = Repeated<scalar::UINT64, 8>;
+
 // Design rationale
 // ================
 //
 // Using a profiler to observe size distributions for calls into libc
 // functions, it was found most operations act on a small number of bytes.
 // This makes it important to favor small sizes.
 //
 // We have used __builtin_expect to tell the compiler to favour lower sizes as

 // - As compilers and processors get better, the generated code is improved
 //   with little change on the code side.
 // This implementation has been tuned for Neoverse-N1.
 static void memcpy_aarch64(char *__restrict dst, const char *__restrict src,
                            size_t count) {
   if (count == 0)
     return;
   if (count == 1)
-    return CopyBlock<1>(dst, src);
+    return Copy<_1>(dst, src);
   if (count == 2)
-    return CopyBlock<2>(dst, src);
+    return Copy<_2>(dst, src);
   if (count == 3)
-    return CopyBlock<3>(dst, src);
+    return Copy<_3>(dst, src);
   if (count == 4)
-    return CopyBlock<4>(dst, src);
+    return Copy<_4>(dst, src);
   if (count < 8)
-    return CopyBlockOverlap<4>(dst, src, count);
+    return Copy<HeadTail<_4>>(dst, src, count);
   if (count < 16)
-    return CopyBlockOverlap<8>(dst, src, count);
+    return Copy<HeadTail<_8>>(dst, src, count);
   if (count < 32)
-    return CopyBlockOverlap<16>(dst, src, count);
+    return Copy<HeadTail<_16>>(dst, src, count);
   if (count < 64)
-    return CopyBlockOverlap<32>(dst, src, count);
+    return Copy<HeadTail<_32>>(dst, src, count);
   if (count < 128)
-    return CopyBlockOverlap<64>(dst, src, count);
-  return CopySrcAlignedBlocks<64, 16>(dst, src, count);
+    return Copy<HeadTail<_64>>(dst, src, count);
+  return Copy<Align<_16, Arg::Src>::Then<Loop<_64>>>(dst, src, count);
 }
 
 LLVM_LIBC_FUNCTION(void *, memcpy,
                    (void *__restrict dst, const void *__restrict src,
                     size_t size)) {
   memcpy_aarch64(reinterpret_cast<char *>(dst),
                  reinterpret_cast<const char *>(src), size);
   return dst;
 }
 
 } // namespace __llvm_libc

libc/src/string/memcpy.cpp

 //===-- Implementation of memcpy ------------------------------------------===//
 //
 // 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 "src/string/memcpy.h"
 #include "src/__support/common.h"
-#include "src/string/memory_utils/memcpy_utils.h"
+#include "src/string/memory_utils/elements.h"
 
 namespace __llvm_libc {
 
 // Design rationale
 // ================
 //
 // Using a profiler to observe size distributions for calls into libc
 // functions, it was found most operations act on a small number of bytes.
 // This makes it important to favor small sizes.
 //
 // The tests for `count` are in ascending order so the cost of branching is
 // proportional to the cost of copying.
 //
 // The function is written in C++ for several reasons:
 // - The compiler can __see__ the code, this is useful when performing Profile
 //   Guided Optimization as the optimized code can take advantage of branching
 //   probabilities.
 // - It also allows for easier customization and favors testing multiple
 //   implementation parameters.
 // - As compilers and processors get better, the generated code is improved
 //   with little change on the code side.
 static void memcpy_impl(char *__restrict dst, const char *__restrict src,
                         size_t count) {
+  // Use scalar strategies (_1, _2, _3 ...)
+  using namespace __llvm_libc::scalar;
+
   if (count == 0)
     return;
   if (count == 1)
-    return CopyBlock<1>(dst, src);
+    return Copy<_1>(dst, src);
   if (count == 2)
-    return CopyBlock<2>(dst, src);
+    return Copy<_2>(dst, src);
   if (count == 3)
-    return CopyBlock<3>(dst, src);
+    return Copy<_3>(dst, src);
   if (count == 4)
-    return CopyBlock<4>(dst, src);
+    return Copy<_4>(dst, src);
   if (count < 8)
-    return CopyBlockOverlap<4>(dst, src, count);
+    return Copy<HeadTail<_4>>(dst, src, count);
   if (count < 16)
-    return CopyBlockOverlap<8>(dst, src, count);
+    return Copy<HeadTail<_8>>(dst, src, count);
   if (count < 32)
-    return CopyBlockOverlap<16>(dst, src, count);
+    return Copy<HeadTail<_16>>(dst, src, count);
   if (count < 64)
-    return CopyBlockOverlap<32>(dst, src, count);
+    return Copy<HeadTail<_32>>(dst, src, count);
   if (count < 128)
-    return CopyBlockOverlap<64>(dst, src, count);
-  return CopySrcAlignedBlocks<32>(dst, src, count);
+    return Copy<HeadTail<_64>>(dst, src, count);
+  return Copy<Align<_32, Arg::Src>::Then<Loop<_32>>>(dst, src, count);
 }
 
 LLVM_LIBC_FUNCTION(void *, memcpy,
                    (void *__restrict dst, const void *__restrict src,
                     size_t size)) {
   memcpy_impl(reinterpret_cast<char *>(dst),
               reinterpret_cast<const char *>(src), size);
   return dst;
 }
 
 } // namespace __llvm_libc

libc/src/string/memory_utils/CMakeLists.txt

 add_header_library(
   memory_utils
   HDRS
     utils.h
-    memcpy_utils.h
-    memset_utils.h
+    elements.h
 )

libc/src/string/memory_utils/elements.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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_H
+
+#include <stddef.h> // size_t
+#include <stdint.h> // uint8_t, uint16_t, uint32_t, uint64_t
+
+#include "src/__support/endian.h"
+#include "src/string/memory_utils/utils.h"
+
+namespace __llvm_libc {
+
+// Elementary Operations
+// --------------------------------
+// We define abstract elementary operations acting on fixed chunks of memory.
+// These are low level building blocks that are meant to be assembled to compose
+// higher order abstractions. Each function is defined twice: once with
+// fixed-size operations, and once with runtime-size operations.
+
+// Fixed-size copies from 'src' to 'dst'.
+template <typename Element>
+void Copy(char *__restrict dst, const char *__restrict src) {
+  Element::Copy(dst, src);
+}
+// Runtime-size copies from 'src' to 'dst'.
+template <typename Element>
+void Copy(char *__restrict dst, const char *__restrict src, size_t size) {
+  Element::Copy(dst, src, size);
+}
+
+// Fixed-size equality between 'lhs' and 'rhs'.
+template <typename Element> bool Equals(const char *lhs, const char *rhs) {
+  return Element::Equals(lhs, rhs);
+}
+// Runtime-size equality between 'lhs' and 'rhs'.
+template <typename Element>
+bool Equals(const char *lhs, const char *rhs, size_t size) {
+  return Element::Equals(lhs, rhs, size);
+}
+
+// Fixed-size three-way comparison between 'lhs' and 'rhs'.
+template <typename Element>
+int ThreeWayCompare(const char *lhs, const char *rhs) {
+  return Element::ThreeWayCompare(lhs, rhs);
+}
+// Runtime-size three-way comparison between 'lhs' and 'rhs'.
+template <typename Element>
+int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) {
+  return Element::ThreeWayCompare(lhs, rhs, size);
+}
+
+// Fixed-size initialization.
+template <typename Element>
+void SplatSet(char *dst, const unsigned char value) {
+  Element::SplatSet(dst, value);
+}
+// Runtime-size initialization.
+template <typename Element>
+void SplatSet(char *dst, const unsigned char value, size_t size) {
+  Element::SplatSet(dst, value, size);
+}
+
+// Fixed-size Higher-Order Operations
+// ----------------------------------
+// - Repeated<Type, ElementCount>: Repeat the operation several times in a row.
+// - Chained<Types...>: Chain the operation of several types.
+
+// Repeat the operation several times in a row.
+template <typename Element, size_t ElementCount> struct Repeated {
+  static constexpr size_t kSize = ElementCount * Element::kSize;
+
+  static void Copy(char *__restrict dst, const char *__restrict src) {
+    for (size_t i = 0; i < ElementCount; ++i) {
+      const size_t offset = i * Element::kSize;
+      Element::Copy(dst + offset, src + offset);
+    }
+  }
+
+  static bool Equals(const char *lhs, const char *rhs) {
+    for (size_t i = 0; i < ElementCount; ++i) {
+      const size_t offset = i * Element::kSize;
+      if (!Element::Equals(lhs + offset, rhs + offset))
+        return false;
+    }
+    return true;
+  }
+
+  static int ThreeWayCompare(const char *lhs, const char *rhs) {
+    for (size_t i = 0; i < ElementCount; ++i) {
+      const size_t offset = i * Element::kSize;
+      // We make the assumption that 'Equals' si cheaper than 'ThreeWayCompare'.
+      if (Element::Equals(lhs + offset, rhs + offset))
+        continue;
+      return Element::ThreeWayCompare(lhs + offset, rhs + offset);
+    }
+    return 0;
+  }
+
+  static void SplatSet(char *dst, const unsigned char value) {
+    for (size_t i = 0; i < ElementCount; ++i) {
+      const size_t offset = i * Element::kSize;
+      Element::SplatSet(dst + offset, value);
+    }
+  }
+};
+
+// Chain the operation of several types.
+// For instance, to handle a 3 bytes operation, one can use:
+// Chained<UINT16, UINT8>::Operation();
+template <typename... Types> struct Chained;
+
+template <typename Head, typename... Tail> struct Chained<Head, Tail...> {
+  static constexpr size_t kSize = Head::kSize + Chained<Tail...>::kSize;
+
+  static void Copy(char *__restrict dst, const char *__restrict src) {
+    Chained<Tail...>::Copy(dst + Head::kSize, src + Head::kSize);
+    __llvm_libc::Copy<Head>(dst, src);
+  }
+
+  static bool Equals(const char *lhs, const char *rhs) {
+    if (!__llvm_libc::Equals<Head>(lhs, rhs))
+      return false;
+    return Chained<Tail...>::Equals(lhs + Head::kSize, rhs + Head::kSize);
+  }
+
+  static int ThreeWayCompare(const char *lhs, const char *rhs) {
+    if (__llvm_libc::Equals<Head>(lhs, rhs))
+      return Chained<Tail...>::ThreeWayCompare(lhs + Head::kSize,
+                                               rhs + Head::kSize);
+    return __llvm_libc::ThreeWayCompare<Head>(lhs, rhs);
+  }
+
+  static void SplatSet(char *dst, const unsigned char value) {
+    Chained<Tail...>::SplatSet(dst + Head::kSize, value);
+    __llvm_libc::SplatSet<Head>(dst, value);
+  }
+};
+
+template <> struct Chained<> {
+  static constexpr size_t kSize = 0;
+  static void Copy(char *__restrict dst, const char *__restrict src) {}
+  static bool Equals(const char *lhs, const char *rhs) { return true; }
+  static int ThreeWayCompare(const char *lhs, const char *rhs) { return 0; }
+  static void SplatSet(char *dst, const unsigned char value) {}
+};
+
+// Runtime-size Higher-Order Operations
+// ------------------------------------
+// - Tail<T>: Perform the operation on the last 'T::kSize' bytes of the buffer.
+// - HeadTail<T>: Perform the operation on the first and last 'T::kSize' bytes
+//   of the buffer.
+// - Loop<T>: Perform a loop of fixed-sized operations.
+
+// Perform the operation on the last 'T::kSize' bytes of the buffer.
+//
+// e.g. with
+// [1234567812345678123]
+// [__XXXXXXXXXXXXXX___]
+// [________XXXXXXXX___]
+//
+// Precondition: `size >= T::kSize`.
+template <typename T> struct Tail {
+  static void Copy(char *__restrict dst, const char *__restrict src,
+                   size_t size) {
+    return T::Copy(dst + offset(size), src + offset(size));
+  }
+
+  static bool Equals(const char *lhs, const char *rhs, size_t size) {
+    return T::Equals(lhs + offset(size), rhs + offset(size));
+  }
+
+  static int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) {
+    return T::ThreeWayCompare(lhs + offset(size), rhs + offset(size));
+  }
+
+  static void SplatSet(char *dst, const unsigned char value, size_t size) {
+    return T::SplatSet(dst + offset(size), value);
+  }
+
+  static size_t offset(size_t size) { return size - T::kSize; }
+};
+
+// Perform the operation on the first and last 'T::kSize' bytes of the buffer.
+// This is useful for overlapping operations.
+//
+// e.g. with
+// [1234567812345678123]
+// [__XXXXXXXXXXXXXX___]
+// [__XXXXXXXX_________]
+// [________XXXXXXXX___]
+//
+// Precondition: `size >= T::kSize && size <= 2 x T::kSize`.
+template <typename T> struct HeadTail {
+  static void Copy(char *__restrict dst, const char *__restrict src,
+                   size_t size) {
+    T::Copy(dst, src);
+    Tail<T>::Copy(dst, src, size);
+  }
+
+  static bool Equals(const char *lhs, const char *rhs, size_t size) {
+    if (!T::Equals(lhs, rhs))
+      return false;
+    return Tail<T>::Equals(lhs, rhs, size);
+  }
+
+  static int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) {
+    if (const int result = T::ThreeWayCompare(lhs, rhs))
+      return result;
+    return Tail<T>::ThreeWayCompare(lhs, rhs, size);
+  }
+
+  static void SplatSet(char *dst, const unsigned char value, size_t size) {
+    T::SplatSet(dst, value);
+    Tail<T>::SplatSet(dst, value, size);
+  }
+};
+
+// Simple loop ending with a Tail operation.
+//
+// e.g. with
+// [12345678123456781234567812345678]
+// [__XXXXXXXXXXXXXXXXXXXXXXXXXXXX___]
+// [__XXXXXXXX_______________________]
+// [__________XXXXXXXX_______________]
+// [__________________XXXXXXXX_______]
+// [______________________XXXXXXXX___]
+//
+// Precondition:
+// - size >= T::kSize
+template <typename T> struct Loop {
+  static void Copy(char *__restrict dst, const char *__restrict src,
+                   size_t size) {
+    for (size_t offset = 0; offset < size - T::kSize; offset += T::kSize)
+      T::Copy(dst + offset, src + offset);
+    Tail<T>::Copy(dst, src, size);
+  }
+
+  static bool Equals(const char *lhs, const char *rhs, size_t size) {
+    for (size_t offset = 0; offset < size - T::kSize; offset += T::kSize)
+      if (!T::Equals(lhs + offset, rhs + offset))
+        return false;
+    return Tail<T>::Equals(lhs, rhs, size);
+  }
+
+  static int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) {
+    for (size_t offset = 0; offset < size - T::kSize; offset += T::kSize)
+      if (const int result = T::ThreeWayCompare(lhs + offset, rhs + offset))
+        return result;
+    return Tail<T>::ThreeWayCompare(lhs, rhs, size);
+  }
+
+  static void SplatSet(char *dst, const unsigned char value, size_t size) {
+    for (size_t offset = 0; offset < size - T::kSize; offset += T::kSize)
+      T::SplatSet(dst + offset, value);
+    Tail<T>::SplatSet(dst, value, size);
+  }
+};
+
+enum class Arg { _1, _2, Dst = _1, Src = _2, Lhs = _1, Rhs = _2 };
+
+namespace internal {
+
+// Provides a specialized Bump function that adjusts pointers and size so first
+// argument (resp. second argument) gets aligned to Alignment.
+// We make sure the compiler knows about the adjusted pointer alignment.
+template <Arg arg, size_t Alignment> struct AlignHelper {};
+
+template <size_t Alignment> struct AlignHelper<Arg::_1, Alignment> {
+  template <typename T1, typename T2>
+  static void Bump(T1 *__restrict &p1ref, T2 *__restrict &p2ref, size_t &size) {
+    const intptr_t offset = offset_to_next_aligned<Alignment>(p1ref);
+    p1ref += offset;
+    p2ref += offset;
+    size -= offset;
+    p1ref = assume_aligned<Alignment>(p1ref);
+  }
+};
+
+template <size_t Alignment> struct AlignHelper<Arg::_2, Alignment> {
+  template <typename T1, typename T2>
+  static void Bump(T1 *__restrict &p1ref, T2 *__restrict &p2ref, size_t &size) {
+    const intptr_t offset = offset_to_next_aligned<Alignment>(p2ref);
+    p1ref += offset;
+    p2ref += offset;
+    size -= offset;
+    p2ref = assume_aligned<Alignment>(p2ref);
+  }
+};
+
+} // namespace internal
+
+// An alignment operation that:
+// - executes the 'AlignmentT' operation
+// - bumps 'dst' or 'src' (resp. 'lhs' or 'rhs') pointers so that the selected
+//   pointer gets aligned, size is decreased accordingly.
+// - calls the 'NextT' operation.
+//
+// e.g. A 16-byte Destination Aligned 32-byte Loop Copy can be written as:
+// Copy<Align<_16, Arg::Dst>::Then<Loop<_32>>>(dst, src, count);
+template <typename AlignmentT, Arg AlignOn> struct Align {
+private:
+  static constexpr size_t Alignment = AlignmentT::kSize;
+  static_assert(Alignment > 1, "Alignment must be more than 1");
+  static_assert(is_power2(Alignment), "Alignment must be a power of 2");
+
+public:
+  template <typename NextT> struct Then {
+    static void Copy(char *__restrict dst, const char *__restrict src,
+                     size_t size) {
+      AlignmentT::Copy(dst, src);
+      internal::AlignHelper<AlignOn, Alignment>::Bump(dst, src, size);
+      NextT::Copy(dst, src, size);
+    }
+
+    static bool Equals(const char *lhs, const char *rhs, size_t size) {
+      if (!AlignmentT::Equals(lhs, rhs))
+        return false;
+      internal::AlignHelper<AlignOn, Alignment>::Bump(lhs, rhs, size);
+      return NextT::Equals(lhs, rhs, size);
+    }
+
+    static int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) {
+      if (const int result = AlignmentT::ThreeWayCompare(lhs, rhs))
+        return result;
+      internal::AlignHelper<AlignOn, Alignment>::Bump(lhs, rhs, size);
+      return NextT::ThreeWayCompare(lhs, rhs, size);
+    }
+
+    static void SplatSet(char *dst, const unsigned char value, size_t size) {
+      AlignmentT::SplatSet(dst, value);
+      char *dummy = nullptr;
+      internal::AlignHelper<Arg::_1, Alignment>::Bump(dst, dummy, size);
+      NextT::SplatSet(dst, value, size);
+    }
+  };
+};
+
+// Fixed-size Builtin Operations
+// -----------------------------
+// Note: Do not use 'builtin' right now as it requires the implementation of the
+// `_inline` versions of all the builtins. Theoretically, Clang can still turn
+// them into calls to the C library leading to reentrancy problems.
+namespace builtin {
+template <size_t Size> struct Builtin {
+  static constexpr size_t kSize = Size;
+
+  static void Copy(char *__restrict dst, const char *__restrict src) {
+    __builtin_memcpy_inline(dst, src, kSize);
+  }
+
+  static bool Equals(const char *lhs, const char *rhs) {
+    return __builtin_memcmp(lhs, rhs, kSize) == 0;
+  }
+
+  static int ThreeWayCompare(const char *lhs, const char *rhs) {
+    return __builtin_memcmp(lhs, rhs, kSize);
+  }
+
+  static void SplatSet(char *dst, const unsigned char value) {
+    __builtin_memset(dst, value, kSize);
+  }
+};
+
+using _1 = Builtin<1>;
+using _2 = Builtin<2>;
+using _3 = Builtin<3>;
+using _4 = Builtin<4>;
+using _8 = Builtin<8>;
+using _16 = Builtin<16>;
+using _32 = Builtin<32>;
+using _64 = Builtin<64>;
+using _128 = Builtin<128>;
+
+} // namespace builtin
+
+// Fixed-size Scalar Operations
+// ----------------------------
+namespace scalar {
+
+// The Scalar type makes use of simple sized integers.
+template <typename T> struct Scalar {
+  static constexpr size_t kSize = sizeof(T);
+
+  static void Copy(char *__restrict dst, const char *__restrict src) {
+    Store(dst, Load(src));
+  }
+
+  static bool Equals(const char *lhs, const char *rhs) {
+    return Load(lhs) == Load(rhs);
+  }
+
+  static int ThreeWayCompare(const char *lhs, const char *rhs) {
+    return ScalarThreeWayCompare(Load(lhs), Load(rhs));
+  }
+
+  static void SplatSet(char *dst, const unsigned char value) {
+    Store(dst, GetSplattedValue(value));
+  }
+
+private:
+  static T Load(const char *ptr) {
+    T value;
+    __builtin_memcpy_inline(&value, ptr, kSize);
+    return value;
+  }
+  static void Store(char *ptr, T value) {
+    __builtin_memcpy_inline(ptr, &value, kSize);
+  }
+  static T GetSplattedValue(const unsigned char value) {
+    return T(~0) / T(0xFF) * T(value);
+  }
+  static int ScalarThreeWayCompare(T a, T b);
+};
+
+template <>
+inline int Scalar<uint8_t>::ScalarThreeWayCompare(uint8_t a, uint8_t b) {
+  const int16_t la = Endian::ToBigEndian(a);
+  const int16_t lb = Endian::ToBigEndian(b);
+  return la - lb;
+}
+template <>
+inline int Scalar<uint16_t>::ScalarThreeWayCompare(uint16_t a, uint16_t b) {
+  const int32_t la = Endian::ToBigEndian(a);
+  const int32_t lb = Endian::ToBigEndian(b);
+  return la - lb;
+}
+template <>
+inline int Scalar<uint32_t>::ScalarThreeWayCompare(uint32_t a, uint32_t b) {
+  const int64_t la = Endian::ToBigEndian(a);
+  const int64_t lb = Endian::ToBigEndian(b);
+  if (la < lb)
+    return -1;
+  if (la > lb)
+    return 1;
+  return 0;
+}
+template <>
+inline int Scalar<uint64_t>::ScalarThreeWayCompare(uint64_t a, uint64_t b) {
+  const __int128_t la = Endian::ToBigEndian(a);
+  const __int128_t lb = Endian::ToBigEndian(b);
+  if (la < lb)
+    return -1;
+  if (la > lb)
+    return 1;
+  return 0;
+}
+
+using UINT8 = Scalar<uint8_t>;   // 1 Byte
+using UINT16 = Scalar<uint16_t>; // 2 Bytes
+using UINT32 = Scalar<uint32_t>; // 4 Bytes
+using UINT64 = Scalar<uint64_t>; // 8 Bytes
+
+using _1 = UINT8;
+using _2 = UINT16;
+using _3 = Chained<UINT16, UINT8>;
+using _4 = UINT32;
+using _8 = UINT64;
+using _16 = Repeated<_8, 2>;
+using _32 = Repeated<_8, 4>;
+using _64 = Repeated<_8, 8>;
+using _128 = Repeated<_8, 16>;
+
+} // namespace scalar
+} // namespace __llvm_libc
+
+#include <src/string/memory_utils/elements_x86.h>
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_H

libc/src/string/memory_utils/elements_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_ELEMENTS_X86_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_X86_H
+
+#include <stddef.h> // size_t
+#include <stdint.h> // uint8_t, uint16_t, uint32_t, uint64_t
+
+#ifdef __SSE2__
+#include <immintrin.h>
+#endif //  __SSE2__
+
+#include "src/string/memory_utils/elements.h" // __llvm_libc::scalar
+
+// Fixed-size Vector Operations
+// ----------------------------
+
+namespace __llvm_libc {
+namespace x86 {
+
+#ifdef __SSE2__
+template <typename Base> struct Vector : public Base {
+  static void Copy(char *dst, const char *src) {
+    Base::Store(dst, Base::Load(src));
+  }
+
+  static bool Equals(const char *a, const char *b) {
+    return Base::NotEqualMask(Base::Load(a), Base::Load(b)) == 0;
+  }
+
+  static int ThreeWayCompare(const char *a, const char *b) {
+    const auto mask = Base::NotEqualMask(Base::Load(a), Base::Load(b));
+    if (!mask)
+      return 0;
+    return CharDiff(a, b, mask);
+  }
+
+  static void SplatSet(char *dst, const unsigned char value) {
+    Base::Store(dst, Base::GetSplattedValue(value));
+  }
+
+  static int CharDiff(const char *a, const char *b, uint64_t mask) {
+    const size_t diff_index = __builtin_ctzl(mask);
+    const int ca = (unsigned char)a[diff_index];
+    const int cb = (unsigned char)b[diff_index];
+    return ca - cb;
+  }
+};
+
+struct M128 {
+  static constexpr size_t kSize = 16;
+  using T = char __attribute__((__vector_size__(kSize)));
+  static uint16_t mask(T value) { return _mm_movemask_epi8(value); }
+  static uint16_t NotEqualMask(T a, T b) { return mask(a != b); }
+  static T Load(const char *ptr) {
+    return _mm_loadu_si128(reinterpret_cast<__m128i_u const *>(ptr));
+  }
+  static void Store(char *ptr, T value) {
+    return _mm_storeu_si128(reinterpret_cast<__m128i_u *>(ptr), value);
+  }
+  static T GetSplattedValue(const char v) {
+    const T splatted = {v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v};
+    return splatted;
+  }
+};
+
+using Vector128 = Vector<M128>; // 16 Bytes
+
+#ifdef __AVX2__
+struct M256 {
+  static constexpr size_t kSize = 32;
+  using T = char __attribute__((__vector_size__(kSize)));
+  static uint32_t mask(T value) { return _mm256_movemask_epi8(value); }
+  static uint32_t NotEqualMask(T a, T b) { return mask(a != b); }
+  static T Load(const char *ptr) {
+    return _mm256_loadu_si256(reinterpret_cast<__m256i const *>(ptr));
+  }
+  static void Store(char *ptr, T value) {
+    return _mm256_storeu_si256(reinterpret_cast<__m256i *>(ptr), value);
+  }
+  static T GetSplattedValue(const char v) {
+    const T splatted = {v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v,
+                        v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v};
+    return splatted;
+  }
+};
+
+using Vector256 = Vector<M256>; // 32 Bytes
+
+#if defined(__AVX512F__) and defined(__AVX512BW__)
+struct M512 {
+  static constexpr size_t kSize = 64;
+  using T = char __attribute__((__vector_size__(kSize)));
+  static uint64_t NotEqualMask(T a, T b) {
+    return _mm512_cmpneq_epi8_mask(a, b);
+  }
+  static T Load(const char *ptr) { return _mm512_loadu_epi8(ptr); }
+  static void Store(char *ptr, T value) {
+    return _mm512_storeu_epi8(ptr, value);
+  }
+  static T GetSplattedValue(const char v) {
+    const T splatted = {v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v,
+                        v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v,
+                        v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v,
+                        v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v};
+    return splatted;
+  }
+};
+using Vector512 = Vector<M512>;
+
+#endif // defined(__AVX512F__) and defined(__AVX512BW__)
+#endif // __AVX2__
+#endif // __SSE2__
+
+using _1 = __llvm_libc::scalar::_1;
+using _2 = __llvm_libc::scalar::_2;
+using _3 = __llvm_libc::scalar::_3;
+using _4 = __llvm_libc::scalar::_4;
+using _8 = __llvm_libc::scalar::_8;
+#if defined(__AVX512F__) && defined(__AVX512BW__)
+using _16 = __llvm_libc::x86::Vector128;
+using _32 = __llvm_libc::x86::Vector256;
+using _64 = __llvm_libc::x86::Vector512;
+using _128 = __llvm_libc::Repeated<_64, 2>;
+#elif defined(__AVX2__)
+using _16 = __llvm_libc::x86::Vector128;
+using _32 = __llvm_libc::x86::Vector256;
+using _64 = __llvm_libc::Repeated<_32, 2>;
+using _128 = __llvm_libc::Repeated<_32, 4>;
+#elif defined(__SSE2__)
+using _16 = __llvm_libc::x86::Vector128;
+using _32 = __llvm_libc::Repeated<_16, 2>;
+using _64 = __llvm_libc::Repeated<_16, 4>;
+using _128 = __llvm_libc::Repeated<_16, 8>;
+#else
+using _16 = __llvm_libc::Repeated<_8, 2>;
+using _32 = __llvm_libc::Repeated<_8, 4>;
+using _64 = __llvm_libc::Repeated<_8, 8>;
+using _128 = __llvm_libc::Repeated<_8, 16>;
+#endif
+
+} // namespace x86
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_X86_H

libc/src/string/memory_utils/memcpy_utils.h

-//===-- Memcpy utils --------------------------------------------*- 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 LIBC_SRC_STRING_MEMORY_UTILS_MEMCPY_UTILS_H
-#define LIBC_SRC_STRING_MEMORY_UTILS_MEMCPY_UTILS_H
-
-#include "src/__support/sanitizer.h"
-#include "src/string/memory_utils/utils.h"
-#include <stddef.h> // size_t
-
-// __builtin_memcpy_inline guarantees to never call external functions.
-// Unfortunately it is not widely available.
-#ifdef __clang__
-#if __has_builtin(__builtin_memcpy_inline)
-#define USE_BUILTIN_MEMCPY_INLINE
-#endif
-#elif defined(__GNUC__)
-#define USE_BUILTIN_MEMCPY
-#endif
-
-namespace __llvm_libc {
-
-// This is useful for testing.
-#if defined(LLVM_LIBC_MEMCPY_MONITOR)
-extern "C" void LLVM_LIBC_MEMCPY_MONITOR(char *__restrict,
-                                         const char *__restrict, size_t);
-#endif
-
-// Copies `kBlockSize` bytes from `src` to `dst` using a for loop.
-// This code requires the use of `-fno-buitin-memcpy` to prevent the compiler
-// from turning the for-loop back into `__builtin_memcpy`.
-template <size_t kBlockSize>
-static void ForLoopCopy(char *__restrict dst, const char *__restrict src) {
-  for (size_t i = 0; i < kBlockSize; ++i)
-    dst[i] = src[i];
-}
-
-// Copies `kBlockSize` bytes from `src` to `dst`.
-template <size_t kBlockSize>
-static void CopyBlock(char *__restrict dst, const char *__restrict src) {
-#if defined(LLVM_LIBC_MEMCPY_MONITOR)
-  LLVM_LIBC_MEMCPY_MONITOR(dst, src, kBlockSize);
-#elif LLVM_LIBC_HAVE_MEMORY_SANITIZER || LLVM_LIBC_HAVE_ADDRESS_SANITIZER
-  ForLoopCopy<kBlockSize>(dst, src);
-#elif defined(USE_BUILTIN_MEMCPY_INLINE)
-  __builtin_memcpy_inline(dst, src, kBlockSize);
-#elif defined(USE_BUILTIN_MEMCPY)
-  __builtin_memcpy(dst, src, kBlockSize);
-#else
-  ForLoopCopy<kBlockSize>(dst, src);
-#endif
-}
-
-// Copies `kBlockSize` bytes from `src + count - kBlockSize` to
-// `dst + count - kBlockSize`.
-// Precondition: `count >= kBlockSize`.
-template <size_t kBlockSize>
-static void CopyLastBlock(char *__restrict dst, const char *__restrict src,
-                          size_t count) {
-  const size_t offset = count - kBlockSize;
-  CopyBlock<kBlockSize>(dst + offset, src + offset);
-}
-
-// Copies `kBlockSize` bytes twice with an overlap between the two.
-//
-// [1234567812345678123]
-// [__XXXXXXXXXXXXXX___]
-// [__XXXXXXXX_________]
-// [________XXXXXXXX___]
-//
-// Precondition: `count >= kBlockSize && count <= kBlockSize`.
-template <size_t kBlockSize>
-static void CopyBlockOverlap(char *__restrict dst, const char *__restrict src,
-                             size_t count) {
-  CopyBlock<kBlockSize>(dst, src);
-  CopyLastBlock<kBlockSize>(dst, src, count);
-}
-
-// Copies `count` bytes by blocks of `kBlockSize` bytes.
-// Copies at the start and end of the buffer are unaligned.
-// Copies in the middle of the buffer are aligned to `kAlignment`.
-//
-// e.g. with
-// [12345678123456781234567812345678]
-// [__XXXXXXXXXXXXXXXXXXXXXXXXXXXX___]
-// [__XXXX___________________________]
-// [_____XXXXXXXX____________________]
-// [_____________XXXXXXXX____________]
-// [_____________________XXXXXXXX____]
-// [______________________XXXXXXXX___]
-//
-// Precondition: `kAlignment <= kBlockSize`
-//               `count > 2 * kBlockSize` for efficiency.
-//               `count >= kAlignment` for correctness.
-template <size_t kBlockSize, size_t kAlignment = kBlockSize>
-static void CopySrcAlignedBlocks(char *__restrict dst,
-                                 const char *__restrict src, size_t count) {
-  static_assert(is_power2(kAlignment), "kAlignment must be a power of two");
-  static_assert(is_power2(kBlockSize), "kBlockSize must be a power of two");
-  static_assert(kAlignment <= kBlockSize,
-                "kAlignment must be less or equal to block size");
-  CopyBlock<kAlignment>(dst, src); // Copy first block
-
-  // Copy aligned blocks
-  const size_t ofla = offset_from_last_aligned<kAlignment>(src);
-  const size_t limit = count + ofla - kBlockSize;
-  for (size_t offset = kAlignment; offset < limit; offset += kBlockSize)
-    CopyBlock<kBlockSize>(dst - ofla + offset,
-                          assume_aligned<kAlignment>(src - ofla + offset));
-
-  CopyLastBlock<kBlockSize>(dst, src, count); // Copy last block
-}
-
-template <size_t kBlockSize, size_t kAlignment = kBlockSize>
-static void CopyDstAlignedBlocks(char *__restrict dst,
-                                 const char *__restrict src, size_t count) {
-  static_assert(is_power2(kAlignment), "kAlignment must be a power of two");
-  static_assert(is_power2(kBlockSize), "kBlockSize must be a power of two");
-  static_assert(kAlignment <= kBlockSize,
-                "kAlignment must be less or equal to block size");
-  CopyBlock<kAlignment>(dst, src); // Copy first block
-
-  // Copy aligned blocks
-  const size_t ofla = offset_from_last_aligned<kAlignment>(dst);
-  const size_t limit = count + ofla - kBlockSize;
-  for (size_t offset = kAlignment; offset < limit; offset += kBlockSize)
-    CopyBlock<kBlockSize>(assume_aligned<kAlignment>(dst - ofla + offset),
-                          src - ofla + offset);
-
-  CopyLastBlock<kBlockSize>(dst, src, count); // Copy last block
-}
-
-} // namespace __llvm_libc
-
-#endif //  LIBC_SRC_STRING_MEMORY_UTILS_MEMCPY_UTILS_H

libc/src/string/memory_utils/memset_utils.h

 //===-- Memset utils --------------------------------------------*- 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 LIBC_SRC_STRING_MEMORY_UTILS_MEMSET_UTILS_H
-#define LIBC_SRC_STRING_MEMORY_UTILS_MEMSET_UTILS_H
+#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMSET_UTILS_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMSET_UTILS_H
 
+#include "src/string/memory_utils/elements.h"
 #include "src/string/memory_utils/utils.h"
 
 #include <stddef.h> // size_t
 
 namespace __llvm_libc {
 
-// Sets `kBlockSize` bytes starting from `src` to `value`.
-template <size_t kBlockSize> static void SetBlock(char *dst, unsigned value) {
-  // Theoretically the compiler is allowed to call memset here and end up with a
-  // recursive call, practically it doesn't happen, however this should be
-  // replaced with a __builtin_memset_inline once it's available in clang.
-  __builtin_memset(dst, value, kBlockSize);
-}
-
-// Sets `kBlockSize` bytes from `src + count - kBlockSize` to `value`.
-// Precondition: `count >= kBlockSize`.
-template <size_t kBlockSize>
-static void SetLastBlock(char *dst, unsigned value, size_t count) {
-  SetBlock<kBlockSize>(dst + count - kBlockSize, value);
-}
-
-// Sets `kBlockSize` bytes twice with an overlap between the two.
-//
-// [1234567812345678123]
-// [__XXXXXXXXXXXXXX___]
-// [__XXXXXXXX_________]
-// [________XXXXXXXX___]
-//
-// Precondition: `count >= kBlockSize && count <= kBlockSize`.
-template <size_t kBlockSize>
-static void SetBlockOverlap(char *dst, unsigned value, size_t count) {
-  SetBlock<kBlockSize>(dst, value);
-  SetLastBlock<kBlockSize>(dst, value, count);
-}
-
-// Sets `count` bytes by blocks of `kBlockSize` bytes.
-// Sets at the start and end of the buffer are unaligned.
-// Sets in the middle of the buffer are aligned to `kBlockSize`.
-//
-// e.g. with
-// [12345678123456781234567812345678]
-// [__XXXXXXXXXXXXXXXXXXXXXXXXXXX___]
-// [__XXXXXXXX______________________]
-// [________XXXXXXXX________________]
-// [________________XXXXXXXX________]
-// [_____________________XXXXXXXX___]
-//
-// Precondition: `count > 2 * kBlockSize` for efficiency.
-//               `count >= kBlockSize` for correctness.
-template <size_t kBlockSize>
-static void SetAlignedBlocks(char *dst, unsigned value, size_t count) {
-  SetBlock<kBlockSize>(dst, value); // Set first block
-
-  // Set aligned blocks
-  size_t offset = kBlockSize - offset_from_last_aligned<kBlockSize>(dst);
-  for (; offset + kBlockSize < count; offset += kBlockSize)
-    SetBlock<kBlockSize>(dst + offset, value);
-
-  SetLastBlock<kBlockSize>(dst, value, count); // Set last block
-}
-
 // A general purpose implementation assuming cheap unaligned writes for sizes:
 // 1, 2, 4, 8, 16, 32 and 64 Bytes. Note that some architecture can't store 32
 // or 64 Bytes at a time, the compiler will expand them as needed.
 //
 // This implementation is subject to change as we benchmark more processors. We
 // may also want to customize it for processors with specialized instructions
 // that performs better (e.g. `rep stosb`).
 //

 // advance. SetAlignedBlocks<64> may waste up to 63 Bytes, SetAlignedBlocks<32>
 // may waste up to 31 Bytes. Benchmarks showed that SetAlignedBlocks<64> was not
 // superior for sizes that mattered.
 inline static void GeneralPurposeMemset(char *dst, unsigned char value,
                                         size_t count) {
   if (count == 0)
     return;
   if (count == 1)
-    return SetBlock<1>(dst, value);
+    return SplatSet<scalar::_1>(dst, value);
   if (count == 2)
-    return SetBlock<2>(dst, value);
+    return SplatSet<scalar::_2>(dst, value);
   if (count == 3)
-    return SetBlock<3>(dst, value);
+    return SplatSet<scalar::_3>(dst, value);
   if (count == 4)
-    return SetBlock<4>(dst, value);
+    return SplatSet<scalar::_4>(dst, value);
   if (count <= 8)
-    return SetBlockOverlap<4>(dst, value, count);
+    return SplatSet<HeadTail<scalar::_4>>(dst, value, count);
   if (count <= 16)
-    return SetBlockOverlap<8>(dst, value, count);
+    return SplatSet<HeadTail<scalar::_8>>(dst, value, count);
   if (count <= 32)
-    return SetBlockOverlap<16>(dst, value, count);
+    return SplatSet<HeadTail<scalar::_16>>(dst, value, count);
   if (count <= 64)
-    return SetBlockOverlap<32>(dst, value, count);
+    return SplatSet<HeadTail<scalar::_32>>(dst, value, count);
   if (count <= 128)
-    return SetBlockOverlap<64>(dst, value, count);
-  return SetAlignedBlocks<32>(dst, value, count);
+    return SplatSet<HeadTail<scalar::_64>>(dst, value, count);
+  return SplatSet<Align<scalar::_32, Arg::Dst>::Then<Loop<scalar::_32>>>(
+      dst, value, count);
 }
 
 } // namespace __llvm_libc
 
-#endif //  LIBC_SRC_STRING_MEMORY_UTILS_MEMSET_UTILS_H
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMSET_UTILS_H

libc/src/string/x86_64/memcpy.cpp

 //===-- Implementation of memcpy ------------------------------------------===//
 //
 // 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 "src/string/memcpy.h"
 #include "src/__support/common.h"
-#include "src/string/memory_utils/memcpy_utils.h"
+#include "src/string/memory_utils/elements.h"
 
 namespace __llvm_libc {
 
 // Whether to use only rep;movsb.
 constexpr bool kUseOnlyRepMovsb =
     LLVM_LIBC_IS_DEFINED(LLVM_LIBC_MEMCPY_X86_USE_ONLY_REPMOVSB);
 
 // kRepMovsBSize == -1 : Only CopyAligned is used.
 // kRepMovsBSize ==  0 : Only RepMovsb is used.
 // else CopyAligned is used up to kRepMovsBSize and then RepMovsb.
 constexpr size_t kRepMovsBSize =
 #ifdef LLVM_LIBC_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE
     LLVM_LIBC_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE;
 #else
     -1;
 #endif // LLVM_LIBC_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE
 
 // Whether target supports AVX instructions.
 constexpr bool kHasAvx = LLVM_LIBC_IS_DEFINED(__AVX__);
 
-// The chunk size used for the loop copy strategy.
-constexpr size_t kLoopCopyBlockSize = kHasAvx ? 64 : 32;
+#ifdef __AVX__
+using LoopBlockSize = __llvm_libc::x86::_64;
+#else
+using LoopBlockSize = __llvm_libc::x86::_32;
+#endif
 
 static void CopyRepMovsb(char *__restrict dst, const char *__restrict src,
                          size_t count) {
   // FIXME: Add MSVC support with
   // #include <intrin.h>
   // __movsb(reinterpret_cast<unsigned char *>(dst),
   //         reinterpret_cast<const unsigned char *>(src), count);
   asm volatile("rep movsb" : "+D"(dst), "+S"(src), "+c"(count) : : "memory");

 //   Guided Optimization as the optimized code can take advantage of branching
 //   probabilities.
 // - It also allows for easier customization and favors testing multiple
 //   implementation parameters.
 // - As compilers and processors get better, the generated code is improved
 //   with little change on the code side.
 static void memcpy_x86(char *__restrict dst, const char *__restrict src,
                        size_t count) {
+  // Use x86 strategies (_1, _2, _3 ...)
+  using namespace __llvm_libc::x86;
+
   if (kUseOnlyRepMovsb)
     return CopyRepMovsb(dst, src, count);
 
   if (count == 0)
     return;
   if (count == 1)
-    return CopyBlock<1>(dst, src);
+    return Copy<_1>(dst, src);
   if (count == 2)
-    return CopyBlock<2>(dst, src);
+    return Copy<_2>(dst, src);
   if (count == 3)
-    return CopyBlock<3>(dst, src);
+    return Copy<_3>(dst, src);
   if (count == 4)
-    return CopyBlock<4>(dst, src);
+    return Copy<_4>(dst, src);
   if (count < 8)
-    return CopyBlockOverlap<4>(dst, src, count);
+    return Copy<HeadTail<_4>>(dst, src, count);
   if (count < 16)
-    return CopyBlockOverlap<8>(dst, src, count);
+    return Copy<HeadTail<_8>>(dst, src, count);
   if (count < 32)
-    return CopyBlockOverlap<16>(dst, src, count);
+    return Copy<HeadTail<_16>>(dst, src, count);
   if (count < 64)
-    return CopyBlockOverlap<32>(dst, src, count);
+    return Copy<HeadTail<_32>>(dst, src, count);
   if (count < 128)
-    return CopyBlockOverlap<64>(dst, src, count);
+    return Copy<HeadTail<_64>>(dst, src, count);
   if (kHasAvx && count < 256)
-    return CopyBlockOverlap<128>(dst, src, count);
+    return Copy<HeadTail<_128>>(dst, src, count);
   if (count <= kRepMovsBSize)
-    return CopyDstAlignedBlocks<kLoopCopyBlockSize, 32>(dst, src, count);
+    return Copy<Align<_32, Arg::Dst>::Then<Loop<LoopBlockSize>>>(dst, src,
+                                                                 count);
   return CopyRepMovsb(dst, src, count);
 }
 
 LLVM_LIBC_FUNCTION(void *, memcpy,
                    (void *__restrict dst, const void *__restrict src,
                     size_t size)) {
   memcpy_x86(reinterpret_cast<char *>(dst), reinterpret_cast<const char *>(src),
              size);
   return dst;
 }
 
 } // namespace __llvm_libc

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

 add_libc_unittest(
   utils_test
   SUITE
     libc_string_unittests
   SRCS
+    elements_test.cpp
+    memory_access_test.cpp
     utils_test.cpp
-    memcpy_utils_test.cpp
   DEPENDS
     libc.src.string.memory_utils.memory_utils
     libc.utils.CPP.standalone_cpp
+  COMPILE_OPTIONS
+    ${LIBC_COMPILE_OPTIONS_NATIVE}
 )
 
 target_compile_definitions(
   libc.test.src.string.memory_utils.utils_test
   PRIVATE
   LLVM_LIBC_MEMCPY_MONITOR=memcpy_monitor
 )

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

+//===-- Unittests for memory_utils ----------------------------------------===//
+//
+// 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 "src/string/memory_utils/elements.h"
+#include "utils/CPP/Array.h"
+#include "utils/UnitTest/Test.h"
+
+namespace __llvm_libc {
+
+// Registering Types
+using FixedSizeTypes = testing::TypeList<
+#ifdef __SSE2__
+    x86::Vector128, //
+#endif              // __SSE2__
+#ifdef __AVX2__
+    x86::Vector256, //
+#endif              // __AVX2__
+#if defined(__AVX512F__) and defined(__AVX512BW__)
+    x86::Vector512, //
+#endif              // defined(__AVX512F__) and defined(__AVX512BW__)
+    scalar::UINT8,  //
+    scalar::UINT16, //
+    scalar::UINT32, //
+    scalar::UINT64, //
+    Repeated<scalar::UINT64, 2>,                            //
+    Repeated<scalar::UINT64, 4>,                            //
+    Repeated<scalar::UINT64, 8>,                            //
+    Repeated<scalar::UINT64, 16>,                           //
+    Repeated<scalar::UINT64, 32>,                           //
+    Chained<scalar::UINT16, scalar::UINT8>,                 //
+    Chained<scalar::UINT32, scalar::UINT16, scalar::UINT8>, //
+    builtin::_1,                                            //
+    builtin::_2,                                            //
+    builtin::_3,                                            //
+    builtin::_4,                                            //
+    builtin::_8                                             //
+    >;
+
+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;
+}
+
+template <typename Element> using Buffer = cpp::Array<char, Element::kSize>;
+template <typename Element> Buffer<Element> GetRandomBuffer() {
+  Buffer<Element> buffer;
+  for (auto &current : buffer)
+    current = GetRandomChar();
+  return buffer;
+}
+
+TYPED_TEST(LlvmLibcMemoryElements, Copy, FixedSizeTypes) {
+  Buffer<ParamType> Dst;
+  const auto buffer = GetRandomBuffer<ParamType>();
+  Copy<ParamType>(Dst.data(), buffer.data());
+  for (size_t i = 0; i < ParamType::kSize; ++i)
+    EXPECT_EQ(Dst[i], buffer[i]);
+}
+
+TYPED_TEST(LlvmLibcMemoryElements, Equals, FixedSizeTypes) {
+  const auto buffer = GetRandomBuffer<ParamType>();
+  EXPECT_TRUE(Equals<ParamType>(buffer.data(), buffer.data()));
+}
+
+TYPED_TEST(LlvmLibcMemoryElements, ThreeWayCompare, FixedSizeTypes) {
+  Buffer<ParamType> initial;
+  for (auto &c : initial)
+    c = 5;
+
+  // Testing equality
+  EXPECT_EQ(ThreeWayCompare<ParamType>(initial.data(), initial.data()), 0);
+
+  // Testing all mismatching positions
+  for (size_t i = 0; i < ParamType::kSize; ++i) {
+    auto copy = initial;
+    ++copy[i]; // Copy is now lexicographycally greated than initial
+    const auto *less = initial.data();
+    const auto *greater = copy.data();
+    EXPECT_LT(ThreeWayCompare<ParamType>(less, greater), 0);
+    EXPECT_GT(ThreeWayCompare<ParamType>(greater, less), 0);
+  }
+}
+
+TYPED_TEST(LlvmLibcMemoryElements, Splat, FixedSizeTypes) {
+  Buffer<ParamType> Dst;
+  const cpp::Array<char, 3> values = {char(0x00), char(0x7F), char(0xFF)};
+  for (char value : values) {
+    SplatSet<ParamType>(Dst.data(), value);
+    for (size_t i = 0; i < ParamType::kSize; ++i)
+      EXPECT_EQ(Dst[i], value);
+  }
+}
+
+} // namespace __llvm_libc

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

-//===-- Unittests for memory_utils ----------------------------------------===//
-//
-// 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 "src/string/memory_utils/memcpy_utils.h"
-#include "utils/CPP/Array.h"
-#include "utils/UnitTest/Test.h"
-
-#include <assert.h>
-#include <stdint.h> // uintptr_t
-
-#ifndef LLVM_LIBC_MEMCPY_MONITOR
-#error LLVM_LIBC_MEMCPY_MONITOR must be defined for this test.
-#endif
-
-namespace __llvm_libc {
-
-struct Buffer {
-  static constexpr size_t kMaxBuffer = 1024;
-  char buffer[kMaxBuffer + 1];
-  size_t last = 0;
-
-  void Clear() {
-    last = 0;
-    for (size_t i = 0; i < kMaxBuffer; ++i)
-      buffer[i] = '0';
-    buffer[kMaxBuffer] = '\0';
-  }
-
-  void Increment(const void *ptr) {
-    const auto offset = reinterpret_cast<uintptr_t>(ptr);
-    assert(offset < kMaxBuffer);
-    ++buffer[offset];
-    if (offset > last)
-      last = offset;
-  }
-
-  char *Finish() {
-    assert(last < kMaxBuffer);
-    buffer[last + 1] = '\0';
-    return buffer;
-  }
-};
-
-struct Trace {
-  Buffer read;
-  Buffer write;
-
-  void Add(char *__restrict dst, const char *__restrict src, size_t count) {
-    for (size_t i = 0; i < count; ++i)
-      read.Increment(src + i);
-    for (size_t i = 0; i < count; ++i)
-      write.Increment(dst + i);
-  }
-
-  void Clear() {
-    read.Clear();
-    write.Clear();
-  }
-
-  char *Read() { return read.Finish(); }
-  char *Write() { return write.Finish(); }
-};
-
-static Trace &GetTrace() {
-  static thread_local Trace events;
-  return events;
-}
-
-extern "C" void LLVM_LIBC_MEMCPY_MONITOR(char *__restrict dst,
-                                         const char *__restrict src,
-                                         size_t count) {
-  GetTrace().Add(dst, src, count);
-}
-
-char *I(uintptr_t offset) { return reinterpret_cast<char *>(offset); }
-
-TEST(LlvmLibcMemcpyUtilsTest, CopyTrivial) {
-  auto &trace = GetTrace();
-
-  trace.Clear();
-  CopyBlock<1>(I(0), I(0));
-  EXPECT_STREQ(trace.Write(), "1");
-  EXPECT_STREQ(trace.Read(), "1");
-
-  trace.Clear();
-  CopyBlock<2>(I(0), I(0));
-  EXPECT_STREQ(trace.Write(), "11");
-  EXPECT_STREQ(trace.Read(), "11");
-
-  trace.Clear();
-  CopyBlock<4>(I(0), I(0));
-  EXPECT_STREQ(trace.Write(), "1111");
-  EXPECT_STREQ(trace.Read(), "1111");
-
-  trace.Clear();
-  CopyBlock<8>(I(0), I(0));
-  EXPECT_STREQ(trace.Write(), "11111111");
-  EXPECT_STREQ(trace.Read(), "11111111");
-
-  trace.Clear();
-  CopyBlock<16>(I(0), I(0));
-  EXPECT_STREQ(trace.Write(), "1111111111111111");
-  EXPECT_STREQ(trace.Read(), "1111111111111111");
-
-  trace.Clear();
-  CopyBlock<32>(I(0), I(0));
-  EXPECT_STREQ(trace.Write(), "11111111111111111111111111111111");
-  EXPECT_STREQ(trace.Read(), "11111111111111111111111111111111");
-
-  trace.Clear();
-  CopyBlock<64>(I(0), I(0));
-  EXPECT_STREQ(
-      trace.Write(),
-      "1111111111111111111111111111111111111111111111111111111111111111");
-  EXPECT_STREQ(
-      trace.Read(),
-      "1111111111111111111111111111111111111111111111111111111111111111");
-}
-
-TEST(LlvmLibcMemcpyUtilsTest, CopyOffset) {
-  auto &trace = GetTrace();
-
-  trace.Clear();
-  CopyBlock<1>(I(3), I(1));
-  EXPECT_STREQ(trace.Write(), "0001");
-  EXPECT_STREQ(trace.Read(), "01");
-
-  trace.Clear();
-  CopyBlock<1>(I(2), I(1));
-  EXPECT_STREQ(trace.Write(), "001");
-  EXPECT_STREQ(trace.Read(), "01");
-}
-
-TEST(LlvmLibcMemcpyUtilsTest, CopyBlockOverlap) {
-  auto &trace = GetTrace();
-
-  trace.Clear();
-  CopyBlockOverlap<2>(I(0), I(0), 2);
-  EXPECT_STREQ(trace.Write(), "22");
-  EXPECT_STREQ(trace.Read(), "22");
-
-  trace.Clear();
-  CopyBlockOverlap<2>(I(0), I(0), 3);
-  EXPECT_STREQ(trace.Write(), "121");
-  EXPECT_STREQ(trace.Read(), "121");
-
-  trace.Clear();
-  CopyBlockOverlap<2>(I(0), I(0), 4);
-  EXPECT_STREQ(trace.Write(), "1111");
-  EXPECT_STREQ(trace.Read(), "1111");
-
-  trace.Clear();
-  CopyBlockOverlap<4>(I(2), I(1), 7);
-  EXPECT_STREQ(trace.Write(), "001112111");
-  EXPECT_STREQ(trace.Read(), "01112111");
-}
-
-TEST(LlvmLibcMemcpyUtilsTest, CopySrcAlignedBlocks) {
-  auto &trace = GetTrace();
-  // Source is aligned and multiple of alignment.
-  //   "1111"
-  trace.Clear();
-  CopySrcAlignedBlocks<4>(I(0), I(0), 4);
-  EXPECT_STREQ(trace.Write(), "2222");
-  EXPECT_STREQ(trace.Read(), "2222");
-
-  // Source is aligned and multiple of alignment.
-  //   "11110000"
-  // + "00001111"
-  // = "11111111"
-  trace.Clear();
-  CopySrcAlignedBlocks<4>(I(0), I(0), 8);
-  EXPECT_STREQ(trace.Write(), "11111111");
-  EXPECT_STREQ(trace.Read(), "11111111");
-
-  // Source is aligned already overlap at end.
-  //   "1111000000000"
-  // + "0000111100000"
-  // + "0000000011110"
-  // + "0000000001111"
-  // = "1111111112221"
-  trace.Clear();
-  CopySrcAlignedBlocks<4>(I(0), I(0), 13);
-  EXPECT_STREQ(trace.Write(), "1111111112221");
-  EXPECT_STREQ(trace.Read(), "1111111112221");
-
-  // Misaligned source.
-  //   "01111000000000"
-  // + "00001111000000"
-  // + "00000000111100"
-  // + "00000000001111"
-  // = "01112111112211"
-  trace.Clear();
-  CopySrcAlignedBlocks<4>(I(0), I(1), 13);
-  EXPECT_STREQ(trace.Write(), "1112111112211");
-  EXPECT_STREQ(trace.Read(), "01112111112211");
-
-  // Misaligned source aligned at end.
-  //   "011110000000"
-  // + "000011110000"
-  // + "000000001111"
-  // = "011121111111"
-  trace.Clear();
-  CopySrcAlignedBlocks<4>(I(0), I(1), 11);
-  EXPECT_STREQ(trace.Write(), "11121111111");
-  EXPECT_STREQ(trace.Read(), "011121111111");
-}
-
-TEST(LlvmLibcMemcpyUtilsTest, CopyDstAlignedBlocks) {
-  auto &trace = GetTrace();
-  // Destination is aligned and multiple of alignment.
-  //   "1111"
-  trace.Clear();
-  CopyDstAlignedBlocks<4>(I(0), I(0), 4);
-  EXPECT_STREQ(trace.Write(), "2222");
-  EXPECT_STREQ(trace.Read(), "2222");
-
-  // Destination is aligned and multiple of alignment.
-  //   "11110000"
-  // + "00001111"
-  // = "11111111"
-  trace.Clear();
-  CopyDstAlignedBlocks<4>(I(0), I(0), 8);
-  EXPECT_STREQ(trace.Write(), "11111111");
-  EXPECT_STREQ(trace.Read(), "11111111");
-
-  // Destination is aligned already overlap at end.
-  //   "1111000000000"
-  // + "0000111100000"
-  // + "0000000011110"
-  // + "0000000001111"
-  // = "1111111112221"
-  trace.Clear();
-  CopyDstAlignedBlocks<4>(I(0), I(0), 13);
-  EXPECT_STREQ(trace.Write(), "1111111112221");
-  EXPECT_STREQ(trace.Read(), "1111111112221");
-
-  // Misaligned destination.
-  //   "01111000000000"
-  // + "00001111000000"
-  // + "00000000111100"
-  // + "00000000001111"
-  // = "01112111112211"
-  trace.Clear();
-  CopyDstAlignedBlocks<4>(I(1), I(0), 13);
-  EXPECT_STREQ(trace.Write(), "01112111112211");
-  EXPECT_STREQ(trace.Read(), "1112111112211");
-
-  // Misaligned destination aligned at end.
-  //   "011110000000"
-  // + "000011110000"
-  // + "000000001111"
-  // = "011121111111"
-  trace.Clear();
-  CopyDstAlignedBlocks<4>(I(1), I(0), 11);
-  EXPECT_STREQ(trace.Write(), "011121111111");
-  EXPECT_STREQ(trace.Read(), "11121111111");
-}
-
-TEST(LlvmLibcMemcpyUtilsTest, CopyAlignedBlocksWithAlignment) {
-  auto &trace = GetTrace();
-  // Source is aligned and multiple of alignment.
-  //   "11111111"
-  trace.Clear();
-  CopySrcAlignedBlocks<8, 4>(I(0), I(0), 8);
-  EXPECT_STREQ(trace.Write(), "22221111");
-  EXPECT_STREQ(trace.Read(), "22221111");
-
-  // Destination is aligned and multiple of alignment.
-  //   "11111111"
-  trace.Clear();
-  CopyDstAlignedBlocks<8, 4>(I(0), I(0), 8);
-  EXPECT_STREQ(trace.Write(), "22221111");
-  EXPECT_STREQ(trace.Read(), "22221111");
-
-  // Source is aligned and multiple of alignment.
-  //   "111111111"
-  trace.Clear();
-  CopySrcAlignedBlocks<8, 4>(I(0), I(0), 9);
-  EXPECT_STREQ(trace.Write(), "122211111");
-  EXPECT_STREQ(trace.Read(), "122211111");
-
-  // Destination is aligned and multiple of alignment.
-  //   "111111111"
-  trace.Clear();
-  CopyDstAlignedBlocks<8, 4>(I(0), I(0), 9);
-  EXPECT_STREQ(trace.Write(), "122211111");
-  EXPECT_STREQ(trace.Read(), "122211111");
-}
-
-TEST(LlvmLibcMemcpyUtilsTest, CopyAlignedBlocksMaxReloads) {
-  auto &trace = GetTrace();
-  for (size_t alignment = 0; alignment < 32; ++alignment) {
-    for (size_t count = 64; count < 768; ++count) {
-      trace.Clear();
-      // We should never reload more than twice when copying from count = 2x32.
-      CopySrcAlignedBlocks<32>(I(alignment), I(0), count);
-      const char *const written = trace.Write();
-      // First bytes are untouched.
-      for (size_t i = 0; i < alignment; ++i)
-        EXPECT_EQ(written[i], '0');
-      // Next bytes are loaded once or twice but no more.
-      for (size_t i = alignment; i < count; ++i) {
-        EXPECT_GE(written[i], '1');
-        EXPECT_LE(written[i], '2');
-      }
-    }
-  }
-}
-
-TEST(LlvmLibcMemcpyUtilsTest, CopyAlignedBlocksWithAlignmentMaxReloads) {
-  auto &trace = GetTrace();
-  for (size_t alignment = 0; alignment < 32; ++alignment) {
-    for (size_t count = 64; count < 768; ++count) {
-      trace.Clear();
-      // We should never reload more than twice when copying from count = 2x32.
-      CopySrcAlignedBlocks<32, 16>(I(alignment), I(0), count);
-      const char *const written = trace.Write();
-      // First bytes are untouched.
-      for (size_t i = 0; i < alignment; ++i)
-        EXPECT_EQ(written[i], '0');
-      // Next bytes are loaded once or twice but no more.
-      for (size_t i = alignment; i < count; ++i) {
-        EXPECT_GE(written[i], '1');
-        EXPECT_LE(written[i], '2');
-      }
-    }
-  }
-}
-
-} // namespace __llvm_libc

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

+//===-- Unittests for memory_utils ----------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#define LLVM_LIBC_UNITTEST_OBSERVE 1
+
+#include "src/string/memory_utils/elements.h"
+#include "utils/CPP/Array.h"
+#include "utils/CPP/ArrayRef.h"
+#include "utils/UnitTest/Test.h"
+
+#include <stdio.h>
+#include <string.h>
+
+namespace __llvm_libc {
+
+static constexpr const size_t kMaxBuffer = 32;
+
+struct BufferAccess : cpp::Array<char, kMaxBuffer + 1> {
+  BufferAccess() { Reset(); }
+  void Reset() {
+    for (auto &value : *this)
+      value = '0';
+    this->operator[](kMaxBuffer) = '\0';
+  }
+  void Touch(ptrdiff_t offset, size_t size) {
+    if (offset < 0)
+      return;
+    for (size_t i = 0; i < size; ++i)
+      ++(*this)[offset + i];
+  }
+  operator const char *() const { return this->data(); }
+};
+
+struct Buffer {
+  ptrdiff_t Offset(const char *ptr) const {
+    const bool contained = ptr >= data.begin() && ptr < data.end();
+    return contained ? ptr - data.begin() : -1;
+  }
+  void Reset() {
+    reads.Reset();
+    writes.Reset();
+  }
+  cpp::Array<char, kMaxBuffer> data;
+  BufferAccess __attribute__((aligned(64))) reads;
+  BufferAccess __attribute__((aligned(64))) writes;
+};
+
+struct MemoryAccessObserver {
+  void ObserveRead(const char *ptr, size_t size) {
+    Buffer1.reads.Touch(Buffer1.Offset(ptr), size);
+    Buffer2.reads.Touch(Buffer2.Offset(ptr), size);
+  }
+
+  void ObserveWrite(const char *ptr, size_t size) {
+    Buffer1.writes.Touch(Buffer1.Offset(ptr), size);
+    Buffer2.writes.Touch(Buffer2.Offset(ptr), size);
+  }
+
+  void Reset() {
+    Buffer1.Reset();
+    Buffer2.Reset();
+  }
+
+  Buffer Buffer1;
+  Buffer Buffer2;
+};
+
+MemoryAccessObserver Observer;
+
+template <size_t Size> struct TestingElement {
+  static constexpr size_t kSize = Size;
+
+  static void Copy(char *__restrict dst, const char *__restrict src) {
+    Observer.ObserveRead(src, kSize);
+    Observer.ObserveWrite(dst, kSize);
+  }
+
+  static bool Equals(const char *lhs, const char *rhs) {
+    Observer.ObserveRead(lhs, kSize);
+    Observer.ObserveRead(rhs, kSize);
+    return true;
+  }
+
+  static int ThreeWayCompare(const char *lhs, const char *rhs) {
+    Observer.ObserveRead(lhs, kSize);
+    Observer.ObserveRead(rhs, kSize);
+    return 0;
+  }
+
+  static void SplatSet(char *dst, const unsigned char value) {
+    Observer.ObserveWrite(dst, kSize);
+  }
+};
+
+using Types = testing::TypeList<
+    TestingElement<1>,                                               // 1 Byte
+    TestingElement<2>,                                               // 2 Bytes
+    TestingElement<4>,                                               // 4 Bytes
+    Repeated<TestingElement<2>, 3>,                                  // 6 Bytes
+    Chained<TestingElement<4>, TestingElement<2>, TestingElement<1>> // 7 Bytes
+    >;
+
+struct LlvmLibcTestAccessBase : public testing::Test {
+
+  template <typename HigherOrder, size_t Size, size_t Offset = 0>
+  void checkOperations(const BufferAccess &expected) {
+    static const BufferAccess untouched;
+
+    Observer.Reset();
+    HigherOrder::Copy(dst_ptr() + Offset, src_ptr() + Offset, Size);
+    ASSERT_STREQ(src().writes, untouched);
+    ASSERT_STREQ(dst().reads, untouched);
+    ASSERT_STREQ(src().reads, expected);
+    ASSERT_STREQ(dst().writes, expected);
+    Observer.Reset();
+    HigherOrder::Equals(lhs_ptr() + Offset, rhs_ptr() + Offset, Size);
+    ASSERT_STREQ(lhs().writes, untouched);
+    ASSERT_STREQ(rhs().writes, untouched);
+    ASSERT_STREQ(lhs().reads, expected);
+    ASSERT_STREQ(rhs().reads, expected);
+    Observer.Reset();
+    HigherOrder::ThreeWayCompare(lhs_ptr() + Offset, rhs_ptr() + Offset, Size);
+    ASSERT_STREQ(lhs().writes, untouched);
+    ASSERT_STREQ(rhs().writes, untouched);
+    ASSERT_STREQ(lhs().reads, expected);
+    ASSERT_STREQ(rhs().reads, expected);
+    Observer.Reset();
+    HigherOrder::SplatSet(dst_ptr() + Offset, 5, Size);
+    ASSERT_STREQ(src().reads, untouched);
+    ASSERT_STREQ(src().writes, untouched);
+    ASSERT_STREQ(dst().reads, untouched);
+    ASSERT_STREQ(dst().writes, expected);
+  }
+
+  void checkMaxAccess(const BufferAccess &expected, int max) {
+    for (size_t i = 0; i < kMaxBuffer; ++i) {
+      int value = (int)expected[i] - '0';
+      if (value < 0 || value > max) {
+        printf("expected no more than %d access, was '%s'\n", max,
+               (const char *)expected);
+        ASSERT_LE(value, max);
+      }
+    }
+  }
+
+private:
+  const Buffer &lhs() const { return Observer.Buffer1; }
+  const Buffer &rhs() const { return Observer.Buffer2; }
+  const Buffer &src() const { return Observer.Buffer2; }
+  const Buffer &dst() const { return Observer.Buffer1; }
+  Buffer &dst() { return Observer.Buffer1; }
+
+  char *dst_ptr() { return dst().data.begin(); }
+  const char *src_ptr() { return src().data.begin(); }
+  const char *lhs_ptr() { return lhs().data.begin(); }
+  const char *rhs_ptr() { return rhs().data.begin(); }
+};
+
+template <typename ParamType>
+struct LlvmLibcTestAccessTail : public LlvmLibcTestAccessBase {
+
+  void TearDown() override {
+    static constexpr size_t Size = 10;
+
+    BufferAccess expected;
+    expected.Touch(Size - ParamType::kSize, ParamType::kSize);
+
+    checkMaxAccess(expected, 1);
+    checkOperations<Tail<ParamType>, Size>(expected);
+  }
+};
+TYPED_TEST_F(LlvmLibcTestAccessTail, Operations, Types) {}
+
+template <typename ParamType>
+struct LlvmLibcTestAccessHeadTail : public LlvmLibcTestAccessBase {
+  void TearDown() override {
+    static constexpr size_t Size = 10;
+
+    BufferAccess expected;
+    expected.Touch(0, ParamType::kSize);
+    expected.Touch(Size - ParamType::kSize, ParamType::kSize);
+
+    checkMaxAccess(expected, 2);
+    checkOperations<HeadTail<ParamType>, Size>(expected);
+  }
+};
+TYPED_TEST_F(LlvmLibcTestAccessHeadTail, Operations, Types) {}
+
+template <typename ParamType>
+struct LlvmLibcTestAccessLoop : public LlvmLibcTestAccessBase {
+  void TearDown() override {
+    static constexpr size_t Size = 20;
+
+    BufferAccess expected;
+    for (size_t i = 0; i < Size - ParamType::kSize; i += ParamType::kSize)
+      expected.Touch(i, ParamType::kSize);
+    expected.Touch(Size - ParamType::kSize, ParamType::kSize);
+
+    checkMaxAccess(expected, 2);
+    checkOperations<Loop<ParamType>, Size>(expected);
+  }
+};
+TYPED_TEST_F(LlvmLibcTestAccessLoop, Operations, Types) {}
+
+template <typename ParamType>
+struct LlvmLibcTestAccessAlignedAccess : public LlvmLibcTestAccessBase {
+  void TearDown() override {
+    static constexpr size_t Size = 10;
+    static constexpr size_t Offset = 2;
+    using AlignmentT = TestingElement<4>;
+
+    BufferAccess expected;
+    expected.Touch(Offset, AlignmentT::kSize);
+    expected.Touch(AlignmentT::kSize, ParamType::kSize);
+    expected.Touch(Offset + Size - ParamType::kSize, ParamType::kSize);
+
+    checkMaxAccess(expected, 3);
+    checkOperations<Align<AlignmentT, Arg::_1>::Then<HeadTail<ParamType>>, Size,
+                    Offset>(expected);
+    checkOperations<Align<AlignmentT, Arg::_2>::Then<HeadTail<ParamType>>, Size,
+                    Offset>(expected);
+  }
+};
+TYPED_TEST_F(LlvmLibcTestAccessAlignedAccess, Operations, Types) {}
+
+} // namespace __llvm_libc