[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

14

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

14

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

14

@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

14

@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

14

@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 ↗

(On Diff #351796)

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 ↗

(On Diff #351796)

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/memory_utils/CMakeLists.txt

 add_header_library(
   memory_utils
   HDRS
     utils.h
+    elements.h
     memcpy_utils.h
     memset_utils.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 {
+
+// Fixed-size 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.
+
+// Copies 'Element::kSize' bytes from 'src' to 'dst'.
+template <typename Element>
+void Copy(char *__restrict dst, const char *__restrict src) {
+  Element::Copy(dst, src);
+}
+
+// Checks whether the 'Element::kSize' first bytes of 'lhs' and 'rhs' compare
+// equal.
+template <typename Element> bool Equals(const char *lhs, const char *rhs) {
+  return Element::Equals(lhs, rhs);
+}
+
+// Computes the three-way comparison of the 'Element::kSize' first bytes
+// between 'lhs' and 'rhs'.
+template <typename Element>
+int ThreeWayCompare(const char *lhs, const char *rhs) {
+  return Element::ThreeWayCompare(lhs, rhs);
+}
+
+// Sets the 'Element::kSize' first bytes of 'dst' to 'value'.
+template <typename Element>
+void SplatSet(char *dst, const unsigned char value) {
+  Element::SplatSet(dst, value);
+}
+
+// Fixed-size Scalar Operations
+// ----------------------------
+
+// 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);
+  const int64_t diff = la - lb;
+  return diff ? (diff < 0 ? -1 : 1) : 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);
+  const __int128_t diff = la - lb;
+  return diff ? (diff < 0 ? -1 : 1) : 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
+
+// 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 Elementary Operations
+// ----------------------------------
+// We define abstract elementary operations acting on chunks of memory.
+// These are low level building blocks that are meant to be assembled to compose
+// higher order abstractions.
+
+// Copies 'Element::kSize' bytes from 'src' to 'dst'.
+template <typename Element>
+void Copy(char *__restrict dst, const char *__restrict src, size_t size) {
+  Element::Copy(dst, src, size);
+}
+
+// Checks whether the 'Element::kSize' first bytes of 'lhs' and 'rhs' compare
+// equal.
+template <typename Element>
+bool Equals(const char *lhs, const char *rhs, size_t size) {
+  return Element::Equals(lhs, rhs, size);
+}
+
+// Computes the three-way comparison of the 'Element::kSize' first bytes
+// between 'lhs' and 'rhs'.
+template <typename Element>
+int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) {
+  return Element::ThreeWayCompare(lhs, rhs, size);
+}
+
+// Sets the 'Element::kSize' first bytes of 'dst' to 'value'.
+template <typename Element>
+void SplatSet(char *dst, const unsigned char value, size_t size) {
+  Element::SplatSet(dst, value, size);
+}
+
+// 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);
+  }
+};
+
+// Same as 'Loop' but starts with a first operation to align underlying buffers.
+//
+// e.g. with
+// [12345678123456781234567812345678]
+// [__XXXXXXXXXXXXXXXXXXXXXXXXXXXX___]
+// [__XXXX___________________________]
+// [_____XXXXXXXX____________________]
+// [_____________XXXXXXXX____________]
+// [_____________________XXXXXXXX____]
+// [______________________XXXXXXXX___]
+//
+// Precondition:
+// - size >= T::kSize
+// - AlignmentT::kSize >= 1
+template <typename T, typename AlignmentT, bool AlignOnFirstPointer>
+struct AlignedLoop {
+private:
+  static_assert(AlignmentT::kSize > 1, "Alignment must be more than 1");
+  static_assert(is_power2(AlignmentT::kSize), "Alignment must be a power of 2");
+
+  static intptr_t offset_from_last_aligned(const void *a, const void *b) {
+    return ::__llvm_libc::offset_from_last_aligned<AlignmentT::kSize>(
+        AlignOnFirstPointer ? a : b);
+  }
+
+public:
+  static void Copy(char *__restrict dst, const char *__restrict src,
+                   size_t size) {
+    AlignmentT::Copy(dst, src);
+    const size_t ofla = offset_from_last_aligned(dst, src);
+    Loop<T>::Copy(dst + ofla, src + ofla, size - ofla);
+  }
+
+  static bool Equals(const char *lhs, const char *rhs, size_t size) {
+    if (!AlignmentT::Equals(lhs, rhs))
+      return false;
+    const size_t ofla = offset_from_last_aligned(lhs, rhs);
+    return Loop<T>::Equals(lhs + ofla, rhs + ofla, size - ofla);
+  }
+
+  static int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) {
+    if (const int result = AlignmentT::ThreeWayCompare(lhs, rhs))
+      return result;
+    const size_t ofla = offset_from_last_aligned(lhs, rhs);
+    return Loop<T>::ThreeWayCompare(lhs + ofla, rhs + ofla, size - ofla);
+  }
+
+  static void SplatSet(char *dst, const unsigned char value, size_t size) {
+    AlignmentT::SplatSet(dst, value);
+    const size_t ofla = offset_from_last_aligned(dst, dst);
+    Loop<T>::SplatSet(dst + ofla, value, size - ofla);
+  }
+};
+
+} // 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__
+
+// 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__
+
+} // namespace x86
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_X86_H

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
+    -march=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"
+#include <cstring>
+
+namespace __llvm_libc {
+
+// Registering Types
+using FixedSizeTypes = testing::TypeList<
+#ifdef __SSE2__
+    x86::Vector128,               //
+    Repeated<x86::Vector128, 2>,  //
+    Repeated<x86::Vector128, 4>,  //
+    Repeated<x86::Vector128, 8>,  //
+    Repeated<x86::Vector128, 16>, //
+#endif                            // __SSE2__
+#ifdef __AVX2__
+    x86::Vector256,              //
+    Repeated<x86::Vector256, 2>, //
+    Repeated<x86::Vector256, 4>, //
+    Repeated<x86::Vector256, 8>, //
+#endif                           // __AVX2__
+#if defined(__AVX512F__) and defined(__AVX512BW__)
+    x86::Vector512,              //
+    Repeated<x86::Vector512, 2>, //
+    Repeated<x86::Vector512, 4>, //
+#endif                      // defined(__AVX512F__) and defined(__AVX512BW__)
+    UINT8,                  //
+    UINT16,                 //
+    UINT32,                 //
+    UINT64,                 //
+    Repeated<UINT64, 2>,    //
+    Repeated<UINT64, 4>,    //
+    Repeated<UINT64, 8>,    //
+    Repeated<UINT64, 16>,   //
+    Repeated<UINT64, 32>,   //
+    Chained<UINT16, UINT8>, //
+    Chained<UINT32, UINT16, UINT8>>;
+
+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/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 LlvmLibcTestAccessAlignedLoop : public LlvmLibcTestAccessBase {
+  void TearDown() override {
+    static constexpr size_t Size = 10;
+    static constexpr size_t Offset = 2;
+    static constexpr size_t Alignment = 4;
+    using AlignmentT = TestingElement<Alignment>;
+
+    BufferAccess expected;
+    expected.Touch(Offset, AlignmentT::kSize);
+    for (size_t i = AlignmentT::kSize; i < Offset + Size - ParamType::kSize;
+         i += ParamType::kSize)
+      expected.Touch(i, ParamType::kSize);
+    expected.Touch(Offset + Size - ParamType::kSize, ParamType::kSize);
+
+    checkMaxAccess(expected, 3);
+    checkOperations<AlignedLoop<ParamType, AlignmentT, true>, Size, Offset>(
+        expected);
+  }
+};
+TYPED_TEST_F(LlvmLibcTestAccessAlignedLoop, Operations, Types) {}
+
+} // namespace __llvm_libc