[InstCombine] Optimize some memccpy calls to memcpy/null

[xbolva00]

Summary

return memccpy(d, "helloworld", 'r', 20)

>

return memcpy(d, "helloworld", 8 /* pos of 'r' in string */), d + 8

[xbolva00]

Implemented more patterns.

[xbolva00]

Rebased

[xbolva00]

More tests

Godbolt for verification: https://godbolt.org/z/2rsnFe

[efriedma]

(Comments using argument names from the signature void *memccpy(void *dest, const void *src, int c, size_t n);.)

Please add a testcase where the optimization triggers and "c" is 0. (I think getConstantStringInfo trims the null terminator by default?)

It should be possible to optimize cases where "c" doesn't appear in "src" if "n" is smaller than the length of "src".

test/Transforms/InstCombine/memccpy.ll

57

This is obviously wrong; you've removed the side-effect.

[xbolva00]

Please add a testcase where the optimization triggers and "c" is 0. (I think getConstantStringInfo trims the null terminator by default?)

Ah, right.

test/Transforms/InstCombine/memccpy.ll

57

oops

[xbolva00]

Added new tests + fixed issues.

[xbolva00]

Renamed one test function

[xbolva00]

where "c" doesn't appear in "src" if "n" is smaller than the length of "src".

We dont even need to know n. If c is not in src, we have just memcpy(dst, src, n), no?

[efriedma]

We dont even need to know n. If c is not in src, we have just memcpy(dst, src, n), no?

I think it's possible for there to be valid data after the array returned by getConstantStringInfo, in some cases. For example, if you're doing a memccpy out of something like struct X { char a[10]; char b[10]; }. Maybe worth adding a testcase.

[xbolva00]

Added test

[xbolva00]

I think it's possible for there to be valid data after the array returned by getConstantStringInfo, in some cases.

I added test with string like "blabla\0x" and stop char is 'x'. As test shows, we leave this case as is.

Sorry if I misunderstood you.

[xbolva00]

test/Transforms/InstCombine/memccpy.ll

69

@efriedma ?

Maybe you meant this case?

e.g. n = 20

and we have block of memory "helloworld" "saaaattttt" and stop is char is 's'. In reality we copy 11 chars, but memcpy would copy n = 20 chars.

[xbolva00]

Fix

[xbolva00]

One more test

[xbolva00]

This comment was removed by xbolva00.

[xbolva00]

Use Str.size() instead of GetStringLength

[xbolva00]

Handle case when dst == src

[xbolva00]

Any more comments here?

[xbolva00]

ping

[xbolva00]

Ping

[xbolva00]

ping

[xbolva00]

ping

[jdoerfert]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1126

Unclear why we name Size.

1137

Simplification nits: Move the 1136 check to 1130, then simplify 1131, and swap the cases in 1133.

1138

I do not know so I ask, is SExt the right choice here or ZExt? StopChar could be i8 -1 right? Now the question is, what do we want to find in SrcStr, -1 or 255?

1151

I guess it is always i8Ty but it would make it easier to read if we do not mix i8Ty and CI->getType(). (Just stick with the latter and CI->getType()->getPointerElementType()).

1152

The return value is wrong if std::min(Pos + 1, N->getZExtValue()) is not Pos + 1 because then we should have return null. (I think)

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1126

Will changed.

1137

Ok.

1138

Inspired by optimizeStrChr, that code uses Str.find(CharC->getSExtValue()); so I think it is OK.

1151

Ok.

1152

Yeah.

[jdoerfert]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1138

I dislike this reason, maybe that case was missed there as well. Could we make a test (and execute it) with a string that has i8 -1 as character and we look for that one with memccpy just to be sure?

[jdoerfert]

Btw, the sext vs zext question is my last request, I think this is fine otherwise.

[xbolva00]

Fixed.

[xbolva00]

Up.

[xbolva00]

Removed unneeded variable.

[jdoerfert]

In D68089#1728785, @jdoerfert wrote:

Btw, the sext vs zext question is my last request, I think this is fine otherwise.

Did you add a test or check for this?

[xbolva00]

This comment was removed by xbolva00.

[xbolva00]

Ah, ok, another test is needed.

[xbolva00]

This comment was removed by xbolva00.

[xbolva00]

This comment was removed by xbolva00.

[xbolva00]

Updated with sext or zext testcase.

[jdoerfert]

LGTM.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1142 ↗

