[libc] Optimized version of memmove

[gchatelet]

Summary

This implementation relies on storing data in registers for sizes up to 128B.
Then depending on whether dst is less (resp. greater) than src we move data forward (resp. backward) by chunks of 32B.
We first make sure one of the pointers is aligned to increase performance on large move sizes.

[sivachandra]

libc/test/src/string/memmove_test.cpp

15

Including cstdio and functional from tests is not allowed.

23

For things like this, you should use a matcher. Look at this for example: https://github.com/llvm/llvm-project/blob/main/libc/utils/UnitTest/FPMatcher.h#L26.

You can probably implement a matcher which can used like this: EXPECT_MEM_EQ(mem1, mem2, size)

[avieira]

Hi @gchatelet,

I'm working on an aarch64 optimised version and I came across something that might be of use to you too. I found that the Repeated implementation of Move was yielding sub-optimal code in the large loop, it would load a _64 element in reverse (last 32-bytes first), I believe this was a side-effect of how it was stacking the loads and stores in opposite order like:
Load (src)
Load (src + 8)
Load (src + 16)
Load (src + 32)
Store (src + 32)
Store (src + 16)
...

I found that changing the implementation of the Repeated Move to a for-loop of loads followed by a for-loop of stores from 0 to ElementCount solved it and gave me a speed up on larger memmoves.

One of the things I am looking at now is weaving the loads and stores, as we've seen some improvements in some of our cores using interleaved series of LDP-STPs(64-byte loads and stores). Obviously that means that for backwards copies I need to do the end ones first so I'd probably only do it for the loop and use an aarch64-only elements one with a forwards weaving _64::Move and one backwards.

[gchatelet]

• rebase and conform to new style

[gchatelet]

In D114637#3199471, @avieira wrote:

Hi @gchatelet,

I'm working on an aarch64 optimised version and I came across something that might be of use to you too. I found that the Repeated implementation of Move was yielding sub-optimal code in the large loop, it would load a _64 element in reverse (last 32-bytes first), I believe this was a side-effect of how it was stacking the loads and stores in opposite order like:
Load (src)
Load (src + 8)
Load (src + 16)
Load (src + 32)
Store (src + 32)
Store (src + 16)
...

Do you have an idea of why this is yielding suboptimal results?
In the code I generated for x86-64, using this pyramid shape offset pattern reduced the number of instructions (the compiler could outline the last store across different functions).
I'm not sure this translated into better performance though, only slightly smaller function size.

I found that changing the implementation of the Repeated Move to a for-loop of loads followed by a for-loop of stores from 0 to ElementCount solved it and gave me a speed up on larger memmoves.

Could you share the resulting asm?

libc/test/src/string/memmove_test.cpp

23

I've been lazy :D Thx for pointing this out.

[gchatelet]

• Add MemoryMatcher util and simplify tests

[gchatelet]

• Fix typo

[gchatelet]

• rebase

[gchatelet]

• rebase
• squash
• tune the implementation a bit further (less cases, smaller alignment and larger loop size)

[gchatelet]

rebasing

[gchatelet]

@avieira Shall I transform

static void move(char *dst, const char *src) {
  const auto value = Element::load(src);
  Repeated<Element, ElementCount - 1>::move(dst + Element::SIZE, src + Element::SIZE);
  Element::store(dst, value);
}

into

static void move(char *dst, const char *src) {
  const auto value = load(src);
  store(dst, value);
}

before submitting?
As discussed offline, this seems to help on aarch64 but doesn't seem to affect x86.

[avieira]

In D114637#3300668, @gchatelet wrote:

@avieira Shall I transform

static void move(char *dst, const char *src) {
  const auto value = Element::load(src);
  Repeated<Element, ElementCount - 1>::move(dst + Element::SIZE, src + Element::SIZE);
  Element::store(dst, value);
}

into

static void move(char *dst, const char *src) {
  const auto value = load(src);
  store(dst, value);
}

before submitting?
As discussed offline, this seems to help on aarch64 but doesn't seem to affect x86.

Yes please!

[avieira]

In D114637#3231652, @gchatelet wrote:

