[libc] Add a reasonably optimized version for bcmp

[gchatelet]

Summary

This is based on current memcmp implementation.

[sivachandra]

No objections from my side.

[sivachandra]

This is broken for aarch64: https://lab.llvm.org/buildbot/#/builders/138/builds/14620.
In the case of aarch64, it looks like _64 is defined only for memset.

[gchatelet]

In D114432#3163380, @sivachandra wrote:

This is broken for aarch64: https://lab.llvm.org/buildbot/#/builders/138/builds/14620.
In the case of aarch64, it looks like _64 is defined only for memset.

Thx for reporting, I'll send a fix ASAP.

[gchatelet]

Should be fixed by rGbdcc5aadf5aa90f36b5a964e2285dc6a3b244ed9

libc/src/string/CMakeLists.txt

 endfunction()
 
 # ------------------------------------------------------------------------------
 # bcmp
 # ------------------------------------------------------------------------------
 
 function(add_bcmp bcmp_name)
   add_implementation(bcmp ${bcmp_name}
-    SRCS ${LIBC_BCMP_SRC}
+    SRCS ${LIBC_SOURCE_DIR}/src/string/bcmp.cpp
     HDRS ${LIBC_SOURCE_DIR}/src/string/bcmp.h
     DEPENDS
       .memory_utils.memory_utils
       libc.include.string
     COMPILE_OPTIONS
       -fno-builtin-memcmp
       -fno-builtin-bcmp
     ${ARGN}
   )
 endfunction()
 
 if(${LIBC_TARGET_ARCHITECTURE_IS_X86})
-  set(LIBC_BCMP_SRC ${LIBC_SOURCE_DIR}/src/string/bcmp.cpp)
   add_bcmp(bcmp_x86_64_opt_sse2   COMPILE_OPTIONS -march=k8             REQUIRE SSE2)
   add_bcmp(bcmp_x86_64_opt_sse4   COMPILE_OPTIONS -march=nehalem        REQUIRE SSE4_2)
   add_bcmp(bcmp_x86_64_opt_avx2   COMPILE_OPTIONS -march=haswell        REQUIRE AVX2)
   add_bcmp(bcmp_x86_64_opt_avx512 COMPILE_OPTIONS -march=skylake-avx512 REQUIRE AVX512F)
   add_bcmp(bcmp_opt_host          COMPILE_OPTIONS ${LIBC_COMPILE_OPTIONS_NATIVE})
   add_bcmp(bcmp)
 else()
-  set(LIBC_BCMP_SRC ${LIBC_SOURCE_DIR}/src/string/bcmp.cpp)
   add_bcmp(bcmp_opt_host          COMPILE_OPTIONS ${LIBC_COMPILE_OPTIONS_NATIVE})
   add_bcmp(bcmp)
 endif()
 
 # ------------------------------------------------------------------------------
 # bzero
 # ------------------------------------------------------------------------------
 

libc/src/string/bcmp.cpp

 //===-- Implementation of bcmp --------------------------------------------===//
 //
 // 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/bcmp.h"
 #include "src/__support/common.h"
+#include "src/string/memory_utils/bcmp_implementations.h"
 
 namespace __llvm_libc {
 
 LLVM_LIBC_FUNCTION(int, bcmp,
                    (const void *lhs, const void *rhs, size_t count)) {
-  const unsigned char *_lhs = reinterpret_cast<const unsigned char *>(lhs);
-  const unsigned char *_rhs = reinterpret_cast<const unsigned char *>(rhs);
-  for (size_t i = 0; i < count; ++i) {
-    if (_lhs[i] != _rhs[i]) {
-      return 1;
-    }
-  }
-  // count is 0 or _lhs and _rhs are the same.
-  return 0;
+  return inline_bcmp(static_cast<const char *>(lhs),
+                     static_cast<const char *>(rhs), count);
 }
 
 } // namespace __llvm_libc