(On Diff #230962)

Please add a comment here explaining this.

[xbolva00]

Added a comment.

include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
   Value *optimizeStrSpn(CallInst *CI, IRBuilder<> &B);
   Value *optimizeStrCSpn(CallInst *CI, IRBuilder<> &B);
   Value *optimizeStrStr(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemChr(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemRChr(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemCmp(CallInst *CI, IRBuilder<> &B);
   Value *optimizeBCmp(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemCmpBCmpCommon(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeMemCCpy(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemPCpy(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemCpy(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemMove(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemSet(CallInst *CI, IRBuilder<> &B);
   Value *optimizeRealloc(CallInst *CI, IRBuilder<> &B);
   Value *optimizeWcslen(CallInst *CI, IRBuilder<> &B);
   // Wrapper for all String/Memory Library Call Optimizations
   Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B);

lib/Transforms/Utils/SimplifyLibCalls.cpp

Value *LibCallSimplifier::optimizeMemCpy(CallInst *CI, IRBuilder<> &B) {
 
   // memcpy(x, y, n) -> llvm.memcpy(align 1 x, align 1 y, n)
   CallInst *NewCI =
       B.CreateMemCpy(CI->getArgOperand(0), 1, CI->getArgOperand(1), 1, Size);
   NewCI->setAttributes(CI->getAttributes());
   return CI->getArgOperand(0);
 }
 
+Value *LibCallSimplifier::optimizeMemCCpy(CallInst *CI, IRBuilder<> &B) {
+  Value *Dst = CI->getArgOperand(0);
+  Value *Src = CI->getArgOperand(1);
+  ConstantInt *StopChar = dyn_cast<ConstantInt>(CI->getArgOperand(2));
+  ConstantInt *N = dyn_cast<ConstantInt>(CI->getArgOperand(3));
+  StringRef SrcStr;
+  // memccpy(d, s, c, 0) -> nullptr
+  if (N && N->isNullValue())
+    return Constant::getNullValue(CI->getType());
+  if (!getConstantStringInfo(Src, SrcStr) || !StopChar)
+    return nullptr;
+
+  size_t Pos = SrcStr.find(StopChar->getSExtValue());
+  if (Pos == StringRef::npos)
+    return Constant::getNullValue(CI->getType());
+  if (!N)
+    return nullptr;
+  if (Pos >= N->getZExtValue())
+    return Constant::getNullValue(CI->getType());
+
+  Value *NewN =
+      ConstantInt::get(N->getType(), std::min(Pos + 1, N->getZExtValue()));
+  // memccpy -> llvm.memcpy
+  B.CreateMemCpy(Dst, 1, Src, 1, NewN);
+  return B.CreateInBoundsGEP(B.getInt8Ty(), Dst, NewN);
+}
+
 Value *LibCallSimplifier::optimizeMemPCpy(CallInst *CI, IRBuilder<> &B) {
   Value *Dst = CI->getArgOperand(0);
   Value *N = CI->getArgOperand(2);
   // mempcpy(x, y, n) -> llvm.memcpy(align 1 x, align 1 y, n), x + n
   CallInst *NewCI = B.CreateMemCpy(Dst, 1, CI->getArgOperand(1), 1, N);
   NewCI->setAttributes(CI->getAttributes());
   return B.CreateInBoundsGEP(B.getInt8Ty(), Dst, N);
 }
 
 Value *LibCallSimplifier::optimizeMemMove(CallInst *CI, IRBuilder<> &B) {
   Value *Size = CI->getArgOperand(2);
   annotateNonNullAndDereferenceable(CI, {0, 1}, Size, DL);
   if (isa<IntrinsicInst>(CI))
if (TLI->getLibFunc(*Callee, Func) && TLI->has(Func)) {
     case LibFunc_memrchr:
       return optimizeMemRChr(CI, Builder);
     case LibFunc_bcmp:
       return optimizeBCmp(CI, Builder);
     case LibFunc_memcmp:
       return optimizeMemCmp(CI, Builder);
     case LibFunc_memcpy:
       return optimizeMemCpy(CI, Builder);
+    case LibFunc_memccpy:
+      return optimizeMemCCpy(CI, Builder);
     case LibFunc_mempcpy:
       return optimizeMemPCpy(CI, Builder);
     case LibFunc_memmove:
       return optimizeMemMove(CI, Builder);
     case LibFunc_memset:
       return optimizeMemSet(CI, Builder);
     case LibFunc_realloc:
       return optimizeRealloc(CI, Builder);

test/Transforms/InstCombine/memccpy.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 @hello = private constant [11 x i8] c"helloworld\00", align 1
 
 declare i8* @memccpy(i8*, i8*, i32, i64)
 
 define i8* @memccpy_to_memcpy(i8* %dst) {
 ; CHECK-LABEL: @memccpy_to_memcpy(
-; CHECK-NEXT:    [[CALL:%.*]] = call i8* @memccpy(i8* [[DST:%.*]], i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 114, i64 12)
-; CHECK-NEXT:    ret i8* [[CALL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[DST:%.*]] to i64*
+; CHECK-NEXT:    store i64 8245940763182785896, i64* [[TMP1]], align 1
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i8, i8* [[DST]], i64 8
+; CHECK-NEXT:    ret i8* [[TMP2]]
 ;
   %call = call i8* @memccpy(i8* %dst, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 114, i64 12) ; 114 is 'r'
   ret i8* %call
 }
 
 define i8* @memccpy_to_memcpy2(i8* %dst) {
 ; CHECK-LABEL: @memccpy_to_memcpy2(
-; CHECK-NEXT:    [[CALL:%.*]] = call i8* @memccpy(i8* [[DST:%.*]], i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 114, i64 5)
-; CHECK-NEXT:    ret i8* [[CALL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[DST:%.*]] to i64*
+; CHECK-NEXT:    store i64 8245940763182785896, i64* [[TMP1]], align 1
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i8, i8* [[DST]], i64 8
+; CHECK-NEXT:    ret i8* [[TMP2]]
 ;
-  %call = call i8* @memccpy(i8* %dst, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 114, i64 5)
+  %call = call i8* @memccpy(i8* %dst, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 114, i64 8);
   ret i8* %call
 }
 
 define void @memccpy_to_memcpy3(i8* %dst) {
 ; CHECK-LABEL: @memccpy_to_memcpy3(
-; CHECK-NEXT:    [[CALL:%.*]] = call i8* @memccpy(i8* [[DST:%.*]], i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 114, i64 5)
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(5) [[DST:%.*]], i8* nonnull align 1 dereferenceable(5) getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i64 5, i1 false)
 ; CHECK-NEXT:    ret void
 ;
-  %call = call i8* @memccpy(i8* %dst, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 114, i64 5)
+  %call = call i8* @memccpy(i8* %dst, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 111, i64 10) ; 111 is 'o'
   ret void
 }
 
 define i8* @memccpy_to_null(i8* %dst, i8* %src, i32 %c) {
 ; CHECK-LABEL: @memccpy_to_null(
-; CHECK-NEXT:    [[CALL:%.*]] = call i8* @memccpy(i8* [[DST:%.*]], i8* [[SRC:%.*]], i32 [[C:%.*]], i64 0)
-; CHECK-NEXT:    ret i8* [[CALL]]
+; CHECK-NEXT:    ret i8* null
 ;
   %call = call i8* @memccpy(i8* %dst, i8* %src, i32 %c, i64 0)
   ret i8* %call
 }
 
 define i8* @memccpy_to_null2(i8* %dst) {
 ; CHECK-LABEL: @memccpy_to_null2(
-; CHECK-NEXT:    [[CALL:%.*]] = call i8* @memccpy(i8* [[DST:%.*]], i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 115, i64 5)
-; CHECK-NEXT:    ret i8* [[CALL]]
+; CHECK-NEXT:    ret i8* null
 ;
   %call = call i8* @memccpy(i8* %dst, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 115, i64 5) ; 115 is 's'
   ret i8* %call
 }
 
+define i8* @memccpy_to_null3(i8* %dst, i64 %n) {
+; CHECK-LABEL: @memccpy_to_null3(
+; CHECK-NEXT:    ret i8* null
+;
+  %call = call i8* @memccpy(i8* %dst, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 115, i64 %n) ; 115 is 's'
+  ret i8* %call
+}
+
+define i8* @memccpy_to_null4(i8* %dst) {
+; CHECK-LABEL: @memccpy_to_null4(
+; CHECK-NEXT:    ret i8* null
+;
+  %call = call i8* @memccpy(i8* %dst, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 114, i64 7)
+  ret i8* %call
+}
+
+define i8* @memccpy_to_null5(i8* %dst) {
+; CHECK-LABEL: @memccpy_to_null5(
+; CHECK-NEXT:    ret i8* null
+;
+  %call = call i8* @memccpy(i8* %dst, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @hello, i64 0, i64 0), i32 114, i64 6);
+  ret i8* %call
+}
+
 ; Negative tests
 define i8* @unknown_src(i8* %dst, i8* %src) {
 ; CHECK-LABEL: @unknown_src(
 ; CHECK-NEXT:    [[CALL:%.*]] = call i8* @memccpy(i8* [[DST:%.*]], i8* [[SRC:%.*]], i32 114, i64 12)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = call i8* @memccpy(i8* %dst, i8* %src, i32 114, i64 12)
   ret i8* %call