[InstCombine] Replace malloc+strcpy with malloc+memcpy

[xbolva00]

Summary

len = strlen(s) + 1;
d = malloc(len);
strcpy(d,s); // ---> memcpy(d,s, len);

[xbolva00]

Updated tests

[xbolva00]

Removed duplicated test

[efriedma]

What does the malloc have to do with this transform? The transform here is just strcpy(d, s) -> memcpy(d, s, strlen(s)+1), where strlen(s) is free because we can CSE it with the previous call. I guess in general, you can transform strcpy(malloc(strlen(s)+1), s) to strdup, but that's not what you're doing.

Also, you're making the same mistake *again*: you're not checking whether the string is modified between the strlen and the strcpy.

[xbolva00]

In D47198#1108283, @efriedma wrote:

What does the malloc have to do with this transform? The transform here is just strcpy(d, s) -> memcpy(d, s, strlen(s)+1), where strlen(s) is free because we can CSE it with the previous call. I guess in general, you can transform strcpy(malloc(strlen(s)+1), s) to strdup, but that's not what you're doing.

Also, you're making the same mistake *again*: you're not checking whether the string is modified between the strlen and the strcpy.

Ah yes, sure (why I still think that if value comes from malloc, it cannot modified between, sigh, sorry) :/
Too bad that helper function "isModifiedBetween" cannot be used here.

But with these transformations (malloc-memset, malloc-strcpy), arent we just transforming part of InstCombine to DSE? Are all these transformations legal there, I mean the right place for them?

If yes, I could rework this patch for DSE after some time.

lib/Transforms/Utils/SimplifyLibCalls.cpp

static bool isLocallyOpenedFile(Value *File, CallInst *CI, IRBuilder<> &B,
 
   inferLibFuncAttributes(*CI->getCalledFunction(), *TLI);
   if (PointerMayBeCaptured(File, true, true))
     return false;
 
   return true;
 }
 
+static bool isStrLenOfValue(Value *Len, Value *Src, const TargetLibraryInfo *TLI) {
+  auto *Strlen = dyn_cast<CallInst>(Len);
+  if (!Strlen)
+    return false;
+
+  // Is the inner call really strlen()?
+  Function *InnerCallee = Strlen->getCalledFunction();
+  if (!InnerCallee)
+    return false;
+
+  LibFunc Func;
+  if (!TLI->getLibFunc(*InnerCallee, Func) || !TLI->has(Func) ||
+      Func != LibFunc_strlen)
+    return false;
+
+  return Strlen->getOperand(0) == Src;
+}
+
+static Value *getStringLengthFromMalloc(Value *Dst, Value *Src, CallInst *CI,
+                                        IRBuilder<> &B,
+                                        const TargetLibraryInfo *TLI) {
+  auto *Malloc = dyn_cast<CallInst>(Dst);
+  if (!Malloc)
+    return nullptr;
+
+  // Is the inner call really malloc()?
+  Function *InnerCallee = Malloc->getCalledFunction();
+  if (!InnerCallee)
+    return nullptr;
+
+  LibFunc Func;
+  if (!TLI->getLibFunc(*InnerCallee, Func) || !TLI->has(Func) ||
+      Func != LibFunc_malloc)
+    return nullptr;
+
+  auto *Op = cast<Instruction>(Malloc->getOperand(0));
+  if (isStrLenOfValue(Op, Src, TLI)) {
+    return B.CreateAdd(Op, ConstantInt::get(Op->getType(), 1));
+  }
+
+  auto *BOp = dyn_cast<BinaryOperator>(Op);
+  if (!BOp)
+    return nullptr;
+
+  for (unsigned I = 0; I < 2; ++I) {
+    auto *Op = BOp->getOperand(I);
+    if (isStrLenOfValue(Op, Src, TLI)) {
+      return B.CreateAdd(Op, ConstantInt::get(Op->getType(), 1));
+    }
+  }
+
+  return nullptr;
+}
+
 //===----------------------------------------------------------------------===//
 // String and Memory Library Call Optimizations
 //===----------------------------------------------------------------------===//
 
 Value *LibCallSimplifier::optimizeStrCat(CallInst *CI, IRBuilder<> &B) {
   // Extract some information from the instruction
   Value *Dst = CI->getArgOperand(0);
   Value *Src = CI->getArgOperand(1);

 
 Value *LibCallSimplifier::optimizeStrCpy(CallInst *CI, IRBuilder<> &B) {
   Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
   if (Dst == Src) // strcpy(x,x)  -> x
     return Src;
 
   // See if we can get the length of the input string.
   uint64_t Len = GetStringLength(Src);
-  if (Len == 0)
-    return nullptr;
-
+  if (Len > 0) {
     // We have enough information to now generate the memcpy call to do the
     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
     B.CreateMemCpy(Dst, 1, Src, 1,
                    ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len));
     return Dst;
   }
 
+  // strcpy(malloc(len + 1), str) -> memcpy(malloc(len), str, len + 1)
+  if (Value *Size = getStringLengthFromMalloc(Dst, Src, CI, B, TLI)) {
+    B.CreateMemCpy(Dst, 1, Src, 1, Size);
+    return Dst;
+  }
+
+  return nullptr;
+}
+
 Value *LibCallSimplifier::optimizeStpCpy(CallInst *CI, IRBuilder<> &B) {
   Function *Callee = CI->getCalledFunction();
   Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
   if (Dst == Src) { // stpcpy(x,x)  -> x+strlen(x)
     Value *StrLen = emitStrLen(Src, B, DL, TLI);
     return StrLen ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, StrLen) : nullptr;
   }
 

