From 2ecf4eca922c12a93918f2c4b7c3b3b962d63e98 Mon Sep 17 00:00:00 2001 From: Aditya Kumar Date: Wed, 18 Nov 2015 21:08:33 +0000 Subject: [PATCH] Move codegen related functions to graphite-isl-ast-to-gimple.c No functional changes intended. This patch passes regtest and bootstrap on linux-x86-64 with BOOT_CFLAGS='-O2 -fgraphite-identity -floop-nest-optimize' gcc/ChangeLog: 2015-11-14 hiraditya * graphite-isl-ast-to-gimple.c (struct ast_build_info): Remove semicolon. (class translate_isl_ast_to_gimple): Indentation. (translate_pending_phi_nodes): Comment. (add_parameters_to_ivs_params): Moved from sese.c inside class translate_isl_ast_to_gimple. (get_max_schedule_dimensions): Same. (generate_isl_context): Same. (extend_schedule): Same. (generate_isl_schedule): Same. (set_options): Same. (scop_to_isl_ast): Same. (is_valid_rename): Same. (get_rename): Same. (get_rename_from_scev): Same. (get_def_bb_for_const): Same. (get_new_name): Same. (collect_all_ssa_names): Same. (copy_loop_phi_args): Same. (copy_loop_phi_nodes): Same. (copy_loop_close_phi_args): Same. (copy_loop_close_phi_nodes): Same. (copy_cond_phi_args): Same. (copy_cond_phi_nodes): Same. (graphite_copy_stmts_from_block): Same. (copy_bb_and_scalar_dependences): Same. (add_phi_arg_for_new_expr): Same. (rename_uses): Same. (set_rename): Same. (set_rename_for_each_def): Same. (gsi_insert_earliest): Same. (rename_all_uses): Same. (codegen_error_p): Same. (print_isl_ast_node): Same. (translate_isl_ast_for_loop): Call function codegen_error_p. (translate_isl_ast_to_gimple::translate_isl_ast): Same. (translate_isl_ast_node_user): Make nb_loops const and release iv_map before exit. (get_true_edge_from_guard_bb): Move all free-functions early. (get_false_edge_from_guard_bb): Same. (bb_contains_loop_close_phi_nodes): Same. (bb_contains_loop_phi_nodes): Same. (is_loop_closed_ssa_use): Same. (number_of_phi_nodes): Same. (phi_uses_name): Same. (later_of_the_two): Same. (substitute_ssa_name): (get_edges): Same. (get_loc): Same. (get_loop_init_value): Same. (find_init_value): Same. (find_init_value_close_phi): Same. (ast_build_before_for): Same. (graphite_regenerate_ast_isl): Formatting changes. * graphite-scop-detection.c (build_cross_bb_scalars_use): Same. * sese.c (get_rename): Move to graphite-isl-ast-to-gimple.c (set_rename): Same. (gsi_insert_earliest): Same. (collect_all_ssa_names): Same. (rename_all_uses): Same. (rename_uses): Same. (get_def_bb_for_const): Same. (copy_loop_phi_nodes): Same. (copy_loop_close_phi_args): Same. (copy_loop_close_phi_nodes): Same. (copy_cond_phi_args): Same. (copy_cond_phi_nodes): Same. (set_rename_for_each_def): Same. (graphite_copy_stmts_from_block): Same. (copy_bb_and_scalar_dependences): Same. (if_region_set_false_region): Same. (scev_analyzable_p): Same. * sese.h: Delete extern functions moved to graphite-isl-ast-to-gimple.c From-SVN: r230566 --- gcc/ChangeLog | 75 + gcc/graphite-isl-ast-to-gimple.c | 2233 ++++++++++++++++++++++++++---- gcc/graphite-scop-detection.c | 4 +- gcc/sese.c | 1575 +-------------------- gcc/sese.h | 44 +- 5 files changed, 2113 insertions(+), 1818 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8bf60bb3eae..521c3aebe38 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,78 @@ +2015-11-18 Aditya Kumar + + * graphite-isl-ast-to-gimple.c (struct ast_build_info): Remove semicolon. + (class translate_isl_ast_to_gimple): Indentation. + (translate_pending_phi_nodes): Comment. + (add_parameters_to_ivs_params): Moved from sese.c inside class + translate_isl_ast_to_gimple. + (get_max_schedule_dimensions): Same. + (generate_isl_context): Same. + (extend_schedule): Same. + (generate_isl_schedule): Same. + (set_options): Same. + (scop_to_isl_ast): Same. + (is_valid_rename): Same. + (get_rename): Same. + (get_rename_from_scev): Same. + (get_def_bb_for_const): Same. + (get_new_name): Same. + (collect_all_ssa_names): Same. + (copy_loop_phi_args): Same. + (copy_loop_phi_nodes): Same. + (copy_loop_close_phi_args): Same. + (copy_loop_close_phi_nodes): Same. + (copy_cond_phi_args): Same. + (copy_cond_phi_nodes): Same. + (graphite_copy_stmts_from_block): Same. + (copy_bb_and_scalar_dependences): Same. + (add_phi_arg_for_new_expr): Same. + (rename_uses): Same. + (set_rename): Same. + (set_rename_for_each_def): Same. + (gsi_insert_earliest): Same. + (rename_all_uses): Same. + (codegen_error_p): Same. + (print_isl_ast_node): Same. + (translate_isl_ast_for_loop): Call function codegen_error_p. + (translate_isl_ast_to_gimple::translate_isl_ast): Same. + (translate_isl_ast_node_user): Make nb_loops const and release + iv_map before exit. + (get_true_edge_from_guard_bb): Move all free-functions early. + (get_false_edge_from_guard_bb): Same. + (bb_contains_loop_close_phi_nodes): Same. + (bb_contains_loop_phi_nodes): Same. + (is_loop_closed_ssa_use): Same. + (number_of_phi_nodes): Same. + (phi_uses_name): Same. + (later_of_the_two): Same. + (substitute_ssa_name): + (get_edges): Same. + (get_loc): Same. + (get_loop_init_value): Same. + (find_init_value): Same. + (find_init_value_close_phi): Same. + (ast_build_before_for): Same. + (graphite_regenerate_ast_isl): Formatting changes. + * graphite-scop-detection.c (build_cross_bb_scalars_use): Same. + * sese.c (get_rename): Move to graphite-isl-ast-to-gimple.c + (set_rename): Same. + (gsi_insert_earliest): Same. + (collect_all_ssa_names): Same. + (rename_all_uses): Same. + (rename_uses): Same. + (get_def_bb_for_const): Same. + (copy_loop_phi_nodes): Same. + (copy_loop_close_phi_args): Same. + (copy_loop_close_phi_nodes): Same. + (copy_cond_phi_args): Same. + (copy_cond_phi_nodes): Same. + (set_rename_for_each_def): Same. + (graphite_copy_stmts_from_block): Same. + (copy_bb_and_scalar_dependences): Same. + (if_region_set_false_region): Same. + (scev_analyzable_p): Same. + * sese.h: Delete extern functions moved to graphite-isl-ast-to-gimple.c. + 2015-11-18 Andreas Tobler * config/i386/freebsd.h (ASM_OUTPUT_MAX_SKIP_ALIGN): Bring in the diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c index 7fa4ce3d395..b9e0a4e417b 100644 --- a/gcc/graphite-isl-ast-to-gimple.c +++ b/gcc/graphite-isl-ast-to-gimple.c @@ -48,8 +48,14 @@ extern "C" { #include "gimple.h" #include "params.h" #include "fold-const.h" +#include "gimple-fold.h" #include "gimple-iterator.h" +#include "gimplify.h" +#include "gimplify-me.h" +#include "tree-eh.h" #include "tree-ssa-loop.h" +#include "tree-ssa-operands.h" +#include "tree-ssa-propagate.h" #include "tree-pass.h" #include "cfgloop.h" #include "tree-data-ref.h" @@ -60,10 +66,13 @@ extern "C" { #include "tree-phinodes.h" #include "tree-into-ssa.h" #include "ssa-iterators.h" -#include #include "graphite-isl-ast-to-gimple.h" #include "tree-cfg.h" #include "gimple-pretty-print.h" +#include "cfganal.h" +#include "value-prof.h" + +#include /* 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 @@ -78,7 +87,7 @@ struct ast_build_info { ast_build_info() : is_parallelizable(false) - { }; + { } bool is_parallelizable; }; @@ -129,7 +138,7 @@ class translate_isl_ast_to_gimple public: translate_isl_ast_to_gimple (sese_info_p r) : region (r), codegen_error (false) - { } + { } /* Translates an ISL AST node NODE to GCC representation in the context of a SESE. */ @@ -258,9 +267,193 @@ class translate_isl_ast_to_gimple __isl_keep isl_ast_expr *user_expr, ivs_params &ip, sese_l ®ion); + /* Patch the missing arguments of the phi nodes. */ + void translate_pending_phi_nodes (void); - bool codegen_error_p () { return codegen_error; } + /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */ + + void add_parameters_to_ivs_params (scop_p scop, ivs_params &ip); + + /* Get the maximal number of schedule dimensions in the scop SCOP. */ + + int get_max_schedule_dimensions (scop_p scop); + + /* Generates a build, which specifies the constraints on the parameters. */ + + __isl_give isl_ast_build *generate_isl_context (scop_p scop); + + /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions. + + For schedules with different dimensionality, the isl AST generator can not + define an order and will just randomly choose an order. The solution to + this problem is to extend all schedules to the maximal number of schedule + dimensions (using '0's for the remaining values). */ + + __isl_give isl_map *extend_schedule (__isl_take isl_map *schedule, + int nb_schedule_dims); + + /* Generates a schedule, which specifies an order used to + visit elements in a domain. */ + + __isl_give isl_union_map *generate_isl_schedule (scop_p scop); + + /* Set the separate option for all dimensions. + This helps to reduce control overhead. */ + + __isl_give isl_ast_build * set_options (__isl_take isl_ast_build *control, + __isl_keep isl_union_map *schedule); + + /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in + IP. */ + + __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop, ivs_params &ip); + + + /* 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. */ + + bool is_valid_rename (tree rename, basic_block def_bb, basic_block use_bb, + bool loop_phi, tree old_name, basic_block old_bb) const; + + /* 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. */ + + tree get_rename (basic_block new_bb, tree old_name, + basic_block old_bb, bool loop_phi) const; + + /* For ops which are scev_analyzeable, we can regenerate a new name from + its scalar evolution around LOOP. */ + + tree get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop, + basic_block new_bb, basic_block old_bb, + vec iv_map); + + /* 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. */ + + basic_block get_def_bb_for_const (basic_block bb, basic_block old_bb) const; + + /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is + true when we want to rename an OP within a loop PHI instruction. */ + + tree get_new_name (basic_block new_bb, tree op, + basic_block old_bb, bool loop_phi) const; + + /* Collect all the operands of NEW_EXPR by recursively visiting each + operand. */ + + void collect_all_ssa_names (tree new_expr, vec *vec_ssa); + + /* 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, + bool postpone); + + /* Copy loop phi nodes from BB to NEW_BB. */ + + bool copy_loop_phi_nodes (basic_block bb, basic_block new_bb); + + /* 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, + bool postpone); + + /* Copy loop close phi nodes from BB to NEW_BB. */ + + bool copy_loop_close_phi_nodes (basic_block old_bb, basic_block new_bb); + + /* 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 iv_map, + bool postpone); + + /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block + containing phi nodes coming from two predecessors, and none of them are back + edges. */ + + bool copy_cond_phi_nodes (basic_block bb, basic_block new_bb, + vec iv_map); + + /* Duplicates the statements of basic block BB into basic block NEW_BB + and compute the new induction variables according to the IV_MAP. + CODEGEN_ERROR is set when the code generation cannot continue. */ + + bool graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, + vec iv_map); + + /* Copies BB and includes in the copied BB all the statements that can + be reached following the use-def chains from the memory accesses, + and returns the next edge following this new block. codegen_error is + set when the code generation cannot continue. */ + + edge copy_bb_and_scalar_dependences (basic_block bb, edge next_e, + vec iv_map); + + /* 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. */ + + 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); + + /* Renames the scalar uses of the statement COPY, using the substitution map + RENAME_MAP, inserting the gimplification code at GSI_TGT, for the + translation REGION, with the original copied statement in LOOP, and using + the induction variable renaming map IV_MAP. Returns true when something + has been renamed. codegen_error is set when the code generation cannot + continue. */ + + bool rename_uses (gimple *copy, gimple_stmt_iterator *gsi_tgt, + basic_block old_bb, loop_p loop, vec iv_map); + + /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). + When OLD_NAME and EXPR are the same we assert. */ + + void set_rename (tree old_name, tree expr); + + /* Create new names for all the definitions created by COPY and add + replacement mappings for each new name. */ + + void set_rename_for_each_def (gimple *stmt); + + /* Insert each statement from SEQ at its earliest insertion p. */ + + void gsi_insert_earliest (gimple_seq seq); + + /* Rename all the operands of NEW_EXPR by recursively visiting each + operand. */ + + tree rename_all_uses (tree new_expr, basic_block new_bb, basic_block old_bb); + + bool codegen_error_p () const + { return codegen_error; } + + /* Prints NODE to FILE. */ + + void print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node, + __isl_keep isl_ctx *ctx) const; private: sese_info_p region; @@ -586,21 +779,21 @@ translate_isl_ast_for_loop (loop_p context_loop, isl_ast_node_free (for_body); /* Early return if we failed to translate loop body. */ - if (!next_e || codegen_error) + if (!next_e || codegen_error_p ()) return NULL; redirect_edge_succ_nodup (next_e, after); set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); if (flag_loop_parallelize_all) - { - isl_id *id = isl_ast_node_get_annotation (node_for); - gcc_assert (id); - ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id); - loop->can_be_parallel = for_info->is_parallelizable; - free (for_info); - isl_id_free (id); - } + { + isl_id *id = isl_ast_node_get_annotation (node_for); + gcc_assert (id); + ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id); + loop->can_be_parallel = for_info->is_parallelizable; + free (for_info); + isl_id_free (id); + } return last_e; } @@ -612,7 +805,7 @@ translate_isl_ast_for_loop (loop_p context_loop, { - ... + ... } @@ -646,7 +839,7 @@ get_upper_bound (__isl_keep isl_ast_node *node_for) case isl_ast_op_lt: { - // (iterator < ub) => (iterator <= ub - 1) + /* (iterator < ub) => (iterator <= ub - 1). */ isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1); isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1); @@ -794,7 +987,7 @@ translate_isl_ast_node_user (__isl_keep isl_ast_node *node, gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) && "The entry block should not even appear within a scop"); - int nb_loops = number_of_loops (cfun); + const int nb_loops = number_of_loops (cfun); vec iv_map; iv_map.create (nb_loops); iv_map.safe_grow_cleared (nb_loops); @@ -810,11 +1003,12 @@ translate_isl_ast_node_user (__isl_keep isl_ast_node *node, 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, - &codegen_error); - if (codegen_error) + next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), next_e, + iv_map); + + iv_map.release (); + + if (codegen_error_p ()) return NULL; if (dump_file) @@ -823,7 +1017,6 @@ translate_isl_ast_node_user (__isl_keep isl_ast_node *node, print_loops_bb (dump_file, next_e->src, 0, 3); } - iv_map.release (); mark_virtual_operands_for_renaming (cfun); update_ssa (TODO_update_ssa); @@ -904,7 +1097,7 @@ 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) + if (codegen_error_p ()) return NULL; switch (isl_ast_node_get_type (node)) @@ -932,263 +1125,1838 @@ translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop, } } -/* Patch the missing arguments of the phi nodes. */ +/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ -void -translate_isl_ast_to_gimple::translate_pending_phi_nodes () +edge +get_true_edge_from_guard_bb (basic_block bb) { - 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); - } + edge e; + edge_iterator ei; - auto_vec 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 (); + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->flags & EDGE_TRUE_VALUE) + return e; - if (dump_file) - { - fprintf (dump_file, "[codegen] to new-phi: "); - print_gimple_stmt (dump_file, new_phi, 0, 0); - } - } + gcc_unreachable (); + return NULL; } -/* Prints NODE to FILE. */ +/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ -void -print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node, - __isl_keep isl_ctx *ctx) +edge +get_false_edge_from_guard_bb (basic_block bb) { - isl_printer *prn = isl_printer_to_file (ctx, file); - prn = isl_printer_set_output_format (prn, ISL_FORMAT_C); - prn = isl_printer_print_ast_node (prn, node); - prn = isl_printer_print_str (prn, "\n"); - isl_printer_free (prn); -} + edge e; + edge_iterator ei; -/* Add ISL's parameter identifiers and corresponding.trees to ivs_params */ + FOR_EACH_EDGE (e, ei, bb->succs) + if (!(e->flags & EDGE_TRUE_VALUE)) + return e; -static void -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 == 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] = region->params[i]; - } + gcc_unreachable (); + return NULL; } +/* Return true when BB contains loop close phi nodes. A loop close phi node is + at the exit of loop which takes one argument that is the last value of the + variable being used out of the loop. */ -/* Generates a build, which specifies the constraints on the parameters. */ - -static __isl_give isl_ast_build * -generate_isl_context (scop_p scop) +bool +bb_contains_loop_close_phi_nodes (basic_block bb) { - isl_set *context_isl = isl_set_params (isl_set_copy (scop->param_context)); - return isl_ast_build_from_context (context_isl); + return single_pred_p (bb) + && bb->loop_father != single_pred_edge (bb)->src->loop_father; } -/* Get the maximal number of schedule dimensions in the scop SCOP. */ +/* Return true when BB contains loop phi nodes. A loop phi node is the loop + header containing phi nodes which has one init-edge and one back-edge. */ -static -int get_max_schedule_dimensions (scop_p scop) +bool +bb_contains_loop_phi_nodes (basic_block bb) { - int i; - poly_bb_p pbb; - int schedule_dims = 0; + gcc_assert (EDGE_COUNT (bb->preds) <= 2); - FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) - { - int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out); - if (pbb_schedule_dims > schedule_dims) - schedule_dims = pbb_schedule_dims; - } + if (bb->preds->length () == 1) + return false; - return schedule_dims; -} + unsigned depth = loop_depth (bb->loop_father); -/* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions. + edge preds[2] = { (*bb->preds)[0], (*bb->preds)[1] }; - For schedules with different dimensionality, the isl AST generator can not - define an order and will just randomly choose an order. The solution to this - problem is to extend all schedules to the maximal number of schedule - dimensions (using '0's for the remaining values). */ + if (depth > loop_depth (preds[0]->src->loop_father) + || depth > loop_depth (preds[1]->src->loop_father)) + return true; -static __isl_give isl_map * -extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims) -{ - int tmp_dims = isl_map_dim (schedule, isl_dim_out); - schedule = - isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims); - isl_val *zero = - isl_val_int_from_si (isl_map_get_ctx (schedule), 0); - int i; - for (i = tmp_dims; i < nb_schedule_dims; i++) - { - schedule = - isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero)); - } - isl_val_free (zero); - return schedule; + /* 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; } -/* Generates a schedule, which specifies an order used to - visit elements in a domain. */ +/* Check if USE is defined in a basic block from where the definition of USE can + propagate from all the paths. FIXME: Verify checks for virtual operands. */ -static __isl_give isl_union_map * -generate_isl_schedule (scop_p scop) +static bool +is_loop_closed_ssa_use (basic_block bb, tree use) { - int nb_schedule_dims = get_max_schedule_dimensions (scop); - int i; - poly_bb_p pbb; - isl_union_map *schedule_isl = - isl_union_map_empty (isl_set_get_space (scop->param_context)); + if (TREE_CODE (use) != SSA_NAME || virtual_operand_p (use)) + return true; - FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) - { - /* Dead code elimination: when the domain of a PBB is empty, - don't generate code for the PBB. */ - if (isl_set_is_empty (pbb->domain)) - continue; + /* 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; - isl_map *bb_schedule = isl_map_copy (pbb->transformed); - bb_schedule = isl_map_intersect_domain (bb_schedule, - isl_set_copy (pbb->domain)); - bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims); - schedule_isl = - isl_union_map_union (schedule_isl, - isl_union_map_from_map (bb_schedule)); - } - return schedule_isl; + 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)); } -/* This method is executed before the construction of a for node. */ -static __isl_give isl_id * -ast_build_before_for (__isl_keep isl_ast_build *build, void *user) +/* Return the number of phi nodes in BB. */ + +static int +number_of_phi_nodes (basic_block bb) { - isl_union_map *dependences = (isl_union_map *) user; - ast_build_info *for_info = XNEW (struct ast_build_info); - isl_union_map *schedule = isl_ast_build_get_schedule (build); - isl_space *schedule_space = isl_ast_build_get_schedule_space (build); - int dimension = isl_space_dim (schedule_space, isl_dim_out); - for_info->is_parallelizable = - !carries_deps (schedule, dependences, dimension); - isl_union_map_free (schedule); - isl_space_free (schedule_space); - isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info); - return id; + int num_phis = 0; + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + num_phis++; + return num_phis; } -/* Set the separate option for all dimensions. - This helps to reduce control overhead. */ +/* Returns true if BB uses name in one of its PHIs. */ -static __isl_give isl_ast_build * -set_options (__isl_take isl_ast_build *control, - __isl_keep isl_union_map *schedule) +static bool +phi_uses_name (basic_block bb, tree name) { - isl_ctx *ctx = isl_union_map_get_ctx (schedule); - isl_space *range_space = isl_space_set_alloc (ctx, 0, 1); - range_space = - isl_space_set_tuple_name (range_space, isl_dim_set, "separate"); - isl_union_set *range = - isl_union_set_from_set (isl_set_universe (range_space)); - isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule)); - domain = isl_union_set_universe (domain); - isl_union_map *options = isl_union_map_from_domain_and_range (domain, range); - return isl_ast_build_set_options (control, options); + 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; } -static __isl_give isl_ast_node * -scop_to_isl_ast (scop_p scop, ivs_params &ip) +/* 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. */ + +bool +translate_isl_ast_to_gimple:: +is_valid_rename (tree rename, basic_block def_bb, basic_block use_bb, + bool loop_phi, tree old_name, basic_block old_bb) const { - /* Generate loop upper bounds that consist of the current loop iterator, - an operator (< or <=) and an expression not involving the iterator. - If this option is not set, then the current loop iterator may appear several - times in the upper bound. See the isl manual for more details. */ - isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, true); + /* 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; + } - add_parameters_to_ivs_params (scop, ip); - isl_union_map *schedule_isl = generate_isl_schedule (scop); - isl_ast_build *context_isl = generate_isl_context (scop); - context_isl = set_options (context_isl, schedule_isl); - isl_union_map *dependences = NULL; - if (flag_loop_parallelize_all) - { - dependences = scop_get_dependences (scop); - context_isl = - isl_ast_build_set_before_each_for (context_isl, ast_build_before_for, - dependences); - } - isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl, - schedule_isl); - if(dependences) - isl_union_map_free (dependences); - isl_ast_build_free (context_isl); - return ast_isl; -} + if (dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)) + return true; -/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for - the given SCOP. Return true if code generation succeeded. + 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. + FIXME: Verify if this is true. */ + if (phi_uses_name (old_bb, old_name)) + return true; + } + return false; +} - FIXME: This is not yet a full implementation of the code generator - with ISL ASTs. Generation of GIMPLE code has to be completed. */ +/* 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. */ -bool -graphite_regenerate_ast_isl (scop_p scop) +tree +translate_isl_ast_to_gimple::get_rename (basic_block new_bb, + tree old_name, + basic_block old_bb, + bool loop_phi) const { - loop_p context_loop; - sese_info_p region = scop->scop_info; - ifsese if_region = NULL; - isl_ast_node *root_node; - ivs_params ip; + gcc_assert (TREE_CODE (old_name) == SSA_NAME); + vec *renames = region->rename_map->get (old_name); - timevar_push (TV_GRAPHITE_CODE_GEN); - root_node = scop_to_isl_ast (scop, ip); + if (!renames || renames->is_empty ()) + return NULL_TREE; - if (dump_file && (dump_flags & TDF_DETAILS)) + if (1 == renames->length ()) { - fprintf (dump_file, "\nISL AST generated by ISL: \n"); - print_isl_ast_node (dump_file, root_node, scop->isl_context); - fprintf (dump_file, "\n"); + 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; } - recompute_all_dominators (); - graphite_verify (); + /* 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)); - if_region = move_sese_in_condition (region); - region->if_region = if_region; - recompute_all_dominators (); + /* Defined in the same basic block as used. */ + if (t2_bb == new_bb) + return t2; - context_loop = region->region.entry->src->loop_father; + /* 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; + } + } + + return t1; +} + +/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). + When OLD_NAME and EXPR are the same we assert. */ + +void +translate_isl_ast_to_gimple::set_rename (tree old_name, tree expr) +{ + if (dump_file) + { + 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); + } + + if (old_name == expr) + return; + + vec *renames = region->rename_map->get (old_name); + + if (renames) + renames->safe_push (expr); + else + { + vec 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. */ + +void +translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq) +{ + 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 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)) + 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. */ + +void +translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr, + vec *vec_ssa) +{ + + /* 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); + } +} + +/* This is abridged version of the function: + tree.c:substitute_in_expr (tree exp, tree f, tree r). */ + +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. */ + +tree +translate_isl_ast_to_gimple::rename_all_uses (tree new_expr, basic_block new_bb, + basic_block old_bb) +{ + auto_vec ssa_names; + collect_all_ssa_names (new_expr, &ssa_names); + tree t; + int i; + FOR_EACH_VEC_ELT (ssa_names, i, t) + if (tree r = get_rename (new_bb, t, old_bb, false)) + new_expr = substitute_ssa_name (new_expr, t, r); + + return new_expr; +} + +/* For ops which are scev_analyzeable, we can regenerate a new name from +its scalar evolution around LOOP. */ + +tree +translate_isl_ast_to_gimple:: +get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop, + basic_block new_bb, basic_block old_bb, + vec iv_map) +{ + 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)) + { + codegen_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)) + { + codegen_error = true; + return build_zero_cst (TREE_TYPE (old_name)); + } + + /* We should check all the operands and all of them should dominate the use at + new_expr. */ + if (TREE_CODE (new_expr) == SSA_NAME) + { + basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (new_expr)); + if (bb && !dominated_by_p (CDI_DOMINATORS, new_bb, bb)) + { + /* FIXME: Remove if bootstrap passes. */ + codegen_error = true; + gcc_unreachable (); + return build_zero_cst (TREE_TYPE (old_name)); + } + } + + new_expr = rename_all_uses (new_expr, new_bb, old_bb); + /* We should check all the operands and all of them should dominate the use at + new_expr. */ + if (TREE_CODE (new_expr) == SSA_NAME) + { + basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (new_expr)); + if (bb && !dominated_by_p (CDI_DOMINATORS, new_bb, bb)) + { + /* FIXME: Remove if bootstrap passes. */ + codegen_error = true; + gcc_unreachable (); + return build_zero_cst (TREE_TYPE (old_name)); + } + } + + /* 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 + substitution map RENAME_MAP, inserting the gimplification code at + GSI_TGT, for the translation REGION, with the original copied + statement in LOOP, and using the induction variable renaming map + IV_MAP. Returns true when something has been renamed. codegen_error + is set when the code generation cannot continue. */ + +bool +translate_isl_ast_to_gimple::rename_uses (gimple *copy, + gimple_stmt_iterator *gsi_tgt, + basic_block old_bb, + loop_p loop, vec iv_map) +{ + bool changed = false; + + if (is_gimple_debug (copy)) + { + if (gimple_debug_bind_p (copy)) + gimple_debug_bind_reset_value (copy); + else if (gimple_debug_source_bind_p (copy)) + return false; + else + gcc_unreachable (); + + 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); + + 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; + tree new_expr = get_rename (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) + { + tree var = create_tmp_var (type_old_name, "var"); + + 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_earliest (stmts); + } + + replace_exp (use_p, new_expr); + continue; + } + + gimple_seq stmts; + new_expr = get_rename_from_scev (old_name, &stmts, loop, gimple_bb (copy), + old_bb, iv_map); + if (!new_expr || codegen_error_p ()) + return false; + + if (dump_file) + { + fprintf (dump_file, "\n[codegen] not in rename map, scev: "); + print_generic_expr (dump_file, new_expr, 0); + } + + gsi_insert_earliest (stmts); + replace_exp (use_p, new_expr); + + if (TREE_CODE (new_expr) == INTEGER_CST + && is_gimple_assign (copy)) + { + tree rhs = gimple_assign_rhs1 (copy); + + if (TREE_CODE (rhs) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (rhs); + } + + set_rename (old_name, new_expr); + } + + 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. */ + +basic_block +translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb, + basic_block old_bb) const +{ + vec *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; +} + +/* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true + when we want to rename an OP within a loop PHI instruction. */ + +tree +translate_isl_ast_to_gimple:: +get_new_name (basic_block new_bb, tree op, + basic_block old_bb, bool loop_phi) const +{ + /* For constants the names are the same. */ + 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 (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 +get_edges (basic_block bb) +{ + std::pair 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 +translate_isl_ast_to_gimple:: +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, + 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 (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. */ + +bool +translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb, + basic_block new_bb) +{ + 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); + copy_loop_phi_args (phi, ibp_old_bb, new_phi, ibp_new_bb, 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 (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 +translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb, + basic_block new_bb, + 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); + + tree old_name = gimple_phi_arg_def (phi, 0); + tree new_name = get_new_name (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. 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); + + 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. */ + +bool +translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb, + basic_block new_bb) +{ + 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, 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. */ + +bool +translate_isl_ast_to_gimple:: +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) +{ + 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 (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 *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 +translate_isl_ast_to_gimple::copy_cond_phi_args (gphi *phi, gphi *new_phi, + vec iv_map, + 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 (new_bb, old_name, old_bb, false); + old_phi_args[i] = old_name; + if (new_name) + { + new_phi_args [i] = new_name; + continue; + } + + /* If the phi-arg was a parameter. */ + 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; + tree new_expr = get_rename_from_scev (old_name, &stmts, loop, new_bb, + old_bb, iv_map); + if (codegen_error_p ()) + 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); + 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 (); + //add_phi_arg (new_phi, old_name, new_e, get_loc (old_name)); + 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); +} + +/* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block + containing phi nodes coming from two predecessors, and none of them are back + edges. */ + +bool +translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb, + basic_block new_bb, + vec iv_map) +{ + + 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); + + if (!copy_cond_phi_args (phi, new_phi, iv_map, 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. */ + +void +translate_isl_ast_to_gimple::set_rename_for_each_def (gimple *stmt) +{ + 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); + } +} + +/* Duplicates the statements of basic block BB into basic block NEW_BB + and compute the new induction variables according to the IV_MAP. + CODEGEN_ERROR is set when the code generation cannot continue. */ + +bool +translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb, + basic_block new_bb, + vec iv_map) +{ + /* Iterator poining to the place where new statement (s) will be inserted. */ + gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb); + + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (!should_copy_to_new_region (stmt, region)) + continue; + + /* Create a new copy of STMT and duplicate STMT's virtual + operands. */ + 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); + + /* Crete new names for each def in the copied stmt. */ + set_rename_for_each_def (copy); + + loop_p loop = bb->loop_father; + if (rename_uses (copy, &gsi_tgt, bb, loop, iv_map)) + { + fold_stmt_inplace (&gsi_tgt); + gcc_assert (gsi_stmt (gsi_tgt) == copy); + } + + if (codegen_error_p ()) + return false; + + update_stmt (copy); + } + + return true; +} + +/* Copies BB and includes in the copied BB all the statements that can + be reached following the use-def chains from the memory accesses, + and returns the next edge following this new block. codegen_error is + set when the code generation cannot continue. */ + +edge +translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb, + edge next_e, + vec iv_map) +{ + int num_phis = number_of_phi_nodes (bb); + + if (region->copied_bb_map->get (bb)) + { + /* FIXME: we should be able to handle phi nodes with args coming from + outside the region. */ + if (num_phis) + { + codegen_error = true; + return NULL; + } + } + + basic_block new_bb = split_edge (next_e); + if (num_phis > 0 && bb_contains_loop_phi_nodes (bb)) + { + basic_block phi_bb = next_e->dest->loop_father->header; + + /* 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_error = true; + return NULL; + } + + if (dump_file) + fprintf (dump_file, "\n[codegen] bb_%d contains loop phi nodes", + bb->index); + if (!copy_loop_phi_nodes (bb, phi_bb)) + { + codegen_error = 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 *bbs = region->copied_bb_map->get (old_loop_bb); + if (!bbs || bbs->length () != 1) + { + codegen_error = 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)) + { + codegen_error = 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)) + { + codegen_error = true; + return NULL; + } + } + + if (dump_file) + fprintf (dump_file, "\n[codegen] copying from bb_%d to bb_%d", + bb->index, new_bb->index); + + vec *copied_bbs = region->copied_bb_map->get (bb); + if (copied_bbs) + copied_bbs->safe_push (new_bb); + else + { + vec 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)) + { + codegen_error = true; + return NULL; + } + + return single_succ_edge (new_bb); +} + +/* 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 iv_map; + if (bb_contains_loop_phi_nodes (new_bb)) + copy_loop_phi_args (old_phi, ibp_old_bb, new_phi, + ibp_new_bb, false); + else if (bb_contains_loop_close_phi_nodes (new_bb)) + copy_loop_close_phi_args (old_bb, new_bb, false); + else if (!copy_cond_phi_args (old_phi, new_phi, iv_map, 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 +translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file, + __isl_keep isl_ast_node *node, + __isl_keep isl_ctx *ctx) const +{ + isl_printer *prn = isl_printer_to_file (ctx, file); + prn = isl_printer_set_output_format (prn, ISL_FORMAT_C); + prn = isl_printer_print_ast_node (prn, node); + prn = isl_printer_print_str (prn, "\n"); + isl_printer_free (prn); +} + +/* Add ISL's parameter identifiers and corresponding trees to ivs_params. */ + +void +translate_isl_ast_to_gimple::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 == 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] = region->params[i]; + } +} + + +/* Generates a build, which specifies the constraints on the parameters. */ + +__isl_give isl_ast_build * +translate_isl_ast_to_gimple::generate_isl_context (scop_p scop) +{ + isl_set *context_isl = isl_set_params (isl_set_copy (scop->param_context)); + return isl_ast_build_from_context (context_isl); +} + +/* Get the maximal number of schedule dimensions in the scop SCOP. */ + +int +translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop) +{ + int i; + poly_bb_p pbb; + int schedule_dims = 0; + + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) + { + int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out); + if (pbb_schedule_dims > schedule_dims) + schedule_dims = pbb_schedule_dims; + } + + return schedule_dims; +} + +/* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions. + + For schedules with different dimensionality, the isl AST generator can not + define an order and will just randomly choose an order. The solution to this + problem is to extend all schedules to the maximal number of schedule + dimensions (using '0's for the remaining values). */ + +__isl_give isl_map * +translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map *schedule, + int nb_schedule_dims) +{ + int tmp_dims = isl_map_dim (schedule, isl_dim_out); + schedule = + isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims); + isl_val *zero = + isl_val_int_from_si (isl_map_get_ctx (schedule), 0); + int i; + for (i = tmp_dims; i < nb_schedule_dims; i++) + { + schedule + = isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero)); + } + isl_val_free (zero); + return schedule; +} + +/* Generates a schedule, which specifies an order used to + visit elements in a domain. */ + +__isl_give isl_union_map * +translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop) +{ + int nb_schedule_dims = get_max_schedule_dimensions (scop); + int i; + poly_bb_p pbb; + isl_union_map *schedule_isl = + isl_union_map_empty (isl_set_get_space (scop->param_context)); + + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) + { + /* Dead code elimination: when the domain of a PBB is empty, + don't generate code for the PBB. */ + if (isl_set_is_empty (pbb->domain)) + continue; + + isl_map *bb_schedule = isl_map_copy (pbb->transformed); + bb_schedule = isl_map_intersect_domain (bb_schedule, + isl_set_copy (pbb->domain)); + bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims); + schedule_isl + = isl_union_map_union (schedule_isl, + isl_union_map_from_map (bb_schedule)); + } + return schedule_isl; +} + +/* This method is executed before the construction of a for node. */ +__isl_give isl_id * +ast_build_before_for (__isl_keep isl_ast_build *build, void *user) +{ + isl_union_map *dependences = (isl_union_map *) user; + ast_build_info *for_info = XNEW (struct ast_build_info); + isl_union_map *schedule = isl_ast_build_get_schedule (build); + isl_space *schedule_space = isl_ast_build_get_schedule_space (build); + int dimension = isl_space_dim (schedule_space, isl_dim_out); + for_info->is_parallelizable = + !carries_deps (schedule, dependences, dimension); + isl_union_map_free (schedule); + isl_space_free (schedule_space); + isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info); + return id; +} + +/* Set the separate option for all dimensions. + This helps to reduce control overhead. */ + +__isl_give isl_ast_build * +translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build *control, + __isl_keep isl_union_map *schedule) +{ + isl_ctx *ctx = isl_union_map_get_ctx (schedule); + isl_space *range_space = isl_space_set_alloc (ctx, 0, 1); + range_space = + isl_space_set_tuple_name (range_space, isl_dim_set, "separate"); + isl_union_set *range = + isl_union_set_from_set (isl_set_universe (range_space)); + isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule)); + domain = isl_union_set_universe (domain); + isl_union_map *options = isl_union_map_from_domain_and_range (domain, range); + return isl_ast_build_set_options (control, options); +} + +/* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */ + +__isl_give isl_ast_node * +translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop, ivs_params &ip) +{ + /* Generate loop upper bounds that consist of the current loop iterator, an + operator (< or <=) and an expression not involving the iterator. If this + option is not set, then the current loop iterator may appear several times + in the upper bound. See the isl manual for more details. */ + isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, true); + + add_parameters_to_ivs_params (scop, ip); + isl_union_map *schedule_isl = generate_isl_schedule (scop); + isl_ast_build *context_isl = generate_isl_context (scop); + context_isl = set_options (context_isl, schedule_isl); + isl_union_map *dependences = NULL; + if (flag_loop_parallelize_all) + { + dependences = scop_get_dependences (scop); + context_isl = + isl_ast_build_set_before_each_for (context_isl, ast_build_before_for, + dependences); + } + isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl, + schedule_isl); + if (dependences) + isl_union_map_free (dependences); + isl_ast_build_free (context_isl); + return ast_isl; +} + +/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for + the given SCOP. Return true if code generation succeeded. + + FIXME: This is not yet a full implementation of the code generator + with ISL ASTs. Generation of GIMPLE code has to be completed. */ + +bool +graphite_regenerate_ast_isl (scop_p scop) +{ + sese_info_p region = scop->scop_info; + translate_isl_ast_to_gimple t (region); + + ifsese if_region = NULL; + isl_ast_node *root_node; + ivs_params ip; + + timevar_push (TV_GRAPHITE_CODE_GEN); + root_node = t.scop_to_isl_ast (scop, ip); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nISL AST generated by ISL: \n"); + t.print_isl_ast_node (dump_file, root_node, scop->isl_context); + } + + recompute_all_dominators (); + graphite_verify (); + + if_region = move_sese_in_condition (region); + region->if_region = if_region; + recompute_all_dominators (); + + loop_p context_loop = region->region.entry->src->loop_father; + + edge e = single_succ_edge (if_region->true_region->region.entry->dest); + basic_block bb = split_edge (e); - translate_isl_ast_to_gimple t(region); - edge e = single_succ_edge (if_region->true_region->region.entry->dest); - basic_block bb = split_edge (e); /* Update the true_region exit edge. */ region->if_region->true_region->region.exit = single_succ_edge (bb); @@ -1196,8 +2964,8 @@ graphite_regenerate_ast_isl (scop_p scop) if (t.codegen_error_p ()) { if (dump_file) - fprintf (dump_file, "\n[codegen] unsuccessful, " - "reverting back to the original code."); + fprintf (dump_file, "\n[codegen] unsuccessful," + " reverting back to the original code."); set_ifsese_condition (if_region, integer_zero_node); } else @@ -1219,8 +2987,8 @@ graphite_regenerate_ast_isl (scop_p scop) graphite_verify (); } else if (dump_file) - fprintf (dump_file, "\n[codegen] unsuccessful in translating " - "pending phis, reverting back to the original code."); + fprintf (dump_file, "\n[codegen] unsuccessful in translating" + " pending phis, reverting back to the original code."); } free (if_region->true_region); @@ -1246,4 +3014,5 @@ graphite_regenerate_ast_isl (scop_p scop) return !t.codegen_error_p (); } + #endif /* HAVE_isl */ diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index b5298d7e0a2..e42b9bf9c41 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -1717,9 +1717,9 @@ build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt, gimple *def_stmt = SSA_NAME_DEF_STMT (use); if (gimple_bb (def_stmt) != gimple_bb (use_stmt)) { - DEBUG_PRINT (dp << "Adding scalar read:\n"; + DEBUG_PRINT (dp << "\nAdding scalar read:"; print_generic_expr (dump_file, use, 0); - dp << "From stmt:\n"; + dp << "\nFrom stmt:"; print_gimple_stmt (dump_file, use_stmt, 0, 0)); reads->safe_push (std::make_pair (use_stmt, use)); } diff --git a/gcc/sese.c b/gcc/sese.c index 5aa558b88ac..94fcc114499 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -25,14 +25,11 @@ 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" #include "tree-pretty-print.h" #include "fold-const.h" -#include "gimple-fold.h" -#include "tree-eh.h" #include "gimplify.h" #include "gimple-iterator.h" #include "gimple-pretty-print.h" @@ -43,7 +40,6 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "tree-data-ref.h" #include "tree-scalar-evolution.h" -#include "value-prof.h" #include "sese.h" #include "tree-ssa-propagate.h" @@ -178,7 +174,8 @@ sese_bad_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb, are not marked as liveouts. */ static void -sese_reset_debug_liveouts_bb (sese_info_p region, bitmap liveouts, basic_block bb) +sese_reset_debug_liveouts_bb (sese_info_p region, bitmap liveouts, + basic_block bb) { gimple_stmt_iterator bsi; ssa_op_iter iter; @@ -317,1541 +314,6 @@ sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb, update_ssa (TODO_update_ssa); } -/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ - -edge -get_true_edge_from_guard_bb (basic_block bb) -{ - edge e; - edge_iterator ei; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->flags & EDGE_TRUE_VALUE) - return e; - - gcc_unreachable (); - return NULL; -} - -/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ - -edge -get_false_edge_from_guard_bb (basic_block bb) -{ - edge e; - edge_iterator ei; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (!(e->flags & EDGE_TRUE_VALUE)) - return e; - - gcc_unreachable (); - return NULL; -} - -/* 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_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); - vec *renames = rename_map->get (old_name); - - 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). - When OLD_NAME and EXPR are the same we assert. */ - -static void -set_rename (tree old_name, tree expr, sese_info_p region) -{ - if (dump_file) - { - 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); - } - - if (old_name == expr) - return; - - vec *renames = region->rename_map->get (old_name); - - if (renames) - renames->safe_push (expr); - else - { - vec 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 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 *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 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 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 - substitution map RENAME_MAP, inserting the gimplification code at - GSI_TGT, for the translation REGION, with the original copied - statement in LOOP, and using the induction variable renaming map - IV_MAP. Returns true when something has been renamed. GLOOG_ERROR - is set when the code generation cannot continue. */ - -static bool -rename_uses (gimple *copy, gimple_stmt_iterator *gsi_tgt, - basic_block old_bb, sese_info_p region, - loop_p loop, vec iv_map, bool *gloog_error) -{ - bool changed = false; - - if (is_gimple_debug (copy)) - { - if (gimple_debug_bind_p (copy)) - gimple_debug_bind_reset_value (copy); - else if (gimple_debug_source_bind_p (copy)) - return false; - else - gcc_unreachable (); - - 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); - - 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; - 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) - { - tree var = create_tmp_var (type_old_name, "var"); - - 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_earliest (stmts, region); - } - - replace_exp (use_p, new_expr); - continue; - } - - 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; - - if (dump_file) - { - fprintf (dump_file, "\n[codegen] not in rename map, scev: "); - print_generic_expr (dump_file, new_expr, 0); - } - - gsi_insert_earliest (stmts, region); - replace_exp (use_p, new_expr); - - if (TREE_CODE (new_expr) == INTEGER_CST - && is_gimple_assign (copy)) - { - tree rhs = gimple_assign_rhs1 (copy); - - if (TREE_CODE (rhs) == ADDR_EXPR) - recompute_tree_invariant_for_addr_expr (rhs); - } - - 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 *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 -get_edges (basic_block bb) -{ - std::pair 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 (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 *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 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 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 bool -graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, - vec iv_map, sese_info_p region, - bool *gloog_error) -{ - /* Iterator poining to the place where new statement (s) will be inserted. */ - gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb); - - for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); - gsi_next (&gsi)) - { - gimple *stmt = gsi_stmt (gsi); - if (!should_copy_to_new_region (stmt, region)) - continue; - - /* Create a new copy of STMT and duplicate STMT's virtual - operands. */ - 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); - - /* Crete new names for each def in the copied stmt. */ - set_rename_for_each_def (copy, region); - - loop_p loop = bb->loop_father; - if (rename_uses (copy, &gsi_tgt, bb, region, loop, iv_map, gloog_error)) - { - 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 - be reached following the use-def chains from the memory accesses, - and returns the next edge following this new block. GLOOG_ERROR is - set when the code generation cannot continue. */ - -edge -copy_bb_and_scalar_dependences (basic_block bb, sese_info_p region, - edge next_e, vec iv_map, - 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); - if (num_phis > 0 && bb_contains_loop_phi_nodes (bb)) - { - basic_block phi_bb = next_e->dest->loop_father->header; - - /* 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; - } - - 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 *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 *copied_bbs = region->copied_bb_map->get (bb); - if (copied_bbs) - copied_bbs->safe_push (new_bb); - else - { - vec 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. */ struct loop * @@ -1930,7 +392,8 @@ if_region_set_false_region (ifsese if_region, sese_info_p region) { struct loop_exit *loop_exit = ggc_cleared_alloc (); - memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit)); + memcpy (loop_exit, *((struct loop_exit **) slot), + sizeof (struct loop_exit)); current_loops->exits->clear_slot (slot); hashval_t hash = htab_hash_pointer (false_edge); @@ -2071,6 +534,36 @@ invariant_in_sese_p_rec (tree t, sese_l ®ion, bool *has_vdefs) return true; } +/* Return true when DEF can be analyzed in REGION by the scalar + evolution analyzer. */ + +bool +scev_analyzable_p (tree def, sese_l ®ion) +{ + loop_p loop; + tree scev; + tree type = TREE_TYPE (def); + + /* When Graphite generates code for a scev, the code generator + expresses the scev in function of a single induction variable. + This is unsafe for floating point computations, as it may replace + a floating point sum reduction with a multiplication. The + following test returns false for non integer types to avoid such + problems. */ + if (!INTEGRAL_TYPE_P (type) + && !POINTER_TYPE_P (type)) + return false; + + loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def)); + scev = scalar_evolution_in_region (region, loop, def); + + return !chrec_contains_undetermined (scev) + && (TREE_CODE (scev) != SSA_NAME + || !defined_in_sese_p (scev, region)) + && (tree_does_not_contain_chrecs (scev) + || evolution_function_is_affine_p (scev)); +} + /* Returns the scalar evolution of T in REGION. Every variable that is not defined in the REGION is considered a parameter. */ diff --git a/gcc/sese.h b/gcc/sese.h index bce226a6cfc..c3d4c9adae5 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -59,7 +59,6 @@ get_exit_bb (sese_l &s) } /* Returns the index of V where ELEM can be found. -1 Otherwise. */ - template int vec_find (const vec &v, const T &elem) @@ -109,21 +108,10 @@ extern sese_info_p new_sese_info (edge, edge); extern void free_sese_info (sese_info_p); extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge); extern void build_sese_loop_nests (sese_info_p); -extern edge copy_bb_and_scalar_dependences (basic_block, sese_info_p, edge, - vec , bool *); extern struct loop *outermost_loop_in_sese (sese_l &, basic_block); extern tree scalar_evolution_in_region (sese_l &, loop_p, tree); +extern bool scev_analyzable_p (tree, sese_l &); 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. */ @@ -360,34 +348,4 @@ nb_common_loops (sese_l ®ion, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2) return sese_loop_depth (region, common); } -/* Return true when DEF can be analyzed in REGION by the scalar - evolution analyzer. */ - -static inline bool -scev_analyzable_p (tree def, sese_l ®ion) -{ - loop_p loop; - tree scev; - tree type = TREE_TYPE (def); - - /* When Graphite generates code for a scev, the code generator - expresses the scev in function of a single induction variable. - This is unsafe for floating point computations, as it may replace - a floating point sum reduction with a multiplication. The - following test returns false for non integer types to avoid such - problems. */ - if (!INTEGRAL_TYPE_P (type) - && !POINTER_TYPE_P (type)) - return false; - - loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def)); - scev = scalar_evolution_in_region (region, loop, def); - - return !chrec_contains_undetermined (scev) - && (TREE_CODE (scev) != SSA_NAME - || !defined_in_sese_p (scev, region)) - && (tree_does_not_contain_chrecs (scev) - || evolution_function_is_affine_p (scev)); -} - #endif -- 2.30.2