[libc] Add memcpy with software prefetcher

[Matt]

libc/src/string/memory_utils/op_x86.h

50

Perhaps you may be able to reuse the cache line information in the subtargets, e.g.,

• CacheLineSize, https://github.com/llvm/llvm-project/blob/d036bf071111001aadf3fc8cbbf058246046a62e/llvm/lib/Target/AArch64/AArch64Subtarget.cpp#L101
• exposed via getCacheLineSize(), https://github.com/llvm/llvm-project/blob/1ee4d880e8760256c606fe55b7af85a4f70d006d/llvm/lib/Target/AArch64/AArch64Subtarget.h#L234
• cf. getCPUCacheLineSize for X86, https://github.com/llvm/llvm-project/blob/1ee4d880e8760256c606fe55b7af85a4f70d006d/clang/lib/Basic/Targets/X86.cpp#L1376

[gchatelet]

This has been submitted as https://reviews.llvm.org/D154494

[gchatelet]

libc/src/string/memory_utils/op_x86.h

50

Unfortunately LLVM libc doesn't have access to LLVM sources, to implement a libc you need to be very careful about the dependencies you're pulling in. We can only import very specific macro defining C headers, that's it.

[Matt]

I see, this makes sense, thanks!

libc/src/string/memory_utils/CMakeLists.txt

HDRS
     op_builtin.h
     op_generic.h
     op_x86.h
     utils.h
   DEPS
     libc.src.__support.CPP.bit
     libc.src.__support.CPP.cstddef
     libc.src.__support.CPP.type_traits
+    libc.src.__support.macros.compiler
     libc.src.__support.macros.config
     libc.src.__support.macros.optimization
 )
 
 add_header_library(
   memcpy_implementation
   HDRS
     memcpy_implementations.h

libc/src/string/memory_utils/op_builtin.h

#endif
   }
 
   LIBC_INLINE static void head_tail(Ptr __restrict dst, CPtr __restrict src,
                                     size_t count) {
     block(dst, src);
     tail(dst, src, count);
   }
 
