/* Loop autoparallelization.
- Copyright (C) 2006-2015 Free Software Foundation, Inc.
+ Copyright (C) 2006-2020 Free Software Foundation, Inc.
Contributed by Sebastian Pop <pop@cri.ensmp.fr>
Zdenek Dvorak <dvorakz@suse.cz> and Razya Ladelsky <razya@il.ibm.com>.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "alias.h"
-#include "symtab.h"
-#include "options.h"
+#include "backend.h"
#include "tree.h"
-#include "fold-const.h"
-#include "predict.h"
-#include "tm.h"
-#include "hard-reg-set.h"
-#include "function.h"
-#include "dominance.h"
-#include "cfg.h"
-#include "basic-block.h"
-#include "tree-ssa-alias.h"
-#include "internal-fn.h"
-#include "gimple-expr.h"
#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "cgraph.h"
+#include "gimple-pretty-print.h"
+#include "fold-const.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
#include "gimple-walk.h"
#include "stor-layout.h"
#include "tree-nested.h"
-#include "gimple-ssa.h"
#include "tree-cfg.h"
-#include "tree-phinodes.h"
-#include "ssa-iterators.h"
-#include "stringpool.h"
-#include "tree-ssanames.h"
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-into-ssa.h"
#include "cfgloop.h"
-#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
-#include "gimple-pretty-print.h"
-#include "tree-pass.h"
#include "langhooks.h"
#include "tree-vectorizer.h"
#include "tree-hasher.h"
#include "tree-parloops.h"
+#include "omp-general.h"
#include "omp-low.h"
-#include "tree-nested.h"
-#include "plugin-api.h"
-#include "ipa-ref.h"
-#include "cgraph.h"
#include "tree-ssa.h"
+#include "tree-ssa-alias.h"
+#include "tree-eh.h"
+#include "gomp-constants.h"
+#include "tree-dfa.h"
+#include "stringpool.h"
+#include "attribs.h"
/* This pass tries to distribute iterations of loops into several threads.
The implementation is straightforward -- for each loop we test whether its
More info can also be found at http://gcc.gnu.org/wiki/AutoParInGCC */
/*
Reduction handling:
- currently we use vect_force_simple_reduction() to detect reduction patterns.
+ currently we use code inspired by vect_force_simple_reduction to detect
+ reduction patterns.
The code transformation will be introduced by an example.
*/
+/* Error reporting helper for parloops_is_simple_reduction below. GIMPLE
+ statement STMT is printed with a message MSG. */
+
+static void
+report_ploop_op (dump_flags_t msg_type, gimple *stmt, const char *msg)
+{
+ dump_printf_loc (msg_type, vect_location, "%s%G", msg, stmt);
+}
+
+/* DEF_STMT_INFO occurs in a loop that contains a potential reduction
+ operation. Return true if the results of DEF_STMT_INFO are something
+ that can be accumulated by such a reduction. */
+
+static bool
+parloops_valid_reduction_input_p (stmt_vec_info def_stmt_info)
+{
+ return (is_gimple_assign (def_stmt_info->stmt)
+ || is_gimple_call (def_stmt_info->stmt)
+ || STMT_VINFO_DEF_TYPE (def_stmt_info) == vect_induction_def
+ || (gimple_code (def_stmt_info->stmt) == GIMPLE_PHI
+ && STMT_VINFO_DEF_TYPE (def_stmt_info) == vect_internal_def
+ && !is_loop_header_bb_p (gimple_bb (def_stmt_info->stmt))));
+}
+
+/* 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
+parloops_is_slp_reduction (loop_vec_info loop_info, gimple *phi,
+ gimple *first_stmt)
+{
+ class loop *loop = (gimple_bb (phi))->loop_father;
+ class loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
+ enum tree_code code;
+ gimple *loop_use_stmt = NULL;
+ stmt_vec_info use_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;
+
+ auto_vec<stmt_vec_info, 8> reduc_chain;
+ 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;
+
+ /* 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)))
+ {
+ 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 = loop_info->lookup_stmt (loop_use_stmt);
+ reduc_chain.safe_push (use_stmt_info);
+
+ lhs = gimple_assign_lhs (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);
+ for (unsigned i = 0; i < reduc_chain.length (); ++i)
+ {
+ gassign *next_stmt = as_a <gassign *> (reduc_chain[i]->stmt);
+ if (gimple_assign_rhs2 (next_stmt) == lhs)
+ {
+ tree op = gimple_assign_rhs1 (next_stmt);
+ stmt_vec_info def_stmt_info = loop_info->lookup_def (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_info
+ && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt_info->stmt))
+ && parloops_valid_reduction_input_p (def_stmt_info))
+ {
+ lhs = gimple_assign_lhs (next_stmt);
+ continue;
+ }
+
+ return false;
+ }
+ else
+ {
+ tree op = gimple_assign_rhs2 (next_stmt);
+ stmt_vec_info def_stmt_info = loop_info->lookup_def (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_info
+ && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt_info->stmt))
+ && parloops_valid_reduction_input_p (def_stmt_info))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location, "swapping oprnds: %G",
+ next_stmt);
+
+ swap_ssa_operands (next_stmt,
+ gimple_assign_rhs1_ptr (next_stmt),
+ gimple_assign_rhs2_ptr (next_stmt));
+ update_stmt (next_stmt);
+ }
+ else
+ return false;
+ }
+
+ lhs = gimple_assign_lhs (next_stmt);
+ }
+
+ /* Build up the actual chain. */
+ for (unsigned i = 0; i < reduc_chain.length () - 1; ++i)
+ {
+ REDUC_GROUP_FIRST_ELEMENT (reduc_chain[i]) = reduc_chain[0];
+ REDUC_GROUP_NEXT_ELEMENT (reduc_chain[i]) = reduc_chain[i+1];
+ }
+ REDUC_GROUP_FIRST_ELEMENT (reduc_chain.last ()) = reduc_chain[0];
+ REDUC_GROUP_NEXT_ELEMENT (reduc_chain.last ()) = NULL;
+
+ /* Save the chain for further analysis in SLP detection. */
+ LOOP_VINFO_REDUCTION_CHAINS (loop_info).safe_push (reduc_chain[0]);
+ REDUC_GROUP_SIZE (reduc_chain[0]) = size;
+
+ return true;
+}
+
+/* Return true if we need an in-order reduction for operation CODE
+ on type TYPE. NEED_WRAPPING_INTEGRAL_OVERFLOW is true if integer
+ overflow must wrap. */
+
+static bool
+parloops_needs_fold_left_reduction_p (tree type, tree_code code,
+ bool need_wrapping_integral_overflow)
+{
+ /* CHECKME: check for !flag_finite_math_only too? */
+ if (SCALAR_FLOAT_TYPE_P (type))
+ switch (code)
+ {
+ case MIN_EXPR:
+ case MAX_EXPR:
+ return false;
+
+ default:
+ return !flag_associative_math;
+ }
+
+ if (INTEGRAL_TYPE_P (type))
+ {
+ if (!operation_no_trapping_overflow (type, code))
+ return true;
+ if (need_wrapping_integral_overflow
+ && !TYPE_OVERFLOW_WRAPS (type)
+ && operation_can_overflow (code))
+ return true;
+ return false;
+ }
+
+ if (SAT_FIXED_POINT_TYPE_P (type))
+ return true;
+
+ return false;
+}
+
+
+/* Function parloops_is_simple_reduction
+
+ (1) Detect a cross-iteration def-use cycle that represents a simple
+ reduction computation. We look for the following pattern:
+
+ loop_header:
+ a1 = phi < a0, a2 >
+ a3 = ...
+ a2 = operation (a3, a1)
+
+ or
+
+ a3 = ...
+ loop_header:
+ a1 = phi < a0, a2 >
+ a2 = operation (a3, a1)
+
+ such that:
+ 1. operation is commutative and associative and it is safe to
+ change the order of the computation
+ 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
+ 4. no uses of a1 outside the loop.
+
+ Conditions 1,4 are tested here.
+ Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
+
+ (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
+ nested cycles.
+
+ (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
+ reductions:
+
+ a1 = phi < a0, a2 >
+ inner loop (def of a3)
+ a2 = phi < a3 >
+
+ (4) Detect condition expressions, ie:
+ for (int i = 0; i < N; i++)
+ if (a[i] < val)
+ ret_val = a[i];
+
+*/
+
+static stmt_vec_info
+parloops_is_simple_reduction (loop_vec_info loop_info, stmt_vec_info phi_info,
+ bool *double_reduc,
+ bool need_wrapping_integral_overflow,
+ enum vect_reduction_type *v_reduc_type)
+{
+ gphi *phi = as_a <gphi *> (phi_info->stmt);
+ class loop *loop = (gimple_bb (phi))->loop_father;
+ class loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
+ bool nested_in_vect_loop = flow_loop_nested_p (vect_loop, loop);
+ gimple *phi_use_stmt = NULL;
+ enum tree_code orig_code, code;
+ tree op1, op2, op3 = NULL_TREE, op4 = NULL_TREE;
+ tree type;
+ tree name;
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
+ bool phi_def;
+
+ *double_reduc = false;
+ *v_reduc_type = TREE_CODE_REDUCTION;
+
+ tree phi_name = PHI_RESULT (phi);
+ /* ??? If there are no uses of the PHI result the inner loop reduction
+ won't be detected as possibly double-reduction by vectorizable_reduction
+ because that tries to walk the PHI arg from the preheader edge which
+ can be constant. See PR60382. */
+ if (has_zero_uses (phi_name))
+ return NULL;
+ unsigned nphi_def_loop_uses = 0;
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, phi_name)
+ {
+ gimple *use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
+
+ if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "intermediate value used outside loop.\n");
+
+ return NULL;
+ }
+
+ nphi_def_loop_uses++;
+ phi_use_stmt = use_stmt;
+ }
+
+ edge latch_e = loop_latch_edge (loop);
+ tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
+ if (TREE_CODE (loop_arg) != SSA_NAME)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "reduction: not ssa_name: %T\n", loop_arg);
+ return NULL;
+ }
+
+ stmt_vec_info def_stmt_info = loop_info->lookup_def (loop_arg);
+ if (!def_stmt_info
+ || !flow_bb_inside_loop_p (loop, gimple_bb (def_stmt_info->stmt)))
+ return NULL;
+
+ if (gassign *def_stmt = dyn_cast <gassign *> (def_stmt_info->stmt))
+ {
+ name = gimple_assign_lhs (def_stmt);
+ phi_def = false;
+ }
+ else if (gphi *def_stmt = dyn_cast <gphi *> (def_stmt_info->stmt))
+ {
+ name = PHI_RESULT (def_stmt);
+ phi_def = true;
+ }
+ else
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "reduction: unhandled reduction operation: %G",
+ def_stmt_info->stmt);
+ return NULL;
+ }
+
+ unsigned nlatch_def_loop_uses = 0;
+ auto_vec<gphi *, 3> lcphis;
+ bool inner_loop_of_double_reduc = false;
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
+ {
+ gimple *use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
+ if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
+ nlatch_def_loop_uses++;
+ else
+ {
+ /* We can have more than one loop-closed PHI. */
+ lcphis.safe_push (as_a <gphi *> (use_stmt));
+ if (nested_in_vect_loop
+ && (STMT_VINFO_DEF_TYPE (loop_info->lookup_stmt (use_stmt))
+ == vect_double_reduction_def))
+ inner_loop_of_double_reduc = true;
+ }
+ }
+
+ /* 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 ((!nested_in_vect_loop || inner_loop_of_double_reduc)
+ && (nlatch_def_loop_uses > 1 || nphi_def_loop_uses > 1))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "reduction used in loop.\n");
+ return NULL;
+ }
+
+ /* If DEF_STMT is a phi node itself, we expect it to have a single argument
+ defined in the inner loop. */
+ if (phi_def)
+ {
+ gphi *def_stmt = as_a <gphi *> (def_stmt_info->stmt);
+ op1 = PHI_ARG_DEF (def_stmt, 0);
+
+ if (gimple_phi_num_args (def_stmt) != 1
+ || TREE_CODE (op1) != SSA_NAME)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "unsupported phi node definition.\n");
+
+ return NULL;
+ }
+
+ gimple *def1 = SSA_NAME_DEF_STMT (op1);
+ if (gimple_bb (def1)
+ && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
+ && loop->inner
+ && flow_bb_inside_loop_p (loop->inner, gimple_bb (def1))
+ && is_gimple_assign (def1)
+ && is_a <gphi *> (phi_use_stmt)
+ && flow_bb_inside_loop_p (loop->inner, gimple_bb (phi_use_stmt)))
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_NOTE, def_stmt,
+ "detected double reduction: ");
+
+ *double_reduc = true;
+ return def_stmt_info;
+ }
+
+ return NULL;
+ }
+
+ /* If we are vectorizing an inner reduction we are executing that
+ in the original order only in case we are not dealing with a
+ double reduction. */
+ bool check_reduction = true;
+ if (flow_loop_nested_p (vect_loop, loop))
+ {
+ gphi *lcphi;
+ unsigned i;
+ check_reduction = false;
+ FOR_EACH_VEC_ELT (lcphis, i, lcphi)
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (lcphi))
+ {
+ gimple *use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
+ if (! flow_bb_inside_loop_p (vect_loop, gimple_bb (use_stmt)))
+ check_reduction = true;
+ }
+ }
+
+ gassign *def_stmt = as_a <gassign *> (def_stmt_info->stmt);
+ code = orig_code = gimple_assign_rhs_code (def_stmt);
+
+ if (nested_in_vect_loop && !check_reduction)
+ {
+ /* FIXME: Even for non-reductions code generation is funneled
+ through vectorizable_reduction for the stmt defining the
+ PHI latch value. So we have to artificially restrict ourselves
+ for the supported operations. */
+ switch (get_gimple_rhs_class (code))
+ {
+ case GIMPLE_BINARY_RHS:
+ case GIMPLE_TERNARY_RHS:
+ break;
+ default:
+ /* Not supported by vectorizable_reduction. */
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
+ "nested cycle: not handled operation: ");
+ return NULL;
+ }
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_NOTE, def_stmt, "detected nested cycle: ");
+ return def_stmt_info;
+ }
+
+ /* We can handle "res -= x[i]", which is non-associative by
+ simply rewriting this into "res += -x[i]". Avoid changing
+ gimple instruction for the first simple tests and only do this
+ if we're allowed to change code at all. */
+ if (code == MINUS_EXPR && gimple_assign_rhs2 (def_stmt) != phi_name)
+ code = PLUS_EXPR;
+
+ if (code == COND_EXPR)
+ {
+ if (! nested_in_vect_loop)
+ *v_reduc_type = COND_REDUCTION;
+
+ op3 = gimple_assign_rhs1 (def_stmt);
+ if (COMPARISON_CLASS_P (op3))
+ {
+ op4 = TREE_OPERAND (op3, 1);
+ op3 = TREE_OPERAND (op3, 0);
+ }
+ if (op3 == phi_name || op4 == phi_name)
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
+ "reduction: condition depends on previous"
+ " iteration: ");
+ return NULL;
+ }
+
+ op1 = gimple_assign_rhs2 (def_stmt);
+ op2 = gimple_assign_rhs3 (def_stmt);
+ }
+ else if (!commutative_tree_code (code) || !associative_tree_code (code))
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
+ "reduction: not commutative/associative: ");
+ return NULL;
+ }
+ else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
+ {
+ op1 = gimple_assign_rhs1 (def_stmt);
+ op2 = gimple_assign_rhs2 (def_stmt);
+ }
+ else
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
+ "reduction: not handled operation: ");
+ return NULL;
+ }
+
+ if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
+ "reduction: both uses not ssa_names: ");
+
+ return NULL;
+ }
+
+ type = TREE_TYPE (gimple_assign_lhs (def_stmt));
+ if ((TREE_CODE (op1) == SSA_NAME
+ && !types_compatible_p (type,TREE_TYPE (op1)))
+ || (TREE_CODE (op2) == SSA_NAME
+ && !types_compatible_p (type, TREE_TYPE (op2)))
+ || (op3 && TREE_CODE (op3) == SSA_NAME
+ && !types_compatible_p (type, TREE_TYPE (op3)))
+ || (op4 && TREE_CODE (op4) == SSA_NAME
+ && !types_compatible_p (type, TREE_TYPE (op4))))
+ {
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "reduction: multiple types: operation type: "
+ "%T, operands types: %T,%T",
+ type, TREE_TYPE (op1), TREE_TYPE (op2));
+ if (op3)
+ dump_printf (MSG_NOTE, ",%T", TREE_TYPE (op3));
+
+ if (op4)
+ dump_printf (MSG_NOTE, ",%T", TREE_TYPE (op4));
+ dump_printf (MSG_NOTE, "\n");
+ }
+
+ return NULL;
+ }
+
+ /* Check whether 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,
+ and therefore vectorizing reductions in the inner-loop during
+ outer-loop vectorization is safe. */
+ if (check_reduction
+ && *v_reduc_type == TREE_CODE_REDUCTION
+ && parloops_needs_fold_left_reduction_p (type, code,
+ need_wrapping_integral_overflow))
+ *v_reduc_type = FOLD_LEFT_REDUCTION;
+
+ /* 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
+ 3) nested cycle (i.e., outer loop vectorization). */
+ stmt_vec_info def1_info = loop_info->lookup_def (op1);
+ stmt_vec_info def2_info = loop_info->lookup_def (op2);
+ if (code != COND_EXPR && !def1_info && !def2_info)
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_NOTE, def_stmt,
+ "reduction: no defs for operands: ");
+ return NULL;
+ }
+
+ /* Check that one def is the reduction def, defined by PHI,
+ 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 (def2_info
+ && def2_info->stmt == phi
+ && (code == COND_EXPR
+ || !def1_info
+ || !flow_bb_inside_loop_p (loop, gimple_bb (def1_info->stmt))
+ || parloops_valid_reduction_input_p (def1_info)))
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_NOTE, def_stmt, "detected reduction: ");
+ return def_stmt_info;
+ }
+
+ if (def1_info
+ && def1_info->stmt == phi
+ && (code == COND_EXPR
+ || !def2_info
+ || !flow_bb_inside_loop_p (loop, gimple_bb (def2_info->stmt))
+ || parloops_valid_reduction_input_p (def2_info)))
+ {
+ if (! nested_in_vect_loop && orig_code != MINUS_EXPR)
+ {
+ /* Check if we can 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 (code == COND_EXPR)
+ {
+ /* Swap cond_expr by inverting the condition. */
+ tree cond_expr = gimple_assign_rhs1 (def_stmt);
+ enum tree_code invert_code = ERROR_MARK;
+ enum tree_code cond_code = TREE_CODE (cond_expr);
+
+ if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
+ {
+ bool honor_nans = HONOR_NANS (TREE_OPERAND (cond_expr, 0));
+ invert_code = invert_tree_comparison (cond_code, honor_nans);
+ }
+ if (invert_code != ERROR_MARK)
+ {
+ TREE_SET_CODE (cond_expr, invert_code);
+ swap_ssa_operands (def_stmt,
+ gimple_assign_rhs2_ptr (def_stmt),
+ gimple_assign_rhs3_ptr (def_stmt));
+ }
+ else
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_NOTE, def_stmt,
+ "detected reduction: cannot swap operands "
+ "for cond_expr");
+ return NULL;
+ }
+ }
+ else
+ swap_ssa_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
+ gimple_assign_rhs2_ptr (def_stmt));
+
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_NOTE, def_stmt,
+ "detected reduction: need to swap operands: ");
+ }
+ else
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_NOTE, def_stmt, "detected reduction: ");
+ }
+
+ return def_stmt_info;
+ }
+
+ /* Try to find SLP reduction chain. */
+ if (! nested_in_vect_loop
+ && code != COND_EXPR
+ && orig_code != MINUS_EXPR
+ && parloops_is_slp_reduction (loop_info, phi, def_stmt))
+ {
+ if (dump_enabled_p ())
+ report_ploop_op (MSG_NOTE, def_stmt,
+ "reduction: detected reduction chain: ");
+
+ return def_stmt_info;
+ }
+
+ /* Look for the expression computing loop_arg from loop PHI result. */
+ if (check_reduction_path (vect_location, loop, phi, loop_arg, code))
+ return def_stmt_info;
+
+ if (dump_enabled_p ())
+ {
+ report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
+ "reduction: unknown pattern: ");
+ }
+
+ return NULL;
+}
+
+/* Wrapper around vect_is_simple_reduction, which will modify code
+ in-place if it enables detection of more reductions. Arguments
+ as there. */
+
+stmt_vec_info
+parloops_force_simple_reduction (loop_vec_info loop_info, stmt_vec_info phi_info,
+ bool *double_reduc,
+ bool need_wrapping_integral_overflow)
+{
+ enum vect_reduction_type v_reduc_type;
+ stmt_vec_info def_info
+ = parloops_is_simple_reduction (loop_info, phi_info, double_reduc,
+ need_wrapping_integral_overflow,
+ &v_reduc_type);
+ if (def_info)
+ {
+ STMT_VINFO_REDUC_TYPE (phi_info) = v_reduc_type;
+ STMT_VINFO_REDUC_DEF (phi_info) = def_info;
+ STMT_VINFO_REDUC_TYPE (def_info) = v_reduc_type;
+ STMT_VINFO_REDUC_DEF (def_info) = phi_info;
+ }
+ return def_info;
+}
+
/* Minimal number of iterations of a loop that should be executed in each
thread. */
-#define MIN_PER_THREAD 100
+#define MIN_PER_THREAD param_parloops_min_per_thread
/* Element of the hashtable, representing a
reduction in the current loop. */
struct reduction_info
{
- gimple reduc_stmt; /* reduction statement. */
- gimple reduc_phi; /* The phi node defining the reduction. */
+ gimple *reduc_stmt; /* reduction statement. */
+ gimple *reduc_phi; /* The phi node defining the reduction. */
enum tree_code reduction_code;/* code for the reduction operation. */
unsigned reduc_version; /* SSA_NAME_VERSION of original reduc_phi
result. */
of the reduction variable when existing the loop. */
tree initial_value; /* The initial value of the reduction var before entering the loop. */
tree field; /* the name of the field in the parloop data structure intended for reduction. */
+ tree reduc_addr; /* The address of the reduction variable for
+ openacc reductions. */
tree init; /* reduction initialization value. */
gphi *new_phi; /* (helper field) Newly created phi node whose result
will be passed to the atomic operation. Represents
/* Reduction info hashtable helpers. */
-struct reduction_hasher : typed_free_remove <reduction_info>
+struct reduction_hasher : free_ptr_hash <reduction_info>
{
- typedef reduction_info *value_type;
- typedef reduction_info *compare_type;
static inline hashval_t hash (const reduction_info *);
static inline bool equal (const reduction_info *, const reduction_info *);
};
static struct reduction_info *
-reduction_phi (reduction_info_table_type *reduction_list, gimple phi)
+reduction_phi (reduction_info_table_type *reduction_list, gimple *phi)
{
struct reduction_info tmpred, *red;
- if (reduction_list->elements () == 0 || phi == NULL)
+ if (reduction_list->is_empty () || phi == NULL)
+ return NULL;
+
+ if (gimple_uid (phi) == (unsigned int)-1
+ || gimple_uid (phi) == 0)
return NULL;
tmpred.reduc_phi = phi;
tmpred.reduc_version = gimple_uid (phi);
red = reduction_list->find (&tmpred);
+ gcc_assert (red == NULL || red->reduc_phi == phi);
return red;
}
/* Name copies hashtable helpers. */
-struct name_to_copy_hasher : typed_free_remove <name_to_copy_elt>
+struct name_to_copy_hasher : free_ptr_hash <name_to_copy_elt>
{
- typedef name_to_copy_elt *value_type;
- typedef name_to_copy_elt *compare_type;
static inline hashval_t hash (const name_to_copy_elt *);
static inline bool equal (const name_to_copy_elt *, const name_to_copy_elt *);
};
in parallel). */
static bool
-loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)
+loop_parallel_p (class loop *loop, struct obstack * parloop_obstack)
{
vec<ddr_p> dependence_relations;
vec<data_reference_p> datarefs;
BB_IRREDUCIBLE_LOOP flag. */
static inline bool
-loop_has_blocks_with_irreducible_flag (struct loop *loop)
+loop_has_blocks_with_irreducible_flag (class loop *loop)
{
unsigned i;
basic_block *bbs = get_loop_body_in_dom_order (loop);
if (gsi == NULL)
return build_fold_addr_expr_with_type (obj, type);
- name = force_gimple_operand (build_addr (obj, current_function_decl),
+ name = force_gimple_operand (build_addr (obj),
&stmts, true, NULL_TREE);
if (!gimple_seq_empty_p (stmts))
gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
return name;
}
+static tree
+reduc_stmt_res (gimple *stmt)
+{
+ return (gimple_code (stmt) == GIMPLE_PHI
+ ? gimple_phi_result (stmt)
+ : gimple_assign_lhs (stmt));
+}
+
/* Callback for htab_traverse. Create the initialization statement
for reduction described in SLOT, and place it at the preheader of
the loop described in DATA. */
int
-initialize_reductions (reduction_info **slot, struct loop *loop)
+initialize_reductions (reduction_info **slot, class loop *loop)
{
- tree init, c;
- tree bvar, type, arg;
+ tree init;
+ tree type, arg;
edge e;
struct reduction_info *const reduc = *slot;
/* In the phi node at the header, replace the argument coming
from the preheader with the reduction initialization value. */
- /* Create a new variable to initialize the reduction. */
+ /* Initialize the reduction. */
type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
- bvar = create_tmp_var (type, "reduction");
-
- c = build_omp_clause (gimple_location (reduc->reduc_stmt),
- OMP_CLAUSE_REDUCTION);
- OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
- OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
-
- init = omp_reduction_init (c, TREE_TYPE (bvar));
+ init = omp_reduction_init_op (gimple_location (reduc->reduc_stmt),
+ reduc->reduction_code, type);
reduc->init = init;
/* Replace the argument representing the initialization value
int_tree_htab_type *decl_address)
{
struct elv_data dta;
- gimple stmt = gsi_stmt (*gsi);
+ gimple *stmt = gsi_stmt (*gsi);
memset (&dta.info, '\0', sizeof (dta.info));
dta.entry = entry;
}
else if (gimple_clobber_p (stmt))
{
+ unlink_stmt_vdef (stmt);
stmt = gimple_build_nop ();
gsi_replace (gsi, stmt, false);
dta.changed = true;
FOR_EACH_VEC_ELT (body, i, bb)
if (bb != entry_bb && bb != exit_bb)
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- if (is_gimple_debug (gsi_stmt (gsi)))
- {
- if (gimple_debug_bind_p (gsi_stmt (gsi)))
- has_debug_stmt = true;
- }
- else
- eliminate_local_variables_stmt (entry, &gsi, &decl_address);
+ {
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (is_gimple_debug (gsi_stmt (gsi)))
+ {
+ if (gimple_debug_bind_p (gsi_stmt (gsi)))
+ has_debug_stmt = true;
+ }
+ else
+ eliminate_local_variables_stmt (entry, &gsi, &decl_address);
+ }
if (has_debug_stmt)
FOR_EACH_VEC_ELT (body, i, bb)
if (!dslot->to)
{
var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
- DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
+ DECL_NOT_GIMPLE_REG_P (var_copy) = DECL_NOT_GIMPLE_REG_P (var);
dslot->uid = uid;
dslot->to = var_copy;
replacement decls are stored in DECL_COPIES. */
static void
-separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
+separate_decls_in_region_stmt (edge entry, edge exit, gimple *stmt,
name_to_copy_table_type *name_copies,
int_tree_htab_type *decl_copies)
{
replacement decls are stored in DECL_COPIES. */
static bool
-separate_decls_in_region_debug (gimple stmt,
+separate_decls_in_region_debug (gimple *stmt,
name_to_copy_table_type *name_copies,
int_tree_htab_type *decl_copies)
{
{
struct reduction_info *const red = *slot;
- tree var = gimple_assign_lhs (red->reduc_stmt);
+ tree var = reduc_stmt_res (red->reduc_stmt);
tree field = build_decl (gimple_location (red->reduc_stmt), FIELD_DECL,
SSA_NAME_IDENTIFIER (var), TREE_TYPE (var));
reduction's data structure. */
int
-create_phi_for_local_result (reduction_info **slot, struct loop *loop)
+create_phi_for_local_result (reduction_info **slot, class loop *loop)
{
struct reduction_info *const reduc = *slot;
edge e;
gphi *new_phi;
- basic_block store_bb;
+ basic_block store_bb, continue_bb;
tree local_res;
- source_location locus;
+ location_t locus;
/* STORE_BB is the block where the phi
should be stored. It is the destination of the loop exit.
(Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
- store_bb = FALLTHRU_EDGE (loop->latch)->dest;
+ continue_bb = single_pred (loop->latch);
+ store_bb = FALLTHRU_EDGE (continue_bb)->dest;
/* STORE_BB has two predecessors. One coming from the loop
(the reduction's result is computed at the loop),
and another coming from a block preceding the loop,
when no iterations
are executed (the initial value should be taken). */
- if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
+ if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (continue_bb))
e = EDGE_PRED (store_bb, 1);
else
e = EDGE_PRED (store_bb, 0);
- local_res = copy_ssa_name (gimple_assign_lhs (reduc->reduc_stmt));
+ tree lhs = reduc_stmt_res (reduc->reduc_stmt);
+ local_res = copy_ssa_name (lhs);
locus = gimple_location (reduc->reduc_stmt);
new_phi = create_phi_node (local_res, store_bb);
add_phi_arg (new_phi, reduc->init, e, locus);
- add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
- FALLTHRU_EDGE (loop->latch), locus);
+ add_phi_arg (new_phi, lhs, FALLTHRU_EDGE (continue_bb), locus);
reduc->new_phi = new_phi;
return 1;
edge e;
tree t, addr, ref, x;
tree tmp_load, name;
- gimple load;
+ gimple *load;
- load_struct = build_simple_mem_ref (clsn_data->load);
- t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
+ if (reduc->reduc_addr == NULL_TREE)
+ {
+ load_struct = build_simple_mem_ref (clsn_data->load);
+ t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
+
+ addr = build_addr (t);
+ }
+ else
+ {
+ /* Set the address for the atomic store. */
+ addr = reduc->reduc_addr;
- addr = build_addr (t, current_function_decl);
+ /* Remove the non-atomic store '*addr = sum'. */
+ tree res = PHI_RESULT (reduc->keep_res);
+ use_operand_p use_p;
+ gimple *stmt;
+ bool single_use_p = single_imm_use (res, &use_p, &stmt);
+ gcc_assert (single_use_p);
+ replace_uses_by (gimple_vdef (stmt),
+ gimple_vuse (stmt));
+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+ gsi_remove (&gsi, true);
+ }
/* Create phi node. */
bb = clsn_data->load_bb;
tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)));
tmp_load = make_ssa_name (tmp_load);
- load = gimple_build_omp_atomic_load (tmp_load, addr);
+ load = gimple_build_omp_atomic_load (tmp_load, addr,
+ OMP_MEMORY_ORDER_RELAXED);
SSA_NAME_DEF_STMT (tmp_load) = load;
gsi = gsi_start_bb (new_bb);
gsi_insert_after (&gsi, load, GSI_NEW_STMT);
name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
GSI_CONTINUE_LINKING);
- gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
+ gimple *store = gimple_build_omp_atomic_store (name,
+ OMP_MEMORY_ORDER_RELAXED);
+ gsi_insert_after (&gsi, store, GSI_NEW_STMT);
return 1;
}
LD_ST_DATA describes the shared data structure where
shared data is stored in and loaded from. */
static void
-create_call_for_reduction (struct loop *loop,
+create_call_for_reduction (class loop *loop,
reduction_info_table_type *reduction_list,
struct clsn_data *ld_st_data)
{
- reduction_list->traverse <struct loop *, create_phi_for_local_result> (loop);
+ reduction_list->traverse <class loop *, create_phi_for_local_result> (loop);
/* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
- ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
+ basic_block continue_bb = single_pred (loop->latch);
+ ld_st_data->load_bb = FALLTHRU_EDGE (continue_bb)->dest;
reduction_list
->traverse <struct clsn_data *, create_call_for_reduction_1> (ld_st_data);
}
create_loads_for_reductions (reduction_info **slot, struct clsn_data *clsn_data)
{
struct reduction_info *const red = *slot;
- gimple stmt;
+ gimple *stmt;
gimple_stmt_iterator gsi;
- tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
+ tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));
tree load_struct;
tree name;
tree x;
+ /* If there's no exit phi, the result of the reduction is unused. */
+ if (red->keep_res == NULL)
+ return 1;
+
gsi = gsi_after_labels (clsn_data->load_bb);
load_struct = build_simple_mem_ref (clsn_data->load);
load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
{
gimple_stmt_iterator gsi;
tree t;
- gimple stmt;
+ gimple *stmt;
gsi = gsi_after_labels (ld_st_data->load_bb);
t = build_fold_addr_expr (ld_st_data->store);
{
struct reduction_info *const red = *slot;
tree t;
- gimple stmt;
+ gimple *stmt;
gimple_stmt_iterator gsi;
- tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
+ tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));
gsi = gsi_last_bb (clsn_data->store_bb);
t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
{
struct name_to_copy_elt *const elt = *slot;
tree t;
- gimple stmt;
+ gimple *stmt;
gimple_stmt_iterator gsi;
tree type = TREE_TYPE (elt->new_name);
tree load_struct;
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple stmt = gsi_stmt (gsi);
+ gimple *stmt = gsi_stmt (gsi);
if (is_gimple_debug (stmt))
has_debug_stmt = true;
{
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
{
- gimple stmt = gsi_stmt (gsi);
+ gimple *stmt = gsi_stmt (gsi);
if (is_gimple_debug (stmt))
{
}
}
- if (name_copies.elements () == 0 && reduction_list->elements () == 0)
+ if (name_copies.is_empty () && reduction_list->is_empty ())
{
/* It may happen that there is nothing to copy (if there are only
loop carried and external variables in the loop). */
TYPE_NAME (type) = type_name;
name_copies.traverse <tree, add_field_for_name> (type);
- if (reduction_list && reduction_list->elements () > 0)
+ if (reduction_list && !reduction_list->is_empty ())
{
/* Create the fields for reductions. */
reduction_list->traverse <tree, add_field_for_reduction> (type);
/* Load the calculation from memory (after the join of the threads). */
- if (reduction_list && reduction_list->elements () > 0)
+ if (reduction_list && !reduction_list->is_empty ())
{
reduction_list
->traverse <struct clsn_data *, create_stores_for_reduction>
DECL_EXTERNAL (decl) = 0;
DECL_CONTEXT (decl) = NULL_TREE;
DECL_INITIAL (decl) = make_node (BLOCK);
+ BLOCK_SUPERCONTEXT (DECL_INITIAL (decl)) = decl;
t = build_decl (loc, RESULT_DECL, NULL_TREE, void_type_node);
DECL_ARTIFICIAL (t) = 1;
static void
replace_uses_in_bb_by (tree name, tree val, basic_block bb)
{
- gimple use_stmt;
+ gimple *use_stmt;
imm_use_iterator imm_iter;
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name)
}
}
-/* Replace uses of NAME by VAL in blocks BBS. */
+/* Do transformation from:
-static void
-replace_uses_in_bbs_by (tree name, tree val, bitmap bbs)
-{
- gimple use_stmt;
- imm_use_iterator imm_iter;
-
- FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name)
- {
- if (!bitmap_bit_p (bbs, gimple_bb (use_stmt)->index))
- continue;
-
- use_operand_p use_p;
- FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
- SET_USE (use_p, val);
- }
-}
-
-/* Do transformation from:
-
- <bb preheader>:
- ...
- goto <bb header>
+ <bb preheader>:
+ ...
+ goto <bb header>
<bb header>:
ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
goto <bb header>
<bb exit>:
- sum_z = PHI <sum_b (cond[1])>
+ sum_z = PHI <sum_b (cond[1]), ...>
[1] Where <bb cond> is single_pred (bb latch); In the simplest case,
that's <bb header>.
if (ivtmp_c < n + 1)
goto <bb header>;
else
- goto <bb exit>;
+ goto <bb newexit>;
<bb latch>:
ivtmp_b = ivtmp_a + 1;
goto <bb newheader>
+ <bb newexit>:
+ sum_y = PHI <sum_c (newheader)>
+
<bb exit>:
- sum_z = PHI <sum_c (newheader)>
+ sum_z = PHI <sum_y (newexit), ...>
In unified diff format:
- goto <bb header>
+ goto <bb newheader>
++ <bb newexit>:
++ sum_y = PHI <sum_c (newheader)>
+
<bb exit>:
-- sum_z = PHI <sum_b (cond[1])>
-+ sum_z = PHI <sum_c (newheader)>
+- sum_z = PHI <sum_b (cond[1]), ...>
++ sum_z = PHI <sum_y (newexit), ...>
Note: the example does not show any virtual phis, but these are handled more
or less as reductions.
bound. */
static void
-transform_to_exit_first_loop_alt (struct loop *loop,
+transform_to_exit_first_loop_alt (class loop *loop,
reduction_info_table_type *reduction_list,
tree bound)
{
tree control = gimple_cond_lhs (cond_stmt);
edge e;
- /* Gather the bbs dominated by the exit block. */
- bitmap exit_dominated = BITMAP_ALLOC (NULL);
- bitmap_set_bit (exit_dominated, exit_block->index);
- vec<basic_block> exit_dominated_vec
- = get_dominated_by (CDI_DOMINATORS, exit_block);
-
- int i;
- basic_block dom_bb;
- FOR_EACH_VEC_ELT (exit_dominated_vec, i, dom_bb)
- bitmap_set_bit (exit_dominated, dom_bb->index);
-
- exit_dominated_vec.release ();
+ /* Rewriting virtuals into loop-closed ssa normal form makes this
+ transformation simpler. It also ensures that the virtuals are in
+ loop-closed ssa normal from after the transformation, which is required by
+ create_parallel_loop. */
+ rewrite_virtuals_into_loop_closed_ssa (loop);
/* Create the new_header block. */
basic_block new_header = split_block_before_cond_jump (exit->src);
- edge split_edge = single_pred_edge (new_header);
+ edge edge_at_split = single_pred_edge (new_header);
/* Redirect entry edge to new_header. */
edge entry = loop_preheader_edge (loop);
e = redirect_edge_and_branch (post_cond_edge, header);
gcc_assert (e == post_cond_edge);
- /* Redirect split_edge to latch. */
- e = redirect_edge_and_branch (split_edge, latch);
- gcc_assert (e == split_edge);
+ /* Redirect edge_at_split to latch. */
+ e = redirect_edge_and_branch (edge_at_split, latch);
+ gcc_assert (e == edge_at_split);
/* Set the new loop bound. */
gimple_cond_set_rhs (cond_stmt, bound);
+ update_stmt (cond_stmt);
/* Repair the ssa. */
vec<edge_var_map> *v = redirect_edge_var_map_vector (post_inc_edge);
edge_var_map *vm;
gphi_iterator gsi;
+ int i;
for (gsi = gsi_start_phis (header), i = 0;
!gsi_end_p (gsi) && v->iterate (i, &vm);
gsi_next (&gsi), i++)
/* Replace ivtmp/sum_b with ivtmp/sum_c in header phi. */
add_phi_arg (phi, res_c, post_cond_edge, UNKNOWN_LOCATION);
- /* Replace sum_b with sum_c in exit phi. Loop-closed ssa does not hold
- for virtuals, so we cannot get away with exit_block only. */
+ /* Replace sum_b with sum_c in exit phi. */
tree res_b = redirect_edge_var_map_def (vm);
- replace_uses_in_bbs_by (res_b, res_c, exit_dominated);
+ replace_uses_in_bb_by (res_b, res_c, exit_block);
struct reduction_info *red = reduction_phi (reduction_list, phi);
gcc_assert (virtual_operand_p (res_a)
}
}
gcc_assert (gsi_end_p (gsi) && !v->iterate (i, &vm));
- BITMAP_FREE (exit_dominated);
/* Set the preheader argument of the new phis to ivtmp/sum_init. */
flush_pending_stmts (entry);
/* Set the latch arguments of the new phis to ivtmp/sum_b. */
flush_pending_stmts (post_inc_edge);
- /* Register the reduction exit phis. */
+
+ basic_block new_exit_block = NULL;
+ if (!single_pred_p (exit->dest))
+ {
+ /* Create a new empty exit block, inbetween the new loop header and the
+ old exit block. The function separate_decls_in_region needs this block
+ to insert code that is active on loop exit, but not any other path. */
+ new_exit_block = split_edge (exit);
+ }
+
+ /* Insert and register the reduction exit phis. */
for (gphi_iterator gsi = gsi_start_phis (exit_block);
!gsi_end_p (gsi);
gsi_next (&gsi))
{
gphi *phi = gsi.phi ();
+ gphi *nphi = NULL;
tree res_z = PHI_RESULT (phi);
+ tree res_c;
+
+ if (new_exit_block != NULL)
+ {
+ /* Now that we have a new exit block, duplicate the phi of the old
+ exit block in the new exit block to preserve loop-closed ssa. */
+ edge succ_new_exit_block = single_succ_edge (new_exit_block);
+ edge pred_new_exit_block = single_pred_edge (new_exit_block);
+ tree res_y = copy_ssa_name (res_z, phi);
+ nphi = create_phi_node (res_y, new_exit_block);
+ res_c = PHI_ARG_DEF_FROM_EDGE (phi, succ_new_exit_block);
+ add_phi_arg (nphi, res_c, pred_new_exit_block, UNKNOWN_LOCATION);
+ add_phi_arg (phi, res_y, succ_new_exit_block, UNKNOWN_LOCATION);
+ }
+ else
+ res_c = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+
if (virtual_operand_p (res_z))
continue;
- tree res_c = PHI_ARG_DEF_FROM_EDGE (phi, exit);
- gimple reduc_phi = SSA_NAME_DEF_STMT (res_c);
+ gimple *reduc_phi = SSA_NAME_DEF_STMT (res_c);
struct reduction_info *red = reduction_phi (reduction_list, reduc_phi);
if (red != NULL)
- red->keep_res = phi;
+ red->keep_res = (nphi != NULL
+ ? nphi
+ : phi);
}
/* We're going to cancel the loop at the end of gen_parallel_loop, but until
/* Recalculate dominance info. */
free_dominance_info (CDI_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
+
+ checking_verify_ssa (true, true);
}
/* Tries to moves the exit condition of LOOP to the beginning of its header
transformation is successful. */
static bool
-try_transform_to_exit_first_loop_alt (struct loop *loop,
+try_transform_to_exit_first_loop_alt (class loop *loop,
reduction_info_table_type *reduction_list,
tree nit)
{
if (!gimple_seq_nondebug_singleton_p (bb_seq (loop->latch)))
return false;
+ /* Check whether the latch contains no phis. */
+ if (phi_nodes (loop->latch) != NULL)
+ return false;
+
/* Check whether the latch contains the loop iv increment. */
edge back = single_succ_edge (loop->latch);
edge exit = single_dom_exit (loop);
/* Figure out whether nit + 1 overflows. */
if (TREE_CODE (nit) == INTEGER_CST)
{
- if (!tree_int_cst_equal (nit, TYPE_MAXVAL (nit_type)))
+ if (!tree_int_cst_equal (nit, TYPE_MAX_VALUE (nit_type)))
{
alt_bound = fold_build2_loc (UNKNOWN_LOCATION, PLUS_EXPR, nit_type,
nit, build_one_cst (nit_type));
gcc_assert (TREE_CODE (alt_bound) == INTEGER_CST);
+ transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
+ return true;
}
else
{
/* Todo: Figure out if we can trigger this, if it's worth to handle
optimally, and if we can handle it optimally. */
+ return false;
}
}
- else
- {
- gcc_assert (TREE_CODE (nit) == SSA_NAME);
- gimple def = SSA_NAME_DEF_STMT (nit);
+ gcc_assert (TREE_CODE (nit) == SSA_NAME);
- if (def
- && is_gimple_assign (def)
- && gimple_assign_rhs_code (def) == PLUS_EXPR)
- {
- tree op1 = gimple_assign_rhs1 (def);
- tree op2 = gimple_assign_rhs2 (def);
- if (integer_minus_onep (op1))
- alt_bound = op2;
- else if (integer_minus_onep (op2))
- alt_bound = op1;
- }
+ /* Variable nit is the loop bound as returned by canonicalize_loop_ivs, for an
+ iv with base 0 and step 1 that is incremented in the latch, like this:
- /* There is a number of test-cases for which we don't get an alt_bound
- here: they're listed here, with the lhs of the last stmt as the nit:
+ <bb header>:
+ # iv_1 = PHI <0 (preheader), iv_2 (latch)>
+ ...
+ if (iv_1 < nit)
+ goto <bb latch>;
+ else
+ goto <bb exit>;
- libgomp.graphite/force-parallel-1.c:
- _21 = (signed long) N_6(D);
- _19 = _21 + -1;
- _7 = (unsigned long) _19;
+ <bb latch>:
+ iv_2 = iv_1 + 1;
+ goto <bb header>;
- libgomp.graphite/force-parallel-2.c:
- _33 = (signed long) N_9(D);
- _16 = _33 + -1;
- _37 = (unsigned long) _16;
+ The range of iv_1 is [0, nit]. The latch edge is taken for
+ iv_1 == [0, nit - 1] and the exit edge is taken for iv_1 == nit. So the
+ number of latch executions is equal to nit.
- libgomp.graphite/force-parallel-5.c:
- <bb 6>:
- # graphite_IV.5_46 = PHI <0(5), graphite_IV.5_47(11)>
- <bb 7>:
- _33 = (unsigned long) graphite_IV.5_46;
+ The function max_loop_iterations gives us the maximum number of latch
+ executions, so it gives us the maximum value of nit. */
+ widest_int nit_max;
+ if (!max_loop_iterations (loop, &nit_max))
+ return false;
- g++.dg/tree-ssa/pr34355.C:
- _2 = (unsigned int) i_9;
- _3 = 4 - _2;
+ /* Check if nit + 1 overflows. */
+ widest_int type_max = wi::to_widest (TYPE_MAX_VALUE (nit_type));
+ if (nit_max >= type_max)
+ return false;
- gcc.dg/pr53849.c:
- _5 = d.0_11 + -2;
- _18 = (unsigned int) _5;
+ gimple *def = SSA_NAME_DEF_STMT (nit);
- We will be able to handle some of these cases, if we can determine when
- it's safe to look past casts. */
+ /* Try to find nit + 1, in the form of n in an assignment nit = n - 1. */
+ if (def
+ && is_gimple_assign (def)
+ && gimple_assign_rhs_code (def) == PLUS_EXPR)
+ {
+ tree op1 = gimple_assign_rhs1 (def);
+ tree op2 = gimple_assign_rhs2 (def);
+ if (integer_minus_onep (op1))
+ alt_bound = op2;
+ else if (integer_minus_onep (op2))
+ alt_bound = op1;
}
+ /* If not found, insert nit + 1. */
if (alt_bound == NULL_TREE)
- return false;
+ {
+ alt_bound = fold_build2 (PLUS_EXPR, nit_type, nit,
+ build_int_cst_type (nit_type, 1));
+
+ gimple_stmt_iterator gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
+
+ alt_bound
+ = force_gimple_operand_gsi (&gsi, alt_bound, true, NULL_TREE, false,
+ GSI_CONTINUE_LINKING);
+ }
transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
return true;
LOOP. */
static void
-transform_to_exit_first_loop (struct loop *loop,
+transform_to_exit_first_loop (class loop *loop,
reduction_info_table_type *reduction_list,
tree nit)
{
PHI_RESULT of this phi is the resulting value of the reduction
variable when exiting the loop. */
- if (reduction_list->elements () > 0)
+ if (!reduction_list->is_empty ())
{
struct reduction_info *red;
/* Create the parallel constructs for LOOP as described in gen_parallel_loop.
LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
NEW_DATA is the variable that should be initialized from the argument
- of LOOP_FN. N_THREADS is the requested number of threads. Returns the
- basic block containing GIMPLE_OMP_PARALLEL tree. */
+ of LOOP_FN. N_THREADS is the requested number of threads, which can be 0 if
+ that number is to be determined later. */
-static basic_block
-create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
- tree new_data, unsigned n_threads, location_t loc)
+static void
+create_parallel_loop (class loop *loop, tree loop_fn, tree data,
+ tree new_data, unsigned n_threads, location_t loc,
+ bool oacc_kernels_p)
{
gimple_stmt_iterator gsi;
- basic_block bb, paral_bb, for_bb, ex_bb;
+ basic_block for_bb, ex_bb, continue_bb;
tree t, param;
gomp_parallel *omp_par_stmt;
- gimple omp_return_stmt1, omp_return_stmt2;
- gimple phi;
+ gimple *omp_return_stmt1, *omp_return_stmt2;
+ gimple *phi;
gcond *cond_stmt;
gomp_for *for_stmt;
gomp_continue *omp_cont_stmt;
tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
edge exit, nexit, guard, end, e;
- /* Prepare the GIMPLE_OMP_PARALLEL statement. */
- bb = loop_preheader_edge (loop)->src;
- paral_bb = single_pred (bb);
- gsi = gsi_last_bb (paral_bb);
+ if (oacc_kernels_p)
+ {
+ gcc_checking_assert (lookup_attribute ("oacc kernels",
+ DECL_ATTRIBUTES (cfun->decl)));
+ /* Indicate to later processing that this is a parallelized OpenACC
+ kernels construct. */
+ DECL_ATTRIBUTES (cfun->decl)
+ = tree_cons (get_identifier ("oacc kernels parallelized"),
+ NULL_TREE, DECL_ATTRIBUTES (cfun->decl));
+ }
+ else
+ {
+ /* Prepare the GIMPLE_OMP_PARALLEL statement. */
- t = build_omp_clause (loc, OMP_CLAUSE_NUM_THREADS);
- OMP_CLAUSE_NUM_THREADS_EXPR (t)
- = build_int_cst (integer_type_node, n_threads);
- omp_par_stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
- gimple_set_location (omp_par_stmt, loc);
+ basic_block bb = loop_preheader_edge (loop)->src;
+ basic_block paral_bb = single_pred (bb);
+ gsi = gsi_last_bb (paral_bb);
- gsi_insert_after (&gsi, omp_par_stmt, GSI_NEW_STMT);
+ gcc_checking_assert (n_threads != 0);
+ t = build_omp_clause (loc, OMP_CLAUSE_NUM_THREADS);
+ OMP_CLAUSE_NUM_THREADS_EXPR (t)
+ = build_int_cst (integer_type_node, n_threads);
+ omp_par_stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
+ gimple_set_location (omp_par_stmt, loc);
- /* Initialize NEW_DATA. */
- if (data)
- {
- gassign *assign_stmt;
+ gsi_insert_after (&gsi, omp_par_stmt, GSI_NEW_STMT);
- gsi = gsi_after_labels (bb);
+ /* Initialize NEW_DATA. */
+ if (data)
+ {
+ gassign *assign_stmt;
- param = make_ssa_name (DECL_ARGUMENTS (loop_fn));
- assign_stmt = gimple_build_assign (param, build_fold_addr_expr (data));
- gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
+ gsi = gsi_after_labels (bb);
- assign_stmt = gimple_build_assign (new_data,
- fold_convert (TREE_TYPE (new_data), param));
- gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
- }
+ param = make_ssa_name (DECL_ARGUMENTS (loop_fn));
+ assign_stmt = gimple_build_assign (param, build_fold_addr_expr (data));
+ gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
- /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
- bb = split_loop_exit_edge (single_dom_exit (loop));
- gsi = gsi_last_bb (bb);
- omp_return_stmt1 = gimple_build_omp_return (false);
- gimple_set_location (omp_return_stmt1, loc);
- gsi_insert_after (&gsi, omp_return_stmt1, GSI_NEW_STMT);
+ assign_stmt = gimple_build_assign (new_data,
+ fold_convert (TREE_TYPE (new_data), param));
+ gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
+ }
+
+ /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
+ bb = split_loop_exit_edge (single_dom_exit (loop));
+ gsi = gsi_last_bb (bb);
+ omp_return_stmt1 = gimple_build_omp_return (false);
+ gimple_set_location (omp_return_stmt1, loc);
+ gsi_insert_after (&gsi, omp_return_stmt1, GSI_NEW_STMT);
+ }
/* Extract data for GIMPLE_OMP_FOR. */
gcc_assert (loop->header == single_dom_exit (loop)->src);
gcc_assert (exit == single_dom_exit (loop));
guard = make_edge (for_bb, ex_bb, 0);
- single_succ_edge (loop->latch)->flags = 0;
- end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
+ /* FIXME: What is the probability? */
+ guard->probability = profile_probability::guessed_never ();
+ /* Split the latch edge, so LOOPS_HAVE_SIMPLE_LATCHES is still valid. */
+ loop->latch = split_edge (single_succ_edge (loop->latch));
+ single_pred_edge (loop->latch)->flags = 0;
+ end = make_single_succ_edge (single_pred (loop->latch), ex_bb, EDGE_FALLTHRU);
+ rescan_loop_exit (end, true, false);
+
for (gphi_iterator gpi = gsi_start_phis (ex_bb);
!gsi_end_p (gpi); gsi_next (&gpi))
{
- source_location locus;
- tree def;
+ location_t locus;
gphi *phi = gpi.phi ();
- gphi *stmt;
+ tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (def);
- stmt = as_a <gphi *> (
- SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit)));
+ /* If the exit phi is not connected to a header phi in the same loop, this
+ value is not modified in the loop, and we're done with this phi. */
+ if (!(gimple_code (def_stmt) == GIMPLE_PHI
+ && gimple_bb (def_stmt) == loop->header))
+ {
+ locus = gimple_phi_arg_location_from_edge (phi, exit);
+ add_phi_arg (phi, def, guard, locus);
+ add_phi_arg (phi, def, end, locus);
+ continue;
+ }
+ gphi *stmt = as_a <gphi *> (def_stmt);
def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
locus = gimple_phi_arg_location_from_edge (stmt,
loop_preheader_edge (loop));
PENDING_STMT (e) = NULL;
/* Emit GIMPLE_OMP_FOR. */
+ if (oacc_kernels_p)
+ /* Parallelized OpenACC kernels constructs use gang parallelism. See also
+ omp-offload.c:execute_oacc_device_lower. */
+ t = build_omp_clause (loc, OMP_CLAUSE_GANG);
+ else
+ {
+ t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
+ int chunk_size = param_parloops_chunk_size;
+ switch (param_parloops_schedule)
+ {
+ case PARLOOPS_SCHEDULE_STATIC:
+ OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
+ break;
+ case PARLOOPS_SCHEDULE_DYNAMIC:
+ OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_DYNAMIC;
+ break;
+ case PARLOOPS_SCHEDULE_GUIDED:
+ OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_GUIDED;
+ break;
+ case PARLOOPS_SCHEDULE_AUTO:
+ OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_AUTO;
+ chunk_size = 0;
+ break;
+ case PARLOOPS_SCHEDULE_RUNTIME:
+ OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_RUNTIME;
+ chunk_size = 0;
+ break;
+ default:
+ gcc_unreachable ();
+ }
+ if (chunk_size != 0)
+ OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t)
+ = build_int_cst (integer_type_node, chunk_size);
+ }
+
+ for_stmt = gimple_build_omp_for (NULL,
+ (oacc_kernels_p
+ ? GF_OMP_FOR_KIND_OACC_LOOP
+ : GF_OMP_FOR_KIND_FOR),
+ t, 1, NULL);
+
gimple_cond_set_lhs (cond_stmt, cvar_base);
type = TREE_TYPE (cvar);
- t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
- OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
-
- for_stmt = gimple_build_omp_for (NULL, GF_OMP_FOR_KIND_FOR, t, 1, NULL);
gimple_set_location (for_stmt, loc);
gimple_omp_for_set_index (for_stmt, 0, initvar);
gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
SSA_NAME_DEF_STMT (initvar) = for_stmt;
/* Emit GIMPLE_OMP_CONTINUE. */
- gsi = gsi_last_bb (loop->latch);
+ continue_bb = single_pred (loop->latch);
+ gsi = gsi_last_bb (continue_bb);
omp_cont_stmt = gimple_build_omp_continue (cvar_next, cvar);
gimple_set_location (omp_cont_stmt, loc);
gsi_insert_after (&gsi, omp_cont_stmt, GSI_NEW_STMT);
/* After the above dom info is hosed. Re-compute it. */
free_dominance_info (CDI_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
+}
+
+/* Return number of phis in bb. If COUNT_VIRTUAL_P is false, don't count the
+ virtual phi. */
- return paral_bb;
+static unsigned int
+num_phis (basic_block bb, bool count_virtual_p)
+{
+ unsigned int nr_phis = 0;
+ gphi_iterator gsi;
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ if (!count_virtual_p && virtual_operand_p (PHI_RESULT (gsi.phi ())))
+ continue;
+
+ nr_phis++;
+ }
+
+ return nr_phis;
}
/* Generates code to execute the iterations of LOOP in N_THREADS
- threads in parallel.
+ threads in parallel, which can be 0 if that number is to be determined
+ later.
NITER describes number of iterations of LOOP.
REDUCTION_LIST describes the reductions existent in the LOOP. */
static void
-gen_parallel_loop (struct loop *loop,
+gen_parallel_loop (class loop *loop,
reduction_info_table_type *reduction_list,
- unsigned n_threads, struct tree_niter_desc *niter)
+ unsigned n_threads, class tree_niter_desc *niter,
+ bool oacc_kernels_p)
{
tree many_iterations_cond, type, nit;
tree arg_struct, new_arg_struct;
gimple_seq stmts;
edge entry, exit;
struct clsn_data clsn_data;
- unsigned prob;
location_t loc;
- gimple cond_stmt;
+ gimple *cond_stmt;
unsigned int m_p_thread=2;
/* From
if (stmts)
gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
- if (loop->inner)
- m_p_thread=2;
- else
- m_p_thread=MIN_PER_THREAD;
-
- many_iterations_cond =
- fold_build2 (GE_EXPR, boolean_type_node,
- nit, build_int_cst (type, m_p_thread * n_threads));
-
- many_iterations_cond
- = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
- invert_truthvalue (unshare_expr (niter->may_be_zero)),
- many_iterations_cond);
- many_iterations_cond
- = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
- if (stmts)
- gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
- if (!is_gimple_condexpr (many_iterations_cond))
+ if (!oacc_kernels_p)
{
+ if (loop->inner)
+ m_p_thread=2;
+ else
+ m_p_thread=MIN_PER_THREAD;
+
+ gcc_checking_assert (n_threads != 0);
+ many_iterations_cond =
+ fold_build2 (GE_EXPR, boolean_type_node,
+ nit, build_int_cst (type, m_p_thread * n_threads - 1));
+
many_iterations_cond
- = force_gimple_operand (many_iterations_cond, &stmts,
- true, NULL_TREE);
+ = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ invert_truthvalue (unshare_expr (niter->may_be_zero)),
+ many_iterations_cond);
+ many_iterations_cond
+ = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
if (stmts)
gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
- }
+ if (!is_gimple_condexpr (many_iterations_cond))
+ {
+ many_iterations_cond
+ = force_gimple_operand (many_iterations_cond, &stmts,
+ true, NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop),
+ stmts);
+ }
- initialize_original_copy_tables ();
+ initialize_original_copy_tables ();
- /* We assume that the loop usually iterates a lot. */
- prob = 4 * REG_BR_PROB_BASE / 5;
- loop_version (loop, many_iterations_cond, NULL,
- prob, prob, REG_BR_PROB_BASE - prob, true);
- update_ssa (TODO_update_ssa);
- free_original_copy_tables ();
+ /* We assume that the loop usually iterates a lot. */
+ loop_version (loop, many_iterations_cond, NULL,
+ profile_probability::likely (),
+ profile_probability::unlikely (),
+ profile_probability::likely (),
+ profile_probability::unlikely (), true);
+ update_ssa (TODO_update_ssa);
+ free_original_copy_tables ();
+ }
/* Base all the induction variables in LOOP on a single control one. */
canonicalize_loop_ivs (loop, &nit, true);
+ if (num_phis (loop->header, false) != reduction_list->elements () + 1)
+ {
+ /* The call to canonicalize_loop_ivs above failed to "base all the
+ induction variables in LOOP on a single control one". Do damage
+ control. */
+ basic_block preheader = loop_preheader_edge (loop)->src;
+ basic_block cond_bb = single_pred (preheader);
+ gcond *cond = as_a <gcond *> (gsi_stmt (gsi_last_bb (cond_bb)));
+ gimple_cond_make_true (cond);
+ update_stmt (cond);
+ /* We've gotten rid of the duplicate loop created by loop_version, but
+ we can't undo whatever canonicalize_loop_ivs has done.
+ TODO: Fix this properly by ensuring that the call to
+ canonicalize_loop_ivs succeeds. */
+ if (dump_file
+ && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "canonicalize_loop_ivs failed for loop %d,"
+ " aborting transformation\n", loop->num);
+ return;
+ }
/* Ensure that the exit condition is the first statement in the loop.
The common case is that latch of the loop is empty (apart from the
increment) and immediately follows the loop exit test. Attempt to move the
entry of the loop directly before the exit check and increase the number of
iterations of the loop by one. */
- if (!try_transform_to_exit_first_loop_alt (loop, reduction_list, nit))
+ if (try_transform_to_exit_first_loop_alt (loop, reduction_list, nit))
+ {
+ if (dump_file
+ && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "alternative exit-first loop transform succeeded"
+ " for loop %d\n", loop->num);
+ }
+ else
{
+ if (oacc_kernels_p)
+ n_threads = 1;
+
/* Fall back on the method that handles more cases, but duplicates the
loop body: move the exit condition of LOOP to the beginning of its
header, and duplicate the part of the last iteration that gets disabled
}
/* Generate initializations for reductions. */
- if (reduction_list->elements () > 0)
- reduction_list->traverse <struct loop *, initialize_reductions> (loop);
+ if (!reduction_list->is_empty ())
+ reduction_list->traverse <class loop *, initialize_reductions> (loop);
/* Eliminate the references to local variables from the loop. */
gcc_assert (single_exit (loop));
entry = loop_preheader_edge (loop);
exit = single_dom_exit (loop);
- eliminate_local_variables (entry, exit);
- /* In the old loop, move all variables non-local to the loop to a structure
- and back, and create separate decls for the variables used in loop. */
- separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
- &new_arg_struct, &clsn_data);
+ /* This rewrites the body in terms of new variables. This has already
+ been done for oacc_kernels_p in pass_lower_omp/lower_omp (). */
+ if (!oacc_kernels_p)
+ {
+ eliminate_local_variables (entry, exit);
+ /* In the old loop, move all variables non-local to the loop to a
+ structure and back, and create separate decls for the variables used in
+ loop. */
+ separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
+ &new_arg_struct, &clsn_data);
+ }
+ else
+ {
+ arg_struct = NULL_TREE;
+ new_arg_struct = NULL_TREE;
+ clsn_data.load = NULL_TREE;
+ clsn_data.load_bb = exit->dest;
+ clsn_data.store = NULL_TREE;
+ clsn_data.store_bb = NULL;
+ }
/* Create the parallel constructs. */
loc = UNKNOWN_LOCATION;
cond_stmt = last_stmt (loop->header);
if (cond_stmt)
loc = gimple_location (cond_stmt);
- create_parallel_loop (loop, create_loop_fn (loc), arg_struct,
- new_arg_struct, n_threads, loc);
- if (reduction_list->elements () > 0)
+ create_parallel_loop (loop, create_loop_fn (loc), arg_struct, new_arg_struct,
+ n_threads, loc, oacc_kernels_p);
+ if (!reduction_list->is_empty ())
create_call_for_reduction (loop, reduction_list, &clsn_data);
scev_reset ();
- /* Cancel the loop (it is simpler to do it here rather than to teach the
- expander to do it). */
- cancel_loop_tree (loop);
-
/* Free loop bound estimations that could contain references to
removed statements. */
- FOR_EACH_LOOP (loop, 0)
- free_numbers_of_iterations_estimates_loop (loop);
+ free_numbers_of_iterations_estimates (cfun);
}
/* Returns true when LOOP contains vector phi nodes. */
static bool
-loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
+loop_has_vector_phi_nodes (class loop *loop ATTRIBUTE_UNUSED)
{
unsigned i;
basic_block *bbs = get_loop_body_in_dom_order (loop);
static void
build_new_reduction (reduction_info_table_type *reduction_list,
- gimple reduc_stmt, gphi *phi)
+ gimple *reduc_stmt, gphi *phi)
{
reduction_info **slot;
struct reduction_info *new_reduction;
+ enum tree_code reduction_code;
gcc_assert (reduc_stmt);
+ if (gimple_code (reduc_stmt) == GIMPLE_PHI)
+ {
+ tree op1 = PHI_ARG_DEF (reduc_stmt, 0);
+ gimple *def1 = SSA_NAME_DEF_STMT (op1);
+ reduction_code = gimple_assign_rhs_code (def1);
+ }
+ else
+ reduction_code = gimple_assign_rhs_code (reduc_stmt);
+ /* Check for OpenMP supported reduction. */
+ switch (reduction_code)
+ {
+ case PLUS_EXPR:
+ case MULT_EXPR:
+ case MAX_EXPR:
+ case MIN_EXPR:
+ case BIT_IOR_EXPR:
+ case BIT_XOR_EXPR:
+ case BIT_AND_EXPR:
+ case TRUTH_OR_EXPR:
+ case TRUTH_XOR_EXPR:
+ case TRUTH_AND_EXPR:
+ break;
+ default:
+ return;
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
- "Detected reduction. reduction stmt is: \n");
- print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
+ "Detected reduction. reduction stmt is:\n");
+ print_gimple_stmt (dump_file, reduc_stmt, 0);
fprintf (dump_file, "\n");
}
new_reduction->reduc_stmt = reduc_stmt;
new_reduction->reduc_phi = phi;
new_reduction->reduc_version = SSA_NAME_VERSION (gimple_phi_result (phi));
- new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
+ new_reduction->reduction_code = reduction_code;
slot = reduction_list->find_slot (new_reduction, INSERT);
*slot = new_reduction;
}
return 1;
}
+/* Return true if the type of reduction performed by STMT_INFO is suitable
+ for this pass. */
+
+static bool
+valid_reduction_p (stmt_vec_info stmt_info)
+{
+ /* Parallelization would reassociate the operation, which isn't
+ allowed for in-order reductions. */
+ vect_reduction_type reduc_type = STMT_VINFO_REDUC_TYPE (stmt_info);
+ return reduc_type != FOLD_LEFT_REDUCTION;
+}
+
/* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
static void
{
gphi_iterator gsi;
loop_vec_info simple_loop_info;
+ auto_vec<gphi *, 4> double_reduc_phis;
+ auto_vec<gimple *, 4> double_reduc_stmts;
- simple_loop_info = vect_analyze_loop_form (loop);
+ vec_info_shared shared;
+ simple_loop_info = vect_analyze_loop_form (loop, &shared);
+ if (simple_loop_info == NULL)
+ goto gather_done;
for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
{
if (virtual_operand_p (res))
continue;
- if (!simple_iv (loop, loop, res, &iv, true)
- && simple_loop_info)
+ if (simple_iv (loop, loop, res, &iv, true))
+ continue;
+
+ stmt_vec_info reduc_stmt_info
+ = parloops_force_simple_reduction (simple_loop_info,
+ simple_loop_info->lookup_stmt (phi),
+ &double_reduc, true);
+ if (!reduc_stmt_info || !valid_reduction_p (reduc_stmt_info))
+ continue;
+
+ if (double_reduc)
{
- gimple reduc_stmt = vect_force_simple_reduction (simple_loop_info,
- phi, true,
- &double_reduc);
- if (reduc_stmt && !double_reduc)
- build_new_reduction (reduction_list, reduc_stmt, phi);
- }
+ if (loop->inner->inner != NULL)
+ continue;
+
+ double_reduc_phis.safe_push (phi);
+ double_reduc_stmts.safe_push (reduc_stmt_info->stmt);
+ continue;
+ }
+
+ build_new_reduction (reduction_list, reduc_stmt_info->stmt, phi);
}
- destroy_loop_vec_info (simple_loop_info, true);
+ delete simple_loop_info;
+
+ if (!double_reduc_phis.is_empty ())
+ {
+ vec_info_shared shared;
+ simple_loop_info = vect_analyze_loop_form (loop->inner, &shared);
+ if (simple_loop_info)
+ {
+ gphi *phi;
+ unsigned int i;
+
+ FOR_EACH_VEC_ELT (double_reduc_phis, i, phi)
+ {
+ affine_iv iv;
+ tree res = PHI_RESULT (phi);
+ bool double_reduc;
+
+ use_operand_p use_p;
+ gimple *inner_stmt;
+ bool single_use_p = single_imm_use (res, &use_p, &inner_stmt);
+ gcc_assert (single_use_p);
+ if (gimple_code (inner_stmt) != GIMPLE_PHI)
+ continue;
+ gphi *inner_phi = as_a <gphi *> (inner_stmt);
+ if (simple_iv (loop->inner, loop->inner, PHI_RESULT (inner_phi),
+ &iv, true))
+ continue;
+
+ stmt_vec_info inner_phi_info
+ = simple_loop_info->lookup_stmt (inner_phi);
+ stmt_vec_info inner_reduc_stmt_info
+ = parloops_force_simple_reduction (simple_loop_info,
+ inner_phi_info,
+ &double_reduc, true);
+ gcc_assert (!double_reduc);
+ if (!inner_reduc_stmt_info
+ || !valid_reduction_p (inner_reduc_stmt_info))
+ continue;
+
+ build_new_reduction (reduction_list, double_reduc_stmts[i], phi);
+ }
+ delete simple_loop_info;
+ }
+ }
+
+ gather_done:
+ if (reduction_list->is_empty ())
+ return;
/* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
- and destroy_loop_vec_info, we can set gimple_uid of reduc_phi stmts
- only now. */
+ and delete simple_loop_info, we can set gimple_uid of reduc_phi stmts only
+ now. */
+ basic_block bb;
+ FOR_EACH_BB_FN (bb, cfun)
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ gimple_set_uid (gsi_stmt (gsi), (unsigned int)-1);
reduction_list->traverse <void *, set_reduc_phi_uids> (NULL);
}
/* Try to initialize NITER for code generation part. */
static bool
-try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
+try_get_loop_niter (loop_p loop, class tree_niter_desc *niter)
{
edge exit = single_dom_exit (loop);
return true;
}
+/* Return the default def of the first function argument. */
+
+static tree
+get_omp_data_i_param (void)
+{
+ tree decl = DECL_ARGUMENTS (cfun->decl);
+ gcc_assert (DECL_CHAIN (decl) == NULL_TREE);
+ return ssa_default_def (cfun, decl);
+}
+
+/* For PHI in loop header of LOOP, look for pattern:
+
+ <bb preheader>
+ .omp_data_i = &.omp_data_arr;
+ addr = .omp_data_i->sum;
+ sum_a = *addr;
+
+ <bb header>:
+ sum_b = PHI <sum_a (preheader), sum_c (latch)>
+
+ and return addr. Otherwise, return NULL_TREE. */
+
+static tree
+find_reduc_addr (class loop *loop, gphi *phi)
+{
+ edge e = loop_preheader_edge (loop);
+ tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ gimple *stmt = SSA_NAME_DEF_STMT (arg);
+ if (!gimple_assign_single_p (stmt))
+ return NULL_TREE;
+ tree memref = gimple_assign_rhs1 (stmt);
+ if (TREE_CODE (memref) != MEM_REF)
+ return NULL_TREE;
+ tree addr = TREE_OPERAND (memref, 0);
+
+ gimple *stmt2 = SSA_NAME_DEF_STMT (addr);
+ if (!gimple_assign_single_p (stmt2))
+ return NULL_TREE;
+ tree compref = gimple_assign_rhs1 (stmt2);
+ if (TREE_CODE (compref) != COMPONENT_REF)
+ return NULL_TREE;
+ tree addr2 = TREE_OPERAND (compref, 0);
+ if (TREE_CODE (addr2) != MEM_REF)
+ return NULL_TREE;
+ addr2 = TREE_OPERAND (addr2, 0);
+ if (TREE_CODE (addr2) != SSA_NAME
+ || addr2 != get_omp_data_i_param ())
+ return NULL_TREE;
+
+ return addr;
+}
+
/* Try to initialize REDUCTION_LIST for code generation part.
REDUCTION_LIST describes the reductions. */
static bool
try_create_reduction_list (loop_p loop,
- reduction_info_table_type *reduction_list)
+ reduction_info_table_type *reduction_list,
+ bool oacc_kernels_p)
{
edge exit = single_dom_exit (loop);
gphi_iterator gsi;
gcc_assert (exit);
+ /* Try to get rid of exit phis. */
+ final_value_replacement_loop (loop);
+
gather_scalar_reductions (loop, reduction_list);
struct reduction_info *red;
imm_use_iterator imm_iter;
use_operand_p use_p;
- gimple reduc_phi;
+ gimple *reduc_phi;
tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
if (!virtual_operand_p (val))
{
+ if (TREE_CODE (val) != SSA_NAME)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ " FAILED: exit PHI argument invariant.\n");
+ return false;
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "phi is ");
- print_gimple_stmt (dump_file, phi, 0, 0);
+ print_gimple_stmt (dump_file, phi, 0);
fprintf (dump_file, "arg of phi to exit: value ");
- print_generic_expr (dump_file, val, 0);
+ print_generic_expr (dump_file, val);
fprintf (dump_file, " used outside loop\n");
fprintf (dump_file,
- " checking if it a part of reduction pattern: \n");
+ " checking if it is part of reduction pattern:\n");
}
- if (reduction_list->elements () == 0)
+ if (reduction_list->is_empty ())
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
" FAILED: it is not a part of reduction.\n");
return false;
}
+ if (red->keep_res != NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ " FAILED: reduction has multiple exit phis.\n");
+ return false;
+ }
+ red->keep_res = phi;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "reduction phi is ");
- print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
+ print_gimple_stmt (dump_file, red->reduc_phi, 0);
fprintf (dump_file, "reduction stmt is ");
- print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
+ print_gimple_stmt (dump_file, red->reduc_stmt, 0);
}
}
}
}
}
+ if (oacc_kernels_p)
+ {
+ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ tree def = PHI_RESULT (phi);
+ affine_iv iv;
+
+ if (!virtual_operand_p (def)
+ && !simple_iv (loop, loop, def, &iv, true))
+ {
+ tree addr = find_reduc_addr (loop, phi);
+ if (addr == NULL_TREE)
+ return false;
+ struct reduction_info *red = reduction_phi (reduction_list, phi);
+ red->reduc_addr = addr;
+ }
+ }
+ }
return true;
}
+/* Return true if LOOP contains phis with ADDR_EXPR in args. */
+
+static bool
+loop_has_phi_with_address_arg (class loop *loop)
+{
+ basic_block *bbs = get_loop_body (loop);
+ bool res = false;
+
+ unsigned i, j;
+ gphi_iterator gsi;
+ for (i = 0; i < loop->num_nodes; i++)
+ for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ for (j = 0; j < gimple_phi_num_args (phi); j++)
+ {
+ tree arg = gimple_phi_arg_def (phi, j);
+ if (TREE_CODE (arg) == ADDR_EXPR)
+ {
+ /* This should be handled by eliminate_local_variables, but that
+ function currently ignores phis. */
+ res = true;
+ goto end;
+ }
+ }
+ }
+ end:
+ free (bbs);
+
+ return res;
+}
+
+/* Return true if memory ref REF (corresponding to the stmt at GSI in
+ REGIONS_BB[I]) conflicts with the statements in REGIONS_BB[I] after gsi,
+ or the statements in REGIONS_BB[I + n]. REF_IS_STORE indicates if REF is a
+ store. Ignore conflicts with SKIP_STMT. */
+
+static bool
+ref_conflicts_with_region (gimple_stmt_iterator gsi, ao_ref *ref,
+ bool ref_is_store, vec<basic_block> region_bbs,
+ unsigned int i, gimple *skip_stmt)
+{
+ basic_block bb = region_bbs[i];
+ gsi_next (&gsi);
+
+ while (true)
+ {
+ for (; !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ if (stmt == skip_stmt)
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, "skipping reduction store: ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ }
+ continue;
+ }
+
+ if (!gimple_vdef (stmt)
+ && !gimple_vuse (stmt))
+ continue;
+
+ if (gimple_code (stmt) == GIMPLE_RETURN)
+ continue;
+
+ if (ref_is_store)
+ {
+ if (ref_maybe_used_by_stmt_p (stmt, ref))
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, "Stmt ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ }
+ return true;
+ }
+ }
+ else
+ {
+ if (stmt_may_clobber_ref_p_1 (stmt, ref))
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, "Stmt ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ }
+ return true;
+ }
+ }
+ }
+ i++;
+ if (i == region_bbs.length ())
+ break;
+ bb = region_bbs[i];
+ gsi = gsi_start_bb (bb);
+ }
+
+ return false;
+}
+
+/* Return true if the bbs in REGION_BBS but not in in_loop_bbs can be executed
+ in parallel with REGION_BBS containing the loop. Return the stores of
+ reduction results in REDUCTION_STORES. */
+
+static bool
+oacc_entry_exit_ok_1 (bitmap in_loop_bbs, vec<basic_block> region_bbs,
+ reduction_info_table_type *reduction_list,
+ bitmap reduction_stores)
+{
+ tree omp_data_i = get_omp_data_i_param ();
+
+ unsigned i;
+ basic_block bb;
+ FOR_EACH_VEC_ELT (region_bbs, i, bb)
+ {
+ if (bitmap_bit_p (in_loop_bbs, bb->index))
+ continue;
+
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ gimple *skip_stmt = NULL;
+
+ if (is_gimple_debug (stmt)
+ || gimple_code (stmt) == GIMPLE_COND)
+ continue;
+
+ ao_ref ref;
+ bool ref_is_store = false;
+ if (gimple_assign_load_p (stmt))
+ {
+ tree rhs = gimple_assign_rhs1 (stmt);
+ tree base = get_base_address (rhs);
+ if (TREE_CODE (base) == MEM_REF
+ && operand_equal_p (TREE_OPERAND (base, 0), omp_data_i, 0))
+ continue;
+
+ tree lhs = gimple_assign_lhs (stmt);
+ if (TREE_CODE (lhs) == SSA_NAME
+ && has_single_use (lhs))
+ {
+ use_operand_p use_p;
+ gimple *use_stmt;
+ struct reduction_info *red;
+ single_imm_use (lhs, &use_p, &use_stmt);
+ if (gimple_code (use_stmt) == GIMPLE_PHI
+ && (red = reduction_phi (reduction_list, use_stmt)))
+ {
+ tree val = PHI_RESULT (red->keep_res);
+ if (has_single_use (val))
+ {
+ single_imm_use (val, &use_p, &use_stmt);
+ if (gimple_store_p (use_stmt))
+ {
+ unsigned int id
+ = SSA_NAME_VERSION (gimple_vdef (use_stmt));
+ bitmap_set_bit (reduction_stores, id);
+ skip_stmt = use_stmt;
+ if (dump_file)
+ {
+ fprintf (dump_file, "found reduction load: ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ }
+ }
+ }
+ }
+ }
+
+ ao_ref_init (&ref, rhs);
+ }
+ else if (gimple_store_p (stmt))
+ {
+ ao_ref_init (&ref, gimple_assign_lhs (stmt));
+ ref_is_store = true;
+ }
+ else if (gimple_code (stmt) == GIMPLE_OMP_RETURN)
+ continue;
+ else if (!gimple_has_side_effects (stmt)
+ && !gimple_could_trap_p (stmt)
+ && !stmt_could_throw_p (cfun, stmt)
+ && !gimple_vdef (stmt)
+ && !gimple_vuse (stmt))
+ continue;
+ else if (gimple_call_internal_p (stmt, IFN_GOACC_DIM_POS))
+ continue;
+ else if (gimple_code (stmt) == GIMPLE_RETURN)
+ continue;
+ else
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, "Unhandled stmt in entry/exit: ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ }
+ return false;
+ }
+
+ if (ref_conflicts_with_region (gsi, &ref, ref_is_store, region_bbs,
+ i, skip_stmt))
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, "conflicts with entry/exit stmt: ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ }
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+/* Find stores inside REGION_BBS and outside IN_LOOP_BBS, and guard them with
+ gang_pos == 0, except when the stores are REDUCTION_STORES. Return true
+ if any changes were made. */
+
+static bool
+oacc_entry_exit_single_gang (bitmap in_loop_bbs, vec<basic_block> region_bbs,
+ bitmap reduction_stores)
+{
+ tree gang_pos = NULL_TREE;
+ bool changed = false;
+
+ unsigned i;
+ basic_block bb;
+ FOR_EACH_VEC_ELT (region_bbs, i, bb)
+ {
+ if (bitmap_bit_p (in_loop_bbs, bb->index))
+ continue;
+
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
+ {
+ gimple *stmt = gsi_stmt (gsi);
+
+ if (!gimple_store_p (stmt))
+ {
+ /* Update gsi to point to next stmt. */
+ gsi_next (&gsi);
+ continue;
+ }
+
+ if (bitmap_bit_p (reduction_stores,
+ SSA_NAME_VERSION (gimple_vdef (stmt))))
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file,
+ "skipped reduction store for single-gang"
+ " neutering: ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ }
+
+ /* Update gsi to point to next stmt. */
+ gsi_next (&gsi);
+ continue;
+ }
+
+ changed = true;
+
+ if (gang_pos == NULL_TREE)
+ {
+ tree arg = build_int_cst (integer_type_node, GOMP_DIM_GANG);
+ gcall *gang_single
+ = gimple_build_call_internal (IFN_GOACC_DIM_POS, 1, arg);
+ gang_pos = make_ssa_name (integer_type_node);
+ gimple_call_set_lhs (gang_single, gang_pos);
+ gimple_stmt_iterator start
+ = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
+ tree vuse = ssa_default_def (cfun, gimple_vop (cfun));
+ gimple_set_vuse (gang_single, vuse);
+ gsi_insert_before (&start, gang_single, GSI_SAME_STMT);
+ }
+
+ if (dump_file)
+ {
+ fprintf (dump_file,
+ "found store that needs single-gang neutering: ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ }
+
+ {
+ /* Split block before store. */
+ gimple_stmt_iterator gsi2 = gsi;
+ gsi_prev (&gsi2);
+ edge e;
+ if (gsi_end_p (gsi2))
+ {
+ e = split_block_after_labels (bb);
+ gsi2 = gsi_last_bb (bb);
+ }
+ else
+ e = split_block (bb, gsi_stmt (gsi2));
+ basic_block bb2 = e->dest;
+
+ /* Split block after store. */
+ gimple_stmt_iterator gsi3 = gsi_start_bb (bb2);
+ edge e2 = split_block (bb2, gsi_stmt (gsi3));
+ basic_block bb3 = e2->dest;
+
+ gimple *cond
+ = gimple_build_cond (EQ_EXPR, gang_pos, integer_zero_node,
+ NULL_TREE, NULL_TREE);
+ gsi_insert_after (&gsi2, cond, GSI_NEW_STMT);
+
+ edge e3 = make_edge (bb, bb3, EDGE_FALSE_VALUE);
+ /* FIXME: What is the probability? */
+ e3->probability = profile_probability::guessed_never ();
+ e->flags = EDGE_TRUE_VALUE;
+
+ tree vdef = gimple_vdef (stmt);
+ tree vuse = gimple_vuse (stmt);
+
+ tree phi_res = copy_ssa_name (vdef);
+ gphi *new_phi = create_phi_node (phi_res, bb3);
+ replace_uses_by (vdef, phi_res);
+ add_phi_arg (new_phi, vuse, e3, UNKNOWN_LOCATION);
+ add_phi_arg (new_phi, vdef, e2, UNKNOWN_LOCATION);
+
+ /* Update gsi to point to next stmt. */
+ bb = bb3;
+ gsi = gsi_start_bb (bb);
+ }
+ }
+ }
+
+ return changed;
+}
+
+/* Return true if the statements before and after the LOOP can be executed in
+ parallel with the function containing the loop. Resolve conflicting stores
+ outside LOOP by guarding them such that only a single gang executes them. */
+
+static bool
+oacc_entry_exit_ok (class loop *loop,
+ reduction_info_table_type *reduction_list)
+{
+ basic_block *loop_bbs = get_loop_body_in_dom_order (loop);
+ vec<basic_block> region_bbs
+ = get_all_dominated_blocks (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (cfun));
+
+ bitmap in_loop_bbs = BITMAP_ALLOC (NULL);
+ bitmap_clear (in_loop_bbs);
+ for (unsigned int i = 0; i < loop->num_nodes; i++)
+ bitmap_set_bit (in_loop_bbs, loop_bbs[i]->index);
+
+ bitmap reduction_stores = BITMAP_ALLOC (NULL);
+ bool res = oacc_entry_exit_ok_1 (in_loop_bbs, region_bbs, reduction_list,
+ reduction_stores);
+
+ if (res)
+ {
+ bool changed = oacc_entry_exit_single_gang (in_loop_bbs, region_bbs,
+ reduction_stores);
+ if (changed)
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_DOMINATORS);
+ }
+ }
+
+ region_bbs.release ();
+ free (loop_bbs);
+
+ BITMAP_FREE (in_loop_bbs);
+ BITMAP_FREE (reduction_stores);
+
+ return res;
+}
+
/* Detect parallel loops and generate parallel code using libgomp
primitives. Returns true if some loop was parallelized, false
otherwise. */
static bool
-parallelize_loops (void)
+parallelize_loops (bool oacc_kernels_p)
{
- unsigned n_threads = flag_tree_parallelize_loops;
+ unsigned n_threads;
bool changed = false;
- struct loop *loop;
- struct tree_niter_desc niter_desc;
+ class loop *loop;
+ class loop *skip_loop = NULL;
+ class tree_niter_desc niter_desc;
struct obstack parloop_obstack;
HOST_WIDE_INT estimated;
- source_location loop_loc;
/* Do not parallelize loops in the functions created by parallelization. */
- if (parallelized_function_p (cfun->decl))
+ if (!oacc_kernels_p
+ && parallelized_function_p (cfun->decl))
return false;
+
+ /* Do not parallelize loops in offloaded functions. */
+ if (!oacc_kernels_p
+ && oacc_get_fn_attrib (cfun->decl) != NULL)
+ return false;
+
if (cfun->has_nonlocal_label)
return false;
+ /* For OpenACC kernels, n_threads will be determined later; otherwise, it's
+ the argument to -ftree-parallelize-loops. */
+ if (oacc_kernels_p)
+ n_threads = 0;
+ else
+ n_threads = flag_tree_parallelize_loops;
+
gcc_obstack_init (&parloop_obstack);
reduction_info_table_type reduction_list (10);
- init_stmt_vec_info_vec ();
+
+ calculate_dominance_info (CDI_DOMINATORS);
FOR_EACH_LOOP (loop, 0)
{
+ if (loop == skip_loop)
+ {
+ if (!loop->in_oacc_kernels_region
+ && dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Skipping loop %d as inner loop of parallelized loop\n",
+ loop->num);
+
+ skip_loop = loop->inner;
+ continue;
+ }
+ else
+ skip_loop = NULL;
+
reduction_list.empty ();
+
+ if (oacc_kernels_p)
+ {
+ if (!loop->in_oacc_kernels_region)
+ continue;
+
+ /* Don't try to parallelize inner loops in an oacc kernels region. */
+ if (loop->inner)
+ skip_loop = loop->inner;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Trying loop %d with header bb %d in oacc kernels"
+ " region\n", loop->num, loop->header->index);
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Trying loop %d as candidate\n",loop->num);
fprintf (dump_file, "loop %d is innermost\n",loop->num);
}
- /* If we use autopar in graphite pass, we use its marked dependency
- checking results. */
- if (flag_loop_parallelize_all && !loop->can_be_parallel)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "loop is not parallel according to graphite\n");
- continue;
- }
-
if (!single_dom_exit (loop))
{
|| loop_has_vector_phi_nodes (loop))
continue;
- estimated = estimated_stmt_executions_int (loop);
+ estimated = estimated_loop_iterations_int (loop);
if (estimated == -1)
- estimated = max_stmt_executions_int (loop);
+ estimated = get_likely_max_loop_iterations_int (loop);
/* FIXME: Bypass this check as graphite doesn't update the
count and frequency correctly now. */
if (!flag_loop_parallelize_all
+ && !oacc_kernels_p
&& ((estimated != -1
- && estimated <= (HOST_WIDE_INT) n_threads * MIN_PER_THREAD)
+ && (estimated
+ < ((HOST_WIDE_INT) n_threads
+ * (loop->inner ? 2 : MIN_PER_THREAD) - 1)))
/* Do not bother with loops in cold areas. */
|| optimize_loop_nest_for_size_p (loop)))
continue;
if (!try_get_loop_niter (loop, &niter_desc))
continue;
- if (!try_create_reduction_list (loop, &reduction_list))
+ if (!try_create_reduction_list (loop, &reduction_list, oacc_kernels_p))
continue;
- if (!flag_loop_parallelize_all
+ if (loop_has_phi_with_address_arg (loop))
+ continue;
+
+ if (!loop->can_be_parallel
&& !loop_parallel_p (loop, &parloop_obstack))
continue;
+ if (oacc_kernels_p
+ && !oacc_entry_exit_ok (loop, &reduction_list))
+ {
+ if (dump_file)
+ fprintf (dump_file, "entry/exit not ok: FAILED\n");
+ continue;
+ }
+
changed = true;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- if (loop->inner)
- fprintf (dump_file, "parallelizing outer loop %d\n",loop->header->index);
- else
- fprintf (dump_file, "parallelizing inner loop %d\n",loop->header->index);
- loop_loc = find_loop_location (loop);
- if (loop_loc != UNKNOWN_LOCATION)
- fprintf (dump_file, "\nloop at %s:%d: ",
- LOCATION_FILE (loop_loc), LOCATION_LINE (loop_loc));
- }
+ skip_loop = loop->inner;
+
+ if (dump_enabled_p ())
+ {
+ dump_user_location_t loop_loc = find_loop_location (loop);
+ if (loop->inner)
+ dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loop_loc,
+ "parallelizing outer loop %d\n", loop->num);
+ else
+ dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loop_loc,
+ "parallelizing inner loop %d\n", loop->num);
+ }
+
gen_parallel_loop (loop, &reduction_list,
- n_threads, &niter_desc);
+ n_threads, &niter_desc, oacc_kernels_p);
}
- free_stmt_vec_info_vec ();
obstack_free (&parloop_obstack, NULL);
/* Parallelization will cause new function calls to be inserted through
{
public:
pass_parallelize_loops (gcc::context *ctxt)
- : gimple_opt_pass (pass_data_parallelize_loops, ctxt)
+ : gimple_opt_pass (pass_data_parallelize_loops, ctxt),
+ oacc_kernels_p (false)
{}
/* opt_pass methods: */
- virtual bool gate (function *) { return flag_tree_parallelize_loops > 1; }
+ virtual bool gate (function *)
+ {
+ if (oacc_kernels_p)
+ return flag_openacc;
+ else
+ return flag_tree_parallelize_loops > 1;
+ }
virtual unsigned int execute (function *);
+ opt_pass * clone () { return new pass_parallelize_loops (m_ctxt); }
+ void set_pass_param (unsigned int n, bool param)
+ {
+ gcc_assert (n == 0);
+ oacc_kernels_p = param;
+ }
+ private:
+ bool oacc_kernels_p;
}; // class pass_parallelize_loops
unsigned
pass_parallelize_loops::execute (function *fun)
{
+ tree nthreads = builtin_decl_explicit (BUILT_IN_OMP_GET_NUM_THREADS);
+ if (nthreads == NULL_TREE)
+ return 0;
+
+ bool in_loop_pipeline = scev_initialized_p ();
+ if (!in_loop_pipeline)
+ loop_optimizer_init (LOOPS_NORMAL
+ | LOOPS_HAVE_RECORDED_EXITS);
+
if (number_of_loops (fun) <= 1)
return 0;
- if (parallelize_loops ())
+ if (!in_loop_pipeline)
+ {
+ rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+ scev_initialize ();
+ }
+
+ unsigned int todo = 0;
+ if (parallelize_loops (oacc_kernels_p))
{
fun->curr_properties &= ~(PROP_gimple_eomp);
- return TODO_update_ssa;
+
+ checking_verify_loop_structure ();
+
+ todo |= TODO_update_ssa;
+ }
+
+ if (!in_loop_pipeline)
+ {
+ scev_finalize ();
+ loop_optimizer_finalize ();
}
- return 0;
+ return todo;
}
} // anon namespace
projects / thirdparty / gcc.git / blobdiff