libc/src/string/memory_utils/CMakeLists.txt

 add_header_library(
   memory_utils
   HDRS
     utils.h
     elements.h
+    bcmp_implementations.h
+    memcmp_implementations.h
+    memcpy_implementations.h
+    memset_implementations.h
 )
 
 add_header_library(
   memcpy_implementation
   HDRS
     memcpy_implementations.h
   DEPS
     .memory_utils

libc/src/string/memory_utils/bcmp_implementations.h

+//===-- Implementation of bcmp --------------------------------------------===//
+//
+// 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_BCMP_IMPLEMENTATIONS_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BCMP_IMPLEMENTATIONS_H
+
+#include "src/__support/architectures.h"
+#include "src/__support/common.h"
+#include "src/string/memory_utils/elements.h"
+
+#include <stddef.h> // size_t
+
+namespace __llvm_libc {
+
+// Fixed-size difference between 'lhs' and 'rhs'.
+template <typename Element> bool Differs(const char *lhs, const char *rhs) {
+  return !Element::Equals(lhs, rhs);
+}
+// Runtime-size difference between 'lhs' and 'rhs'.
+template <typename Element>
+bool Differs(const char *lhs, const char *rhs, size_t size) {
+  return !Element::Equals(lhs, rhs, size);
+}
+
+static inline int inline_bcmp(const char *lhs, const char *rhs, size_t count) {
+#if defined(LLVM_LIBC_ARCH_X86)
+  using namespace ::__llvm_libc::x86;
+#elif defined(LLVM_LIBC_ARCH_AARCH64)
+  using namespace ::__llvm_libc::aarch64;
+#else
+  using namespace ::__llvm_libc::scalar;
+#endif
+  if (count == 0)
+    return 0;
+  if (count == 1)
+    return Differs<_1>(lhs, rhs);
+  if (count == 2)
+    return Differs<_2>(lhs, rhs);
+  if (count == 3)
+    return Differs<_3>(lhs, rhs);
+  if (count <= 8)
+    return Differs<HeadTail<_4>>(lhs, rhs, count);
+  if (count <= 16)
+    return Differs<HeadTail<_8>>(lhs, rhs, count);
+  if (count <= 32)
+    return Differs<HeadTail<_16>>(lhs, rhs, count);
+  if (count <= 64)
+    return Differs<HeadTail<_32>>(lhs, rhs, count);
+  if (count <= 128)
+    return Differs<HeadTail<_64>>(lhs, rhs, count);
+  return Differs<Align<_32>::Then<Loop<_32>>>(lhs, rhs, count);
+}
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BCMP_IMPLEMENTATIONS_H

libc/test/src/string/bcmp_test.cpp

TEST(LlvmLibcBcmpTest, LhsRhsAreTheSame) {
   const char *lhs = "ab";
   const char *rhs = "ab";
   EXPECT_EQ(__llvm_libc::bcmp(lhs, rhs, 2), 0);
 }
 
 TEST(LlvmLibcBcmpTest, LhsBeforeRhsLexically) {
   const char *lhs = "ab";
   const char *rhs = "ac";
-  EXPECT_EQ(__llvm_libc::bcmp(lhs, rhs, 2), 1);
+  EXPECT_NE(__llvm_libc::bcmp(lhs, rhs, 2), 0);
 }
 
 TEST(LlvmLibcBcmpTest, LhsAfterRhsLexically) {
   const char *lhs = "ac";
   const char *rhs = "ab";
-  EXPECT_EQ(__llvm_libc::bcmp(lhs, rhs, 2), 1);
+  EXPECT_NE(__llvm_libc::bcmp(lhs, rhs, 2), 0);
 }
 
 TEST(LlvmLibcBcmpTest, Sweep) {
   static constexpr size_t kMaxSize = 1024;
   char lhs[kMaxSize];
   char rhs[kMaxSize];
 
   const auto reset = [](char *const ptr) {
     for (size_t i = 0; i < kMaxSize; ++i)
       ptr[i] = 'a';
   };
 
   reset(lhs);
   reset(rhs);
   for (size_t i = 0; i < kMaxSize; ++i)
     EXPECT_EQ(__llvm_libc::bcmp(lhs, rhs, i), 0);
 
   reset(lhs);
   reset(rhs);
   for (size_t i = 0; i < kMaxSize; ++i) {
     rhs[i] = 'b';
-    EXPECT_EQ(__llvm_libc::bcmp(lhs, rhs, kMaxSize), 1);
+    EXPECT_NE(__llvm_libc::bcmp(lhs, rhs, kMaxSize), 0);
     rhs[i] = 'a';
   }
 }