Revert "Temporarily Revert "Add basic loop fusion pass.""

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

10 files changed, 618 insertions, 0 deletions

diff --git a/llvm/test/Transforms/InstMerge/exceptions.ll b/llvm/test/Transforms/InstMerge/exceptions.ll
new file mode 100644
index 00000000000..54c39960f01
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/exceptions.ll
@@ -0,0 +1,61 @@
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes='require<memdep>',mldst-motion \
+; RUN:   -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@r = common global i32 0, align 4
+@s = common global i32 0, align 4
+
+; CHECK-LABEL: define void @test1(
+define void @test1(i1 %cmp, i32* noalias %p) {
+entry:
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  call void @may_exit() nounwind
+  %arrayidx = getelementptr inbounds i32, i32* %p, i64 1
+  %0 = load i32, i32* %arrayidx, align 4
+  store i32 %0, i32* @r, align 4
+  br label %if.end
+; CHECK:       call void @may_exit()
+; CHECK-NEXT:  %[[gep:.*]] = getelementptr inbounds i32, i32* %p, i64 1
+; CHECK-NEXT:  %[[load:.*]] = load i32, i32* %[[gep]], align 4
+; CHECK-NEXT:  store i32 %[[load]], i32* @r, align 4
+
+if.else:                                          ; preds = %entry
+  %arrayidx1 = getelementptr inbounds i32, i32* %p, i64 1
+  %1 = load i32, i32* %arrayidx1, align 4
+  store i32 %1, i32* @s, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+; CHECK-LABEL: define void @test2(
+define void @test2(i1 %cmp, i32* noalias %p) {
+entry:
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %arrayidx = getelementptr inbounds i32, i32* %p, i64 1
+  store i32 1, i32* %arrayidx, align 4
+  call void @may_throw()
+; CHECK:       %[[gep:.*]] = getelementptr inbounds i32, i32* %p, i64 1
+; CHECK-NEXT:  store i32 1, i32* %[[gep]], align 4
+; CHECK-NEXT:  call void @may_throw()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %arrayidx1 = getelementptr inbounds i32, i32* %p, i64 1
+  store i32 2, i32* %arrayidx1, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+declare void @may_throw()
+declare void @may_exit() nounwind
diff --git a/llvm/test/Transforms/InstMerge/st_sink_barrier_call.ll b/llvm/test/Transforms/InstMerge/st_sink_barrier_call.ll
new file mode 100644
index 00000000000..cdcc34624d5
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/st_sink_barrier_call.ll
@@ -0,0 +1,43 @@
+; Test to make sure that a function call that needs to be a barrier to sinking stores is indeed a barrier.
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+declare i32 @foo(i32 %x)
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node, %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node*, %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32, i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32, i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: store i32
+  store i32 %1, i32* %p1, align 4
+  br label %if.end
+  
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32, i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: store i32
+  store i32 %add, i32* %p3, align 4
+  call i32 @foo(i32 5)				  ;barrier
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK-NOT: store
+  ret void
+}
diff --git a/llvm/test/Transforms/InstMerge/st_sink_bugfix_22613.ll b/llvm/test/Transforms/InstMerge/st_sink_bugfix_22613.ll
new file mode 100644
index 00000000000..48882eca44c
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/st_sink_bugfix_22613.ll
@@ -0,0 +1,106 @@
+; ModuleID = 'bug.c'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; RUN: opt -O2 -S < %s | FileCheck %s
+
+; CHECK-LABEL: main
+; CHECK: if.end
+; CHECK: store
+; CHECK: memset
+; CHECK: if.then
+; CHECK: store
+; CHECK: memset
+
+@d = common global i32 0, align 4
+@b = common global i32 0, align 4
+@f = common global [1 x [3 x i8]] zeroinitializer, align 1
+@e = common global i32 0, align 4
+@c = common global i32 0, align 4
+@a = common global i32 0, align 4
+
+; Function Attrs: nounwind uwtable
+define void @fn1() {
+entry:
+  store i32 0, i32* @d, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc8, %entry
+  %0 = load i32, i32* @d, align 4
+  %cmp = icmp slt i32 %0, 2
+  br i1 %cmp, label %for.body, label %for.end10
+
+for.body:                                         ; preds = %for.cond
+  %1 = load i32, i32* @d, align 4
+  %idxprom = sext i32 %1 to i64
+  %2 = load i32, i32* @b, align 4
+  %idxprom1 = sext i32 %2 to i64
+  %arrayidx = getelementptr inbounds [1 x [3 x i8]], [1 x [3 x i8]]* @f, i32 0, i64 %idxprom1
+  %arrayidx2 = getelementptr inbounds [3 x i8], [3 x i8]* %arrayidx, i32 0, i64 %idxprom
+  store i8 0, i8* %arrayidx2, align 1
+  store i32 0, i32* @e, align 4
+  br label %for.cond3
+
+for.cond3:                                        ; preds = %for.inc, %for.body
+  %3 = load i32, i32* @e, align 4
+  %cmp4 = icmp slt i32 %3, 3
+  br i1 %cmp4, label %for.body5, label %for.end
+
+for.body5:                                        ; preds = %for.cond3
+  %4 = load i32, i32* @c, align 4
+  %tobool = icmp ne i32 %4, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body5
+  %5 = load i32, i32* @a, align 4
+  %dec = add nsw i32 %5, -1
+  store i32 %dec, i32* @a, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body5
+  %6 = load i32, i32* @e, align 4
+  %idxprom6 = sext i32 %6 to i64
+  %arrayidx7 = getelementptr inbounds [3 x i8], [3 x i8]* getelementptr inbounds ([1 x [3 x i8]], [1 x [3 x i8]]* @f, i32 0, i64 0), i32 0, i64 %idxprom6
+  store i8 1, i8* %arrayidx7, align 1
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %7 = load i32, i32* @e, align 4
+  %inc = add nsw i32 %7, 1
+  store i32 %inc, i32* @e, align 4
+  br label %for.cond3
+
+for.end:                                          ; preds = %for.cond3
+  br label %for.inc8
+
+for.inc8:                                         ; preds = %for.end
+  %8 = load i32, i32* @d, align 4
+  %inc9 = add nsw i32 %8, 1
+  store i32 %inc9, i32* @d, align 4
+  br label %for.cond
+
+for.end10:                                        ; preds = %for.cond
+  ret void
+}
+
+; Function Attrs: nounwind uwtable
+define i32 @main() {
+entry:
+  %retval = alloca i32, align 4
+  store i32 0, i32* %retval
+  call void @fn1()
+  %0 = load i8, i8* getelementptr inbounds ([1 x [3 x i8]], [1 x [3 x i8]]* @f, i32 0, i64 0, i64 1), align 1
+  %conv = sext i8 %0 to i32
+  %cmp = icmp ne i32 %conv, 1
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  call void @abort()
+  unreachable
+
+if.end:                                           ; preds = %entry
+  ret i32 0
+}
+
+; Function Attrs: noreturn nounwind
+declare void @abort()
diff --git a/llvm/test/Transforms/InstMerge/st_sink_check_debug.ll b/llvm/test/Transforms/InstMerge/st_sink_check_debug.ll
new file mode 100644
index 00000000000..3c078919325
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/st_sink_check_debug.ll
@@ -0,0 +1,33 @@
+; RUN: opt < %s -S -debugify -mldst-motion -o - | FileCheck %s
+
+%struct.S = type { i32 }
+
+define dso_local void @foo(%struct.S* %this, i32 %bar) {
+entry:
+  %this.addr = alloca %struct.S*, align 8
+  %bar.addr = alloca i32, align 4
+  store %struct.S* %this, %struct.S** %this.addr, align 8
+  store i32 %bar, i32* %bar.addr, align 4
+  %this1 = load %struct.S*, %struct.S** %this.addr, align 8
+  %0 = load i32, i32* %bar.addr, align 4
+  %tobool = icmp ne i32 %0, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %foo = getelementptr inbounds %struct.S, %struct.S* %this1, i32 0, i32 0
+  store i32 1, i32* %foo, align 4
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %foo2 = getelementptr inbounds %struct.S, %struct.S* %this1, i32 0, i32 0
+  store i32 0, i32* %foo2, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+; CHECK:      @foo
+; CHECK:      if.end: ; preds = %if.else, %if.then
+; CHECK-NEXT:   %.sink = phi {{.*}} !dbg ![[DBG:[0-9]+]]
+; CHECK: ![[DBG]] = !DILocation(line: 0,
diff --git a/llvm/test/Transforms/InstMerge/st_sink_debuginvariant.ll b/llvm/test/Transforms/InstMerge/st_sink_debuginvariant.ll
new file mode 100644
index 00000000000..4a2d8040726
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/st_sink_debuginvariant.ll
@@ -0,0 +1,156 @@
+; RUN: opt < %s -S -mldst-motion -o - | FileCheck %s
+; RUN: opt < %s -S -strip-debug -mldst-motion -o - | FileCheck %s
+
+; Verify that the amount of stores that are sunk is invariant regarding debug
+; info.  This used to fail due to including dbg.value instructions when
+; calculating the size of a basic block for the "MagicCompileTimeControl"
+; check in MergedLoadStoreMotion::mergeStores.
+
+; CHECK-LABEL: return:
+; CHECK-NEXT:    %.sink = phi i16 [ 5, %if.end ], [ 6, %if.then ]
+; CHECK-NEXT:    %0 = getelementptr inbounds %struct.S0, %struct.S0* %agg.result, i16 0, i32 0
+; CHECK-NEXT:    store i16 %.sink, i16* %0
+; CHECK-NEXT:    %1 = getelementptr inbounds %struct.S0, %struct.S0* %agg.result, i16 0, i32 1
+; CHECK-NEXT:    store i16 0, i16* %1
+; CHECK-NEXT:    ret void
+
+%struct.S0 = type { i16, i16 }
+
+@g_173 = dso_local local_unnamed_addr global i16 0, !dbg !0
+
+; Function Attrs: noinline norecurse nounwind
+define dso_local void @func_34(%struct.S0* noalias sret %agg.result) local_unnamed_addr #0 !dbg !11 {
+entry:
+  br i1 undef, label %if.end, label %if.then, !dbg !18
+
+if.then:                                          ; preds = %entry
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata i16 5, metadata !19, metadata !DIExpression()), !dbg !22
+  %l_303.sroa.0.0..sroa_idx = getelementptr inbounds %struct.S0, %struct.S0* %agg.result, i16 0, i32 0, !dbg !23
+  store i16 6, i16* %l_303.sroa.0.0..sroa_idx, !dbg !23
+  %l_303.sroa.2.0..sroa_idx1 = getelementptr inbounds %struct.S0, %struct.S0* %agg.result, i16 0, i32 1, !dbg !23
+  store i16 0, i16* %l_303.sroa.2.0..sroa_idx1, !dbg !23
+  br label %return, !dbg !24
+
+if.end:                                           ; preds = %entry
+  %f037 = getelementptr inbounds %struct.S0, %struct.S0* %agg.result, i16 0, i32 0, !dbg !25
+  store i16 5, i16* %f037, !dbg !25
+  %f138 = getelementptr inbounds %struct.S0, %struct.S0* %agg.result, i16 0, i32 1, !dbg !25
+  store i16 0, i16* %f138, !dbg !25
+  store i16 0, i16* @g_173, !dbg !27
+  br label %return, !dbg !28
+
+return:                                           ; preds = %if.end, %if.then
+  ret void, !dbg !29
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+attributes #0 = { noinline norecurse nounwind }
+attributes #1 = { nounwind readnone speculatable }
+
+!llvm.dbg.cu = !{!2}
+!llvm.module.flags = !{!7, !8, !9}
+!llvm.ident = !{!10}
+
+!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+!1 = distinct !DIGlobalVariable(name: "g_173", scope: !2, file: !3, line: 7, type: !6, isLocal: false, isDefinition: true)
+!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 7.0.0 (x)", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5)
+!3 = !DIFile(filename: "csmith11794002068761.c", directory: "")
+!4 = !{}
+!5 = !{!0}
+!6 = !DIBasicType(name: "int", size: 16, encoding: DW_ATE_signed)
+!7 = !{i32 2, !"Dwarf Version", i32 4}
+!8 = !{i32 2, !"Debug Info Version", i32 3}
+!9 = !{i32 1, !"wchar_size", i32 1}
+!10 = !{!"clang version 7.0.0 (x)"}
+!11 = distinct !DISubprogram(name: "func_34", scope: !3, file: !3, line: 16, type: !12, isLocal: false, isDefinition: true, scopeLine: 16, isOptimized: false, unit: !2, retainedNodes: !4)
+!12 = !DISubroutineType(types: !13)
+!13 = !{!14}
+!14 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "S0", file: !3, line: 2, size: 32, elements: !15)
+!15 = !{!16, !17}
+!16 = !DIDerivedType(tag: DW_TAG_member, name: "f0", scope: !14, file: !3, line: 3, baseType: !6, size: 16)
+!17 = !DIDerivedType(tag: DW_TAG_member, name: "f1", scope: !14, file: !3, line: 4, baseType: !6, size: 16, offset: 16)
+!18 = !DILocation(line: 18, column: 7, scope: !11)
+!19 = !DILocalVariable(name: "left", scope: !20, file: !3, line: 23, type: !6)
+!20 = distinct !DILexicalBlock(scope: !21, file: !3, line: 18, column: 14)
+!21 = distinct !DILexicalBlock(scope: !11, file: !3, line: 18, column: 7)
+!22 = !DILocation(line: 23, column: 9, scope: !20)
+!23 = !DILocation(line: 26, column: 12, scope: !20)
+!24 = !DILocation(line: 26, column: 5, scope: !20)
+!25 = !DILocation(line: 29, column: 23, scope: !26)
+!26 = distinct !DILexicalBlock(scope: !11, file: !3, line: 28, column: 3)
+!27 = !DILocation(line: 30, column: 11, scope: !26)
+!28 = !DILocation(line: 31, column: 5, scope: !26)
+!29 = !DILocation(line: 33, column: 1, scope: !11)
diff --git a/llvm/test/Transforms/InstMerge/st_sink_no_barrier_call.ll b/llvm/test/Transforms/InstMerge/st_sink_no_barrier_call.ll
new file mode 100644
index 00000000000..c2da0f3d0ec
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/st_sink_no_barrier_call.ll
@@ -0,0 +1,45 @@
+; Test to make sure that stores in a diamond get merged with a non barrier function call after the store instruction
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+declare i32 @foo(i32 %x) #0
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node, %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node*, %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32, i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32, i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p1, align 4
+  br label %if.end
+  
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32, i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %add, i32* %p3, align 4
+  call i32 @foo(i32 5) nounwind				  ;not a barrier
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK: store
+  ret void
+}
+
+attributes #0 = { readnone } 
diff --git a/llvm/test/Transforms/InstMerge/st_sink_no_barrier_load.ll b/llvm/test/Transforms/InstMerge/st_sink_no_barrier_load.ll
new file mode 100644
index 00000000000..b7236e4c6a0
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/st_sink_no_barrier_load.ll
@@ -0,0 +1,43 @@
+; Test to make sure that stores in a diamond get merged with a non barrier load after the store instruction
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node, %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node*, %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32, i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32, i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p1, align 4
+  %p2 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 5, i32 6
+  ; CHECK: load i32, i32*
+  %not_barrier = load i32 , i32 * %p2, align 4
+  br label %if.end
+
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32, i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %add, i32* %p3, align 4
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK: store
+  ret void
+}
diff --git a/llvm/test/Transforms/InstMerge/st_sink_no_barrier_store.ll b/llvm/test/Transforms/InstMerge/st_sink_no_barrier_store.ll
new file mode 100644
index 00000000000..e13f28aa5e1
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/st_sink_no_barrier_store.ll
@@ -0,0 +1,42 @@
+; Test to make sure that stores in a diamond get merged with a non barrier store after the store instruction to be sunk
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node, %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node*, %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32, i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32, i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p1, align 4
+  br label %if.end
+
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32, i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p2 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  store i32 %add, i32* %p2, align 4
+  %p3 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 5, i32 6
+  ; CHECK: store i32
+  store i32 %add, i32* %p3, align 4  			  ; This is not a barrier
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK: store
+  ret void
+}
diff --git a/llvm/test/Transforms/InstMerge/st_sink_two_stores.ll b/llvm/test/Transforms/InstMerge/st_sink_two_stores.ll
new file mode 100644
index 00000000000..5b5582f438c
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/st_sink_two_stores.ll
@@ -0,0 +1,47 @@
+; Test to make sure that stores in a diamond get merged
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node, %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node*, %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32, i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32, i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p1, align 4
+  %p2 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 4, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p2, align 4
+  br label %if.end
+
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32, i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %add, i32* %p3, align 4
+  %p4 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 4, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %2, i32* %p4, align 4  
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK: store
+; CHECK: store
+  ret void
+}
diff --git a/llvm/test/Transforms/InstMerge/st_sink_with_barrier.ll b/llvm/test/Transforms/InstMerge/st_sink_with_barrier.ll
new file mode 100644
index 00000000000..a05ae88e384
--- /dev/null
+++ b/llvm/test/Transforms/InstMerge/st_sink_with_barrier.ll
@@ -0,0 +1,42 @@
+; Test to make sure that load from the same address as a store and appears after the store prevents the store from being sunk
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node, %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node*, %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32, i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32, i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: store i32
+  store i32 %1, i32* %p1, align 4
+  %p2 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: load i32, i32*
+  %barrier = load i32 , i32 * %p2, align 4
+  br label %if.end
+
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32, i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node, %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: store i32
+  store i32 %add, i32* %p3, align 4
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK-NOT: store
+  ret void
+}