[vect] Support min/max + index pattern

[vect] Support min/max + index pattern

[Joel Hutton]

[-- Attachment #1: Type: text/plain, Size: 1770 bytes --]

Hi all,

looking for some feedback on this, one thing I would like to draw attention to is the fact that this pattern requires 2 separate dependent reductions in the epilogue.
The accumulator vector for the maximum/minimum elements can be reduced to a scalar result trivially with a min/max, but getting the index from accumulator 
vector of indices is more complex and requires using the position of the maximum/minimum scalar result value within the accumulator vector to create a mask.

The given solution works but it's slightly messy. vect_create_epilogue_for_reduction creates the epilogue for one vectorized scalar stmt at a time. This modification makes one
invocation create the epilogue for both related stmts and marks the other as 'done'. Alternate suggestions are welcome.

Joel

[vect] Support min/max + index pattern

Add the capability to vect-loop to support the following pattern.

for (int i = 0; i < n; i ++)
{
    if (data[i] < best)
    {
        best = data[i];
        best_i = i;
    }
}

gcc/ChangeLog:

	* tree-vect-loop.c (vect_reassociating_reduction_simple_p): New                                                                                          
	function.                                                                                                                                                        
	(vect_recog_minmax_index_pattern): New function.                                                                                                             
	(vect_is_simple_reduction): Add multi_use_reduction case.                                                                                                    
	(vect_create_epilog_for_reduction): Add minmax+index epilogue handling.

[-- Attachment #2: minmax.patch --]
[-- Type: application/octet-stream, Size: 15287 bytes --]

diff --git a/gcc/testsuite/gcc.dg/vect/vect-127.c b/gcc/testsuite/gcc.dg/vect/vect-127.c
new file mode 100644
index 0000000000000000000000000000000000000000..fc1fb6eb7bc44fdcced4e6a904e998cce845b8dc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-127.c
@@ -0,0 +1,51 @@
+/* { dg-do run } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "-O3 -fdump-tree-vect-all -fno-vect-cost-model -fdisable-tree-cunroll" } */
+#include "tree-vect.h"
+#define ARR_LEN(A) (sizeof (A)/sizeof(A[0]))
+
+void max_to_front (int *data, int n) {
+  int best_i=0, best = 0;
+
+  for (int i = 0; i < n; i++) {
+    if (data[i] > best) {
+      best = data[i];
+      best_i = i;
+    }
+  }
+  data[best_i] = data[0];
+  data[0] = best;
+}
+
+void lastmax_to_front (int *data, int n) {
+  int best_i=0, best = 0;
+
+  for (int i = 0; i < n; i++) {
+    if (data[i] >= best) {
+      best = data[i];
+      best_i = i;
+    }
+  }
+  data[best_i] = data[0];
+  data[0] = best;
+}
+int main ()
+{
+	int a[] = {0,1,0,1,3,1,5,16,4,4,1,16,3,1};
+	max_to_front (a, ARR_LEN (a));
+	if (a[0] != 16 || a[7] != 0)
+	  abort ();
+
+	int b[] = {15,0,0,0,0,0,0,16,0,15,0,0,0,0};
+	max_to_front (b, ARR_LEN (b));
+	if (b[0] != 16 || b[7] != 15)
+	  abort ();
+
+	int c[] = {15,0,0,0,0,0,0,16,0,16,0,0,0,0};
+	lastmax_to_front (c, ARR_LEN (c));
+	if (c[0] != 16 || c[9] != 15)
+	  abort ();
+}
+
+/* { dg-final { scan-tree-dump-times "Found minmax index pattern.*" 1 "vect" } } */
+/* { dg-final { scan-tree-dump-times "Reduce minmax index pattern.*" 1 "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-128.c b/gcc/testsuite/gcc.dg/vect/vect-128.c
new file mode 100644
index 0000000000000000000000000000000000000000..a8f403433baec5b835213fa222cd453c8c85be37
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-128.c
@@ -0,0 +1,51 @@
+#include <limits.h>
+/* { dg-do run } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "-O3 -fdump-tree-vect-all -fno-vect-cost-model -fdisable-tree-cunroll" } */
+#include "tree-vect.h"
+#define ARR_LEN(A) (sizeof (A)/sizeof(A[0]))
+
+
+/* This is vectorized.  */
+void min_to_front (int *data, int n) {
+  int best_i=0, best = INT_MAX;
+
+  for (int i = 0; i < n; i++) {
+    if (data[i] < best) {
+      best = data[i];
+      best_i = i;
+    }
+  }
+  data[best_i] = data[0];
+  data[0] = best;
+}
+
+/* This is not vectorized.  */
+void lastmin_to_front (int *data, int n) {
+  int best_i=0, best = INT_MAX;
+
+  for (int i = 0; i < n; i++) {
+    if (data[i] <= best) {
+      best = data[i];
+      best_i = i;
+    }
+  }
+  data[best_i] = data[0];
+  data[0] = best;
+}
+
+int main ()
+{
+	int d[] = {15,-3,-2,-2,-3,-1,0,16,0,16,0,0,0,-3};
+	min_to_front (d, ARR_LEN (d));
+	if (d[0] != -3 || d[1] != 15)
+	  abort ();
+
+	int e[] = {15,-3,-2,-2,-3,-1,0,16,0,16,0,0,0,-3};
+	lastmin_to_front (e, ARR_LEN (e));
+	if (e[0] != -3 || e[13] != 15)
+	  abort ();
+}
+
+/* { dg-final { scan-tree-dump-times "Found minmax index pattern.*" 1 "vect" } } */
+/* { dg-final { scan-tree-dump-times "Reduce minmax index pattern.*" 1 "vect" } } */
diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
index 2aba503fef7b195c7dd18c3ff6977add1ab73d3c..c2dc26c1f6568d1e6f068985a8e3765d69bfb27a 100644
--- a/gcc/tree-vect-loop.c
+++ b/gcc/tree-vect-loop.c
@@ -156,6 +156,112 @@ static void vect_estimate_min_profitable_iters (loop_vec_info, int *, int *);
 static stmt_vec_info vect_is_simple_reduction (loop_vec_info, stmt_vec_info,
 					       bool *, bool *);
 
+static bool
+vect_reassociating_reduction_simple_p (stmt_vec_info stmt_info,
+				       loop_vec_info loop_info,
+				       tree_code code,
+				       tree *op0_out, tree *op1_out)
+{
+  gassign *assign = dyn_cast <gassign *> (stmt_info->stmt);
+  if (!assign || gimple_assign_rhs_code (assign) != code)
+    return false;
+
+  /* We don't allow changing the order of the computation in the inner-loop
+     when doing outer-loop vectorization.  */
+  class loop *loop = LOOP_VINFO_LOOP (loop_info);
+  if (loop && nested_in_vect_loop_p (loop, stmt_info))
+    return false;
+
+  *op0_out = gimple_assign_rhs1 (assign);
+  *op1_out = gimple_assign_rhs2 (assign);
+  return true;
+}
+
+/*
+ Recognises a loop of the form:
+  for (int i = 0; i < n; i++) {
+    if (data[i] > best) {
+      best = data[i];
+      best_i = i;
+    }
+  }
+  Returns true if stmt_info describes the min/max assignment stmt ("best = data[i];" in the example above)
+ */
+static bool
+vect_recog_minmax_index_pattern (stmt_vec_info stmt_vinfo,
+					loop_vec_info loop_vinfo)
+{
+  tree oprnd0, oprnd1;
+  gimple *stmt = stmt_vinfo->stmt;
+  gimple *use_stmt;
+  use_operand_p use_p;
+  imm_use_iterator iter;
+
+  if (!(vect_reassociating_reduction_simple_p (stmt_vinfo, loop_vinfo,
+					       MAX_EXPR,
+					       &oprnd0, &oprnd1)
+	|| vect_reassociating_reduction_simple_p (stmt_vinfo, loop_vinfo,
+						  MIN_EXPR,
+						  &oprnd0, &oprnd1)))
+    return false;
+
+  if (!((TREE_CODE (oprnd0) == SSA_NAME)
+	&& (TREE_CODE (oprnd1) == SSA_NAME)
+	&& (is_a <gphi *> (SSA_NAME_DEF_STMT (oprnd1))
+	    || is_a <gphi *> (SSA_NAME_DEF_STMT (oprnd0)))))
+    return false;
+
+
+  tree_code tc_stmt = gimple_assign_rhs_code (stmt);
+
+  /* Starting from LAST_STMT, follow the defs of its uses in search
+     of the above pattern.  */
+  FOR_EACH_IMM_USE_FAST (use_p, iter, oprnd1)
+    {
+      tree_code tc_us;
+      tree_code tc_us_cond;
+      use_stmt = USE_STMT (use_p);
+      if (stmt->bb != use_stmt->bb)
+	continue;
+      if (!is_gimple_assign (use_stmt))
+	continue;
+      tc_us = gimple_assign_rhs_code (use_stmt);
+      if (tc_us != COND_EXPR)
+	continue;
+      tree us_op0 = TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0);
+      tree us_op1 = TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 1);
+      if (!((us_op0 == oprnd0 && us_op1 == oprnd1)
+	    ||(us_op0 == oprnd1 && us_op1 == oprnd0)))
+	  continue;
+      tree us_cond = gimple_assign_rhs1 (use_stmt);
+      tc_us_cond = TREE_CODE (us_cond);
+      tree minmax_type = TREE_TYPE (gimple_assign_lhs (stmt_vinfo->stmt));
+      tree us_type = TREE_TYPE (gimple_assign_lhs (use_stmt));
+      if (minmax_type != us_type)
+	continue;
+      if ((tc_stmt == MAX_EXPR
+	   &&(tc_us_cond == GT_EXPR ||  tc_us_cond == LE_EXPR))
+	  || (tc_stmt == MIN_EXPR
+	      &&(tc_us_cond == LT_EXPR ||  tc_us_cond == GE_EXPR)))
+	{
+	  /* stmt which saves the index corresponding to min/max */
+	  stmt_vec_info ind_stmt = loop_vinfo->lookup_stmt (use_stmt);
+	  ind_stmt->reduc_multi_use_related_stmt = stmt_vinfo;
+	  stmt_vinfo->reduc_multi_use_related_stmt = ind_stmt;
+	  ind_stmt->is_minmax_index = true;
+	  stmt_vinfo->is_minmax = true;
+	  if (dump_enabled_p ())
+	  {
+	    dump_printf (MSG_NOTE, "Found minmax index pattern:\n %G%G",
+			 stmt_vinfo->stmt, ind_stmt->stmt);
+	  }
+	  return true;
+	}
+    }
+
+  return false;
+}
+
 /* Subroutine of vect_determine_vf_for_stmt that handles only one
    statement.  VECTYPE_MAYBE_SET_P is true if STMT_VINFO_VECTYPE
    may already be set for general statements (not just data refs).  */
