X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-loop-manip.c;h=848abbc88d6130b2ad96886390463e7b8dfbdaab;hb=218d4d214de099c33636ec2c1aadff4a734c0198;hp=cde3ce8fb4d80e4ca8d017f4943ebb57c2b9c7df;hpb=8c0963c4a8751406a784d5c4c34001e18272463a;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index cde3ce8fb4d..848abbc88d6 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. @@ -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). */ @@ -110,8 +111,8 @@ create_iv (tree base, tree step, tree var, struct loop *loop, 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. */ @@ -123,10 +124,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)) @@ -138,8 +140,8 @@ add_exit_phis_edge (basic_block exit, tree use) phi = create_phi_node (use, exit); - for (e = exit->pred; e; e = e->pred_next) - add_phi_arg (&phi, use, e); + FOR_EACH_EDGE (e, ei, exit->preds) + add_phi_arg (phi, use, e); SSA_NAME_DEF_STMT (use) = def_stmt; } @@ -151,18 +153,21 @@ 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); - 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. @@ -173,11 +178,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. */ @@ -185,13 +191,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)) { @@ -228,7 +235,7 @@ 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)) @@ -248,7 +255,7 @@ find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks) 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) find_uses_to_rename_use (bb, var, use_blocks); } @@ -266,9 +273,9 @@ find_uses_to_rename (bitmap *use_blocks) 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++) - find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src, + find_uses_to_rename_use (EDGE_PRED (bb, i)->src, PHI_ARG_DEF (phi, i), use_blocks); for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) @@ -323,10 +330,10 @@ rewrite_into_loop_closed_ssa (void) add_exit_phis (names_to_rename, use_blocks, loop_exits); for (i = 0; i < num_ssa_names; i++) - BITMAP_XFREE (use_blocks[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 (); @@ -377,7 +384,7 @@ verify_loop_closed_ssa (void) 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)); @@ -395,17 +402,26 @@ 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; + tree phi, new_phi, new_name, name; use_operand_p op_p; - for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi)) + for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) { - op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, bb->succ); + op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, EDGE_SUCC (bb, 0)); + + 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; - new_name = duplicate_ssa_name (USE_FROM_PTR (op_p), NULL); + /* 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, USE_FROM_PTR (op_p), exit); + add_phi_arg (new_phi, name, exit); SET_USE (op_p, new_name); } } @@ -455,17 +471,17 @@ ip_normal_pos (struct loop *loop) basic_block bb; edge exit; - if (loop->latch->pred->pred_next) + if (EDGE_COUNT (loop->latch->preds) > 1) return NULL; - bb = loop->latch->pred->src; + bb = EDGE_PRED (loop->latch, 0)->src; last = last_stmt (bb); if (TREE_CODE (last) != COND_EXPR) return NULL; - exit = bb->succ; + exit = EDGE_SUCC (bb, 0); if (exit->dest == loop->latch) - exit = exit->succ_next; + exit = EDGE_SUCC (bb, 1); if (flow_bb_inside_loop_p (loop, exit->dest)) return NULL; @@ -497,3 +513,308 @@ standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, *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)->rbi->duplicated = 1; + + 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)->rbi->duplicated = 0; +} + +/* Renames variables in the area copied by tree_duplicate_loop_to_header_edge. + FIRST_NEW_BLOCK is the first block in the copied area. DEFINITIONS is + a bitmap of all ssa names defined inside the loop. */ + +static void +rename_variables (unsigned first_new_block, bitmap definitions) +{ + unsigned i, copy_number = 0; + basic_block bb; + htab_t ssa_name_map = NULL; + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + { + bb = BASIC_BLOCK (i); + + /* We assume that first come all blocks from the first copy, then all + blocks from the second copy, etc. */ + if (copy_number != (unsigned) bb->rbi->copy_number) + { + allocate_ssa_names (definitions, &ssa_name_map); + copy_number = bb->rbi->copy_number; + } + + rewrite_to_new_ssa_names_bb (bb, ssa_name_map); + } + + htab_delete (ssa_name_map); +} + +/* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB. */ + +static void +set_phi_def_stmts (basic_block bb) +{ + tree phi; + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi; +} + +/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates + ssa. In order to achieve this, only loops whose exits all lead to the same + location are handled. + + FIXME: we create some degenerate phi nodes that could be avoided by copy + propagating them instead. Unfortunately this is not completely + straightforward due to problems with constant folding. */ + +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; + basic_block bb; + unsigned i; + bitmap definitions; + + 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 + + gcc_assert (!any_marked_for_rewrite_p ()); + + 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); + + /* Rename the variables. */ + definitions = marked_ssa_names (); + rename_variables (first_new_block, definitions); + unmark_all_for_rewrite (); + BITMAP_FREE (definitions); + + /* For some time we have the identical ssa names as results in multiple phi + nodes. When phi node is resized, it sets SSA_NAME_DEF_STMT of its result + to the new copy. This means that we cannot easily ensure that the ssa + names defined in those phis are pointing to the right one -- so just + recompute SSA_NAME_DEF_STMT for them. */ + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + { + bb = BASIC_BLOCK (i); + set_phi_def_stmts (bb); + if (bb->rbi->copy_number == 1) + set_phi_def_stmts (bb->rbi->original); + } + + scev_reset (); +#ifdef ENABLE_CHECKING + verify_loop_closed_ssa (); +#endif + + return true; +} + +/*--------------------------------------------------------------------------- + Loop versioning + ---------------------------------------------------------------------------*/ + +/* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy + of 'first'. Both of them are dominated by 'new_head' basic block. When + 'new_head' was created by 'second's incoming edge it received phi arguments + on the edge by split_edge(). Later, additional edge 'e' was created to + connect 'new_head' and 'first'. Now this routine adds phi args on this + additional edge 'e' that new_head to second edge received as part of edge + splitting. +*/ + +static void +lv_adjust_loop_header_phi (basic_block first, basic_block second, + basic_block new_head, edge e) +{ + tree phi1, phi2; + + /* Browse all 'second' basic block phi nodes and add phi args to + edge 'e' for 'first' head. PHI args are always in correct order. */ + + for (phi2 = phi_nodes (second), phi1 = phi_nodes (first); + phi2 && phi1; + phi2 = PHI_CHAIN (phi2), phi1 = PHI_CHAIN (phi1)) + { + edge e2 = find_edge (new_head, second); + + if (e2) + { + tree def = PHI_ARG_DEF (phi2, e2->dest_idx); + add_phi_arg (phi1, def, e); + } + } +} + +/* Adjust entry edge for lv. + + e is an incoming edge. + + --- edge e ---- > [second_head] + + Split it and insert new conditional expression and adjust edges. + + --- edge e ---> [cond expr] ---> [first_head] + | + +---------> [second_head] + +*/ + +static basic_block +lv_adjust_loop_entry_edge (basic_block first_head, + basic_block second_head, + edge e, + tree cond_expr) +{ + block_stmt_iterator bsi; + basic_block new_head = NULL; + tree goto1 = NULL_TREE; + tree goto2 = NULL_TREE; + tree new_cond_expr = NULL_TREE; + edge e0, e1; + + gcc_assert (e->dest == second_head); + + /* Split edge 'e'. This will create a new basic block, where we can + insert conditional expr. */ + new_head = split_edge (e); + + /* Build new conditional expr */ + goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head)); + goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head)); + new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2); + + /* Add new cond. in new head. */ + bsi = bsi_start (new_head); + bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT); + + /* Adjust edges appropriately to connect new head with first head + as well as second head. */ + e0 = EDGE_SUCC (new_head, 0); + e0->flags &= ~EDGE_FALLTHRU; + e0->flags |= EDGE_FALSE_VALUE; + e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE); + set_immediate_dominator (CDI_DOMINATORS, first_head, new_head); + set_immediate_dominator (CDI_DOMINATORS, second_head, new_head); + + /* Adjust loop header phi nodes. */ + lv_adjust_loop_header_phi (first_head, second_head, new_head, e1); + + return new_head; +} + +/* Main entry point for Loop Versioning transformation. + +This transformation given a condition and a loop, creates +-if (condition) { loop_copy1 } else { loop_copy2 }, +where loop_copy1 is the loop transformed in one way, and loop_copy2 +is the loop transformed in another way (or unchanged). 'condition' +may be a run time test for things that were not resolved by static +analysis (overlapping ranges (anti-aliasing), alignment, etc.). */ + +struct loop * +tree_ssa_loop_version (struct loops *loops, struct loop * loop, + tree cond_expr, basic_block *condition_bb) +{ + edge entry, latch_edge, exit, true_edge, false_edge; + basic_block first_head, second_head; + int irred_flag; + struct loop *nloop; + + /* CHECKME: Loop versioning does not handle nested loop at this point. */ + if (loop->inner) + return NULL; + + /* Record entry and latch edges for the loop */ + entry = loop_preheader_edge (loop); + + /* Note down head of loop as first_head. */ + first_head = entry->dest; + + /* Duplicate loop. */ + irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; + entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; + if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1, + NULL, NULL, NULL, NULL, 0)) + { + entry->flags |= irred_flag; + return NULL; + } + + /* After duplication entry edge now points to new loop head block. + Note down new head as second_head. */ + second_head = entry->dest; + + /* Split loop entry edge and insert new block with cond expr. */ + *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry, + cond_expr); + + latch_edge = EDGE_SUCC (loop->latch->rbi->copy, 0); + + extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge); + nloop = loopify (loops, + latch_edge, + EDGE_PRED (loop->header->rbi->copy, 0), + *condition_bb, true_edge, false_edge, + false /* Do not redirect all edges. */); + + exit = loop->single_exit; + if (exit) + nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest); + + /* loopify redirected latch_edge. Update its PENDING_STMTS. */ + flush_pending_stmts (latch_edge); + + /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */ + extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge); + flush_pending_stmts (false_edge); + + /* Adjust irreducible flag. */ + if (irred_flag) + { + (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP; + loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP; + loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP; + EDGE_PRED ((*condition_bb), 0)->flags |= EDGE_IRREDUCIBLE_LOOP; + } + + /* At this point condition_bb is loop predheader with two successors, + first_head and second_head. Make sure that loop predheader has only + one successor. */ + loop_split_edge_with (loop_preheader_edge (loop), NULL); + loop_split_edge_with (loop_preheader_edge (nloop), NULL); + + return nloop; +}