/* Loop autoparallelization.
- Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
+ Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
Contributed by Sebastian Pop <pop@cri.ensmp.fr> and
Zdenek Dvorak <dvorakz@suse.cz>.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
The implementation is straightforward -- for each loop we test whether its
iterations are independent, and if it is the case (and some additional
conditions regarding profitability and correctness are satisfied), we
- add OMP_PARALLEL and OMP_FOR codes and let omp expansion machinery do
- its job.
+ add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
+ machinery do its job.
The most of the complexity is in bringing the code into shape expected
by the omp expanders:
- -- for OMP_FOR, ensuring that the loop has only one induction variable
- and that the exit test is at the start of the loop body
- -- for OMP_PARALLEL, replacing the references to local addressable
+ -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
+ variable and that the exit test is at the start of the loop body
+ -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
variables by accesses through pointers, and breaking up ssa chains
by storing the values incoming to the parallelized loop to a structure
passed to the new function as an argument (something similar is done
sum.27_11 = D.1827_8 + sum.27_29;
- OMP_CONTINUE
+ GIMPLE_OMP_CONTINUE
# Adding this reduction phi is done at create_phi_for_local_result() #
# sum.27_56 = PHI <sum.27_11, 0>
- OMP_RETURN
+ GIMPLE_OMP_RETURN
# Creating the atomic operation is done at
create_call_for_reduction_1() #
D.1840_60 = sum.27_56 + D.1839_59;
#pragma omp atomic_store (D.1840_60);
- OMP_RETURN
+ GIMPLE_OMP_RETURN
# collecting the result after the join of the threads is done at
create_loads_for_reductions().
reduction in the current loop. */
struct reduction_info
{
- tree reduc_stmt; /* reduction statement. */
- tree reduc_phi; /* The phi node defining the reduction. */
- enum tree_code reduction_code; /* code for the reduction operation. */
- tree keep_res; /* The PHI_RESULT of this phi is the resulting value
+ gimple reduc_stmt; /* reduction statement. */
+ gimple reduc_phi; /* The phi node defining the reduction. */
+ enum tree_code reduction_code;/* code for the reduction operation. */
+ gimple 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 init; /* reduction initialization value. */
- tree new_phi; /* (helper field) Newly created phi node whose result
+ gimple 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. */
}
static struct reduction_info *
-reduction_phi (htab_t reduction_list, tree phi)
+reduction_phi (htab_t reduction_list, gimple phi)
{
struct reduction_info tmpred, *red;
return (hashval_t) a->version;
}
-/* Returns true if the iterations of LOOP are independent on each other (that
- is, if we can execute them in parallel), and if LOOP satisfies other
- conditions that we need to be able to parallelize it. Description of number
- of iterations is stored to NITER. Reduction analysis is done, if
- reductions are found, they are inserted to the REDUCTION_LIST. */
+
+/* Data dependency analysis. Returns true if the iterations of LOOP
+ are independent on each other (that is, if we can execute them
+ in parallel). */
static bool
-loop_parallel_p (struct loop *loop, htab_t reduction_list, struct tree_niter_desc *niter)
+loop_parallel_p (struct loop *loop)
{
- edge exit = single_dom_exit (loop);
VEC (ddr_p, heap) * dependence_relations;
- VEC (data_reference_p, heap) * datarefs;
+ VEC (data_reference_p, heap) *datarefs;
lambda_trans_matrix trans;
bool ret = false;
- tree phi;
- loop_vec_info simple_loop_info;
-
- /* Only consider innermost loops with just one exit. The innermost-loop
- restriction is not necessary, but it makes things simpler. */
- if (loop->inner || !exit)
- return false;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nConsidering loop %d\n", loop->num);
- /* We need to know # of iterations, and there should be no uses of values
- defined inside loop outside of it, unless the values are invariants of
- the loop. */
- if (!number_of_iterations_exit (loop, exit, niter, false))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " FAILED: number of iterations not known\n");
- return false;
- }
-
- simple_loop_info = vect_analyze_loop_form (loop);
-
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
- {
- tree reduc_stmt = NULL, operation;
-
- /* ??? TODO: Change this into a generic function that
- recognizes reductions. */
- if (!is_gimple_reg (PHI_RESULT (phi)))
- continue;
- if (simple_loop_info)
- reduc_stmt = vect_is_simple_reduction (simple_loop_info, phi);
-
- /* Create a reduction_info struct, initialize it and insert it to
- the reduction list. */
-
- if (reduc_stmt)
- {
- PTR *slot;
- struct reduction_info *new_reduction;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file,
- "Detected reduction. reduction stmt is: \n");
- print_generic_stmt (dump_file, reduc_stmt, 0);
- fprintf (dump_file, "\n");
- }
-
- new_reduction = XCNEW (struct reduction_info);
-
- new_reduction->reduc_stmt = reduc_stmt;
- new_reduction->reduc_phi = phi;
- operation = GIMPLE_STMT_OPERAND (reduc_stmt, 1);
- new_reduction->reduction_code = TREE_CODE (operation);
- slot = htab_find_slot (reduction_list, new_reduction, INSERT);
- *slot = new_reduction;
- }
- }
-
- /* Get rid of the information created by the vectorizer functions. */
- destroy_loop_vec_info (simple_loop_info, true);
-
- for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
- {
- struct reduction_info *red;
- imm_use_iterator imm_iter;
- use_operand_p use_p;
- tree reduc_phi;
-
- tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
-
- if (is_gimple_reg (val))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "phi is ");
- print_generic_expr (dump_file, phi, 0);
- fprintf (dump_file, "arg of phi to exit: value ");
- print_generic_expr (dump_file, val, 0);
- fprintf (dump_file, " used outside loop\n");
- fprintf (dump_file,
- " checking if it a part of reduction pattern: \n");
- }
- if (htab_elements (reduction_list) == 0)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- " FAILED: it is not a part of reduction.\n");
- return false;
- }
- reduc_phi = NULL;
- FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
- {
- if (flow_bb_inside_loop_p (loop, bb_for_stmt (USE_STMT (use_p))))
- {
- reduc_phi = USE_STMT (use_p);
- break;
- }
- }
- red = reduction_phi (reduction_list, reduc_phi);
- if (red == NULL)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- " FAILED: it is not a part of reduction.\n");
- return false;
- }
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "reduction phi is ");
- print_generic_expr (dump_file, red->reduc_phi, 0);
- fprintf (dump_file, "reduction stmt is ");
- print_generic_expr (dump_file, red->reduc_stmt, 0);
- }
-
- }
- }
-
- /* The iterations of the loop may communicate only through bivs whose
- iteration space can be distributed efficiently. */
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
- {
- tree def = PHI_RESULT (phi);
- affine_iv iv;
-
- if (is_gimple_reg (def) && !simple_iv (loop, phi, def, &iv, true))
- {
- struct reduction_info *red;
-
- red = reduction_phi (reduction_list, phi);
- if (red == NULL)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- " FAILED: scalar dependency between iterations\n");
- return false;
- }
- }
- }
-
- /* We need to version the loop to verify assumptions in runtime. */
- if (!can_duplicate_loop_p (loop))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " FAILED: cannot be duplicated\n");
- return false;
- }
-
/* Check for problems with dependences. If the loop can be reversed,
the iterations are independent. */
datarefs = VEC_alloc (data_reference_p, heap, 10);
int uid;
void **dslot;
struct int_tree_map ielt, *nielt;
- tree *var_p, name, bvar, stmt, addr;
+ tree *var_p, name, bvar, addr;
+ gimple stmt;
+ gimple_seq stmts;
/* Since the address of OBJ is invariant, the trees may be shared.
Avoid rewriting unrelated parts of the code. */
addr = build_addr (*var_p, current_function_decl);
bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));
add_referenced_var (bvar);
- stmt = build_gimple_modify_stmt (bvar, addr);
+ stmt = gimple_build_assign (bvar, addr);
name = make_ssa_name (bvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- bsi_insert_on_edge_immediate (entry, stmt);
+ gimple_assign_set_lhs (stmt, name);
+ gsi_insert_on_edge_immediate (entry, stmt);
nielt = XNEW (struct int_tree_map);
nielt->uid = uid;
{
*var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);
name = force_gimple_operand (build_addr (obj, current_function_decl),
- &stmt, true, NULL_TREE);
- if (stmt)
- bsi_insert_on_edge_immediate (entry, stmt);
+ &stmts, true, NULL_TREE);
+ if (!gimple_seq_empty_p (stmts))
+ gsi_insert_seq_on_edge_immediate (entry, stmts);
}
if (TREE_TYPE (name) != type)
{
- name = force_gimple_operand (fold_convert (type, name), &stmt, true,
+ name = force_gimple_operand (fold_convert (type, name), &stmts, true,
NULL_TREE);
- if (stmt)
- bsi_insert_on_edge_immediate (entry, stmt);
+ if (!gimple_seq_empty_p (stmts))
+ gsi_insert_seq_on_edge_immediate (entry, stmts);
}
return name;
bvar = create_tmp_var (type, "reduction");
add_referenced_var (bvar);
- c = build_omp_clause (OMP_CLAUSE_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_STMT_OPERAND (reduc->reduc_stmt, 0));
+ OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
init = omp_reduction_init (c, TREE_TYPE (bvar));
reduc->init = init;
struct elv_data
{
+ struct walk_stmt_info info;
edge entry;
htab_t decl_address;
bool changed;
return NULL_TREE;
}
- if (!EXPR_P (t) && !GIMPLE_STMT_P (t))
+ if (!EXPR_P (t))
*walk_subtrees = 0;
return NULL_TREE;
already. */
static void
-eliminate_local_variables_stmt (edge entry, tree stmt,
+eliminate_local_variables_stmt (edge entry, gimple stmt,
htab_t decl_address)
{
struct elv_data dta;
+ memset (&dta.info, '\0', sizeof (dta.info));
dta.entry = entry;
dta.decl_address = decl_address;
dta.changed = false;
- walk_tree (&stmt, eliminate_local_variables_1, &dta, NULL);
+ walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
if (dta.changed)
update_stmt (stmt);
basic_block bb;
VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
unsigned i;
- block_stmt_iterator bsi;
+ gimple_stmt_iterator gsi;
htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
free);
basic_block entry_bb = entry->src;
for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
if (bb != entry_bb && bb != exit_bb)
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- eliminate_local_variables_stmt (entry, bsi_stmt (bsi),
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ eliminate_local_variables_stmt (entry, gsi_stmt (gsi),
decl_address);
htab_delete (decl_address);
basic_block entry_bb = entry->src;
basic_block exit_bb = exit->dest;
basic_block def_bb;
- unsigned i, len;
if (is_gimple_min_invariant (expr))
return true;
if (TREE_CODE (expr) == SSA_NAME)
{
- def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
+ def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
if (def_bb
&& dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
&& !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
return true;
}
- if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
- return false;
-
- len = TREE_OPERAND_LENGTH (expr);
- for (i = 0; i < len; i++)
- if (!expr_invariant_in_region_p (entry, exit, TREE_OPERAND (expr, i)))
- return false;
-
- return true;
+ return false;
}
/* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
if (copy_name_p)
{
- copy = duplicate_ssa_name (name, NULL_TREE);
+ copy = duplicate_ssa_name (name, NULL);
nelt = XNEW (struct name_to_copy_elt);
nelt->version = idx;
nelt->new_name = copy;
replacement decls are stored in DECL_COPIES. */
static void
-separate_decls_in_region_stmt (edge entry, edge exit, tree stmt,
+separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
htab_t name_copies, htab_t decl_copies)
{
use_operand_p use;
struct reduction_info *const red = (struct reduction_info *) *slot;
tree const type = (tree) data;
- tree var = SSA_NAME_VAR (GIMPLE_STMT_OPERAND (red->reduc_stmt, 0));
- tree field = build_decl (FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
+ tree var = SSA_NAME_VAR (gimple_assign_lhs (red->reduc_stmt));
+ tree field = build_decl (gimple_location (red->reduc_stmt),
+ FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
insert_field_into_struct (type, field);
tree type = (tree) data;
tree name = ssa_name (elt->version);
tree var = SSA_NAME_VAR (name);
- tree field = build_decl (FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
+ tree field = build_decl (DECL_SOURCE_LOCATION (var),
+ FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
insert_field_into_struct (type, field);
elt->field = field;
struct reduction_info *const reduc = (struct reduction_info *) *slot;
const struct loop *const loop = (const struct loop *) data;
edge e;
- tree new_phi;
+ gimple new_phi;
basic_block store_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 OMP_CONTINUE). */
+ (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
store_bb = FALLTHRU_EDGE (loop->latch)->dest;
/* STORE_BB has two predecessors. One coming from the loop
e = EDGE_PRED (store_bb, 1);
else
e = EDGE_PRED (store_bb, 0);
- local_res = make_ssa_name (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (reduc->reduc_stmt, 0)), NULL_TREE);
+ local_res
+ = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)),
+ NULL);
+ locus = gimple_location (reduc->reduc_stmt);
new_phi = create_phi_node (local_res, store_bb);
SSA_NAME_DEF_STMT (local_res) = new_phi;
- add_phi_arg (new_phi, reduc->init, e);
- add_phi_arg (new_phi, GIMPLE_STMT_OPERAND (reduc->reduc_stmt, 0),
- FALLTHRU_EDGE (loop->latch));
+ 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);
reduc->new_phi = new_phi;
return 1;
{
struct reduction_info *const reduc = (struct reduction_info *) *slot;
struct clsn_data *const clsn_data = (struct clsn_data *) data;
- block_stmt_iterator bsi;
+ gimple_stmt_iterator gsi;
tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
tree load_struct;
basic_block new_bb;
edge e;
tree t, addr, addr_type, ref, x;
- tree tmp_load, load, name;
+ tree tmp_load, name;
+ gimple load;
load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
add_referenced_var (tmp_load);
tmp_load = make_ssa_name (tmp_load, NULL);
- load = build2 (OMP_ATOMIC_LOAD, void_type_node, tmp_load, addr);
+ load = gimple_build_omp_atomic_load (tmp_load, addr);
SSA_NAME_DEF_STMT (tmp_load) = load;
- bsi = bsi_start (new_bb);
- bsi_insert_after (&bsi, load, BSI_NEW_STMT);
+ gsi = gsi_start_bb (new_bb);
+ gsi_insert_after (&gsi, load, GSI_NEW_STMT);
e = split_block (new_bb, load);
new_bb = e->dest;
- bsi = bsi_start (new_bb);
+ gsi = gsi_start_bb (new_bb);
ref = tmp_load;
- x =
- fold_build2 (reduc->reduction_code,
- TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
- PHI_RESULT (reduc->new_phi));
-
- name =
- force_gimple_operand_bsi (&bsi, x, true, NULL_TREE, true,
- BSI_CONTINUE_LINKING);
+ x = fold_build2 (reduc->reduction_code,
+ TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
+ PHI_RESULT (reduc->new_phi));
- x = build1 (OMP_ATOMIC_STORE, void_type_node, name);
+ name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
+ GSI_CONTINUE_LINKING);
- bsi_insert_after (&bsi, x, BSI_NEW_STMT);
+ gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
return 1;
}
struct clsn_data *ld_st_data)
{
htab_traverse (reduction_list, create_phi_for_local_result, loop);
- /* Find the fallthru edge from OMP_CONTINUE. */
+ /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
htab_traverse (reduction_list, create_call_for_reduction_1, ld_st_data);
}
{
struct reduction_info *const red = (struct reduction_info *) *slot;
struct clsn_data *const clsn_data = (struct clsn_data *) data;
- tree stmt;
- block_stmt_iterator bsi;
- tree type = TREE_TYPE (GIMPLE_STMT_OPERAND (red->reduc_stmt, 0));
+ gimple stmt;
+ gimple_stmt_iterator gsi;
+ tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
tree load_struct;
tree name;
tree x;
- bsi = bsi_after_labels (clsn_data->load_bb);
+ gsi = gsi_after_labels (clsn_data->load_bb);
load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
NULL_TREE);
x = load_struct;
name = PHI_RESULT (red->keep_res);
- stmt = build_gimple_modify_stmt (name, x);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
+ stmt = gimple_build_assign (name, x);
SSA_NAME_DEF_STMT (name) = stmt;
- bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
- remove_phi_node (red->keep_res, NULL_TREE, false);
-
- return 1;
+ for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ if (gsi_stmt (gsi) == red->keep_res)
+ {
+ remove_phi_node (&gsi, false);
+ return 1;
+ }
+ gcc_unreachable ();
}
/* Load the reduction result that was stored in LD_ST_DATA.
create_final_loads_for_reduction (htab_t reduction_list,
struct clsn_data *ld_st_data)
{
- block_stmt_iterator bsi;
+ gimple_stmt_iterator gsi;
tree t;
+ gimple stmt;
- bsi = bsi_after_labels (ld_st_data->load_bb);
+ gsi = gsi_after_labels (ld_st_data->load_bb);
t = build_fold_addr_expr (ld_st_data->store);
- t =
- build_gimple_modify_stmt (ld_st_data->load,
- build_fold_addr_expr (ld_st_data->store));
+ stmt = gimple_build_assign (ld_st_data->load, t);
- bsi_insert_before (&bsi, t, BSI_NEW_STMT);
- SSA_NAME_DEF_STMT (ld_st_data->load) = t;
- GIMPLE_STMT_OPERAND (t, 0) = ld_st_data->load;
+ gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
+ SSA_NAME_DEF_STMT (ld_st_data->load) = stmt;
htab_traverse (reduction_list, create_loads_for_reductions, ld_st_data);
{
struct reduction_info *const red = (struct reduction_info *) *slot;
struct clsn_data *const clsn_data = (struct clsn_data *) data;
- tree stmt;
- block_stmt_iterator bsi;
- tree type = TREE_TYPE (GIMPLE_STMT_OPERAND (red->reduc_stmt, 0));
-
- bsi = bsi_last (clsn_data->store_bb);
- stmt =
- build_gimple_modify_stmt (build3
- (COMPONENT_REF, type, clsn_data->store,
- red->field, NULL_TREE),
- red->initial_value);
+ tree t;
+ gimple stmt;
+ gimple_stmt_iterator gsi;
+ tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
+
+ gsi = gsi_last_bb (clsn_data->store_bb);
+ t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
+ stmt = gimple_build_assign (t, red->initial_value);
mark_virtual_ops_for_renaming (stmt);
- bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
return 1;
}
{
struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
struct clsn_data *const clsn_data = (struct clsn_data *) data;
- tree stmt;
- block_stmt_iterator bsi;
+ tree t;
+ gimple stmt;
+ gimple_stmt_iterator gsi;
tree type = TREE_TYPE (elt->new_name);
tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
tree load_struct;
- bsi = bsi_last (clsn_data->store_bb);
- stmt =
- build_gimple_modify_stmt (build3
- (COMPONENT_REF, type, clsn_data->store,
- elt->field, NULL_TREE),
- ssa_name (elt->version));
+ gsi = gsi_last_bb (clsn_data->store_bb);
+ t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
+ stmt = gimple_build_assign (t, ssa_name (elt->version));
mark_virtual_ops_for_renaming (stmt);
- bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
- bsi = bsi_last (clsn_data->load_bb);
+ gsi = gsi_last_bb (clsn_data->load_bb);
load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
- stmt = build_gimple_modify_stmt (elt->new_name,
- build3 (COMPONENT_REF, type, load_struct,
- elt->field, NULL_TREE));
+ t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
+ stmt = gimple_build_assign (elt->new_name, t);
SSA_NAME_DEF_STMT (elt->new_name) = stmt;
- bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
return 1;
}
htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq,
free);
unsigned i;
- tree phi, type, type_name, nvar;
- block_stmt_iterator bsi;
+ tree type, type_name, nvar;
+ gimple_stmt_iterator gsi;
struct clsn_data clsn_data;
VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
basic_block bb;
basic_block entry_bb = bb1;
basic_block exit_bb = exit->dest;
- entry = single_succ_edge(entry_bb);
+ entry = single_succ_edge (entry_bb);
gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
{
if (bb != entry_bb && bb != exit_bb)
{
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- separate_decls_in_region_stmt (entry, exit, phi, name_copies,
- decl_copies);
-
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- separate_decls_in_region_stmt (entry, exit, bsi_stmt (bsi),
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
+ name_copies, decl_copies);
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
name_copies, decl_copies);
}
}
VEC_free (basic_block, heap, body);
- if (htab_elements (name_copies) == 0)
+ if (htab_elements (name_copies) == 0 && reduction_list == 0)
{
/* It may happen that there is nothing to copy (if there are only
loop carried and external variables in the loop). */
{
/* Create the type for the structure to store the ssa names to. */
type = lang_hooks.types.make_type (RECORD_TYPE);
- type_name = build_decl (TYPE_DECL, create_tmp_var_name (".paral_data"),
+ type_name = build_decl (BUILTINS_LOCATION,
+ TYPE_DECL, create_tmp_var_name (".paral_data"),
type);
TYPE_NAME (type) = type_name;
add_referenced_var (*arg_struct);
nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
add_referenced_var (nvar);
- *new_arg_struct = make_ssa_name (nvar, NULL_TREE);
+ *new_arg_struct = make_ssa_name (nvar, NULL);
ld_st_data->store = *arg_struct;
ld_st_data->load = *new_arg_struct;
{
htab_traverse (reduction_list, create_stores_for_reduction,
ld_st_data);
- clsn_data.load = make_ssa_name (nvar, NULL_TREE);
+ clsn_data.load = make_ssa_name (nvar, NULL);
clsn_data.load_bb = exit->dest;
clsn_data.store = ld_st_data->store;
create_final_loads_for_reduction (reduction_list, &clsn_data);
name = get_identifier (tname);
type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
- decl = build_decl (FUNCTION_DECL, name, type);
+ decl = build_decl (BUILTINS_LOCATION,
+ FUNCTION_DECL, name, type);
if (!parallelized_functions)
parallelized_functions = BITMAP_GGC_ALLOC ();
bitmap_set_bit (parallelized_functions, DECL_UID (decl));
DECL_CONTEXT (decl) = NULL_TREE;
DECL_INITIAL (decl) = make_node (BLOCK);
- t = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
+ t = build_decl (BUILTINS_LOCATION,
+ RESULT_DECL, NULL_TREE, void_type_node);
DECL_ARTIFICIAL (t) = 1;
DECL_IGNORED_P (t) = 1;
DECL_RESULT (decl) = t;
- t = build_decl (PARM_DECL, get_identifier (".paral_data_param"),
+ t = build_decl (BUILTINS_LOCATION,
+ PARM_DECL, get_identifier (".paral_data_param"),
ptr_type_node);
DECL_ARTIFICIAL (t) = 1;
DECL_ARG_TYPE (t) = ptr_type_node;
return decl;
}
-/* Bases all the induction variables in LOOP on a single induction variable
- (unsigned with base 0 and step 1), whose final value is compared with
- NIT. The induction variable is incremented in the loop latch.
- REDUCTION_LIST describes the reductions in LOOP. */
-
-static void
-canonicalize_loop_ivs (struct loop *loop, htab_t reduction_list, tree nit)
-{
- unsigned precision = TYPE_PRECISION (TREE_TYPE (nit));
- tree phi, prev, res, type, var_before, val, atype, mtype, t, next;
- block_stmt_iterator bsi;
- bool ok;
- affine_iv iv;
- edge exit = single_dom_exit (loop);
- struct reduction_info *red;
-
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
- {
- res = PHI_RESULT (phi);
-
- if (is_gimple_reg (res) && TYPE_PRECISION (TREE_TYPE (res)) > precision)
- precision = TYPE_PRECISION (TREE_TYPE (res));
- }
-
- type = lang_hooks.types.type_for_size (precision, 1);
-
- bsi = bsi_last (loop->latch);
- create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE,
- loop, &bsi, true, &var_before, NULL);
-
- bsi = bsi_after_labels (loop->header);
- prev = NULL;
- for (phi = phi_nodes (loop->header); phi; phi = next)
- {
- next = PHI_CHAIN (phi);
- res = PHI_RESULT (phi);
-
- if (!is_gimple_reg (res) || res == var_before)
- {
- prev = phi;
- continue;
- }
-
- ok = simple_iv (loop, phi, res, &iv, true);
- red = reduction_phi (reduction_list, phi);
- /* We preserve the reduction phi nodes. */
- if (!ok && red)
- {
- prev = phi;
- continue;
- }
- else
- gcc_assert (ok);
- remove_phi_node (phi, prev, false);
-
- atype = TREE_TYPE (res);
- mtype = POINTER_TYPE_P (atype) ? sizetype : atype;
- val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step),
- fold_convert (mtype, var_before));
- val = fold_build2 (POINTER_TYPE_P (atype)
- ? POINTER_PLUS_EXPR : PLUS_EXPR,
- atype, unshare_expr (iv.base), val);
- val = force_gimple_operand_bsi (&bsi, val, false, NULL_TREE, true,
- BSI_SAME_STMT);
- t = build_gimple_modify_stmt (res, val);
- bsi_insert_before (&bsi, t, BSI_SAME_STMT);
- SSA_NAME_DEF_STMT (res) = t;
- }
-
- t = last_stmt (exit->src);
- /* Make the loop exit if the control condition is not satisfied. */
- if (exit->flags & EDGE_TRUE_VALUE)
- {
- edge te, fe;
-
- extract_true_false_edges_from_block (exit->src, &te, &fe);
- te->flags = EDGE_FALSE_VALUE;
- fe->flags = EDGE_TRUE_VALUE;
- }
- COND_EXPR_COND (t) = build2 (LT_EXPR, boolean_type_node, var_before, nit);
-}
-
/* 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
unsigned n;
bool ok;
edge exit = single_dom_exit (loop), hpred;
- tree phi, nphi, cond, control, control_name, res, t, cond_stmt;
- block_stmt_iterator bsi;
+ tree control, control_name, res, t;
+ gimple phi, nphi, cond_stmt, stmt;
+ gimple_stmt_iterator gsi;
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 = COND_EXPR_COND (cond_stmt);
- control = TREE_OPERAND (cond, 0);
- gcc_assert (TREE_OPERAND (cond, 1) == nit);
+ 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 (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
{
+ phi = gsi_stmt (gsi);
res = PHI_RESULT (phi);
t = make_ssa_name (SSA_NAME_VAR (res), phi);
SET_PHI_RESULT (phi, t);
nphi = create_phi_node (res, orig_header);
SSA_NAME_DEF_STMT (res) = nphi;
- add_phi_arg (nphi, t, hpred);
+ add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);
if (res == control)
{
- TREE_OPERAND (cond, 0) = t;
+ gimple_cond_set_lhs (cond_stmt, t);
update_stmt (cond_stmt);
control = t;
}
for (n = 0; bbs[n] != exit->src; n++)
continue;
nbbs = XNEWVEC (basic_block, n);
- ok = tree_duplicate_sese_tail (single_succ_edge (loop->header), exit,
- bbs + 1, n, nbbs);
+ ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
+ bbs + 1, n, nbbs);
gcc_assert (ok);
free (bbs);
ex_bb = nbbs[0];
free (nbbs);
/* Other than reductions, the only gimple reg that should be copied
- out of the loop is the control variable. */
+ out of the loop is the control variable. */
control_name = NULL_TREE;
- for (phi = phi_nodes (ex_bb); phi; phi = PHI_CHAIN (phi))
+ for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
{
+ phi = gsi_stmt (gsi);
res = PHI_RESULT (phi);
if (!is_gimple_reg (res))
- continue;
+ {
+ gsi_next (&gsi);
+ continue;
+ }
/* Check if it is a part of reduction. If it is,
keep the phi at the reduction's keep_res field. The
red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
if (red)
- red->keep_res = phi;
+ {
+ red->keep_res = phi;
+ gsi_next (&gsi);
+ continue;
+ }
}
- else
- gcc_assert (control_name == NULL_TREE
- && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
+ gcc_assert (control_name == NULL_TREE
+ && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
control_name = res;
+ remove_phi_node (&gsi, false);
}
gcc_assert (control_name != NULL_TREE);
- phi = SSA_NAME_DEF_STMT (control_name);
- remove_phi_node (phi, NULL_TREE, false);
/* Initialize the control variable to NIT. */
- bsi = bsi_after_labels (ex_bb);
- nit = force_gimple_operand_bsi (&bsi,
+ gsi = gsi_after_labels (ex_bb);
+ nit = force_gimple_operand_gsi (&gsi,
fold_convert (TREE_TYPE (control_name), nit),
- false, NULL_TREE, false, BSI_SAME_STMT);
- t = build_gimple_modify_stmt (control_name, nit);
- bsi_insert_before (&bsi, t, BSI_NEW_STMT);
- SSA_NAME_DEF_STMT (control_name) = t;
+ false, NULL_TREE, false, GSI_SAME_STMT);
+ stmt = gimple_build_assign (control_name, nit);
+ gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
+ SSA_NAME_DEF_STMT (control_name) = stmt;
}
/* Create the parallel constructs for LOOP as described in gen_parallel_loop.
- LOOP_FN and DATA are the arguments of OMP_PARALLEL.
+ 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 OMP_PARALLEL tree. */
+ basic block containing GIMPLE_OMP_PARALLEL tree. */
static basic_block
create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
tree new_data, unsigned n_threads)
{
- block_stmt_iterator bsi;
+ gimple_stmt_iterator gsi;
basic_block bb, paral_bb, for_bb, ex_bb;
- tree t, param, res, for_stmt;
- tree cvar, cvar_init, initvar, cvar_next, cvar_base, cond, phi, type;
+ tree t, param, res;
+ gimple stmt, for_stmt, phi, cond_stmt;
+ tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
edge exit, nexit, guard, end, e;
- /* Prepare the OMP_PARALLEL statement. */
+ /* Prepare the GIMPLE_OMP_PARALLEL statement. */
bb = loop_preheader_edge (loop)->src;
paral_bb = single_pred (bb);
- bsi = bsi_last (paral_bb);
+ gsi = gsi_last_bb (paral_bb);
- t = build_omp_clause (OMP_CLAUSE_NUM_THREADS);
+ t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_NUM_THREADS);
OMP_CLAUSE_NUM_THREADS_EXPR (t)
= build_int_cst (integer_type_node, n_threads);
- t = build4 (OMP_PARALLEL, void_type_node, NULL_TREE, t, loop_fn, data);
+ stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
- bsi_insert_after (&bsi, t, BSI_NEW_STMT);
+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
/* Initialize NEW_DATA. */
if (data)
{
- bsi = bsi_after_labels (bb);
-
- param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL_TREE);
- t = build_gimple_modify_stmt (param, build_fold_addr_expr (data));
- bsi_insert_before (&bsi, t, BSI_SAME_STMT);
- SSA_NAME_DEF_STMT (param) = t;
-
- t = build_gimple_modify_stmt (new_data,
- fold_convert (TREE_TYPE (new_data),
- param));
- bsi_insert_before (&bsi, t, BSI_SAME_STMT);
- SSA_NAME_DEF_STMT (new_data) = t;
+ gsi = gsi_after_labels (bb);
+
+ 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);
+ SSA_NAME_DEF_STMT (param) = stmt;
+
+ stmt = gimple_build_assign (new_data,
+ fold_convert (TREE_TYPE (new_data), param));
+ gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
+ SSA_NAME_DEF_STMT (new_data) = stmt;
}
- /* Emit OMP_RETURN for OMP_PARALLEL. */
+ /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
bb = split_loop_exit_edge (single_dom_exit (loop));
- bsi = bsi_last (bb);
- bsi_insert_after (&bsi, make_node (OMP_RETURN), BSI_NEW_STMT);
+ gsi = gsi_last_bb (bb);
+ gsi_insert_after (&gsi, gimple_build_omp_return (false), GSI_NEW_STMT);
- /* Extract data for OMP_FOR. */
+ /* Extract data for GIMPLE_OMP_FOR. */
gcc_assert (loop->header == single_dom_exit (loop)->src);
- cond = COND_EXPR_COND (last_stmt (loop->header));
+ cond_stmt = last_stmt (loop->header);
- cvar = TREE_OPERAND (cond, 0);
+ 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 = make_ssa_name (cvar_base, NULL_TREE);
+ initvar = make_ssa_name (cvar_base, NULL);
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));
- bsi = bsi_last (loop->latch);
- gcc_assert (bsi_stmt (bsi) == SSA_NAME_DEF_STMT (cvar_next));
- bsi_remove (&bsi, true);
+ gsi = gsi_last_bb (loop->latch);
+ gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
+ gsi_remove (&gsi, true);
/* Prepare cfg. */
for_bb = split_edge (loop_preheader_edge (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 (phi = phi_nodes (ex_bb); phi; phi = PHI_CHAIN (phi))
+ for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
+ source_location locus;
+ tree def;
+ phi = gsi_stmt (gsi);
res = PHI_RESULT (phi);
- gcc_assert (!is_gimple_reg (phi));
- t = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
- add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (t, loop_preheader_edge (loop)),
- guard);
- add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (t, loop_latch_edge (loop)),
- end);
+ stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
+
+ def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
+ locus = gimple_phi_arg_location_from_edge (stmt,
+ loop_preheader_edge (loop));
+ add_phi_arg (phi, def, guard, locus);
+
+ def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
+ locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
+ add_phi_arg (phi, def, end, locus);
}
e = redirect_edge_and_branch (exit, nexit->dest);
PENDING_STMT (e) = NULL;
- /* Emit OMP_FOR. */
- TREE_OPERAND (cond, 0) = cvar_base;
+ /* Emit GIMPLE_OMP_FOR. */
+ gimple_cond_set_lhs (cond_stmt, cvar_base);
type = TREE_TYPE (cvar);
- t = build_omp_clause (OMP_CLAUSE_SCHEDULE);
+ t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_SCHEDULE);
OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
- for_stmt = make_node (OMP_FOR);
- TREE_TYPE (for_stmt) = void_type_node;
- OMP_FOR_CLAUSES (for_stmt) = t;
- OMP_FOR_INIT (for_stmt) = make_tree_vec (1);
- TREE_VEC_ELT (OMP_FOR_INIT (for_stmt), 0)
- = build_gimple_modify_stmt (initvar, cvar_init);
- OMP_FOR_COND (for_stmt) = make_tree_vec (1);
- TREE_VEC_ELT (OMP_FOR_COND (for_stmt), 0) = cond;
- OMP_FOR_INCR (for_stmt) = make_tree_vec (2);
- TREE_VEC_ELT (OMP_FOR_INCR (for_stmt), 0)
- = build_gimple_modify_stmt (cvar_base,
- build2 (PLUS_EXPR, type, cvar_base,
- build_int_cst (type, 1)));
- OMP_FOR_BODY (for_stmt) = NULL_TREE;
- OMP_FOR_PRE_BODY (for_stmt) = NULL_TREE;
-
- bsi = bsi_last (for_bb);
- bsi_insert_after (&bsi, for_stmt, BSI_NEW_STMT);
+ for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
+ gimple_omp_for_set_index (for_stmt, 0, initvar);
+ gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
+ gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
+ gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
+ gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
+ cvar_base,
+ build_int_cst (type, 1)));
+
+ gsi = gsi_last_bb (for_bb);
+ gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
SSA_NAME_DEF_STMT (initvar) = for_stmt;
- /* Emit OMP_CONTINUE. */
- bsi = bsi_last (loop->latch);
- t = build2 (OMP_CONTINUE, void_type_node, cvar_next, cvar);
- bsi_insert_after (&bsi, t, BSI_NEW_STMT);
- SSA_NAME_DEF_STMT (cvar_next) = t;
+ /* Emit GIMPLE_OMP_CONTINUE. */
+ gsi = gsi_last_bb (loop->latch);
+ stmt = gimple_build_omp_continue (cvar_next, cvar);
+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
+ SSA_NAME_DEF_STMT (cvar_next) = stmt;
- /* Emit OMP_RETURN for OMP_FOR. */
- bsi = bsi_last (ex_bb);
- t = make_node (OMP_RETURN);
- OMP_RETURN_NOWAIT (t) = 1;
- bsi_insert_after (&bsi, t, BSI_NEW_STMT);
+ /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
+ gsi = gsi_last_bb (ex_bb);
+ gsi_insert_after (&gsi, gimple_build_omp_return (true), GSI_NEW_STMT);
return paral_bb;
}
-/* Generates code to execute the iterations of LOOP in N_THREADS threads in
- parallel. NITER describes number of iterations of LOOP.
+/* Generates code to execute the iterations of LOOP in N_THREADS
+ threads in parallel.
+
+ NITER describes number of iterations of LOOP.
REDUCTION_LIST describes the reductions existent in the LOOP. */
static void
-gen_parallel_loop (struct loop *loop, htab_t reduction_list,
+gen_parallel_loop (struct loop *loop, htab_t reduction_list,
unsigned n_threads, struct tree_niter_desc *niter)
{
struct loop *nloop;
loop_iterator li;
tree many_iterations_cond, type, nit;
- tree stmts, arg_struct, new_arg_struct;
+ tree arg_struct, new_arg_struct;
+ gimple_seq stmts;
basic_block parallel_head;
edge entry, exit;
struct clsn_data clsn_data;
BODY1;
store all local loop-invariant variables used in body of the loop to DATA.
- OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
+ GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
load the variables from DATA.
- OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
+ GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
BODY2;
BODY1;
- OMP_CONTINUE;
- OMP_RETURN -- OMP_FOR
- OMP_RETURN -- OMP_PARALLEL
+ GIMPLE_OMP_CONTINUE;
+ GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
+ GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
goto end;
original:
nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
NULL_TREE);
if (stmts)
- bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
many_iterations_cond =
fold_build2 (GE_EXPR, boolean_type_node,
many_iterations_cond
= force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
if (stmts)
- bsi_insert_on_edge_immediate (loop_preheader_edge (loop), 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)
- bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
}
initialize_original_copy_tables ();
free_original_copy_tables ();
/* Base all the induction variables in LOOP on a single control one. */
- canonicalize_loop_ivs (loop, reduction_list, nit);
+ canonicalize_loop_ivs (loop, &nit);
/* Ensure that the exit condition is the first statement in the loop. */
transform_to_exit_first_loop (loop, reduction_list, nit);
/* Returns true when LOOP contains vector phi nodes. */
static bool
-loop_has_vector_phi_nodes (struct loop *loop)
+loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
{
unsigned i;
basic_block *bbs = get_loop_body_in_dom_order (loop);
+ gimple_stmt_iterator gsi;
bool res = true;
- tree phi;
for (i = 0; i < loop->num_nodes; i++)
- for (phi = phi_nodes (bbs[i]); phi; phi = PHI_CHAIN (phi))
- if (TREE_CODE (TREE_TYPE (PHI_RESULT (phi))) == VECTOR_TYPE)
+ 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)
goto end;
res = false;
return res;
}
+/* Create a reduction_info struct, initialize it with REDUC_STMT
+ and PHI, insert it to the REDUCTION_LIST. */
+
+static void
+build_new_reduction (htab_t reduction_list, gimple reduc_stmt, gimple phi)
+{
+ PTR *slot;
+ struct reduction_info *new_reduction;
+
+ 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");
+ }
+
+ new_reduction = XCNEW (struct reduction_info);
+
+ new_reduction->reduc_stmt = reduc_stmt;
+ new_reduction->reduc_phi = phi;
+ new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
+ slot = htab_find_slot (reduction_list, new_reduction, INSERT);
+ *slot = new_reduction;
+}
+
+/* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
+
+static void
+gather_scalar_reductions (loop_p loop, htab_t reduction_list)
+{
+ gimple_stmt_iterator gsi;
+ loop_vec_info simple_loop_info;
+
+ vect_dump = NULL;
+ simple_loop_info = vect_analyze_loop_form (loop);
+
+ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+ affine_iv iv;
+ tree res = PHI_RESULT (phi);
+ bool double_reduc;
+
+ if (!is_gimple_reg (res))
+ continue;
+
+ if (!simple_iv (loop, loop, res, &iv, true)
+ && simple_loop_info)
+ {
+ gimple reduc_stmt = vect_is_simple_reduction (simple_loop_info, phi, true, &double_reduc);
+ if (reduc_stmt)
+ build_new_reduction (reduction_list, reduc_stmt, phi);
+ }
+ }
+ destroy_loop_vec_info (simple_loop_info, true);
+}
+
+/* Try to initialize NITER for code generation part. */
+
+static bool
+try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
+{
+ edge exit = single_dom_exit (loop);
+
+ gcc_assert (exit);
+
+ /* We need to know # of iterations, and there should be no uses of values
+ defined inside loop outside of it, unless the values are invariants of
+ the loop. */
+ if (!number_of_iterations_exit (loop, exit, niter, false))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " FAILED: number of iterations not known\n");
+ return false;
+ }
+
+ return true;
+}
+
+/* Try to initialize REDUCTION_LIST for code generation part.
+ REDUCTION_LIST describes the reductions. */
+
+static bool
+try_create_reduction_list (loop_p loop, htab_t reduction_list)
+{
+ edge exit = single_dom_exit (loop);
+ gimple_stmt_iterator gsi;
+
+ gcc_assert (exit);
+
+ 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);
+ struct reduction_info *red;
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
+ gimple reduc_phi;
+ tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+
+ if (is_gimple_reg (val))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "phi is ");
+ print_gimple_stmt (dump_file, phi, 0, 0);
+ fprintf (dump_file, "arg of phi to exit: value ");
+ print_generic_expr (dump_file, val, 0);
+ fprintf (dump_file, " used outside loop\n");
+ fprintf (dump_file,
+ " checking if it a part of reduction pattern: \n");
+ }
+ if (htab_elements (reduction_list) == 0)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ " FAILED: it is not a part of reduction.\n");
+ return false;
+ }
+ reduc_phi = NULL;
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
+ {
+ if (flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
+ {
+ reduc_phi = USE_STMT (use_p);
+ break;
+ }
+ }
+ red = reduction_phi (reduction_list, reduc_phi);
+ if (red == NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ " FAILED: it is not a part of reduction.\n");
+ return false;
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "reduction phi is ");
+ print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
+ fprintf (dump_file, "reduction stmt is ");
+ print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
+ }
+ }
+ }
+
+ /* The iterations of the loop may communicate only through bivs whose
+ 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);
+ tree def = PHI_RESULT (phi);
+ affine_iv iv;
+
+ if (is_gimple_reg (def) && !simple_iv (loop, loop, def, &iv, true))
+ {
+ struct reduction_info *red;
+
+ red = reduction_phi (reduction_list, phi);
+ if (red == NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ " FAILED: scalar dependency between iterations\n");
+ return false;
+ }
+ }
+ }
+
+
+ return true;
+}
+
/* Detect parallel loops and generate parallel code using libgomp
primitives. Returns true if some loop was parallelized, false
otherwise. */
return false;
reduction_list = htab_create (10, reduction_info_hash,
- reduction_info_eq, free);
+ reduction_info_eq, free);
+ init_stmt_vec_info_vec ();
FOR_EACH_LOOP (li, loop, 0)
{
htab_empty (reduction_list);
- if (/* Do not bother with loops in cold areas. */
- !maybe_hot_bb_p (loop->header)
- /* Or loops that roll too little. */
- || expected_loop_iterations (loop) <= n_threads
- /* And of course, the loop must be parallelizable. */
- || !can_duplicate_loop_p (loop)
+
+ /* FIXME: Only consider innermost loops with just one exit. */
+ if (loop->inner || !single_dom_exit (loop))
+ continue;
+
+ if (/* And of course, the loop must be parallelizable. */
+ !can_duplicate_loop_p (loop)
|| loop_has_blocks_with_irreducible_flag (loop)
/* FIXME: the check for vector phi nodes could be removed. */
- || loop_has_vector_phi_nodes (loop)
- || !loop_parallel_p (loop, reduction_list, &niter_desc))
+ || loop_has_vector_phi_nodes (loop))
+ continue;
+
+ if (/* Do not bother with loops in cold areas. */
+ optimize_loop_nest_for_size_p (loop)
+ /* Or loops that roll too little. */
+ || expected_loop_iterations (loop) <= n_threads)
+ continue;
+ if (!try_get_loop_niter (loop, &niter_desc))
+ continue;
+
+ if (!try_create_reduction_list (loop, reduction_list))
+ continue;
+
+ if (!loop_parallel_p (loop))
continue;
changed = true;
- gen_parallel_loop (loop, reduction_list, n_threads, &niter_desc);
+ gen_parallel_loop (loop, reduction_list,
+ n_threads, &niter_desc);
verify_flow_info ();
verify_dominators (CDI_DOMINATORS);
verify_loop_structure ();
verify_loop_closed_ssa ();
}
+ free_stmt_vec_info_vec ();
htab_delete (reduction_list);
+
+ /* Parallelization will cause new function calls to be inserted through
+ which local variables will escape. Reset the points-to solutions
+ for ESCAPED and CALLUSED. */
+ if (changed)
+ {
+ pt_solution_reset (&cfun->gimple_df->escaped);
+ pt_solution_reset (&cfun->gimple_df->callused);
+ }
+
return changed;
}
OSDN Git Service
