diff options
Diffstat (limited to 'gcc/sese.c')
| -rw-r--r-- | gcc/sese.c | 1543 |
1 files changed, 1409 insertions, 134 deletions
@@ -25,6 +25,7 @@ along with GCC; see the file COPYING3. If not see #include "backend.h" #include "tree.h" #include "gimple.h" +#include "cfganal.h" #include "cfghooks.h" #include "tree-pass.h" #include "ssa.h" @@ -34,6 +35,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-eh.h" #include "gimplify.h" #include "gimple-iterator.h" +#include "gimple-pretty-print.h" #include "gimplify-me.h" #include "tree-cfg.h" #include "tree-ssa-loop.h" @@ -44,33 +46,6 @@ along with GCC; see the file COPYING3. If not see #include "value-prof.h" #include "sese.h" #include "tree-ssa-propagate.h" -#include "tree-hash-traits.h" - -/* Helper function for debug_rename_map. */ - -bool -debug_rename_map_1 (tree_node *const &old_name, tree_node *const &expr, - void *) -{ - fprintf (stderr, "("); - print_generic_expr (stderr, old_name, 0); - fprintf (stderr, ", "); - print_generic_expr (stderr, expr, 0); - fprintf (stderr, ")\n"); - return true; -} - -typedef hash_map<tree_ssa_name_hash, tree> rename_map_type; - - -/* Print to stderr all the elements of RENAME_MAP. */ - -DEBUG_FUNCTION void -debug_rename_map (rename_map_type *rename_map) -{ - rename_map->traverse <void *, debug_rename_map_1> (NULL); -} - /* Record LOOP as occurring in REGION. */ @@ -80,8 +55,8 @@ sese_record_loop (sese_info_p region, loop_p loop) if (sese_contains_loop (region, loop)) return; - bitmap_set_bit (SESE_LOOPS (region), loop->num); - SESE_LOOP_NEST (region).safe_push (loop); + bitmap_set_bit (region->loops, loop->num); + region->loop_nest.safe_push (loop); } /* Build the loop nests contained in REGION. Returns true when the @@ -108,16 +83,16 @@ build_sese_loop_nests (sese_info_p region) /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It can be the case that an inner loop is inserted before an outer loop. To avoid this, semi-sort once. */ - FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop0) + FOR_EACH_VEC_ELT (region->loop_nest, i, loop0) { - if (SESE_LOOP_NEST (region).length () == i + 1) + if (region->loop_nest.length () == i + 1) break; - loop1 = SESE_LOOP_NEST (region)[i + 1]; + loop1 = region->loop_nest[i + 1]; if (loop0->num > loop1->num) { - SESE_LOOP_NEST (region)[i] = loop1; - SESE_LOOP_NEST (region)[i + 1] = loop0; + region->loop_nest[i] = loop1; + region->loop_nest[i + 1] = loop0; } } } @@ -256,10 +231,13 @@ new_sese_info (edge entry, edge exit) region->region.entry = entry; region->region.exit = exit; - SESE_LOOPS (region) = BITMAP_ALLOC (NULL); - SESE_LOOP_NEST (region).create (3); - SESE_PARAMS (region).create (3); + region->loops = BITMAP_ALLOC (NULL); + region->loop_nest.create (3); + region->params.create (3); + region->rename_map = new rename_map_t; + region->copied_bb_map = new bb_map_t; region->bbs.create (3); + region->incomplete_phis.create (3); return region; } @@ -269,11 +247,28 @@ new_sese_info (edge entry, edge exit) void free_sese_info (sese_info_p region) { - if (SESE_LOOPS (region)) - SESE_LOOPS (region) = BITMAP_ALLOC (NULL); + if (region->loops) + region->loops = BITMAP_ALLOC (NULL); - SESE_PARAMS (region).release (); - SESE_LOOP_NEST (region).release (); + region->params.release (); + region->loop_nest.release (); + + for (rename_map_t::iterator it = region->rename_map->begin (); + it != region->rename_map->begin (); ++it) + (*it).second.release (); + + for (bb_map_t::iterator it = region->copied_bb_map->begin (); + it != region->copied_bb_map->begin (); ++it) + (*it).second.release (); + + delete region->rename_map; + delete region->copied_bb_map; + + region->rename_map = NULL; + region->copied_bb_map = NULL; + + region->bbs.release (); + region->incomplete_phis.release (); XDELETE (region); } @@ -312,8 +307,11 @@ sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb, update_ssa (TODO_update_ssa); sese_build_liveouts (region, liveouts); + EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi) - sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); + if (!virtual_operand_p (ssa_name (i))) + sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); + BITMAP_FREE (liveouts); update_ssa (TODO_update_ssa); @@ -351,37 +349,550 @@ get_false_edge_from_guard_bb (basic_block bb) return NULL; } -/* Returns the expression associated to OLD_NAME in RENAME_MAP. */ +/* Check if USE is defined in a basic block from where the definition of USE can + propagate from all the paths. */ + +static bool +is_loop_closed_ssa_use (basic_block bb, tree use) +{ + if (TREE_CODE (use) != SSA_NAME) + return true; + + /* We should not have a rename for virtual operands. */ + gcc_assert (!virtual_operand_p (use)); + + /* For close-phi nodes def always comes from a loop which has a back-edge. */ + if (bb_contains_loop_close_phi_nodes (bb)) + return true; + + gimple *def = SSA_NAME_DEF_STMT (use); + basic_block def_bb = gimple_bb (def); + return (!def_bb + || flow_bb_inside_loop_p (def_bb->loop_father, bb)); +} + +/* Return the number of phi nodes in BB. */ + +static int +number_of_phi_nodes (basic_block bb) +{ + int num_phis = 0; + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + num_phis++; + return num_phis; +} + +/* Return true when BB contains loop close phi nodes. */ + +bool +bb_contains_loop_close_phi_nodes (basic_block bb) +{ + return single_pred_p (bb) + && bb->loop_father != single_pred_edge (bb)->src->loop_father; +} + +/* Return true when BB contains loop phi nodes. */ + +bool +bb_contains_loop_phi_nodes (basic_block bb) +{ + gcc_assert (EDGE_COUNT (bb->preds) <= 2); + + if (bb->preds->length () == 1) + return false; + + unsigned depth = loop_depth (bb->loop_father); + + edge preds[2] = { (*bb->preds)[0], (*bb->preds)[1] }; + + if (depth > loop_depth (preds[0]->src->loop_father) + || depth > loop_depth (preds[1]->src->loop_father)) + return true; + + /* When one of the edges correspond to the same loop father and other + doesn't. */ + if (bb->loop_father != preds[0]->src->loop_father + && bb->loop_father == preds[1]->src->loop_father) + return true; + + if (bb->loop_father != preds[1]->src->loop_father + && bb->loop_father == preds[0]->src->loop_father) + return true; + + return false; +} + +/* Returns true if BB uses name in one of its PHIs. */ + +static bool +phi_uses_name (basic_block bb, tree name) +{ + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + for (unsigned i = 0; i < gimple_phi_num_args (phi); i++) + { + tree use_arg = gimple_phi_arg_def (phi, i); + if (use_arg == name) + return true; + } + } + return false; +} + +/* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The +definition should flow into use, and the use should respect the loop-closed SSA +form. */ + +static bool +is_valid_rename (tree rename, basic_block def_bb, + basic_block use_bb, bool loop_phi, + tree old_name, basic_block old_bb) +{ + /* The def of the rename must either dominate the uses or come from a + back-edge. Also the def must respect the loop closed ssa form. */ + if (!is_loop_closed_ssa_use (use_bb, rename)) + { + if (dump_file) + { + fprintf (dump_file, "\n[codegen] rename not in loop closed ssa:"); + print_generic_expr (dump_file, rename, 0); + } + return false; + } + + if (dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)) + return true; + + if (bb_contains_loop_phi_nodes (use_bb) && loop_phi) + { + /* The loop-header dominates the loop-body. */ + if (!dominated_by_p (CDI_DOMINATORS, def_bb, use_bb)) + return false; + + /* RENAME would be used in loop-phi. */ + gcc_assert (number_of_phi_nodes (use_bb)); + + /* For definitions coming from back edges, we should check that + old_name is used in a loop PHI node. */ + if (phi_uses_name (old_bb, old_name)) + return true; + } + return false; +} + +/* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in + NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME + within a loop PHI instruction. */ static tree -get_rename (rename_map_type *rename_map, tree old_name) +get_rename (rename_map_t *rename_map, basic_block new_bb, tree old_name, + basic_block old_bb, bool loop_phi) { gcc_assert (TREE_CODE (old_name) == SSA_NAME); - tree *expr = rename_map->get (old_name); - if (expr) - return *expr; + vec <tree> *renames = rename_map->get (old_name); - return NULL_TREE; + if (!renames || renames->is_empty ()) + return NULL_TREE; + + if (1 == renames->length ()) + { + tree rename = (*renames)[0]; + basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (rename)); + if (is_valid_rename (rename, bb, new_bb, loop_phi, old_name, old_bb)) + return rename; + return NULL_TREE; + } + + /* More than one renames corresponding to the old_name. Find the rename for + which the definition flows into usage at new_bb. */ + int i; + tree t1 = NULL_TREE, t2; + basic_block t1_bb = NULL; + FOR_EACH_VEC_ELT (*renames, i, t2) + { + basic_block t2_bb = gimple_bb (SSA_NAME_DEF_STMT (t2)); + + /* Defined in the same basic block as used. */ + if (t2_bb == new_bb) + return t2; + + /* NEW_BB and T2_BB are in two unrelated if-clauses. */ + if (!dominated_by_p (CDI_DOMINATORS, new_bb, t2_bb)) + continue; + + /* Compute the nearest dominator. */ + if (!t1 || dominated_by_p (CDI_DOMINATORS, t2_bb, t1_bb)) + { + t1_bb = t2_bb; + t1 = t2; + } + //if (is_valid_rename (rename, bb, new_bb, loop_phi, old_name, old_bb)) + //return rename; + } + + return t1; } -/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */ +/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). + When OLD_NAME and EXPR are the same we assert. */ static void -set_rename (rename_map_type *rename_map, tree old_name, tree expr) +set_rename (tree old_name, tree expr, sese_info_p region) { if (dump_file) { - fprintf (dump_file, "[codegen] setting rename: old_name = "); + fprintf (dump_file, "\n[codegen] setting rename: old_name = "); print_generic_expr (dump_file, old_name, 0); fprintf (dump_file, ", new_name = "); print_generic_expr (dump_file, expr, 0); - fprintf (dump_file, "\n"); } if (old_name == expr) return; - rename_map->put (old_name, expr); + vec <tree> *renames = region->rename_map->get (old_name); + + if (renames) + renames->safe_push (expr); + else + { + vec<tree> r; + r.create (2); + r.safe_push (expr); + region->rename_map->put (old_name, r); + } +} + +/* Return an iterator to the instructions comes + last in the execution order. Either GSI1 and GSI2 should belong + to the same basic block or one of their respective basic blocks + should dominate the other. */ + +gimple_stmt_iterator +later_of_the_two (gimple_stmt_iterator gsi1, gimple_stmt_iterator gsi2) +{ + basic_block bb1 = gsi_bb (gsi1); + basic_block bb2 = gsi_bb (gsi2); + + /* Find the iterator which is the latest. */ + if (bb1 == bb2) + { + /* For empty basic blocks gsis point to the end of the sequence. Since + there is no operator== defined for gimple_stmt_iterator and for gsis + not pointing to a valid statement gsi_next would assert. */ + gimple_stmt_iterator gsi = gsi1; + do { + if (gsi_stmt (gsi) == gsi_stmt (gsi2)) + return gsi2; + gsi_next (&gsi); + } while (!gsi_end_p (gsi)); + + return gsi1; + } + + /* Find the basic block closest to the basic block which defines stmt. */ + if (dominated_by_p (CDI_DOMINATORS, bb1, bb2)) + return gsi1; + + gcc_assert (dominated_by_p (CDI_DOMINATORS, bb2, bb1)); + return gsi2; +} + +/* Insert each statement from SEQ at its earliest insertion p. */ + +static void +gsi_insert_earliest (gimple_seq seq, sese_info_p region) +{ + update_modified_stmts (seq); + sese_l &codegen_region = region->if_region->true_region->region; + basic_block begin_bb = get_entry_bb (codegen_region); + + /* Inserting the gimple statements in a vector because gimple_seq behave + in strage ways when inserting the stmts from it into different basic + blocks one at a time. */ + auto_vec<gimple *, 3> stmts; + for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi); + gsi_next (&gsi)) + stmts.safe_push (gsi_stmt (gsi)); + + int i; + gimple *use_stmt; + FOR_EACH_VEC_ELT (stmts, i, use_stmt) + { + gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI); + gimple_stmt_iterator gsi_def_stmt = gsi_start_bb_nondebug (begin_bb); + + use_operand_p use_p; + ssa_op_iter op_iter; + FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, op_iter, SSA_OP_USE) + { + /* Iterator to the current def of use_p. For function parameters or + anything where def is not found, insert at the beginning of the + generated region. */ + gimple_stmt_iterator gsi_stmt = gsi_def_stmt; + + tree op = USE_FROM_PTR (use_p); + gimple *stmt = SSA_NAME_DEF_STMT (op); + if (stmt && (gimple_code (stmt) != GIMPLE_NOP)) + gsi_stmt = gsi_for_stmt (stmt); + + /* For region parameters, insert at the beginning of the generated + region. */ + if (!bb_in_sese_p (gsi_bb (gsi_stmt), codegen_region)) + { + /* The parameter should have been inserted in the parameter + map or it must have a scev. */ + gsi_stmt = gsi_def_stmt; + } + + gsi_def_stmt = later_of_the_two (gsi_stmt, gsi_def_stmt); + } + + if (!gsi_stmt (gsi_def_stmt)) + { + gimple_stmt_iterator gsi = gsi_after_labels (gsi_bb (gsi_def_stmt)); + gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT); + } + else if (gimple_code (gsi_stmt (gsi_def_stmt)) == GIMPLE_PHI) + { + gimple_stmt_iterator bsi + = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt)); + /* Insert right after the PHI statements. */ + gsi_insert_before (&bsi, use_stmt, GSI_NEW_STMT); + } + else + gsi_insert_after (&gsi_def_stmt, use_stmt, GSI_NEW_STMT); + + if (dump_file) + { + fprintf (dump_file, "\n[codegen] inserting statement: "); + print_gimple_stmt (dump_file, use_stmt, 0, TDF_VOPS | TDF_MEMSYMS); + print_loops_bb (dump_file, gimple_bb (use_stmt), 0, 3); + } + } +} + +/* Collect all the operands of NEW_EXPR by recursively visiting each + operand. */ + +static void +collect_all_ssa_names (tree new_expr, vec<tree> *vec_ssa, sese_info_p region) +{ + + /* Rename all uses in new_expr. */ + if (TREE_CODE (new_expr) == SSA_NAME) + { + vec_ssa->safe_push (new_expr); + return; + } + + /* Iterate over SSA_NAMES in NEW_EXPR. */ + for (int i = 0; i < (TREE_CODE_LENGTH (TREE_CODE (new_expr))); i++) + { + tree op = TREE_OPERAND (new_expr, i); + collect_all_ssa_names (op, vec_ssa, region); + } +} + +static tree +substitute_ssa_name (tree exp, tree f, tree r) +{ + enum tree_code code = TREE_CODE (exp); + tree op0, op1, op2, op3; + tree new_tree; + + /* We handle TREE_LIST and COMPONENT_REF separately. */ + if (code == TREE_LIST) + { + op0 = substitute_ssa_name (TREE_CHAIN (exp), f, r); + op1 = substitute_ssa_name (TREE_VALUE (exp), f, r); + if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp)) + return exp; + + return tree_cons (TREE_PURPOSE (exp), op1, op0); + } + else if (code == COMPONENT_REF) + { + tree inner; + + /* If this expression is getting a value from a PLACEHOLDER_EXPR + and it is the right field, replace it with R. */ + for (inner = TREE_OPERAND (exp, 0); + REFERENCE_CLASS_P (inner); + inner = TREE_OPERAND (inner, 0)) + ; + + /* The field. */ + op1 = TREE_OPERAND (exp, 1); + + if (TREE_CODE (inner) == PLACEHOLDER_EXPR && op1 == f) + return r; + + /* If this expression hasn't been completed let, leave it alone. */ + if (TREE_CODE (inner) == PLACEHOLDER_EXPR && !TREE_TYPE (inner)) + return exp; + + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + if (op0 == TREE_OPERAND (exp, 0)) + return exp; + + new_tree + = fold_build3 (COMPONENT_REF, TREE_TYPE (exp), op0, op1, NULL_TREE); + } + else + switch (TREE_CODE_CLASS (code)) + { + case tcc_constant: + return exp; + + case tcc_declaration: + if (exp == f) + return r; + else + return exp; + + case tcc_expression: + if (exp == f) + return r; + + /* Fall through... */ + + case tcc_exceptional: + case tcc_unary: + case tcc_binary: + case tcc_comparison: + case tcc_reference: + switch (TREE_CODE_LENGTH (code)) + { + case 0: + if (exp == f) + return r; + return exp; + + case 1: + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + if (op0 == TREE_OPERAND (exp, 0)) + return exp; + + new_tree = fold_build1 (code, TREE_TYPE (exp), op0); + break; + + case 2: + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r); + + if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)) + return exp; + + new_tree = fold_build2 (code, TREE_TYPE (exp), op0, op1); + break; + + case 3: + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r); + op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r); + + if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1) + && op2 == TREE_OPERAND (exp, 2)) + return exp; + + new_tree = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2); + break; + + case 4: + op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r); + op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r); + op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r); + op3 = substitute_ssa_name (TREE_OPERAND (exp, 3), f, r); + + if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1) + && op2 == TREE_OPERAND (exp, 2) + && op3 == TREE_OPERAND (exp, 3)) + return exp; + + new_tree + = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3)); + break; + + default: + gcc_unreachable (); + } + break; + + case tcc_vl_exp: + default: + gcc_unreachable (); + } + + TREE_READONLY (new_tree) |= TREE_READONLY (exp); + + if (code == INDIRECT_REF || code == ARRAY_REF || code == ARRAY_RANGE_REF) + TREE_THIS_NOTRAP (new_tree) |= TREE_THIS_NOTRAP (exp); + + return new_tree; +} + +/* Rename all the operands of NEW_EXPR by recursively visiting each operand. */ + +static tree +rename_all_uses (tree new_expr, basic_block new_bb, basic_block old_bb, + sese_info_p region) +{ + vec<tree> ssa_names; + ssa_names.create (2); + collect_all_ssa_names (new_expr, &ssa_names, region); + tree t; + int i; + FOR_EACH_VEC_ELT (ssa_names, i, t) + { + if (tree r = get_rename (region->rename_map, new_bb, t, old_bb, false)) + new_expr = substitute_ssa_name (new_expr, t, r); + /* else + return NULL_TREE;*/ + } + + return new_expr; +} + +static tree +get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop, + basic_block new_bb, basic_block old_bb, + vec<tree> iv_map, sese_info_p region, bool *gloog_error) +{ + tree scev = scalar_evolution_in_region (region->region, loop, old_name); + + /* At this point we should know the exact scev for each + scalar SSA_NAME used in the scop: all the other scalar + SSA_NAMEs should have been translated out of SSA using + arrays with one element. */ + tree new_expr; + if (chrec_contains_undetermined (scev)) + { + *gloog_error = true; + return build_zero_cst (TREE_TYPE (old_name)); + } + + new_expr = chrec_apply_map (scev, iv_map); + + /* The apply should produce an expression tree containing + the uses of the new induction variables. We should be + able to use new_expr instead of the old_name in the newly + generated loop nest. */ + if (chrec_contains_undetermined (new_expr) + || tree_contains_chrecs (new_expr, NULL)) + { + *gloog_error = true; + return build_zero_cst (TREE_TYPE (old_name)); + } + + new_expr = rename_all_uses (new_expr, new_bb, old_bb, region); + + /* Replace the old_name with the new_expr. */ + return force_gimple_operand (unshare_expr (new_expr), stmts, + true, NULL_TREE); } /* Renames the scalar uses of the statement COPY, using the @@ -392,13 +903,10 @@ set_rename (rename_map_type *rename_map, tree old_name, tree expr) is set when the code generation cannot continue. */ static bool -rename_uses (gimple *copy, rename_map_type *rename_map, - gimple_stmt_iterator *gsi_tgt, - sese_info_p region, loop_p loop, vec<tree> iv_map, - bool *gloog_error) +rename_uses (gimple *copy, gimple_stmt_iterator *gsi_tgt, + basic_block old_bb, sese_info_p region, + loop_p loop, vec<tree> iv_map, bool *gloog_error) { - use_operand_p use_p; - ssa_op_iter op_iter; bool changed = false; if (is_gimple_debug (copy)) @@ -413,23 +921,43 @@ rename_uses (gimple *copy, rename_map_type *rename_map, return false; } + if (dump_file) + { + fprintf (dump_file, "\n[codegen] renaming uses of stmt: "); + print_gimple_stmt (dump_file, copy, 0, 0); + } + + use_operand_p use_p; + ssa_op_iter op_iter; FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_USE) { tree old_name = USE_FROM_PTR (use_p); - tree new_expr, scev; - gimple_seq stmts; + + if (dump_file) + { + fprintf (dump_file, "\n[codegen] renaming old_name = "); + print_generic_expr (dump_file, old_name, 0); + } if (TREE_CODE (old_name) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (old_name)) continue; changed = true; - new_expr = get_rename (rename_map, old_name); + tree new_expr = get_rename (region->rename_map, gsi_tgt->bb, old_name, + old_bb, false); + if (new_expr) { tree type_old_name = TREE_TYPE (old_name); tree type_new_expr = TREE_TYPE (new_expr); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] from rename_map: new_name = "); + print_generic_expr (dump_file, new_expr, 0); + } + if (type_old_name != type_new_expr || TREE_CODE (new_expr) != SSA_NAME) { @@ -438,44 +966,28 @@ rename_uses (gimple *copy, rename_map_type *rename_map, if (!useless_type_conversion_p (type_old_name, type_new_expr)) new_expr = fold_convert (type_old_name, new_expr); + gimple_seq stmts; new_expr = force_gimple_operand (new_expr, &stmts, true, var); - gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); + gsi_insert_earliest (stmts, region); } replace_exp (use_p, new_expr); continue; } - scev = scalar_evolution_in_region (region->region, loop, old_name); - - /* At this point we should know the exact scev for each - scalar SSA_NAME used in the scop: all the other scalar - SSA_NAMEs should have been translated out of SSA using - arrays with one element. */ - if (chrec_contains_undetermined (scev)) - { - *gloog_error = true; - new_expr = build_zero_cst (TREE_TYPE (old_name)); - } - else - new_expr = chrec_apply_map (scev, iv_map); + gimple_seq stmts; + new_expr = get_rename_from_scev (old_name, &stmts, loop, gimple_bb (copy), + old_bb, iv_map, region, gloog_error); + if (!new_expr || *gloog_error) + return false; - /* The apply should produce an expression tree containing - the uses of the new induction variables. We should be - able to use new_expr instead of the old_name in the newly - generated loop nest. */ - if (chrec_contains_undetermined (new_expr) - || tree_contains_chrecs (new_expr, NULL)) + if (dump_file) { - *gloog_error = true; - new_expr = build_zero_cst (TREE_TYPE (old_name)); + fprintf (dump_file, "\n[codegen] not in rename map, scev: "); + print_generic_expr (dump_file, new_expr, 0); } - else - /* Replace the old_name with the new_expr. */ - new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts, - true, NULL_TREE); - gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); + gsi_insert_earliest (stmts, region); replace_exp (use_p, new_expr); if (TREE_CODE (new_expr) == INTEGER_CST @@ -487,73 +999,726 @@ rename_uses (gimple *copy, rename_map_type *rename_map, recompute_tree_invariant_for_addr_expr (rhs); } - set_rename (rename_map, old_name, new_expr); + set_rename (old_name, new_expr, region); } return changed; } +/* Returns a basic block that could correspond to where a constant was defined + in the original code. In the original code OLD_BB had the definition, we + need to find which basic block out of the copies of old_bb, in the new + region, should a definition correspond to if it has to reach BB. */ + +static basic_block +get_def_bb_for_const (sese_info_p region, basic_block bb, basic_block old_bb) +{ + vec <basic_block> *bbs = region->copied_bb_map->get (old_bb); + + if (!bbs || bbs->is_empty ()) + return NULL; + + if (1 == bbs->length ()) + return (*bbs)[0]; + + int i; + basic_block b1 = NULL, b2; + FOR_EACH_VEC_ELT (*bbs, i, b2) + { + if (b2 == bb) + return bb; + + /* BB and B2 are in two unrelated if-clauses. */ + if (!dominated_by_p (CDI_DOMINATORS, bb, b2)) + continue; + + /* Compute the nearest dominator. */ + if (!b1 || dominated_by_p (CDI_DOMINATORS, b2, b1)) + b1 = b2; + } + + gcc_assert (b1); + return b1; +} + +/* LOOP_PHI is true when we want to rename an OP within a loop PHI + instruction. */ + +static tree +get_new_name (sese_info_p region, basic_block new_bb, tree op, + basic_block old_bb, bool loop_phi) +{ + if (TREE_CODE (op) == INTEGER_CST + || TREE_CODE (op) == REAL_CST + || TREE_CODE (op) == COMPLEX_CST + || TREE_CODE (op) == VECTOR_CST) + return op; + + return get_rename (region->rename_map, new_bb, op, old_bb, loop_phi); +} + +/* Return a debug location for OP. */ + +static location_t +get_loc (tree op) +{ + location_t loc = UNKNOWN_LOCATION; + + if (TREE_CODE (op) == SSA_NAME) + loc = gimple_location (SSA_NAME_DEF_STMT (op)); + return loc; +} + +/* Returns the incoming edges of basic_block BB in the pair. The first edge is + the init edge (from outside the loop) and the second one is the back edge + from the same loop. */ + +std::pair<edge, edge> +get_edges (basic_block bb) +{ + std::pair<edge, edge> edges; + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->preds) + if (bb->loop_father != e->src->loop_father) + edges.first = e; + else + edges.second = e; + return edges; +} + +/* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI + must be found unless they can be POSTPONEd for later. */ + +void +copy_loop_phi_args (gphi *old_phi, init_back_edge_pair_t &ibp_old_bb, + gphi *new_phi, init_back_edge_pair_t &ibp_new_bb, + sese_info_p region, bool postpone) +{ + gcc_assert (gimple_phi_num_args (old_phi) == gimple_phi_num_args (new_phi)); + + basic_block new_bb = gimple_bb (new_phi); + for (unsigned i = 0; i < gimple_phi_num_args (old_phi); i++) + { + edge e; + if (gimple_phi_arg_edge (old_phi, i) == ibp_old_bb.first) + e = ibp_new_bb.first; + else + e = ibp_new_bb.second; + + tree old_name = gimple_phi_arg_def (old_phi, i); + tree new_name = get_new_name (region, new_bb, old_name, + gimple_bb (old_phi), true); + if (new_name) + { + add_phi_arg (new_phi, new_name, e, get_loc (old_name)); + continue; + } + + gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name); + if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP) + /* If the phi arg was a function arg, or wasn't defined, just use the old + name. */ + add_phi_arg (new_phi, old_name, e, get_loc (old_name)); + else if (postpone) + { + /* Postpone code gen for later for those back-edges we don't have the + names yet. */ + region->incomplete_phis.safe_push (std::make_pair (old_phi, new_phi)); + if (dump_file) + fprintf (dump_file, "\n[codegen] postpone loop phi nodes: "); + } + else + /* Either we should add the arg to phi or, we should postpone. */ + gcc_unreachable (); + } +} + +/* Copy loop phi nodes from BB to NEW_BB. */ + +static bool +copy_loop_phi_nodes (basic_block bb, basic_block new_bb, sese_info_p region) +{ + if (dump_file) + fprintf (dump_file, "\n[codegen] copying loop phi nodes in bb_%d.", + new_bb->index); + + /* Loop phi nodes should have only two arguments. */ + gcc_assert (2 == EDGE_COUNT (bb->preds)); + + /* First edge is the init edge and second is the back edge. */ + init_back_edge_pair_t ibp_old_bb = get_edges (bb); + + /* First edge is the init edge and second is the back edge. */ + init_back_edge_pair_t ibp_new_bb = get_edges (new_bb); + + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + tree res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; + if (is_gimple_reg (res) && scev_analyzable_p (res, region->region)) + continue; + + gphi *new_phi = create_phi_node (SSA_NAME_VAR (res), new_bb); + tree new_res = create_new_def_for (res, new_phi, + gimple_phi_result_ptr (new_phi)); + set_rename (res, new_res, region); + copy_loop_phi_args (phi, ibp_old_bb, new_phi, ibp_new_bb, region, true); + update_stmt (new_phi); + } + + return true; +} + +/* Return the init value of PHI, the value coming from outside the loop. */ + +static tree +get_loop_init_value (gphi *phi) +{ + + loop_p loop = gimple_bb (phi)->loop_father; + + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds) + if (e->src->loop_father != loop) + return gimple_phi_arg_def (phi, e->dest_idx); + + return NULL_TREE; +} + +/* Find the init value (the value which comes from outside the loop), of one of + the operands of DEF which is defined by a loop phi. */ + +static tree +find_init_value (gimple *def) +{ + if (gimple_code (def) == GIMPLE_PHI) + return get_loop_init_value (as_a <gphi*> (def)); + + if (gimple_vuse (def)) + return NULL_TREE; + + ssa_op_iter iter; + use_operand_p use_p; + FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE) + { + tree use = USE_FROM_PTR (use_p); + if (TREE_CODE (use) == SSA_NAME) + { + if (tree res = find_init_value (SSA_NAME_DEF_STMT (use))) + return res; + } + } + + return NULL_TREE; +} + +/* Return the init value, the value coming from outside the loop. */ + +static tree +find_init_value_close_phi (gphi *phi) +{ + gcc_assert (gimple_phi_num_args (phi) == 1); + tree use_arg = gimple_phi_arg_def (phi, 0); + gimple *def = SSA_NAME_DEF_STMT (use_arg); + return find_init_value (def); +} + +/* Copy all the loop-close phi args from BB to NEW_BB. */ + +bool +copy_loop_close_phi_args (basic_block old_bb, basic_block new_bb, + sese_info_p region, bool postpone) +{ + /* The successor of bb having close phi should be a merge of the diamond + inserted to guard the loop during codegen. */ + basic_block close_phi_merge_bb = single_succ (new_bb); + + for (gphi_iterator psi = gsi_start_phis (old_bb); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + tree res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; + + if (is_gimple_reg (res) && scev_analyzable_p (res, region->region)) + /* Loop close phi nodes should not be scev_analyzable_p. */ + gcc_unreachable (); + + gphi *new_phi = create_phi_node (SSA_NAME_VAR (res), new_bb); + tree new_res = create_new_def_for (res, new_phi, + gimple_phi_result_ptr (new_phi)); + set_rename (res, new_res, region); + + tree old_name = gimple_phi_arg_def (phi, 0); + tree new_name = get_new_name (region, new_bb, old_name, old_bb, false); + + /* Predecessor basic blocks of a loop close phi should have been code + generated before. FIXME: This is fixable by merging PHIs from inner + loops as well. When we are looking at close-phi of an outer loop, and + arguments flowing out of inner loop as not been collected by the + outer-loop close phi, we will hit this situation. For now we just bail + out. See: gfortran.dg/graphite/interchange-3.f90. */ + if (!new_name) + return false; + + add_phi_arg (new_phi, new_name, single_pred_edge (new_bb), + get_loc (old_name)); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] Adding loop-closed phi: "); + print_gimple_stmt (dump_file, new_phi, 0, 0); + } + + update_stmt (new_phi); + + /* When there is no loop guard around this codegenerated loop, there is no + need to collect the close-phi arg. */ + if (2 != EDGE_COUNT (close_phi_merge_bb->preds)) + continue; + + /* Add a PHI in the close_phi_merge_bb for each close phi of the loop. */ + tree init = find_init_value_close_phi (new_phi); + + /* A close phi must come from a loop-phi having an init value. */ + if (!init) + { + gcc_assert (postpone); + region->incomplete_phis.safe_push (std::make_pair (phi, new_phi)); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] postpone close phi nodes: "); + print_gimple_stmt (dump_file, new_phi, 0, 0); + } + continue; + } + + gphi *merge_phi = create_phi_node (SSA_NAME_VAR (res), + close_phi_merge_bb); + tree merge_res = create_new_def_for (res, merge_phi, + gimple_phi_result_ptr (merge_phi)); + set_rename (res, merge_res, region); + + edge from_loop = single_succ_edge (new_bb); + add_phi_arg (merge_phi, new_res, from_loop, get_loc (old_name)); + + /* The edge coming from loop guard. */ + edge other = from_loop == (*close_phi_merge_bb->preds)[0] + ? (*close_phi_merge_bb->preds)[1] : (*close_phi_merge_bb->preds)[0]; + + add_phi_arg (merge_phi, init, other, get_loc (old_name)); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] Adding guard-phi: "); + print_gimple_stmt (dump_file, merge_phi, 0, 0); + } + + update_stmt (new_phi); + } + + return true; +} + +/* Copy loop close phi nodes from BB to NEW_BB. */ + +static bool +copy_loop_close_phi_nodes (basic_block old_bb, basic_block new_bb, + sese_info_p region) +{ + if (dump_file) + fprintf (dump_file, "\n[codegen] copying loop closed phi nodes in bb_%d.", + new_bb->index); + /* Loop close phi nodes should have only one argument. */ + gcc_assert (1 == EDGE_COUNT (old_bb->preds)); + + return copy_loop_close_phi_args (old_bb, new_bb, region, true); +} + + +/* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB. + DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the + other pred of OLD_BB as well. If no such basic block exists then it is NULL. + NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be + NULL. + + Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa. + In this case DOMINATING_PRED = NULL. + + Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2. + + Returns true on successful copy of the args, false otherwise. */ + +static bool +add_phi_arg_for_new_expr (tree old_phi_args[2], tree new_phi_args[2], + edge old_bb_dominating_edge, + edge old_bb_non_dominating_edge, + gphi *phi, gphi *new_phi, + basic_block new_bb, sese_info_p region) +{ + basic_block def_pred[2]; + int not_found_bb_index = -1; + for (int i = 0; i < 2; i++) + { + /* If the corresponding def_bb could not be found the entry will be + NULL. */ + if (TREE_CODE (old_phi_args[i]) == INTEGER_CST) + def_pred[i] = get_def_bb_for_const (region, new_bb, + gimple_phi_arg_edge (phi, i)->src); + else + def_pred[i] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args[i])); + if (!def_pred[i]) + { + gcc_assert (not_found_bb_index == -1); + not_found_bb_index = i; + } + } + + /* Here we are pattern matching on the structure of CFG w.r.t. old one. */ + if (old_bb_dominating_edge) + { + return false; + basic_block new_pred1 = (*new_bb->preds)[0]->src; + basic_block new_pred2 = (*new_bb->preds)[1]->src; + vec <basic_block> *bbs + = region->copied_bb_map->get (old_bb_non_dominating_edge->src); + gcc_assert (bbs); + basic_block new_pred = NULL; + basic_block b; + int i; + FOR_EACH_VEC_ELT (*bbs, i, b) + if (new_pred1 == b || new_pred2 == b) + { + gcc_assert (!new_pred); + new_pred = b; + } + + gcc_assert (new_pred); + + edge new_non_dominating_edge = find_edge (new_pred, new_bb); + /* By the process of elimination we first insert insert phi-edge for + non-dominating pred which is computed above and then we insert the + remaining one. */ + int inserted_edge = 0; + for (; inserted_edge < 2; inserted_edge++) + { + edge new_bb_pred_edge = gimple_phi_arg_edge (phi, inserted_edge); + if (new_non_dominating_edge == new_bb_pred_edge) + { + add_phi_arg (new_phi, new_phi_args[inserted_edge], + new_non_dominating_edge, + get_loc (old_phi_args[inserted_edge])); + break; + } + } + + int edge_dominating = 0; + if (inserted_edge == 0) + edge_dominating = 1; + + edge new_dominating_edge = NULL; + for (int i; i < 2; i++) + { + edge e = gimple_phi_arg_edge (new_phi, i); + if (e != new_non_dominating_edge) + new_dominating_edge = e; + } + + add_phi_arg (new_phi, new_phi_args[edge_dominating], new_dominating_edge, + get_loc (old_phi_args[inserted_edge])); + } + else + { + /* Classic diamond structure: both edges are non-dominating. We need to + find one unique edge then the other can be found be elimination. If + any definition (def_pred) dominates both the preds of new_bb then we + bail out. Entries of def_pred maybe NULL, in that case we must + uniquely find pred with help of only one entry. */ + edge new_e[2] = { NULL, NULL }; + for (int i = 0; i < 2; i++) + { + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, new_bb->preds) + if (def_pred[i] + && dominated_by_p (CDI_DOMINATORS, e->src, def_pred[i])) + { + if (new_e[i]) + /* We do not know how to handle the case when def_pred + dominates more than a predecessor. */ + return false; + new_e[i] = e; + } + } + + gcc_assert (new_e[0] || new_e[1]); + + /* Find the other edge by process of elimination. */ + if (not_found_bb_index != -1) + { + gcc_assert (!new_e[not_found_bb_index]); + int found_bb_index = not_found_bb_index == 1 ? 0 : 1; + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, new_bb->preds) + { + if (new_e[found_bb_index] == e) + continue; + new_e[not_found_bb_index] = e; + } + } + + /* Add edges to phi args. */ + for (int i = 0; i < 2; i++) + add_phi_arg (new_phi, new_phi_args[i], new_e[i], + get_loc (old_phi_args[i])); + } + + return true; +} + +/* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated + region. If postpone is true and it isn't possible to copy any arg of PHI, + the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated + later. Returns false if the copying was unsuccessful. */ + +bool +copy_cond_phi_args (gphi *phi, gphi *new_phi, vec<tree> iv_map, + sese_info_p region, bool postpone) +{ + if (dump_file) + fprintf (dump_file, "\n[codegen] copying cond phi args: "); + gcc_assert (2 == gimple_phi_num_args (phi)); + + basic_block new_bb = gimple_bb (new_phi); + loop_p loop = gimple_bb (phi)->loop_father; + + basic_block old_bb = gimple_bb (phi); + edge old_bb_non_dominating_edge = NULL, old_bb_dominating_edge = NULL; + + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, old_bb->preds) + if (!dominated_by_p (CDI_DOMINATORS, old_bb, e->src)) + old_bb_non_dominating_edge = e; + else + old_bb_dominating_edge = e; + + gcc_assert (!dominated_by_p (CDI_DOMINATORS, old_bb, + old_bb_non_dominating_edge->src)); + + tree new_phi_args[2]; + tree old_phi_args[2]; + + for (unsigned i = 0; i < gimple_phi_num_args (phi); i++) + { + tree old_name = gimple_phi_arg_def (phi, i); + tree new_name = get_new_name (region, new_bb, old_name, old_bb, false); + old_phi_args[i] = old_name; + if (new_name) + { + new_phi_args [i] = new_name; + continue; + } + + if (vec_find (region->params, old_name)) + { + new_phi_args [i] = old_name; + if (dump_file) + { + fprintf (dump_file, + "\n[codegen] parameter argument to phi, new_expr: "); + print_gimple_stmt (dump_file, new_phi, 0, 0); + } + continue; + } + + /* If the phi-arg is scev-analyzeable but only in the first stage. */ + if (postpone && is_gimple_reg (old_name) + && scev_analyzable_p (old_name, region->region)) + { + gimple_seq stmts; + bool gloog_error = false; + tree new_expr + = get_rename_from_scev (old_name, &stmts, loop, new_bb, + old_bb, iv_map, region, &gloog_error); + if (gloog_error) + return false; + + gcc_assert (new_expr); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] scev analyzeable, new_expr: "); + print_generic_expr (dump_file, new_expr, 0); + } + gsi_insert_earliest (stmts, region); + new_phi_args [i] = new_name; + continue; + } + + gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name); + if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP) + /* If the phi arg was a function arg, or wasn't defined, just use the + old name. */ + gcc_unreachable (); + else if (postpone) + { + /* Postpone code gen for later for back-edges. */ + region->incomplete_phis.safe_push (std::make_pair (phi, new_phi)); + + if (dump_file) + { + fprintf (dump_file, "\n[codegen] postpone cond phi nodes: "); + print_gimple_stmt (dump_file, new_phi, 0, 0); + } + + new_phi_args [i] = NULL_TREE; + continue; + } + else + gcc_unreachable (); + } + + return add_phi_arg_for_new_expr (old_phi_args, new_phi_args, + old_bb_dominating_edge, + old_bb_non_dominating_edge, + phi, new_phi, new_bb, region); +} + +/* Copy cond phi nodes from BB to NEW_BB. */ + +static bool +copy_cond_phi_nodes (basic_block bb, basic_block new_bb, vec<tree> iv_map, + sese_info_p region) +{ + + gcc_assert (!bb_contains_loop_close_phi_nodes (bb)); + + if (dump_file) + fprintf (dump_file, "\n[codegen] copying cond phi nodes in bb_%d:", + new_bb->index); + + /* Cond phi nodes should have exactly two arguments. */ + gcc_assert (2 == EDGE_COUNT (bb->preds)); + + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + tree res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; + if (is_gimple_reg (res) && scev_analyzable_p (res, region->region)) + /* Cond phi nodes should not be scev_analyzable_p. */ + gcc_unreachable (); + + gphi *new_phi = create_phi_node (SSA_NAME_VAR (res), new_bb); + tree new_res = create_new_def_for (res, new_phi, + gimple_phi_result_ptr (new_phi)); + set_rename (res, new_res, region); + + if (!copy_cond_phi_args (phi, new_phi, iv_map, region, true)) + return false; + + update_stmt (new_phi); + } + + return true; +} + +/* Return true if STMT should be copied from region to the + new code-generated region. LABELs, CONDITIONS, induction-variables + and region parameters need not be copied. */ + +static bool +should_copy_to_new_region (gimple *stmt, sese_info_p region) +{ + /* Do not copy labels or conditions. */ + if (gimple_code (stmt) == GIMPLE_LABEL + || gimple_code (stmt) == GIMPLE_COND) + return false; + + tree lhs; + /* Do not copy induction variables. */ + if (is_gimple_assign (stmt) + && (lhs = gimple_assign_lhs (stmt)) + && TREE_CODE (lhs) == SSA_NAME + && is_gimple_reg (lhs) + && scev_analyzable_p (lhs, region->region)) + return false; + + return true; +} + +/* Create new names for all the definitions created by COPY and + add replacement mappings for each new name. */ + +static void +set_rename_for_each_def (gimple *stmt, sese_info_p region) +{ + def_operand_p def_p; + ssa_op_iter op_iter; + FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS) + { + tree old_name = DEF_FROM_PTR (def_p); + tree new_name = create_new_def_for (old_name, stmt, def_p); + set_rename (old_name, new_name, region); + } +} + /* Duplicates the statements of basic block BB into basic block NEW_BB and compute the new induction variables according to the IV_MAP. GLOOG_ERROR is set when the code generation cannot continue. */ - -static void +static bool graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, - rename_map_type *rename_map, vec<tree> iv_map, sese_info_p region, bool *gloog_error) { - gimple_stmt_iterator gsi, gsi_tgt; - loop_p loop = bb->loop_father; + /* Iterator poining to the place where new statement (s) will be inserted. */ + gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb); - gsi_tgt = gsi_start_bb (new_bb); - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) { - def_operand_p def_p; - ssa_op_iter op_iter; gimple *stmt = gsi_stmt (gsi); - gimple *copy; - tree lhs; - - /* Do not copy labels or conditions. */ - if (gimple_code (stmt) == GIMPLE_LABEL - || gimple_code (stmt) == GIMPLE_COND) - continue; - - /* Do not copy induction variables. */ - if (is_gimple_assign (stmt) - && (lhs = gimple_assign_lhs (stmt)) - && TREE_CODE (lhs) == SSA_NAME - && is_gimple_reg (lhs) - && scev_analyzable_p (lhs, region->region)) + if (!should_copy_to_new_region (stmt, region)) continue; /* Create a new copy of STMT and duplicate STMT's virtual operands. */ - copy = gimple_copy (stmt); + gimple *copy = gimple_copy (stmt); gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT); + if (dump_file) + { + fprintf (dump_file, "\n[codegen] inserting statement: "); + print_gimple_stmt (dump_file, copy, 0, 0); + } + maybe_duplicate_eh_stmt (copy, stmt); gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt); - /* Create new names for all the definitions created by COPY and - add replacement mappings for each new name. */ - FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS) - { - tree old_name = DEF_FROM_PTR (def_p); - tree new_name = create_new_def_for (old_name, copy, def_p); - set_rename (rename_map, old_name, new_name); - } + /* Crete new names for each def in the copied stmt. */ + set_rename_for_each_def (copy, region); - if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map, - gloog_error)) + loop_p loop = bb->loop_father; + if (rename_uses (copy, &gsi_tgt, bb, region, loop, iv_map, gloog_error)) { - gcc_assert (gsi_stmt (gsi_tgt) == copy); fold_stmt_inplace (&gsi_tgt); + gcc_assert (gsi_stmt (gsi_tgt) == copy); } + if (*gloog_error) + return false; + update_stmt (copy); } + + return true; } /* Copies BB and includes in the copied BB all the statements that can @@ -564,17 +1729,127 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, edge copy_bb_and_scalar_dependences (basic_block bb, sese_info_p region, edge next_e, vec<tree> iv_map, - bool *gloog_error) + bool *codegen_err) { + int num_phis = number_of_phi_nodes (bb); + + if (region->copied_bb_map->get (bb)) + { + /* FIXME: We do not handle inner loop unrolling when the inner loop has + phi-nodes. In that case inner loop will be copied multiple times + outside the region. */ + if (num_phis) + { + *codegen_err = true; + return NULL; + } + } + basic_block new_bb = split_edge (next_e); - rename_map_type rename_map (10); + if (num_phis > 0 && bb_contains_loop_phi_nodes (bb)) + { + basic_block phi_bb = next_e->dest->loop_father->header; - next_e = single_succ_edge (new_bb); - graphite_copy_stmts_from_block (bb, new_bb, &rename_map, iv_map, region, - gloog_error); - remove_phi_nodes (new_bb); + /* At this point we are unable to codegenerate by still preserving the SSA + structure because maybe the loop is completely unrolled and the PHIs + and cross-bb scalar dependencies are untrackable w.r.t. the original + code. See gfortran.dg/graphite/pr29832.f90. */ + if (EDGE_COUNT (bb->preds) != EDGE_COUNT (phi_bb->preds)) + { + *codegen_err = true; + return NULL; + } - return next_e; + if (dump_file) + fprintf (dump_file, "\n[codegen] bb_%d contains loop phi nodes", + bb->index); + if (!copy_loop_phi_nodes (bb, phi_bb, region)) + { + *codegen_err = true; + return NULL; + } + } + else if (bb_contains_loop_close_phi_nodes (bb)) + { + if (dump_file) + fprintf (dump_file, "\n[codegen] bb_%d contains close phi nodes", + bb->index); + + /* Make sure that NEW_BB is the loop->exit->dest. */ + edge e = single_pred_edge (new_bb); + basic_block phi_bb = new_bb; + if (e->src->loop_father == e->dest->loop_father) + { + /* This is one of the places which shows preserving original structure + is not always possible, as we may need to insert close PHI for a + loop where the latch does not have any mapping, or the mapping is + ambiguous. */ + basic_block old_loop_bb = single_pred_edge (bb)->src; + vec <basic_block> *bbs = region->copied_bb_map->get (old_loop_bb); + if (!bbs || bbs->length () != 1) + { + *codegen_err = true; + return NULL; + } + + basic_block new_loop_bb = (*bbs)[0]; + loop_p new_loop = new_loop_bb->loop_father; + phi_bb = single_exit (new_loop)->dest; + e = single_pred_edge (phi_bb); + } + + gcc_assert (e->src->loop_father != e->dest->loop_father); + + if (!copy_loop_close_phi_nodes (bb, phi_bb, region)) + { + *codegen_err = true; + return NULL; + } + } + else if (num_phis > 0) + { + if (dump_file) + fprintf (dump_file, "\n[codegen] bb_%d contains cond phi nodes", + bb->index); + + basic_block phi_bb = single_pred (new_bb); + loop_p loop_father = new_bb->loop_father; + + /* Move back until we find the block with two predecessors. */ + while (single_pred_p (phi_bb)) + phi_bb = single_pred_edge (phi_bb)->src; + + /* If a corresponding merge-point was not found, then abort codegen. */ + if (phi_bb->loop_father != loop_father + || !copy_cond_phi_nodes (bb, phi_bb, iv_map, region)) + { + *codegen_err = true; + return NULL; + } + } + + if (dump_file) + fprintf (dump_file, "\n[codegen] copying from bb_%d to bb_%d", + bb->index, new_bb->index); + + vec <basic_block> *copied_bbs = region->copied_bb_map->get (bb); + if (copied_bbs) + copied_bbs->safe_push (new_bb); + else + { + vec<basic_block> bbs; + bbs.create (2); + bbs.safe_push (new_bb); + region->copied_bb_map->put (bb, bbs); + } + + if (!graphite_copy_stmts_from_block (bb, new_bb, iv_map, region, codegen_err)) + { + *codegen_err = true; + return NULL; + } + + return single_succ_edge (new_bb); } /* Returns the outermost loop in SCOP that contains BB. */ @@ -759,8 +2034,6 @@ set_ifsese_condition (ifsese if_region, tree condition) bool invariant_in_sese_p_rec (tree t, sese_l ®ion, bool *has_vdefs) { - ssa_op_iter iter; - use_operand_p use_p; if (!defined_in_sese_p (t, region)) return true; @@ -782,6 +2055,8 @@ invariant_in_sese_p_rec (tree t, sese_l ®ion, bool *has_vdefs) if (tree vuse = gimple_vuse (stmt)) return invariant_in_sese_p_rec (vuse, region, has_vdefs); + ssa_op_iter iter; + use_operand_p use_p; FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) { tree use = USE_FROM_PTR (use_p); |