Thank you both for your comments.
I have added the check to ensure the index vector won't cause an
overflow. I also added tests to the testsuite in order to check that the
loop is vectorized for UINT_MAX - 1 iterations but not UINT_MAX
iterations. I was not able to write code that triggers
INTEGER_INDUC_COND_REDUCTION when using char or other smaller types
(changing the types of last, min_v and a to something else causes
COND_REDUCTION to be used instead), so these tests are only compiled and
not executed.
I also moved an instruction that generates a vector of zeroes (used for
COND_REDUCTION) in the branch of code run only for COND_REDUCTION, this
should remove the unused vector that Alan noticed.
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 254996)
+++ gcc/tree-vect-loop.c (working copy)
@@ -4316,7 +4316,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, enum tree_code reduc_code,
vec<gimple *> reduction_phis,
bool double_reduc,
@@ -4477,7 +4477,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);
@@ -4754,7 +4756,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_code != ERROR_MARK)
{
/* For condition reductions, we have a vector (NEW_PHI_RESULT) containing
@@ -4779,18 +4783,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);
gimple *max_index_stmt = gimple_build_assign (max_index, REDUC_MAX_EXPR,
@@ -4797,76 +4789,130 @@ vect_create_epilog_for_reduction (vec<tree> vect_d
induction_index);
gsi_insert_before (&exit_gsi, max_index_stmt, GSI_SAME_STMT);
- /* Vector of {max_index, max_index, max_index,...}. */
- tree max_index_vec = make_ssa_name (index_vec_type);
- tree max_index_vec_rhs = build_vector_from_val (index_vec_type,
- max_index);
- gimple *max_index_vec_stmt = gimple_build_assign (max_index_vec,
- max_index_vec_rhs);
- gsi_insert_before (&exit_gsi, max_index_vec_stmt, GSI_SAME_STMT);
+ if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
+ {
+ /* 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. */
- /* 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). */
+ /* 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);
- /* 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 {max_index, max_index, max_index,...}. */
+ tree max_index_vec = make_ssa_name (index_vec_type);
+ tree max_index_vec_rhs = build_vector_from_val (index_vec_type,
+ max_index);
+ gimple *max_index_vec_stmt = gimple_build_assign (max_index_vec,
+ max_index_vec_rhs);
+ gsi_insert_before (&exit_gsi, max_index_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);
+ /* 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). */
- /* 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. */
+ /* 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);
- /* 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);
+ /* 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);
- /* Reduce down to a scalar value. */
- tree data_reduc = make_ssa_name (scalar_type_unsigned);
- optab ot = optab_for_tree_code (REDUC_MAX_EXPR, vectype_unsigned,
- optab_default);
- gcc_assert (optab_handler (ot, TYPE_MODE (vectype_unsigned))
- != CODE_FOR_nothing);
- gimple *data_reduc_stmt = gimple_build_assign (data_reduc,
- REDUC_MAX_EXPR,
- vec_cond_cast);
- gsi_insert_before (&exit_gsi, data_reduc_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. */
- /* 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);
+ /* 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);
+
+ /* Reduce down to a scalar value. */
+ tree data_reduc = make_ssa_name (scalar_type_unsigned);
+ optab ot = optab_for_tree_code (REDUC_MAX_EXPR, vectype_unsigned,
+ optab_default);
+ gcc_assert (optab_handler (ot, TYPE_MODE (vectype_unsigned))
+ != CODE_FOR_nothing);
+ gimple *data_reduc_stmt = gimple_build_assign (data_reduc,
+ REDUC_MAX_EXPR,
+ vec_cond_cast);
+ 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
+ else if ((STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION
+ || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
+ == INTEGER_INDUC_COND_REDUCTION)
&& reduc_code == ERROR_MARK)
{
/* Condition redution without supported REDUC_MAX_EXPR. Generate
@@ -4907,8 +4953,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,
@@ -4928,12 +4978,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
@@ -5625,6 +5715,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
@@ -5869,7 +5960,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;
+ }
}
}
@@ -6137,7 +6231,9 @@ vectorizable_reduction (gimple *stmt, gimple_stmt_
epilog_reduc_code = ERROR_MARK;
- 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_code_for_scalar_code (orig_code, &epilog_reduc_code))
{
@@ -6218,7 +6314,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;
@@ -6232,7 +6330,6 @@ vectorizable_reduction (gimple *stmt, gimple_stmt_
}
/* Convert backedges to iterations. */
ni += 1;
-
/* The additional index will be the same type as the condition. Check
that the loop can fit into this less one (because we'll use up the
zero slot for when there are no matches). */
@@ -6461,7 +6558,7 @@ 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,
+ induct_stmt, epilog_copies,
epilog_reduc_code, phis,
double_reduc, slp_node, slp_node_instance);
