[libc] Add memmove benchmarks

[gchatelet]

Summary

This patch enables the benchmarking of memmove.
Ideally, this should be submitted before D114637.

[gchatelet]

• rebase

libc/benchmarks/CMakeLists.txt

if(can_run)
         string(TOUPPER ${name} name_upper)
         target_compile_definitions(${benchmark_name} PRIVATE "-DLIBC_BENCHMARK_FUNCTION_${name_upper}=__llvm_libc::${name}" "-DLIBC_BENCHMARK_FUNCTION_NAME=\"${fq_config_name}\"")
     else()
       message(STATUS "Skipping benchmark for '${fq_config_name}' insufficient host cpu features '${required_cpu_features}'")
     endif()
   endforeach()
 endfunction()
 
-add_libc_multi_impl_benchmark(memcpy)
-add_libc_multi_impl_benchmark(memset)
+add_libc_multi_impl_benchmark(bcmp)
 add_libc_multi_impl_benchmark(bzero)
 add_libc_multi_impl_benchmark(memcmp)
-add_libc_multi_impl_benchmark(bcmp)
+add_libc_multi_impl_benchmark(memcpy)
+add_libc_multi_impl_benchmark(memmove)
+add_libc_multi_impl_benchmark(memset)
 
 #==============================================================================
 # Google Benchmarking tool
 #==============================================================================
 
 # This target uses the Google Benchmark facility to report throughput for llvm
 # libc memory functions compiled for the host machine. This is useful to
 # continuously monitor the performance of the memory functions.
 add_executable(libc.benchmarks.memory_functions.opt_host
   EXCLUDE_FROM_ALL
   LibcMemoryGoogleBenchmarkMain.cpp
   LibcDefaultImplementations.cpp
 )
 
 target_link_libraries(libc.benchmarks.memory_functions.opt_host
   PRIVATE
   libc-memory-benchmark
   libc.src.string.memcmp_opt_host
   libc.src.string.bcmp_opt_host
   libc.src.string.memcpy_opt_host
   libc.src.string.memset_opt_host
   libc.src.string.bzero_opt_host
+  libc.src.string.memmove_opt_host
   benchmark_main
 )
 
 add_subdirectory(automemcpy)

libc/benchmarks/LibcDefaultImplementations.cpp

 #include "LibcFunctionPrototypes.h"
 #include "llvm/ADT/ArrayRef.h"
 #include <cstddef>
 
 namespace __llvm_libc {
 
 extern void *memcpy(void *__restrict, const void *__restrict, size_t);
+extern void *memmove(void *, const void *, size_t);
 extern void *memset(void *, int, size_t);
 extern void bzero(void *, size_t);
 extern int memcmp(const void *, const void *, size_t);
 extern int bcmp(const void *, const void *, size_t);
 
 } // namespace __llvm_libc
 
 // List of implementations to test.
 
 using llvm::libc_benchmarks::BzeroConfiguration;
 using llvm::libc_benchmarks::MemcmpOrBcmpConfiguration;
 using llvm::libc_benchmarks::MemcpyConfiguration;
+using llvm::libc_benchmarks::MemmoveConfiguration;
 using llvm::libc_benchmarks::MemsetConfiguration;
 
 llvm::ArrayRef<MemcpyConfiguration> getMemcpyConfigurations() {
   static constexpr MemcpyConfiguration kMemcpyConfigurations[] = {
       {__llvm_libc::memcpy, "__llvm_libc::memcpy"}};
   return llvm::makeArrayRef(kMemcpyConfigurations);
 }
