/* Loop autoparallelization.
- Copyright (C) 2006-2016 Free Software Foundation, Inc.
+ Copyright (C) 2006-2018 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 "tree-vectorizer.h"
#include "tree-hasher.h"
#include "tree-parloops.h"
+#include "omp-general.h"
#include "omp-low.h"
#include "tree-ssa.h"
#include "params.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
/* Minimal number of iterations of a loop that should be executed in each
thread. */
-#define MIN_PER_THREAD 100
+#define MIN_PER_THREAD PARAM_VALUE (PARAM_PARLOOPS_MIN_PER_THREAD)
/* Element of the hashtable, representing a
reduction in the current loop. */
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)
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;
/* 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));
return false;
/* Check if nit + 1 overflows. */
- widest_int type_max = wi::to_widest (TYPE_MAXVAL (nit_type));
- if (!wi::lts_p (nit_max, type_max))
+ widest_int type_max = wi::to_widest (TYPE_MAX_VALUE (nit_type));
+ if (nit_max >= type_max)
return false;
gimple *def = SSA_NAME_DEF_STMT (nit);
/* 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. */
+ of LOOP_FN. N_THREADS is the requested number of threads, which can be 0 if
+ that number is to be determined later. */
static void
create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
edge exit, nexit, guard, end, e;
- /* Prepare the GIMPLE_OMP_PARALLEL statement. */
if (oacc_kernels_p)
{
- tree clause = build_omp_clause (loc, OMP_CLAUSE_NUM_GANGS);
- OMP_CLAUSE_NUM_GANGS_EXPR (clause)
- = build_int_cst (integer_type_node, n_threads);
- set_oacc_fn_attrib (cfun->decl, clause, true, NULL);
+ 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. */
+
basic_block bb = loop_preheader_edge (loop)->src;
basic_block paral_bb = single_pred (bb);
gsi = gsi_last_bb (paral_bb);
+ 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);
gcc_assert (exit == single_dom_exit (loop));
guard = make_edge (for_bb, ex_bb, 0);
+ /* 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_edge (single_pred (loop->latch), ex_bb, EDGE_FALLTHRU);
+ 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);
/* Emit GIMPLE_OMP_FOR. */
if (oacc_kernels_p)
- /* In combination with the NUM_GANGS on the parallel. */
+ /* 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
{
calculate_dominance_info (CDI_DOMINATORS);
}
+/* Return number of phis in bb. If COUNT_VIRTUAL_P is false, don't count the
+ virtual phi. */
+
+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. */
gimple_seq stmts;
edge entry, exit;
struct clsn_data clsn_data;
- unsigned prob;
location_t loc;
gimple *cond_stmt;
unsigned int 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));
+ nit, build_int_cst (type, m_p_thread * n_threads - 1));
many_iterations_cond
= fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
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);
+ 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
/* 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. */
gcc_assert (reduc_stmt);
- 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);
- fprintf (dump_file, "\n");
- }
-
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);
+ fprintf (dump_file, "\n");
+ }
new_reduction = XCNEW (struct reduction_info);
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;
- loop_vec_info simple_inner_loop_info = NULL;
- bool allow_double_reduc = true;
+ auto_vec<gphi *, 4> double_reduc_phis;
+ auto_vec<gimple *, 4> double_reduc_stmts;
- if (!stmt_vec_info_vec.exists ())
- init_stmt_vec_info_vec ();
+ vec<stmt_vec_info> stmt_vec_infos;
+ stmt_vec_infos.create (50);
+ set_stmt_vec_info_vec (&stmt_vec_infos);
- 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;
if (simple_iv (loop, loop, res, &iv, true))
continue;
- gimple *reduc_stmt
- = vect_force_simple_reduction (simple_loop_info, phi, true,
+ stmt_vec_info reduc_stmt_info
+ = vect_force_simple_reduction (simple_loop_info,
+ simple_loop_info->lookup_stmt (phi),
&double_reduc, true);
- if (!reduc_stmt)
+ if (!reduc_stmt_info || !valid_reduction_p (reduc_stmt_info))
continue;
if (double_reduc)
{
- if (!allow_double_reduc
- || loop->inner->inner != NULL)
+ if (loop->inner->inner != NULL)
continue;
- if (!simple_inner_loop_info)
+ 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);
+ }
+ 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)
{
- simple_inner_loop_info = vect_analyze_loop_form (loop->inner);
- if (!simple_inner_loop_info)
- {
- allow_double_reduc = false;
- continue;
- }
- }
+ 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;
- 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
+ = vect_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;
- gimple *inner_reduc_stmt
- = vect_force_simple_reduction (simple_inner_loop_info, inner_phi,
- true, &double_reduc, true);
- gcc_assert (!double_reduc);
- if (inner_reduc_stmt == NULL)
- continue;
+ build_new_reduction (reduction_list, double_reduc_stmts[i], phi);
+ }
+ delete simple_loop_info;
}
-
- build_new_reduction (reduction_list, reduc_stmt, phi);
}
- destroy_loop_vec_info (simple_loop_info, true);
- destroy_loop_vec_info (simple_inner_loop_info, true);
gather_done:
/* Release the claim on gimple_uid. */
- free_stmt_vec_info_vec ();
+ free_stmt_vec_infos (&stmt_vec_infos);
if (reduction_list->elements () == 0)
return;
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 is part of reduction pattern:\n");
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 (dump_file)
{
fprintf (dump_file, "skipping reduction store: ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ print_gimple_stmt (dump_file, stmt, 0);
}
continue;
}
if (dump_file)
{
fprintf (dump_file, "Stmt ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ print_gimple_stmt (dump_file, stmt, 0);
}
return true;
}
if (dump_file)
{
fprintf (dump_file, "Stmt ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ print_gimple_stmt (dump_file, stmt, 0);
}
return true;
}
if (dump_file)
{
fprintf (dump_file, "found reduction load: ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ print_gimple_stmt (dump_file, stmt, 0);
}
}
}
&& !gimple_vdef (stmt)
&& !gimple_vuse (stmt))
continue;
- else if (is_gimple_call (stmt)
- && gimple_call_internal_p (stmt)
- && gimple_call_internal_fn (stmt) == IFN_GOACC_DIM_POS)
+ else if (gimple_call_internal_p (stmt, IFN_GOACC_DIM_POS))
continue;
else if (gimple_code (stmt) == GIMPLE_RETURN)
continue;
if (dump_file)
{
fprintf (dump_file, "Unhandled stmt in entry/exit: ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ print_gimple_stmt (dump_file, stmt, 0);
}
return false;
}
if (dump_file)
{
fprintf (dump_file, "conflicts with entry/exit stmt: ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ print_gimple_stmt (dump_file, stmt, 0);
}
return false;
}
fprintf (dump_file,
"skipped reduction store for single-gang"
" neutering: ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ print_gimple_stmt (dump_file, stmt, 0);
}
/* Update gsi to point to next stmt. */
{
fprintf (dump_file,
"found store that needs single-gang neutering: ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ print_gimple_stmt (dump_file, stmt, 0);
}
{
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);
}
}
+ region_bbs.release ();
free (loop_bbs);
BITMAP_FREE (in_loop_bbs);
static bool
parallelize_loops (bool oacc_kernels_p)
{
- unsigned n_threads = flag_tree_parallelize_loops;
+ unsigned n_threads;
bool changed = false;
struct loop *loop;
struct loop *skip_loop = NULL;
struct 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 (!oacc_kernels_p
/* Do not parallelize loops in offloaded functions. */
if (!oacc_kernels_p
- && get_oacc_fn_attrib (cfun->decl) != NULL)
+ && 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);
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 (loop_has_phi_with_address_arg (loop))
continue;
- if (!flag_loop_parallelize_all
+ if (!loop->can_be_parallel
&& !loop_parallel_p (loop, &parloop_obstack))
continue;
changed = true;
skip_loop = loop->inner;
- 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));
- }
+
+ 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, oacc_kernels_p);
{}
/* 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)
projects / gcc.git / blobdiff