[RFC] Support vectorization of min/max location pattern

Hi,

This patch adds vectorization support of min/max location pattern:

  for (i = 0; i < N; i++)
    if (arr[i] < limit)
      {
        pos = i + 1;
        limit = arr[i];
      }

The recognized pattern is compound of two statements (and is called
compound pattern):

  # pos_22 = PHI <pos_1(4), 1(2)>
  # limit_24 = PHI <limit_4(4), 0(2)>
  ...
  pos_1 = [cond_expr] limit_9 < limit_24 ? pos_10 : pos_22;
  limit_4 = [cond_expr] limit_9 < limit_24 ? limit_9 : limit_24;

both statements should be reductions with cond_expr and have the same
condition part. The min/max statement is expected to be of the form "x op
y ? x : y" (where op can be >, <, >= or <=), and the location is expected
to be an induction.

To vectorize min/max location pattern we use a technique described in
"Multimedia vectorization of floating-point MIN/MAX reductions" by
A.J.C.Bik, X.Tian and M.B.Girkar,
http://portal.acm.org/citation.cfm?id=1145765.

Vectorized loop (maxloc, first index):
     vcx[0:vl-1:1] = | x |..| x |;  - vector of max values
     vck[0:vl-1:1] = | k |..| k |;  - vector of positions
     ind[0:vl-1:1] = |vl-1|..| 0 |;
     inc[0:vl-1:1] = | vl |..| vl |;
     for (i = 0; i < N; i += vl) {
       msk[0:vl-1:1] = (a[i:i+vl-1:1] > vcx[0:vl-1:1]);
       vck[0:vl-1:1] = (ind[0:vl-1:1] & msk[0:vl-1:1]) |
                       (vck[0:vl-1:1] & !msk[0:vl-1:1]);
       vcx[0:vl-1:1] = VMAX(vcx[0:vl-1:1], a[i:i+vl-1:1]);
       ind[0:vl-1:1] += inc[0:vl-1:1];
     }
     x = HMAX(vcx[0:vl-1:1]);       - scalar maximum extraction
     msk[0:vl-1:1] = (vcx[0:vl-1:1] == |x|..|x|);
     vck[0:vl-1:1] = (vck[0:vl-1:1] & msk[0:vl-1:1]) |
                     (|MaxInt|..|MaxInt| & !msk[0:vl-1:1]);
     k = HMIN(vck[0:vl-1:1]);       - first position extraction


Vectorization of minloc is supposed to help gas_dyn from Polyhedron as
discussed in PR 31067.

PRs 44710 and 44711 currently prevent the vectorization. PR 44711 can be
bypassed by using -fno-tree-pre. I'll wait for a fix of PR 44710 before I
commit this patch (after I regtest it again).
Also the case of pos = i; instead of pos = i+1; is not supported since in
this case the operands are switched, i.e., we get "x op y ? y : x".


My main question is the implementation of vector comparisons. I understand
that different targets can return different types of results. So instead of
defining new tree codes, I used target builtin which also returns the type
of the result.

Other comments are welcome too.

Bootstrapped and tested on powerpc64-suse-linux.

Thanks,
Ira


ChangeLog:

      * doc/tm.texi (TARGET_VECTORIZE_BUILTIN_VEC_CMP): Document.
      * target.h (struct vectorize): Add new target builtin.
      * tree-vectorizer.h (enum vect_compound_pattern): New.
      (struct _stmt_vec_info): Add new fields compound_pattern and
      reduc_scalar_result_stmt. Add macros to access them.
      (is_pattern_stmt_p): Return true for compound pattern.
      (vectorizable_condition): Add arguments.
      (vect_recog_compound_func_ptr): New function-pointer type.
      (NUM_COMPOUND_PATTERNS): New.
      (vect_compound_pattern_recog): Declare.
      * tree-vect-loop.c (vect_determine_vectorization_factor): Fix assert
      for compound patterns.
      (vect_analyze_scalar_cycles_1): Fix typo. Detect compound reduction
      patterns. Update comment.
      (vect_analyze_scalar_cycles): Update comment.
      (destroy_loop_vec_info): Update def stmt for the original pattern
      statement.
      (vect_is_simple_reduction_1): Skip compound pattern statements in
      uses check. Add spaces. Skip commutativity and type checks for
      minimum location statement. Fix printings.
      (vect_model_reduction_cost): Add min/max location pattern cost
      computation.
      (vect_create_epilogue_for_compound_pattern): New function.
      (vect_create_epilog_for_reduction): Don't retrieve the original
      statement for compound pattern. Fix comment accordingly. Store the
      result of vector reduction computation in a variable and use it. Call
      vect_create_epilogue_for_compound_pattern (). Check if optab exists
      before using it. Keep the scalar result computation statement. Use
      either exit phi node result or compound pattern result in scalar
      extraction. Don't expect to find an exit phi node for min/max
      statement.
      (vectorizable_reduction): Skip check for uses in loop for compound
      patterns. Don't retrieve the original statement for compound pattern.
      Call vectorizable_condition () with additional parameters. Skip
      reduction code check for compound patterns. Prepare operands for
      min/max location statement vectorization and pass them to
      vectorizable_condition ().
      (vectorizable_live_operation): Return TRUE for compound patterns.
      * tree-vect-patterns.c (vect_recog_min_max_loc_pattern): Declare.
      (vect_recog_compound_func_ptrs): Likewise.
      (vect_recog_min_max_loc_pattern): New function.
      (vect_compound_pattern_recog): Likewise.
      * target-def.h (TARGET_VECTORIZE_BUILTIN_VEC_CMP): New.
      * tree-vect-stmts.c (process_use): Mark compound pattern statements
