[SelectionDAG][RFC] Allow the user to specify a memeq function (v4).

[courbet]

Summary

Right now, when we encounter a string equality check,
e.g. if (memcmp(a, b, s) == 0), we try to expand to a comparison if s is a
small compile-time constant, and fall back on calling memcmp() else.

This is sub-optimal because memcmp has to compute much more than
equality.

This patch uses bcmp() on platforms that support it.

This function will be called instead of memcmp() when the result of the memcmp
call is only used for equality comparison.

bcmp can be made much more efficient than memcmp because equality
compare is trivially parallel while lexicographic ordering has a chain
dependency.

include/llvm/IR/RuntimeLibcalls.def

 HANDLE_LIBCALL(O_F128, "__unordtf2")
 HANDLE_LIBCALL(O_PPCF128, "__gcc_qunord")
 
 // Memory
 HANDLE_LIBCALL(MEMCPY, "memcpy")
 HANDLE_LIBCALL(MEMMOVE, "memmove")
 HANDLE_LIBCALL(MEMSET, "memset")
 HANDLE_LIBCALL(BZERO, nullptr)
+HANDLE_LIBCALL(BCMP, nullptr)
 
 // Element-wise unordered-atomic memory of different sizes
 HANDLE_LIBCALL(MEMCPY_ELEMENT_UNORDERED_ATOMIC_1, "__llvm_memcpy_element_unordered_atomic_1")
 HANDLE_LIBCALL(MEMCPY_ELEMENT_UNORDERED_ATOMIC_2, "__llvm_memcpy_element_unordered_atomic_2")
 HANDLE_LIBCALL(MEMCPY_ELEMENT_UNORDERED_ATOMIC_4, "__llvm_memcpy_element_unordered_atomic_4")
 HANDLE_LIBCALL(MEMCPY_ELEMENT_UNORDERED_ATOMIC_8, "__llvm_memcpy_element_unordered_atomic_8")
 HANDLE_LIBCALL(MEMCPY_ELEMENT_UNORDERED_ATOMIC_16, "__llvm_memcpy_element_unordered_atomic_16")
 HANDLE_LIBCALL(MEMMOVE_ELEMENT_UNORDERED_ATOMIC_1, "__llvm_memmove_element_unordered_atomic_1")

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 }
 
 /// See if we can lower a memcmp call into an optimized form. If so, return
 /// true and lower it. Otherwise return false, and it will be lowered like a
 /// normal call.
 /// The caller already checked that \p I calls the appropriate LibFunc with a
 /// correct prototype.
 bool SelectionDAGBuilder::visitMemCmpCall(const CallInst &I) {
+  const auto &TLI = DAG.getTargetLoweringInfo();
+  const auto &DL = DAG.getDataLayout();
   const Value *LHS = I.getArgOperand(0), *RHS = I.getArgOperand(1);
   const Value *Size = I.getArgOperand(2);
   const ConstantInt *CSize = dyn_cast<ConstantInt>(Size);
   if (CSize && CSize->getZExtValue() == 0) {
-    EVT CallVT = DAG.getTargetLoweringInfo().getValueType(DAG.getDataLayout(),
-                                                          I.getType(), true);
+    EVT CallVT = TLI.getValueType(DL, I.getType(), true);
     setValue(&I, DAG.getConstant(0, getCurSDLoc(), CallVT));
     return true;
   }
 
   const SelectionDAGTargetInfo &TSI = DAG.getSelectionDAGInfo();
   std::pair<SDValue, SDValue> Res = TSI.EmitTargetCodeForMemcmp(
       DAG, getCurSDLoc(), DAG.getRoot(), getValue(LHS), getValue(RHS),
       getValue(Size), MachinePointerInfo(LHS), MachinePointerInfo(RHS));
   if (Res.first.getNode()) {
     processIntegerCallValue(I, Res.first, true);
     PendingLoads.push_back(Res.second);
     return true;
   }
 
-  // memcmp(S1,S2,2) != 0 -> (*(short*)LHS != *(short*)RHS)  != 0
-  // memcmp(S1,S2,4) != 0 -> (*(int*)LHS != *(int*)RHS)  != 0
-  if (!CSize || !isOnlyUsedInZeroEqualityComparison(&I))
+  if (!isOnlyUsedInZeroEqualityComparison(&I))
     return false;
 
+  // We're only interested in the boolean comparison value (equal/not equal).
+
+  // If the size is a compile-time constant, we first try to lower to a single
+  // comparison between two loads:
+  //   memcmp(S1,S2,2) != 0 -> (*(short*)LHS != *(short*)RHS)  != 0
+  //   memcmp(S1,S2,4) != 0 -> (*(int*)LHS != *(int*)RHS)  != 0
+  if (CSize) {
     // If the target has a fast compare for the given size, it will return a
     // preferred load type for that size. Require that the load VT is legal and
     // that the target supports unaligned loads of that type. Otherwise, return
     // INVALID.
     auto hasFastLoadsAndCompare = [&](unsigned NumBits) {
       const TargetLowering &TLI = DAG.getTargetLoweringInfo();
       MVT LVT = TLI.hasFastEqualityCompare(NumBits);
       if (LVT != MVT::INVALID_SIMPLE_VALUE_TYPE) {
         // TODO: Handle 5 byte compare as 4-byte + 1 byte.
         // TODO: Handle 8 byte compare on x86-32 as two 32-bit loads.
         // TODO: Check alignment of src and dest ptrs.
         unsigned DstAS = LHS->getType()->getPointerAddressSpace();
         unsigned SrcAS = RHS->getType()->getPointerAddressSpace();
         if (!TLI.isTypeLegal(LVT) ||
             !TLI.allowsMisalignedMemoryAccesses(LVT, SrcAS) ||
             !TLI.allowsMisalignedMemoryAccesses(LVT, DstAS))
           LVT = MVT::INVALID_SIMPLE_VALUE_TYPE;
       }
 
       return LVT;
     };
 
     // This turns into unaligned loads. We only do this if the target natively
     // supports the MVT we'll be loading or if it is small enough (<= 4) that
     // we'll only produce a small number of byte loads.
     MVT LoadVT;
     unsigned NumBitsToCompare = CSize->getZExtValue() * 8;
     switch (NumBitsToCompare) {
     default:
-    return false;
+      LoadVT = MVT::INVALID_SIMPLE_VALUE_TYPE;
+      break;
     case 16:
       LoadVT = MVT::i16;
       break;
     case 32:
       LoadVT = MVT::i32;
       break;
     case 64:
     case 128:
     case 256:
       LoadVT = hasFastLoadsAndCompare(NumBitsToCompare);
       break;
     }
 
-  if (LoadVT == MVT::INVALID_SIMPLE_VALUE_TYPE)
-    return false;
-
+    if (LoadVT != MVT::INVALID_SIMPLE_VALUE_TYPE) {
       SDValue LoadL = getMemCmpLoad(LHS, LoadVT, *this);
       SDValue LoadR = getMemCmpLoad(RHS, LoadVT, *this);
 
       // Bitcast to a wide integer type if the loads are vectors.
       if (LoadVT.isVector()) {
-    EVT CmpVT = EVT::getIntegerVT(LHS->getContext(), LoadVT.getSizeInBits());
+        EVT CmpVT =
+            EVT::getIntegerVT(LHS->getContext(), LoadVT.getSizeInBits());
         LoadL = DAG.getBitcast(CmpVT, LoadL);
         LoadR = DAG.getBitcast(CmpVT, LoadR);
       }
 
-  SDValue Cmp = DAG.getSetCC(getCurSDLoc(), MVT::i1, LoadL, LoadR, ISD::SETNE);
+      SDValue Cmp =
+          DAG.getSetCC(getCurSDLoc(), MVT::i1, LoadL, LoadR, ISD::SETNE);
       processIntegerCallValue(I, Cmp, false);
       return true;
     }
+  }
+
+  // The size is not constant or it's not efficient to use the strategy above.
+  // If the target has a `bcmp()` function, call it.
+  if (const char* const BcmpFuncName = TLI.getLibcallName(RTLIB::BCMP)) {
+    TargetLowering::ArgListTy Args;
+    TargetLowering::ArgListEntry Entry;
+    // signature: bool(const char*, const char*, size_t)
+    Entry.Ty = DL.getIntPtrType(*DAG.getContext());
+    Entry.Node = getValue(LHS);
+    Args.push_back(Entry);
+    Entry.Node = getValue(RHS);
+    Args.push_back(Entry);
+    Entry.Node = getValue(Size);
+    Args.push_back(Entry);
+    TargetLowering::CallLoweringInfo CLI(DAG);
+    CLI.setDebugLoc(getCurSDLoc())
+        .setChain(DAG.getRoot())
+        .setLibCallee(
+            TLI.getLibcallCallingConv(RTLIB::BCMP),
+            Type::getInt1Ty(*DAG.getContext()),
+            DAG.getExternalSymbol(BcmpFuncName, TLI.getPointerTy(DL)),
+            std::move(Args))
+        .setDiscardResult(false);
+
+    std::pair<SDValue, SDValue> CallResult = TLI.LowerCallTo(CLI);
+    processIntegerCallValue(I, CallResult.first, false);
+    PendingLoads.push_back(CallResult.second);
+    return true;
+  }
+
+  // Nothing better, just call memcmp().
+  return false;
+}
 
 /// See if we can lower a memchr call into an optimized form. If so, return
 /// true and lower it. Otherwise return false, and it will be lowered like a
 /// normal call.
 /// The caller already checked that \p I calls the appropriate LibFunc with a
 /// correct prototype.
 bool SelectionDAGBuilder::visitMemChrCall(const CallInst &I) {
   const Value *Src = I.getArgOperand(0);

lib/CodeGen/TargetLoweringBase.cpp

if (TT.isMacOSX())
     return !TT.isMacOSXVersionLT(10, 9) && TT.isArch64Bit();
   // iOS < 7.0 has no sincos_stret.
   if (TT.isiOS())
     return !TT.isOSVersionLT(7, 0);
   // Any other darwin such as WatchOS/TvOS is new enough.
   return true;
 }
 