@@ -3344,7 +3450,8 @@ needs_fold_left_reduction_p (tree type, tree_code code)
 static bool
 check_reduction_path (dump_user_location_t loc, loop_p loop, gphi *phi,
 		      tree loop_arg, enum tree_code *code,
-		      vec<std::pair<ssa_op_iter, use_operand_p> > &path)
+		      vec<std::pair<ssa_op_iter, use_operand_p> > &path,
+		      bool supported_multi_use_reduction)
 {
   auto_bitmap visited;
   tree lookfor = PHI_RESULT (phi);
@@ -3445,10 +3552,10 @@ pop:
 				    TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
 	;
       else if (*code == ERROR_MARK)
-	{
+      {
 	  *code = use_code;
 	  sign = TYPE_SIGN (TREE_TYPE (gimple_assign_lhs (use_stmt)));
-	}
+      }
       else if (use_code != *code)
 	{
 	  fail = true;
@@ -3484,7 +3591,7 @@ pop:
 	    else
 	      cnt++;
 	  }
-      if (cnt != 1)
+      if (cnt != 1 && !supported_multi_use_reduction)
 	{
 	  fail = true;
 	  break;
@@ -3499,7 +3606,7 @@ check_reduction_path (dump_user_location_t loc, loop_p loop, gphi *phi,
 {
   auto_vec<std::pair<ssa_op_iter, use_operand_p> > path;
   enum tree_code code_;
-  return (check_reduction_path (loc, loop, phi, loop_arg, &code_, path)
+  return (check_reduction_path (loc, loop, phi, loop_arg, &code_, path, false)
 	  && code_ == code);
 }
 
@@ -3638,10 +3745,14 @@ vect_is_simple_reduction (loop_vec_info loop_info, stmt_vec_info phi_info,
       return def_stmt_info;
     }
 
+  bool supported_multi_use_reduction
+    = vect_recog_minmax_index_pattern (def_stmt_info, loop_info);
+
   /* If this isn't a nested cycle or if the nested cycle reduction value
      is used ouside of the inner loop we cannot handle uses of the reduction
      value.  */
-  if (nlatch_def_loop_uses > 1 || nphi_def_loop_uses > 1)
+  if (!(supported_multi_use_reduction)
+	&& (nlatch_def_loop_uses > 1 || nphi_def_loop_uses > 1))
     {
       if (dump_enabled_p ())
 	dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
@@ -3688,7 +3799,7 @@ vect_is_simple_reduction (loop_vec_info loop_info, stmt_vec_info phi_info,
   auto_vec<std::pair<ssa_op_iter, use_operand_p> > path;
   enum tree_code code;
   if (check_reduction_path (vect_location, loop, phi, latch_def, &code,
-			    path))
+			    path, supported_multi_use_reduction))
     {
       STMT_VINFO_REDUC_CODE (phi_info) = code;
       if (code == COND_EXPR && !nested_in_vect_loop)
@@ -5312,7 +5423,124 @@ vect_create_epilog_for_reduction (loop_vec_info loop_vinfo,
   else
     new_phi_result = PHI_RESULT (new_phis[0]);
 
-  if (STMT_VINFO_REDUC_TYPE (reduc_info) == COND_REDUCTION
+  if (stmt_info->is_minmax_index || stmt_info->is_minmax)
+    {
+      if (dump_enabled_p ())
+	dump_printf_loc (MSG_NOTE, vect_location,
+			 "Reduce minmax index pattern\n");
+
+      stmt_vec_info minmax;
+      stmt_vec_info minmax_i;
+
+      if (stmt_info->is_minmax_index)
+      {
+	minmax_i = stmt_info;
+	minmax = stmt_info->reduc_multi_use_related_stmt;
+	if (induc_val != NULL_TREE)
+	  minmax_i->induc_val = induc_val;
+	if (initial_def != NULL_TREE)
+	  minmax_i->initial_def = initial_def;
+      }
+      else
+      {
+	minmax = stmt_info;
+	minmax_i = stmt_info->reduc_multi_use_related_stmt;
+      }
+
+      if (!stmt_info->epilog_finished
+	  && minmax->vec_stmts.length () != 0
+	  && minmax_i->vec_stmts.length () != 0)
+      {
+	/* The 'accumulator' stmts - the stmts that maintain a vector of
+	   minimum/maximum elements, and corresponding index respectively. */
+	gimple* minmax_accum_stmt = minmax->vec_stmts[0];
+	gimple* minmax_i_accum_stmt = minmax_i->vec_stmts[0];
+
+	tree minmax_accum_lhs = gimple_assign_lhs (minmax_accum_stmt);
+	tree minmax_i_accum_lhs = gimple_assign_lhs (minmax_i_accum_stmt);
+	tree scalar_type = TREE_TYPE (vectype);
+
+	/* Reduce the min/max accumulator to the final result by taking the min/max. */
+	if (gimple_assign_rhs_code (minmax->stmt) == MAX_EXPR)
+	  reduc_fn = IFN_REDUC_MAX;
+	else
+	  reduc_fn = IFN_REDUC_MIN;
+	if (minmax->scalar_result == NULL)
+	  minmax->scalar_result = make_ssa_name (scalar_type);
+	gimple* maxreducstmt = gimple_build_call_internal (reduc_fn, 1,
+							   minmax_accum_lhs);
+	gimple_call_set_lhs (maxreducstmt, minmax->scalar_result);
+	gsi_insert_before (&exit_gsi, maxreducstmt, GSI_NEW_STMT);
+
+	/* To reduce the index accumulator, the index corresponding to the
+	 scalar result reduced above must be extracted. Start by creating a vector 
+	 of {maxval, maxval...}.  */
+	tree maxval = minmax->scalar_result;
+	tree maxvec = make_ssa_name (vectype);
+	tree maxvec_rhs = build_vector_from_val (vectype, maxval);
+	gimple* maxvec_decl = gimple_build_assign (maxvec, maxvec_rhs);
+	gsi_insert_after (&exit_gsi, maxvec_decl, GSI_NEW_STMT);
+
+	/* Create a vector of {INT_MAX,INT_MAX,INT_MAX}.  */
+	tree intmax = TYPE_MAX_VALUE (TREE_TYPE (vectype));
+	tree intmaxvec = build_vector_from_val (vectype, intmax);
+
+	/* Select the correct index from the index accumulator vector, using
+	   the position in the minmax accumulator vector.  Mask out the
+	   incorrect indexes with INT_MAX, to allow for a MIN reduction.  */
+	tree truthvectype = truth_type_for (vectype);
+	tree cond = build2 (EQ_EXPR, truthvectype, minmax_accum_lhs, maxvec);
+	tree cond_lhs = make_ssa_name(truthvectype);
+	gimple* cond_decl = gimple_build_assign (cond_lhs, cond);
+	gsi_insert_after (&exit_gsi, cond_decl, GSI_NEW_STMT);
+	tree mask_rhs = build3 (VEC_COND_EXPR, truthvectype, cond_lhs,
+				minmax_i_accum_lhs, intmaxvec);
+	tree masked_ind = make_ssa_name (vectype);
+	gimple* masked_ind_stmt = gimple_build_assign (masked_ind, mask_rhs);
+	gsi_insert_after (&exit_gsi, masked_ind_stmt, GSI_NEW_STMT);
+
+	/* Reduce the index vector to a scalar result.  */
+	tree index_scalar_reduc;
+	if (minmax_i->scalar_result == NULL)
+	  minmax_i->scalar_result = make_ssa_name (TREE_TYPE (vectype));
+	if (minmax_i->induc_val == NULL_TREE)
+	  index_scalar_reduc = minmax_i->scalar_result;
+	else
+	  index_scalar_reduc = make_ssa_name (scalar_type);
+	gimple* index_result_stmt = gimple_build_call_internal (IFN_REDUC_MIN,
+								1, masked_ind);
+	gimple_call_set_lhs (index_result_stmt, index_scalar_reduc);
+	gsi_insert_after (&exit_gsi, index_result_stmt, GSI_NEW_STMT);
+
+	if (minmax_i->induc_val != NULL_TREE)
+	{
+	  /* Earlier we set the initial value to be a vector if induc_val
+	     values.  Check the result and if it is induc_val then replace
+	     with the original initial value, unless induc_val is
+	     the same as initial_def already.  */
+	  tree zcompare = build2 (EQ_EXPR, boolean_type_node,
+				  index_scalar_reduc, minmax_i->induc_val);
+
+	  epilog_stmt = gimple_build_assign (minmax_i->scalar_result, COND_EXPR,
+					     zcompare, minmax_i->initial_def,
+					     index_scalar_reduc);
+	  gsi_insert_after (&exit_gsi, epilog_stmt, GSI_NEW_STMT);
+	}
+
+	minmax->epilog_finished = true;
+	minmax_i->epilog_finished = true;
+      }
+      else if (stmt_info->scalar_result == NULL)
+      {
+	/* Placeholder.  The vectorized forms from both the max and the index
+	   are needed for the reduction.  */
+	tree scalar_result = make_ssa_name (scalar_type);
+	stmt_info->scalar_result = scalar_result;
+      }
+
+      scalar_results.safe_push (stmt_info->scalar_result);
+    }
+  else if (STMT_VINFO_REDUC_TYPE (reduc_info) == COND_REDUCTION
       && reduc_fn != IFN_LAST)
     {
       /* For condition reductions, we have a vector (NEW_PHI_RESULT) containing
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 9861d9e88102138c0e2de8dfc34422ff65a0e9e0..8ef402e5efb19e643645b4d788997c834c5ca118 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -1093,6 +1093,17 @@ public:
         pattern).  */
   stmt_vec_info related_stmt;
 
+  /* For handling multi phi reductions.  */
+  tree scalar_result;
+  stmt_vec_info reduc_multi_use_related_stmt;
+  gimple* reduc_multi_use_result;
+  tree induc_val;
+  tree initial_def;
+  bool is_minmax_index;
+  bool is_minmax;
+  bool epilog_finished;
+
+
   /* Used to keep a sequence of def stmts of a pattern stmt if such exists.
      The sequence is attached to the original statement rather than the
      pattern statement.  */

Re: [vect] Support min/max + index pattern

[Richard Biener]

On Wed, 5 May 2021, Joel Hutton wrote:

> Hi all,
> 
> looking for some feedback on this, one thing I would like to draw 
> attention to is the fact that this pattern requires 2 separate dependent 
> reductions in the epilogue. The accumulator vector for the 
> maximum/minimum elements can be reduced to a scalar result trivially 
> with a min/max, but getting the index from accumulator vector of indices 
> is more complex and requires using the position of the maximum/minimum 
> scalar result value within the accumulator vector to create a mask.
> 
> The given solution works but it's slightly messy. 
> vect_create_epilogue_for_reduction creates the epilogue for one 
> vectorized scalar stmt at a time. This modification makes one invocation 
> create the epilogue for both related stmts and marks the other as 
> 'done'. Alternate suggestions are welcome.

So I'm not looking at the very details in the patch but I think
a concept of "dependent" reductions might be useful (there might
be related patterns that could be vectorized).  So during
reduction discovery detect unhandled multi-uses and queue those
for later re-evaluation (in case we analyze the value reduction
first).  Discover the index reduction as regular reduction.
Upon re-analyzing the value reduction allow multi-uses that are
reductions themselves and note the dependence in some new stmt_vinfo
field.

Then during reduction analysis we can verify if we handle
a particular dependence and during code-gen we can ensure
to only code-gen one epilogue and have access to the other part.

That said, I'd make the thing a bit more generic in appearance
but otherwise yes, we do need to handle this together somehow.

+  /* For handling multi phi reductions.  */
+  tree scalar_result;
+  stmt_vec_info reduc_multi_use_related_stmt;
+  gimple* reduc_multi_use_result;
+  tree induc_val;
+  tree initial_def;
+  bool is_minmax_index;
+  bool is_minmax;
+  bool epilog_finished;

which should ideally reduce to a single field then.

Oh, and make sure an SLP variant is supported.

  for (int i = 0; i < n; i++) {
    if (data[2*i] < best1) {
      best1 = data[2*i];
      best_i1 = 2*i;
    }
    if (data[2*i+1] < best2) {
      best2 = data[2*i+1];
      best_i2 = 2*i;
    }
  }

Richard.

> Joel
> 
> [vect] Support min/max + index pattern
> 
> Add the capability to vect-loop to support the following pattern.
> 
> for (int i = 0; i < n; i ++)
> {
>     if (data[i] < best)
>     {
>         best = data[i];
>         best_i = i;
>     }
> }
> 
> gcc/ChangeLog:
> 
> 	* tree-vect-loop.c (vect_reassociating_reduction_simple_p): New                                                                                          
> 	function.                                                                                                                                                        
> 	(vect_recog_minmax_index_pattern): New function.                                                                                                             
> 	(vect_is_simple_reduction): Add multi_use_reduction case.                                                                                                    
> 	(vect_create_epilog_for_reduction): Add minmax+index epilogue handling.
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)