/* Loop autoparallelization.
- Copyright (C) 2006-2014 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 "config.h"
#include "system.h"
#include "coretypes.h"
+#include "backend.h"
#include "tree.h"
-#include "predict.h"
-#include "vec.h"
-#include "hashtab.h"
-#include "hash-set.h"
-#include "machmode.h"
-#include "tm.h"
-#include "hard-reg-set.h"
-#include "input.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 "is-a.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 "tree-ssa.h"
+#include "params.h"
+#include "params-enum.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
/* 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. */
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. */
- gimple keep_res; /* The PHI_RESULT of this phi is the resulting value
+ gphi *keep_res; /* The PHI_RESULT of this phi is the resulting value
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. */
- gimple new_phi; /* (helper field) Newly created phi node whose result
+ gphi *new_phi; /* (helper field) Newly created phi node whose result
will be passed to the atomic operation. Represents
the local result each thread computed for the reduction
operation. */
/* 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 value_type *);
- static inline bool equal (const value_type *, const compare_type *);
+ static inline hashval_t hash (const reduction_info *);
+ static inline bool equal (const reduction_info *, const reduction_info *);
};
/* Equality and hash functions for hashtab code. */
inline bool
-reduction_hasher::equal (const value_type *a, const compare_type *b)
+reduction_hasher::equal (const reduction_info *a, const reduction_info *b)
{
return (a->reduc_phi == b->reduc_phi);
}
inline hashval_t
-reduction_hasher::hash (const value_type *a)
+reduction_hasher::hash (const reduction_info *a)
{
return a->reduc_version;
}
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)
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 value_type *);
- static inline bool equal (const value_type *, const 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 *);
};
/* Equality and hash functions for hashtab code. */
inline bool
-name_to_copy_hasher::equal (const value_type *a, const compare_type *b)
+name_to_copy_hasher::equal (const name_to_copy_elt *a, const name_to_copy_elt *b)
{
return a->version == b->version;
}
inline hashval_t
-name_to_copy_hasher::hash (const value_type *a)
+name_to_copy_hasher::hash (const name_to_copy_elt *a)
{
return (hashval_t) a->version;
}
{
int uid;
tree *var_p, name, addr;
- gimple stmt;
+ gassign *stmt;
gimple_seq stmts;
/* Since the address of OBJ is invariant, the trees may be shared.
if (obj_name)
name = make_temp_ssa_name (TREE_TYPE (addr), NULL, obj_name);
else
- name = make_ssa_name (TREE_TYPE (addr), NULL);
+ name = make_ssa_name (TREE_TYPE (addr));
stmt = gimple_build_assign (name, addr);
gsi_insert_on_edge_immediate (entry, stmt);
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)
{
- 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)
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));
{
struct reduction_info *const reduc = *slot;
edge e;
- gimple new_phi;
- basic_block store_bb;
+ gphi *new_phi;
+ basic_block store_bb, continue_bb;
tree local_res;
source_location 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), NULL);
+ 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;
- e = split_block (bb, t);
+ gsi = gsi_last_bb (bb);
+ e = split_block (bb, gsi_stmt (gsi));
new_bb = e->dest;
- tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
- tmp_load = make_ssa_name (tmp_load, NULL);
+ 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);
SSA_NAME_DEF_STMT (tmp_load) = load;
gsi = gsi_start_bb (new_bb);
{
reduction_list->traverse <struct 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))
{
/* Create the loads and stores. */
*arg_struct = create_tmp_var (type, ".paral_data_store");
nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
- *new_arg_struct = make_ssa_name (nvar, NULL);
+ *new_arg_struct = make_ssa_name (nvar);
ld_st_data->store = *arg_struct;
ld_st_data->load = *new_arg_struct;
reduction_list
->traverse <struct clsn_data *, create_stores_for_reduction>
(ld_st_data);
- clsn_data.load = make_ssa_name (nvar, NULL);
+ clsn_data.load = make_ssa_name (nvar);
clsn_data.load_bb = exit->dest;
clsn_data.store = ld_st_data->store;
create_final_loads_for_reduction (reduction_list, &clsn_data);
}
}
-/* Bitmap containing uids of functions created by parallelization. We cannot
- allocate it from the default obstack, as it must live across compilation
- of several functions; we make it gc allocated instead. */
-
-static GTY(()) bitmap parallelized_functions;
-
-/* Returns true if FN was created by create_loop_fn. */
+/* Returns true if FN was created to run in parallel. */
bool
-parallelized_function_p (tree fn)
+parallelized_function_p (tree fndecl)
{
- if (!parallelized_functions || !DECL_ARTIFICIAL (fn))
- return false;
-
- return bitmap_bit_p (parallelized_functions, DECL_UID (fn));
+ cgraph_node *node = cgraph_node::get (fndecl);
+ gcc_assert (node != NULL);
+ return node->parallelized_function;
}
/* Creates and returns an empty function that will receive the body of
type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
decl = build_decl (loc, FUNCTION_DECL, name, type);
- if (!parallelized_functions)
- parallelized_functions = BITMAP_GGC_ALLOC ();
- bitmap_set_bit (parallelized_functions, DECL_UID (decl));
-
TREE_STATIC (decl) = 1;
TREE_USED (decl) = 1;
DECL_ARTIFICIAL (decl) = 1;
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;
return decl;
}
-/* Moves the exit condition of LOOP to the beginning of its header, and
- duplicates the part of the last iteration that gets disabled to the
- exit of the loop. NIT is the number of iterations of the loop
- (used to initialize the variables in the duplicated part).
+/* Replace uses of NAME by VAL in block BB. */
+
+static void
+replace_uses_in_bb_by (tree name, tree val, basic_block bb)
+{
+ gimple *use_stmt;
+ imm_use_iterator imm_iter;
+
+ FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name)
+ {
+ if (gimple_bb (use_stmt) != bb)
+ 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 header>:
+ ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
+ sum_a = PHI <sum_init (preheader), sum_b (latch)>
+ ...
+ use (ivtmp_a)
+ ...
+ sum_b = sum_a + sum_update
+ ...
+ if (ivtmp_a < n)
+ goto <bb latch>;
+ else
+ goto <bb exit>;
+
+ <bb latch>:
+ ivtmp_b = ivtmp_a + 1;
+ goto <bb header>
+
+ <bb exit>:
+ sum_z = PHI <sum_b (cond[1]), ...>
+
+ [1] Where <bb cond> is single_pred (bb latch); In the simplest case,
+ that's <bb header>.
+
+ to:
+
+ <bb preheader>:
+ ...
+ goto <bb newheader>
+
+ <bb header>:
+ ivtmp_a = PHI <ivtmp_c (latch)>
+ sum_a = PHI <sum_c (latch)>
+ ...
+ use (ivtmp_a)
+ ...
+ sum_b = sum_a + sum_update
+ ...
+ goto <bb latch>;
+
+ <bb newheader>:
+ ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
+ sum_c = PHI <sum_init (preheader), sum_b (latch)>
+ if (ivtmp_c < n + 1)
+ goto <bb header>;
+ else
+ 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_y (newexit), ...>
+
+
+ In unified diff format:
+
+ <bb preheader>:
+ ...
+- goto <bb header>
++ goto <bb newheader>
+
+ <bb header>:
+- ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
+- sum_a = PHI <sum_init (preheader), sum_b (latch)>
++ ivtmp_a = PHI <ivtmp_c (latch)>
++ sum_a = PHI <sum_c (latch)>
+ ...
+ use (ivtmp_a)
+ ...
+ sum_b = sum_a + sum_update
+ ...
+- if (ivtmp_a < n)
+- goto <bb latch>;
++ goto <bb latch>;
++
++ <bb newheader>:
++ ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
++ sum_c = PHI <sum_init (preheader), sum_b (latch)>
++ if (ivtmp_c < n + 1)
++ goto <bb header>;
+ else
+ goto <bb exit>;
- TODO: the common case is that latch of the loop is empty and immediately
- follows the loop exit. In this case, it would be better not to copy the
- body of the loop, but only move the entry of the loop directly before the
- exit check and increase the number of iterations of the loop by one.
- This may need some additional preconditioning in case NIT = ~0.
- REDUCTION_LIST describes the reductions in LOOP. */
+ <bb latch>:
+ ivtmp_b = ivtmp_a + 1;
+- 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_y (newexit), ...>
+
+ Note: the example does not show any virtual phis, but these are handled more
+ or less as reductions.
+
+
+ Moves the exit condition of LOOP to the beginning of its header.
+ REDUCTION_LIST describes the reductions in LOOP. BOUND is the new loop
+ bound. */
+
+static void
+transform_to_exit_first_loop_alt (struct loop *loop,
+ reduction_info_table_type *reduction_list,
+ tree bound)
+{
+ basic_block header = loop->header;
+ basic_block latch = loop->latch;
+ edge exit = single_dom_exit (loop);
+ basic_block exit_block = exit->dest;
+ gcond *cond_stmt = as_a <gcond *> (last_stmt (exit->src));
+ tree control = gimple_cond_lhs (cond_stmt);
+ edge e;
+
+ /* 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 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 (entry, new_header);
+ gcc_assert (e == entry);
+
+ /* Redirect post_inc_edge to new_header. */
+ edge post_inc_edge = single_succ_edge (latch);
+ e = redirect_edge_and_branch (post_inc_edge, new_header);
+ gcc_assert (e == post_inc_edge);
+
+ /* Redirect post_cond_edge to header. */
+ edge post_cond_edge = single_pred_edge (latch);
+ e = redirect_edge_and_branch (post_cond_edge, header);
+ gcc_assert (e == post_cond_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++)
+ {
+ gphi *phi = gsi.phi ();
+ tree res_a = PHI_RESULT (phi);
+
+ /* Create new phi. */
+ tree res_c = copy_ssa_name (res_a, phi);
+ gphi *nphi = create_phi_node (res_c, new_header);
+
+ /* Replace ivtmp_a with ivtmp_c in condition 'if (ivtmp_a < n)'. */
+ replace_uses_in_bb_by (res_a, res_c, new_header);
+
+ /* 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. */
+ tree res_b = redirect_edge_var_map_def (vm);
+ 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)
+ || res_a == control
+ || red != NULL);
+
+ if (red)
+ {
+ /* Register the new reduction phi. */
+ red->reduc_phi = nphi;
+ gimple_set_uid (red->reduc_phi, red->reduc_version);
+ }
+ }
+ gcc_assert (gsi_end_p (gsi) && !v->iterate (i, &vm));
+
+ /* 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);
+
+
+ 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;
+
+ 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 = (nphi != NULL
+ ? nphi
+ : phi);
+ }
+
+ /* We're going to cancel the loop at the end of gen_parallel_loop, but until
+ then we're still using some fields, so only bother about fields that are
+ still used: header and latch.
+ The loop has a new header bb, so we update it. The latch bb stays the
+ same. */
+ loop->header = new_header;
+
+ /* 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
+ without duplication of the loop body. NIT is the number of iterations of the
+ loop. REDUCTION_LIST describes the reductions in LOOP. Return true if
+ transformation is successful. */
+
+static bool
+try_transform_to_exit_first_loop_alt (struct loop *loop,
+ reduction_info_table_type *reduction_list,
+ tree nit)
+{
+ /* Check whether the latch contains a single statement. */
+ 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);
+ gcond *cond_stmt = as_a <gcond *> (last_stmt (exit->src));
+ tree control = gimple_cond_lhs (cond_stmt);
+ gphi *phi = as_a <gphi *> (SSA_NAME_DEF_STMT (control));
+ tree inc_res = gimple_phi_arg_def (phi, back->dest_idx);
+ if (gimple_bb (SSA_NAME_DEF_STMT (inc_res)) != loop->latch)
+ return false;
+
+ /* Check whether there's no code between the loop condition and the latch. */
+ if (!single_pred_p (loop->latch)
+ || single_pred (loop->latch) != exit->src)
+ return false;
+
+ tree alt_bound = NULL_TREE;
+ tree nit_type = TREE_TYPE (nit);
+
+ /* Figure out whether nit + 1 overflows. */
+ if (TREE_CODE (nit) == INTEGER_CST)
+ {
+ 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;
+ }
+ }
+
+ gcc_assert (TREE_CODE (nit) == SSA_NAME);
+
+ /* 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:
+
+ <bb header>:
+ # iv_1 = PHI <0 (preheader), iv_2 (latch)>
+ ...
+ if (iv_1 < nit)
+ goto <bb latch>;
+ else
+ goto <bb exit>;
+
+ <bb latch>:
+ iv_2 = iv_1 + 1;
+ goto <bb header>;
+
+ 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.
+
+ 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;
+
+ /* Check if nit + 1 overflows. */
+ 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);
+
+ /* 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)
+ {
+ 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;
+}
+
+/* Moves the exit condition of LOOP to the beginning of its header. NIT is the
+ number of iterations of the loop. REDUCTION_LIST describes the reductions in
+ LOOP. */
static void
transform_to_exit_first_loop (struct loop *loop,
bool ok;
edge exit = single_dom_exit (loop), hpred;
tree control, control_name, res, t;
- gimple phi, nphi, cond_stmt, stmt, cond_nit;
- gimple_stmt_iterator gsi;
+ gphi *phi, *nphi;
+ gassign *stmt;
+ gcond *cond_stmt, *cond_nit;
tree nit_1;
split_block_after_labels (loop->header);
orig_header = single_succ (loop->header);
hpred = single_succ_edge (loop->header);
- cond_stmt = last_stmt (exit->src);
+ cond_stmt = as_a <gcond *> (last_stmt (exit->src));
control = gimple_cond_lhs (cond_stmt);
gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
/* Make sure that we have phi nodes on exit for all loop header phis
(create_parallel_loop requires that). */
- for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gphi_iterator gsi = gsi_start_phis (loop->header);
+ !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
- phi = gsi_stmt (gsi);
+ phi = gsi.phi ();
res = PHI_RESULT (phi);
t = copy_ssa_name (res, phi);
SET_PHI_RESULT (phi, t);
out of the loop is the control variable. */
exit = single_dom_exit (loop);
control_name = NULL_TREE;
- for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
+ for (gphi_iterator gsi = gsi_start_phis (ex_bb);
+ !gsi_end_p (gsi); )
{
- phi = gsi_stmt (gsi);
+ phi = gsi.phi ();
res = PHI_RESULT (phi);
if (virtual_operand_p (res))
{
/* Initialize the control variable to number of iterations
according to the rhs of the exit condition. */
- gsi = gsi_after_labels (ex_bb);
- cond_nit = last_stmt (exit->src);
+ gimple_stmt_iterator gsi = gsi_after_labels (ex_bb);
+ cond_nit = as_a <gcond *> (last_stmt (exit->src));
nit_1 = gimple_cond_rhs (cond_nit);
nit_1 = force_gimple_operand_gsi (&gsi,
fold_convert (TREE_TYPE (control_name), nit_1),
/* 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
+static void
create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
- tree new_data, unsigned n_threads, location_t loc)
+ 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;
- gimple stmt, for_stmt, phi, cond_stmt;
+ gomp_parallel *omp_par_stmt;
+ 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);
- stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
- gimple_set_location (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, 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)
- {
- gsi = gsi_after_labels (bb);
+ gsi_insert_after (&gsi, omp_par_stmt, GSI_NEW_STMT);
- param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL);
- stmt = gimple_build_assign (param, build_fold_addr_expr (data));
- gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
+ /* Initialize NEW_DATA. */
+ if (data)
+ {
+ gassign *assign_stmt;
- stmt = gimple_build_assign (new_data,
- fold_convert (TREE_TYPE (new_data), param));
- gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
- }
+ gsi = gsi_after_labels (bb);
- /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
- bb = split_loop_exit_edge (single_dom_exit (loop));
- gsi = gsi_last_bb (bb);
- stmt = gimple_build_omp_return (false);
- gimple_set_location (stmt, loc);
- gsi_insert_after (&gsi, stmt, GSI_NEW_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);
+
+ 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);
- cond_stmt = last_stmt (loop->header);
+ cond_stmt = as_a <gcond *> (last_stmt (loop->header));
cvar = gimple_cond_lhs (cond_stmt);
cvar_base = SSA_NAME_VAR (cvar);
phi = SSA_NAME_DEF_STMT (cvar);
cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
- initvar = copy_ssa_name (cvar, NULL);
+ initvar = copy_ssa_name (cvar);
SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
initvar);
cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
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);
- for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ /* 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;
- phi = gsi_stmt (gsi);
- stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
+ gphi *phi = gpi.phi ();
+ tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (def);
+
+ /* 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_VALUE (PARAM_PARLOOPS_CHUNK_SIZE);
+ enum PARAM_PARLOOPS_SCHEDULE_KIND schedule_type \
+ = (enum PARAM_PARLOOPS_SCHEDULE_KIND) PARAM_VALUE (PARAM_PARLOOPS_SCHEDULE);
+ switch (schedule_type)
+ {
+ case PARAM_PARLOOPS_SCHEDULE_KIND_static:
+ OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
+ break;
+ case PARAM_PARLOOPS_SCHEDULE_KIND_dynamic:
+ OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_DYNAMIC;
+ break;
+ case PARAM_PARLOOPS_SCHEDULE_KIND_guided:
+ OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_GUIDED;
+ break;
+ case PARAM_PARLOOPS_SCHEDULE_KIND_auto:
+ OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_AUTO;
+ chunk_size = 0;
+ break;
+ case PARAM_PARLOOPS_SCHEDULE_KIND_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);
- stmt = gimple_build_omp_continue (cvar_next, cvar);
- gimple_set_location (stmt, loc);
- gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
- SSA_NAME_DEF_STMT (cvar_next) = stmt;
+ 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);
+ SSA_NAME_DEF_STMT (cvar_next) = omp_cont_stmt;
/* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
gsi = gsi_last_bb (ex_bb);
- stmt = gimple_build_omp_return (true);
- gimple_set_location (stmt, loc);
- gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
+ omp_return_stmt2 = gimple_build_omp_return (true);
+ gimple_set_location (omp_return_stmt2, loc);
+ gsi_insert_after (&gsi, omp_return_stmt2, 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. */
+
+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 paral_bb;
+ 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,
reduction_info_table_type *reduction_list,
- unsigned n_threads, struct tree_niter_desc *niter)
+ unsigned n_threads, struct tree_niter_desc *niter,
+ bool oacc_kernels_p)
{
tree many_iterations_cond, type, nit;
tree arg_struct, new_arg_struct;
gimple_seq stmts;
- basic_block parallel_head;
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
+ = 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,
- true, NULL_TREE);
+ = 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. */
- transform_to_exit_first_loop (loop, reduction_list, nit);
+ /* 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 (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
+ to the exit of the loop. */
+ transform_to_exit_first_loop (loop, reduction_list, nit);
+ }
/* Generate initializations for reductions. */
if (reduction_list->elements () > 0)
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);
- parallel_head = create_parallel_loop (loop, create_loop_fn (loc), arg_struct,
- new_arg_struct, n_threads, loc);
+ create_parallel_loop (loop, create_loop_fn (loc), arg_struct, new_arg_struct,
+ n_threads, loc, oacc_kernels_p);
if (reduction_list->elements () > 0)
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);
-
- /* Expand the parallel constructs. We do it directly here instead of running
- a separate expand_omp pass, since it is more efficient, and less likely to
- cause troubles with further analyses not being able to deal with the
- OMP trees. */
-
- omp_expand_local (parallel_head);
+ free_numbers_of_iterations_estimates (cfun);
}
/* Returns true when LOOP contains vector phi nodes. */
{
unsigned i;
basic_block *bbs = get_loop_body_in_dom_order (loop);
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
bool res = true;
for (i = 0; i < loop->num_nodes; i++)
for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
- if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi)))) == VECTOR_TYPE)
+ if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi.phi ()))) == VECTOR_TYPE)
goto end;
res = false;
static void
build_new_reduction (reduction_info_table_type *reduction_list,
- gimple reduc_stmt, gimple 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
gather_scalar_reductions (loop_p loop, reduction_info_table_type *reduction_list)
{
- gimple_stmt_iterator gsi;
+ 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<stmt_vec_info> stmt_vec_infos;
+ stmt_vec_infos.create (50);
+ set_stmt_vec_info_vec (&stmt_vec_infos);
+
+ 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))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
affine_iv iv;
tree res = PHI_RESULT (phi);
bool double_reduc;
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
+ = vect_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)
+ {
+ 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);
+ }
+ 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)
{
- 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);
- }
+ 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
+ = 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;
+
+ build_new_reduction (reduction_list, double_reduc_stmts[i], phi);
+ }
+ delete simple_loop_info;
+ }
}
- destroy_loop_vec_info (simple_loop_info, true);
+
+ gather_done:
+ /* Release the claim on gimple_uid. */
+ free_stmt_vec_infos (&stmt_vec_infos);
+
+ if (reduction_list->elements () == 0)
+ 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 free_stmt_vec_info_vec, 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);
}
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 (struct 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);
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
gcc_assert (exit);
+ /* Try to get rid of exit phis. */
+ final_value_replacement_loop (loop);
+
gather_scalar_reductions (loop, reduction_list);
for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
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 (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)
{
" 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);
}
}
}
iteration space can be distributed efficiently. */
for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
tree def = PHI_RESULT (phi);
affine_iv iv;
}
}
+ 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 (struct 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;
+ single_imm_use (lhs, &use_p, &use_stmt);
+ if (gimple_code (use_stmt) == GIMPLE_PHI)
+ {
+ struct reduction_info *red;
+ 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 (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 (struct 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. */
-bool
-parallelize_loops (void)
+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 (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;
+
+ 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 ())
- return TODO_cleanup_cfg | TODO_rebuild_alias;
- return 0;
+ 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);
+
+ checking_verify_loop_structure ();
+
+ todo |= TODO_update_ssa;
+ }
+
+ if (!in_loop_pipeline)
+ {
+ scev_finalize ();
+ loop_optimizer_finalize ();
+ }
+
+ return todo;
}
} // anon namespace
{
return new pass_parallelize_loops (ctxt);
}
-
-
-#include "gt-tree-parloops.h"
projects / gcc.git / blobdiff