X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-loop-manip.c;h=cbd03b73061df421ea886241bb92a83c1b8fd6a7;hb=430e64f89b6803820d16ae499c4cbab6cb76a8cb;hp=edb821d24f7266de823560d4d31619340e2be138;hpb=43daa21e7c3b20f510ed5e16e2aef1b806d69d2b;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index edb821d24f7..cbd03b73061 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -1,5 +1,5 @@ /* High-level loop manipulation functions. - Copyright (C) 2004 Free Software Foundation, Inc. + Copyright (C) 2004, 2005 Free Software Foundation, Inc. This file is part of GCC. @@ -15,8 +15,8 @@ for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ #include "config.h" #include "system.h" @@ -41,7 +41,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA It is expected that neither BASE nor STEP are shared with other expressions (unless the sharing rules allow this). Use VAR as a base var_decl for it (if NULL, a new temporary will be created). The increment will occur at - INCR_POS (after it if AFTER is true, before it otherwise). The ssa versions + INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and + AFTER can be computed using standard_iv_increment_position. The ssa versions of the variable before and after increment will be stored in VAR_BEFORE and VAR_AFTER (unless they are NULL). */ @@ -50,9 +51,10 @@ create_iv (tree base, tree step, tree var, struct loop *loop, block_stmt_iterator *incr_pos, bool after, tree *var_before, tree *var_after) { - tree stmt, initial, step1; + tree stmt, initial, step1, stmts; tree vb, va; enum tree_code incr_op = PLUS_EXPR; + edge pe = loop_preheader_edge (loop); if (!var) { @@ -73,7 +75,7 @@ create_iv (tree base, tree step, tree var, struct loop *loop, { if (TYPE_UNSIGNED (TREE_TYPE (step))) { - step1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step)); + step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); if (tree_int_cst_lt (step1, step)) { incr_op = MINUS_EXPR; @@ -86,11 +88,17 @@ create_iv (tree base, tree step, tree var, struct loop *loop, && may_negate_without_overflow_p (step)) { incr_op = MINUS_EXPR; - step = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step)); + step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); } } } + /* Gimplify the step if necessary. We put the computations in front of the + loop (i.e. the step should be loop invariant). */ + step = force_gimple_operand (step, &stmts, true, var); + if (stmts) + bsi_insert_on_edge_immediate_loop (pe, stmts); + stmt = build2 (MODIFY_EXPR, void_type_node, va, build2 (incr_op, TREE_TYPE (base), vb, step)); @@ -100,12 +108,14 @@ create_iv (tree base, tree step, tree var, struct loop *loop, else bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT); - initial = base; + initial = force_gimple_operand (base, &stmts, true, var); + if (stmts) + bsi_insert_on_edge_immediate_loop (pe, stmts); stmt = create_phi_node (vb, loop->header); SSA_NAME_DEF_STMT (vb) = stmt; - add_phi_arg (&stmt, initial, loop_preheader_edge (loop)); - add_phi_arg (&stmt, va, loop_latch_edge (loop)); + add_phi_arg (stmt, initial, loop_preheader_edge (loop)); + add_phi_arg (stmt, va, loop_latch_edge (loop)); } /* Add exit phis for the USE on EXIT. */ @@ -117,10 +127,11 @@ add_exit_phis_edge (basic_block exit, tree use) basic_block def_bb = bb_for_stmt (def_stmt); struct loop *def_loop; edge e; + edge_iterator ei; /* Check that some of the edges entering the EXIT block exits a loop in that USE is defined. */ - for (e = exit->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, exit->preds) { def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father); if (!flow_bb_inside_loop_p (def_loop, e->dest)) @@ -131,11 +142,9 @@ add_exit_phis_edge (basic_block exit, tree use) return; phi = create_phi_node (use, exit); - - for (e = exit->pred; e; e = e->pred_next) - add_phi_arg (&phi, use, e); - - SSA_NAME_DEF_STMT (use) = def_stmt; + create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi)); + FOR_EACH_EDGE (e, ei, exit->preds) + add_phi_arg (phi, use, e); } /* Add exit phis for VAR that is used in LIVEIN. @@ -145,18 +154,24 @@ static void add_exit_phis_var (tree var, bitmap livein, bitmap exits) { bitmap def; - int index; + unsigned index; basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); + bitmap_iterator bi; - bitmap_clear_bit (livein, def_bb->index); + if (is_gimple_reg (var)) + bitmap_clear_bit (livein, def_bb->index); + else + bitmap_set_bit (livein, def_bb->index); - def = BITMAP_XMALLOC (); + def = BITMAP_ALLOC (NULL); bitmap_set_bit (def, def_bb->index); compute_global_livein (livein, def); - BITMAP_XFREE (def); + BITMAP_FREE (def); - EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, - add_exit_phis_edge (BASIC_BLOCK (index), var)); + EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi) + { + add_exit_phis_edge (BASIC_BLOCK (index), var); + } } /* Add exit phis for the names marked in NAMES_TO_RENAME. @@ -167,11 +182,12 @@ static void add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) { unsigned i; + bitmap_iterator bi; - EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, + EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) { add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); - }); + } } /* Returns a bitmap of all loop exit edge targets. */ @@ -179,13 +195,14 @@ add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) static bitmap get_loops_exits (void) { - bitmap exits = BITMAP_XMALLOC (); + bitmap exits = BITMAP_ALLOC (NULL); basic_block bb; edge e; + edge_iterator ei; FOR_EACH_BB (bb) { - for (e = bb->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, bb->preds) if (e->src != ENTRY_BLOCK_PTR && !flow_bb_inside_loop_p (e->src->loop_father, bb)) { @@ -199,10 +216,11 @@ get_loops_exits (void) /* For USE in BB, if it is used outside of the loop it is defined in, mark it for rewrite. Record basic block BB where it is used - to USE_BLOCKS. */ + to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */ static void -find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks) +find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, + bitmap need_phis) { unsigned ver; basic_block def_bb; @@ -211,6 +229,10 @@ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks) if (TREE_CODE (use) != SSA_NAME) return; + /* We don't need to keep virtual operands in loop-closed form. */ + if (!is_gimple_reg (use)) + return; + ver = SSA_NAME_VERSION (use); def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); if (!def_bb) @@ -222,51 +244,75 @@ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks) return; if (!use_blocks[ver]) - use_blocks[ver] = BITMAP_XMALLOC (); + use_blocks[ver] = BITMAP_ALLOC (NULL); bitmap_set_bit (use_blocks[ver], bb->index); - if (!flow_bb_inside_loop_p (def_loop, bb)) - mark_for_rewrite (use); + bitmap_set_bit (need_phis, ver); } /* For uses in STMT, mark names that are used outside of the loop they are defined to rewrite. Record the set of blocks in that the ssa - names are defined to USE_BLOCKS. */ + names are defined to USE_BLOCKS and the ssa names themselves to + NEED_PHIS. */ static void -find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks) +find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis) { ssa_op_iter iter; tree var; basic_block bb = bb_for_stmt (stmt); - get_stmt_operands (stmt); - - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) - find_uses_to_rename_use (bb, var, use_blocks); + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) + find_uses_to_rename_use (bb, var, use_blocks, need_phis); } +/* Marks names that are used in BB and outside of the loop they are + defined in for rewrite. Records the set of blocks in that the ssa + names are defined to USE_BLOCKS. Record the SSA names that will + need exit PHIs in NEED_PHIS. */ + +static void +find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) +{ + block_stmt_iterator bsi; + edge e; + edge_iterator ei; + tree phi; + + FOR_EACH_EDGE (e, ei, bb->succs) + for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) + find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e), + use_blocks, need_phis); + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis); +} + /* Marks names that are used outside of the loop they are defined in for rewrite. Records the set of blocks in that the ssa - names are defined to USE_BLOCKS. */ + names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, + scan only blocks in this set. */ static void -find_uses_to_rename (bitmap *use_blocks) +find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) { basic_block bb; - block_stmt_iterator bsi; - tree phi; - unsigned i; + unsigned index; + bitmap_iterator bi; - FOR_EACH_BB (bb) + if (changed_bbs && !bitmap_empty_p (changed_bbs)) { - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) - for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) - find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src, - PHI_ARG_DEF (phi, i), use_blocks); - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks); + EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) + { + find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis); + } + } + else + { + FOR_EACH_BB (bb) + { + find_uses_to_rename_bb (bb, use_blocks, need_phis); + } } } @@ -294,37 +340,45 @@ find_uses_to_rename (bitmap *use_blocks) Looking from the outer loop with the normal SSA form, the first use of k is not well-behaved, while the second one is an induction variable with - base 99 and step 1. */ + base 99 and step 1. + + If CHANGED_BBS is not NULL, we look for uses outside loops only in + the basic blocks in this set. + + UPDATE_FLAG is used in the call to update_ssa. See + TODO_update_ssa* for documentation. */ void -rewrite_into_loop_closed_ssa (void) +rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) { bitmap loop_exits = get_loops_exits (); bitmap *use_blocks; - unsigned i; - bitmap names_to_rename; + unsigned i, old_num_ssa_names; + bitmap names_to_rename = BITMAP_ALLOC (NULL); - if (any_marked_for_rewrite_p ()) - abort (); + /* If the pass has caused the SSA form to be out-of-date, update it + now. */ + update_ssa (update_flag); - use_blocks = xcalloc (num_ssa_names, sizeof (bitmap)); + old_num_ssa_names = num_ssa_names; + use_blocks = xcalloc (old_num_ssa_names, sizeof (bitmap)); /* Find the uses outside loops. */ - find_uses_to_rename (use_blocks); + find_uses_to_rename (changed_bbs, use_blocks, names_to_rename); - /* Add the phi nodes on exits of the loops for the names we need to + /* Add the PHI nodes on exits of the loops for the names we need to rewrite. */ - names_to_rename = marked_ssa_names (); add_exit_phis (names_to_rename, use_blocks, loop_exits); - for (i = 0; i < num_ssa_names; i++) - BITMAP_XFREE (use_blocks[i]); + for (i = 0; i < old_num_ssa_names; i++) + BITMAP_FREE (use_blocks[i]); free (use_blocks); - BITMAP_XFREE (loop_exits); - BITMAP_XFREE (names_to_rename); + BITMAP_FREE (loop_exits); + BITMAP_FREE (names_to_rename); - /* Do the rewriting. */ - rewrite_ssa_into_ssa (); + /* Fix up all the names found to be used outside their original + loops. */ + update_ssa (TODO_update_ssa); } /* Check invariants of the loop closed ssa form for the USE in BB. */ @@ -335,14 +389,13 @@ check_loop_closed_ssa_use (basic_block bb, tree use) tree def; basic_block def_bb; - if (TREE_CODE (use) != SSA_NAME) + if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use)) return; def = SSA_NAME_DEF_STMT (use); def_bb = bb_for_stmt (def); - if (def_bb - && !flow_bb_inside_loop_p (def_bb->loop_father, bb)) - abort (); + gcc_assert (!def_bb + || flow_bb_inside_loop_p (def_bb->loop_father, bb)); } /* Checks invariants of loop closed ssa form in statement STMT in BB. */ @@ -353,9 +406,7 @@ check_loop_closed_ssa_stmt (basic_block bb, tree stmt) ssa_op_iter iter; tree var; - get_stmt_operands (stmt); - - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) check_loop_closed_ssa_use (bb, var); } @@ -369,11 +420,14 @@ verify_loop_closed_ssa (void) tree phi; unsigned i; - verify_ssa (); + if (current_loops == NULL) + return; + + verify_ssa (false); FOR_EACH_BB (bb) { - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src, PHI_ARG_DEF (phi, i)); @@ -382,3 +436,185 @@ verify_loop_closed_ssa (void) check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi)); } } + +/* Split loop exit edge EXIT. The things are a bit complicated by a need to + preserve the loop closed ssa form. */ + +void +split_loop_exit_edge (edge exit) +{ + basic_block dest = exit->dest; + basic_block bb = loop_split_edge_with (exit, NULL); + tree phi, new_phi, new_name, name; + use_operand_p op_p; + + for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) + { + op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); + + name = USE_FROM_PTR (op_p); + + /* If the argument of the phi node is a constant, we do not need + to keep it inside loop. */ + if (TREE_CODE (name) != SSA_NAME) + continue; + + /* Otherwise create an auxiliary phi node that will copy the value + of the ssa name out of the loop. */ + new_name = duplicate_ssa_name (name, NULL); + new_phi = create_phi_node (new_name, bb); + SSA_NAME_DEF_STMT (new_name) = new_phi; + add_phi_arg (new_phi, name, exit); + SET_USE (op_p, new_name); + } +} + +/* Insert statement STMT to the edge E and update the loop structures. + Returns the newly created block (if any). */ + +basic_block +bsi_insert_on_edge_immediate_loop (edge e, tree stmt) +{ + basic_block src, dest, new_bb; + struct loop *loop_c; + + src = e->src; + dest = e->dest; + + loop_c = find_common_loop (src->loop_father, dest->loop_father); + + new_bb = bsi_insert_on_edge_immediate (e, stmt); + + if (!new_bb) + return NULL; + + add_bb_to_loop (new_bb, loop_c); + if (dest->loop_father->latch == src) + dest->loop_father->latch = new_bb; + + return new_bb; +} + +/* Returns the basic block in that statements should be emitted for induction + variables incremented at the end of the LOOP. */ + +basic_block +ip_end_pos (struct loop *loop) +{ + return loop->latch; +} + +/* Returns the basic block in that statements should be emitted for induction + variables incremented just before exit condition of a LOOP. */ + +basic_block +ip_normal_pos (struct loop *loop) +{ + tree last; + basic_block bb; + edge exit; + + if (!single_pred_p (loop->latch)) + return NULL; + + bb = single_pred (loop->latch); + last = last_stmt (bb); + if (TREE_CODE (last) != COND_EXPR) + return NULL; + + exit = EDGE_SUCC (bb, 0); + if (exit->dest == loop->latch) + exit = EDGE_SUCC (bb, 1); + + if (flow_bb_inside_loop_p (loop, exit->dest)) + return NULL; + + return bb; +} + +/* Stores the standard position for induction variable increment in LOOP + (just before the exit condition if it is available and latch block is empty, + end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if + the increment should be inserted after *BSI. */ + +void +standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, + bool *insert_after) +{ + basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); + tree last = last_stmt (latch); + + if (!bb + || (last && TREE_CODE (last) != LABEL_EXPR)) + { + *bsi = bsi_last (latch); + *insert_after = true; + } + else + { + *bsi = bsi_last (bb); + *insert_after = false; + } +} + +/* Copies phi node arguments for duplicated blocks. The index of the first + duplicated block is FIRST_NEW_BLOCK. */ + +static void +copy_phi_node_args (unsigned first_new_block) +{ + unsigned i; + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + BASIC_BLOCK (i)->flags |= BB_DUPLICATED; + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + add_phi_args_after_copy_bb (BASIC_BLOCK (i)); + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED; +} + + +/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also + updates the PHI nodes at start of the copied region. In order to + achieve this, only loops whose exits all lead to the same location + are handled. + + Notice that we do not completely update the SSA web after + duplication. The caller is responsible for calling update_ssa + after the loop has been duplicated. */ + +bool +tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, + struct loops *loops, + unsigned int ndupl, sbitmap wont_exit, + edge orig, edge *to_remove, + unsigned int *n_to_remove, int flags) +{ + unsigned first_new_block; + + if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) + return false; + if (!(loops->state & LOOPS_HAVE_PREHEADERS)) + return false; + +#ifdef ENABLE_CHECKING + verify_loop_closed_ssa (); +#endif + + first_new_block = last_basic_block; + if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, + orig, to_remove, n_to_remove, flags)) + return false; + + /* Readd the removed phi args for e. */ + flush_pending_stmts (e); + + /* Copy the phi node arguments. */ + copy_phi_node_args (first_new_block); + + scev_reset (); + + return true; +}