Optimize memcmp(x,y,n)==0 for small n and suitably aligned x/y.

[Eelis]

Summary

This fixes http://llvm.org/bugs/show_bug.cgi?id=20673

[joerg]

For platforms with suppport for unaligned access, this is always a win, isn't it? I.e. independent of the correct alignment of the pointers.

[Eelis]

Thanks Joerg, that's a great point!

I don't really know how to do that though. I see that the memcmp code in SelectionDAGBuilder.cpp uses allowsMisalignedMemoryAccesses(), but that function takes an EVT, a type which is not known in Transforms/Utils/SimplifyLibCalls.cpp.

[majnemer]

lib/Transforms/Utils/SimplifyLibCalls.cpp

955

Isn't the RHS just isPowerOf2_64?

Also, '8' sounds awfully target specific. I doubt this is the correct number for the MSP430 target.

956–958

This seems strangely formatted, consider running clang-format over these lines.

960

There is no need to manually strength-reduce multiplication by eight. Also, this can never fail.

962–965

Perhaps:

Type *LHSPtrTy =
    IntType->getPointerTo(LHS->getType()->getPointerAddressSpace());
Type *RHSPtrTy =
    IntType->getPointerTo(RHS->getType()->getPointerAddressSpace());

[Eelis]

Thanks David! I'll attach an updated patch, but I don't know how to get rid of the "8" constant.

lib/Transforms/Utils/SimplifyLibCalls.cpp

955

Oh, I just took this from InstCombiner::SimplifyMemTransfer, which does:

if (Size > 8 || (Size&(Size-1)))
  return nullptr;  // If not 1/2/4/8 bytes, exit.

I'll use isPowerOf2_64 instead, but I'm not sure what I should I use instead of 8.

956–958

I like the &&s aligned on the left so I easily see it's a repeated conjunction, but I see that clang-format wants them on the right, so I'll do that.

960

Oh, I just took the "Len << 3" from InstCombiner::SimplifyMemTransfer. Will fix. :)

962–965

This too I just took from InstCombiner::SimplifyMemTransfer. I will use what you suggest instead.

[Eelis]

Addressed all review comments except the "Len <= 8" check, because I don't know what should be used instead.

[Eelis]

Oh crap, left out the tests this time. Reuploading.

[Eelis]

Now once more with tests. :)

[mcrosier]

test/Transforms/InstCombine/memcmp-1.ll

77

; CHECK-LABEL:

94

; CHECK-LABEL:

111

; CHECK-LABEL:

[Eelis]

Thanks mcrosier, will fix!

(I'm curious: how come this wasn't caught when I ran the tests? Are these names case-insensitive?)

[Eelis]

CHECK-label -> CHECK-LABEL

[mcrosier]

In D6952#108619, @Eelis wrote:

(I'm curious: how come this wasn't caught when I ran the tests? Are these names case-insensitive?)

The tests will pass with or without the CHECK-LABEL directives. I believe the FileCheck directives are case-sensitive, but I would have to look at the FileCheck implementation to verify. Regardless, CHECK-LABEL is the preferred style.

Chad

[majnemer]

LGTM

[mcrosier]

Eelis,
Do you have commit rights? If not, I'd be happy to commit the patch on your behalf.

Chad

[Eelis]

I don't think this code should be committed yet, because it does not yet check whether the integer types are available. I tried doing it with:

if (DL && DL->isLegalInteger(Len * 8) && ...

.. but that doesn't work (and the tests fail) because DL is nullptr.

[Eelis]

Ah, it wasn't that DL was null, but rather that there were no native integer types specified in the target datalayout for the test. I've added those, and I've also refined the alignment check to take the integer type's preferred alignment into account.

I think it's okay to commit now. Chad: I don't have commit rights, so yes please! Thanks :)

[Eelis]

Ping :)

[mcrosier]

@majnemer: David, would you mind giving this a once over before I commit? This has been sitting for many months..

[majnemer]

LGTM

[mcrosier]

Committed r246313.

lib/Transforms/Utils/SimplifyLibCalls.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Transforms/Utils/BuildLibCalls.h"
+#include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 using namespace PatternMatch;

     return B.CreateSub(LHSV, RHSV, "chardiff");
   }
 
