From 65b016eb13b67dd990f30a55948a623d9deadd11 Mon Sep 17 00:00:00 2001 From: Aditya Kumar Date: Thu, 12 Nov 2015 00:37:47 +0000 Subject: Preserve the original program while using graphite. Earlier, graphite used to translate portions of the original program after scop-detection in order to represent the SCoP into polyhedral model. This was required because each basic block was represented as independent basic block in the polyhedral model. So all the cross-basic-block dependencies were translated out-of-ssa. With this patch those dependencies are also exposed to the ISL, so there is no need to modify the original structure of the program. After this patch we should be able to enable graphite at some default optimization level. Highlights: Remove cross bb scalar to array translation For reductions, add support for more than just INT_CST Early bailout on codegen. Verify loop-closed ssa structure during copy of renames The uses of exprs should come from bb which dominates the bb Collect the init value of close phi in loop-guard Do not follow vuses for close-phi, postpone loop-close phi until the corresponding loop-phi is processed Bail out if no bb found to place cond/loop -phis Move insertion of liveouts at the end of codegen Insert loop-phis in the loop-header. This patch passes regtest and bootstrap with BOOT_CFLAGS='-O2 -fgraphite-identity -floop-nest-optimize' 2015-11-11 Aditya Kumar Sebastian Pop * 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. Co-Authored-By: Sebastian Pop From-SVN: r230200 --- gcc/sese.h | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 54 insertions(+), 6 deletions(-) (limited to 'gcc/sese.h') diff --git a/gcc/sese.h b/gcc/sese.h index b3d48b9..bce226a 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -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 > bb_map_t; +typedef hash_map > rename_map_t; +typedef struct ifsese_s *ifsese; +/* First phi is the new codegenerated phi second one is original phi. */ +typedef std::pair phi_rename; +/* First edge is the init edge and second is the back edge w.r.t. a loop. */ +typedef std::pair 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 +int +vec_find (const vec &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 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_nest; /* Basic blocks contained in this SESE. */ vec 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 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 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, + 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 scalar_use; + typedef struct gimple_poly_bb { basic_block bb; @@ -267,6 +313,8 @@ typedef struct gimple_poly_bb vec conditions; vec condition_cases; vec data_refs; + vec read_scalar_refs; + vec write_scalar_refs; } *gimple_poly_bb_p; #define GBB_BB(GBB) (GBB)->bb -- cgit v1.1