Add support for bottom-up SLP vectorization infrastructure.

This commit adds the infrastructure for performing bottom-up SLP vectorization (and other optimizations) on parallel computations.
The infrastructure has three potential users:

  1. The loop vectorizer needs to be able to vectorize AOS data structures such as (sum += A[i] + A[i+1]).

  2. The BB-vectorizer needs this infrastructure for bottom-up SLP vectorization, because bottom-up vectorization is faster to compute.

  3. A loop-roller needs to be able to analyze consecutive chains and roll them into a loop, in order to reduce code size. A loop roller does not need to create vector instructions, and this infrastructure separates the chain analysis from the vectorization.

This patch also includes a simple (100 LOC) bottom up SLP vectorizer that uses the infrastructure, and can vectorize this code:

void SAXPY(int *x, int *y, int a, int i) {
  x[i]   = a * x[i]   + y[i];
  x[i+1] = a * x[i+1] + y[i+1];
  x[i+2] = a * x[i+2] + y[i+2];
  x[i+3] = a * x[i+3] + y[i+3];
}



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

7 files changed, 280 insertions, 0 deletions

diff --git a/test/Transforms/SLPVectorizer/X86/flag.ll b/test/Transforms/SLPVectorizer/X86/flag.ll
new file mode 100644
index 0000000000..a76ebd798c
--- /dev/null
+++ b/test/Transforms/SLPVectorizer/X86/flag.ll
@@ -0,0 +1,51 @@
+; RUN: opt < %s -basicaa -slp-vectorizer -slp-threshold=1000 -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"
+
+; Check that the command line flag works.
+;CHECK:rollable
+;CHECK-NOT:load <4 x i32>
+;CHECK: ret
+
+define i32 @rollable(i32* noalias nocapture %in, i32* noalias nocapture %out, i64 %n) nounwind ssp uwtable {
+  %1 = icmp eq i64 %n, 0
+  br i1 %1, label %._crit_edge, label %.lr.ph
+
+.lr.ph:                                           ; preds = %0, %.lr.ph
+  %i.019 = phi i64 [ %26, %.lr.ph ], [ 0, %0 ]
+  %2 = shl i64 %i.019, 2
+  %3 = getelementptr inbounds i32* %in, i64 %2
+  %4 = load i32* %3, align 4
+  %5 = or i64 %2, 1
+  %6 = getelementptr inbounds i32* %in, i64 %5
+  %7 = load i32* %6, align 4
+  %8 = or i64 %2, 2
+  %9 = getelementptr inbounds i32* %in, i64 %8
+  %10 = load i32* %9, align 4
+  %11 = or i64 %2, 3
+  %12 = getelementptr inbounds i32* %in, i64 %11
+  %13 = load i32* %12, align 4
+  %14 = mul i32 %4, 7
+  %15 = add i32 %14, 7
+  %16 = mul i32 %7, 7
+  %17 = add i32 %16, 14
+  %18 = mul i32 %10, 7
+  %19 = add i32 %18, 21
+  %20 = mul i32 %13, 7
+  %21 = add i32 %20, 28
+  %22 = getelementptr inbounds i32* %out, i64 %2
+  store i32 %15, i32* %22, align 4
+  %23 = getelementptr inbounds i32* %out, i64 %5
+  store i32 %17, i32* %23, align 4
+  %24 = getelementptr inbounds i32* %out, i64 %8
+  store i32 %19, i32* %24, align 4
+  %25 = getelementptr inbounds i32* %out, i64 %11
+  store i32 %21, i32* %25, align 4
+  %26 = add i64 %i.019, 1
+  %exitcond = icmp eq i64 %26, %n
+  br i1 %exitcond, label %._crit_edge, label %.lr.ph
+
+._crit_edge:                                      ; preds = %.lr.ph, %0
+  ret i32 undef
+}
diff --git a/test/Transforms/SLPVectorizer/X86/lit.local.cfg b/test/Transforms/SLPVectorizer/X86/lit.local.cfg
new file mode 100644
index 0000000000..a8ad0f1a28
--- /dev/null
+++ b/test/Transforms/SLPVectorizer/X86/lit.local.cfg
@@ -0,0 +1,6 @@
+config.suffixes = ['.ll', '.c', '.cpp']
+
+targets = set(config.root.targets_to_build.split())
+if not 'X86' in targets:
+    config.unsupported = True
+
diff --git a/test/Transforms/SLPVectorizer/X86/multi_user.ll b/test/Transforms/SLPVectorizer/X86/multi_user.ll
new file mode 100644
index 0000000000..cd47eb34b0
--- /dev/null
+++ b/test/Transforms/SLPVectorizer/X86/multi_user.ll
@@ -0,0 +1,47 @@
+; 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.7.0"
+
+;int foo (int *A, int n) {
+;  A[0] += n * 5 + 7;
+;  A[1] += n * 5 + 8;
+;  A[2] += n * 5 + 9;
+;  A[3] += n * 5 + 10;
+;  A[4] += n * 5 + 11;
+;}
+
+;CHECK: @foo
+;CHECK: insertelement <4 x i32>
+;CHECK: load <4 x i32>
+;CHECK: add <4 x i32>
+;CHECK: store <4 x i32>
+;CHECK: ret
+define i32 @foo(i32* nocapture %A, i32 %n) nounwind ssp uwtable {
+  %1 = mul nsw i32 %n, 5
+  %2 = add nsw i32 %1, 7
+  %3 = load i32* %A, align 4
+  %4 = add nsw i32 %2, %3
+  store i32 %4, i32* %A, align 4
+  %5 = add nsw i32 %1, 8
+  %6 = getelementptr inbounds i32* %A, i64 1
+  %7 = load i32* %6, align 4
+  %8 = add nsw i32 %5, %7
+  store i32 %8, i32* %6, align 4
+  %9 = add nsw i32 %1, 9
+  %10 = getelementptr inbounds i32* %A, i64 2
+  %11 = load i32* %10, align 4
+  %12 = add nsw i32 %9, %11
+  store i32 %12, i32* %10, align 4
+  %13 = add nsw i32 %1, 10
+  %14 = getelementptr inbounds i32* %A, i64 3
+  %15 = load i32* %14, align 4
+  %16 = add nsw i32 %13, %15
+  store i32 %16, i32* %14, align 4
+  %17 = add nsw i32 %1, 11
+  %18 = getelementptr inbounds i32* %A, i64 4
+  %19 = load i32* %18, align 4
+  %20 = add nsw i32 %17, %19
+  store i32 %20, i32* %18, align 4
+  ret i32 undef
+}
diff --git a/test/Transforms/SLPVectorizer/X86/saxpy.ll b/test/Transforms/SLPVectorizer/X86/saxpy.ll
new file mode 100644
index 0000000000..5f06f9f4af
--- /dev/null
+++ b/test/Transforms/SLPVectorizer/X86/saxpy.ll
@@ -0,0 +1,50 @@
+; 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"
+
+; SLP vectorization example from http://cs.stanford.edu/people/eschkufz/research/asplos291-schkufza.pdf
+;CHECK: SAXPY
+;CHECK: mul <4 x i32>
+;CHECK: ret
+
+define void @SAXPY(i32* noalias nocapture %x, i32* noalias nocapture %y, i32 %a, i64 %i) #0 {
+  %1 = getelementptr inbounds i32* %x, i64 %i
+  %2 = load i32* %1, align 4, !tbaa !0
+  %3 = mul nsw i32 %2, %a
+  %4 = getelementptr inbounds i32* %y, i64 %i
+  %5 = load i32* %4, align 4, !tbaa !0
+  %6 = add nsw i32 %3, %5
+  store i32 %6, i32* %1, align 4, !tbaa !0
+  %7 = add i64 %i, 1
+  %8 = getelementptr inbounds i32* %x, i64 %7
+  %9 = load i32* %8, align 4, !tbaa !0
+  %10 = mul nsw i32 %9, %a
+  %11 = getelementptr inbounds i32* %y, i64 %7
+  %12 = load i32* %11, align 4, !tbaa !0
+  %13 = add nsw i32 %10, %12
+  store i32 %13, i32* %8, align 4, !tbaa !0
+  %14 = add i64 %i, 2
+  %15 = getelementptr inbounds i32* %x, i64 %14
+  %16 = load i32* %15, align 4, !tbaa !0
+  %17 = mul nsw i32 %16, %a
+  %18 = getelementptr inbounds i32* %y, i64 %14
+  %19 = load i32* %18, align 4, !tbaa !0
+  %20 = add nsw i32 %17, %19
+  store i32 %20, i32* %15, align 4, !tbaa !0
+  %21 = add i64 %i, 3
+  %22 = getelementptr inbounds i32* %x, i64 %21
+  %23 = load i32* %22, align 4, !tbaa !0
+  %24 = mul nsw i32 %23, %a
+  %25 = getelementptr inbounds i32* %y, i64 %21
+  %26 = load i32* %25, align 4, !tbaa !0
+  %27 = add nsw i32 %24, %26
+  store i32 %27, i32* %22, align 4, !tbaa !0
+  ret void
+}
+
+attributes #0 = { nounwind ssp uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf"="true" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!0 = metadata !{metadata !"int", metadata !1}
+!1 = metadata !{metadata !"omnipotent char", metadata !2}
+!2 = metadata !{metadata !"Simple C/C++ TBAA"}
diff --git a/test/Transforms/SLPVectorizer/X86/simple-loop.ll b/test/Transforms/SLPVectorizer/X86/simple-loop.ll
new file mode 100644
index 0000000000..4c15ed00da
--- /dev/null
+++ b/test/Transforms/SLPVectorizer/X86/simple-loop.ll
@@ -0,0 +1,100 @@
+; 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"
+
+;CHECK:rollable
+define i32 @rollable(i32* noalias nocapture %in, i32* noalias nocapture %out, i64 %n) nounwind ssp uwtable {
+  %1 = icmp eq i64 %n, 0
+  br i1 %1, label %._crit_edge, label %.lr.ph
+
+.lr.ph:                                           ; preds = %0, %.lr.ph
+  %i.019 = phi i64 [ %26, %.lr.ph ], [ 0, %0 ]
+  %2 = shl i64 %i.019, 2
+  %3 = getelementptr inbounds i32* %in, i64 %2
+;CHECK:load <4 x i32>
+  %4 = load i32* %3, align 4
+  %5 = or i64 %2, 1
+  %6 = getelementptr inbounds i32* %in, i64 %5
+  %7 = load i32* %6, align 4
+  %8 = or i64 %2, 2
+  %9 = getelementptr inbounds i32* %in, i64 %8
+  %10 = load i32* %9, align 4
+  %11 = or i64 %2, 3
+  %12 = getelementptr inbounds i32* %in, i64 %11
+  %13 = load i32* %12, align 4
+;CHECK:mul <4 x i32>
+  %14 = mul i32 %4, 7
+;CHECK:add <4 x i32>
+  %15 = add i32 %14, 7
+  %16 = mul i32 %7, 7
+  %17 = add i32 %16, 14
+  %18 = mul i32 %10, 7
+  %19 = add i32 %18, 21
+  %20 = mul i32 %13, 7
+  %21 = add i32 %20, 28
+  %22 = getelementptr inbounds i32* %out, i64 %2
+;CHECK:store <4 x i32>
+  store i32 %15, i32* %22, align 4
+  %23 = getelementptr inbounds i32* %out, i64 %5
+  store i32 %17, i32* %23, align 4
+  %24 = getelementptr inbounds i32* %out, i64 %8
+  store i32 %19, i32* %24, align 4
+  %25 = getelementptr inbounds i32* %out, i64 %11
+  store i32 %21, i32* %25, align 4
+  %26 = add i64 %i.019, 1
+  %exitcond = icmp eq i64 %26, %n
+  br i1 %exitcond, label %._crit_edge, label %.lr.ph
+
+._crit_edge:                                      ; preds = %.lr.ph, %0
+;CHECK: ret
+  ret i32 undef
+}
+
+;CHECK:unrollable
+;CHECK-NOT: <4 x i32>
+;CHECK: ret
+define i32 @unrollable(i32* %in, i32* %out, i64 %n) nounwind ssp uwtable {
+  %1 = icmp eq i64 %n, 0
+  br i1 %1, label %._crit_edge, label %.lr.ph
+
+.lr.ph:                                           ; preds = %0, %.lr.ph
+  %i.019 = phi i64 [ %26, %.lr.ph ], [ 0, %0 ]
+  %2 = shl i64 %i.019, 2
+  %3 = getelementptr inbounds i32* %in, i64 %2
+  %4 = load i32* %3, align 4
+  %5 = or i64 %2, 1
+  %6 = getelementptr inbounds i32* %in, i64 %5
+  %7 = load i32* %6, align 4
+  %8 = or i64 %2, 2
+  %9 = getelementptr inbounds i32* %in, i64 %8
+  %10 = load i32* %9, align 4
+  %11 = or i64 %2, 3
+  %12 = getelementptr inbounds i32* %in, i64 %11
+  %13 = load i32* %12, align 4
+  %14 = mul i32 %4, 7
+  %15 = add i32 %14, 7
+  %16 = mul i32 %7, 7
+  %17 = add i32 %16, 14
+  %18 = mul i32 %10, 7
+  %19 = add i32 %18, 21
+  %20 = mul i32 %13, 7
+  %21 = add i32 %20, 28
+  %22 = getelementptr inbounds i32* %out, i64 %2
+  store i32 %15, i32* %22, align 4
+  %23 = getelementptr inbounds i32* %out, i64 %5
+  store i32 %17, i32* %23, align 4
+  %barrier = call i32 @goo(i32 0)                      ; <---------------- memory barrier.
+  %24 = getelementptr inbounds i32* %out, i64 %8
+  store i32 %19, i32* %24, align 4
+  %25 = getelementptr inbounds i32* %out, i64 %11
+  store i32 %21, i32* %25, align 4
+  %26 = add i64 %i.019, 1
+  %exitcond = icmp eq i64 %26, %n
+  br i1 %exitcond, label %._crit_edge, label %.lr.ph
+
+._crit_edge:                                      ; preds = %.lr.ph, %0
+  ret i32 undef
+}
+
+declare i32 @goo(i32)
diff --git a/test/Transforms/SLPVectorizer/X86/simplebb.ll b/test/Transforms/SLPVectorizer/X86/simplebb.ll
new file mode 100644
index 0000000000..0af30ab2bb
--- /dev/null
+++ b/test/Transforms/SLPVectorizer/X86/simplebb.ll
@@ -0,0 +1,25 @@
+; 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"
+
+; Simple 3-pair chain with loads and stores
+; CHECK: test1
+; CHECK: store <2 x double>
+; CHECK: ret
+define void @test1(double* %a, double* %b, double* %c) nounwind uwtable readonly {
+entry:
+  %i0 = load double* %a, align 8
+  %i1 = load double* %b, align 8
+  %mul = fmul double %i0, %i1
+  %arrayidx3 = getelementptr inbounds double* %a, i64 1
+  %i3 = load double* %arrayidx3, align 8
+  %arrayidx4 = getelementptr inbounds double* %b, i64 1
+  %i4 = load double* %arrayidx4, align 8
+  %mul5 = fmul double %i3, %i4
+  store double %mul, double* %c, align 8
+  %arrayidx5 = getelementptr inbounds double* %c, i64 1
+  store double %mul5, double* %arrayidx5, align 8
+  ret void
+}
+
diff --git a/test/Transforms/SLPVectorizer/lit.local.cfg b/test/Transforms/SLPVectorizer/lit.local.cfg
new file mode 100644
index 0000000000..19eebc0ac7
--- /dev/null
+++ b/test/Transforms/SLPVectorizer/lit.local.cfg
@@ -0,0 +1 @@
+config.suffixes = ['.ll', '.c', '.cpp']