Hello,
Jakub Jelinek <ja...@redhat.com> writes:
> As it doesn't apply, I can't easily check what the patch generates
> on the PR80631 testcases vs. my thoughts on that; though, if it emits
> something more complicated for the simple cases, perhaps we could improve
> those (not handle it like COND_REDUCTION, but instead as former
> INTEGER_INDUC_COND_REDUCTION and just use a different constant instead of 0
> if 0 isn't usable for the condition never matched value.
While you could use values different from 0, I'm not sure this can be
done as efficiently. 0 is convenient because a single bitwise-and
between the index vector and the condition will set lanes that do not
contain a match to 0.
Jakub Jelinek <ja...@redhat.com> writes:
> First of all, I fail to see why we don't handle negative step,
> that can be done with REDUC_MIN instead of REDUC_MAX.
That would not work without first using values different from 0 to
indicate the absence of matches (except in cases where all indices are
negative), which I assume is why the test was there in the first place.
Below is the patch with fixed formatting and changes to make it apply
cleanly to r255537 (as far as I can tell this was simply caused by some
variables and constants having been renamed).
2017-11-21 Kilian Verhetsel <kilian.verhet...@uclouvain.be>
gcc/ChangeLog:
PR testsuite/81179
* tree-vect-loop.c (vect_create_epilog_for_reduction): Fix the
returned value for INTEGER_INDUC_COND_REDUCTION whose last match
occurred at index 0.
(vectorizable_reduction): For
INTEGER_INDUC_COND_REDUCTION, pass the PHI statement that sets
the induction variable to the code generating the epilogue and
check that no overflow will occur.
gcc/testsuite/ChangeLog:
* gcc.dg/vect/vect-iv-cond-reduc-overflow-1.c: New test for
overflows when compiling conditional reductions.
* gcc.dg/vect/vect-iv-cond-reduc-overflow-2.c: Likewise.
Index: gcc/testsuite/gcc.dg/vect/vect-iv-cond-reduc-overflow-1.c
===================================================================
--- gcc/testsuite/gcc.dg/vect/vect-iv-cond-reduc-overflow-1.c (nonexistent)
+++ gcc/testsuite/gcc.dg/vect/vect-iv-cond-reduc-overflow-1.c (working copy)
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_condition } */
+
+#include "tree-vect.h"
+#include <limits.h>
+
+extern void abort (void) __attribute__ ((noreturn));
+
+#define N UINT_MAX
+
+/* Condition reduction with maximum possible loop size. Will fail to vectorize
+ because values in the index vector will overflow. */
+unsigned int
+condition_reduction (unsigned int *a, unsigned int min_v)
+{
+ unsigned int last = -72;
+
+ for (unsigned int i = 0; i < N; i++)
+ if (a[i] < min_v)
+ last = i;
+
+ return last;
+}
+
+/* { dg-final { scan-tree-dump-not "LOOP VECTORIZED" "vect" } } */
+/* { dg-final { scan-tree-dump "condition expression based on integer induction." "vect" } } */
+/* { dg-final { scan-tree-dump "loop size is greater than data size" "vect" } } */
Index: gcc/testsuite/gcc.dg/vect/vect-iv-cond-reduc-overflow-2.c
===================================================================
--- gcc/testsuite/gcc.dg/vect/vect-iv-cond-reduc-overflow-2.c (nonexistent)
+++ gcc/testsuite/gcc.dg/vect/vect-iv-cond-reduc-overflow-2.c (working copy)
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_condition } */
+
+#include "tree-vect.h"
+#include <limits.h>
+
+extern void abort (void) __attribute__ ((noreturn));
+
+#define N (UINT_MAX - 1)
+
+/* Condition reduction with maximum possible loop size, minus one. This should
+ still be vectorized correctly. */
+unsigned int
+condition_reduction (unsigned int *a, unsigned int min_v)
+{
+ unsigned int last = -72;
+
+ for (unsigned int i = 0; i < N; i++)
+ if (a[i] < min_v)
+ last = i;
+
+ return last;
+}
+
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
+/* { dg-final { scan-tree-dump "condition expression based on integer induction." "vect" } } */
Index: gcc/tree-vect-loop.c
===================================================================
--- gcc/tree-vect-loop.c (revision 255537)
+++ gcc/tree-vect-loop.c (working copy)
@@ -4325,7 +4325,7 @@ get_initial_defs_for_reduction (slp_tree slp_node,
static void
vect_create_epilog_for_reduction (vec<tree> vect_defs, gimple *stmt,
- gimple *reduc_def_stmt,
+ gimple *reduc_def_stmt, gimple *induct_stmt,
int ncopies, internal_fn reduc_fn,
vec<gimple *> reduction_phis,
bool double_reduc,
@@ -4486,7 +4486,9 @@ vect_create_epilog_for_reduction (vec<tree> vect_d
The first match will be a 1 to allow 0 to be used for non-matching
indexes. If there are no matches at all then the vector will be all
zeroes. */
- if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
+ if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION
+ || (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
+ == INTEGER_INDUC_COND_REDUCTION))
{
tree indx_before_incr, indx_after_incr;
int nunits_out = TYPE_VECTOR_SUBPARTS (vectype);
@@ -4763,7 +4765,9 @@ vect_create_epilog_for_reduction (vec<tree> vect_d
else
new_phi_result = PHI_RESULT (new_phis[0]);
- if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION
+ if ((STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION
+ || (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
+ == INTEGER_INDUC_COND_REDUCTION))
&& reduc_fn != IFN_LAST)
{
/* For condition reductions, we have a vector (NEW_PHI_RESULT) containing
@@ -4788,18 +4792,6 @@ vect_create_epilog_for_reduction (vec<tree> vect_d
tree vectype_unsigned = build_vector_type
(scalar_type_unsigned, TYPE_VECTOR_SUBPARTS (vectype));
- /* First we need to create a vector (ZERO_VEC) of zeros and another
- vector (MAX_INDEX_VEC) filled with the last matching index, which we
- can create using a MAX reduction and then expanding.
- In the case where the loop never made any matches, the max index will
- be zero. */
-
- /* Vector of {0, 0, 0,...}. */
- tree zero_vec = make_ssa_name (vectype);
- tree zero_vec_rhs = build_zero_cst (vectype);
- gimple *zero_vec_stmt = gimple_build_assign (zero_vec, zero_vec_rhs);
- gsi_insert_before (&exit_gsi, zero_vec_stmt, GSI_SAME_STMT);
-
/* Find maximum value from the vector of found indexes. */
tree max_index = make_ssa_name (index_scalar_type);
gcall *max_index_stmt = gimple_build_call_internal (IFN_REDUC_MAX,
@@ -4815,65 +4807,114 @@ vect_create_epilog_for_reduction (vec<tree> vect_d
max_index_vec_rhs);
gsi_insert_before (&exit_gsi, max_index_vec_stmt, GSI_SAME_STMT);
- /* Next we compare the new vector (MAX_INDEX_VEC) full of max indexes
- with the vector (INDUCTION_INDEX) of found indexes, choosing values
- from the data vector (NEW_PHI_RESULT) for matches, 0 (ZERO_VEC)
- otherwise. Only one value should match, resulting in a vector
- (VEC_COND) with one data value and the rest zeros.
- In the case where the loop never made any matches, every index will
- match, resulting in a vector with all data values (which will all be
- the default value). */
+ if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
+ {
+ /* Next we compare the new vector (MAX_INDEX_VEC) full of max indexes
+ with the vector (INDUCTION_INDEX) of found indexes, choosing values
+ from the data vector (NEW_PHI_RESULT) for matches, 0 (ZERO_VEC)
+ otherwise. Only one value should match, resulting in a vector
+ (VEC_COND) with one data value and the rest zeros. In the case
+ where the loop never made any matches, every index will match,
+ resulting in a vector with all data values (which will all be the
+ default value). */
- /* Compare the max index vector to the vector of found indexes to find
- the position of the max value. */
- tree vec_compare = make_ssa_name (index_vec_cmp_type);
- gimple *vec_compare_stmt = gimple_build_assign (vec_compare, EQ_EXPR,
- induction_index,
- max_index_vec);
- gsi_insert_before (&exit_gsi, vec_compare_stmt, GSI_SAME_STMT);
+ /* Vector of {0, 0, 0,...}. */
+ tree zero_vec = make_ssa_name (vectype);
+ tree zero_vec_rhs = build_zero_cst (vectype);
+ gimple *zero_vec_stmt = gimple_build_assign (zero_vec, zero_vec_rhs);
+ gsi_insert_before (&exit_gsi, zero_vec_stmt, GSI_SAME_STMT);
- /* Use the compare to choose either values from the data vector or
- zero. */
- tree vec_cond = make_ssa_name (vectype);
- gimple *vec_cond_stmt = gimple_build_assign (vec_cond, VEC_COND_EXPR,
- vec_compare, new_phi_result,
- zero_vec);
- gsi_insert_before (&exit_gsi, vec_cond_stmt, GSI_SAME_STMT);
+ /* Compare the max index vector to the vector of found indexes to find
+ the position of the max value. */
+ tree vec_compare = make_ssa_name (index_vec_cmp_type);
+ gimple *vec_compare_stmt = gimple_build_assign (vec_compare, EQ_EXPR,
+ induction_index,
+ max_index_vec);
+ gsi_insert_before (&exit_gsi, vec_compare_stmt, GSI_SAME_STMT);
- /* Finally we need to extract the data value from the vector (VEC_COND)
- into a scalar (MATCHED_DATA_REDUC). Logically we want to do a OR
- reduction, but because this doesn't exist, we can use a MAX reduction
- instead. The data value might be signed or a float so we need to cast
- it first.
- In the case where the loop never made any matches, the data values are
- all identical, and so will reduce down correctly. */
+ /* Use the compare to choose either values from the data vector or
+ zero. */
+ tree vec_cond = make_ssa_name (vectype);
+ gimple *vec_cond_stmt = gimple_build_assign (vec_cond, VEC_COND_EXPR,
+ vec_compare,
+ new_phi_result,
+ zero_vec);
+ gsi_insert_before (&exit_gsi, vec_cond_stmt, GSI_SAME_STMT);
- /* Make the matched data values unsigned. */
- tree vec_cond_cast = make_ssa_name (vectype_unsigned);
- tree vec_cond_cast_rhs = build1 (VIEW_CONVERT_EXPR, vectype_unsigned,
- vec_cond);
- gimple *vec_cond_cast_stmt = gimple_build_assign (vec_cond_cast,
- VIEW_CONVERT_EXPR,
- vec_cond_cast_rhs);
- gsi_insert_before (&exit_gsi, vec_cond_cast_stmt, GSI_SAME_STMT);
+ /* Finally we need to extract the data value from the vector
+ (VEC_COND) into a scalar (MATCHED_DATA_REDUC). Logically we want
+ to do a OR reduction, but because this doesn't exist, we can use a
+ MAX reduction instead. The data value might be signed or a float
+ so we need to cast it first. In the case where the loop never made
+ any matches, the data values are all identical, and so will reduce
+ down correctly. */
- /* Reduce down to a scalar value. */
- tree data_reduc = make_ssa_name (scalar_type_unsigned);
- gcall *data_reduc_stmt = gimple_build_call_internal (IFN_REDUC_MAX,
- 1, vec_cond_cast);
- gimple_call_set_lhs (data_reduc_stmt, data_reduc);
- gsi_insert_before (&exit_gsi, data_reduc_stmt, GSI_SAME_STMT);
+ /* Make the matched data values unsigned. */
+ tree vec_cond_cast = make_ssa_name (vectype_unsigned);
+ tree vec_cond_cast_rhs = build1 (VIEW_CONVERT_EXPR, vectype_unsigned,
+ vec_cond);
+ gimple *vec_cond_cast_stmt = gimple_build_assign (vec_cond_cast,
+ VIEW_CONVERT_EXPR,
+ vec_cond_cast_rhs);
+ gsi_insert_before (&exit_gsi, vec_cond_cast_stmt, GSI_SAME_STMT);
- /* Convert the reduced value back to the result type and set as the
- result. */
- gimple_seq stmts = NULL;
- new_temp = gimple_build (&stmts, VIEW_CONVERT_EXPR, scalar_type,
- data_reduc);
- gsi_insert_seq_before (&exit_gsi, stmts, GSI_SAME_STMT);
+ /* Reduce down to a scalar value. */
+ tree data_reduc = make_ssa_name (scalar_type_unsigned);
+ gcall *data_reduc_stmt = gimple_build_call_internal (IFN_REDUC_MAX,
+ 1,
+ vec_cond_cast);
+ gimple_call_set_lhs (data_reduc_stmt, data_reduc);
+ gsi_insert_before (&exit_gsi, data_reduc_stmt, GSI_SAME_STMT);
+
+ /* Convert the reduced value back to the result type and set as the
+ result. */
+ gimple_seq stmts = NULL;
+ new_temp = gimple_build (&stmts, VIEW_CONVERT_EXPR, scalar_type,
+ data_reduc);
+ gsi_insert_seq_before (&exit_gsi, stmts, GSI_SAME_STMT);
+ }
+ else
+ {
+ /* Retrieve the index of the last match, and adjust the result value
+ if there were no matches. */
+ gimple_seq stmts = NULL;
+
+ stmt_vec_info induct_stmt_info = vinfo_for_stmt (induct_stmt);
+
+ tree base = PHI_ARG_DEF_FROM_EDGE (induct_stmt,
+ loop_preheader_edge (loop));
+ tree step = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (induct_stmt_info);
+
+ tree one = build_one_cst (TREE_TYPE (max_index));
+ tree index = gimple_build (&stmts, MINUS_EXPR, TREE_TYPE (max_index),
+ max_index, one);
+
+ index = gimple_convert (&stmts, scalar_type, index);
+
+ tree offset = gimple_build (&stmts, MULT_EXPR, scalar_type,
+ step, index);
+ tree result = gimple_build (&stmts, PLUS_EXPR, scalar_type,
+ base, offset);
+
+ tree zero = build_zero_cst (TREE_TYPE (max_index));
+ tree zcompare = build2 (EQ_EXPR, boolean_type_node,
+ max_index, zero);
+
+ gsi_insert_seq_before (&exit_gsi, stmts, GSI_SAME_STMT);
+
+ new_temp = make_ssa_name (new_scalar_dest);
+ epilog_stmt = gimple_build_assign (new_temp, COND_EXPR, zcompare,
+ initial_def, result);
+
+ gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
+ }
+
scalar_results.safe_push (new_temp);
}
- else if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION
- && reduc_fn == IFN_LAST)
+ else if ((STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION
+ || (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
+ == INTEGER_INDUC_COND_REDUCTION))
+ && reduc_fn == IFN_LAST)ยป
{
/* Condition reduction without supported IFN_REDUC_MAX. Generate
idx = 0;
@@ -4913,8 +4954,12 @@ vect_create_epilog_for_reduction (vec<tree> vect_d
{
tree new_idx_val = idx_val;
tree new_val = val;
- if (off != v_size - el_size)
+ if (off != v_size - el_size
+ || (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
+ == INTEGER_INDUC_COND_REDUCTION))
{
+ /* For integer induction, the index of the last match
+ must always be known. */
new_idx_val = make_ssa_name (idx_eltype);
epilog_stmt = gimple_build_assign (new_idx_val,
MAX_EXPR, idx_val,
@@ -4934,12 +4979,52 @@ vect_create_epilog_for_reduction (vec<tree> vect_d
val = new_val;
}
}
- /* Convert the reduced value back to the result type and set as the
- result. */
+
gimple_seq stmts = NULL;
- val = gimple_convert (&stmts, scalar_type, val);
- gsi_insert_seq_before (&exit_gsi, stmts, GSI_SAME_STMT);
- scalar_results.safe_push (val);
+
+ if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
+ {
+ /* Convert the reduced value back to the result type and set as the
+ result. */
+ val = gimple_convert (&stmts, scalar_type, val);
+ gsi_insert_seq_before (&exit_gsi, stmts, GSI_SAME_STMT);
+ scalar_results.safe_push (val);
+ }
+ else if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
+ == INTEGER_INDUC_COND_REDUCTION)
+ {
+ /* Retrieve the index of the last match, and adjust the result value
+ if there were no matches. */
+ stmt_vec_info induct_stmt_info = vinfo_for_stmt (induct_stmt);
+
+ tree base = PHI_ARG_DEF_FROM_EDGE (induct_stmt,
+ loop_preheader_edge (loop));
+ tree step = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (induct_stmt_info);
+
+ tree one = build_one_cst (idx_eltype);
+ tree index = gimple_build (&stmts, MINUS_EXPR, idx_eltype,
+ idx_val, one);
+
+ index = gimple_convert (&stmts, scalar_type, index);
+
+ tree offset = gimple_build (&stmts, MULT_EXPR, scalar_type,
+ step, index);
+ tree result = gimple_build (&stmts, PLUS_EXPR, scalar_type,
+ base, offset);
+
+ gsi_insert_seq_before (&exit_gsi, stmts, GSI_SAME_STMT);
+
+ tree zero = build_zero_cst (TREE_TYPE (idx_val));
+ tree zcompare = build2 (EQ_EXPR, boolean_type_node,
+ idx_val, zero);
+
+ new_temp = make_ssa_name (new_scalar_dest);
+ epilog_stmt = gimple_build_assign (new_temp, COND_EXPR, zcompare,
+ initial_def, result);
+ gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
+
+ scalar_results.safe_push (new_temp);
+ }
}
/* 2.3 Create the reduction code, using one of the three schemes described
@@ -5637,6 +5722,7 @@ vectorizable_reduction (gimple *stmt, gimple_stmt_
bool first_p = true;
tree cr_index_scalar_type = NULL_TREE, cr_index_vector_type = NULL_TREE;
tree cond_reduc_val = NULL_TREE;
+ gimple *induct_stmt = NULL;
/* Make sure it was already recognized as a reduction computation. */
if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt)) != vect_reduction_def
@@ -5881,7 +5967,10 @@ vectorizable_reduction (gimple *stmt, gimple_stmt_
}
if (dt == vect_induction_def && def_stmt != NULL
&& is_nonwrapping_integer_induction (def_stmt, loop))
- cond_reduc_dt = dt;
+ {
+ cond_reduc_dt = dt;
+ induct_stmt = def_stmt;
+ }
}
}
@@ -6149,7 +6238,9 @@ vectorizable_reduction (gimple *stmt, gimple_stmt_
reduc_fn = IFN_LAST;
- if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) != COND_REDUCTION)
+ if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) != COND_REDUCTION
+ && (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
+ != INTEGER_INDUC_COND_REDUCTION))
{
if (reduction_fn_for_scalar_code (orig_code, &reduc_fn))
{
@@ -6220,7 +6311,9 @@ vectorizable_reduction (gimple *stmt, gimple_stmt_
}
}
- if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
+ if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION
+ || (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
+ == INTEGER_INDUC_COND_REDUCTION))
{
widest_int ni;
@@ -6463,8 +6556,9 @@ vectorizable_reduction (gimple *stmt, gimple_stmt_
vect_defs[0] = gimple_assign_lhs (*vec_stmt);
vect_create_epilog_for_reduction (vect_defs, stmt, reduc_def_stmt,
- epilog_copies, reduc_fn, phis,
- double_reduc, slp_node, slp_node_instance);
+ induct_stmt, epilog_copies, reduc_fn,
+ phis, double_reduc, slp_node,
+ slp_node_instance);
return true;
}