-  LIBC_INLINE static void loop_and_tail(Ptr __restrict dst, CPtr __restrict src,
-                                        size_t count) {
+  LIBC_INLINE static void loop(Ptr __restrict dst, CPtr __restrict src,
+                               size_t count, size_t offset = 0) {
     static_assert(Size > 1, "a loop of size 1 does not need tail");
-    size_t offset = 0;
-    do {
+    for (; offset < (count - SIZE); offset += SIZE)
       block(dst + offset, src + offset);
-      offset += SIZE;
-    } while (offset < count - SIZE);
+  }
+
+  LIBC_INLINE static void loop_and_tail(Ptr __restrict dst, CPtr __restrict src,
+                                        size_t count) {
+    loop(dst, src, count);
     tail(dst, src, count);
   }
 };
 
 ///////////////////////////////////////////////////////////////////////////////
 // Memset
 template <size_t Size> struct Memset {
   using ME = Memset;

libc/src/string/memory_utils/op_x86.h

 #ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_X86_H
 #define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_X86_H
 
 #include "src/__support/macros/properties/architectures.h"
 
 #if defined(LIBC_TARGET_ARCH_IS_X86_64)
 
 #include "src/__support/common.h"
+#include "src/__support/macros/properties/compiler.h"
 #include "src/string/memory_utils/op_builtin.h"
 #include "src/string/memory_utils/op_generic.h"
 
 #if defined(__AVX512BW__) || defined(__AVX512F__) || defined(__AVX2__) ||      \
     defined(__SSE2__)
 #include <immintrin.h>
 #endif
 

 
 // A set of constants to check compile time features.
 static inline constexpr bool kSse2 = LLVM_LIBC_IS_DEFINED(__SSE2__);
 static inline constexpr bool kAvx = LLVM_LIBC_IS_DEFINED(__AVX__);
 static inline constexpr bool kAvx2 = LLVM_LIBC_IS_DEFINED(__AVX2__);
 static inline constexpr bool kAvx512F = LLVM_LIBC_IS_DEFINED(__AVX512F__);
 static inline constexpr bool kAvx512BW = LLVM_LIBC_IS_DEFINED(__AVX512BW__);
 
+static constexpr size_t kCachelineSize = 64;
+
+LIBC_INLINE void read_prefetch_local(CPtr __restrict src) {
+#if defined(LIBC_COMPILER_IS_CLANG) || defined(LIBC_COMPILER_IS_GCC)
+  // This call has the same semantic between GCC and Clang.
+  // https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
+  // https://clang.llvm.org/docs/LanguageExtensions.html#builtin-prefetch
+  // It's a read prefetch with maximum locality.
+  __builtin_prefetch(src);
+#else
+#error "Unknown compiler, can't generate prefetch instruction"
+#endif
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 // Memcpy repmovsb implementation
-struct Memcpy {
-  static void repmovsb(void *dst, const void *src, size_t count) {
-    asm volatile("rep movsb" : "+D"(dst), "+S"(src), "+c"(count) : : "memory");
+
+template <size_t Size> struct MemcpyPrefetch {
+  static_assert(Size % kCachelineSize == 0,
+                "Size must be a multiple of cache lines");
+  static constexpr size_t kCacheLines = Size / kCachelineSize;
+
+  LIBC_INLINE static void block(Ptr __restrict dst, CPtr __restrict src) {
+    for (size_t i = 1; i < kCacheLines + 1; ++i)
+      read_prefetch_local(src + (kCachelineSize * i));
+    builtin::Memcpy<Size>::block(dst, src);
+  }
+
+  LIBC_INLINE static void loop(Ptr __restrict dst, CPtr __restrict src,
+                               size_t count, size_t offset = 0) {
+    static_assert(Size > 1, "a loop of size 1 does not need tail");
+    for (; offset < (count - Size); offset += Size)
+      block(dst + offset, src + offset);
+    builtin::Memcpy<32>::loop(dst, src, count, offset);
+    builtin::Memcpy<32>::tail(dst, src, count);
   }
 };
 
+LIBC_INLINE void repmovsb(void *dst, const void *src, size_t count) {
+  asm volatile("rep movsb" : "+D"(dst), "+S"(src), "+c"(count) : : "memory");
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 // Bcmp
 
 // Base implementation for the Bcmp specializations.
 //  - BlockSize is either 16, 32 or 64 depending on the available compile time
 // features, it is used to switch between "single native operation" or a
 // "sequence of native operations".
 //  - BlockBcmp is the function that implements the bcmp logic.

libc/src/string/memory_utils/utils.h

 //===-- Memory 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 LLVM_LIBC_SRC_MEMORY_UTILS_UTILS_H
 #define LLVM_LIBC_SRC_MEMORY_UTILS_UTILS_H
 
 #include "src/__support/CPP/bit.h"
 #include "src/__support/CPP/cstddef.h"
 #include "src/__support/CPP/type_traits.h"
-#include "src/__support/macros/attributes.h"          //LIBC_INLINE
+#include "src/__support/macros/attributes.h"          // LIBC_INLINE
 #include "src/__support/macros/config.h"              // LIBC_HAS_BUILTIN
 
 #include <stddef.h> // size_t
 #include <stdint.h> // intptr_t / uintptr_t
 
 namespace __llvm_libc {
 
 // Allows compile time error reporting in `if constexpr` branches.

libc/src/string/memory_utils/x86_64/memcpy_implementations.h

 #include "src/string/memory_utils/op_x86.h"
 #include "src/string/memory_utils/utils.h"
 
 #include <stddef.h> // size_t
 
 namespace __llvm_libc {
 
 [[maybe_unused]] LIBC_INLINE void
-inline_memcpy_x86(Ptr __restrict dst, CPtr __restrict src, size_t count) {
+inline_memcpy_x86_hw_prefetch(Ptr __restrict dst, CPtr __restrict src,
+                              size_t count) {
   if (count == 0)
     return;
   if (count == 1)
     return builtin::Memcpy<1>::block(dst, src);
   if (count == 2)
     return builtin::Memcpy<2>::block(dst, src);
   if (count == 3)
     return builtin::Memcpy<3>::block(dst, src);
if (x86::kAvx && count < 256)
     return builtin::Memcpy<128>::head_tail(dst, src, count);
   builtin::Memcpy<32>::block(dst, src);
   align_to_next_boundary<32, Arg::Dst>(dst, src, count);
   static constexpr size_t kBlockSize = x86::kAvx ? 64 : 32;
   return builtin::Memcpy<kBlockSize>::loop_and_tail(dst, src, count);
 }
 
 [[maybe_unused]] LIBC_INLINE void
+inline_memcpy_x86_sw_prefetch(Ptr __restrict dst, CPtr __restrict src,
+                              size_t count) {
+  if (count == 0)
+    return;
+  if (count == 1)
+    return builtin::Memcpy<1>::block(dst, src);
+  if (count == 2)
+    return builtin::Memcpy<2>::block(dst, src);
+  if (count == 3)
+    return builtin::Memcpy<3>::block(dst, src);
+  if (count == 4)
+    return builtin::Memcpy<4>::block(dst, src);
+  if (count < 8)
+    return builtin::Memcpy<4>::head_tail(dst, src, count);
+  if (count < 16)
+    return builtin::Memcpy<8>::head_tail(dst, src, count);
+  if (count < 32)
+    return builtin::Memcpy<16>::head_tail(dst, src, count);
+  if (count < 64)
+    return builtin::Memcpy<32>::head_tail(dst, src, count);
+  x86::read_prefetch_local(src + x86::kCachelineSize);
+  if (count < 128)
+    return builtin::Memcpy<64>::head_tail(dst, src, count);
+  x86::read_prefetch_local(src + (2 * x86::kCachelineSize));
+  // Align to 32B
+  builtin::Memcpy<32>::block(dst, src);
+  align_to_next_boundary<32, Arg::Dst>(dst, src, count);
+  // Invariant count >= 96.
+  if (count >= 128) {
+    if (count < 352)
+      x86::MemcpyPrefetch<128>::loop(dst, src, count);
+    else
+      x86::MemcpyPrefetch<192>::loop(dst, src, count);
+  }
+  if (count >= 32)
+    builtin::Memcpy<32>::loop(dst, src, count);
+  builtin::Memcpy<32>::tail(dst, src, count);
+}
+
+[[maybe_unused]] LIBC_INLINE void
+inline_memcpy_x86(Ptr __restrict dst, CPtr __restrict src, size_t count) {
+#ifdef LIBC_COPT_MEMCPY_X86_USE_SOFTWARE_PREFETCHER
+  return inline_memcpy_x86_sw_prefetch(dst, src, count);
+#else
+  return inline_memcpy_x86_hw_prefetch(dst, src, count);
+#endif //  LIBC_COPT_MEMCPY_X86_USE_SOFTWARE_PREFETCHER
+}
+
+[[maybe_unused]] LIBC_INLINE void
 inline_memcpy_x86_maybe_interpose_repmovsb(Ptr __restrict dst,
                                            CPtr __restrict src, size_t count) {
   // Whether to use rep;movsb exclusively, not at all, or only above a certain
   // threshold.
 #ifndef LIBC_COPT_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE
 #define LIBC_COPT_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE -1
 #endif
 
 #ifdef LLVM_LIBC_MEMCPY_X86_USE_ONLY_REPMOVSB
 #error LLVM_LIBC_MEMCPY_X86_USE_ONLY_REPMOVSB is deprecated use LIBC_COPT_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE=0 instead.
 #endif // LLVM_LIBC_MEMCPY_X86_USE_ONLY_REPMOVSB
 
 #ifdef LLVM_LIBC_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE
 #error LLVM_LIBC_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE is deprecated use LIBC_COPT_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE=0 instead.
 #endif // LLVM_LIBC_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE
 
   static constexpr size_t kRepMovsbThreshold =
       LIBC_COPT_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE;
   if constexpr (kRepMovsbThreshold == 0) {
-    return x86::Memcpy::repmovsb(dst, src, count);
+    return x86::repmovsb(dst, src, count);
   } else if constexpr (kRepMovsbThreshold == size_t(-1)) {
     return inline_memcpy_x86(dst, src, count);
   } else {
     if (LIBC_UNLIKELY(count >= kRepMovsbThreshold))
-      return x86::Memcpy::repmovsb(dst, src, count);
+      return x86::repmovsb(dst, src, count);
     else
       return inline_memcpy_x86(dst, src, count);
   }
 }
 
 } // namespace __llvm_libc
 
 #endif // LIBC_SRC_STRING_MEMORY_UTILS_X86_64_MEMCPY_IMPLEMENTATIONS_H

utils/bazel/llvm-project-overlay/libc/BUILD.bazel

libc_support_library(
     name = "string_memory_utils",
     hdrs = [
         "src/string/memory_utils/op_aarch64.h",
         "src/string/memory_utils/op_builtin.h",
         "src/string/memory_utils/op_generic.h",
         "src/string/memory_utils/op_x86.h",
         "src/string/memory_utils/utils.h",
     ],
+    defines = ["LIBC_COPT_MEMCPY_X86_USE_SOFTWARE_PREFETCHER"],
     textual_hdrs = [
         "src/string/memory_utils/bcmp_implementations.h",
         "src/string/memory_utils/bzero_implementations.h",
         "src/string/memory_utils/memcmp_implementations.h",
         "src/string/memory_utils/memcpy_implementations.h",
         "src/string/memory_utils/aarch64/memcpy_implementations.h",
         "src/string/memory_utils/x86_64/memcpy_implementations.h",
         "src/string/memory_utils/memmove_implementations.h",
         "src/string/memory_utils/memset_implementations.h",
         "src/string/memory_utils/strcmp_implementations.h",
         "src/string/memory_utils/strstr_implementations.h",
     ],
     deps = [
         ":__support_common",
         ":__support_cpp_array",
         ":__support_cpp_bit",
         ":__support_cpp_cstddef",
         ":__support_cpp_type_traits",
         ":__support_macros_attributes",
         ":__support_macros_config",
         ":__support_macros_optimization",
         ":__support_macros_properties_architectures",
+        ":__support_macros_properties_compiler",
         ":__support_macros_properties_cpu_features",
         ":libc_root",
     ],
 )
 
 libc_support_library(
     name = "string_utils",
     hdrs = ["src/string/string_utils.h"],