[SimplifyLibcalls] Memcpy + strlen propagation

[xbolva00]

Summary

Patch optimizes the following case:

unsigned memcpy_strlen (char *d) {

memcpy (d, "aaaa", 5);
// ...  
return strlen(d); //  optimize to 4

}

if between memcpy and strlen calls "d" is modified, transformation is not performed.

[• dberlin]

GVN should already be able to get this, and if it can't, improve it's intrinsic handling (Either in VNCoercion's memory transfer intrinsic handling, or ...).

That's gonna do a lot better than trying to special case it in libcall simplification.
It also looks like you made it O(number of instructions) worst case per call?

[xbolva00]

In D45599#1066574, @dberlin wrote:

GVN should already be able to get this, and if it can't, improve it's intrinsic handling (Either in VNCoercion's memory transfer intrinsic handling, or ...).

That's gonna do a lot better than trying to special case it in libcall simplification.
It also looks like you made it O(number of instructions) worst case per call?

Ok, so I will close this change. If you know GVN, check this case..

lib/Transforms/Utils/SimplifyLibCalls.cpp

Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilder<> &B,
   // strlen(x) == 0 --> *x == 0
   if (isOnlyUsedInZeroEqualityComparison(CI))
     return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
 
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilder<> &B) {
-  return optimizeStringLength(CI, B, 8);
+  if (Value *V = optimizeStringLength(CI, B, 8))
+    return V;
+
+  Value *Dst = CI->getOperand(0);
+  Instruction *PrevInst = CI->getPrevNode();
+
+  while (PrevInst) {
+    if (auto *Call = dyn_cast<IntrinsicInst>(PrevInst)) {
+      Function *InnerCallee = Call->getCalledFunction();
+      if (!InnerCallee)
+        return nullptr;
+
+      // check if memcpy
+      if (Call->getIntrinsicID() != Intrinsic::memcpy)
+        return nullptr;
+
+      if (Dst != Call->getOperand(0))
+        return nullptr;
+
+      StringRef Str;
+      if (!getConstantStringInfo(Call->getArgOperand(1), Str))
+        return nullptr;
+
+      // strlen is memcpy N argument
+      if (ConstantInt *CInt = dyn_cast<ConstantInt>(Call->getOperand(2)))
+        if (CInt->getZExtValue() == Str.size() + 1)
+          return ConstantInt::get(CI->getType(), Str.size());
+
+      return nullptr;
+    } else {
+      if (isa<CallInst>(PrevInst))
+        return nullptr;
+
+      for (unsigned i = 0; i < PrevInst->getNumOperands(); ++i) {
+        if (Dst == PrevInst->getOperand(i)) {
+          return nullptr;
+        }
+      }
+    }
+
+    PrevInst = PrevInst->getPrevNode();
+  }
+
+  return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeWcslen(CallInst *CI, IRBuilder<> &B) {
   Module &M = *CI->getParent()->getParent()->getParent();
   unsigned WCharSize = TLI->getWCharSize(M) * 8;
   // We cannot perform this optimization without wchar_size metadata.
   if (WCharSize == 0)
     return nullptr;

test/Transforms/InstCombine/memcpy-strlen.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+@.str = private unnamed_addr constant [5 x i8] c"aaaa\00", align 1
+
+declare void @llvm.memcpy.p0i8.p0i8.i32(i8* nocapture writeonly, i8* nocapture readonly, i32, i1) #2
+declare i32 @strlen(i8*) #1
+
+
+define i32 @memcpy_strlen_not_const_str(i8* %p, i8* %d) #0 {
+; CHECK-LABEL: @memcpy_strlen_not_const_str(
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[D:%.*]], i8* align 1 [[P:%.*]], i32 5, i1 false)
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @strlen(i8* [[D]])
+; CHECK-NEXT:    ret i32 [[CALL]]
+;
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 %d, i8* align 1 %p, i32 5, i1 false)
+  %call = call i32 @strlen(i8* %d) #3
+  ret i32 %call
+}
+
+define i32 @memcpy_strlen_n_larger_than_str_len(i8* %d) #0 {
+; CHECK-LABEL: @memcpy_strlen_n_larger_than_str_len(
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[D:%.*]] to i64*
+; CHECK-NEXT:    store i64 1633771873, i64* [[TMP1]], align 1
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @strlen(i8* [[D]])
+; CHECK-NEXT:    ret i32 [[CALL]]
+;
+  %1 = bitcast i8* %d to i64*
+  store i64 1633771873, i64* %1, align 1
+  %call = call i32 @strlen(i8* %d) #3
+  ret i32 %call
+}
+
+define i32 @memcpy_strlen_n_smaller_than_str_len(i8* %d) #0 {
+; CHECK-LABEL: @memcpy_strlen_n_smaller_than_str_len(
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[D:%.*]] to i16*
+; CHECK-NEXT:    store i16 24929, i16* [[TMP1]], align 1
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @strlen(i8* [[D]])
+; CHECK-NEXT:    ret i32 [[CALL]]
+;
+  %1 = bitcast i8* %d to i16*
+  store i16 24929, i16* %1, align 1
+  %call = call i32 @strlen(i8* %d) #3
+  ret i32 %call
+}
+
+define i32 @memcpy_strlen_const_n(i8* %d) #0 {
+; CHECK-LABEL: @memcpy_strlen_const_n(
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[D:%.*]], i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i32 5, i1 false)
+; CHECK-NEXT:    ret i32 4
+;
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 %d, i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i32 5, i1 false)
+  %call = call i32 @strlen(i8* %d) #3
+  ret i32 %call
+}
+
+define i32 @memcpy_strlen_non_const_n(i8* %d, i32 %n) #0 {
+; CHECK-LABEL: @memcpy_strlen_non_const_n(
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[D:%.*]], i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i32 [[N:%.*]], i1 false)
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @strlen(i8* [[D]])
+; CHECK-NEXT:    ret i32 [[CALL]]
+;
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 %d, i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i32 %n, i1 false)
+  %call = call i32 @strlen(i8* %d) #3
+  ret i32 %call
+}
+
+define i32 @memcpy_strlen_str_modify(i8* %d, i32 %p) #0 {
+; CHECK-LABEL: @memcpy_strlen_str_modify(
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[D:%.*]], i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i32 5, i1 false)
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[P:%.*]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i8, i8* [[D]], i64 [[TMP1]]
+; CHECK-NEXT:    store i8 0, i8* [[ARRAYIDX]], align 1
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @strlen(i8* [[D]])
+; CHECK-NEXT:    ret i32 [[CALL]]
+;
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 %d, i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i32 5, i1 false)
+  %arrayidx = getelementptr inbounds i8, i8* %d, i32 %p
+  store i8 0, i8* %arrayidx, align 1
+  %call = call i32 @strlen(i8* %d) #3
+  ret i32 %call
+}
+
+define i32 @memcpy_strlen_str_modify_alt(i8* %d, i32 %p) #0 {
+; CHECK-LABEL: @memcpy_strlen_str_modify_alt(
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[D:%.*]], i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i32 5, i1 false)
+; CHECK-NEXT:    store i8 0, i8* [[D]], align 1
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @strlen(i8* [[D]])
+; CHECK-NEXT:    ret i32 [[CALL]]
+;
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 %d, i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i32 5, i1 false)
+  store i8 0, i8* %d, align 1
+  %call = call i32 @strlen(i8* %d) #3
+  ret i32 %call
+}
+
+define i32 @memcpy_strlen_str_modify_alt2(i8* %d, i32 %p) #0 {
+; CHECK-LABEL: @memcpy_strlen_str_modify_alt2(
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[D:%.*]], i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i32 5, i1 false)
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i8, i8* [[D]], i64 10
+; CHECK-NEXT:    store i8 0, i8* [[ARRAYIDX]], align 1
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @strlen(i8* [[D]])
+; CHECK-NEXT:    ret i32 [[CALL]]
+;
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 %d, i8* align 1 getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i32 5, i1 false)
+  %arrayidx = getelementptr inbounds i8, i8* %d, i32 10
+  store i8 0, i8* %arrayidx, align 1
+  %call = call i32 @strlen(i8* %d) #3
+  ret i32 %call
+}