[MemCpyOpt] Fixing Incorrect Code Motion while Handling Aggregate Type Values

[myhsu]

Summary

When MemCpyOpt is handling aggregate type values, if an instruction (let's call it P) between the targeting load (L) and store (S) clobbers the source pointer of L, it will try to hoist S before P. This process will also hoist S's data dependency instructions.

However, the current implementation has a bug that if one of S's dependency instructions is also a user of P, MemCpyOpt will not prevent it from being hoisted above P and cause a use-before-define error. For example, in the newly added test file (i.e. aggregate-type-crash.ll), it will try to hoist both store %my_struct %1, %my_struct* %3 and its dependent, %3 = bitcast i8* %2 to %my_struct*, above %2 = call i8* @my_malloc(%my_struct* %0). Creating the following BB:

entry:
  %1 = bitcast i8* %4 to %my_struct*
  %2 = bitcast %my_struct* %1 to i8*
  %3 = bitcast %my_struct* %0 to i8*
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 %2, i8* align 4 %3, i64 8, i1 false)
  %4 = call i8* @my_malloc(%my_struct* %0)
  ret void

Where there is a use-before-define error between %1 and %4.

Update: The compiler for the Pony Programming Language also encounter the same bug

[myhsu]

Ping on this review.
Also, the compiler for the Pony Programming Language bumped into the same bug. Since MemCpyOpt will run by default in O3, it would be a little bit hard for a downstream user to avoid this bug without changing the LLVM source tree.

[eugenis]

LGTM
Looks great.

[lenary]

@myhsu do you need me to land this for you? I presume you don't yet have commit privileges.

[myhsu]

In D66060#1715719, @lenary wrote:

@myhsu do you need me to land this for you? I presume you don't yet have commit privileges.

That would be great. Thank you very much

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

if (MayAlias) {
         MemLocs.push_back(ML);
       } else
         // We don't know how to lift this instruction.
         return false;
     }
 
     ToLift.push_back(C);
     for (unsigned k = 0, e = C->getNumOperands(); k != e; ++k)
-      if (auto *A = dyn_cast<Instruction>(C->getOperand(k)))
-        if (A->getParent() == SI->getParent())
+      if (auto *A = dyn_cast<Instruction>(C->getOperand(k))) {
+        if (A->getParent() == SI->getParent()) {
+          // Cannot hoist user of P above P
+          if(A == P) return false;
           Args.insert(A);
         }
+      }
+  }
 
   // We made it, we need to lift
   for (auto *I : llvm::reverse(ToLift)) {
     LLVM_DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n");
     I->moveBefore(P);
   }
 
   return true;

llvm/test/Transforms/MemCpyOpt/aggregate-type-crash.ll

+; RUN: opt -memcpyopt -S -o - < %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.14.0"
+
+%my_struct = type { i8, i32 }
+
+; Function Attrs: inaccessiblemem_or_argmemonly
+declare noalias i8* @my_malloc(%my_struct*) #0
+
+define void @my_func(%my_struct* %0) {
+entry:
+; CHECK: entry:
+  %1 = load %my_struct, %my_struct* %0
+  %2 = call i8* @my_malloc(%my_struct* %0)
+  %3 = bitcast i8* %2 to %my_struct*
+  store %my_struct %1, %my_struct* %3
+; CHECK-NOT: call void @llvm.memcpy.{{.*}}.{{.*}}.{{.*}}
+  ret void
+}
+
+attributes #0 = { inaccessiblemem_or_argmemonly }
+
+!llvm.module.flags = !{!0, !1, !2}
+!llvm.ident = !{!3}
+
+!0 = !{i32 2, !"SDK Version", [2 x i32] [i32 10, i32 14]}
+!1 = !{i32 1, !"wchar_size", i32 4}
+!2 = !{i32 7, !"PIC Level", i32 2}
+!3 = !{!"Apple LLVM version 10.0.1 (clang-1001.0.46.4)"}