+llvm::ArrayRef<MemmoveConfiguration> getMemmoveConfigurations() {
+  static constexpr MemmoveConfiguration kMemmoveConfigurations[] = {
+      {__llvm_libc::memmove, "__llvm_libc::memmove"}};
+  return llvm::makeArrayRef(kMemmoveConfigurations);
+}
 llvm::ArrayRef<MemcmpOrBcmpConfiguration> getMemcmpConfigurations() {
   static constexpr MemcmpOrBcmpConfiguration kMemcmpConfiguration[] = {
       {__llvm_libc::memcmp, "__llvm_libc::memcmp"}};
   return llvm::makeArrayRef(kMemcmpConfiguration);
 }
 llvm::ArrayRef<MemcmpOrBcmpConfiguration> getBcmpConfigurations() {
   static constexpr MemcmpOrBcmpConfiguration kBcmpConfigurations[] = {
       {__llvm_libc::bcmp, "__llvm_libc::bcmp"}};

libc/benchmarks/LibcFunctionPrototypes.h

 #ifndef LLVM_LIBC_BENCHMARKS_LIBC_FUNCTION_PROTOTYPES_H
 #define LLVM_LIBC_BENCHMARKS_LIBC_FUNCTION_PROTOTYPES_H
 
 #include "llvm/ADT/StringRef.h"
 
 namespace llvm {
 namespace libc_benchmarks {
 
 /// Memory function prototype and configuration.
 using MemcpyFunction = void *(*)(void *__restrict, const void *__restrict,
                                  size_t);
 struct MemcpyConfiguration {
   MemcpyFunction Function;
   llvm::StringRef Name;
 };
 
+using MemmoveFunction = void *(*)(void *, const void *, size_t);
+struct MemmoveConfiguration {
+  MemmoveFunction Function;
+  llvm::StringRef Name;
+};
+
 using MemsetFunction = void *(*)(void *, int, size_t);
 struct MemsetConfiguration {
   MemsetFunction Function;
   llvm::StringRef Name;
 };
 
 using BzeroFunction = void (*)(void *, size_t);
 struct BzeroConfiguration {

libc/benchmarks/LibcMemoryBenchmark.h

return Memcpy(DstBuffer + Parameter.OffsetBytes,
                   SrcBuffer + Parameter.OffsetBytes, Parameter.SizeBytes);
   }
 
 private:
   AlignedBuffer SrcBuffer;
   AlignedBuffer DstBuffer;
 };
 
+/// Provides source and destination buffers for the Move operation as well as
+/// the associated size distributions.
+struct MoveSetup : public ParameterBatch {
+  MoveSetup();
+
+  inline static const ArrayRef<MemorySizeDistribution> getDistributions() {
+    return getMemmoveSizeDistributions();
+  }
+
+  inline void *Call(ParameterType Parameter, MemmoveFunction Memmove) {
+    return Memmove(Buffer + ParameterBatch::BufferSize / 3,
+                   Buffer + Parameter.OffsetBytes, Parameter.SizeBytes);
+  }
+
+private:
+  AlignedBuffer Buffer;
+};
+
 /// Provides destination buffer for the Set operation as well as the associated
 /// size distributions.
 struct SetSetup : public ParameterBatch {
   SetSetup();
 
   inline static const ArrayRef<MemorySizeDistribution> getDistributions() {
     return getMemsetSizeDistributions();
   }

libc/benchmarks/LibcMemoryBenchmark.cpp

report_fatal_error(
             .concat(", BufferSize=")
             .concat(llvm::Twine(BufferSize)));
 }
 
 CopySetup::CopySetup()
     : ParameterBatch(2), SrcBuffer(ParameterBatch::BufferSize),
       DstBuffer(ParameterBatch::BufferSize) {}
 
+MoveSetup::MoveSetup()
+    : ParameterBatch(3), Buffer(ParameterBatch::BufferSize * 3) {}
+
 ComparisonSetup::ComparisonSetup()
     : ParameterBatch(2), LhsBuffer(ParameterBatch::BufferSize),
       RhsBuffer(ParameterBatch::BufferSize) {
   // The memcmp buffers always compare equal.
   memset(LhsBuffer.begin(), 0xF, BufferSize);
   memset(RhsBuffer.begin(), 0xF, BufferSize);
 }
 
 SetSetup::SetSetup()
     : ParameterBatch(1), DstBuffer(ParameterBatch::BufferSize) {}
 
 } // namespace libc_benchmarks
 } // namespace llvm

