if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
- /* First - identify all inductions. */
+ /* First - identify all inductions. Reduction detection assumes that all the
+ inductions have been identified, therefore, this order must not be
+ changed. */
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple phi = gsi_stmt (gsi);
}
- /* Second - identify all reductions. */
+ /* Second - identify all reductions and nested cycles. */
while (VEC_length (gimple, worklist) > 0)
{
gimple phi = VEC_pop (gimple, worklist);
tree def = PHI_RESULT (phi);
stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
gimple reduc_stmt;
+ bool nested_cycle;
if (vect_print_dump_info (REPORT_DETAILS))
{
gcc_assert (is_gimple_reg (SSA_NAME_VAR (def)));
gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
- reduc_stmt = vect_is_simple_reduction (loop_vinfo, phi);
+ nested_cycle = (loop != LOOP_VINFO_LOOP (loop_vinfo));
+ reduc_stmt = vect_is_simple_reduction (loop_vinfo, phi, !nested_cycle);
if (reduc_stmt)
{
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "Detected reduction.");
- STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
- STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
+ if (nested_cycle)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "Detected vectorizable nested cycle.");
+
+ STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_nested_cycle;
+ STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
+ vect_nested_cycle;
+ }
+ else
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "Detected reduction.");
+
+ STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
+ STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
vect_reduction_def;
+ }
}
else
if (vect_print_dump_info (REPORT_DETAILS))
}
VEC_free (gimple, heap, worklist);
- return;
}
such that:
1. operation is commutative and associative and it is safe to
- change the order of the computation.
+ change the order of the computation (if CHECK_REDUCTION is true)
2. no uses for a2 in the loop (a2 is used out of the loop)
3. no uses of a1 in the loop besides the reduction operation.
Condition 1 is tested here.
- Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized. */
+ Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
+
+ Also detect a cross-iteration def-use cycle in nested loops, i.e., nested
+ cycles, if CHECK_REDUCTION is false. */
gimple
-vect_is_simple_reduction (loop_vec_info loop_info, gimple phi)
+vect_is_simple_reduction (loop_vec_info loop_info, gimple phi,
+ bool check_reduction)
{
struct loop *loop = (gimple_bb (phi))->loop_father;
struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
imm_use_iterator imm_iter;
use_operand_p use_p;
- gcc_assert (loop == vect_loop || flow_loop_nested_p (vect_loop, loop));
+ /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
+ otherwise, we assume outer loop vectorization. */
+ gcc_assert ((check_reduction && loop == vect_loop)
+ || (!check_reduction && flow_loop_nested_p (vect_loop, loop)));
name = PHI_RESULT (phi);
nloop_uses = 0;
code = gimple_assign_rhs_code (def_stmt);
- if (!commutative_tree_code (code) || !associative_tree_code (code))
+ if (check_reduction
+ && (!commutative_tree_code (code) || !associative_tree_code (code)))
{
if (vect_print_dump_info (REPORT_DETAILS))
report_vect_op (def_stmt, "reduction: not commutative/associative: ");
return NULL;
}
- /* Check that it's ok to change the order of the computation. */
type = TREE_TYPE (gimple_assign_lhs (def_stmt));
if (TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op1))
|| TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op2)))
return NULL;
}
- /* Generally, when vectorizing a reduction we change the order of the
+ /* Check that it's ok to change the order of the computation.
+ Generally, when vectorizing a reduction we change the order of the
computation. This may change the behavior of the program in some
cases, so we need to check that this is ok. One exception is when
vectorizing an outer-loop: the inner-loop is executed sequentially,
/* CHECKME: check for !flag_finite_math_only too? */
if (SCALAR_FLOAT_TYPE_P (type) && !flag_associative_math
- && !nested_in_vect_loop_p (vect_loop, def_stmt))
+ && check_reduction)
{
/* Changing the order of operations changes the semantics. */
if (vect_print_dump_info (REPORT_DETAILS))
return NULL;
}
else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type)
- && !nested_in_vect_loop_p (vect_loop, def_stmt))
+ && check_reduction)
{
/* Changing the order of operations changes the semantics. */
if (vect_print_dump_info (REPORT_DETAILS))
report_vect_op (def_stmt, "reduction: unsafe int math optimization: ");
return NULL;
}
- else if (SAT_FIXED_POINT_TYPE_P (type))
+ else if (SAT_FIXED_POINT_TYPE_P (type) && check_reduction)
{
/* Changing the order of operations changes the semantics. */
if (vect_print_dump_info (REPORT_DETAILS))
return NULL;
}
- /* reduction is safe. we're dealing with one of the following:
+ /* Reduction is safe. We're dealing with one of the following:
1) integer arithmetic and no trapv
- 2) floating point arithmetic, and special flags permit this optimization.
- */
+ 2) floating point arithmetic, and special flags permit this optimization
+ 3) nested cycle (i.e., outer loop vectorization). */
def1 = SSA_NAME_DEF_STMT (op1);
def2 = SSA_NAME_DEF_STMT (op2);
if (!def1 || !def2 || gimple_nop_p (def1) || gimple_nop_p (def2))
&& (is_gimple_assign (def1)
|| STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1)) == vect_induction_def
|| (gimple_code (def1) == GIMPLE_PHI
- && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1)) == vect_internal_def
+ && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
+ == vect_internal_def
&& !is_loop_header_bb_p (gimple_bb (def1)))))
{
if (vect_print_dump_info (REPORT_DETAILS))
- report_vect_op (def_stmt, "detected reduction:");
+ report_vect_op (def_stmt, "detected reduction: ");
return def_stmt;
}
else if (def1 == phi
&& flow_bb_inside_loop_p (loop, gimple_bb (def2))
&& (is_gimple_assign (def2)
- || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2)) == vect_induction_def
+ || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
+ == vect_induction_def
|| (gimple_code (def2) == GIMPLE_PHI
- && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2)) == vect_internal_def
+ && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
+ == vect_internal_def
&& !is_loop_header_bb_p (gimple_bb (def2)))))
{
- /* Swap operands (just for simplicity - so that the rest of the code
- can assume that the reduction variable is always the last (second)
- argument). */
- if (vect_print_dump_info (REPORT_DETAILS))
- report_vect_op (def_stmt ,
- "detected reduction: need to swap operands:");
- swap_tree_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
- gimple_assign_rhs2_ptr (def_stmt));
+ if (check_reduction)
+ {
+ /* Swap operands (just for simplicity - so that the rest of the code
+ can assume that the reduction variable is always the last (second)
+ argument). */
+ if (vect_print_dump_info (REPORT_DETAILS))
+ report_vect_op (def_stmt,
+ "detected reduction: need to swap operands: ");
+
+ swap_tree_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
+ gimple_assign_rhs2_ptr (def_stmt));
+ }
+ else
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ report_vect_op (def_stmt, "detected reduction: ");
+ }
+
return def_stmt;
}
else
{
if (vect_print_dump_info (REPORT_DETAILS))
- report_vect_op (def_stmt, "reduction: unknown pattern.");
+ report_vect_op (def_stmt, "reduction: unknown pattern: ");
+
return NULL;
}
}
case WIDEN_SUM_EXPR:
case DOT_PROD_EXPR:
case PLUS_EXPR:
+ case MINUS_EXPR:
if (nested_in_vect_loop)
*adjustment_def = vect_get_vec_def_for_operand (init_val, stmt, NULL);
else
in vectorizable_operation.
STMT is the scalar reduction stmt that is being vectorized.
REDUCTION_PHI is the phi-node that carries the reduction computation.
+ REDUC_INDEX is the index of the operand in the right hand side of the
+ statement that is defined by REDUCTION_PHI.
This function:
1. Creates the reduction def-use cycle: sets the arguments for
vect_create_epilog_for_reduction (tree vect_def, gimple stmt,
int ncopies,
enum tree_code reduc_code,
- gimple reduction_phi)
+ gimple reduction_phi,
+ int reduc_index)
{
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
stmt_vec_info prev_phi_info;
switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
{
case GIMPLE_SINGLE_RHS:
- gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt)) == ternary_op);
- reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2);
+ gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt))
+ == ternary_op);
+ reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), reduc_index);
break;
case GIMPLE_UNARY_RHS:
reduction_op = gimple_assign_rhs1 (stmt);
break;
case GIMPLE_BINARY_RHS:
- reduction_op = gimple_assign_rhs2 (stmt);
+ reduction_op = reduc_index ?
+ gimple_assign_rhs2 (stmt) : gimple_assign_rhs1 (stmt);
break;
default:
gcc_unreachable ();
SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, def);
prev_phi_info = vinfo_for_stmt (phi);
}
+
exit_gsi = gsi_after_labels (exit_bb);
/* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
}
+
code = gimple_assign_rhs_code (orig_stmt);
scalar_dest = gimple_assign_lhs (orig_stmt);
scalar_type = TREE_TYPE (scalar_dest);
{
if (nested_in_vect_loop)
{
+ /* For MINUS_EXPR we create new_temp = loop_exit_def + adjustment_def
+ since the initial value is [0,0,...,0]. */
+ if (code == MINUS_EXPR)
+ code = PLUS_EXPR;
+
gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) == VECTOR_TYPE);
expr = build2 (code, vectype, PHI_RESULT (new_phi), adjustment_def);
new_dest = vect_create_destination_var (scalar_dest, vectype);
expr = build2 (code, scalar_type, new_temp, adjustment_def);
new_dest = vect_create_destination_var (scalar_dest, scalar_type);
}
+
epilog_stmt = gimple_build_assign (new_dest, expr);
new_temp = make_ssa_name (new_dest, epilog_stmt);
gimple_assign_set_lhs (epilog_stmt, new_temp);
Check if STMT performs a reduction operation that can be vectorized.
If VEC_STMT is also passed, vectorize the STMT: create a vectorized
- stmt to replace it, put it in VEC_STMT, and insert it at BSI.
+ stmt to replace it, put it in VEC_STMT, and insert it at GSI.
Return FALSE if not a vectorizable STMT, TRUE otherwise.
This function also handles reduction idioms (patterns) that have been
gimple new_stmt = NULL;
int j;
tree ops[3];
+ bool nested_cycle = false, found_nested_cycle_def = false;
+ gimple reduc_def_stmt = NULL;
+ /* The default is that the reduction variable is the last in statement. */
+ int reduc_index = 2;
if (nested_in_vect_loop_p (loop, stmt))
- loop = loop->inner;
+ {
+ loop = loop->inner;
+ nested_cycle = true;
+ }
gcc_assert (ncopies >= 1);
return false;
/* Make sure it was already recognized as a reduction computation. */
- if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def)
+ if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def
+ && STMT_VINFO_DEF_TYPE (stmt_info) != vect_nested_cycle)
return false;
/* 2. Has this been recognized as a reduction pattern?
return false;
/* All uses but the last are expected to be defined in the loop.
- The last use is the reduction variable. */
+ The last use is the reduction variable. In case of nested cycle this
+ assumption is not true: we use reduc_index to record the index of the
+ reduction variable. */
for (i = 0; i < op_type-1; i++)
{
is_simple_use = vect_is_simple_use (ops[i], loop_vinfo, NULL, &def_stmt,
if (dt != vect_internal_def
&& dt != vect_external_def
&& dt != vect_constant_def
- && dt != vect_induction_def)
+ && dt != vect_induction_def
+ && dt != vect_nested_cycle)
return false;
+
+ if (dt == vect_nested_cycle)
+ {
+ found_nested_cycle_def = true;
+ reduc_def_stmt = def_stmt;
+ reduc_index = i;
+ }
}
is_simple_use = vect_is_simple_use (ops[i], loop_vinfo, NULL, &def_stmt,
&def, &dt);
gcc_assert (is_simple_use);
- gcc_assert (dt == vect_reduction_def);
- gcc_assert (gimple_code (def_stmt) == GIMPLE_PHI);
+ gcc_assert (dt == vect_reduction_def
+ || dt == vect_nested_cycle
+ || ((dt == vect_internal_def || dt == vect_external_def
+ || dt == vect_constant_def || dt == vect_induction_def)
+ && nested_cycle && found_nested_cycle_def));
+ if (!found_nested_cycle_def)
+ reduc_def_stmt = def_stmt;
+
+ gcc_assert (gimple_code (reduc_def_stmt) == GIMPLE_PHI);
if (orig_stmt)
- gcc_assert (orig_stmt == vect_is_simple_reduction (loop_vinfo, def_stmt));
+ gcc_assert (orig_stmt == vect_is_simple_reduction (loop_vinfo,
+ reduc_def_stmt,
+ !nested_cycle));
else
- gcc_assert (stmt == vect_is_simple_reduction (loop_vinfo, def_stmt));
+ gcc_assert (stmt == vect_is_simple_reduction (loop_vinfo, reduc_def_stmt,
+ !nested_cycle));
- if (STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt)))
+ if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt)))
return false;
/* 4. Supportable by target? */
orig_code = code;
}
- if (!reduction_code_for_scalar_code (orig_code, &epilog_reduc_code))
- return false;
+ if (nested_cycle)
+ epilog_reduc_code = orig_code;
+ else
+ if (!reduction_code_for_scalar_code (orig_code, &epilog_reduc_code))
+ return false;
+
reduc_optab = optab_for_tree_code (epilog_reduc_code, vectype, optab_default);
if (!reduc_optab)
{
/* Handle uses. */
if (j == 0)
{
- loop_vec_def0 = vect_get_vec_def_for_operand (ops[0], stmt, NULL);
+ loop_vec_def0 = vect_get_vec_def_for_operand (ops[!reduc_index],
+ stmt, NULL);
if (op_type == ternary_op)
{
- loop_vec_def1 = vect_get_vec_def_for_operand (ops[1], stmt, NULL);
+ if (reduc_index == 0)
+ loop_vec_def1 = vect_get_vec_def_for_operand (ops[2], stmt,
+ NULL);
+ else
+ loop_vec_def1 = vect_get_vec_def_for_operand (ops[1], stmt,
+ NULL);
}
- /* Get the vector def for the reduction variable from the phi node */
+ /* Get the vector def for the reduction variable from the phi
+ node. */
reduc_def = PHI_RESULT (new_phi);
first_phi = new_phi;
}
STMT_VINFO_RELATED_STMT (prev_phi_info) = new_phi;
}
+
/* Arguments are ready. create the new vector stmt. */
if (op_type == binary_op)
- expr = build2 (code, vectype, loop_vec_def0, reduc_def);
+ {
+ if (reduc_index == 0)
+ expr = build2 (code, vectype, reduc_def, loop_vec_def0);
+ else
+ expr = build2 (code, vectype, loop_vec_def0, reduc_def);
+ }
else
- expr = build3 (code, vectype, loop_vec_def0, loop_vec_def1,
- reduc_def);
+ {
+ if (reduc_index == 0)
+ expr = build3 (code, vectype, reduc_def, loop_vec_def0,
+ loop_vec_def1);
+ else
+ {
+ if (reduc_index == 1)
+ expr = build3 (code, vectype, loop_vec_def0, reduc_def,
+ loop_vec_def1);
+ else
+ expr = build3 (code, vectype, loop_vec_def0, loop_vec_def1,
+ reduc_def);
+ }
+ }
+
new_stmt = gimple_build_assign (vec_dest, expr);
new_temp = make_ssa_name (vec_dest, new_stmt);
gimple_assign_set_lhs (new_stmt, new_temp);
if (!single_defuse_cycle)
new_temp = gimple_assign_lhs (*vec_stmt);
vect_create_epilog_for_reduction (new_temp, stmt, epilog_copies,
- epilog_reduc_code, first_phi);
+ epilog_reduc_code, first_phi, reduc_index);
return true;
}
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "outer-loop def-stmt defining inner-loop stmt.");
+
switch (relevant)
{
case vect_unused_in_scope:
- relevant = (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def) ?
- vect_used_by_reduction : vect_unused_in_scope;
+ relevant = (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_nested_cycle) ?
+ vect_used_in_scope : vect_unused_in_scope;
break;
+
case vect_used_in_outer_by_reduction:
+ gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def);
relevant = vect_used_by_reduction;
break;
+
case vect_used_in_outer:
+ gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def);
relevant = vect_used_in_scope;
break;
- case vect_used_by_reduction:
+
case vect_used_in_scope:
break;
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "inner-loop def-stmt defining outer-loop stmt.");
+
switch (relevant)
{
case vect_unused_in_scope:
vect_used_in_outer_by_reduction : vect_unused_in_scope;
break;
- case vect_used_in_outer_by_reduction:
- case vect_used_in_outer:
- break;
-
case vect_used_by_reduction:
relevant = vect_used_in_outer_by_reduction;
break;
those that are used by a reduction computation, and those that are
(also) used by a regular computation. This allows us later on to
identify stmts that are used solely by a reduction, and therefore the
- order of the results that they produce does not have to be kept.
-
- Reduction phis are expected to be used by a reduction stmt, or by
- in an outer loop; Other reduction stmts are expected to be
- in the loop, and possibly used by a stmt in an outer loop.
- Here are the expected values of "relevant" for reduction phis/stmts:
-
- relevance: phi stmt
- vect_unused_in_scope ok
- vect_used_in_outer_by_reduction ok ok
- vect_used_in_outer ok ok
- vect_used_by_reduction ok
- vect_used_in_scope */
+ order of the results that they produce does not have to be kept. */
if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
{
relevant = vect_used_by_reduction;
break;
- case vect_used_in_outer_by_reduction:
- case vect_used_in_outer:
- gcc_assert (gimple_code (stmt) != GIMPLE_ASSIGN
- || (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR
- && (gimple_assign_rhs_code (stmt)
- != DOT_PROD_EXPR)));
- break;
-
case vect_used_by_reduction:
if (gimple_code (stmt) == GIMPLE_PHI)
break;
/* fall through */
- case vect_used_in_scope:
+
default:
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "unsupported use of reduction.");
VEC_free (gimple, heap, worklist);
return false;
}
+
live_p = false;
}
+ else if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_nested_cycle)
+ {
+ enum vect_relevant tmp_relevant = relevant;
+ switch (tmp_relevant)
+ {
+ case vect_unused_in_scope:
+ case vect_used_in_outer_by_reduction:
+ case vect_used_in_outer:
+ break;
+ default:
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "unsupported use of nested cycle.");
+
+ VEC_free (gimple, heap, worklist);
+ return false;
+ }
+
+ live_p = false;
+ }
+
FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
{
tree op = USE_FROM_PTR (use_p);
/* Case 4: operand is defined by a loop header phi - reduction */
case vect_reduction_def:
+ case vect_nested_cycle:
{
struct loop *loop;
break;
case vect_reduction_def:
+ case vect_nested_cycle:
gcc_assert (!bb_vinfo && (relevance == vect_used_in_outer
|| relevance == vect_used_in_outer_by_reduction
|| relevance == vect_unused_in_scope));
OSDN Git Service
