diff options
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/ChangeLog | 114 | ||||
| -rw-r--r-- | gcc/graphite-isl-ast-to-gimple.c | 151 | ||||
| -rw-r--r-- | gcc/graphite-poly.c | 26 | ||||
| -rw-r--r-- | gcc/graphite-poly.h | 35 | ||||
| -rw-r--r-- | gcc/graphite-scop-detection.c | 161 | ||||
| -rw-r--r-- | gcc/graphite-sese-to-poly.c | 799 | ||||
| -rw-r--r-- | gcc/graphite.c | 14 | ||||
| -rw-r--r-- | gcc/sese.c | 1543 | ||||
| -rw-r--r-- | gcc/sese.h | 60 |
9 files changed, 1953 insertions, 950 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index efbd38f..fcf0bf6 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,117 @@ +2015-11-11 Aditya Kumar <aditya.k7@samsung.com> + Sebastian Pop <s.pop@samsung.com> + + * graphite-isl-ast-to-gimple.c (class translate_isl_ast_to_gimple): + New member codegen_error + (translate_isl_ast_for_loop): Remove call to single_succ_edge and + early return. + (translate_isl_ast_node_user): Early return in case of error. + (translate_isl_ast_to_gimple::translate_isl_ast): Same. + (translate_isl_ast_to_gimple::translate_pending_phi_nodes): New. + (add_parameters_to_ivs_params): Remove macro. + (graphite_regenerate_ast_isl): Add if_region pointer to region. + * graphite-poly.c (new_poly_dr): Remove macro. + (print_pdr): Same. + (new_gimple_poly_bb): Same. + (free_gimple_poly_bb): Same. + (print_scop_params): Same. + * graphite-poly.h (struct poly_dr): Same. + (struct poly_bb): Add new_bb. + (gbb_from_bb): Remove dead code. + (pbb_from_bb): Same. + * graphite-scop-detection.c (parameter_index_in_region_1): Same. + (parameter_index_in_region): Same. + (find_scop_parameters): Same. + (build_cross_bb_scalars_def): New. + (build_cross_bb_scalars_use): New. + (graphite_find_cross_bb_scalar_vars): New + (try_generate_gimple_bb): Reads and Writes. + (build_alias_set): Move. + (gather_bbs::before_dom_children): Gather bbs visited. + (build_scops): call build_alias_set. + * graphite-sese-to-poly.c (phi_arg_in_outermost_loop): Delete. + (remove_simple_copy_phi): Delete. + (remove_invariant_phi): Delete. + (simple_copy_phi_p): Delete. + (reduction_phi_p): Delete. + (isl_id_for_dr): Remove unused param. + (parameter_index_in_region_1): Remove macro usage. + (set_scop_parameter_dim): Same. + (add_param_constraints): Same. + (add_conditions_to_constraints): Same + (build_scop_iteration_domain): Same. + (pdr_add_alias_set): Comment. + (add_scalar_version_numbers): New. + (build_poly_dr): ISL id. + (build_scop_drs): Move. + (build_poly_sr_1): Same. + (insert_stmts): Remove. + (build_poly_sr): New. + (new_pbb_from_pbb): Delete. + (insert_out_of_ssa_copy_on_edge): Delete. + (create_zero_dim_array): Delete. + (scalar_close_phi_node_p): Delete. + (propagate_expr_outside_region): Delete. + (rewrite_close_phi_out_of_ssa): Delete. + (rewrite_phi_out_of_ssa): Delete. + (rewrite_degenerate_phi): Delete. + (rewrite_reductions_out_of_ssa): Delete. + (rewrite_cross_bb_scalar_dependence): Delete. + (handle_scalar_deps_crossing_scop_limits): + (rewrite_cross_bb_scalar_deps): Delete. + (build_poly_scop): Remove calls to out-of-ssa functions. + * graphite.c (graphite_transform_loops): Early return in case of + codegen error. + * sese.c (debug_rename_map_1): Delete. + (debug_rename_map): Delete. + (sese_record_loop): Remove macro. + (build_sese_loop_nests): Same. + (new_sese_info): Same. + (free_sese_info): Same. + (sese_insert_phis_for_liveouts): + (is_loop_closed_ssa_use): New. + (number_of_phi_nodes): New. + (bb_contains_loop_close_phi_nodes): New. + (bb_contains_loop_phi_nodes): New. + (phi_uses_name): New. + (is_valid_rename): + (get_rename): Add old_bb and loop_phi for more precise matching of + exprs. + (set_rename): Pass region. + (later_of_the_two): New. + (gsi_insert_earliest): New. + (collect_all_ssa_names): New. + (substitute_ssa_name): New. + (rename_all_uses): New. + (get_rename_from_scev): New. + (rename_uses): Pass old_bb for more precise matching of exprs. + (get_def_bb_for_const): New. + (get_new_name): New. + (get_loc): New. + (get_edges): New. + (copy_loop_phi_args): New. + (copy_loop_phi_nodes): New. + (get_loop_init_value): New. + (find_init_value): New. + (find_init_value_close_phi): New. + (copy_loop_close_phi_args): New. + (copy_loop_close_phi_nodes): New. + (add_phi_arg_for_new_expr): New. + (copy_cond_phi_args): New. + (copy_cond_phi_nodes): New. + (copy_phi_nodes): New. + (should_copy_to_new_region): New. + (set_rename_for_each_def): New. + (graphite_copy_stmts_from_block): Early return in case of error. + (copy_bb_and_scalar_dependences): Same. + * sese.h (vec_find): New. + (SESE_PARAMS): Delete. + (SESE_LOOPS): Delete. + (SESE_LOOP_NEST): Delete. + (sese_contains_loop): Remove macro usage. + (sese_nb_params): Same. + (struct gimple_poly_bb): Added read_scalar_refs, write_scalar_refs. + 2015-11-11 Abderrazek Zaafrani <a.zaafrani@samsung.com> * graphite-sese-to-poly.c (build_scop_original_schedule): Call diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c index 628fc90..7fa4ce3 100644 --- a/gcc/graphite-isl-ast-to-gimple.c +++ b/gcc/graphite-isl-ast-to-gimple.c @@ -63,11 +63,7 @@ extern "C" { #include <map> #include "graphite-isl-ast-to-gimple.h" #include "tree-cfg.h" - -/* This flag is set when an error occurred during the translation of - ISL AST to Gimple. */ - -static bool graphite_regenerate_error; +#include "gimple-pretty-print.h" /* We always try to use signed 128 bit types, but fall back to smaller types in case a platform does not provide types of these sizes. In the future we @@ -132,7 +128,7 @@ class translate_isl_ast_to_gimple { public: translate_isl_ast_to_gimple (sese_info_p r) - : region (r) + : region (r), codegen_error (false) { } /* Translates an ISL AST node NODE to GCC representation in the @@ -261,8 +257,17 @@ class translate_isl_ast_to_gimple void build_iv_mapping (vec<tree> iv_map, gimple_poly_bb_p gbb, __isl_keep isl_ast_expr *user_expr, ivs_params &ip, sese_l ®ion); + + void translate_pending_phi_nodes (void); + + bool codegen_error_p () { return codegen_error; } + private: sese_info_p region; + + /* This flag is set when an error occurred during the translation of ISL AST + to Gimple. */ + bool codegen_error; }; /* Return the tree variable that corresponds to the given isl ast identifier @@ -575,13 +580,15 @@ translate_isl_ast_for_loop (loop_p context_loop, edge to_body = single_succ_edge (loop->header); basic_block after = to_body->dest; - /* Create a basic block for loop close phi nodes. */ - last_e = single_succ_edge (split_edge (last_e)); - /* Translate the body of the loop. */ isl_ast_node *for_body = isl_ast_node_for_get_body (node_for); next_e = translate_isl_ast (loop, for_body, to_body, ip); isl_ast_node_free (for_body); + + /* Early return if we failed to translate loop body. */ + if (!next_e || codegen_error) + return NULL; + redirect_edge_succ_nodup (next_e, after); set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); @@ -770,14 +777,17 @@ translate_isl_ast_node_user (__isl_keep isl_ast_node *node, edge next_e, ivs_params &ip) { gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user); + isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node); isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0); gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id); + isl_id *name_id = isl_ast_expr_get_id (name_expr); poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id); gcc_assert (pbb); + gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); - vec<tree> iv_map; + isl_ast_expr_free (name_expr); isl_id_free (name_id); @@ -785,6 +795,7 @@ translate_isl_ast_node_user (__isl_keep isl_ast_node *node, "The entry block should not even appear within a scop"); int nb_loops = number_of_loops (cfun); + vec<tree> iv_map; iv_map.create (nb_loops); iv_map.safe_grow_cleared (nb_loops); @@ -793,23 +804,35 @@ translate_isl_ast_node_user (__isl_keep isl_ast_node *node, if (dump_file) { - fprintf (dump_file, "[codegen] copying"); + fprintf (dump_file, "[codegen] copying from basic block\n"); print_loops_bb (dump_file, GBB_BB (gbb), 0, 3); + fprintf (dump_file, "\n[codegen] to new basic block\n"); + print_loops_bb (dump_file, next_e->src, 0, 3); } next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), pbb->scop->scop_info, next_e, iv_map, - &graphite_regenerate_error); + &codegen_error); + if (codegen_error) + return NULL; + if (dump_file) { - fprintf (dump_file, "[codegen] to"); + fprintf (dump_file, "\n[codegen] (after copy) new basic block\n"); print_loops_bb (dump_file, next_e->src, 0, 3); } iv_map.release (); mark_virtual_operands_for_renaming (cfun); update_ssa (TODO_update_ssa); + + if (dump_file) + { + fprintf (dump_file, "\n[codegen] (after update SSA) new basic block\n"); + print_loops_bb (dump_file, next_e->src, 0, 3); + } + return next_e; } @@ -881,6 +904,9 @@ translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node, edge next_e, ivs_params &ip) { + if (codegen_error) + return NULL; + switch (isl_ast_node_get_type (node)) { case isl_ast_node_error: @@ -906,6 +932,47 @@ translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop, } } +/* Patch the missing arguments of the phi nodes. */ + +void +translate_isl_ast_to_gimple::translate_pending_phi_nodes () +{ + int i; + phi_rename *rename; + FOR_EACH_VEC_ELT (region->incomplete_phis, i, rename) + { + gphi *old_phi = rename->first; + gphi *new_phi = rename->second; + basic_block old_bb = gimple_bb (old_phi); + basic_block new_bb = gimple_bb (new_phi); + + /* First edge is the init edge and second is the back edge. */ + init_back_edge_pair_t ibp_old_bb = get_edges (old_bb); + init_back_edge_pair_t ibp_new_bb = get_edges (new_bb); + + if (dump_file) + { + fprintf (dump_file, "\n[codegen] translating pending old-phi: "); + print_gimple_stmt (dump_file, old_phi, 0, 0); + } + + auto_vec <tree, 1> iv_map; + if (bb_contains_loop_phi_nodes (new_bb)) + copy_loop_phi_args (old_phi, ibp_old_bb, new_phi, + ibp_new_bb, region, false); + else if (bb_contains_loop_close_phi_nodes (new_bb)) + copy_loop_close_phi_args (old_bb, new_bb, region, false); + else if (!copy_cond_phi_args (old_phi, new_phi, iv_map, region, false)) + gcc_unreachable (); + + if (dump_file) + { + fprintf (dump_file, "[codegen] to new-phi: "); + print_gimple_stmt (dump_file, new_phi, 0, 0); + } + } +} + /* Prints NODE to FILE. */ void @@ -926,13 +993,13 @@ add_parameters_to_ivs_params (scop_p scop, ivs_params &ip) { sese_info_p region = scop->scop_info; unsigned nb_parameters = isl_set_dim (scop->param_context, isl_dim_param); - gcc_assert (nb_parameters == SESE_PARAMS (region).length ()); + gcc_assert (nb_parameters == region->params.length ()); unsigned i; for (i = 0; i < nb_parameters; i++) { isl_id *tmp_id = isl_set_get_dim_id (scop->param_context, isl_dim_param, i); - ip[tmp_id] = SESE_PARAMS (region)[i]; + ip[tmp_id] = region->params[i]; } } @@ -1101,7 +1168,6 @@ graphite_regenerate_ast_isl (scop_p scop) ivs_params ip; timevar_push (TV_GRAPHITE_CODE_GEN); - graphite_regenerate_error = false; root_node = scop_to_isl_ast (scop, ip); if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1115,30 +1181,47 @@ graphite_regenerate_ast_isl (scop_p scop) graphite_verify (); if_region = move_sese_in_condition (region); - sese_insert_phis_for_liveouts (region, - if_region->region->region.exit->src, - if_region->false_region->region.exit, - if_region->true_region->region.exit); + region->if_region = if_region; recompute_all_dominators (); - graphite_verify (); context_loop = region->region.entry->src->loop_father; translate_isl_ast_to_gimple t(region); edge e = single_succ_edge (if_region->true_region->region.entry->dest); - split_edge (e); - t.translate_isl_ast (context_loop, root_node, e, ip); + basic_block bb = split_edge (e); + /* Update the true_region exit edge. */ + region->if_region->true_region->region.exit = single_succ_edge (bb); - mark_virtual_operands_for_renaming (cfun); - update_ssa (TODO_update_ssa); - - graphite_verify (); - scev_reset (); - recompute_all_dominators (); - graphite_verify (); - - if (graphite_regenerate_error) - set_ifsese_condition (if_region, integer_zero_node); + t.translate_isl_ast (context_loop, root_node, e, ip); + if (t.codegen_error_p ()) + { + if (dump_file) + fprintf (dump_file, "\n[codegen] unsuccessful, " + "reverting back to the original code."); + set_ifsese_condition (if_region, integer_zero_node); + } + else + { + t.translate_pending_phi_nodes (); + if (!t.codegen_error_p ()) + { + sese_insert_phis_for_liveouts (region, + if_region->region->region.exit->src, + if_region->false_region->region.exit, + if_region->true_region->region.exit); + mark_virtual_operands_for_renaming (cfun); + update_ssa (TODO_update_ssa); + + + graphite_verify (); + scev_reset (); + recompute_all_dominators (); + graphite_verify (); + } + else if (dump_file) + fprintf (dump_file, "\n[codegen] unsuccessful in translating " + "pending phis, reverting back to the original code."); + } free (if_region->true_region); free (if_region->region); @@ -1161,6 +1244,6 @@ graphite_regenerate_ast_isl (scop_p scop) num_no_dependency); } - return !graphite_regenerate_error; + return !t.codegen_error_p (); } #endif /* HAVE_isl */ diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 36c3061..5928b4c 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -132,21 +132,19 @@ apply_poly_transforms (scop_p scop) NB_SUBSCRIPTS. */ void -new_poly_dr (poly_bb_p pbb, enum poly_dr_type type, data_reference_p cdr, - graphite_dim_t nb_subscripts, +new_poly_dr (poly_bb_p pbb, gimple *stmt, enum poly_dr_type type, isl_map *acc, isl_set *subscript_sizes) { static int id = 0; poly_dr_p pdr = XNEW (struct poly_dr); + pdr->stmt = stmt; PDR_ID (pdr) = id++; PDR_NB_REFS (pdr) = 1; PDR_PBB (pdr) = pbb; pdr->accesses = acc; pdr->subscript_sizes = subscript_sizes; PDR_TYPE (pdr) = type; - PDR_CDR (pdr) = cdr; - PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts; PBB_DRS (pbb).safe_push (pdr); } @@ -226,6 +224,8 @@ print_pdr (FILE *file, poly_dr_p pdr) gcc_unreachable (); } + fprintf (file, "in gimple stmt: "); + print_gimple_stmt (file, pdr->stmt, 0, 0); fprintf (file, "data accesses: "); print_isl_map (file, pdr->accesses); fprintf (file, "subscript sizes: "); @@ -244,14 +244,14 @@ debug_pdr (poly_dr_p pdr) /* Store the GRAPHITE representation of BB. */ gimple_poly_bb_p -new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs) +new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs, + vec<scalar_use> reads, vec<tree> writes) { - gimple_poly_bb_p gbb; - - gbb = XNEW (struct gimple_poly_bb); - bb->aux = gbb; + gimple_poly_bb_p gbb = XNEW (struct gimple_poly_bb); GBB_BB (gbb) = bb; GBB_DATA_REFS (gbb) = drs; + gbb->read_scalar_refs = reads; + gbb->write_scalar_refs = writes; GBB_CONDITIONS (gbb).create (0); GBB_CONDITION_CASES (gbb).create (0); @@ -264,10 +264,10 @@ void free_gimple_poly_bb (gimple_poly_bb_p gbb) { free_data_refs (GBB_DATA_REFS (gbb)); - GBB_CONDITIONS (gbb).release (); GBB_CONDITION_CASES (gbb).release (); - GBB_BB (gbb)->aux = 0; + gbb->read_scalar_refs.release (); + gbb->write_scalar_refs.release (); XDELETE (gbb); } @@ -477,13 +477,13 @@ print_pbb (FILE *file, poly_bb_p pbb) void print_scop_params (FILE *file, scop_p scop) { - if (SESE_PARAMS (scop->scop_info).is_empty ()) + if (scop->scop_info->params.is_empty ()) return; int i; tree t; fprintf (file, "parameters ("); - FOR_EACH_VEC_ELT (SESE_PARAMS (scop->scop_info), i, t) + FOR_EACH_VEC_ELT (scop->scop_info->params, i, t) { print_generic_expr (file, t, 0); fprintf (file, ", "); diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index b35431a..3fcbbaf 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -58,8 +58,8 @@ struct poly_dr /* The number of data refs identical to this one in the PBB. */ int nb_refs; - /* A pointer to compiler's data reference description. */ - data_reference_p compiler_dr; + /* A pointer to the gimple stmt containing this reference. */ + gimple *stmt; /* A pointer to the PBB that contains this data reference. */ poly_bb_p pbb; @@ -181,21 +181,16 @@ struct poly_dr In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */ isl_map *accesses; isl_set *subscript_sizes; - - /* The number of subscripts. */ - graphite_dim_t nb_subscripts; }; #define PDR_ID(PDR) (PDR->id) #define PDR_NB_REFS(PDR) (PDR->nb_refs) -#define PDR_CDR(PDR) (PDR->compiler_dr) #define PDR_PBB(PDR) (PDR->pbb) #define PDR_TYPE(PDR) (PDR->type) #define PDR_ACCESSES(PDR) (NULL) -#define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts) -void new_poly_dr (poly_bb_p, enum poly_dr_type, data_reference_p, - graphite_dim_t, isl_map *, isl_set *); +void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type, + isl_map *, isl_set *); void free_poly_dr (poly_dr_p); void debug_pdr (poly_dr_p); void print_pdr (FILE *, poly_dr_p); @@ -270,6 +265,9 @@ struct poly_bb /* True when this PBB contains only a reduction statement. */ bool is_reduction; + + /* The last basic block generated for this pbb. */ + basic_block new_bb; }; #define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box) @@ -314,22 +312,6 @@ extern bool optimize_isl (scop_p); extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t); extern void debug_gmp_value (mpz_t); -/* Returns a gimple_bb from BB. */ - -static inline gimple_poly_bb_p -gbb_from_bb (basic_block bb) -{ - return (gimple_poly_bb_p) bb->aux; -} - -/* The poly_bb of the BB. */ - -static inline poly_bb_p -pbb_from_bb (basic_block bb) -{ - return GBB_PBB (gbb_from_bb (bb)); -} - /* The basic block of the PBB. */ static inline basic_block @@ -446,7 +428,8 @@ struct scop extern scop_p new_scop (edge, edge); extern void free_scop (scop_p); -extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>); +extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>, + vec<scalar_use>, vec<tree>); extern void free_gimple_poly_bb (gimple_poly_bb_p); extern void print_generated_program (FILE *, scop_p); extern void debug_generated_program (scop_p); diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index 9fb8264..a7179d9 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -1507,7 +1507,7 @@ parameter_index_in_region_1 (tree name, sese_info_p region) gcc_assert (TREE_CODE (name) == SSA_NAME); - FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, p) + FOR_EACH_VEC_ELT (region->params, i, p) if (p == name) return i; @@ -1536,8 +1536,8 @@ parameter_index_in_region (tree name, sese_info_p region) if (i != -1) return i; - i = SESE_PARAMS (region).length (); - SESE_PARAMS (region).safe_push (name); + i = region->params.length (); + region->params.safe_push (name); return i; } @@ -1635,7 +1635,7 @@ find_scop_parameters (scop_p scop) struct loop *loop; /* Find the parameters used in the loop bounds. */ - FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop) + FOR_EACH_VEC_ELT (region->loop_nest, i, loop) { tree nb_iters = number_of_latch_executions (loop); @@ -1655,6 +1655,94 @@ find_scop_parameters (scop_p scop) scop_set_nb_params (scop, nbp); } +/* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */ + +static void +build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb, + vec<tree> *writes) +{ + gcc_assert (def); + if (!is_gimple_reg (def)) + return; + + /* Do not gather scalar variables that can be analyzed by SCEV as they can be + generated out of the induction variables. */ + if (scev_analyzable_p (def, scop->scop_info->region)) + return; + + gimple *use_stmt; + imm_use_iterator imm_iter; + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) + if (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)) + { + writes->safe_push (def); + DEBUG_PRINT (dp << "Adding scalar write:\n"; + print_generic_expr (dump_file, def, 0); + dp << "From stmt:\n"; + print_gimple_stmt (dump_file, + SSA_NAME_DEF_STMT (def), 0, 0)); + /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break + before all the uses have been visited. */ + BREAK_FROM_IMM_USE_STMT (imm_iter); + } +} + +/* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */ + +static void +build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt, + vec<scalar_use> *reads) +{ + gcc_assert (use); + if (!is_gimple_reg (use)) + return; + + /* Do not gather scalar variables that can be analyzed by SCEV as they can be + generated out of the induction variables. */ + if (scev_analyzable_p (use, scop->scop_info->region)) + return; + + gimple *def_stmt = SSA_NAME_DEF_STMT (use); + if (gimple_bb (def_stmt) != gimple_bb (use_stmt)) + { + DEBUG_PRINT (dp << "Adding scalar read:\n"; + print_generic_expr (dump_file, use, 0); + dp << "From stmt:\n"; + print_gimple_stmt (dump_file, use_stmt, 0, 0)); + reads->safe_push (std::make_pair (use_stmt, use)); + } +} + +/* Record all scalar variables that are defined and used in different BBs of the + SCOP. */ + +static void +graphite_find_cross_bb_scalar_vars (scop_p scop, gimple *stmt, + vec<scalar_use> *reads, vec<tree> *writes) +{ + tree def; + + if (gimple_code (stmt) == GIMPLE_ASSIGN) + def = gimple_assign_lhs (stmt); + else if (gimple_code (stmt) == GIMPLE_CALL) + def = gimple_call_lhs (stmt); + else if (gimple_code (stmt) == GIMPLE_PHI) + def = gimple_phi_result (stmt); + else + return; + + + build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), writes); + + ssa_op_iter iter; + use_operand_p use_p; + FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) + { + tree use = USE_FROM_PTR (use_p); + build_cross_bb_scalars_use (scop, use, stmt, reads); + } +} + /* Generates a polyhedral black box only if the bb contains interesting information. */ @@ -1662,7 +1750,12 @@ static gimple_poly_bb_p try_generate_gimple_bb (scop_p scop, basic_block bb) { vec<data_reference_p> drs; - drs.create (5); + drs.create (3); + vec<tree> writes; + writes.create (3); + vec<scalar_use> reads; + reads.create (3); + sese_l region = scop->scop_info->region; loop_p nest = outermost_loop_in_sese (region, bb); @@ -1670,17 +1763,58 @@ try_generate_gimple_bb (scop_p scop, basic_block bb) if (!loop_in_sese_p (loop, region)) loop = nest; - gimple_stmt_iterator gsi; - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) { gimple *stmt = gsi_stmt (gsi); if (is_gimple_debug (stmt)) continue; graphite_find_data_references_in_stmt (nest, loop, stmt, &drs); + graphite_find_cross_bb_scalar_vars (scop, stmt, &reads, &writes); } - return new_gimple_poly_bb (bb, drs); + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + if (!virtual_operand_p (gimple_phi_result (psi.phi ()))) + graphite_find_cross_bb_scalar_vars (scop, psi.phi (), &reads, &writes); + + if (drs.is_empty () && writes.is_empty () && reads.is_empty ()) + return NULL; + + return new_gimple_poly_bb (bb, drs, reads, writes); +} + +/* Compute alias-sets for all data references in DRS. */ + +static void +build_alias_set (scop_p scop) +{ + int num_vertices = scop->drs.length (); + struct graph *g = new_graph (num_vertices); + dr_info *dr1, *dr2; + int i, j; + int *all_vertices; + + FOR_EACH_VEC_ELT (scop->drs, i, dr1) + for (j = i+1; scop->drs.iterate (j, &dr2); j++) + if (dr_may_alias_p (dr1->dr, dr2->dr, true)) + { + add_edge (g, i, j); + add_edge (g, j, i); + } + + all_vertices = XNEWVEC (int, num_vertices); + for (i = 0; i < num_vertices; i++) + all_vertices[i] = i; + + graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL); + free (all_vertices); + + for (i = 0; i < g->n_vertices; i++) + scop->drs[i].alias_set = g->vertices[i].component + 1; + + free_graph (g); } /* Gather BBs and conditions for a SCOP. */ @@ -1728,11 +1862,19 @@ gather_bbs::before_dom_children (basic_block bb) scop->scop_info->bbs.safe_push (bb); gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb); + if (!gbb) + return; + GBB_CONDITIONS (gbb) = conditions.copy (); GBB_CONDITION_CASES (gbb) = cases.copy (); poly_bb_p pbb = new_poly_bb (scop, gbb); scop->pbbs.safe_push (pbb); + + int i; + data_reference_p dr; + FOR_EACH_VEC_ELT (gbb->data_refs, i, dr) + scop->drs.safe_push (dr_info (dr, pbb)); } /* Call-back for dom_walk executed after visiting the dominated @@ -1776,6 +1918,8 @@ build_scops (vec<scop_p> *scops) /* Record all basic blocks and their conditions in REGION. */ gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr); + build_alias_set (scop); + /* Do not optimize a scop containing only PBBs that do not belong to any loops. */ if (sb.nb_pbbs_in_loops (scop) == 0) @@ -1807,7 +1951,6 @@ build_scops (vec<scop_p> *scops) << scop_nb_params (scop) << " larger than --param graphite-max-nb-scop-params=" << max_dim << ".\n"); - free_scop (scop); continue; } diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 3c24512..83acc4a 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -75,124 +75,6 @@ tree_int_to_gmp (tree t, mpz_t res) wi::to_mpz (t, res, TYPE_SIGN (TREE_TYPE (t))); } -/* Returns the index of the PHI argument defined in the outermost - loop. */ - -static size_t -phi_arg_in_outermost_loop (gphi *phi) -{ - loop_p loop = gimple_bb (phi)->loop_father; - size_t i, res = 0; - - for (i = 0; i < gimple_phi_num_args (phi); i++) - if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src)) - { - loop = gimple_phi_arg_edge (phi, i)->src->loop_father; - res = i; - } - - return res; -} - -/* Removes a simple copy phi node "RES = phi (INIT, RES)" at position - PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */ - -static void -remove_simple_copy_phi (gphi_iterator *psi) -{ - gphi *phi = psi->phi (); - tree res = gimple_phi_result (phi); - size_t entry = phi_arg_in_outermost_loop (phi); - tree init = gimple_phi_arg_def (phi, entry); - gassign *stmt = gimple_build_assign (res, init); - edge e = gimple_phi_arg_edge (phi, entry); - - remove_phi_node (psi, false); - gsi_insert_on_edge_immediate (e, stmt); -} - -/* Removes an invariant phi node at position PSI by inserting on the - loop ENTRY edge the assignment RES = INIT. */ - -static void -remove_invariant_phi (sese_l ®ion, gphi_iterator *psi) -{ - gphi *phi = psi->phi (); - loop_p loop = loop_containing_stmt (phi); - tree res = gimple_phi_result (phi); - tree scev = scalar_evolution_in_region (region, loop, res); - size_t entry = phi_arg_in_outermost_loop (phi); - edge e = gimple_phi_arg_edge (phi, entry); - tree var; - gassign *stmt; - gimple_seq stmts = NULL; - - if (tree_contains_chrecs (scev, NULL)) - scev = gimple_phi_arg_def (phi, entry); - - var = force_gimple_operand (scev, &stmts, true, NULL_TREE); - stmt = gimple_build_assign (res, var); - remove_phi_node (psi, false); - - gimple_seq_add_stmt (&stmts, stmt); - gsi_insert_seq_on_edge (e, stmts); - gsi_commit_edge_inserts (); - SSA_NAME_DEF_STMT (res) = stmt; -} - -/* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */ - -static inline bool -simple_copy_phi_p (gphi *phi) -{ - if (gimple_phi_num_args (phi) != 2) - return false; - - tree res = gimple_phi_result (phi); - return (res == gimple_phi_arg_def (phi, 0) - || res == gimple_phi_arg_def (phi, 1)); -} - -/* Returns true when the phi node at position PSI is a reduction phi - node in REGION. Otherwise moves the pointer PSI to the next phi to - be considered. */ - -static bool -reduction_phi_p (sese_l ®ion, gphi_iterator *psi) -{ - loop_p loop; - gphi *phi = psi->phi (); - tree res = gimple_phi_result (phi); - - loop = loop_containing_stmt (phi); - - if (simple_copy_phi_p (phi)) - { - /* PRE introduces phi nodes like these, for an example, - see id-5.f in the fortran graphite testsuite: - - # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)> - */ - remove_simple_copy_phi (psi); - return false; - } - - if (scev_analyzable_p (res, region)) - { - tree scev = scalar_evolution_in_region (region, loop, res); - - if (evolution_function_is_invariant_p (scev, loop->num)) - remove_invariant_phi (region, psi); - else - gsi_next (psi); - - return false; - } - - /* All the other cases are considered reductions. */ - return true; -} - /* Return an ISL identifier for the polyhedral basic block PBB. */ static isl_id * @@ -532,14 +414,14 @@ isl_id_for_ssa_name (scop_p s, tree e) return id; } -/* Return an ISL identifier for the data reference DR. */ +/* Return an ISL identifier for the data reference DR. Data references and + scalar references get the same isl_id. They need to be comparable and are + distinguished through the first dimension, which contains the alias set or + SSA_NAME_VERSION number. */ static isl_id * -isl_id_for_dr (scop_p s, data_reference_p dr ATTRIBUTE_UNUSED) +isl_id_for_dr (scop_p s) { - /* Data references all get the same isl_id. They need to be comparable - and are distinguished through the first dimension, which contains the - alias set number. */ return isl_id_alloc (s->isl_context, "", 0); } @@ -612,7 +494,7 @@ parameter_index_in_region_1 (tree name, sese_info_p region) gcc_assert (TREE_CODE (name) == SSA_NAME); - FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, p) + FOR_EACH_VEC_ELT (region->params, i, p) if (p == name) return i; @@ -700,7 +582,7 @@ set_scop_parameter_dim (scop_p scop) unsigned i; tree e; - FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, e) + FOR_EACH_VEC_ELT (region->params, i, e) space = isl_space_set_dim_id (space, isl_dim_param, i, isl_id_for_ssa_name (scop, e)); @@ -941,7 +823,7 @@ add_conditions_to_constraints (scop_p scop) static void add_param_constraints (scop_p scop, graphite_dim_t p) { - tree parameter = SESE_PARAMS (scop->scop_info)[p]; + tree parameter = scop->scop_info->params[p]; tree type = TREE_TYPE (parameter); tree lb = NULL_TREE; tree ub = NULL_TREE; @@ -1021,7 +903,7 @@ build_scop_iteration_domain (scop_p scop) int i; struct loop *loop; - FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop) + FOR_EACH_VEC_ELT (region->loop_nest, i, loop) if (!loop_in_sese_p (loop_outer (loop), region->region)) build_loop_iteration_domains (scop, loop, 0, isl_set_copy (scop->param_context), doms); @@ -1057,12 +939,32 @@ pdr_add_alias_set (isl_map *acc, dr_info &dri) { isl_constraint *c = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc))); + /* Positive numbers for all alias sets. */ c = isl_constraint_set_constant_si (c, -dri.alias_set); c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); return isl_map_add_constraint (acc, c); } +/* Add a constrain to the ACCESSES polyhedron for the alias set of + data reference DR. ACCESSP_NB_DIMS is the dimension of the + ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration + domain. */ + +static isl_map * +add_scalar_version_numbers (isl_map *acc, tree var) +{ + isl_constraint *c = isl_equality_alloc + (isl_local_space_from_space (isl_map_get_space (acc))); + int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP); + /* Each scalar variables has a unique alias set number starting from + max_arrays. */ + c = isl_constraint_set_constant_si (c, -max_arrays - SSA_NAME_VERSION (var)); + c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); + + return isl_map_add_constraint (acc, c); +} + /* Assign the affine expression INDEX to the output dimension POS of MAP and return the result. */ @@ -1178,7 +1080,7 @@ pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop, return subscript_sizes; } -/* Build data accesses for DR in PBB. */ +/* Build data accesses for DRI. */ static void build_poly_dr (dr_info &dri) @@ -1188,6 +1090,7 @@ build_poly_dr (dr_info &dri) poly_bb_p pbb = dri.pbb; data_reference_p dr = dri.dr; scop_p scop = PBB_SCOP (pbb); + isl_id *id = isl_id_for_dr (scop); { isl_space *dc = isl_set_get_space (pbb->domain); @@ -1196,14 +1099,13 @@ build_poly_dr (dr_info &dri) isl_dim_out, nb_out); acc = isl_map_universe (space); - acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_for_dr (scop, dr)); + acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id)); } acc = pdr_add_alias_set (acc, dri); acc = pdr_add_memory_accesses (acc, dri); { - isl_id *id = isl_id_for_dr (scop, dr); int nb = 1 + DR_NUM_DIMENSIONS (dr); isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb); @@ -1214,614 +1116,72 @@ build_poly_dr (dr_info &dri) subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr); } - new_poly_dr (pbb, - DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, - dr, DR_NUM_DIMENSIONS (dr), acc, subscript_sizes); -} - -/* Compute alias-sets for all data references in DRS. */ - -static void -build_alias_set (scop_p scop) -{ - int num_vertices = scop->drs.length (); - struct graph *g = new_graph (num_vertices); - dr_info *dr1, *dr2; - int i, j; - int *all_vertices; - - FOR_EACH_VEC_ELT (scop->drs, i, dr1) - for (j = i+1; scop->drs.iterate (j, &dr2); j++) - if (dr_may_alias_p (dr1->dr, dr2->dr, true)) - { - add_edge (g, i, j); - add_edge (g, j, i); - } - - all_vertices = XNEWVEC (int, num_vertices); - for (i = 0; i < num_vertices; i++) - all_vertices[i] = i; - - graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL); - free (all_vertices); - - for (i = 0; i < g->n_vertices; i++) - scop->drs[i].alias_set = g->vertices[i].component + 1; - - free_graph (g); -} - -/* Build data references in SCOP. */ - -static void -build_scop_drs (scop_p scop) -{ - int i, j; - poly_bb_p pbb; - - /* Remove all the PBBs that do not have data references: these basic - blocks are not handled in the polyhedral representation. */ - for (i = 0; scop->pbbs.iterate (i, &pbb); i++) - if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb)).is_empty ()) - { - free_gimple_poly_bb (PBB_BLACK_BOX (pbb)); - free_poly_bb (pbb); - scop->pbbs.ordered_remove (i); - i--; - } - - data_reference_p dr; - FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) - if (pbb) - FOR_EACH_VEC_ELT (GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr) - scop->drs.safe_push (dr_info (dr, pbb)); - - build_alias_set (scop); - - dr_info *dri; - FOR_EACH_VEC_ELT (scop->drs, i, dri) - build_poly_dr (*dri); + new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, + acc, subscript_sizes); } -/* Analyze all the data references of STMTS and add them to the - GBB_DATA_REFS vector of BB. */ - static void -analyze_drs_in_stmts (scop_p scop, basic_block bb, vec<gimple *> stmts) +build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind, + isl_map *acc, isl_set *subscript_sizes) { - sese_l region = scop->scop_info->region; - if (!bb_in_sese_p (bb, region)) - return; - - loop_p nest = outermost_loop_in_sese (region, bb); - loop_p loop = bb->loop_father; - if (!loop_in_sese_p (loop, region)) - loop = nest; - - gimple_poly_bb_p gbb = gbb_from_bb (bb); - - gimple *stmt; - int i; - FOR_EACH_VEC_ELT (stmts, i, stmt) - { - if (is_gimple_debug (stmt)) - continue; - - graphite_find_data_references_in_stmt (nest, loop, stmt, - &GBB_DATA_REFS (gbb)); - } -} - -/* Insert STMT at the end of the STMTS sequence and then insert the - statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts - on STMTS. */ - -static void -insert_stmts (scop_p scop, gimple *stmt, gimple_seq stmts, - gimple_stmt_iterator insert_gsi) -{ - gimple_stmt_iterator gsi; - auto_vec<gimple *, 3> x; - - gimple_seq_add_stmt (&stmts, stmt); - for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi)) - x.safe_push (gsi_stmt (gsi)); - - gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT); - analyze_drs_in_stmts (scop, gsi_bb (insert_gsi), x); + int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP); + /* Each scalar variables has a unique alias set number starting from + max_arrays. */ + subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0, + max_arrays + SSA_NAME_VERSION (var)); + + new_poly_dr (pbb, stmt, kind, add_scalar_version_numbers (acc, var), + subscript_sizes); } -/* Insert the assignment "RES := EXPR" just after AFTER_STMT. */ +/* Record all cross basic block scalar variables in PBB. */ static void -insert_out_of_ssa_copy (scop_p scop, tree res, tree expr, gimple *after_stmt) +build_poly_sr (poly_bb_p pbb) { - gimple_stmt_iterator gsi; - auto_vec<gimple *, 3> x; - gimple_seq stmts; - tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE); - gassign *stmt = gimple_build_assign (unshare_expr (res), var); - - gimple_seq_add_stmt (&stmts, stmt); - - for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi)) - x.safe_push (gsi_stmt (gsi)); - - if (gimple_code (after_stmt) == GIMPLE_PHI) - { - gsi = gsi_after_labels (gimple_bb (after_stmt)); - gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); - } - else - { - gsi = gsi_for_stmt (after_stmt); - gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT); - } - - analyze_drs_in_stmts (scop, gimple_bb (after_stmt), x); -} - -/* Creates a poly_bb_p for basic_block BB from the existing PBB. */ - -static void -new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb) -{ - vec<data_reference_p> drs; - drs.create (3); + scop_p scop = PBB_SCOP (pbb); gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); - gimple_poly_bb_p gbb1 = new_gimple_poly_bb (bb, drs); - poly_bb_p pbb1 = new_poly_bb (scop, gbb1); - int index, n = scop->pbbs.length (); - - for (index = 0; index < n; index++) - if (scop->pbbs[index] == pbb) - break; - - pbb1->domain = isl_set_copy (pbb->domain); - pbb1->domain = isl_set_set_tuple_id (pbb1->domain, - isl_id_for_pbb (scop, pbb1)); - - GBB_PBB (gbb1) = pbb1; - GBB_CONDITIONS (gbb1) = GBB_CONDITIONS (gbb).copy (); - GBB_CONDITION_CASES (gbb1) = GBB_CONDITION_CASES (gbb).copy (); - scop->pbbs.safe_insert (index + 1, pbb1); -} - -/* Insert on edge E the assignment "RES := EXPR". */ - -static void -insert_out_of_ssa_copy_on_edge (scop_p scop, edge e, tree res, tree expr) -{ - gimple_seq stmts = NULL; - tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE); - gimple *stmt = gimple_build_assign (unshare_expr (res), var); - auto_vec<gimple *, 3> x; - - gimple_seq_add_stmt (&stmts, stmt); - gimple_stmt_iterator gsi; - for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi)) - x.safe_push (gsi_stmt (gsi)); - - gsi_insert_seq_on_edge (e, stmts); - gsi_commit_edge_inserts (); - basic_block bb = gimple_bb (stmt); - - if (!bb_in_sese_p (bb, scop->scop_info->region)) - return; - - if (!gbb_from_bb (bb)) - new_pbb_from_pbb (scop, pbb_from_bb (e->src), bb); - - analyze_drs_in_stmts (scop, bb, x); -} - -/* Creates a zero dimension array of the same type as VAR. */ - -static tree -create_zero_dim_array (tree var, const char *base_name) -{ - tree index_type = build_index_type (integer_zero_node); - tree elt_type = TREE_TYPE (var); - tree array_type = build_array_type (elt_type, index_type); - tree base = create_tmp_var (array_type, base_name); - - return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE, - NULL_TREE); -} - -/* Returns true when PHI is a loop close phi node. */ - -static bool -scalar_close_phi_node_p (gimple *phi) -{ - if (gimple_code (phi) != GIMPLE_PHI - || virtual_operand_p (gimple_phi_result (phi))) - return false; - - /* Note that loop close phi nodes should have a single argument - because we translated the representation into a canonical form - before Graphite: see canonicalize_loop_closed_ssa_form. */ - return (gimple_phi_num_args (phi) == 1); -} - -/* For a definition DEF in REGION, propagates the expression EXPR in - all the uses of DEF outside REGION. */ + vec<scalar_use> reads = gbb->read_scalar_refs; + vec<tree> writes = gbb->write_scalar_refs; -static void -propagate_expr_outside_region (tree def, tree expr, sese_l ®ion) -{ - gimple_seq stmts; - bool replaced_once = false; - - gcc_assert (TREE_CODE (def) == SSA_NAME); - - expr = force_gimple_operand (unshare_expr (expr), &stmts, true, - NULL_TREE); - - imm_use_iterator imm_iter; - gimple *use_stmt; - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) - if (!is_gimple_debug (use_stmt) - && !bb_in_sese_p (gimple_bb (use_stmt), region)) - { - ssa_op_iter iter; - use_operand_p use_p; - - FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES) - if (operand_equal_p (def, USE_FROM_PTR (use_p), 0) - && (replaced_once = true)) - replace_exp (use_p, expr); - - update_stmt (use_stmt); - } - - if (replaced_once) - { - gsi_insert_seq_on_edge (region.entry, stmts); - gsi_commit_edge_inserts (); - } -} - -/* Rewrite out of SSA the reduction phi node at PSI by creating a zero - dimension array for it. */ - -static void -rewrite_close_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi) -{ - sese_l region = scop->scop_info->region; - gimple *phi = gsi_stmt (*psi); - tree res = gimple_phi_result (phi); - basic_block bb = gimple_bb (phi); - gimple_stmt_iterator gsi = gsi_after_labels (bb); - tree arg = gimple_phi_arg_def (phi, 0); - gimple *stmt; - - /* Note that loop close phi nodes should have a single argument - because we translated the representation into a canonical form - before Graphite: see canonicalize_loop_closed_ssa_form. */ - gcc_assert (gimple_phi_num_args (phi) == 1); - - /* The phi node can be a non close phi node, when its argument is - invariant, or a default definition. */ - if (is_gimple_min_invariant (arg) - || SSA_NAME_IS_DEFAULT_DEF (arg)) - { - propagate_expr_outside_region (res, arg, region); - gsi_next (psi); - return; - } - - else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father) - { - propagate_expr_outside_region (res, arg, region); - stmt = gimple_build_assign (res, arg); - remove_phi_node (psi, false); - gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); - return; - } - - /* If res is scev analyzable and is not a scalar value, it is safe - to ignore the close phi node: it will be code generated in the - out of Graphite pass. */ - else if (scev_analyzable_p (res, region)) - { - loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res)); - tree scev; - - if (!loop_in_sese_p (loop, region)) - { - loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg)); - scev = scalar_evolution_in_region (region, loop, arg); - scev = compute_overall_effect_of_inner_loop (loop, scev); - } - else - scev = scalar_evolution_in_region (region, loop, res); - - if (tree_does_not_contain_chrecs (scev)) - propagate_expr_outside_region (res, scev, region); - - gsi_next (psi); - return; - } - else - { - tree zero_dim_array = create_zero_dim_array (res, "Close_Phi"); - - stmt = gimple_build_assign (res, unshare_expr (zero_dim_array)); - - if (TREE_CODE (arg) == SSA_NAME) - insert_out_of_ssa_copy (scop, zero_dim_array, arg, - SSA_NAME_DEF_STMT (arg)); - else - insert_out_of_ssa_copy_on_edge (scop, single_pred_edge (bb), - zero_dim_array, arg); - } - - remove_phi_node (psi, false); - SSA_NAME_DEF_STMT (res) = stmt; - - insert_stmts (scop, stmt, NULL, gsi_after_labels (bb)); -} - -/* Rewrite out of SSA the reduction phi node at PSI by creating a zero - dimension array for it. */ - -static void -rewrite_phi_out_of_ssa (scop_p scop, gphi_iterator *psi) -{ - gphi *phi = psi->phi (); - basic_block bb = gimple_bb (phi); - tree res = gimple_phi_result (phi); - tree zero_dim_array = create_zero_dim_array (res, "phi_out_of_ssa"); - - for (size_t i = 0; i < gimple_phi_num_args (phi); i++) - { - tree arg = gimple_phi_arg_def (phi, i); - edge e = gimple_phi_arg_edge (phi, i); - - /* Avoid the insertion of code in the loop latch to please the - pattern matching of the vectorizer. */ - if (TREE_CODE (arg) == SSA_NAME - && !SSA_NAME_IS_DEFAULT_DEF (arg) - && e->src == bb->loop_father->latch) - insert_out_of_ssa_copy (scop, zero_dim_array, arg, - SSA_NAME_DEF_STMT (arg)); - else - insert_out_of_ssa_copy_on_edge (scop, e, zero_dim_array, arg); - } - - gimple *stmt = gimple_build_assign (res, unshare_expr (zero_dim_array)); - remove_phi_node (psi, false); - insert_stmts (scop, stmt, NULL, gsi_after_labels (bb)); -} - -/* Rewrite the degenerate phi node at position PSI from the degenerate - form "x = phi (y, y, ..., y)" to "x = y". */ - -static void -rewrite_degenerate_phi (gphi_iterator *psi) -{ - gphi *phi = psi->phi (); - tree res = gimple_phi_result (phi); - - basic_block bb = gimple_bb (phi); - tree rhs = degenerate_phi_result (phi); - gcc_assert (rhs); - - gimple *stmt = gimple_build_assign (res, rhs); - remove_phi_node (psi, false); - - gimple_stmt_iterator gsi = gsi_after_labels (bb); - gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); -} - -/* Rewrite out of SSA all the reduction phi nodes of SCOP. */ + isl_space *dc = isl_set_get_space (pbb->domain); + int nb_out = 1; + isl_space *space = isl_space_add_dims (isl_space_from_domain (dc), + isl_dim_out, nb_out); + isl_id *id = isl_id_for_dr (scop); + space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id)); + isl_map *acc = isl_map_universe (isl_space_copy (space)); + acc = isl_map_set_tuple_id (acc, isl_dim_out, id); + isl_set *subscript_sizes = isl_set_nat_universe (space); -static void -rewrite_reductions_out_of_ssa (scop_p scop) -{ int i; - basic_block bb; - FOR_EACH_VEC_ELT (scop->scop_info->bbs, i, bb) - for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);) - { - gphi *phi = psi.phi (); - - if (virtual_operand_p (gimple_phi_result (phi))) - { - gsi_next (&psi); - continue; - } - - if (gimple_phi_num_args (phi) > 1 - && degenerate_phi_result (phi)) - rewrite_degenerate_phi (&psi); - - else if (scalar_close_phi_node_p (phi)) - rewrite_close_phi_out_of_ssa (scop, &psi); - - else if (reduction_phi_p (scop->scop_info->region, &psi)) - rewrite_phi_out_of_ssa (scop, &psi); - } - - update_ssa (TODO_update_ssa); - checking_verify_loop_closed_ssa (true); -} - -/* Rewrite the scalar dependence of DEF used in USE_STMT with a memory - read from ZERO_DIM_ARRAY. */ - -static void -rewrite_cross_bb_scalar_dependence (scop_p scop, tree zero_dim_array, - tree def, gimple *use_stmt) -{ - gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI); - - tree name = copy_ssa_name (def); - gimple *name_stmt = gimple_build_assign (name, zero_dim_array); - - gimple_assign_set_lhs (name_stmt, name); - insert_stmts (scop, name_stmt, NULL, gsi_for_stmt (use_stmt)); - - ssa_op_iter iter; - use_operand_p use_p; - FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES) - if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)) - replace_exp (use_p, name); - - update_stmt (use_stmt); -} - -/* For every definition DEF in the SCOP that is used outside the scop, - insert a closing-scop definition in the basic block just after this - SCOP. */ - -static void -handle_scalar_deps_crossing_scop_limits (scop_p scop, tree def, gimple *stmt) -{ - tree var = create_tmp_reg (TREE_TYPE (def)); - tree new_name = make_ssa_name (var, stmt); - bool needs_copy = false; - sese_l region = scop->scop_info->region; - - imm_use_iterator imm_iter; - gimple *use_stmt; - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) - { - if (!bb_in_sese_p (gimple_bb (use_stmt), region)) - { - use_operand_p use_p; - FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) - { - SET_USE (use_p, new_name); - } - update_stmt (use_stmt); - needs_copy = true; - } - } - - /* Insert in the empty BB just after the scop a use of DEF such - that the rewrite of cross_bb_scalar_dependences won't insert - arrays everywhere else. */ - if (needs_copy) - { - gimple *assign = gimple_build_assign (new_name, def); - gimple_stmt_iterator psi = gsi_after_labels (region.exit->dest); - - update_stmt (assign); - gsi_insert_before (&psi, assign, GSI_SAME_STMT); - } -} - -/* Rewrite the scalar dependences crossing the boundary of the BB - containing STMT with an array. Return true when something has been - changed. */ - -static bool -rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi) -{ - sese_l region = scop->scop_info->region; - gimple *stmt = gsi_stmt (*gsi); - imm_use_iterator imm_iter; - tree def; - tree zero_dim_array = NULL_TREE; - gimple *use_stmt; - bool res = false; - - switch (gimple_code (stmt)) - { - case GIMPLE_ASSIGN: - def = gimple_assign_lhs (stmt); - break; - - case GIMPLE_CALL: - def = gimple_call_lhs (stmt); - break; - - default: - return false; - } - - if (!def - || !is_gimple_reg (def)) - return false; - - if (scev_analyzable_p (def, region)) - { - loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def)); - tree scev = scalar_evolution_in_region (region, loop, def); - - if (tree_contains_chrecs (scev, NULL)) - return false; - - propagate_expr_outside_region (def, scev, region); - return true; - } - - basic_block def_bb = gimple_bb (stmt); - - handle_scalar_deps_crossing_scop_limits (scop, def, stmt); - - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) - if (gphi *phi = dyn_cast <gphi *> (use_stmt)) - { - res = true; - gphi_iterator psi = gsi_for_phi (phi); - - if (scalar_close_phi_node_p (gsi_stmt (psi))) - rewrite_close_phi_out_of_ssa (scop, &psi); - else - rewrite_phi_out_of_ssa (scop, &psi); - } - - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) - if (gimple_code (use_stmt) != GIMPLE_PHI - && def_bb != gimple_bb (use_stmt) - && !is_gimple_debug (use_stmt) - && (res = true)) - { - if (!zero_dim_array) - { - zero_dim_array = create_zero_dim_array - (def, "Cross_BB_scalar_dependence"); - insert_out_of_ssa_copy (scop, zero_dim_array, def, - SSA_NAME_DEF_STMT (def)); - gsi_next (gsi); - } - - rewrite_cross_bb_scalar_dependence (scop, unshare_expr (zero_dim_array), - def, use_stmt); - } + tree var; + FOR_EACH_VEC_ELT (writes, i, var) + build_poly_sr_1 (pbb, SSA_NAME_DEF_STMT (var), var, PDR_WRITE, + isl_map_copy (acc), isl_set_copy (subscript_sizes)); - update_ssa (TODO_update_ssa); + scalar_use *use; + FOR_EACH_VEC_ELT (reads, i, use) + build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc), + isl_set_copy (subscript_sizes)); - return res; + isl_map_free (acc); + isl_set_free (subscript_sizes); } -/* Rewrite out of SSA all the reduction phi nodes of SCOP. */ +/* Build data references in SCOP. */ static void -rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop) +build_scop_drs (scop_p scop) { - gimple_stmt_iterator psi; - sese_l region = scop->scop_info->region; - bool changed = false; - - /* Create an extra empty BB after the scop. */ - split_edge (region.exit); - int i; - basic_block bb; - FOR_EACH_VEC_ELT (scop->scop_info->bbs, i, bb) - for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) - changed |= rewrite_cross_bb_scalar_deps (scop, &psi); + dr_info *dri; + FOR_EACH_VEC_ELT (scop->drs, i, dri) + build_poly_dr (*dri); - if (changed) - { - scev_reset_htab (); - update_ssa (TODO_update_ssa); - checking_verify_loop_closed_ssa (true); - } + poly_bb_p pbb; + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) + build_poly_sr (pbb); } /* Builds the polyhedral representation for a SESE region. */ @@ -1834,13 +1194,6 @@ build_poly_scop (scop_p scop) build_scop_context (scop); add_conditions_to_constraints (scop); - /* Rewrite out of SSA only after having translated the - representation to the polyhedral representation to avoid scev - analysis failures. That means that these functions will insert - new data references that they create in the right place. */ - rewrite_reductions_out_of_ssa (scop); - rewrite_cross_bb_scalar_deps_out_of_ssa (scop); - build_scop_drs (scop); build_scop_minimal_scattering (scop); build_scop_original_schedule (scop); diff --git a/gcc/graphite.c b/gcc/graphite.c index 773203e..5316bc4 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -333,12 +333,16 @@ graphite_transform_loops (void) if (dump_file && dump_flags) print_scop (dump_file, scop); - if (scop->poly_scop_p - && apply_poly_transforms (scop) - && graphite_regenerate_ast_isl (scop)) - need_cfg_cleanup_p = true; - + && apply_poly_transforms (scop)) + { + need_cfg_cleanup_p = true; + /* When code generation is not successful, do not continue + generating code for the next scops: the IR has to be cleaned up + and could be in an inconsistent state. */ + if (!graphite_regenerate_ast_isl (scop)) + break; + } } free_scops (scops); @@ -25,6 +25,7 @@ along with GCC; see the file COPYING3. If not see #include "backend.h" #include "tree.h" #include "gimple.h" +#include "cfganal.h" #include "cfghooks.h" #include "tree-pass.h" #include "ssa.h" @@ -34,6 +35,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-eh.h" #include "gimplify.h" #include "gimple-iterator.h" +#include "gimple-pretty-print.h" #include "gimplify-me.h" #include "tree-cfg.h" #include "tree-ssa-loop.h" @@ -44,33 +46,6 @@ along with GCC; see the file COPYING3. If not see #include "value-prof.h" #include "sese.h" #include "tree-ssa-propagate.h" -#include "tree-hash-traits.h" - -/* Helper function for debug_rename_map. */ - -bool -debug_rename_map_1 (tree_node *const &old_name, tree_node *const &expr, - void *) -{ - fprintf (stderr, "("); - print_generic_expr (stderr, old_name, 0); - fprintf (stderr, ", "); - print_generic_expr (stderr, expr, 0); - fprintf (stderr, ")\n"); - return true; -} - -typedef hash_map<tree_ssa_name_hash, tree> rename_map_type; - - -/* Print to stderr all the elements of RENAME_MAP. */ - -DEBUG_FUNCTION void -debug_rename_map (rename_map_type *rename_map) -{ - rename_map->traverse <void *, debug_rename_map_1> (NULL); -} - /* Record LOOP as occurring in REGION. */ @@ -80,8 +55,8 @@ sese_record_loop (sese_info_p region, loop_p loop) if (sese_contains_loop (region, loop)) return; - bitmap_set_bit (SESE_LOOPS (region), loop->num); - SESE_LOOP_NEST (region).safe_push (loop); + bitmap_set_bit (region->loops, loop->num); + region->loop_nest.safe_push (loop); } /* Build the loop nests contained in REGION. Returns true when the @@ -108,16 +83,16 @@ build_sese_loop_nests (sese_info_p region) /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It can be the case that an inner loop is inserted before an outer loop. To avoid this, semi-sort once. */ - FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop0) + FOR_EACH_VEC_ELT (region->loop_nest, i, loop0) { - if (SESE_LOOP_NEST (region).length () == i + 1) + if (region->loop_nest.length () == i + 1) break; - loop1 = SESE_LOOP_NEST (region)[i + 1]; + loop1 = region->loop_nest[i + 1]; if (loop0->num > loop1->num) { - SESE_LOOP_NEST (region)[i] = loop1; - SESE_LOOP_NEST (region)[i + 1] = loop0; + region->loop_nest[i] = loop1; + region->loop_nest[i + 1] = loop0; } } } @@ -256,10 +231,13 @@ new_sese_info (edge entry, edge exit) region->region.entry = entry; region->region.exit = exit; - SESE_LOOPS (region) = BITMAP_ALLOC (NULL); - SESE_LOOP_NEST (region).create (3); - SESE_PARAMS (region).create (3); + region->loops = BITMAP_ALLOC (NULL); + region->loop_nest.create (3); + region->params.create (3); + region->rename_map = new rename_map_t; + region->copied_bb_map = new bb_map_t; region->bbs.create (3); + region->incomplete_phis.create (3); return region; } @@ -269,11 +247,28 @@ new_sese_info (edge entry, edge exit) void free_sese_info (sese_info_p region) { - if (SESE_LOOPS (region)) - SESE_LOOPS (region) = BITMAP_ALLOC (NULL); + if (region->loops) + region->loops = BITMAP_ALLOC (NULL); - SESE_PARAMS (region).release (); - SESE_LOOP_NEST (region).release (); + region->params.release (); + region->loop_nest.release (); + + for (rename_map_t::iterator it = region->rename_map->begin (); + it != region->rename_map->begin (); ++it) + (*it).second.release (); + + for (bb_map_t::iterator it = region->copied_bb_map->begin (); + it != region->copied_bb_map->begin (); ++it) + (*it).second.release (); + + delete region->rename_map; + delete region->copied_bb_map; + + region->rename_map = NULL; + region->copied_bb_map = NULL; + + region->bbs.release (); + region->incomplete_phis.release (); XDELETE (region); } @@ -312,8 +307,11 @@ sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb, update_ssa (TODO_update_ssa); sese_build_liveouts (region, liveouts); + EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi) - sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); + if (!virtual_operand_p (ssa_name (i))) + sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); + BITMAP_FREE (liveouts); update_ssa (TODO_update_ssa); @@ -351,37 +349,550 @@ get_false_edge_from_guard_bb (basic_block bb) return NULL; } -/* Returns the expression associated to OLD_NAME in RENAME_MAP. */ +/* Check if USE is defined in a basic block from where the definition of USE can + propagate from all the paths. */ + +static bool +is_loop_closed_ssa_use (basic_block bb, tree use) +{ + if (TREE_CODE (use) != SSA_NAME) + return true; + + /* We should not have a rename for virtual operands. */ + gcc_assert (!virtual_operand_p (use)); + + /* For close-phi nodes def always comes from a loop which has a back-edge. */ + if (bb_contains_loop_close_phi_nodes (bb)) + return true; + + gimple *def = SSA_NAME_DEF_STMT (use); + basic_block def_bb = gimple_bb (def); + return (!def_bb + || flow_bb_inside_loop_p (def_bb->loop_father, bb)); +} + +/* Return the number of phi nodes in BB. */ + +static int +number_of_phi_nodes (basic_block bb) +{ + int num_phis = 0; + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + num_phis++; + return num_phis; +} + +/* Return true when BB contains loop close phi nodes. */ + +bool +bb_contains_loop_close_phi_nodes (basic_block bb) +{ + return single_pred_p (bb) + && bb->loop_father != single_pred_edge (bb)->src->loop_father; +} + +/* Return true when BB contains loop phi nodes. */ + +bool +bb_contains_loop_phi_nodes (basic_block bb) +{ + gcc_assert (EDGE_COUNT (bb->preds) <= 2); + + if (bb->preds->length () == 1) + return false; + + unsigned depth = loop_depth (bb->loop_father); + + edge preds[2] = { (*bb->preds)[0], (*bb->preds)[1] }; + + if (depth > loop_depth (preds[0]->src->loop_father) + || depth > loop_depth (preds[1]->src->loop_father)) + return true; + + /* When one of the edges correspond to the same loop father and other + doesn't. */ + if (bb->loop_father != preds[0]->src->loop_father + && bb->loop_father == preds[1]->src->loop_father) + return true; + + if (bb->loop_father != preds[1]->src->loop_father + && bb->loop_father == preds[0]->src->loop_father) + return true; + + return false; +} + +/* Returns true if BB uses name in one of its PHIs. */ + +static bool +phi_uses_name (basic_block bb, tree name) +{ + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + for (unsigned i = 0; i < gimple_phi_num_args (phi); i++) + { + tree use_arg = gimple_phi_arg_def (phi, i); + if (use_arg == name) + return true; + } + } + return false; +} + +/* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The +definition should flow into use, and the use should respect the loop-closed SSA +form. */ + +static bool +is_valid_rename (tree rename, basic_block def_bb, + basic_block use_bb, bool loop_phi, + tree old_name, basic_block old_bb) +{ + /* The def of the rename must either dominate the uses or come from a + back-edge. Also the def must respect the loop closed ssa form. */ + if (!is_loop_closed_ssa_use (use_bb, rename)) + { + if (dump_file) + { + fprintf (dump_file, "\n[codegen] rename not in loop closed ssa:"); + print_generic_expr (dump_file, rename, 0); + } + return false; + } + + if (dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)) + return true; + + if (bb_contains_loop_phi_nodes (use_bb) && loop_phi) + { + /* The loop-header dominates the loop-body. */ + if (!dominated_by_p (CDI_DOMINATORS, def_bb, use_bb)) + return false; + + /* RENAME would be used in loop-phi. */ + gcc_assert (number_of_phi_nodes (use_bb)); + + /* For definitions coming from back edges, we should check that + old_name is used in a loop PHI node. */ + if (phi_uses_name (old_bb, old_name)) + return true; + } + return false; +} + +/* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in + NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME + within a loop PHI instruction. */ static tree -get_rename (rename_map_type *rename_map, tree old_name) +get_rename (rename_map_t *rename_map, basic_block new_bb, tree old_name, + basic_block old_bb, bool loop_phi) { gcc_assert (TREE_CODE (old_name) == SSA_NAME); - tree *expr = rename_map->get (old_name); - if (expr) - return *expr; + vec <tree> *renames = rename_map->get (old_name); - return NULL_TREE; + if (!renames || renames->is_empty ()) + return NULL_TREE; + + if (1 == renames->length ()) + { + tree rename = (*renames)[0]; + basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (rename)); + if (is_valid_rename (rename, bb, new_bb, loop_phi, old_name, old_bb)) + return rename; + return NULL_TREE; + } + + /* More than one renames corresponding to the old_name. Find the rename for + which the definition flows into usage at new_bb. */ + int i; + tree t1 = NULL_TREE, t2; + basic_block t1_bb = NULL; + FOR_EACH_VEC_ELT (*renames, i, t2) + { + basic_block t2_bb = gimple_bb (SSA_NAME_DEF_STMT (t2)); + + /* Defined in the same basic block as used. */ + if (t2_bb == new_bb) + return t2; + + /* NEW_BB and T2_BB are in two unrelated if-clauses. */ + if (!dominated_by_p (CDI_DOMINATORS, new_bb, t2_bb)) + continue; + + /* Compute the nearest dominator. */ + if (!t1 || dominated_by_p (CDI_DOMINATORS, t2_bb, t1_bb)) + { + t1_bb = t2_bb; + t1 = t2; + } + //if (is_valid_rename (rename, bb, new_bb, loop_phi, old_name, old_bb)) + //return rename; + } + + return t1; } -/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */ +/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). + When OLD_NAME and EXPR are the same we assert. */ static void -set_rename (rename_map_type *rename_map, tree old_name, tree expr) +set_rename (tree old_name, tree expr, sese_info_p region) { if (dump_file) { - fprintf (dump_file, "[codegen] setting rename: old_name = "); + fprintf (dump_file, "\n[codegen] setting rename: old_name = "); print_generic_expr (dump_file, old_name, 0); fprintf (dump_file, ", new_name = "); print_generic_expr (dump_file, expr, 0); - fprintf (dump_file, "\n"); } if (old_name == expr) return; - rename_map->put (old_name, expr); + vec <tree> *renames = region->rename_map->get (old_name); + + if (renames) + renames->safe_push (expr); + else + { + vec<tree> r; + r.create (2); + r.safe_push (expr); + region->rename_map->put (old_name, r); + } +} + +/* Return an iterator to the instructions comes + last in the execution order. Either GSI1 and GSI2 should belong + to the same basic block or one of their respective basic blocks + should dominate the other. */ + +gimple_stmt_iterator +later_of_the_two (gimple_stmt_iterator gsi1, gimple_stmt_iterator gsi2) +{ + basic_block bb1 = gsi_bb (gsi1); + basic_block bb2 = gsi_bb (gsi2); + + /* Find the iterator which is the latest. */ + if (bb1 == bb2) + { + /* For empty basic blocks gsis point to the end of the sequence. Since + there is no operator== defined for gimple_stmt_iterator and for gsis + not pointing to a valid statement gsi_next would assert. */ + gimple_stmt_iterator gsi = gsi1; + do { + if (gsi_stmt (gsi) == gsi_stmt (gsi2)) + return gsi2; + gsi_next (&gsi); + } while (!gsi_end_p (gsi)); + + return gsi1; + } + + /* Find the basic block closest to the basic block which defines stmt. */ + if (dominated_by_p (CDI_DOMINATORS, bb1, bb2)) + return gsi1; + + gcc_assert (dominated_by_p (CDI_DOMINATORS, bb2, bb1)); + return gsi2; +} + +/* Insert each statement from SEQ at its earliest insertion p. */ + +static void +gsi_insert_earliest (gimple_seq seq, sese_info_p region) +{ + update_modified_stmts (seq); + sese_l &codegen_region = region->if_region->true_region->region; + basic_block begin_bb = get_entry_bb (codegen_region); + + /* Inserting the gimple statements in a vector because gimple_seq behave + in strage ways when inserting the stmts from it into different basic + blocks one at a time. */ + auto_vec<gimple *, 3> stmts; + for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi); + gsi_next (&gsi)) + stmts.safe_push (gsi_stmt (gsi)); + + int i; + gimple *use_stmt; + FOR_EACH_VEC_ELT (stmts, i, use_stmt) + { + gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI); + gimple_stmt_iterator gsi_def_stmt = gsi_start_bb_nondebug (begin_bb); + + use_operand_p use_p; + ssa_op_iter op_iter; + FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, op_iter, SSA_OP_USE) + { + /* Iterator to the current def of use_p. For function parameters or + anything where def is not found, insert at the beginning of the + generated region. */ + gimple_stmt_iterator gsi_stmt = gsi_def_stmt; + + tree op = USE_FROM_PTR (use_p); + gimple *stmt = SSA_NAME_DEF_STMT (op); + if (stmt && (gimple_code (stmt) != GIMPLE_NOP)) + gsi_stmt = gsi_for_stmt (stmt); + + /* For region parameters, insert at the beginning of the generated + region. */ + if (!bb_in_sese_p (gsi_bb (gsi_stmt), codegen_region)) + { + /* The parameter should have been inserted in the parameter + map or it must have a scev. */ + gsi_stmt = gsi_def_stmt; + } + + gsi_def_stmt = later_of_the_two (gsi_stmt, gsi_def_stmt); + } + + if (!gsi_stmt (gsi_def_stmt)) + { + gimple_stmt_iterator gsi = gsi_after_labels (gsi_bb (gsi_def_stmt)); + gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT); + } + else if (gimple_code (gsi_stmt (gsi_def_stmt)) == GIMPLE_PHI) + { + gimple_stmt_iterator bsi + = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt)); + /* Insert right after the PHI statements. */ + gsi_insert_before (&bsi, use_stmt, GSI_NEW_STMT); + } + else + gsi_insert_after (&gsi_def_stmt, use_stmt, GSI_NEW_STMT); + + if (dump_file) + { + fprintf (dump_file, "\n[codegen] inserting statement: "); + print_gimple_stmt (dump_file, use_stmt, 0, TDF_VOPS | TDF_MEMSYMS); + print_loops_bb (dump_file, gimple_bb (use_stmt), 0, 3); + } + } +} + +/* Collect all the operands of NEW_EXPR by recursively visiting each + operand. */ + +static void +collect_all_ssa_names (tree new_expr, vec<tree> *vec_ssa, sese_info_p region) +{ + + /* Rename all uses in new_expr. */ + if (TREE_CODE (new_expr) == SSA_NAME) + { + vec_ssa->safe_push (new_expr); + return; + } + + /* Iterate over SSA_NAMES in NEW_EXPR. */ + for (int i = 0; i < (TREE_CODE_LENGTH (TREE_CODE (new_expr))); i++) + { + tree op = TREE_OPERAND (new_expr, i); + collect_all_ssa_names (op, vec_ssa, region); + } +} + +static tree +substitute_ssa_name (tree exp, tree f, tree r) +{ + enum tree_code code = TREE_CODE (exp); + tree op0, op1, op2, op3; + tree new_tree; + + /* We handle TREE_LIST and COMPONENT_REF separately. */ + if (code == TREE_LIST) + { + op0 = substitute_ssa_name (TREE_CHAIN (exp), f, r); + op1 = substitute_ssa_name (TREE_VALUE (exp), f, r); + if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp)) + return exp; + + return tree_cons (TREE_PURPOSE (exp), op1, op0); + } + else if (code == COMPONENT_REF) + { + tree inner; + + /* If this expression is getting a value from a PLACEHOLDER_EXPR + and it is the right field, replace it with R. */ + for (inner = TREE_OPERAND (exp, 0); + REFERENCE_CLASS_P (inner); + inner = TREE_OPERAND (inner, 0)) + ; + + /* The field. */ + op1 = TREE_OPERAND (exp, 1); + + if (TREE_CODE (inner) == PLACEHOLDER_EXPR && op1 == f) + return r; + + /* If this expression hasn't been completed let, leave it alone. */ + if (TREE_CODE (inner) == PLACEHOLDER_EXPR && !TREE_TYPE (inner)) + return exp; + + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + if (op0 == TREE_OPERAND (exp, 0)) + return exp; + + new_tree + = fold_build3 (COMPONENT_REF, TREE_TYPE (exp), op0, op1, NULL_TREE); + } + else + switch (TREE_CODE_CLASS (code)) + { + case tcc_constant: + return exp; + + case tcc_declaration: + if (exp == f) + return r; + else + return exp; + + case tcc_expression: + if (exp == f) + return r; + + /* Fall through... */ + + case tcc_exceptional: + case tcc_unary: + case tcc_binary: + case tcc_comparison: + case tcc_reference: + switch (TREE_CODE_LENGTH (code)) + { + case 0: + if (exp == f) + return r; + return exp; + + case 1: + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + if (op0 == TREE_OPERAND (exp, 0)) + return exp; + + new_tree = fold_build1 (code, TREE_TYPE (exp), op0); + break; + + case 2: + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r); + + if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)) + return exp; + + new_tree = fold_build2 (code, TREE_TYPE (exp), op0, op1); + break; + + case 3: + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r); + op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r); + + if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1) + && op2 == TREE_OPERAND (exp, 2)) + return exp; + + new_tree = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2); + break; + + case 4: + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r); + op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r); + op3 = substitute_ssa_name (TREE_OPERAND (exp, 3), f, r); + + if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1) + && op2 == TREE_OPERAND (exp, 2) + && op3 == TREE_OPERAND (exp, 3)) + return exp; + + new_tree + = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3)); + break; + + default: + gcc_unreachable (); + } + break; + + case tcc_vl_exp: + default: + gcc_unreachable (); + } + + TREE_READONLY (new_tree) |= TREE_READONLY (exp); + + if (code == INDIRECT_REF || code == ARRAY_REF || code == ARRAY_RANGE_REF) + TREE_THIS_NOTRAP (new_tree) |= TREE_THIS_NOTRAP (exp); + + return new_tree; +} + +/* Rename all the operands of NEW_EXPR by recursively visiting each operand. */ + +static tree +rename_all_uses (tree new_expr, basic_block new_bb, basic_block old_bb, + sese_info_p region) +{ + vec<tree> ssa_names; + ssa_names.create (2); + collect_all_ssa_names (new_expr, &ssa_names, region); + tree t; + int i; + FOR_EACH_VEC_ELT (ssa_names, i, t) + { + if (tree r = get_rename (region->rename_map, new_bb, t, old_bb, false)) + new_expr = substitute_ssa_name (new_expr, t, r); + /* else + return NULL_TREE;*/ + } + + return new_expr; +} + +static tree +get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop, + basic_block new_bb, basic_block old_bb, + vec<tree> iv_map, sese_info_p region, bool *gloog_error) +{ + tree scev = scalar_evolution_in_region (region->region, loop, old_name); + + /* At this point we should know the exact scev for each + scalar SSA_NAME used in the scop: all the other scalar + SSA_NAMEs should have been translated out of SSA using + arrays with one element. */ + tree new_expr; + if (chrec_contains_undetermined (scev)) + { + *gloog_error = true; + return build_zero_cst (TREE_TYPE (old_name)); + } + + new_expr = chrec_apply_map (scev, iv_map); + + /* The apply should produce an expression tree containing + the uses of the new induction variables. We should be + able to use new_expr instead of the old_name in the newly + generated loop nest. */ + if (chrec_contains_undetermined (new_expr) + || tree_contains_chrecs (new_expr, NULL)) + { + *gloog_error = true; + return build_zero_cst (TREE_TYPE (old_name)); + } + + new_expr = rename_all_uses (new_expr, new_bb, old_bb, region); + + /* Replace the old_name with the new_expr. */ + return force_gimple_operand (unshare_expr (new_expr), stmts, + true, NULL_TREE); } /* Renames the scalar uses of the statement COPY, using the @@ -392,13 +903,10 @@ set_rename (rename_map_type *rename_map, tree old_name, tree expr) is set when the code generation cannot continue. */ static bool -rename_uses (gimple *copy, rename_map_type *rename_map, - gimple_stmt_iterator *gsi_tgt, - sese_info_p region, loop_p loop, vec<tree> iv_map, - bool *gloog_error) +rename_uses (gimple *copy, gimple_stmt_iterator *gsi_tgt, + basic_block old_bb, sese_info_p region, + loop_p loop, vec<tree> iv_map, bool *gloog_error) { - use_operand_p use_p; - ssa_op_iter op_iter; bool changed = false; if (is_gimple_debug (copy)) @@ -413,23 +921,43 @@ rename_uses (gimple *copy, rename_map_type *rename_map, return false; } + if (dump_file) + { + fprintf (dump_file, "\n[codegen] renaming uses of stmt: "); + print_gimple_stmt (dump_file, copy, 0, 0); + } + + use_operand_p use_p; + ssa_op_iter op_iter; FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_USE) { tree old_name = USE_FROM_PTR (use_p); - tree new_expr, scev; - gimple_seq stmts; + + if (dump_file) + { + fprintf (dump_file, "\n[codegen] renaming old_name = "); + print_generic_expr (dump_file, old_name, 0); + } if (TREE_CODE (old_name) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (old_name)) continue; changed = true; - new_expr = get_rename (rename_map, old_name); + tree new_expr = get_rename (region->rename_map, gsi_tgt->bb, old_name, + old_bb, false); + if (new_expr) { tree type_old_name = TREE_TYPE (old_name); tree type_new_expr = TREE_TYPE (new_expr); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] from rename_map: new_name = "); + print_generic_expr (dump_file, new_expr, 0); + } + if (type_old_name != type_new_expr || TREE_CODE (new_expr) != SSA_NAME) { @@ -438,44 +966,28 @@ rename_uses (gimple *copy, rename_map_type *rename_map, if (!useless_type_conversion_p (type_old_name, type_new_expr)) new_expr = fold_convert (type_old_name, new_expr); + gimple_seq stmts; new_expr = force_gimple_operand (new_expr, &stmts, true, var); - gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); + gsi_insert_earliest (stmts, region); } replace_exp (use_p, new_expr); continue; } - scev = scalar_evolution_in_region (region->region, loop, old_name); - - /* At this point we should know the exact scev for each - scalar SSA_NAME used in the scop: all the other scalar - SSA_NAMEs should have been translated out of SSA using - arrays with one element. */ - if (chrec_contains_undetermined (scev)) - { - *gloog_error = true; - new_expr = build_zero_cst (TREE_TYPE (old_name)); - } - else - new_expr = chrec_apply_map (scev, iv_map); + gimple_seq stmts; + new_expr = get_rename_from_scev (old_name, &stmts, loop, gimple_bb (copy), + old_bb, iv_map, region, gloog_error); + if (!new_expr || *gloog_error) + return false; - /* The apply should produce an expression tree containing - the uses of the new induction variables. We should be - able to use new_expr instead of the old_name in the newly - generated loop nest. */ - if (chrec_contains_undetermined (new_expr) - || tree_contains_chrecs (new_expr, NULL)) + if (dump_file) { - *gloog_error = true; - new_expr = build_zero_cst (TREE_TYPE (old_name)); + fprintf (dump_file, "\n[codegen] not in rename map, scev: "); + print_generic_expr (dump_file, new_expr, 0); } - else - /* Replace the old_name with the new_expr. */ - new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts, - true, NULL_TREE); - gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); + gsi_insert_earliest (stmts, region); replace_exp (use_p, new_expr); if (TREE_CODE (new_expr) == INTEGER_CST @@ -487,73 +999,726 @@ rename_uses (gimple *copy, rename_map_type *rename_map, recompute_tree_invariant_for_addr_expr (rhs); } - set_rename (rename_map, old_name, new_expr); + set_rename (old_name, new_expr, region); } return changed; } +/* Returns a basic block that could correspond to where a constant was defined + in the original code. In the original code OLD_BB had the definition, we + need to find which basic block out of the copies of old_bb, in the new + region, should a definition correspond to if it has to reach BB. */ + +static basic_block +get_def_bb_for_const (sese_info_p region, basic_block bb, basic_block old_bb) +{ + vec <basic_block> *bbs = region->copied_bb_map->get (old_bb); + + if (!bbs || bbs->is_empty ()) + return NULL; + + if (1 == bbs->length ()) + return (*bbs)[0]; + + int i; + basic_block b1 = NULL, b2; + FOR_EACH_VEC_ELT (*bbs, i, b2) + { + if (b2 == bb) + return bb; + + /* BB and B2 are in two unrelated if-clauses. */ + if (!dominated_by_p (CDI_DOMINATORS, bb, b2)) + continue; + + /* Compute the nearest dominator. */ + if (!b1 || dominated_by_p (CDI_DOMINATORS, b2, b1)) + b1 = b2; + } + + gcc_assert (b1); + return b1; +} + +/* LOOP_PHI is true when we want to rename an OP within a loop PHI + instruction. */ + +static tree +get_new_name (sese_info_p region, basic_block new_bb, tree op, + basic_block old_bb, bool loop_phi) +{ + if (TREE_CODE (op) == INTEGER_CST + || TREE_CODE (op) == REAL_CST + || TREE_CODE (op) == COMPLEX_CST + || TREE_CODE (op) == VECTOR_CST) + return op; + + return get_rename (region->rename_map, new_bb, op, old_bb, loop_phi); +} + +/* Return a debug location for OP. */ + +static location_t +get_loc (tree op) +{ + location_t loc = UNKNOWN_LOCATION; + + if (TREE_CODE (op) == SSA_NAME) + loc = gimple_location (SSA_NAME_DEF_STMT (op)); + return loc; +} + +/* Returns the incoming edges of basic_block BB in the pair. The first edge is + the init edge (from outside the loop) and the second one is the back edge + from the same loop. */ + +std::pair<edge, edge> +get_edges (basic_block bb) +{ + std::pair<edge, edge> edges; + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->preds) + if (bb->loop_father != e->src->loop_father) + edges.first = e; + else + edges.second = e; + return edges; +} + +/* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI + must be found unless they can be POSTPONEd for later. */ + +void +copy_loop_phi_args (gphi *old_phi, init_back_edge_pair_t &ibp_old_bb, + gphi *new_phi, init_back_edge_pair_t &ibp_new_bb, + sese_info_p region, bool postpone) +{ + gcc_assert (gimple_phi_num_args (old_phi) == gimple_phi_num_args (new_phi)); + + basic_block new_bb = gimple_bb (new_phi); + for (unsigned i = 0; i < gimple_phi_num_args (old_phi); i++) + { + edge e; + if (gimple_phi_arg_edge (old_phi, i) == ibp_old_bb.first) + e = ibp_new_bb.first; + else + e = ibp_new_bb.second; + + tree old_name = gimple_phi_arg_def (old_phi, i); + tree new_name = get_new_name (region, new_bb, old_name, + gimple_bb (old_phi), true); + if (new_name) + { + add_phi_arg (new_phi, new_name, e, get_loc (old_name)); + continue; + } + + gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name); + if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP) + /* If the phi arg was a function arg, or wasn't defined, just use the old + name. */ + add_phi_arg (new_phi, old_name, e, get_loc (old_name)); + else if (postpone) + { + /* Postpone code gen for later for those back-edges we don't have the + names yet. */ + region->incomplete_phis.safe_push (std::make_pair (old_phi, new_phi)); + if (dump_file) + fprintf (dump_file, "\n[codegen] postpone loop phi nodes: "); + } + else + /* Either we should add the arg to phi or, we should postpone. */ + gcc_unreachable (); + } +} + +/* Copy loop phi nodes from BB to NEW_BB. */ + +static bool +copy_loop_phi_nodes (basic_block bb, basic_block new_bb, sese_info_p region) +{ + if (dump_file) + fprintf (dump_file, "\n[codegen] copying loop phi nodes in bb_%d.", + new_bb->index); + + /* Loop phi nodes should have only two arguments. */ + gcc_assert (2 == EDGE_COUNT (bb->preds)); + + /* First edge is the init edge and second is the back edge. */ + init_back_edge_pair_t ibp_old_bb = get_edges (bb); + + /* First edge is the init edge and second is the back edge. */ + init_back_edge_pair_t ibp_new_bb = get_edges (new_bb); + + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + tree res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; + if (is_gimple_reg (res) && scev_analyzable_p (res, region->region)) + continue; + + gphi *new_phi = create_phi_node (SSA_NAME_VAR (res), new_bb); + tree new_res = create_new_def_for (res, new_phi, + gimple_phi_result_ptr (new_phi)); + set_rename (res, new_res, region); + copy_loop_phi_args (phi, ibp_old_bb, new_phi, ibp_new_bb, region, true); + update_stmt (new_phi); + } + + return true; +} + +/* Return the init value of PHI, the value coming from outside the loop. */ + +static tree +get_loop_init_value (gphi *phi) +{ + + loop_p loop = gimple_bb (phi)->loop_father; + + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds) + if (e->src->loop_father != loop) + return gimple_phi_arg_def (phi, e->dest_idx); + + return NULL_TREE; +} + +/* Find the init value (the value which comes from outside the loop), of one of + the operands of DEF which is defined by a loop phi. */ + +static tree +find_init_value (gimple *def) +{ + if (gimple_code (def) == GIMPLE_PHI) + return get_loop_init_value (as_a <gphi*> (def)); + + if (gimple_vuse (def)) + return NULL_TREE; + + ssa_op_iter iter; + use_operand_p use_p; + FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE) + { + tree use = USE_FROM_PTR (use_p); + if (TREE_CODE (use) == SSA_NAME) + { + if (tree res = find_init_value (SSA_NAME_DEF_STMT (use))) + return res; + } + } + + return NULL_TREE; +} + +/* Return the init value, the value coming from outside the loop. */ + +static tree +find_init_value_close_phi (gphi *phi) +{ + gcc_assert (gimple_phi_num_args (phi) == 1); + tree use_arg = gimple_phi_arg_def (phi, 0); + gimple *def = SSA_NAME_DEF_STMT (use_arg); + return find_init_value (def); +} + +/* Copy all the loop-close phi args from BB to NEW_BB. */ + +bool +copy_loop_close_phi_args (basic_block old_bb, basic_block new_bb, + sese_info_p region, bool postpone) +{ + /* The successor of bb having close phi should be a merge of the diamond + inserted to guard the loop during codegen. */ + basic_block close_phi_merge_bb = single_succ (new_bb); + + for (gphi_iterator psi = gsi_start_phis (old_bb); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + tree res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; + + if (is_gimple_reg (res) && scev_analyzable_p (res, region->region)) + /* Loop close phi nodes should not be scev_analyzable_p. */ + gcc_unreachable (); + + gphi *new_phi = create_phi_node (SSA_NAME_VAR (res), new_bb); + tree new_res = create_new_def_for (res, new_phi, + gimple_phi_result_ptr (new_phi)); + set_rename (res, new_res, region); + + tree old_name = gimple_phi_arg_def (phi, 0); + tree new_name = get_new_name (region, new_bb, old_name, old_bb, false); + + /* Predecessor basic blocks of a loop close phi should have been code + generated before. FIXME: This is fixable by merging PHIs from inner + loops as well. When we are looking at close-phi of an outer loop, and + arguments flowing out of inner loop as not been collected by the + outer-loop close phi, we will hit this situation. For now we just bail + out. See: gfortran.dg/graphite/interchange-3.f90. */ + if (!new_name) + return false; + + add_phi_arg (new_phi, new_name, single_pred_edge (new_bb), + get_loc (old_name)); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] Adding loop-closed phi: "); + print_gimple_stmt (dump_file, new_phi, 0, 0); + } + + update_stmt (new_phi); + + /* When there is no loop guard around this codegenerated loop, there is no + need to collect the close-phi arg. */ + if (2 != EDGE_COUNT (close_phi_merge_bb->preds)) + continue; + + /* Add a PHI in the close_phi_merge_bb for each close phi of the loop. */ + tree init = find_init_value_close_phi (new_phi); + + /* A close phi must come from a loop-phi having an init value. */ + if (!init) + { + gcc_assert (postpone); + region->incomplete_phis.safe_push (std::make_pair (phi, new_phi)); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] postpone close phi nodes: "); + print_gimple_stmt (dump_file, new_phi, 0, 0); + } + continue; + } + + gphi *merge_phi = create_phi_node (SSA_NAME_VAR (res), + close_phi_merge_bb); + tree merge_res = create_new_def_for (res, merge_phi, + gimple_phi_result_ptr (merge_phi)); + set_rename (res, merge_res, region); + + edge from_loop = single_succ_edge (new_bb); + add_phi_arg (merge_phi, new_res, from_loop, get_loc (old_name)); + + /* The edge coming from loop guard. */ + edge other = from_loop == (*close_phi_merge_bb->preds)[0] + ? (*close_phi_merge_bb->preds)[1] : (*close_phi_merge_bb->preds)[0]; + + add_phi_arg (merge_phi, init, other, get_loc (old_name)); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] Adding guard-phi: "); + print_gimple_stmt (dump_file, merge_phi, 0, 0); + } + + update_stmt (new_phi); + } + + return true; +} + +/* Copy loop close phi nodes from BB to NEW_BB. */ + +static bool +copy_loop_close_phi_nodes (basic_block old_bb, basic_block new_bb, + sese_info_p region) +{ + if (dump_file) + fprintf (dump_file, "\n[codegen] copying loop closed phi nodes in bb_%d.", + new_bb->index); + /* Loop close phi nodes should have only one argument. */ + gcc_assert (1 == EDGE_COUNT (old_bb->preds)); + + return copy_loop_close_phi_args (old_bb, new_bb, region, true); +} + + +/* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB. + DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the + other pred of OLD_BB as well. If no such basic block exists then it is NULL. + NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be + NULL. + + Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa. + In this case DOMINATING_PRED = NULL. + + Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2. + + Returns true on successful copy of the args, false otherwise. */ + +static bool +add_phi_arg_for_new_expr (tree old_phi_args[2], tree new_phi_args[2], + edge old_bb_dominating_edge, + edge old_bb_non_dominating_edge, + gphi *phi, gphi *new_phi, + basic_block new_bb, sese_info_p region) +{ + basic_block def_pred[2]; + int not_found_bb_index = -1; + for (int i = 0; i < 2; i++) + { + /* If the corresponding def_bb could not be found the entry will be + NULL. */ + if (TREE_CODE (old_phi_args[i]) == INTEGER_CST) + def_pred[i] = get_def_bb_for_const (region, new_bb, + gimple_phi_arg_edge (phi, i)->src); + else + def_pred[i] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args[i])); + if (!def_pred[i]) + { + gcc_assert (not_found_bb_index == -1); + not_found_bb_index = i; + } + } + + /* Here we are pattern matching on the structure of CFG w.r.t. old one. */ + if (old_bb_dominating_edge) + { + return false; + basic_block new_pred1 = (*new_bb->preds)[0]->src; + basic_block new_pred2 = (*new_bb->preds)[1]->src; + vec <basic_block> *bbs + = region->copied_bb_map->get (old_bb_non_dominating_edge->src); + gcc_assert (bbs); + basic_block new_pred = NULL; + basic_block b; + int i; + FOR_EACH_VEC_ELT (*bbs, i, b) + if (new_pred1 == b || new_pred2 == b) + { + gcc_assert (!new_pred); + new_pred = b; + } + + gcc_assert (new_pred); + + edge new_non_dominating_edge = find_edge (new_pred, new_bb); + /* By the process of elimination we first insert insert phi-edge for + non-dominating pred which is computed above and then we insert the + remaining one. */ + int inserted_edge = 0; + for (; inserted_edge < 2; inserted_edge++) + { + edge new_bb_pred_edge = gimple_phi_arg_edge (phi, inserted_edge); + if (new_non_dominating_edge == new_bb_pred_edge) + { + add_phi_arg (new_phi, new_phi_args[inserted_edge], + new_non_dominating_edge, + get_loc (old_phi_args[inserted_edge])); + break; + } + } + + int edge_dominating = 0; + if (inserted_edge == 0) + edge_dominating = 1; + + edge new_dominating_edge = NULL; + for (int i; i < 2; i++) + { + edge e = gimple_phi_arg_edge (new_phi, i); + if (e != new_non_dominating_edge) + new_dominating_edge = e; + } + + add_phi_arg (new_phi, new_phi_args[edge_dominating], new_dominating_edge, + get_loc (old_phi_args[inserted_edge])); + } + else + { + /* Classic diamond structure: both edges are non-dominating. We need to + find one unique edge then the other can be found be elimination. If + any definition (def_pred) dominates both the preds of new_bb then we + bail out. Entries of def_pred maybe NULL, in that case we must + uniquely find pred with help of only one entry. */ + edge new_e[2] = { NULL, NULL }; + for (int i = 0; i < 2; i++) + { + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, new_bb->preds) + if (def_pred[i] + && dominated_by_p (CDI_DOMINATORS, e->src, def_pred[i])) + { + if (new_e[i]) + /* We do not know how to handle the case when def_pred + dominates more than a predecessor. */ + return false; + new_e[i] = e; + } + } + + gcc_assert (new_e[0] || new_e[1]); + + /* Find the other edge by process of elimination. */ + if (not_found_bb_index != -1) + { + gcc_assert (!new_e[not_found_bb_index]); + int found_bb_index = not_found_bb_index == 1 ? 0 : 1; + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, new_bb->preds) + { + if (new_e[found_bb_index] == e) + continue; + new_e[not_found_bb_index] = e; + } + } + + /* Add edges to phi args. */ + for (int i = 0; i < 2; i++) + add_phi_arg (new_phi, new_phi_args[i], new_e[i], + get_loc (old_phi_args[i])); + } + + return true; +} + +/* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated + region. If postpone is true and it isn't possible to copy any arg of PHI, + the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated + later. Returns false if the copying was unsuccessful. */ + +bool +copy_cond_phi_args (gphi *phi, gphi *new_phi, vec<tree> iv_map, + sese_info_p region, bool postpone) +{ + if (dump_file) + fprintf (dump_file, "\n[codegen] copying cond phi args: "); + gcc_assert (2 == gimple_phi_num_args (phi)); + + basic_block new_bb = gimple_bb (new_phi); + loop_p loop = gimple_bb (phi)->loop_father; + + basic_block old_bb = gimple_bb (phi); + edge old_bb_non_dominating_edge = NULL, old_bb_dominating_edge = NULL; + + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, old_bb->preds) + if (!dominated_by_p (CDI_DOMINATORS, old_bb, e->src)) + old_bb_non_dominating_edge = e; + else + old_bb_dominating_edge = e; + + gcc_assert (!dominated_by_p (CDI_DOMINATORS, old_bb, + old_bb_non_dominating_edge->src)); + + tree new_phi_args[2]; + tree old_phi_args[2]; + + for (unsigned i = 0; i < gimple_phi_num_args (phi); i++) + { + tree old_name = gimple_phi_arg_def (phi, i); + tree new_name = get_new_name (region, new_bb, old_name, old_bb, false); + old_phi_args[i] = old_name; + if (new_name) + { + new_phi_args [i] = new_name; + continue; + } + + if (vec_find (region->params, old_name)) + { + new_phi_args [i] = old_name; + if (dump_file) + { + fprintf (dump_file, + "\n[codegen] parameter argument to phi, new_expr: "); + print_gimple_stmt (dump_file, new_phi, 0, 0); + } + continue; + } + + /* If the phi-arg is scev-analyzeable but only in the first stage. */ + if (postpone && is_gimple_reg (old_name) + && scev_analyzable_p (old_name, region->region)) + { + gimple_seq stmts; + bool gloog_error = false; + tree new_expr + = get_rename_from_scev (old_name, &stmts, loop, new_bb, + old_bb, iv_map, region, &gloog_error); + if (gloog_error) + return false; + + gcc_assert (new_expr); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] scev analyzeable, new_expr: "); + print_generic_expr (dump_file, new_expr, 0); + } + gsi_insert_earliest (stmts, region); + new_phi_args [i] = new_name; + continue; + } + + gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name); + if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP) + /* If the phi arg was a function arg, or wasn't defined, just use the + old name. */ + gcc_unreachable (); + else if (postpone) + { + /* Postpone code gen for later for back-edges. */ + region->incomplete_phis.safe_push (std::make_pair (phi, new_phi)); + + if (dump_file) + { + fprintf (dump_file, "\n[codegen] postpone cond phi nodes: "); + print_gimple_stmt (dump_file, new_phi, 0, 0); + } + + new_phi_args [i] = NULL_TREE; + continue; + } + else + gcc_unreachable (); + } + + return add_phi_arg_for_new_expr (old_phi_args, new_phi_args, + old_bb_dominating_edge, + old_bb_non_dominating_edge, + phi, new_phi, new_bb, region); +} + +/* Copy cond phi nodes from BB to NEW_BB. */ + +static bool +copy_cond_phi_nodes (basic_block bb, basic_block new_bb, vec<tree> iv_map, + sese_info_p region) +{ + + gcc_assert (!bb_contains_loop_close_phi_nodes (bb)); + + if (dump_file) + fprintf (dump_file, "\n[codegen] copying cond phi nodes in bb_%d:", + new_bb->index); + + /* Cond phi nodes should have exactly two arguments. */ + gcc_assert (2 == EDGE_COUNT (bb->preds)); + + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + tree res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; + if (is_gimple_reg (res) && scev_analyzable_p (res, region->region)) + /* Cond phi nodes should not be scev_analyzable_p. */ + gcc_unreachable (); + + gphi *new_phi = create_phi_node (SSA_NAME_VAR (res), new_bb); + tree new_res = create_new_def_for (res, new_phi, + gimple_phi_result_ptr (new_phi)); + set_rename (res, new_res, region); + + if (!copy_cond_phi_args (phi, new_phi, iv_map, region, true)) + return false; + + update_stmt (new_phi); + } + + return true; +} + +/* Return true if STMT should be copied from region to the + new code-generated region. LABELs, CONDITIONS, induction-variables + and region parameters need not be copied. */ + +static bool +should_copy_to_new_region (gimple *stmt, sese_info_p region) +{ + /* Do not copy labels or conditions. */ + if (gimple_code (stmt) == GIMPLE_LABEL + || gimple_code (stmt) == GIMPLE_COND) + return false; + + tree lhs; + /* Do not copy induction variables. */ + if (is_gimple_assign (stmt) + && (lhs = gimple_assign_lhs (stmt)) + && TREE_CODE (lhs) == SSA_NAME + && is_gimple_reg (lhs) + && scev_analyzable_p (lhs, region->region)) + return false; + + return true; +} + +/* Create new names for all the definitions created by COPY and + add replacement mappings for each new name. */ + +static void +set_rename_for_each_def (gimple *stmt, sese_info_p region) +{ + def_operand_p def_p; + ssa_op_iter op_iter; + FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS) + { + tree old_name = DEF_FROM_PTR (def_p); + tree new_name = create_new_def_for (old_name, stmt, def_p); + set_rename (old_name, new_name, region); + } +} + /* Duplicates the statements of basic block BB into basic block NEW_BB and compute the new induction variables according to the IV_MAP. GLOOG_ERROR is set when the code generation cannot continue. */ - -static void +static bool graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, - rename_map_type *rename_map, vec<tree> iv_map, sese_info_p region, bool *gloog_error) { - gimple_stmt_iterator gsi, gsi_tgt; - loop_p loop = bb->loop_father; + /* Iterator poining to the place where new statement (s) will be inserted. */ + gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb); - gsi_tgt = gsi_start_bb (new_bb); - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) { - def_operand_p def_p; - ssa_op_iter op_iter; gimple *stmt = gsi_stmt (gsi); - gimple *copy; - tree lhs; - - /* Do not copy labels or conditions. */ - if (gimple_code (stmt) == GIMPLE_LABEL - || gimple_code (stmt) == GIMPLE_COND) - continue; - - /* Do not copy induction variables. */ - if (is_gimple_assign (stmt) - && (lhs = gimple_assign_lhs (stmt)) - && TREE_CODE (lhs) == SSA_NAME - && is_gimple_reg (lhs) - && scev_analyzable_p (lhs, region->region)) + if (!should_copy_to_new_region (stmt, region)) continue; /* Create a new copy of STMT and duplicate STMT's virtual operands. */ - copy = gimple_copy (stmt); + gimple *copy = gimple_copy (stmt); gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] inserting statement: "); + print_gimple_stmt (dump_file, copy, 0, 0); + } + maybe_duplicate_eh_stmt (copy, stmt); gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt); - /* Create new names for all the definitions created by COPY and - add replacement mappings for each new name. */ - FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS) - { - tree old_name = DEF_FROM_PTR (def_p); - tree new_name = create_new_def_for (old_name, copy, def_p); - set_rename (rename_map, old_name, new_name); - } + /* Crete new names for each def in the copied stmt. */ + set_rename_for_each_def (copy, region); - if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map, - gloog_error)) + loop_p loop = bb->loop_father; + if (rename_uses (copy, &gsi_tgt, bb, region, loop, iv_map, gloog_error)) { - gcc_assert (gsi_stmt (gsi_tgt) == copy); fold_stmt_inplace (&gsi_tgt); + gcc_assert (gsi_stmt (gsi_tgt) == copy); } + if (*gloog_error) + return false; + update_stmt (copy); } + + return true; } /* Copies BB and includes in the copied BB all the statements that can @@ -564,17 +1729,127 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, edge copy_bb_and_scalar_dependences (basic_block bb, sese_info_p region, edge next_e, vec<tree> iv_map, - bool *gloog_error) + bool *codegen_err) { + int num_phis = number_of_phi_nodes (bb); + + if (region->copied_bb_map->get (bb)) + { + /* FIXME: We do not handle inner loop unrolling when the inner loop has + phi-nodes. In that case inner loop will be copied multiple times + outside the region. */ + if (num_phis) + { + *codegen_err = true; + return NULL; + } + } + basic_block new_bb = split_edge (next_e); - rename_map_type rename_map (10); + if (num_phis > 0 && bb_contains_loop_phi_nodes (bb)) + { + basic_block phi_bb = next_e->dest->loop_father->header; - next_e = single_succ_edge (new_bb); - graphite_copy_stmts_from_block (bb, new_bb, &rename_map, iv_map, region, - gloog_error); - remove_phi_nodes (new_bb); + /* At this point we are unable to codegenerate by still preserving the SSA + structure because maybe the loop is completely unrolled and the PHIs + and cross-bb scalar dependencies are untrackable w.r.t. the original + code. See gfortran.dg/graphite/pr29832.f90. */ + if (EDGE_COUNT (bb->preds) != EDGE_COUNT (phi_bb->preds)) + { + *codegen_err = true; + return NULL; + } - return next_e; + if (dump_file) + fprintf (dump_file, "\n[codegen] bb_%d contains loop phi nodes", + bb->index); + if (!copy_loop_phi_nodes (bb, phi_bb, region)) + { + *codegen_err = true; + return NULL; + } + } + else if (bb_contains_loop_close_phi_nodes (bb)) + { + if (dump_file) + fprintf (dump_file, "\n[codegen] bb_%d contains close phi nodes", + bb->index); + + /* Make sure that NEW_BB is the loop->exit->dest. */ + edge e = single_pred_edge (new_bb); + basic_block phi_bb = new_bb; + if (e->src->loop_father == e->dest->loop_father) + { + /* This is one of the places which shows preserving original structure + is not always possible, as we may need to insert close PHI for a + loop where the latch does not have any mapping, or the mapping is + ambiguous. */ + basic_block old_loop_bb = single_pred_edge (bb)->src; + vec <basic_block> *bbs = region->copied_bb_map->get (old_loop_bb); + if (!bbs || bbs->length () != 1) + { + *codegen_err = true; + return NULL; + } + + basic_block new_loop_bb = (*bbs)[0]; + loop_p new_loop = new_loop_bb->loop_father; + phi_bb = single_exit (new_loop)->dest; + e = single_pred_edge (phi_bb); + } + + gcc_assert (e->src->loop_father != e->dest->loop_father); + + if (!copy_loop_close_phi_nodes (bb, phi_bb, region)) + { + *codegen_err = true; + return NULL; + } + } + else if (num_phis > 0) + { + if (dump_file) + fprintf (dump_file, "\n[codegen] bb_%d contains cond phi nodes", + bb->index); + + basic_block phi_bb = single_pred (new_bb); + loop_p loop_father = new_bb->loop_father; + + /* Move back until we find the block with two predecessors. */ + while (single_pred_p (phi_bb)) + phi_bb = single_pred_edge (phi_bb)->src; + + /* If a corresponding merge-point was not found, then abort codegen. */ + if (phi_bb->loop_father != loop_father + || !copy_cond_phi_nodes (bb, phi_bb, iv_map, region)) + { + *codegen_err = true; + return NULL; + } + } + + if (dump_file) + fprintf (dump_file, "\n[codegen] copying from bb_%d to bb_%d", + bb->index, new_bb->index); + + vec <basic_block> *copied_bbs = region->copied_bb_map->get (bb); + if (copied_bbs) + copied_bbs->safe_push (new_bb); + else + { + vec<basic_block> bbs; + bbs.create (2); + bbs.safe_push (new_bb); + region->copied_bb_map->put (bb, bbs); + } + + if (!graphite_copy_stmts_from_block (bb, new_bb, iv_map, region, codegen_err)) + { + *codegen_err = true; + return NULL; + } + + return single_succ_edge (new_bb); } /* Returns the outermost loop in SCOP that contains BB. */ @@ -759,8 +2034,6 @@ set_ifsese_condition (ifsese if_region, tree condition) bool invariant_in_sese_p_rec (tree t, sese_l ®ion, bool *has_vdefs) { - ssa_op_iter iter; - use_operand_p use_p; if (!defined_in_sese_p (t, region)) return true; @@ -782,6 +2055,8 @@ invariant_in_sese_p_rec (tree t, sese_l ®ion, bool *has_vdefs) if (tree vuse = gimple_vuse (stmt)) return invariant_in_sese_p_rec (vuse, region, has_vdefs); + ssa_op_iter iter; + use_operand_p use_p; FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) { tree use = USE_FROM_PTR (use_p); @@ -22,6 +22,14 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_SESE_H #define GCC_SESE_H +typedef hash_map<basic_block, vec<basic_block> > bb_map_t; +typedef hash_map<tree, vec<tree> > rename_map_t; +typedef struct ifsese_s *ifsese; +/* First phi is the new codegenerated phi second one is original phi. */ +typedef std::pair <gphi *, gphi *> phi_rename; +/* First edge is the init edge and second is the back edge w.r.t. a loop. */ +typedef std::pair<edge, edge> init_back_edge_pair_t; + /* A Single Entry, Single Exit region is a part of the CFG delimited by two edges. */ struct sese_l @@ -50,6 +58,20 @@ get_exit_bb (sese_l &s) return s.exit->src; } +/* Returns the index of V where ELEM can be found. -1 Otherwise. */ + +template<typename T> +int +vec_find (const vec<T> &v, const T &elem) +{ + int i; + T t; + FOR_EACH_VEC_ELT (v, i, t) + if (elem == t) + return i; + return -1; +} + /* A helper structure for bookkeeping information about a scop in graphite. */ typedef struct sese_info_t { @@ -59,17 +81,29 @@ typedef struct sese_info_t /* Parameters used within the SCOP. */ vec<tree> params; + /* Maps an old name to one or more new names. When there are several new + names, one has to select the definition corresponding to the immediate + dominator. */ + rename_map_t *rename_map; + /* Loops completely contained in this SESE. */ bitmap loops; vec<loop_p> loop_nest; /* Basic blocks contained in this SESE. */ vec<basic_block> bbs; -} *sese_info_p; -#define SESE_PARAMS(S) (S->params) -#define SESE_LOOPS(S) (S->loops) -#define SESE_LOOP_NEST(S) (S->loop_nest) + /* Copied basic blocks indexed by the original bb. */ + bb_map_t *copied_bb_map; + + /* A vector of phi nodes to be updated when all arguments are available. The + pair contains first the old_phi and second the new_phi. */ + vec<phi_rename> incomplete_phis; + + /* The condition region generated for this sese. */ + ifsese if_region; + +} *sese_info_p; extern sese_info_p new_sese_info (edge, edge); extern void free_sese_info (sese_info_p); @@ -80,13 +114,23 @@ extern edge copy_bb_and_scalar_dependences (basic_block, sese_info_p, edge, extern struct loop *outermost_loop_in_sese (sese_l &, basic_block); extern tree scalar_evolution_in_region (sese_l &, loop_p, tree); extern bool invariant_in_sese_p_rec (tree, sese_l &, bool *); +extern bool bb_contains_loop_phi_nodes (basic_block); +extern bool bb_contains_loop_close_phi_nodes (basic_block); +extern std::pair<edge, edge> get_edges (basic_block bb); +extern void copy_loop_phi_args (gphi *, init_back_edge_pair_t &, + gphi *, init_back_edge_pair_t &, + sese_info_p, bool); +extern bool copy_loop_close_phi_args (basic_block, basic_block, + sese_info_p, bool); +extern bool copy_cond_phi_args (gphi *, gphi *, vec<tree>, + sese_info_p, bool); /* Check that SESE contains LOOP. */ static inline bool sese_contains_loop (sese_info_p sese, struct loop *loop) { - return bitmap_bit_p (SESE_LOOPS (sese), loop->num); + return bitmap_bit_p (sese->loops, loop->num); } /* The number of parameters in REGION. */ @@ -94,7 +138,7 @@ sese_contains_loop (sese_info_p sese, struct loop *loop) static inline unsigned sese_nb_params (sese_info_p region) { - return SESE_PARAMS (region).length (); + return region->params.length (); } /* Checks whether BB is contained in the region delimited by ENTRY and @@ -239,6 +283,8 @@ recompute_all_dominators (void) calculate_dominance_info (CDI_POST_DOMINATORS); } +typedef std::pair <gimple *, tree> scalar_use; + typedef struct gimple_poly_bb { basic_block bb; @@ -267,6 +313,8 @@ typedef struct gimple_poly_bb vec<gimple *> conditions; vec<gimple *> condition_cases; vec<data_reference_p> data_refs; + vec<scalar_use> read_scalar_refs; + vec<tree> write_scalar_refs; } *gimple_poly_bb_p; #define GBB_BB(GBB) (GBB)->bb |