libc/benchmarks/LibcMemoryBenchmarkMain.cpp

 #include "llvm/Support/raw_ostream.h"
 
 #include <cstring>
 #include <unistd.h>
 
 namespace __llvm_libc {
 
 extern void *memcpy(void *__restrict, const void *__restrict, size_t);
+extern void *memmove(void *, const void *, size_t);
 extern void *memset(void *, int, size_t);
 extern void bzero(void *, size_t);
 extern int memcmp(const void *, const void *, size_t);
 extern int bcmp(const void *, const void *, size_t);
 
 } // namespace __llvm_libc
 
 namespace llvm {

 
 static cl::opt<uint32_t>
     NumTrials("num-trials", cl::desc("The number of benchmarks run to perform"),
               cl::init(1));
 
 #if defined(LIBC_BENCHMARK_FUNCTION_MEMCPY)
 #define LIBC_BENCHMARK_FUNCTION LIBC_BENCHMARK_FUNCTION_MEMCPY
 using BenchmarkSetup = CopySetup;
+#elif defined(LIBC_BENCHMARK_FUNCTION_MEMMOVE)
+#define LIBC_BENCHMARK_FUNCTION LIBC_BENCHMARK_FUNCTION_MEMMOVE
+using BenchmarkSetup = MoveSetup;
 #elif defined(LIBC_BENCHMARK_FUNCTION_MEMSET)
 #define LIBC_BENCHMARK_FUNCTION LIBC_BENCHMARK_FUNCTION_MEMSET
 using BenchmarkSetup = SetSetup;
 #elif defined(LIBC_BENCHMARK_FUNCTION_BZERO)
 #define LIBC_BENCHMARK_FUNCTION LIBC_BENCHMARK_FUNCTION_BZERO
 using BenchmarkSetup = SetSetup;
 #elif defined(LIBC_BENCHMARK_FUNCTION_MEMCMP)
 #define LIBC_BENCHMARK_FUNCTION LIBC_BENCHMARK_FUNCTION_MEMCMP

libc/benchmarks/LibcMemoryGoogleBenchmarkMain.cpp

 using llvm::Align;
 using llvm::ArrayRef;
 using llvm::Twine;
 using llvm::libc_benchmarks::BzeroConfiguration;
 using llvm::libc_benchmarks::ComparisonSetup;
 using llvm::libc_benchmarks::CopySetup;
 using llvm::libc_benchmarks::MemcmpOrBcmpConfiguration;
 using llvm::libc_benchmarks::MemcpyConfiguration;
+using llvm::libc_benchmarks::MemmoveConfiguration;
 using llvm::libc_benchmarks::MemorySizeDistribution;
 using llvm::libc_benchmarks::MemsetConfiguration;
+using llvm::libc_benchmarks::MoveSetup;
 using llvm::libc_benchmarks::OffsetDistribution;
 using llvm::libc_benchmarks::SetSetup;
 
 // Alignment to use for when accessing the buffers.
 static constexpr Align kBenchmarkAlignment = Align::Constant<1>();
 
 static std::mt19937_64 &getGenerator() {
   static std::mt19937_64 Generator(
for (int64_t DistIndex = 0; DistIndex < DistributionSize; ++DistIndex)     \
       for (int64_t ConfIndex = 0; ConfIndex < ConfigurationSize; ++ConfIndex)  \
         benchmark->Args({DistIndex, ConfIndex});                               \
   })
 
 extern llvm::ArrayRef<MemcpyConfiguration> getMemcpyConfigurations();
 BENCHMARK_MEMORY_FUNCTION(BM_Memcpy, CopySetup, MemcpyConfiguration,
                           getMemcpyConfigurations());
 
+extern llvm::ArrayRef<MemmoveConfiguration> getMemmoveConfigurations();
+BENCHMARK_MEMORY_FUNCTION(BM_Memmove, MoveSetup, MemmoveConfiguration,
+                          getMemmoveConfigurations());
+
 extern llvm::ArrayRef<MemcmpOrBcmpConfiguration> getMemcmpConfigurations();
 BENCHMARK_MEMORY_FUNCTION(BM_Memcmp, ComparisonSetup, MemcmpOrBcmpConfiguration,
                           getMemcmpConfigurations());
 
 extern llvm::ArrayRef<MemcmpOrBcmpConfiguration> getBcmpConfigurations();
 BENCHMARK_MEMORY_FUNCTION(BM_Bcmp, ComparisonSetup, MemcmpOrBcmpConfiguration,
                           getBcmpConfigurations());
 
 extern llvm::ArrayRef<MemsetConfiguration> getMemsetConfigurations();
 BENCHMARK_MEMORY_FUNCTION(BM_Memset, SetSetup, MemsetConfiguration,
                           getMemsetConfigurations());
 
 extern llvm::ArrayRef<BzeroConfiguration> getBzeroConfigurations();
 BENCHMARK_MEMORY_FUNCTION(BM_Bzero, SetSetup, BzeroConfiguration,
                           getBzeroConfigurations());

libc/benchmarks/automemcpy/lib/CodeGen.cpp

static void Serialize(raw_ostream &Stream,
   Stream << "\n";
   Stream << "#include \"LibcFunctionPrototypes.h\"\n";
   Stream << "#include \"automemcpy/FunctionDescriptor.h\"\n";
   Stream << "#include \"src/string/memory_utils/elements.h\"\n";
   Stream << "\n";
   Stream << "using llvm::libc_benchmarks::BzeroConfiguration;\n";
   Stream << "using llvm::libc_benchmarks::MemcmpOrBcmpConfiguration;\n";
   Stream << "using llvm::libc_benchmarks::MemcpyConfiguration;\n";
+  Stream << "using llvm::libc_benchmarks::MemmoveConfiguration;\n";
   Stream << "using llvm::libc_benchmarks::MemsetConfiguration;\n";
   Stream << "\n";
   Stream << "namespace __llvm_libc {\n";
   Stream << "\n";
   codegen::functions::Serialize(Stream, Descriptors);
   Stream << "\n";
   Stream << "} // namespace __llvm_libc\n";
   Stream << "\n";
)";
   codegen::configurations::Serialize(Stream, FunctionType::MEMSET, Descriptors);
   Stream << R"(
 using BzeroStub = void (*)(char *, size_t);
 template <BzeroStub Foo> void Wrap(void *dst, size_t size) {
   Foo(reinterpret_cast<char *>(dst), size);
 }
 )";
   codegen::configurations::Serialize(Stream, FunctionType::BZERO, Descriptors);