In D114637#3199471, @avieira wrote:

Hi @gchatelet,

I'm working on an aarch64 optimised version and I came across something that might be of use to you too. I found that the Repeated implementation of Move was yielding sub-optimal code in the large loop, it would load a _64 element in reverse (last 32-bytes first), I believe this was a side-effect of how it was stacking the loads and stores in opposite order like:
Load (src)
Load (src + 8)
Load (src + 16)
Load (src + 32)
Store (src + 32)
Store (src + 16)
...

Do you have an idea of why this is yielding suboptimal results?
In the code I generated for x86-64, using this pyramid shape offset pattern reduced the number of instructions (the compiler could outline the last store across different functions).
I'm not sure this translated into better performance though, only slightly smaller function size.

I found that changing the implementation of the Repeated Move to a for-loop of loads followed by a for-loop of stores from 0 to ElementCount solved it and gave me a speed up on larger memmoves.

Could you share the resulting asm?

Sorry I hadn't seen this earlier, notification must have fallen through the cracks, but I'll share here the same I shared with you, I won't share the full memmove function as that is a lot of code, but basically the difference in codegen between before and your change is that in the forward and backward loops the stores go from:
40fb14: ad011da6 stp q6, q7, [x13, #32]
40fb18: ad0015a4 stp q4, q5, [x13]
to:
40fb14: ad0015a4 stp q4, q5, [x13]
40fb18: ad011da6 stp q6, q7, [x13, #32]

And the latter is preferred on AArch64.

[gchatelet]

• Non recursive Repeated::move implementation

libc/src/__support/CPP/ArrayRef.h

static_assert(
       IsSameV<T, RemoveCVType<T>>,
       "MutableArrayRef must have a non-const, non-volatile value_type");
   using Impl = internal::ArrayRefBase<T>;
   using Impl::Impl;
 
 public:
   // From Array.
   template <size_t N> MutableArrayRef(Array<T, N> &Arr) : Impl(Arr.Data, N) {}
+
+  operator ArrayRef<T>() const {
+    return ArrayRef<T>(this->data(), this->size());
+  }
 };
 
 } // namespace cpp
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_SUPPORT_CPP_ARRAYREF_H

libc/src/string/CMakeLists.txt

 # ------------------------------------------------------------------------------
 
 function(add_memmove memmove_name)
   add_implementation(memmove ${memmove_name}
     SRCS ${LIBC_SOURCE_DIR}/src/string/memmove.cpp
     HDRS ${LIBC_SOURCE_DIR}/src/string/memmove.h
     DEPENDS
       .memory_utils.memory_utils
-      .memory_utils.memcpy_implementation
       libc.include.string
     COMPILE_OPTIONS
       -fno-builtin
     ${ARGN}
   )
 endfunction()
 
 if(${LIBC_TARGET_ARCHITECTURE_IS_X86})

libc/src/string/memmove.cpp

 //===-- Implementation of memmove -----------------------------------------===//
 //
 // 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/memmove.h"
 
 #include "src/__support/common.h"
 #include "src/__support/integer_operations.h"
