SLP Vectorizer: Add support for trees with external users.

To support this we have to insert 'extractelement' instructions to pick the right lane.
We had this functionality before but I removed it when we moved to the multi-block design because it was too complicated.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185230 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 117 insertions, 6 deletions

diff --git a/test/Transforms/SLPVectorizer/X86/cse.ll b/test/Transforms/SLPVectorizer/X86/cse.ll
index 17b966bd962..63eaeecf110 100644
--- a/test/Transforms/SLPVectorizer/X86/cse.ll
+++ b/test/Transforms/SLPVectorizer/X86/cse.ll
@@ -11,13 +11,12 @@ target triple = "i386-apple-macosx10.8.0"
 ;}
 
 ;CHECK: @test
-;CHECK: insertelement <2 x double> undef
-;CHECK-NEXT: insertelement <2 x double>
-;CHECK-NEXT: fadd <2 x double>
+;CHECK: load <2 x double>
+;CHECK: fadd <2 x double>
+;CHECK: store <2 x double>
+;CHECK: insertelement <2 x double>
+;CHECK: fadd <2 x double>
 ;CHECK: store <2 x double>
-;CHECK:  insertelement <2 x double>
-;CHECK-NEXT:  fadd <2 x double>
-;CHECK:  store <2 x double>
 ;CHECK: ret i32
 
 define i32 @test(double* nocapture %G) {
diff --git a/test/Transforms/SLPVectorizer/X86/external_user.ll b/test/Transforms/SLPVectorizer/X86/external_user.ll
new file mode 100644
index 00000000000..7f032b5b197
--- /dev/null
+++ b/test/Transforms/SLPVectorizer/X86/external_user.ll
@@ -0,0 +1,61 @@
+; RUN: opt < %s -basicaa -slp-vectorizer -dce -S -mtriple=x86_64-apple-macosx10.8.0 -mcpu=corei7-avx | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.8.0"
+
+; double foo(double * restrict b,  double * restrict a, int n, int m) {
+;   double r=a[1];
+;   double g=a[0];
+;   double x;
+;   for (int i=0; i < 100; i++) {
+;     r += 10;
+;     g += 10;
+;     r *= 4;
+;     g *= 4;
+;     x = g; <----- external user!
+;     r += 4;
+;     g += 4;
+;   }
+;   b[0] = g;
+;   b[1] = r;
+;
+;   return x; <-- must extract here!
+; }
+
+;CHECK: ext_user
+;CHECK: phi <2 x double>
+;CHECK: fadd <2 x double>
+;CHECK: fmul <2 x double>
+;CHECK: extractelement <2 x double>
+;CHECK: br
+;CHECK: store <2 x double>
+;CHECK: ret double
+
+define double @ext_user(double* noalias nocapture %B, double* noalias nocapture %A, i32 %n, i32 %m) {
+entry:
+  %arrayidx = getelementptr inbounds double* %A, i64 1
+  %0 = load double* %arrayidx, align 8
+  %1 = load double* %A, align 8
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.020 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %G.019 = phi double [ %1, %entry ], [ %add5, %for.body ]
+  %R.018 = phi double [ %0, %entry ], [ %add4, %for.body ]
+  %add = fadd double %R.018, 1.000000e+01
+  %add2 = fadd double %G.019, 1.000000e+01
+  %mul = fmul double %add, 4.000000e+00
+  %mul3 = fmul double %add2, 4.000000e+00
+  %add4 = fadd double %mul, 4.000000e+00
+  %add5 = fadd double %mul3, 4.000000e+00
+  %inc = add nsw i32 %i.020, 1
+  %exitcond = icmp eq i32 %inc, 100
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  store double %add5, double* %B, align 8
+  %arrayidx7 = getelementptr inbounds double* %B, i64 1
+  store double %add4, double* %arrayidx7, align 8
+  ret double %mul3
+}
+
diff --git a/test/Transforms/SLPVectorizer/X86/phi.ll b/test/Transforms/SLPVectorizer/X86/phi.ll
index af0b4808011..1c7f9ccf602 100644
--- a/test/Transforms/SLPVectorizer/X86/phi.ll
+++ b/test/Transforms/SLPVectorizer/X86/phi.ll
@@ -44,3 +44,54 @@ if.end:                                           ; preds = %entry, %if.else
   ret i32 undef
 }
 
+
+;int foo(double * restrict B,  double * restrict A, int n, int m) {
+;  double R=A[1];
+;  double G=A[0];
+;  for (int i=0; i < 100; i++) {
+;    R += 10;
+;    G += 10;
+;    R *= 4;
+;    G *= 4;
+;    R += 4;
+;    G += 4;
+;  }
+;  B[0] = G;
+;  B[1] = R;
+;  return 0;
+;}
+
+;CHECK: foo2
+;CHECK: load <2 x double>
+;CHECK: phi <2 x double>
+;CHECK: fmul <2 x double>
+;CHECK: store <2 x double>
+;CHECK: ret
+define i32 @foo2(double* noalias nocapture %B, double* noalias nocapture %A, i32 %n, i32 %m) #0 {
+entry:
+  %arrayidx = getelementptr inbounds double* %A, i64 1
+  %0 = load double* %arrayidx, align 8
+  %1 = load double* %A, align 8
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.019 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %G.018 = phi double [ %1, %entry ], [ %add5, %for.body ]
+  %R.017 = phi double [ %0, %entry ], [ %add4, %for.body ]
+  %add = fadd double %R.017, 1.000000e+01
+  %add2 = fadd double %G.018, 1.000000e+01
+  %mul = fmul double %add, 4.000000e+00
+  %mul3 = fmul double %add2, 4.000000e+00
+  %add4 = fadd double %mul, 4.000000e+00
+  %add5 = fadd double %mul3, 4.000000e+00
+  %inc = add nsw i32 %i.019, 1
+  %exitcond = icmp eq i32 %inc, 100
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  store double %add5, double* %B, align 8
+  %arrayidx7 = getelementptr inbounds double* %B, i64 1
+  store double %add4, double* %arrayidx7, align 8
+  ret i32 0
+}
+