+  Stream << R"(
+llvm::ArrayRef<MemmoveConfiguration> getMemmoveConfigurations() {
+  return {};
+}
+)";
   Stream << "// Functions : " << Descriptors.size() << "\n";
 }
 
 } // namespace codegen
 
 // Stores `VolatileStr` into a cache and returns a StringRef of the cached
 // version.
 StringRef getInternalizedString(std::string VolatileStr) {

libc/src/string/CMakeLists.txt

SRCS
     memchr.cpp
   HDRS
     memchr.h
   DEPENDS
     .string_utils
 )
 
 add_entrypoint_object(
-  memmove
-  SRCS
-    memmove.cpp
-  HDRS
-    memmove.h
-  DEPENDS
-    libc.src.__support.integer_operations
-    .memory_utils.memcpy_implementation
-)
-
-add_entrypoint_object(
   memrchr
   SRCS
     memrchr.cpp
   HDRS
     memrchr.h
 )
 
 add_entrypoint_object(
add_memcpy(memcpy_opt_host          COMPILE_OPTIONS ${LIBC_COMPILE_OPTIONS_NATIVE}
                                       COMPILE_OPTIONS "SHELL:-mllvm --tail-merge-threshold=0")
   add_memcpy(memcpy                   COMPILE_OPTIONS "SHELL:-mllvm --tail-merge-threshold=0")
 else()
   add_memcpy(memcpy_opt_host          COMPILE_OPTIONS ${LIBC_COMPILE_OPTIONS_NATIVE})
   add_memcpy(memcpy)
 endif()
 
 # ------------------------------------------------------------------------------
+# memmove
+# ------------------------------------------------------------------------------
+
+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})
+  add_memmove(memmove_x86_64_opt_sse2   COMPILE_OPTIONS -march=k8             REQUIRE SSE2)
+  add_memmove(memmove_x86_64_opt_sse4   COMPILE_OPTIONS -march=nehalem        REQUIRE SSE4_2)
+  add_memmove(memmove_x86_64_opt_avx2   COMPILE_OPTIONS -march=haswell        REQUIRE AVX2)
+  add_memmove(memmove_x86_64_opt_avx512 COMPILE_OPTIONS -march=skylake-avx512 REQUIRE AVX512F)
+  add_memmove(memmove_opt_host          COMPILE_OPTIONS ${LIBC_COMPILE_OPTIONS_NATIVE})
+  add_memmove(memmove)
+elseif(${LIBC_TARGET_ARCHITECTURE_IS_AARCH64})
+  # Disable tail merging as it leads to lower performance.
+  # Note that '-mllvm' needs to be prefixed with 'SHELL:' to prevent CMake flag deduplication.
+  add_memmove(memmove_opt_host          COMPILE_OPTIONS ${LIBC_COMPILE_OPTIONS_NATIVE}
+                                        COMPILE_OPTIONS "SHELL:-mllvm --tail-merge-threshold=0")
+  add_memmove(memmove                   COMPILE_OPTIONS "SHELL:-mllvm --tail-merge-threshold=0")
+else()
+  add_memmove(memmove_opt_host          COMPILE_OPTIONS ${LIBC_COMPILE_OPTIONS_NATIVE})
+  add_memmove(memmove)
+endif()
+
+# ------------------------------------------------------------------------------
 # memset
 # ------------------------------------------------------------------------------
 
 function(add_memset memset_name)
   add_implementation(memset ${memset_name}
     SRCS ${LIBC_SOURCE_DIR}/src/string/memset.cpp
     HDRS ${LIBC_SOURCE_DIR}/src/string/memset.h
     DEPENDS