-#include "src/string/memory_utils/memcpy_implementations.h"
+#include "src/string/memory_utils/elements.h"
 #include <stddef.h> // size_t, ptrdiff_t
 
 namespace __llvm_libc {
 
-static inline void move_byte_forward(char *dest_m, const char *src_m,
-                                     size_t count) {
-  for (size_t offset = 0; count; --count, ++offset)
-    dest_m[offset] = src_m[offset];
-}
-
-static inline void move_byte_backward(char *dest_m, const char *src_m,
-                                      size_t count) {
-  for (size_t offset = count - 1; count; --count, --offset)
-    dest_m[offset] = src_m[offset];
+static inline void inline_memmove(char *dst, const char *src, size_t count) {
+  using namespace __llvm_libc::scalar;
+  if (count == 0)
+    return;
+  if (count == 1)
+    return move<_1>(dst, src);
+  if (count <= 4)
+    return move<HeadTail<_2>>(dst, src, count);
+  if (count <= 8)
+    return move<HeadTail<_4>>(dst, src, count);
+  if (count <= 16)
+    return move<HeadTail<_8>>(dst, src, count);
+  if (count <= 32)
+    return move<HeadTail<_16>>(dst, src, count);
+  if (count <= 64)
+    return move<HeadTail<_32>>(dst, src, count);
+  if (count <= 128)
+    return move<HeadTail<_64>>(dst, src, count);
+
+  using AlignedMoveLoop = Align<_16, Arg::Src>::Then<Loop<_64>>;
+  if (dst < src)
+    return move<AlignedMoveLoop>(dst, src, count);
+  else if (dst > src)
+    return move_backward<AlignedMoveLoop>(dst, src, count);
 }
 
 LLVM_LIBC_FUNCTION(void *, memmove,
                    (void *dst, const void *src, size_t count)) {
-  char *dest_c = reinterpret_cast<char *>(dst);
-  const char *src_c = reinterpret_cast<const char *>(src);
-
-  // If the distance between `src_c` and `dest_c` is equal to or greater
-  // than `count` (integerAbs(src_c - dest_c) >= count), they would not overlap.
-  // e.g.   greater     equal       overlapping
-  //        [12345678]  [12345678]  [12345678]
-  // src_c: [_ab_____]  [_ab_____]  [_ab_____]
-  // dest_c:[_____yz_]  [___yz___]  [__yz____]
-
-  // Call `memcpy` if `src_c` and `dest_c` do not overlap.
-  if (__llvm_libc::integer_abs(src_c - dest_c) >=
-      static_cast<ptrdiff_t>(count)) {
-    inline_memcpy(dest_c, src_c, count);
-    return dest_c;
-  }
-
-  // Overlapping cases.
-  // If `dest_c` starts before `src_c` (dest_c < src_c), copy
-  // forward(pointer add 1) from beginning to end.
-  // If `dest_c` starts after `src_c` (dest_c > src_c), copy
-  // backward(pointer add -1) from end to beginning.
-  // If `dest_c` and `src_c` start at the same address (dest_c == src_c),
-  // just return dest.
-  // e.g.    forward      backward
-  //                *->    <-*
-  // src_c : [___abcde_]  [_abcde___]
-  // dest_c: [_abc--___]  [___--cde_]
-
-  // TODO: Optimize `move_byte_xxx(...)` functions.
-  if (dest_c < src_c)
-    move_byte_forward(dest_c, src_c, count);
-  if (dest_c > src_c)
-    move_byte_backward(dest_c, src_c, count);
+  inline_memmove(reinterpret_cast<char *>(dst),
+                 reinterpret_cast<const char *>(src), count);
   return dst;
 }
 
 } // namespace __llvm_libc

libc/src/string/memory_utils/elements.h

 // Fixed-size move from 'src' to 'dst'.
 template <typename Element> void move(char *dst, const char *src) {
   Element::move(dst, src);
 }
 // Runtime-size move from 'src' to 'dst'.
 template <typename Element> void move(char *dst, const char *src, size_t size) {
   Element::move(dst, src, size);
 }
+// Runtime-size move from 'src' to 'dst'.
+template <typename Element>
+void move_backward(char *dst, const char *src, size_t size) {
+  Element::move_backward(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) {
template <typename Element, size_t ElementCount> struct Repeated {
   static void copy(char *__restrict dst, const char *__restrict src) {
     for (size_t i = 0; i < ElementCount; ++i) {
       const size_t offset = i * Element::SIZE;
       Element::copy(dst + offset, src + offset);
     }
   }
 
   static void move(char *dst, const char *src) {
-    const auto value = Element::load(src);
-    Repeated<Element, ElementCount - 1>::move(dst + Element::SIZE,
-                                              src + Element::SIZE);
-    Element::store(dst, value);
+    const auto value = load(src);
+    store(dst, value);
   }
 
   static bool equals(const char *lhs, const char *rhs) {
     for (size_t i = 0; i < ElementCount; ++i) {
       const size_t offset = i * Element::SIZE;
       if (!Element::equals(lhs + offset, rhs + offset))
         return false;
     }
static void copy(char *__restrict dst, const char *__restrict src,
     size_t offset = 0;
     do {
       T::copy(dst + offset, src + offset);
       offset += T::SIZE;
     } while (offset < size - T::SIZE);
     Tail<TailT>::copy(dst, src, size);
   }
 
+  // Move forward suitable when dst < src. We load the tail bytes before
+  // handling the loop.
+  //
+  // e.g. Moving two bytes
+  // [   |       |       |       |       |]
+  // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___]
+  // [_________________________LLLLLLLL___]
+  // [___LLLLLLLL_________________________]
+  // [_SSSSSSSS___________________________]
+  // [___________LLLLLLLL_________________]
+  // [_________SSSSSSSS___________________]
+  // [___________________LLLLLLLL_________]
+  // [_________________SSSSSSSS___________]
+  // [_______________________SSSSSSSS_____]
+  static void move(char *dst, const char *src, size_t size) {
+    const size_t tail_offset = Tail<T>::offset(size);
+    const auto tail_value = TailT::load(src + tail_offset);
+    size_t offset = 0;
+    do {
+      T::move(dst + offset, src + offset);
+      offset += T::SIZE;
+    } while (offset < size - T::SIZE);
+    TailT::store(dst + tail_offset, tail_value);
+  }
+
+  // Move forward suitable when dst > src. We load the head bytes before
+  // handling the loop.
+  //
+  // e.g. Moving two bytes
+  // [   |       |       |       |       |]
+  // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___]
+  // [___LLLLLLLL_________________________]
+  // [_________________________LLLLLLLL___]
+  // [___________________________SSSSSSSS_]
+  // [_________________LLLLLLLL___________]
+  // [___________________SSSSSSSS_________]
+  // [_________LLLLLLLL___________________]
+  // [___________SSSSSSSS_________________]
+  // [_____SSSSSSSS_______________________]
+  static void move_backward(char *dst, const char *src, size_t size) {
+    const auto head_value = TailT::load(src);
+    ptrdiff_t offset = size - T::SIZE;
+    do {
+      T::move(dst + offset, src + offset);
+      offset -= T::SIZE;
+    } while (offset >= 0);
+    TailT::store(dst, head_value);
+  }
+
   static bool equals(const char *lhs, const char *rhs, size_t size) {
     size_t offset = 0;
     do {
       if (!T::equals(lhs + offset, rhs + offset))
         return false;
       offset += T::SIZE;
     } while (offset < size - T::SIZE);
     return Tail<TailT>::equals(lhs, rhs, size);
static void splat_set(char *dst, const unsigned char value, size_t size) {
     Tail<TailT>::splat_set(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 <Arg arg> struct ArgSelector {};
 
-template <size_t Alignment> struct AlignHelper<Arg::_1, Alignment> {
+template <> struct ArgSelector<Arg::_1> {
   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);
+  static T1 *__restrict &Select(T1 *__restrict &p1ref, T2 *__restrict &p2ref) {
+    return p1ref;
   }
 };
 
-template <size_t Alignment> struct AlignHelper<Arg::_2, Alignment> {
+template <> struct ArgSelector<Arg::_2> {
+  template <typename T1, typename T2>
+  static T2 *__restrict &Select(T1 *__restrict &p1ref, T2 *__restrict &p2ref) {
+    return p2ref;
+  }
+};
+
+// 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.
+// The 'additional_bumps' parameter allows to reach previous / next aligned
+// pointers.
+template <Arg arg, size_t Alignment> struct Align {
   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);
+  static void bump(T1 *__restrict &p1ref, T2 *__restrict &p2ref, size_t &size,
+                   int additional_bumps = 0) {
+    auto &aligned_ptr = ArgSelector<arg>::Select(p1ref, p2ref);
+    auto offset = offset_to_next_aligned<Alignment>(aligned_ptr);
+    offset += additional_bumps * Alignment;
     p1ref += offset;
     p2ref += offset;
     size -= offset;
-    p2ref = assume_aligned<Alignment>(p2ref);
+    aligned_ptr = assume_aligned<Alignment>(aligned_ptr);
   }
 };
 
 } // 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 = Arg::_1> struct Align {
 private:
   static constexpr size_t ALIGNMENT = AlignmentT::SIZE;
   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);
+      internal::Align<AlignOn, ALIGNMENT>::bump(dst, src, size);
       NextT::copy(dst, src, size);
     }
 
+    // Move forward suitable when dst < src. The alignment is performed with an
+    // HeadTail operation of size ∈ [Alignment, 2 x Alignment].
+    //
+    // e.g. Moving two bytes and making sure src is then aligned.
+    // [  |       |       |       |      ]
+    // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_]
+    // [____LLLLLLLL_____________________]
+    // [___________LLLLLLLL______________]
+    // [_SSSSSSSS________________________]
+    // [________SSSSSSSS_________________]
+    //
+    // e.g. Moving two bytes and making sure dst is then aligned.
+    // [  |       |       |       |      ]
+    // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_]
+    // [____LLLLLLLL_____________________]
+    // [______LLLLLLLL___________________]
+    // [_SSSSSSSS________________________]
+    // [___SSSSSSSS______________________]
+    static void move(char *dst, const char *src, size_t size) {
+      char *next_dst = dst;
+      const char *next_src = src;
+      size_t next_size = size;
+      internal::Align<AlignOn, ALIGNMENT>::bump(next_dst, next_src, next_size,
+                                                1);
+      HeadTail<AlignmentT>::move(dst, src, size - next_size);
+      NextT::move(next_dst, next_src, next_size);
+    }
+
+    // Move backward suitable when dst > src. The alignment is performed with an
+    // HeadTail operation of size ∈ [Alignment, 2 x Alignment].
+    //
+    // e.g. Moving two bytes backward and making sure src is then aligned.
+    // [  |       |       |       |      ]
+    // [____XXXXXXXXXXXXXXXXXXXXXXXX_____]
+    // [ _________________LLLLLLLL_______]
+    // [ ___________________LLLLLLLL_____]
+    // [____________________SSSSSSSS_____]
+    // [______________________SSSSSSSS___]
+    //
+    // e.g. Moving two bytes and making sure dst is then aligned.
+    // [  |       |       |       |      ]
+    // [____XXXXXXXXXXXXXXXXXXXXXXXX_____]
+    // [ _______________LLLLLLLL_________]
+    // [ ___________________LLLLLLLL_____]
+    // [__________________SSSSSSSS_______]
+    // [______________________SSSSSSSS___]
+    static void move_backward(char *dst, const char *src, size_t size) {
+      char *headtail_dst = dst + size;
+      const char *headtail_src = src + size;
+      size_t headtail_size = 0;
+      internal::Align<AlignOn, ALIGNMENT>::bump(headtail_dst, headtail_src,
+                                                headtail_size, -2);
+      HeadTail<AlignmentT>::move(headtail_dst, headtail_src, headtail_size);
+      NextT::move_backward(dst, src, size - headtail_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);
+      internal::Align<AlignOn, ALIGNMENT>::bump(lhs, rhs, size);
       return NextT::equals(lhs, rhs, size);
     }
 
     static int three_way_compare(const char *lhs, const char *rhs,
                                  size_t size) {
       if (!AlignmentT::equals(lhs, rhs))
         return AlignmentT::three_way_compare(lhs, rhs);
-      internal::AlignHelper<AlignOn, ALIGNMENT>::bump(lhs, rhs, size);
+      internal::Align<AlignOn, ALIGNMENT>::bump(lhs, rhs, size);
       return NextT::three_way_compare(lhs, rhs, size);
     }
 
     static void splat_set(char *dst, const unsigned char value, size_t size) {
       AlignmentT::splat_set(dst, value);
       char *dummy = nullptr;
-      internal::AlignHelper<Arg::_1, ALIGNMENT>::bump(dst, dummy, size);
+      internal::Align<Arg::_1, ALIGNMENT>::bump(dst, dummy, size);
       NextT::splat_set(dst, value, size);
     }
   };
 };
 
 // An operation that allows to skip the specified amount of bytes.
 template <ptrdiff_t Bytes> struct Skip {
   template <typename NextT> struct Then {

libc/test/src/string/CMakeLists.txt

if(can_run)
         SUITE
           libc_string_unittests
         DEPENDS
           ${fq_config_name}
         COMPILE_OPTIONS
           ${LIBC_COMPILE_OPTIONS_NATIVE}
         ${ARGN}
       )
+      get_fq_target_name(${fq_config_name}_test fq_target_name)
+      target_link_libraries(${fq_target_name} PRIVATE LibcMemoryHelpers)
     else()
       message(STATUS "Skipping test for '${fq_config_name}' insufficient host cpu features '${required_cpu_features}'")
     endif()
   endforeach()
 endfunction()
 
 add_libc_multi_impl_test(bcmp SRCS bcmp_test.cpp)
 add_libc_multi_impl_test(bzero SRCS bzero_test.cpp)
 add_libc_multi_impl_test(memcmp SRCS memcmp_test.cpp)
 add_libc_multi_impl_test(memcpy SRCS memcpy_test.cpp)
 add_libc_multi_impl_test(memmove SRCS memmove_test.cpp)
 add_libc_multi_impl_test(memset SRCS memset_test.cpp)

libc/test/src/string/memmove_test.cpp

 //===-- Unittests for memmove ---------------------------------------------===//
 //
 // 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/__support/CPP/ArrayRef.h"
 #include "src/string/memmove.h"
+#include "utils/UnitTest/MemoryMatcher.h"
 #include "utils/UnitTest/Test.h"
 
-class LlvmLibcMemmoveTest : public __llvm_libc::testing::Test {
-public:
-  void check_memmove(void *dst, const void *src, size_t count,
-                     const unsigned char *str,
-                     const __llvm_libc::cpp::ArrayRef<unsigned char> expected) {
-    void *result = __llvm_libc::memmove(dst, src, count);
-    // Making sure the pointer returned is same with `dst`.
-    EXPECT_EQ(result, dst);
-    // `expected` is designed according to `str`.
-    // `dst` and `src` might be part of `str`.
-    // Making sure `str` is same with `expected`.
-    for (size_t i = 0; i < expected.size(); ++i)
-      EXPECT_EQ(str[i], expected[i]);
-  }
-};
-
-TEST_F(LlvmLibcMemmoveTest, MoveZeroByte) {
-  unsigned char dst[] = {'a', 'b'};
-  const unsigned char src[] = {'y', 'z'};
-  const unsigned char expected[] = {'a', 'b'};
-  check_memmove(dst, src, 0, dst, expected);
-}
-
-TEST_F(LlvmLibcMemmoveTest, OverlapThatDstAndSrcPointToSameAddress) {
-  unsigned char str[] = {'a', 'b'};
-  const unsigned char expected[] = {'a', 'b'};
-  check_memmove(str, str, 1, str, expected);
+using __llvm_libc::cpp::Array;
+using __llvm_libc::cpp::ArrayRef;
+using __llvm_libc::cpp::MutableArrayRef;
+
+TEST(LlvmLibcMemmoveTest, MoveZeroByte) {
+  char Buffer[] = {'a', 'b', 'y', 'z'};
+  const char Expected[] = {'a', 'b', 'y', 'z'};
+  void *const Dst = Buffer;
+  void *const Ret = __llvm_libc::memmove(Dst, Buffer + 2, 0);
+  EXPECT_EQ(Ret, Dst);
+  EXPECT_MEM_EQ(Buffer, Expected);
+}
+
+TEST(LlvmLibcMemmoveTest, DstAndSrcPointToSameAddress) {
+  char Buffer[] = {'a', 'b'};
+  const char Expected[] = {'a', 'b'};
+  void *const Dst = Buffer;
+  void *const Ret = __llvm_libc::memmove(Dst, Buffer, 1);
+  EXPECT_EQ(Ret, Dst);
+  EXPECT_MEM_EQ(Buffer, Expected);
 }
 
-TEST_F(LlvmLibcMemmoveTest, OverlapThatDstStartsBeforeSrc) {
+TEST(LlvmLibcMemmoveTest, DstStartsBeforeSrc) {
   // Set boundary at beginning and end for not overstepping when
   // copy forward or backward.
-  unsigned char str[] = {'z', 'a', 'b', 'c', 'z'};
-  const unsigned char expected[] = {'z', 'b', 'c', 'c', 'z'};
-  // `dst` is `&str[1]`.
-  check_memmove(&str[1], &str[2], 2, str, expected);
+  char Buffer[] = {'z', 'a', 'b', 'c', 'z'};
+  const char Expected[] = {'z', 'b', 'c', 'c', 'z'};
+  void *const Dst = Buffer + 1;
+  void *const Ret = __llvm_libc::memmove(Dst, Buffer + 2, 2);
+  EXPECT_EQ(Ret, Dst);
+  EXPECT_MEM_EQ(Buffer, Expected);
+}
+
+TEST(LlvmLibcMemmoveTest, DstStartsAfterSrc) {
+  char Buffer[] = {'z', 'a', 'b', 'c', 'z'};
+  const char Expected[] = {'z', 'a', 'a', 'b', 'z'};
+  void *const Dst = Buffer + 2;
+  void *const Ret = __llvm_libc::memmove(Dst, Buffer + 1, 2);
+  EXPECT_EQ(Ret, Dst);
+  EXPECT_MEM_EQ(Buffer, Expected);
 }
 
-TEST_F(LlvmLibcMemmoveTest, OverlapThatDstStartsAfterSrc) {
-  unsigned char str[] = {'z', 'a', 'b', 'c', 'z'};
-  const unsigned char expected[] = {'z', 'a', 'a', 'b', 'z'};
-  check_memmove(&str[2], &str[1], 2, str, expected);
-}
-
-// e.g. `dst` follow `src`.
+// e.g. `Dst` follow `src`.
 // str: [abcdefghij]
 //      [__src_____]
-//      [_____dst__]
-TEST_F(LlvmLibcMemmoveTest, SrcFollowDst) {
-  unsigned char str[] = {'z', 'a', 'b', 'z'};
-  const unsigned char expected[] = {'z', 'b', 'b', 'z'};
-  check_memmove(&str[1], &str[2], 1, str, expected);
+//      [_____Dst__]
+TEST(LlvmLibcMemmoveTest, SrcFollowDst) {
+  char Buffer[] = {'z', 'a', 'b', 'z'};
+  const char Expected[] = {'z', 'b', 'b', 'z'};
+  void *const Dst = Buffer + 1;
+  void *const Ret = __llvm_libc::memmove(Dst, Buffer + 2, 1);
+  EXPECT_EQ(Ret, Dst);
+  EXPECT_MEM_EQ(Buffer, Expected);
+}
+
+TEST(LlvmLibcMemmoveTest, DstFollowSrc) {
+  char Buffer[] = {'z', 'a', 'b', 'z'};
+  const char Expected[] = {'z', 'a', 'a', 'z'};
+  void *const Dst = Buffer + 2;
+  void *const Ret = __llvm_libc::memmove(Dst, Buffer + 1, 1);
+  EXPECT_EQ(Ret, Dst);
+  EXPECT_MEM_EQ(Buffer, Expected);
+}
+
+static constexpr int kMaxSize = 512;
+
+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;
+}
+
+void Randomize(MutableArrayRef<char> Buffer) {
+  for (auto &current : Buffer)
+    current = GetRandomChar();
+}
+
+TEST(LlvmLibcMemmoveTest, Thorough) {
+  using LargeBuffer = Array<char, 3 * kMaxSize>;
+  LargeBuffer GroundTruth;
+  Randomize(GroundTruth);
+  for (int Size = 0; Size < kMaxSize; ++Size) {
+    for (int Offset = -Size; Offset < Size; ++Offset) {
+      LargeBuffer Buffer = GroundTruth;
+      LargeBuffer Expected = GroundTruth;
+      size_t DstOffset = kMaxSize;
+      size_t SrcOffset = kMaxSize + Offset;
+      for (int I = 0; I < Size; ++I)
+        Expected[DstOffset + I] = GroundTruth[SrcOffset + I];
+      void *const Dst = Buffer.data() + DstOffset;
+      void *const Ret =
+          __llvm_libc::memmove(Dst, Buffer.data() + SrcOffset, Size);
+      EXPECT_EQ(Ret, Dst);
+      EXPECT_MEM_EQ(Buffer, Expected);
+    }
   }
-
-TEST_F(LlvmLibcMemmoveTest, DstFollowSrc) {
-  unsigned char str[] = {'z', 'a', 'b', 'z'};
-  const unsigned char expected[] = {'z', 'a', 'a', 'z'};
-  check_memmove(&str[2], &str[1], 1, str, expected);
 }

libc/utils/UnitTest/CMakeLists.txt

 target_include_directories(LibcFPTestHelpers PUBLIC ${LIBC_SOURCE_DIR})
 target_link_libraries(LibcFPTestHelpers LibcUnitTest)
 add_dependencies(
   LibcFPTestHelpers
   LibcUnitTest
   libc.src.__support.CPP.standalone_cpp
   libc.src.__support.FPUtil.fputil
 )
+
+add_library(
+  LibcMemoryHelpers
+    MemoryMatcher.h
+    MemoryMatcher.cpp
+)
+target_include_directories(LibcMemoryHelpers PUBLIC ${LIBC_SOURCE_DIR})
+target_link_libraries(LibcMemoryHelpers LibcUnitTest)
+add_dependencies(
+  LibcMemoryHelpers
+  LibcUnitTest
+  libc.src.__support.CPP.standalone_cpp
+)

libc/utils/UnitTest/MemoryMatcher.h

+//===-- MemoryMatcher.h -----------------------------------------*- 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 LLVM_LIBC_UTILS_UNITTEST_MEMORY_MATCHER_H
+#define LLVM_LIBC_UTILS_UNITTEST_MEMORY_MATCHER_H
+
+#include "src/__support/CPP/ArrayRef.h"
+
+#include "utils/UnitTest/Test.h"
+
+namespace __llvm_libc {
+namespace memory {
+namespace testing {
+
+using MemoryView = __llvm_libc::cpp::ArrayRef<char>;
+
+class MemoryMatcher : public __llvm_libc::testing::Matcher<MemoryView> {
+  MemoryView expected;
+  MemoryView actual;
+
+public:
+  MemoryMatcher(MemoryView expectedValue) : expected(expectedValue) {}
+
+  bool match(MemoryView actualValue);
+
+  void explainError(testutils::StreamWrapper &stream) override;
+};
+
+} // namespace testing
+} // namespace memory
+} // namespace __llvm_libc
+
+#define EXPECT_MEM_EQ(expected, actual)                                        \
+  EXPECT_THAT(actual, __llvm_libc::memory::testing::MemoryMatcher(expected))
+
+#endif // LLVM_LIBC_UTILS_UNITTEST_MEMORY_MATCHER_H

libc/utils/UnitTest/MemoryMatcher.cpp

+//===-- MemoryMatcher.cpp ---------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "MemoryMatcher.h"
+
+namespace __llvm_libc {
+namespace memory {
+namespace testing {
+
+bool MemoryMatcher::match(MemoryView actualValue) {
+  actual = actualValue;
+  return expected.equals(actual);
+}
+
+void display(testutils::StreamWrapper &Stream, char C) {
+  const auto print = [&Stream](unsigned char I) {
+    Stream << static_cast<char>(I < 10 ? '0' + I : 'A' + I - 10);
+  };
+  print(static_cast<unsigned char>(C) / 16);
+  print(static_cast<unsigned char>(C) & 15);
+}
+
+void display(testutils::StreamWrapper &Stream, MemoryView View) {
+  for (auto C : View) {
+    Stream << ' ';
+    display(Stream, C);
+  }
+}
+
+void MemoryMatcher::explainError(testutils::StreamWrapper &Stream) {
+  Stream << "expected :";
+  display(Stream, expected);
+  Stream << '\n';
+  Stream << "actual   :";
+  display(Stream, actual);
+  Stream << '\n';
+}
+
+} // namespace testing
+} // namespace memory
+} // namespace __llvm_libc