test/Transforms/InstCombine/malloc-strcpy.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+define i8* @test_ok(i8* nocapture readonly %s) {
+; CHECK-LABEL: @test_ok(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 @strlen(i8* [[S:%.*]])
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[CALL]], 1
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call noalias i8* @malloc(i32 [[ADD]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[CALL]], 1
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[CALL1]], i8* align 1 [[S]], i32 [[TMP1]], i1 false)
+; CHECK-NEXT:    ret i8* [[CALL1]]
+;
+  %call = tail call i32 @strlen(i8* %s) #3
+  %add = add i32 %call, 1
+  %call1 = tail call noalias i8* @malloc(i32 %add) #4
+  %call2 = tail call i8* @strcpy(i8* %call1, i8* %s) #4
+  ret i8* %call1
+}
+
+
+declare noalias i8* @malloc(i32)
+declare i32 @strlen(i8* nocapture)
+declare i8* @strcpy(i8*, i8* nocapture readonly)
+
+
+define i8* @test_ok2(i8* nocapture readonly %s) {
+; CHECK-LABEL: @test_ok2(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 @strlen(i8* [[S:%.*]])
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[CALL]], 1
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call noalias i8* @malloc(i32 [[ADD]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[CALL]], 1
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[CALL1]], i8* align 1 [[S]], i32 [[TMP1]], i1 false)
+; CHECK-NEXT:    ret i8* [[CALL1]]
+;
+  %call = tail call i32 @strlen(i8* %s) #3
+  %add = add i32 %call, 1
+  %call1 = tail call noalias i8* @malloc(i32 %add) #4
+  %call2 = tail call i8* @strcpy(i8* %call1, i8* %s) #4
+  ret i8* %call1
+}
+
+
+define i8* @test_const_ok(i8* nocapture readonly %s, i32 %n) {
+; CHECK-LABEL: @test_const_ok(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 @strlen(i8* [[S:%.*]])
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[CALL]], [[N:%.*]]
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call noalias i8* @malloc(i32 [[ADD]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[CALL]], 1
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[CALL1]], i8* align 1 [[S]], i32 [[TMP1]], i1 false)
+; CHECK-NEXT:    ret i8* [[CALL1]]
+;
+  %call = tail call i32 @strlen(i8* %s) #3
+  %add = add i32 %call, %n
+  %call1 = tail call noalias i8* @malloc(i32 %add) #4
+  %call2 = tail call i8* @strcpy(i8* %call1, i8* %s) #4
+  ret i8* %call1
+}
+
+
+define i8* @test_strlen(i8* nocapture readonly %s, i32 %n) {
+; CHECK-LABEL: @test_strlen(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 @strlen(i8* [[S:%.*]])
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call noalias i8* @malloc(i32 [[CALL]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[CALL]], 1
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[CALL1]], i8* align 1 [[S]], i32 [[TMP1]], i1 false)
+; CHECK-NEXT:    ret i8* [[CALL1]]
+;
+  %call = tail call i32 @strlen(i8* %s) #3
+  %call1 = tail call noalias i8* @malloc(i32 %call) #4
+  %call2 = tail call i8* @strcpy(i8* %call1, i8* %s) #4
+  ret i8* %call1
+}
+
+
+define i8* @test_different_str(i8* nocapture readonly %s, i8* nocapture readonly %p) {
+; CHECK-LABEL: @test_different_str(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 @strlen(i8* [[P:%.*]])
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[CALL]], 1
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call noalias i8* @malloc(i32 [[ADD]])
+; CHECK-NEXT:    [[CALL2:%.*]] = tail call i8* @strcpy(i8* [[CALL1]], i8* [[S:%.*]])
+; CHECK-NEXT:    ret i8* [[CALL1]]
+;
+  %call = tail call i32 @strlen(i8* %p) #3
+  %add = add i32 %call, 1
+  %call1 = tail call noalias i8* @malloc(i32 %add) #4
+  %call2 = tail call i8* @strcpy(i8* %call1, i8* %s) #4
+  ret i8* %call1
+}
+
+
+define i8* @test_no_malloc(i8* returned %s, i8* nocapture readonly %p) {
+; CHECK-LABEL: @test_no_malloc(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @strcpy(i8* [[S:%.*]], i8* [[P:%.*]])
+; CHECK-NEXT:    ret i8* [[S]]
+;
+  %call = tail call i8* @strcpy(i8* %s, i8* %p) #4
+  ret i8* %s
+}