+/* Detect SLP reduction of the form:
+
+ #a1 = phi <a5, a0>
+ a2 = operation (a1)
+ a3 = operation (a2)
+ a4 = operation (a3)
+ a5 = operation (a4)
+
+ #a = phi <a5>
+
+ PHI is the reduction phi node (#a1 = phi <a5, a0> above)
+ FIRST_STMT is the first reduction stmt in the chain
+ (a2 = operation (a1)).
+
+ Return TRUE if a reduction chain was detected. */
+
+static bool
+vect_is_slp_reduction (loop_vec_info loop_info, gimple phi, gimple first_stmt)
+{
+ struct loop *loop = (gimple_bb (phi))->loop_father;
+ struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
+ enum tree_code code;
+ gimple current_stmt = NULL, loop_use_stmt = NULL, first, next_stmt;
+ stmt_vec_info use_stmt_info, current_stmt_info;
+ tree lhs;
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
+ int nloop_uses, size = 0, n_out_of_loop_uses;
+ bool found = false;
+
+ if (loop != vect_loop)
+ return false;
+
+ lhs = PHI_RESULT (phi);
+ code = gimple_assign_rhs_code (first_stmt);
+ while (1)
+ {
+ nloop_uses = 0;
+ n_out_of_loop_uses = 0;
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
+ {
+ gimple use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
+
+ use_stmt = USE_STMT (use_p);
+
+ /* Check if we got back to the reduction phi. */
+ if (use_stmt == phi)
+ {
+ loop_use_stmt = use_stmt;
+ found = true;
+ break;
+ }
+
+ if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
+ {
+ if (vinfo_for_stmt (use_stmt)
+ && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt)))
+ {
+ loop_use_stmt = use_stmt;
+ nloop_uses++;
+ }
+ }
+ else
+ n_out_of_loop_uses++;
+
+ /* There are can be either a single use in the loop or two uses in
+ phi nodes. */
+ if (nloop_uses > 1 || (n_out_of_loop_uses && nloop_uses))
+ return false;
+ }
+
+ if (found)
+ break;
+
+ /* We reached a statement with no loop uses. */
+ if (nloop_uses == 0)
+ return false;
+
+ /* This is a loop exit phi, and we haven't reached the reduction phi. */
+ if (gimple_code (loop_use_stmt) == GIMPLE_PHI)
+ return false;
+
+ if (!is_gimple_assign (loop_use_stmt)
+ || code != gimple_assign_rhs_code (loop_use_stmt)
+ || !flow_bb_inside_loop_p (loop, gimple_bb (loop_use_stmt)))
+ return false;
+
+ /* Insert USE_STMT into reduction chain. */
+ use_stmt_info = vinfo_for_stmt (loop_use_stmt);
+ if (current_stmt)
+ {
+ current_stmt_info = vinfo_for_stmt (current_stmt);
+ GROUP_NEXT_ELEMENT (current_stmt_info) = loop_use_stmt;
+ GROUP_FIRST_ELEMENT (use_stmt_info)
+ = GROUP_FIRST_ELEMENT (current_stmt_info);
+ }
+ else
+ GROUP_FIRST_ELEMENT (use_stmt_info) = loop_use_stmt;
+
+ lhs = gimple_assign_lhs (loop_use_stmt);
+ current_stmt = loop_use_stmt;
+ size++;
+ }
+
+ if (!found || loop_use_stmt != phi || size < 2)
+ return false;
+
+ /* Swap the operands, if needed, to make the reduction operand be the second
+ operand. */
+ lhs = PHI_RESULT (phi);
+ next_stmt = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
+ while (next_stmt)
+ {
+ if (gimple_assign_rhs2 (next_stmt) == lhs)
+ {
+ tree op = gimple_assign_rhs1 (next_stmt);
+ gimple def_stmt = NULL;
+
+ if (TREE_CODE (op) == SSA_NAME)
+ def_stmt = SSA_NAME_DEF_STMT (op);
+
+ /* Check that the other def is either defined in the loop
+ ("vect_internal_def"), or it's an induction (defined by a
+ loop-header phi-node). */
+ if (def_stmt
+ && gimple_bb (def_stmt)
+ && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
+ && (is_gimple_assign (def_stmt)
+ || is_gimple_call (def_stmt)
+ || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
+ == vect_induction_def
+ || (gimple_code (def_stmt) == GIMPLE_PHI
+ && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
+ == vect_internal_def
+ && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
+ {
+ lhs = gimple_assign_lhs (next_stmt);
+ next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
+ continue;
+ }
+
+ return false;
+ }
+ else
+ {
+ tree op = gimple_assign_rhs2 (next_stmt);
+ gimple def_stmt = NULL;
+
+ if (TREE_CODE (op) == SSA_NAME)
+ def_stmt = SSA_NAME_DEF_STMT (op);
+
+ /* Check that the other def is either defined in the loop
+ ("vect_internal_def"), or it's an induction (defined by a
+ loop-header phi-node). */
+ if (def_stmt
+ && gimple_bb (def_stmt)
+ && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
+ && (is_gimple_assign (def_stmt)
+ || is_gimple_call (def_stmt)
+ || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
+ == vect_induction_def
+ || (gimple_code (def_stmt) == GIMPLE_PHI
+ && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
+ == vect_internal_def
+ && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "swapping oprnds: ");
+ print_gimple_stmt (vect_dump, next_stmt, 0, TDF_SLIM);
+ }
+
+ swap_tree_operands (next_stmt,
+ gimple_assign_rhs1_ptr (next_stmt),
+ gimple_assign_rhs2_ptr (next_stmt));
+ mark_symbols_for_renaming (next_stmt);
+ }
+ else
+ return false;
+ }
+
+ lhs = gimple_assign_lhs (next_stmt);
+ next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
+ }
+
+ /* Save the chain for further analysis in SLP detection. */
+ first = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
+ VEC_safe_push (gimple, heap, LOOP_VINFO_REDUCTION_CHAINS (loop_info), first);
+ GROUP_SIZE (vinfo_for_stmt (first)) = size;
+
+ return true;
+}
+
+