6 files changed, 268 insertions, 0 deletions
diff --git a/llvm/test/Transforms/LoopLoadElim/backward.ll b/llvm/test/Transforms/LoopLoadElim/backward.ll
new file mode 100644
index 00000000000..7c750a51a2a
--- /dev/null
+++ b/llvm/test/Transforms/LoopLoadElim/backward.ll
@@ -0,0 +1,32 @@
+; RUN: opt -loop-load-elim -S < %s | FileCheck %s
+
+; Simple st->ld forwarding derived from a lexical backward dep.
+;
+;   for (unsigned i = 0; i < 100; i++)
+;     A[i+1] = A[i] + B[i];
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* noalias nocapture %A, i32* noalias nocapture readonly %B, i64 %N) {
+entry:
+; CHECK: %load_initial = load i32, i32* %A
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+; CHECK: %store_forwarded = phi i32 [ %load_initial, %entry ], [ %add, %for.body ]
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %load = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %load_1 = load i32, i32* %arrayidx2, align 4
+; CHECK: %add = add i32 %load_1, %store_forwarded
+  %add = add i32 %load_1, %load
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %arrayidx_next = getelementptr inbounds i32, i32* %A, i64 %indvars.iv.next
+  store i32 %add, i32* %arrayidx_next, align 4
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
diff --git a/llvm/test/Transforms/LoopLoadElim/def-store-before-load.ll b/llvm/test/Transforms/LoopLoadElim/def-store-before-load.ll
new file mode 100644
index 00000000000..3dc93f6786e
--- /dev/null
+++ b/llvm/test/Transforms/LoopLoadElim/def-store-before-load.ll
@@ -0,0 +1,35 @@
+; RUN: opt -loop-load-elim -S < %s | FileCheck %s
+
+;  No loop-carried forwarding: The intervening store to A[i] kills the stored
+;  value from the previous iteration.
+;
+;   for (unsigned i = 0; i < 100; i++) {
+;     A[i] = 1;
+;     A[i+1] = A[i] + B[i];
+;   }
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* noalias nocapture %A, i32* noalias nocapture readonly %B, i64 %N) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+; CHECK-NOT: %store_forwarded
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 1, i32* %arrayidx, align 4
+  %a = load i32, i32* %arrayidx, align 4
+  %arrayidxB = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %b = load i32, i32* %arrayidxB, align 4
+; CHECK: %add = add i32 %b, %a
+  %add = add i32 %b, %a
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %arrayidx_next = getelementptr inbounds i32, i32* %A, i64 %indvars.iv.next
+  store i32 %add, i32* %arrayidx_next, align 4
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
diff --git a/llvm/test/Transforms/LoopLoadElim/forward.ll b/llvm/test/Transforms/LoopLoadElim/forward.ll
new file mode 100644
index 00000000000..1a77297a064
--- /dev/null
+++ b/llvm/test/Transforms/LoopLoadElim/forward.ll
@@ -0,0 +1,47 @@
+; RUN: opt -loop-load-elim -S < %s | FileCheck %s
+
+; Simple st->ld forwarding derived from a lexical forwrad dep.
+;
+;   for (unsigned i = 0; i < 100; i++) {
+;     A[i+1] = B[i] + 2;
+;     C[i] = A[i] * 2;
+;   }
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %B, i32* %C, i64 %N) {
+
+; CHECK:   for.body.lver.memcheck:
+; CHECK:     %found.conflict{{.*}} =
+; CHECK-NOT: %found.conflict{{.*}} =
+
+entry:
+; for.body.ph:
+; CHECK: %load_initial = load i32, i32* %A
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+; CHECK: %store_forwarded = phi i32 [ %load_initial, %for.body.ph ], [ %a_p1, %for.body ]
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+
+  %Aidx_next = getelementptr inbounds i32, i32* %A, i64 %indvars.iv.next
+  %Bidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %Cidx = getelementptr inbounds i32, i32* %C, i64 %indvars.iv
+  %Aidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+
+  %b = load i32, i32* %Bidx, align 4
+  %a_p1 = add i32 %b, 2
+  store i32 %a_p1, i32* %Aidx_next, align 4
+
+  %a = load i32, i32* %Aidx, align 4
+; CHECK: %c = mul i32 %store_forwarded, 2
+  %c = mul i32 %a, 2
+  store i32 %c, i32* %Cidx, align 4
+
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
diff --git a/llvm/test/Transforms/LoopLoadElim/memcheck.ll b/llvm/test/Transforms/LoopLoadElim/memcheck.ll
new file mode 100644
index 00000000000..ebb52825754
--- /dev/null
+++ b/llvm/test/Transforms/LoopLoadElim/memcheck.ll
@@ -0,0 +1,52 @@
+; RUN: opt -loop-load-elim -S < %s | FileCheck %s
+; RUN: opt -loop-load-elim -S -runtime-check-per-loop-load-elim=2 < %s | FileCheck %s --check-prefix=AGGRESSIVE
+
+; This needs two pairs of memchecks (A * { C, D }) for a single load
+; elimination which is considered to expansive by default.
+;
+;   for (unsigned i = 0; i < 100; i++) {
+;     A[i+1] = B[i] + 2;
+;     C[i] = A[i] * 2;
+;     D[i] = 2;
+;   }
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32*  %A, i32*  %B, i32*  %C, i64 %N, i32* %D) {
+entry:
+  br label %for.body
+
+; AGGRESSIVE: for.body.lver.memcheck:
+; AGGRESSIVE: %found.conflict{{.*}} =
+; AGGRESSIVE: %found.conflict{{.*}} =
+; AGGRESSIVE-NOT: %found.conflict{{.*}} =
+
+for.body:                                         ; preds = %for.body, %entry
+; CHECK-NOT: %store_forwarded =
+; AGGRESSIVE: %store_forwarded =
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+
+  %Aidx_next = getelementptr inbounds i32, i32* %A, i64 %indvars.iv.next
+  %Bidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %Cidx = getelementptr inbounds i32, i32* %C, i64 %indvars.iv
+  %Aidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %Didx = getelementptr inbounds i32, i32* %D, i64 %indvars.iv
+
+  %b = load i32, i32* %Bidx, align 4
+  %a_p1 = add i32 %b, 2
+  store i32 %a_p1, i32* %Aidx_next, align 4
+
+  %a = load i32, i32* %Aidx, align 4
+; CHECK: %c = mul i32 %a, 2
+; AGGRESSIVE: %c = mul i32 %store_forwarded, 2
+  %c = mul i32 %a, 2
+  store i32 %c, i32* %Cidx, align 4
+  store i32 2, i32* %Didx, align 4
+
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
diff --git a/llvm/test/Transforms/LoopLoadElim/multiple-stores-same-block.ll b/llvm/test/Transforms/LoopLoadElim/multiple-stores-same-block.ll
new file mode 100644
index 00000000000..b0c0f3dee86
--- /dev/null
+++ b/llvm/test/Transforms/LoopLoadElim/multiple-stores-same-block.ll
@@ -0,0 +1,48 @@
+; RUN: opt -basicaa -loop-load-elim -S < %s | FileCheck %s
+
+; In this case the later store forward to the load:
+;
+;   for (unsigned i = 0; i < 100; i++) {
+;     B[i] = A[i] + 1;
+;     A[i+1] = C[i] + 2;
+;     A[i+1] = D[i] + 3;
+;   }
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* noalias nocapture %A, i32* noalias nocapture readonly %B,
+               i32* noalias nocapture %C, i32* noalias nocapture readonly %D,
+               i64 %N) {
+entry:
+; CHECK: %load_initial = load i32, i32* %A
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+; CHECK: %store_forwarded = phi i32 [ %load_initial, %entry ], [ %addD, %for.body ]
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidxA = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %loadA = load i32, i32* %arrayidxA, align 4
+; CHECK: %addA = add i32 %store_forwarded, 1
+  %addA = add i32 %loadA, 1
+
+  %arrayidxB = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  store i32 %addA, i32* %arrayidxB, align 4
+
+  %arrayidxC = getelementptr inbounds i32, i32* %C, i64 %indvars.iv
+  %loadC = load i32, i32* %arrayidxC, align 4
+  %addC = add i32 %loadC, 2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %arrayidxA_next = getelementptr inbounds i32, i32* %A, i64 %indvars.iv.next
+  store i32 %addC, i32* %arrayidxA_next, align 4
+
+  %arrayidxD = getelementptr inbounds i32, i32* %D, i64 %indvars.iv
+  %loadD = load i32, i32* %arrayidxD, align 4
+  %addD = add i32 %loadD, 3
+  store i32 %addD, i32* %arrayidxA_next, align 4
+
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
diff --git a/llvm/test/Transforms/LoopLoadElim/unknown-dep.ll b/llvm/test/Transforms/LoopLoadElim/unknown-dep.ll
new file mode 100644
index 00000000000..d2df718ca4c
--- /dev/null
+++ b/llvm/test/Transforms/LoopLoadElim/unknown-dep.ll
@@ -0,0 +1,54 @@
+; RUN: opt -basicaa -loop-load-elim -S < %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+; Give up in the presence of unknown deps. Here, the different strides result
+; in unknown dependence:
+;
+;   for (unsigned i = 0; i < 100; i++) {
+;     A[i+1] = B[i] + 2;
+;     A[2*i] = C[i] + 2;
+;     D[i] = A[i] + 2;
+;   }
+
+define void @f(i32* noalias %A, i32* noalias %B, i32* noalias %C,
+               i32* noalias %D, i64 %N) {
+
+entry:
+; for.body.ph:
+; CHECK-NOT: %load_initial =
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+; CHECK-NOT: %store_forwarded =
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+
+  %Aidx_next = getelementptr inbounds i32, i32* %A, i64 %indvars.iv.next
+  %Bidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %Cidx = getelementptr inbounds i32, i32* %C, i64 %indvars.iv
+  %Didx = getelementptr inbounds i32, i32* %D, i64 %indvars.iv
+  %Aidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %indvars.m2 = mul nuw nsw i64 %indvars.iv, 2
+  %A2idx = getelementptr inbounds i32, i32* %A, i64 %indvars.m2
+
+  %b = load i32, i32* %Bidx, align 4
+  %a_p1 = add i32 %b, 2
+  store i32 %a_p1, i32* %Aidx_next, align 4
+
+  %c = load i32, i32* %Cidx, align 4
+  %a_m2 = add i32 %c, 2
+  store i32 %a_m2, i32* %A2idx, align 4
+
+  %a = load i32, i32* %Aidx, align 4
+; CHECK-NOT: %d = add i32 %store_forwarded, 2
+; CHECK: %d = add i32 %a, 2
+  %d = add i32 %a, 2
+  store i32 %d, i32* %Didx, align 4
+
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}