X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fsese.c;h=bfb0276d3a8b74fb1887127a42514617de43244a;hb=e21b444cfb76b8d67c9ad45766f55730901b6957;hp=e67628e4687aa427f1c52a11a788a133e1e0ee68;hpb=2bf96dd78f10196a20c8ae90c3f1eef8c859cc91;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/sese.c b/gcc/sese.c index e67628e4687..bfb0276d3a8 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -23,25 +23,14 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "ggc.h" -#include "tree.h" -#include "rtl.h" -#include "basic-block.h" -#include "diagnostic.h" +#include "tree-pretty-print.h" #include "tree-flow.h" -#include "toplev.h" -#include "tree-dump.h" -#include "timevar.h" #include "cfgloop.h" #include "tree-chrec.h" #include "tree-data-ref.h" #include "tree-scalar-evolution.h" #include "tree-pass.h" -#include "domwalk.h" #include "value-prof.h" -#include "pointer-set.h" -#include "gimple.h" #include "sese.h" /* Print to stderr the element ELT. */ @@ -66,12 +55,12 @@ debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) return 1; } -/* Print to stderr all the elements of MAP. */ +/* Print to stderr all the elements of RENAME_MAP. */ -void -debug_rename_map (htab_t map) +DEBUG_FUNCTION void +debug_rename_map (htab_t rename_map) { - htab_traverse (map, debug_rename_map_1, NULL); + htab_traverse (rename_map, debug_rename_map_1, NULL); } /* Computes a hash function for database element ELT. */ @@ -117,7 +106,7 @@ debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) /* Print to stderr all the elements of MAP. */ -void +DEBUG_FUNCTION void debug_ivtype_map (htab_t map) { htab_traverse (map, debug_ivtype_map_1, NULL); @@ -180,7 +169,7 @@ build_sese_loop_nests (sese region) /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It can be the case that an inner loop is inserted before an outer loop. To avoid this, semi-sort once. */ - for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop0); i++) + FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop0) { if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1) break; @@ -393,122 +382,60 @@ sese_insert_phis_for_liveouts (sese region, basic_block bb, update_ssa (TODO_update_ssa); } -/* Get the definition of NAME before the SESE. Keep track of the - basic blocks that have been VISITED in a bitmap. */ +/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ -static tree -get_vdef_before_sese (sese region, tree name, sbitmap visited) +edge +get_true_edge_from_guard_bb (basic_block bb) { - unsigned i; - gimple stmt = SSA_NAME_DEF_STMT (name); - basic_block def_bb = gimple_bb (stmt); - - if (!def_bb || !bb_in_sese_p (def_bb, region)) - return name; - - if (TEST_BIT (visited, def_bb->index)) - return NULL_TREE; - - SET_BIT (visited, def_bb->index); - - switch (gimple_code (stmt)) - { - case GIMPLE_PHI: - for (i = 0; i < gimple_phi_num_args (stmt); i++) - { - tree arg = gimple_phi_arg_def (stmt, i); - tree res; - - if (gimple_bb (SSA_NAME_DEF_STMT (arg)) - && def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (arg))->index) - continue; - - res = get_vdef_before_sese (region, arg, visited); - if (res) - return res; - } - return NULL_TREE; - - case GIMPLE_ASSIGN: - case GIMPLE_CALL: - { - use_operand_p use_p = gimple_vuse_op (stmt); - tree use = USE_FROM_PTR (use_p); - - if (def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (use))->index) - RESET_BIT (visited, def_bb->index); + edge e; + edge_iterator ei; - return get_vdef_before_sese (region, use, visited); - } + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->flags & EDGE_TRUE_VALUE) + return e; - default: - return NULL_TREE; - } + gcc_unreachable (); + return NULL; } -/* Adjust a virtual phi node PHI that is placed at the end of the - generated code for SCOP: - - | if (1) - | generated code from REGION; - | else - | REGION; - - The FALSE_E edge comes from the original code, TRUE_E edge comes - from the code generated for the SCOP. */ +/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ -static void -sese_adjust_vphi (sese region, gimple phi, edge true_e) +edge +get_false_edge_from_guard_bb (basic_block bb) { - unsigned i; + edge e; + edge_iterator ei; - gcc_assert (gimple_phi_num_args (phi) == 2); + FOR_EACH_EDGE (e, ei, bb->succs) + if (!(e->flags & EDGE_TRUE_VALUE)) + return e; - for (i = 0; i < gimple_phi_num_args (phi); i++) - if (gimple_phi_arg_edge (phi, i) == true_e) - { - tree true_arg, false_arg, before_scop_arg; - sbitmap visited; - - true_arg = gimple_phi_arg_def (phi, i); - if (!SSA_NAME_IS_DEFAULT_DEF (true_arg)) - return; - - false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0); - if (SSA_NAME_IS_DEFAULT_DEF (false_arg)) - return; - - visited = sbitmap_alloc (last_basic_block); - sbitmap_zero (visited); - before_scop_arg = get_vdef_before_sese (region, false_arg, visited); - gcc_assert (before_scop_arg != NULL_TREE); - SET_PHI_ARG_DEF (phi, i, before_scop_arg); - sbitmap_free (visited); - } + gcc_unreachable (); + return NULL; } -/* Returns the expression associated to OLD_NAME in MAP. */ +/* Returns the expression associated to OLD_NAME in RENAME_MAP. */ static tree -get_rename (htab_t map, tree old_name) +get_rename (htab_t rename_map, tree old_name) { struct rename_map_elt_s tmp; PTR *slot; gcc_assert (TREE_CODE (old_name) == SSA_NAME); tmp.old_name = old_name; - slot = htab_find_slot (map, &tmp, NO_INSERT); + slot = htab_find_slot (rename_map, &tmp, NO_INSERT); if (slot && *slot) return ((rename_map_elt) *slot)->expr; - return old_name; + return NULL_TREE; } -/* Register in MAP the rename tuple (OLD_NAME, EXPR). */ +/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */ -void -set_rename (htab_t map, tree old_name, tree expr) +static void +set_rename (htab_t rename_map, tree old_name, tree expr) { struct rename_map_elt_s tmp; PTR *slot; @@ -517,7 +444,7 @@ set_rename (htab_t map, tree old_name, tree expr) return; tmp.old_name = old_name; - slot = htab_find_slot (map, &tmp, INSERT); + slot = htab_find_slot (rename_map, &tmp, INSERT); if (!slot) return; @@ -528,867 +455,114 @@ set_rename (htab_t map, tree old_name, tree expr) *slot = new_rename_map_elt (old_name, expr); } -/* Renames the expression T following the tuples (OLD_NAME, EXPR) in - the rename map M. Returns the expression T after renaming. */ - -static tree -rename_variables_in_expr (htab_t m, tree t) -{ - if (!t) - return t; - - if (TREE_CODE (t) == SSA_NAME) - return get_rename (m, t); - - switch (TREE_CODE_LENGTH (TREE_CODE (t))) - { - case 3: - TREE_OPERAND (t, 2) = rename_variables_in_expr (m, TREE_OPERAND (t, 2)); - - case 2: - TREE_OPERAND (t, 1) = rename_variables_in_expr (m, TREE_OPERAND (t, 1)); - - case 1: - TREE_OPERAND (t, 0) = rename_variables_in_expr (m, TREE_OPERAND (t, 0)); - - default: - return t; - } -} - -/* Renames all the loop->nb_iterations expressions following the - tuples (OLD_NAME, EXPR) in RENAME_MAP. */ - -void -rename_nb_iterations (htab_t rename_map) -{ - loop_iterator li; - struct loop *loop; - - FOR_EACH_LOOP (li, loop, 0) - loop->nb_iterations = rename_variables_in_expr (rename_map, - loop->nb_iterations); -} - -/* Renames all the parameters of SESE following the tuples (OLD_NAME, - EXPR) in RENAME_MAP. */ - -void -rename_sese_parameters (htab_t rename_map, sese region) -{ - int i; - tree p; - - for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++) - VEC_replace (tree, SESE_PARAMS (region), i, - rename_variables_in_expr (rename_map, p)); -} - -/* Adjusts the phi nodes in the block BB for variables defined in - SCOP_REGION and used outside the SCOP_REGION. The code generation - moves SCOP_REGION in the else clause of an "if (1)" and generates - code in the then clause: - - | if (1) - | generated code from REGION; - | else - | REGION; - - To adjust the phi nodes after the condition, the RENAME_MAP is - used. */ +/* 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. */ -void -sese_adjust_liveout_phis (sese region, htab_t rename_map, basic_block bb, - edge false_e, edge true_e) +static bool +rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt, + sese region, loop_p loop, VEC (tree, heap) *iv_map) { - gimple_stmt_iterator si; + use_operand_p use_p; + ssa_op_iter op_iter; + bool changed = false; - for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) + if (is_gimple_debug (copy)) { - unsigned i; - unsigned false_i = 0; - gimple phi = gsi_stmt (si); - tree res = gimple_phi_result (phi); - - if (!is_gimple_reg (res)) - { - sese_adjust_vphi (region, phi, true_e); - continue; - } - - for (i = 0; i < gimple_phi_num_args (phi); i++) - if (gimple_phi_arg_edge (phi, i) == false_e) - { - false_i = i; - break; - } - - for (i = 0; i < gimple_phi_num_args (phi); i++) - if (gimple_phi_arg_edge (phi, i) == true_e) - { - tree old_name = gimple_phi_arg_def (phi, false_i); - tree expr = get_rename (rename_map, old_name); - gimple_seq stmts; - - gcc_assert (old_name != expr); - - if (TREE_CODE (expr) != SSA_NAME - && is_gimple_reg (old_name)) - { - tree type = TREE_TYPE (old_name); - tree var = create_tmp_var (type, "var"); - - expr = build2 (MODIFY_EXPR, type, var, expr); - expr = force_gimple_operand (expr, &stmts, true, NULL); - gsi_insert_seq_on_edge_immediate (true_e, stmts); - } + if (gimple_debug_bind_p (copy)) + gimple_debug_bind_reset_value (copy); + else + gcc_unreachable (); - SET_PHI_ARG_DEF (phi, i, expr); - set_rename (rename_map, old_name, res); - } + return false; } -} - -/* Rename the SSA_NAMEs used in STMT and that appear in MAP. */ - -static void -rename_variables_in_stmt (gimple stmt, htab_t map, gimple_stmt_iterator *insert_gsi) -{ - ssa_op_iter iter; - use_operand_p use_p; - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) + FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_ALL_USES) { - tree use = USE_FROM_PTR (use_p); - tree expr, type_use, type_expr; + tree old_name = USE_FROM_PTR (use_p); + tree new_expr, scev; gimple_seq stmts; - if (TREE_CODE (use) != SSA_NAME) + if (TREE_CODE (old_name) != SSA_NAME + || !is_gimple_reg (old_name) + || SSA_NAME_IS_DEFAULT_DEF (old_name)) continue; - expr = get_rename (map, use); - if (use == expr) - continue; - - type_use = TREE_TYPE (use); - type_expr = TREE_TYPE (expr); - - if (type_use != type_expr - || (TREE_CODE (expr) != SSA_NAME - && is_gimple_reg (use))) + changed = true; + new_expr = get_rename (rename_map, old_name); + if (new_expr) { - tree var; + tree type_old_name = TREE_TYPE (old_name); + tree type_new_expr = TREE_TYPE (new_expr); - if (is_gimple_debug (stmt)) + if (type_old_name != type_new_expr + || (TREE_CODE (new_expr) != SSA_NAME + && is_gimple_reg (old_name))) { - if (gimple_debug_bind_p (stmt)) - gimple_debug_bind_reset_value (stmt); - else - gcc_unreachable (); - - break; - } - - var = create_tmp_var (type_use, "var"); - - if (type_use != type_expr) - expr = fold_convert (type_use, expr); - - expr = build2 (MODIFY_EXPR, type_use, var, expr); - expr = force_gimple_operand (expr, &stmts, true, NULL); - gsi_insert_seq_before (insert_gsi, stmts, GSI_SAME_STMT); - } - - replace_exp (use_p, expr); - } - - update_stmt (stmt); -} - -/* Returns true if NAME is a parameter of SESE. */ - -static bool -is_parameter (sese region, tree name) -{ - int i; - tree p; - - for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++) - if (p == name) - return true; - - return false; -} - -/* Returns true if NAME is an induction variable. */ - -static bool -is_iv (tree name) -{ - return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI; -} - -static void expand_scalar_variables_stmt (gimple, basic_block, sese, - htab_t, gimple_stmt_iterator *); -static tree -expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block, - sese, htab_t, gimple_stmt_iterator *); - -static tree -expand_scalar_variables_call (gimple stmt, basic_block bb, sese region, - htab_t map, gimple_stmt_iterator *gsi) -{ - int i, nargs = gimple_call_num_args (stmt); - VEC (tree, gc) *args = VEC_alloc (tree, gc, nargs); - tree fn_type = TREE_TYPE (gimple_call_fn (stmt)); - tree fn = gimple_call_fndecl (stmt); - tree call_expr, var, lhs; - gimple call; - - for (i = 0; i < nargs; i++) - { - tree arg = gimple_call_arg (stmt, i); - tree t = TREE_TYPE (arg); - - var = create_tmp_var (t, "var"); - arg = expand_scalar_variables_expr (t, arg, TREE_CODE (arg), NULL, - bb, region, map, gsi); - arg = build2 (MODIFY_EXPR, t, var, arg); - arg = force_gimple_operand_gsi (gsi, arg, true, NULL, - true, GSI_SAME_STMT); - VEC_quick_push (tree, args, arg); - } - - lhs = gimple_call_lhs (stmt); - var = create_tmp_var (TREE_TYPE (lhs), "var"); - call_expr = build_call_vec (fn_type, fn, args); - call = gimple_build_call_from_tree (call_expr); - var = make_ssa_name (var, call); - gimple_call_set_lhs (call, var); - gsi_insert_before (gsi, call, GSI_SAME_STMT); - - return var; -} - -/* Copies at GSI all the scalar computations on which the ssa_name OP0 - depends on in the SESE: these are all the scalar variables used in - the definition of OP0, that are defined outside BB and still in the - SESE, i.e. not a parameter of the SESE. The expression that is - returned contains only induction variables from the generated code: - MAP contains the induction variables renaming mapping, and is used - to translate the names of induction variables. */ - -static tree -expand_scalar_variables_ssa_name (tree type, tree op0, basic_block bb, - sese region, htab_t map, - gimple_stmt_iterator *gsi) -{ - gimple def_stmt; - tree new_op; + tree var = create_tmp_var (type_old_name, "var"); - if (is_parameter (region, op0) - || is_iv (op0)) - return fold_convert (type, get_rename (map, op0)); + if (type_old_name != type_new_expr) + new_expr = fold_convert (type_old_name, new_expr); - def_stmt = SSA_NAME_DEF_STMT (op0); - - /* Check whether we already have a rename for OP0. */ - new_op = get_rename (map, op0); - - if (new_op != op0 - && gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb) - return fold_convert (type, new_op); - - if (gimple_bb (def_stmt) == bb) - { - /* If the defining statement is in the basic block already - we do not need to create a new expression for it, we - only need to ensure its operands are expanded. */ - expand_scalar_variables_stmt (def_stmt, bb, region, map, gsi); - return fold_convert (type, new_op); - } - else - { - if (!gimple_bb (def_stmt) - || !bb_in_sese_p (gimple_bb (def_stmt), region)) - return fold_convert (type, new_op); - - switch (gimple_code (def_stmt)) - { - case GIMPLE_ASSIGN: - { - tree var0 = gimple_assign_rhs1 (def_stmt); - enum tree_code subcode = gimple_assign_rhs_code (def_stmt); - tree var1 = gimple_assign_rhs2 (def_stmt); - tree type = gimple_expr_type (def_stmt); - - return expand_scalar_variables_expr (type, var0, subcode, var1, bb, - region, map, gsi); - } - - case GIMPLE_CALL: - return expand_scalar_variables_call (def_stmt, bb, region, map, gsi); - - default: - gcc_unreachable (); - return new_op; - } - } -} - -/* Copies at GSI all the scalar computations on which the expression - OP0 CODE OP1 depends on in the SESE: these are all the scalar - variables used in OP0 and OP1, defined outside BB and still defined - in the SESE, i.e. not a parameter of the SESE. The expression that - is returned contains only induction variables from the generated - code: MAP contains the induction variables renaming mapping, and is - used to translate the names of induction variables. */ - -static tree -expand_scalar_variables_expr (tree type, tree op0, enum tree_code code, - tree op1, basic_block bb, sese region, - htab_t map, gimple_stmt_iterator *gsi) -{ - if (TREE_CODE_CLASS (code) == tcc_constant - || TREE_CODE_CLASS (code) == tcc_declaration) - return op0; - - /* For data references we have to duplicate also its memory - indexing. */ - if (TREE_CODE_CLASS (code) == tcc_reference) - { - switch (code) - { - case REALPART_EXPR: - case IMAGPART_EXPR: - { - tree op = TREE_OPERAND (op0, 0); - tree res = expand_scalar_variables_expr - (type, op, TREE_CODE (op), NULL, bb, region, map, gsi); - return build1 (code, type, res); - } - - case INDIRECT_REF: - { - tree old_name = TREE_OPERAND (op0, 0); - tree expr = expand_scalar_variables_ssa_name - (type, old_name, bb, region, map, gsi); - - if (TREE_CODE (expr) != SSA_NAME - && is_gimple_reg (old_name)) - { - tree type = TREE_TYPE (old_name); - tree var = create_tmp_var (type, "var"); - - expr = build2 (MODIFY_EXPR, type, var, expr); - expr = force_gimple_operand_gsi (gsi, expr, true, NULL, - true, GSI_SAME_STMT); - } - - return fold_build1 (code, type, expr); - } - - case ARRAY_REF: - { - tree op00 = TREE_OPERAND (op0, 0); - tree op01 = TREE_OPERAND (op0, 1); - tree op02 = TREE_OPERAND (op0, 2); - tree op03 = TREE_OPERAND (op0, 3); - tree base = expand_scalar_variables_expr - (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, region, - map, gsi); - tree subscript = expand_scalar_variables_expr - (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, region, - map, gsi); - - return build4 (ARRAY_REF, type, base, subscript, op02, op03); - } - - case COMPONENT_REF: - return op0; - - default: - /* The above cases should catch everything. */ - gcc_unreachable (); - } - } - - if (TREE_CODE_CLASS (code) == tcc_unary) - { - tree op0_type = TREE_TYPE (op0); - enum tree_code op0_code = TREE_CODE (op0); - tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code, - NULL, bb, region, map, gsi); - - return fold_build1 (code, type, op0_expr); - } - - if (TREE_CODE_CLASS (code) == tcc_binary - || TREE_CODE_CLASS (code) == tcc_comparison) - { - tree op0_type = TREE_TYPE (op0); - enum tree_code op0_code = TREE_CODE (op0); - tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code, - NULL, bb, region, map, gsi); - tree op1_type = TREE_TYPE (op1); - enum tree_code op1_code = TREE_CODE (op1); - tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code, - NULL, bb, region, map, gsi); - - return fold_build2 (code, type, op0_expr, op1_expr); - } - - if (code == SSA_NAME) - return expand_scalar_variables_ssa_name (type, op0, bb, region, map, gsi); - - if (code == ADDR_EXPR) - { - tree op00 = TREE_OPERAND (op0, 0); + new_expr = build2 (MODIFY_EXPR, type_old_name, var, new_expr); + new_expr = force_gimple_operand (new_expr, &stmts, true, NULL); + gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); + } - if (handled_component_p (op00) - && TREE_CODE (op00) == ARRAY_REF) - { - tree e = expand_scalar_variables_expr (TREE_TYPE (op00), op00, - TREE_CODE (op00), - NULL, bb, region, map, gsi); - return fold_build1 (code, TREE_TYPE (op0), e); + replace_exp (use_p, new_expr); + continue; } - return op0; - } - - gcc_unreachable (); - return NULL; -} - -/* Copies at the beginning of BB all the scalar computations on which - STMT depends on in the SESE: these are all the scalar variables used - in STMT, defined outside BB and still defined in the SESE, i.e. not a - parameter of the SESE. The expression that is returned contains - only induction variables from the generated code: MAP contains the - induction variables renaming mapping, and is used to translate the - names of induction variables. */ - -static void -expand_scalar_variables_stmt (gimple stmt, basic_block bb, sese region, - htab_t map, gimple_stmt_iterator *gsi) -{ - ssa_op_iter iter; - use_operand_p use_p; - - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) - { - tree use = USE_FROM_PTR (use_p); - tree type = TREE_TYPE (use); - enum tree_code code = TREE_CODE (use); - tree use_expr; - - if (!is_gimple_reg (use)) - continue; - - /* Don't expand USE if we already have a rename for it. */ - use_expr = get_rename (map, use); - if (use_expr != use) - continue; + scev = scalar_evolution_in_region (region, loop, old_name); - use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb, - region, map, gsi); - use_expr = fold_convert (type, use_expr); + /* 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. */ + gcc_assert (!chrec_contains_undetermined (scev)); - if (use_expr == use) - continue; + new_expr = chrec_apply_map (scev, iv_map); - if (is_gimple_debug (stmt)) - { - if (gimple_debug_bind_p (stmt)) - gimple_debug_bind_reset_value (stmt); - else - gcc_unreachable (); + /* 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. */ + gcc_assert (!chrec_contains_undetermined (new_expr) + && !tree_contains_chrecs (new_expr, NULL)); - break; - } + /* Replace the old_name with the new_expr. */ + new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts, + true, NULL_TREE); + gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); + replace_exp (use_p, new_expr); - if (TREE_CODE (use_expr) != SSA_NAME) + if (TREE_CODE (new_expr) == INTEGER_CST + && is_gimple_assign (copy)) { - tree var = create_tmp_var (type, "var"); + tree rhs = gimple_assign_rhs1 (copy); - use_expr = build2 (MODIFY_EXPR, type, var, use_expr); - use_expr = force_gimple_operand_gsi (gsi, use_expr, true, NULL, - true, GSI_SAME_STMT); + if (TREE_CODE (rhs) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (rhs); } - replace_exp (use_p, use_expr); - } - - update_stmt (stmt); -} - -/* Copies at the beginning of BB all the scalar computations on which - BB depends on in the SESE: these are all the scalar variables used - in BB, defined outside BB and still defined in the SESE, i.e. not a - parameter of the SESE. The expression that is returned contains - only induction variables from the generated code: MAP contains the - induction variables renaming mapping, and is used to translate the - names of induction variables. */ - -static void -expand_scalar_variables (basic_block bb, sese region, htab_t map) -{ - gimple_stmt_iterator gsi; - - for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);) - { - gimple stmt = gsi_stmt (gsi); - expand_scalar_variables_stmt (stmt, bb, region, map, &gsi); - gsi_next (&gsi); - } -} - -/* Rename all the SSA_NAMEs from block BB according to the MAP. */ - -static void -rename_variables (basic_block bb, htab_t map) -{ - gimple_stmt_iterator gsi; - gimple_stmt_iterator insert_gsi = gsi_start_bb (bb); - - for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - rename_variables_in_stmt (gsi_stmt (gsi), map, &insert_gsi); -} - -/* Remove condition from BB. */ - -static void -remove_condition (basic_block bb) -{ - gimple last = last_stmt (bb); - - if (last && gimple_code (last) == GIMPLE_COND) - { - gimple_stmt_iterator gsi = gsi_last_bb (bb); - gsi_remove (&gsi, true); - } -} - -/* 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; -} - -/* Returns true when NAME is defined in LOOP. */ - -static bool -name_defined_in_loop_p (tree name, loop_p loop) -{ - return !SSA_NAME_IS_DEFAULT_DEF (name) - && gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father == loop; -} - -/* Returns true when EXPR contains SSA_NAMEs defined in LOOP. */ - -static bool -expr_defined_in_loop_p (tree expr, loop_p loop) -{ - switch (TREE_CODE_LENGTH (TREE_CODE (expr))) - { - case 3: - return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop) - || expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop) - || expr_defined_in_loop_p (TREE_OPERAND (expr, 2), loop); - - case 2: - return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop) - || expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop); - - case 1: - return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop); - - case 0: - return TREE_CODE (expr) == SSA_NAME - && name_defined_in_loop_p (expr, loop); - - default: - return false; - } -} - -/* Returns the gimple statement that uses NAME outside the loop it is - defined in, returns NULL if there is no such loop close phi node. - An invariant of the loop closed SSA form is that the only use of a - variable, outside the loop it is defined in, is in the loop close - phi node that just follows the loop. */ - -static gimple -alive_after_loop (tree name) -{ - use_operand_p use_p; - imm_use_iterator imm_iter; - loop_p loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father; - - FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name) - { - gimple stmt = USE_STMT (use_p); - - if (gimple_code (stmt) == GIMPLE_PHI - && gimple_bb (stmt)->loop_father != loop) - return stmt; - } - - return NULL; -} - -/* Return true if a close phi has not yet been inserted for the use of - variable NAME on the single exit of LOOP. */ - -static bool -close_phi_not_yet_inserted_p (loop_p loop, tree name) -{ - gimple_stmt_iterator psi; - basic_block bb = single_exit (loop)->dest; - - for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) - if (gimple_phi_arg_def (gsi_stmt (psi), 0) == name) - return false; - - return true; -} - -/* A structure for passing parameters to add_loop_exit_phis. */ - -typedef struct alep { - loop_p loop; - VEC (rename_map_elt, heap) *new_renames; -} *alep_p; - -/* Helper function for htab_traverse in insert_loop_close_phis. */ - -static int -add_loop_exit_phis (void **slot, void *data) -{ - struct rename_map_elt_s *entry; - alep_p a; - loop_p loop; - tree expr, new_name, old_name; - bool def_in_loop_p, used_outside_p, need_close_phi_p; - gimple old_close_phi; - - if (!slot || !*slot || !data) - return 1; - - entry = (struct rename_map_elt_s *) *slot; - a = (alep_p) data; - loop = a->loop; - new_name = expr = entry->expr; - old_name = entry->old_name; - - def_in_loop_p = expr_defined_in_loop_p (expr, loop); - if (!def_in_loop_p) - return 1; - - /* Remove the old rename from the map when the expression is defined - in the loop that we're closing. */ - free (*slot); - *slot = NULL; - - if (TREE_CODE (expr) != SSA_NAME) - return 1; - - old_close_phi = alive_after_loop (old_name); - used_outside_p = (old_close_phi != NULL); - need_close_phi_p = (used_outside_p - && close_phi_not_yet_inserted_p (loop, new_name)); - - /* Insert a loop close phi node. */ - if (need_close_phi_p) - { - basic_block bb = single_exit (loop)->dest; - gimple phi = create_phi_node (new_name, bb); - tree new_res = create_new_def_for (gimple_phi_result (phi), phi, - gimple_phi_result_ptr (phi)); - - add_phi_arg (phi, new_name, single_pred_edge (bb), UNKNOWN_LOCATION); - VEC_safe_push (rename_map_elt, heap, a->new_renames, - new_rename_map_elt (gimple_phi_result (old_close_phi), - new_res)); - } - - return 1; -} - -/* Traverses MAP and removes from it all the tuples (OLD, NEW) where - NEW is defined in LOOP. Inserts on the exit of LOOP the close phi - node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in - the original code. Inserts in MAP the tuple (OLD_RES, RES). */ - -void -insert_loop_close_phis (htab_t map, loop_p loop) -{ - int i; - struct alep a; - rename_map_elt elt; - - a.loop = loop; - a.new_renames = VEC_alloc (rename_map_elt, heap, 3); - update_ssa (TODO_update_ssa); - htab_traverse (map, add_loop_exit_phis, &a); - update_ssa (TODO_update_ssa); - - for (i = 0; VEC_iterate (rename_map_elt, a.new_renames, i, elt); i++) - { - set_rename (map, elt->old_name, elt->expr); - free (elt); - } - - VEC_free (rename_map_elt, heap, a.new_renames); -} - -/* Helper structure for htab_traverse in insert_guard_phis. */ - -struct igp { - basic_block bb; - edge true_edge, false_edge; - htab_t before_guard; -}; - -/* Return the default name that is before the guard. */ - -static tree -default_before_guard (htab_t before_guard, tree old_name) -{ - tree res = get_rename (before_guard, old_name); - - if (res == old_name) - { - if (is_gimple_reg (res)) - return fold_convert (TREE_TYPE (res), integer_zero_node); - return gimple_default_def (cfun, SSA_NAME_VAR (res)); - } - - return res; -} - -/* Prepares EXPR to be a good phi argument when the phi result is - RES. Insert needed statements on edge E. */ - -static tree -convert_for_phi_arg (tree expr, tree res, edge e) -{ - tree type = TREE_TYPE (res); - - if (TREE_TYPE (expr) != type) - expr = fold_convert (type, expr); - - if (TREE_CODE (expr) != SSA_NAME - && !is_gimple_min_invariant (expr)) - { - tree var = create_tmp_var (type, "var"); - gimple_seq stmts; - - expr = build2 (MODIFY_EXPR, type, var, expr); - expr = force_gimple_operand (expr, &stmts, true, NULL); - gsi_insert_seq_on_edge_immediate (e, stmts); + set_rename (rename_map, old_name, new_expr); } - return expr; -} - -/* Helper function for htab_traverse in insert_guard_phis. */ - -static int -add_guard_exit_phis (void **slot, void *s) -{ - struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot; - struct igp *i = (struct igp *) s; - basic_block bb = i->bb; - edge true_edge = i->true_edge; - edge false_edge = i->false_edge; - tree res = entry->old_name; - tree name1 = entry->expr; - tree name2 = default_before_guard (i->before_guard, res); - gimple phi; - - /* Nothing to be merged if the name before the guard is the same as - the one after. */ - if (name1 == name2) - return 1; - - name1 = convert_for_phi_arg (name1, res, true_edge); - name2 = convert_for_phi_arg (name2, res, false_edge); - - phi = create_phi_node (res, bb); - res = create_new_def_for (gimple_phi_result (phi), phi, - gimple_phi_result_ptr (phi)); - - add_phi_arg (phi, name1, true_edge, UNKNOWN_LOCATION); - add_phi_arg (phi, name2, false_edge, UNKNOWN_LOCATION); - - entry->expr = res; - *slot = entry; - return 1; -} - -/* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1). - If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD, - with NAME1 different than NAME2, then insert in BB the phi node: - - | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))" - - if there is no tuple for OLD in BEFORE_GUARD, insert - - | RES = phi (NAME1 (on TRUE_EDGE), - | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))". - - Finally register in RENAME_MAP the tuple (OLD, RES). */ - -void -insert_guard_phis (basic_block bb, edge true_edge, edge false_edge, - htab_t before_guard, htab_t rename_map) -{ - struct igp i; - i.bb = bb; - i.true_edge = true_edge; - i.false_edge = false_edge; - i.before_guard = before_guard; - - update_ssa (TODO_update_ssa); - htab_traverse (rename_map, add_guard_exit_phis, &i); - update_ssa (TODO_update_ssa); + return changed; } -/* Create a duplicate of the basic block BB. NOTE: This does not - preserve SSA form. */ +/* Duplicates the statements of basic block BB into basic block NEW_BB + and compute the new induction variables according to the IV_MAP. */ static void -graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map) +graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, + htab_t rename_map, + VEC (tree, heap) *iv_map, sese region) { gimple_stmt_iterator gsi, gsi_tgt; + loop_p loop = bb->loop_father; gsi_tgt = gsi_start_bb (new_bb); for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) @@ -1397,8 +571,19 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map) ssa_op_iter op_iter; gimple stmt = gsi_stmt (gsi); gimple copy; + tree lhs; + + /* Do not copy labels or conditions. */ + if (gimple_code (stmt) == GIMPLE_LABEL + || gimple_code (stmt) == GIMPLE_COND) + continue; - if (gimple_code (stmt) == GIMPLE_LABEL) + /* 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)) continue; /* Create a new copy of STMT and duplicate STMT's virtual @@ -1413,11 +598,16 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map) /* Create new names for all the definitions created by COPY and add replacement mappings for each new name. */ FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS) - { - tree old_name = DEF_FROM_PTR (def_p); - tree new_name = create_new_def_for (old_name, copy, def_p); - set_rename (map, old_name, new_name); - } + { + tree old_name = DEF_FROM_PTR (def_p); + tree new_name = create_new_def_for (old_name, copy, def_p); + set_rename (rename_map, old_name, new_name); + } + + if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map)) + fold_stmt_inplace (copy); + + update_stmt (copy); } } @@ -1427,16 +617,16 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map) edge copy_bb_and_scalar_dependences (basic_block bb, sese region, - edge next_e, htab_t map) + edge next_e, VEC (tree, heap) *iv_map) { basic_block new_bb = split_edge (next_e); + htab_t rename_map = htab_create (10, rename_map_elt_info, + eq_rename_map_elts, free); next_e = single_succ_edge (new_bb); - graphite_copy_stmts_from_block (bb, new_bb, map); - remove_condition (new_bb); + graphite_copy_stmts_from_block (bb, new_bb, rename_map, iv_map, region); remove_phi_nodes (new_bb); - expand_scalar_variables (new_bb, region, map); - rename_variables (new_bb, map); + htab_delete (rename_map); return next_e; } @@ -1492,7 +682,7 @@ if_region_set_false_region (ifsese if_region, sese region) if (slot) { - struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit); + struct loop_exit *loop_exit = ggc_alloc_cleared_loop_exit (); memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit)); htab_clear_slot (current_loops->exits, slot); @@ -1600,14 +790,16 @@ scalar_evolution_in_region (sese region, loop_p loop, tree t) struct loop *def_loop; basic_block before = block_before_sese (region); + /* SCOP parameters. */ + if (TREE_CODE (t) == SSA_NAME + && !defined_in_sese_p (t, region)) + return t; + if (TREE_CODE (t) != SSA_NAME || loop_in_sese_p (loop, region)) return instantiate_scev (before, loop, analyze_scalar_evolution (loop, t)); - if (!defined_in_sese_p (t, region)) - return t; - def = SSA_NAME_DEF_STMT (t); def_loop = loop_containing_stmt (def);