+static bool targetHasBcmp(const Triple &TT) {
+  // Posix removed support from bcmp() in 2001, but the the glibc and several
+  // implementations of the libc still have it.
+  if (TT.isOSLinux())
+    return TT.isGNUEnvironment() || TT.isMusl();
+  // Both NetBSD and OpenBSD are planning to remove the function. Windows does
+  // not have it.
+  return TT.isOSFreeBSD() || TT.isOSSolaris() || TT.isOSDarwin();
+}
+
 // Although this default value is arbitrary, it is not random. It is assumed
 // that a condition that evaluates the same way by a higher percentage than this
 // is best represented as control flow. Therefore, the default value N should be
 // set such that the win from N% correct executions is greater than the loss
 // from (100 - N)% mispredicted executions for the majority of intended targets.
 static cl::opt<int> MinPercentageForPredictableBranch(
     "min-predictable-branch", cl::init(99),
     cl::desc("Minimum percentage (0-100) that a condition must be either true "
if (TT.isGNUEnvironment() || TT.isOSFuchsia() ||
     setLibcallName(RTLIB::SINCOS_F80, "sincosl");
     setLibcallName(RTLIB::SINCOS_F128, "sincosl");
     setLibcallName(RTLIB::SINCOS_PPCF128, "sincosl");
   }
 
   if (TT.isOSOpenBSD()) {
     setLibcallName(RTLIB::STACKPROTECTOR_CHECK_FAIL, nullptr);
   }
+
+  // Some environements have bcmp(), which can be used for more efficient
+  // equality comparison.
+  if (targetHasBcmp(TT))
+    setLibcallName(RTLIB::BCMP, "bcmp");
 }
 
 /// getFPEXT - Return the FPEXT_*_* value for the given types, or
 /// UNKNOWN_LIBCALL if there is none.
 RTLIB::Libcall RTLIB::getFPEXT(EVT OpVT, EVT RetVT) {
   if (OpVT == MVT::f16) {
     if (RetVT == MVT::f32)
       return FPEXT_F16_F32;

test/CodeGen/X86/memcmp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown-unknown -mattr=cmov   | FileCheck %s --check-prefix=X86 --check-prefix=X86-NOSSE
 ; RUN: llc < %s -mtriple=i686-unknown-unknown -mattr=+sse   | FileCheck %s --check-prefix=X86 --check-prefix=SSE --check-prefix=X86-SSE1
 ; RUN: llc < %s -mtriple=i686-unknown-unknown -mattr=+sse2  | FileCheck %s --check-prefix=X86 --check-prefix=SSE --check-prefix=X86-SSE2
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown             | FileCheck %s --check-prefix=X64 --check-prefix=X64-SSE2
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=avx  | FileCheck %s --check-prefix=X64 --check-prefix=X64-AVX --check-prefix=X64-AVX1
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=avx2 | FileCheck %s --check-prefix=X64 --check-prefix=X64-AVX --check-prefix=X64-AVX2
+; RUN: llc < %s -mtriple=x86_64-linux-gnu -mattr=avx2 | FileCheck %s --check-prefix=X64 --check-prefix=X64-AVX --check-prefix=X64-AVX2 --check-prefix=X64-BCMP
 
 ; This tests codegen time inlining/optimization of memcmp
 ; rdar://6480398
 
 @.str = private constant [65 x i8] c"0123456789012345678901234567890123456789012345678901234567890123\00", align 1
 
 declare i32 @memcmp(i8*, i8*, i64)
 

 ;
 ; X64-LABEL: huge_length:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movabsq $9223372036854775807, %rdx # imm = 0x7FFFFFFFFFFFFFFF
 ; X64-NEXT:    jmp memcmp # TAILCALL
   %m = tail call i32 @memcmp(i8* %X, i8* %Y, i64 9223372036854775807) nounwind
   ret i32 %m
 }
+
+define i1 @huge_length_eq(i8* %X, i8* %Y) nounwind {
+; X86-LABEL: huge_length_eq:
+; X86:       # %bb.0:
+; X86-NEXT:    pushl $2147483647 # imm = 0x7FFFFFFF
+; X86-NEXT:    pushl $-1
+; X86-NEXT:    pushl {{[0-9]+}}(%esp)
+; X86-NEXT:    pushl {{[0-9]+}}(%esp)
+; X86-NEXT:    calll memcmp
+; X86-NEXT:    addl $16, %esp
+; X86-NEXT:    testl %eax, %eax
+; X86-NEXT:    sete %al
+; X86-NEXT:    retl
+;
+; X64-SSE2-LABEL: huge_length_eq:
+; X64-SSE2:       # %bb.0:
+; X64-SSE2-NEXT:    pushq %rax
+; X64-SSE2-NEXT:    movabsq $9223372036854775807, %rdx # imm = 0x7FFFFFFFFFFFFFFF
+; X64-SSE2-NEXT:    callq memcmp
+; X64-SSE2-NEXT:    testl %eax, %eax
+; X64-SSE2-NEXT:    sete %al
+; X64-SSE2-NEXT:    popq %rcx
+; X64-SSE2-NEXT:    retq
+;
+; X64-AVX1-LABEL: huge_length_eq:
+; X64-AVX1:       # %bb.0:
+; X64-AVX1-NEXT:    pushq %rax
+; X64-AVX1-NEXT:    movabsq $9223372036854775807, %rdx # imm = 0x7FFFFFFFFFFFFFFF
+; X64-AVX1-NEXT:    callq memcmp
+; X64-AVX1-NEXT:    testl %eax, %eax
+; X64-AVX1-NEXT:    sete %al
+; X64-AVX1-NEXT:    popq %rcx
+; X64-AVX1-NEXT:    retq
+;
+; X64-BCMP-LABEL: huge_length_eq:
+; X64-BCMP:       # %bb.0:
+; X64-BCMP-NEXT:    pushq %rax
+; X64-BCMP-NEXT:    movabsq $9223372036854775807, %rdx # imm = 0x7FFFFFFFFFFFFFFF
+; X64-BCMP-NEXT:    callq bcmp
+; X64-BCMP-NEXT:    notb %al
+; X64-BCMP-NEXT:    andb $1, %al
+; X64-BCMP-NEXT:    popq %rcx
+; X64-BCMP-NEXT:    retq
+
+  %m = tail call i32 @memcmp(i8* %X, i8* %Y, i64 9223372036854775807) nounwind
+  %c = icmp eq i32 %m, 0
+  ret i1 %c
+}
+
+; This checks non-constant sizes.
+define i32 @nonconst_length(i8* %X, i8* %Y, i64 %size) nounwind {
+; X86-LABEL: nonconst_length:
+; X86:       # %bb.0:
+; X86-NEXT:    jmp memcmp # TAILCALL
+;
+; X64-LABEL: nonconst_length:
+; X64:       # %bb.0:
+; X64-NEXT:    jmp memcmp # TAILCALL
+  %m = tail call i32 @memcmp(i8* %X, i8* %Y, i64 %size) nounwind
+  ret i32 %m
+}
+
+define i1 @nonconst_length_eq(i8* %X, i8* %Y, i64 %size) nounwind {
+; X86-LABEL: nonconst_length_eq:
+; X86:       # %bb.0:
+; X86-NEXT:    pushl {{[0-9]+}}(%esp)
+; X86-NEXT:    pushl {{[0-9]+}}(%esp)
+; X86-NEXT:    pushl {{[0-9]+}}(%esp)
+; X86-NEXT:    pushl {{[0-9]+}}(%esp)
+; X86-NEXT:    calll memcmp
+; X86-NEXT:    addl $16, %esp
+; X86-NEXT:    testl %eax, %eax
+; X86-NEXT:    sete %al
+; X86-NEXT:    retl
+;
+; X64-SSE2-LABEL: nonconst_length_eq:
+; X64-SSE2:       # %bb.0:
+; X64-SSE2-NEXT:    pushq %rax
+; X64-SSE2-NEXT:    callq memcmp
+; X64-SSE2-NEXT:    testl %eax, %eax
+; X64-SSE2-NEXT:    sete %al
+; X64-SSE2-NEXT:    popq %rcx
+; X64-SSE2-NEXT:    retq
+;
+; X64-AVX1-LABEL: nonconst_length_eq:
+; X64-AVX1:       # %bb.0:
+; X64-AVX1-NEXT:    pushq %rax
+; X64-AVX1-NEXT:    callq memcmp
+; X64-AVX1-NEXT:    testl %eax, %eax
+; X64-AVX1-NEXT:    sete %al
+; X64-AVX1-NEXT:    popq %rcx
+; X64-AVX1-NEXT:    retq
+;
+; X64-BCMP-LABEL: nonconst_length_eq:
+; X64-BCMP:       # %bb.0:
+; X64-BCMP-NEXT:    pushq %rax
+; X64-BCMP-NEXT:    callq bcmp
+; X64-BCMP-NEXT:    notb %al
+; X64-BCMP-NEXT:    andb $1, %al
+; X64-BCMP-NEXT:    popq %rcx
+; X64-BCMP-NEXT:    retq
+  %m = tail call i32 @memcmp(i8* %X, i8* %Y, i64 %size) nounwind
+  %c = icmp eq i32 %m, 0
+  ret i1 %c
+}