as
      used by reduction.
      (vect_mark_stmts_to_be_vectorized): Allow compound pattern statements
      to be used by reduction.
      (vectorize_minmax_location_pattern): New function.
      (vectorizable_condition): Update comment, add arguments. Skip checks
      irrelevant for compound pattern. Check that vector comparisons are
      supported by the target. Prepare operands using new arguments. Call
      vectorize_minmax_location_pattern().
      (vect_analyze_stmt): Allow nested cycle statements to be used by
      reduction. Call vectorizable_condition () with additional arguments.
      (vect_transform_stmt): Call vectorizable_condition () with additional
      arguments.
      (new_stmt_vec_info): Initialize new fields.
      * config/rs6000/rs6000-builtin.def (ALTIVEC_BUILTIN_VCMPLTFP): New.
      (ALTIVEC_BUILTIN_VCMPLEFP): New.
      * config/rs6000/rs6000.c (rs6000_builtin_vect_compare): New.
      (TARGET_VECTORIZE_BUILTIN_VEC_CMP): Redefine.
      (struct builtin_description bdesc_2arg): Add altivec_vcmpltfp and
      altivec_vcmplefp.
      * config/rs6000/altivec.md (altivec_vcmpltfp): New pattern.
      (altivec_vcmplefp): Likewise.
      * tree-vect-slp.c (vect_get_and_check_slp_defs): Fail for compound
      patterns.

testsuite/ChangeLog:

      * gcc.dg/vect/vect.exp: Define how to run tests named fast-math*.c
      * lib/target-supports.exp (check_effective_target_vect_cmp): New.
      * gcc.dg/vect/fast-math-no-pre-minmax-loc-1.c: New test.
      * gcc.dg/vect/fast-math-no-pre-minmax-loc-2.c,
      gcc.dg/vect/fast-math-no-pre-minmax-loc-3.c,
      gcc.dg/vect/fast-math-no-pre-minmax-loc-4.c,
      gcc.dg/vect/fast-math-no-pre-minmax-loc-5.c,
      gcc.dg/vect/fast-math-no-pre-minmax-loc-6.c,
      gcc.dg/vect/fast-math-no-pre-minmax-loc-7.c,
      gcc.dg/vect/fast-math-no-pre-minmax-loc-8.c,
      gcc.dg/vect/fast-math-no-pre-minmax-loc-9.c: Likewise.


(See attached file: minloc.txt)(See attached file: minloc-tests.txt)

Index: gcc.dg/vect/fast-math-no-pre-minmax-loc-9.c
===================================================================