+  // memcmp(S1,S2,N/8)==0 -> (*(intN_t*)S1 != *(intN_t*)S2)==0
+  if (DL && DL->isLegalInteger(Len * 8) &&
+      isOnlyUsedInZeroEqualityComparison(CI)) {
+
+    IntegerType *IntType = IntegerType::get(CI->getContext(), Len * 8);
+    unsigned PrefAlignment = DL->getPrefTypeAlignment(IntType);
+
+    if (getKnownAlignment(LHS, DL, nullptr, CI) >= PrefAlignment &&
+        getKnownAlignment(RHS, DL, nullptr, CI) >= PrefAlignment) {
+
+      Type *LHSPtrTy =
+          IntType->getPointerTo(LHS->getType()->getPointerAddressSpace());
+      Type *RHSPtrTy =
+          IntType->getPointerTo(RHS->getType()->getPointerAddressSpace());
+
+      Value *LHSV = B.CreateLoad(B.CreateBitCast(LHS, LHSPtrTy, "lhsc"), "lhsv");
+      Value *RHSV = B.CreateLoad(B.CreateBitCast(RHS, RHSPtrTy, "rhsc"), "rhsv");
+
+      return B.CreateZExt(B.CreateICmpNE(LHSV, RHSV), CI->getType(), "memcmp");
+    }
+  }
+
   // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
   StringRef LHSStr, RHSStr;
   if (getConstantStringInfo(LHS, LHSStr) &&

test/Transforms/InstCombine/memcmp-1.ll

 ;
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
-target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32:64"
 
 @foo = constant [4 x i8] c"foo\00"
 @hel = constant [4 x i8] c"hel\00"

   ret i32 %ret
 ; CHECK: ret i32 -1
 }
+
+; Check memcmp(mem1, mem2, 8)==0 -> *(int64_t*)mem1 == *(int64_t*)mem2
+
+define i1 @test_simplify7(i64 %x, i64 %y) {
+; CHECK-LABEL: @test_simplify7(
+  %x.addr = alloca i64, align 8
+  %y.addr = alloca i64, align 8
+  store i64 %x, i64* %x.addr, align 8
+  store i64 %y, i64* %y.addr, align 8
+  %xptr = bitcast i64* %x.addr to i8*
+  %yptr = bitcast i64* %y.addr to i8*
+  %call = call i32 @memcmp(i8* %xptr, i8* %yptr, i32 8)
+  %cmp = icmp eq i32 %call, 0
+  ret i1 %cmp
+; CHECK: %cmp = icmp eq i64 %x, %y
+; CHECK: ret i1 %cmp
+}
+
+; Check memcmp(mem1, mem2, 4)==0 -> *(int32_t*)mem1 == *(int32_t*)mem2
+
+define i1 @test_simplify8(i32 %x, i32 %y) {
+; CHECK-LABEL: @test_simplify8(
+  %x.addr = alloca i32, align 4
+  %y.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  store i32 %y, i32* %y.addr, align 4
+  %xptr = bitcast i32* %x.addr to i8*
+  %yptr = bitcast i32* %y.addr to i8*
+  %call = call i32 @memcmp(i8* %xptr, i8* %yptr, i32 4)
+  %cmp = icmp eq i32 %call, 0
+  ret i1 %cmp
+; CHECK: %cmp = icmp eq i32 %x, %y
+; CHECK: ret i1 %cmp
+}
+
+; Check memcmp(mem1, mem2, 2)==0 -> *(int16_t*)mem1 == *(int16_t*)mem2
+
+define i1 @test_simplify9(i16 %x, i16 %y) {
+; CHECK-LABEL: @test_simplify9(
+  %x.addr = alloca i16, align 2
+  %y.addr = alloca i16, align 2
+  store i16 %x, i16* %x.addr, align 2
+  store i16 %y, i16* %y.addr, align 2
+  %xptr = bitcast i16* %x.addr to i8*
+  %yptr = bitcast i16* %y.addr to i8*
+  %call = call i32 @memcmp(i8* %xptr, i8* %yptr, i32 2)
+  %cmp = icmp eq i32 %call, 0
+  ret i1 %cmp
+; CHECK: %cmp = icmp eq i16 %x, %y
+; CHECK: ret i1 %cmp
+}