--- gcc.dg/vect/fast-math-no-pre-minmax-loc-9.c	(revision 0)
+++ gcc.dg/vect/fast-math-no-pre-minmax-loc-9.c	(revision 0)
@@ -0,0 +1,47 @@
+/* { dg-require-effective-target vect_float } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "tree-vect.h"
+
+#define N 64
+float arr[N];
+
+__attribute__ ((noinline)) 
+int foo ()
+{
+  unsigned int pos = 1;
+  unsigned int i;
+  float limit = 12;
+
+  for (i = 0; i < N; i++)
+    if (arr[i] > limit)
+      {
+        pos = i + 1;
+        limit = arr[i];
+      }
+
+  return pos;
+}
+
+int main (void)
+{
+  int i, pos;
+
+  check_vect();
+
+  for (i = 0; i < N; i++)
+   arr[i] = (float)(i);
+
+  arr [2] = N + 15.8;
+
+  pos = foo ();
+  if (pos != 3)
+    abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { target vect_cmp } } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
Index: gcc.dg/vect/fast-math-no-pre-minmax-loc-1.c
===================================================================
--- gcc.dg/vect/fast-math-no-pre-minmax-loc-1.c	(revision 0)
+++ gcc.dg/vect/fast-math-no-pre-minmax-loc-1.c	(revision 0)
@@ -0,0 +1,47 @@
+/* { dg-require-effective-target vect_float } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "tree-vect.h"
+
+#define N 64
+float arr[N];
+
+__attribute__ ((noinline)) 
+int foo ()
+{
+  unsigned int pos = 1;
+  unsigned int i;
+  float limit = N+N;
+
+  for (i = 0; i < N; i++)
+    if (arr[i] < limit)
+      {
+        pos = i + 1;
+        limit = arr[i];
+      }
+
+  return pos;
+}
+
+int main (void)
+{
+  int i, pos;
+
+  check_vect();
+
+  for (i = 0; i < N; i++)
+   arr[i] = (float)(i);
+
+  arr [2] = -5.8;
+
+  pos = foo ();
+  if (pos != 3)
+    abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { target vect_cmp } } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
Index: gcc.dg/vect/fast-math-no-pre-minmax-loc-2.c
===================================================================
--- gcc.dg/vect/fast-math-no-pre-minmax-loc-2.c	(revision 0)
+++ gcc.dg/vect/fast-math-no-pre-minmax-loc-2.c	(revision 0)
@@ -0,0 +1,49 @@
+/* { dg-require-effective-target vect_float } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "tree-vect.h"
+
+#define N 64
+float arr[N];
+
+__attribute__ ((noinline)) 
+int foo (unsigned int n, float *min)
+{
+  unsigned int pos = 1;
+  unsigned int i;
+  float limit = N+N;
+
+  for (i = 0; i < N; i++)
+    if (arr[i] < limit)
+      {
+        pos = i + 1;
+        limit = arr[i];
+      }
+
+  *min = limit;
+  return pos;
+}
+
+int main (void)
+{
+  int i, pos;
+  float min;
+
+  check_vect();
+
+  for (i = 0; i < N; i++)
+   arr[i] = (float)(i);
+
+  arr[2] = -5.8;
+
+  pos = foo (N, &min);
+  if (pos != 3 || min != arr[2])
+    abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { target vect_cmp } } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
Index: gcc.dg/vect/fast-math-no-pre-minmax-loc-3.c
===================================================================
--- gcc.dg/vect/fast-math-no-pre-minmax-loc-3.c	(revision 0)
+++ gcc.dg/vect/fast-math-no-pre-minmax-loc-3.c	(revision 0)
@@ -0,0 +1,55 @@
+/* { dg-require-effective-target vect_float } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "tree-vect.h"
+
+#define N 64
+float arr[N];
+short a[N];
+
+/* Loop with multiple types - currently not supported.  */
+__attribute__ ((noinline)) 
+int foo (unsigned int n, float *min, short x)
+{
+  unsigned int pos = 1;
+  unsigned int i;
+  float limit = N+N;
+
+  for (i = 0; i < n; i++)
+    {
+      if (arr[i] < limit)
+        {
+          limit = arr[i];
+          pos = i + 1;
+        }
+
+      a[i] = x;
+    }
+
+  *min = limit;
+  return pos;
+}
+
+int main (void)
+{
+  int i, pos;
+  float min;
+
+  check_vect();
+
+  for (i = 0; i < N; i++)
+   arr[i] = (float)(i);
+
+  arr[2] = -5.8;
+
+  pos = foo (N, &min, 6);
+  if (pos != 3 || min != arr[2])
+    abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
Index: gcc.dg/vect/fast-math-no-pre-minmax-loc-4.c
===================================================================
--- gcc.dg/vect/fast-math-no-pre-minmax-loc-4.c	(revision 0)
+++ gcc.dg/vect/fast-math-no-pre-minmax-loc-4.c	(revision 0)
@@ -0,0 +1,52 @@
+/* { dg-require-effective-target vect_float } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "tree-vect.h"
+
+#define N 64
+#define MAX_VALUE N+N
+float arr[N];
+
+/* Not minloc pattern - different conditions.  */
+__attribute__ ((noinline)) 
+int foo ()
+{
+  unsigned int pos = 1;
+  unsigned int i;
+  float limit = MAX_VALUE;
+
+  for (i = 0; i < N; i++)
+    {
+      if (arr[i] < limit)
+        pos = i + 1;
+
+      if (arr[i] > limit)
+        limit = arr[i];
+    }
+
+  return pos;
+}
+
+int main (void)
+{
+  int i, pos;
+
+  check_vect();
+
+  for (i = 0; i < N; i++)
+   arr[i] = (float)(i);
+
+  arr[2] = -5.8;
+
+  pos = foo ();
+
+  if (pos != N)
+    abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
Index: gcc.dg/vect/fast-math-no-pre-minmax-loc-5.c
===================================================================
--- gcc.dg/vect/fast-math-no-pre-minmax-loc-5.c	(revision 0)
+++ gcc.dg/vect/fast-math-no-pre-minmax-loc-5.c	(revision 0)
@@ -0,0 +1,50 @@
+/* { dg-require-effective-target vect_float } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "tree-vect.h"
+
+#define N 64
+float arr[N];
+
+/* Not minloc pattern: position is not induction.  */
+__attribute__ ((noinline)) 
+int foo (unsigned int n, float *min)
+{
+  unsigned int pos = 1;
+  unsigned int i;
+  float limit = N+N;
+
+  for (i = 0; i < n; i++)
+    if (arr[i] < limit)
+      {
+        pos = 5;
+        limit = arr[i];
+      }
+
+  *min = limit;
+  return pos;
+}
+
+int main (void)
+{
+  int i, pos;
+  float min;
+
+  check_vect();
+
+  for (i = 0; i < N; i++)
+   arr[i] = (float)(i);
+
+  arr[2] = -5.8;
+
+  pos = foo (N, &min);
+  if (pos != 5 || min != arr[2])
+    abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
Index: gcc.dg/vect/fast-math-no-pre-minmax-loc-6.c
===================================================================
--- gcc.dg/vect/fast-math-no-pre-minmax-loc-6.c	(revision 0)
+++ gcc.dg/vect/fast-math-no-pre-minmax-loc-6.c	(revision 0)
@@ -0,0 +1,50 @@
+/* { dg-require-effective-target vect_float } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "tree-vect.h"
+
+#define N 64
+float arr[N];
+
+/* Position and minimum are of types of different sizes - not supported.  */
+__attribute__ ((noinline)) 
+int foo (unsigned short n, float *min)
+{
+  unsigned short pos = 1;
+  unsigned short i;
+  float limit = N+N;
+
+  for (i = 0; i < n; i++)
+    if (arr[i] < limit)
+      {
+        pos = i + 1;
+        limit = arr[i];
+      }
+
+  *min = limit;
+  return pos;
+}
+
+int main (void)
+{
+  int i, pos;
+  float min;
+
+  check_vect();
+
+  for (i = 0; i < N; i++)
+   arr[i] = (float)(i);
+
+  arr[2] = -5.8;
+
+  pos = foo (N, &min);
+  if (pos != 3 || min != arr[2])
+    abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
Index: gcc.dg/vect/vect.exp
===================================================================
--- gcc.dg/vect/vect.exp	(revision 161484)
+++ gcc.dg/vect/vect.exp	(working copy)
@@ -158,9 +158,27 @@ dg-runtest [lsort [glob -nocomplain $src
 # -ffast-math tests
 set DEFAULT_VECTCFLAGS $SAVED_DEFAULT_VECTCFLAGS
 lappend DEFAULT_VECTCFLAGS "-ffast-math"
-dg-runtest [lsort [glob -nocomplain $srcdir/$subdir/fast-math-*.\[cS\]]]  \
+dg-runtest [lsort [glob -nocomplain $srcdir/$subdir/fast-math-pr*.\[cS\]]]  \
 	"" $DEFAULT_VECTCFLAGS
 
+# -ffast-math tests
+set DEFAULT_VECTCFLAGS $SAVED_DEFAULT_VECTCFLAGS
+lappend DEFAULT_VECTCFLAGS "-ffast-math"
+dg-runtest [lsort [glob -nocomplain $srcdir/$subdir/fast-math-slp*.\[cS\]]]  \
+        "" $DEFAULT_VECTCFLAGS
+
+# -ffast-math tests
+set DEFAULT_VECTCFLAGS $SAVED_DEFAULT_VECTCFLAGS
+lappend DEFAULT_VECTCFLAGS "-ffast-math"
+dg-runtest [lsort [glob -nocomplain $srcdir/$subdir/fast-math-vect*.\[cS\]]]  \
+        "" $DEFAULT_VECTCFLAGS
+
+# -ffast-math and -fno-tree-pre tests
+set DEFAULT_VECTCFLAGS $SAVED_DEFAULT_VECTCFLAGS
+lappend DEFAULT_VECTCFLAGS "-ffast-math" "-fno-tree-pre"
+dg-runtest [lsort [glob -nocomplain $srcdir/$subdir/fast-math-no-pre*.\[cS\]]]  \
+        "" $DEFAULT_VECTCFLAGS
+
 # -fno-math-errno tests
 set DEFAULT_VECTCFLAGS $SAVED_DEFAULT_VECTCFLAGS
 lappend DEFAULT_VECTCFLAGS "-fno-math-errno"
Index: gcc.dg/vect/fast-math-no-pre-minmax-loc-7.c
===================================================================
--- gcc.dg/vect/fast-math-no-pre-minmax-loc-7.c	(revision 0)
+++ gcc.dg/vect/fast-math-no-pre-minmax-loc-7.c	(revision 0)
@@ -0,0 +1,49 @@
+/* { dg-require-effective-target vect_float } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "tree-vect.h"
+
+#define N 64
+float arr[N][N];
+
+/* Double reduction.  */
+__attribute__ ((noinline)) 
+int foo ()
+{
+  unsigned int pos = 1;
+  unsigned int i, j;
+  float limit = N+N;
+
+  for (j = 0; j < N; j++)
+    for (i = 0; i < N; i++)
+      if (arr[i][j] < limit)
+        {
+          pos = i + 1;
+          limit = arr[i][j];
+        }
+
+  return pos;
+}
+
+int main (void)
+{
+  int i, j, pos;
+
+  check_vect();
+
+  for (j = 0; j < N; j++)
+    for (i = 0; i < N; i++)
+      arr[j][i] = (float)(i+j+1);
+
+  arr[8][2] = 0;
+  pos = foo ();
+  if (pos != 9)
+    abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { target vect_cmp } } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
Index: gcc.dg/vect/fast-math-no-pre-minmax-loc-8.c
===================================================================
--- gcc.dg/vect/fast-math-no-pre-minmax-loc-8.c	(revision 0)
+++ gcc.dg/vect/fast-math-no-pre-minmax-loc-8.c	(revision 0)
@@ -0,0 +1,48 @@
+/* { dg-require-effective-target vect_float } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "tree-vect.h"
+
+#define N 64
+float arr[N];
+
+__attribute__ ((noinline)) 
+int foo ()
+{
+  unsigned int pos = 1;
+  unsigned int i;
+  float limit = 7;
+
+  for (i = 0; i < N; i++)
+    if (arr[i] >= limit)
+      {
+        pos = i + 1;
+        limit = arr[i];
+      }
+
+  return pos;
+}
+
+int main (void)
+{
+  int i, pos;
+
+  check_vect();
+
+  for (i = 0; i < N; i++)
+   arr[i] = (float)(i);
+
+  arr [2] = N + 5.8;
+  arr [12] = N + 5.8;
+
+  pos = foo ();
+  if (pos != 13)
+    abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { target vect_cmp } } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
Index: lib/target-supports.exp
===================================================================
--- lib/target-supports.exp	(revision 161484)
+++ lib/target-supports.exp	(working copy)
@@ -2839,6 +2839,23 @@ proc check_effective_target_vect_strided
     return $et_vect_strided_wide_saved
 }
 
+# Return 1 if the target supports vector comparison, 0 otherwise.
+proc check_effective_target_vect_cmp { } {
+    global et_vect_cmp_saved
+
+    if [info exists et_vect_cmp_saved] {
+        verbose "check_effective_target_vect_cmp: using cached result" 2
+    } else {
+        set et_vect_cmp_saved 0
+        if { [istarget powerpc*-*-*] } {
+           set et_vect_cmp_saved 1
+        }
+    }
+
+    verbose "check_effective_target_vect_cmp: returning $et_vect_cmp_saved" 2
+    return $et_vect_cmp_saved
+}
+
 # Return 1 if the target supports section-anchors
 
 proc check_effective_target_section_anchors { } {


[RFC] Support vectorization of min/max location pattern

Commit Message

Patch