X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-loop-ch.c;h=f5aabebf9407676af3e0363e53ff87356b202546;hb=b4c8770a930c5beb405c7094d4dea99fb488ed4d;hp=ddb2438bae7d649b19e448063fe729a232952f2e;hpb=f45a1ca16b84548bea3b49f7090e5fc6affe776d;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c index ddb2438bae7..f5aabebf940 100644 --- a/gcc/tree-ssa-loop-ch.c +++ b/gcc/tree-ssa-loop-ch.c @@ -1,22 +1,21 @@ /* Loop header copying on trees. - Copyright (C) 2004 Free Software Foundation, Inc. - + Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. + This file is part of GCC. - + GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the -Free Software Foundation; either version 2, or (at your option) any +Free Software Foundation; either version 3, or (at your option) any later version. - + GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 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. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -40,7 +39,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA /* Duplicates headers of loops if they are small enough, so that the statements in the loop body are always executed when the loop is entered. This - increases effectivity of code motion optimizations, and reduces the need + increases effectiveness of code motion optimizations, and reduces the need for loop preconditioning. */ /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT @@ -51,47 +50,53 @@ static bool should_duplicate_loop_header_p (basic_block header, struct loop *loop, int *limit) { - block_stmt_iterator bsi; - tree last; + gimple_stmt_iterator bsi; + gimple last; /* Do not copy one block more than once (we do not really want to do loop peeling here). */ if (header->aux) return false; - if (!header->succ) - abort (); - if (!header->succ->succ_next) + /* Loop header copying usually increases size of the code. This used not to + be true, since quite often it is possible to verify that the condition is + satisfied in the first iteration and therefore to eliminate it. Jump + threading handles these cases now. */ + if (optimize_loop_for_size_p (loop)) return false; - if (header->succ->succ_next->succ_next) + + gcc_assert (EDGE_COUNT (header->succs) > 0); + if (single_succ_p (header)) return false; - if (flow_bb_inside_loop_p (loop, header->succ->dest) - && flow_bb_inside_loop_p (loop, header->succ->succ_next->dest)) + if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest) + && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest)) return false; /* If this is not the original loop header, we want it to have just one predecessor in order to match the && pattern. */ - if (header != loop->header - && header->pred->pred_next) + if (header != loop->header && !single_pred_p (header)) return false; last = last_stmt (header); - if (TREE_CODE (last) != COND_EXPR) + if (gimple_code (last) != GIMPLE_COND) return false; /* Approximately copy the conditions that used to be used in jump.c -- at most 20 insns and no calls. */ - for (bsi = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi)) + for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi)) { - last = bsi_stmt (bsi); + last = gsi_stmt (bsi); - if (TREE_CODE (last) == LABEL_EXPR) + if (gimple_code (last) == GIMPLE_LABEL) continue; - if (get_call_expr_in (last)) + if (is_gimple_debug (last)) + continue; + + if (is_gimple_call (last)) return false; - *limit -= estimate_num_insns (last); + *limit -= estimate_num_insns (last, &eni_size_weights); if (*limit < 0) return false; } @@ -99,137 +104,22 @@ should_duplicate_loop_header_p (basic_block header, struct loop *loop, return true; } -/* Marks variables defined in basic block BB for rewriting. */ - -static void -mark_defs_for_rewrite (basic_block bb) -{ - tree stmt, var; - block_stmt_iterator bsi; - stmt_ann_t ann; - def_optype defs; - v_may_def_optype v_may_defs; - v_must_def_optype v_must_defs; - unsigned i; - - for (stmt = phi_nodes (bb); stmt; stmt = TREE_CHAIN (stmt)) - { - var = PHI_RESULT (stmt); - bitmap_set_bit (vars_to_rename, SSA_NAME_VERSION (var)); - } - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - stmt = bsi_stmt (bsi); - get_stmt_operands (stmt); - ann = stmt_ann (stmt); - - defs = DEF_OPS (ann); - for (i = 0; i < NUM_DEFS (defs); i++) - { - var = DEF_OP (defs, i); - bitmap_set_bit (vars_to_rename, SSA_NAME_VERSION (var)); - } - - v_may_defs = V_MAY_DEF_OPS (ann); - for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) - { - var = V_MAY_DEF_RESULT (v_may_defs, i); - bitmap_set_bit (vars_to_rename, SSA_NAME_VERSION (var)); - } - - v_must_defs = V_MUST_DEF_OPS (ann); - for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++) - { - var = V_MUST_DEF_OP (v_must_defs, i); - bitmap_set_bit (vars_to_rename, SSA_NAME_VERSION (var)); - } - } -} - -/* Duplicates destinations of edges in BBS_TO_DUPLICATE. */ - -static void -duplicate_blocks (varray_type bbs_to_duplicate) -{ - unsigned i; - edge preheader_edge, e, e1; - basic_block header, new_header; - tree phi, new_phi, var; - - /* TODO: It should be quite easy to keep the dominance information - up-to-date. */ - free_dominance_info (CDI_DOMINATORS); - - for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++) - { - preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i); - header = preheader_edge->dest; - - /* It is sufficient to rewrite the definitions, since the uses of - the operands defined outside of the duplicated basic block are - still valid (every basic block that dominates the original block - also dominates the duplicate). */ - mark_defs_for_rewrite (header); - } - - for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++) - { - preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i); - header = preheader_edge->dest; - - if (!header->aux) - abort (); - header->aux = NULL; - - new_header = duplicate_block (header, preheader_edge); - - /* Create the phi nodes on on entry to new_header. */ - for (phi = phi_nodes (header), var = PENDING_STMT (preheader_edge); - phi; - phi = TREE_CHAIN (phi), var = TREE_CHAIN (var)) - { - new_phi = create_phi_node (PHI_RESULT (phi), new_header); - add_phi_arg (&new_phi, TREE_VALUE (var), preheader_edge); - } - PENDING_STMT (preheader_edge) = NULL; - - /* Add the phi arguments to the outgoing edges. */ - for (e = header->succ; e; e = e->succ_next) - { - for (e1 = new_header->succ; e1->dest != e->dest; e1 = e1->succ_next) - continue; - - for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi)) - { - tree def = PHI_ARG_DEF_FROM_EDGE (phi, e); - add_phi_arg (&phi, def, e1); - } - } - } - - calculate_dominance_info (CDI_DOMINATORS); - - rewrite_ssa_into_ssa (vars_to_rename); - bitmap_clear (vars_to_rename); -} - /* Checks whether LOOP is a do-while style loop. */ static bool do_while_loop_p (struct loop *loop) { - tree stmt = last_stmt (loop->latch); + gimple stmt = last_stmt (loop->latch); /* If the latch of the loop is not empty, it is not a do-while loop. */ if (stmt - && TREE_CODE (stmt) != LABEL_EXPR) + && gimple_code (stmt) != GIMPLE_LABEL) return false; /* If the header contains just a condition, it is not a do-while loop. */ stmt = last_and_only_stmt (loop->header); if (stmt - && TREE_CODE (stmt) == COND_EXPR) + && gimple_code (stmt) == GIMPLE_COND) return false; return true; @@ -239,36 +129,39 @@ do_while_loop_p (struct loop *loop) of the loop. This is beneficial since it increases efficiency of code motion optimizations. It also saves one jump on entry to the loop. */ -static void +static unsigned int copy_loop_headers (void) { - struct loops *loops; - unsigned i; + loop_iterator li; struct loop *loop; basic_block header; - edge preheader_edge; - varray_type bbs_to_duplicate = NULL; - - loops = loop_optimizer_init (dump_file); - if (!loops) - return; - - /* We do not try to keep the information about irreducible regions - up-to-date. */ - loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS; + edge exit, entry; + basic_block *bbs, *copied_bbs; + unsigned n_bbs; + unsigned bbs_size; + + loop_optimizer_init (LOOPS_HAVE_PREHEADERS + | LOOPS_HAVE_SIMPLE_LATCHES); + if (number_of_loops () <= 1) + { + loop_optimizer_finalize (); + return 0; + } #ifdef ENABLE_CHECKING - verify_loop_structure (loops); + verify_loop_structure (); #endif - for (i = 1; i < loops->num; i++) + bbs = XNEWVEC (basic_block, n_basic_blocks); + copied_bbs = XNEWVEC (basic_block, n_basic_blocks); + bbs_size = n_basic_blocks; + + FOR_EACH_LOOP (li, loop, 0) { /* Copy at most 20 insns. */ int limit = 20; - loop = loops->parray[i]; - preheader_edge = loop_preheader_edge (loop); - header = preheader_edge->dest; + header = loop->header; /* If the loop is already a do-while style one (either because it was written as such, or because jump threading transformed it into one), @@ -281,48 +174,87 @@ copy_loop_headers (void) like while (a && b) {...}, where we want to have both of the conditions copied. TODO -- handle while (a || b) - like cases, by not requiring the header to have just a single successor and copying up to - postdominator. - - We do not really copy the blocks immediately, so that we do not have - to worry about updating loop structures, and also so that we do not - have to rewrite variables out of and into ssa form for each block. - Instead we just record the block into worklist and duplicate all of - them at once. */ + postdominator. */ + + exit = NULL; + n_bbs = 0; while (should_duplicate_loop_header_p (header, loop, &limit)) { - if (!bbs_to_duplicate) - VARRAY_GENERIC_PTR_NOGC_INIT (bbs_to_duplicate, 10, - "bbs_to_duplicate"); - VARRAY_PUSH_GENERIC_PTR_NOGC (bbs_to_duplicate, preheader_edge); - header->aux = &header->aux; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "Scheduled basic block %d for duplication.\n", - header->index); - /* Find a successor of header that is inside a loop; i.e. the new header after the condition is copied. */ - if (flow_bb_inside_loop_p (loop, header->succ->dest)) - preheader_edge = header->succ; + if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)) + exit = EDGE_SUCC (header, 0); else - preheader_edge = header->succ->succ_next; - header = preheader_edge->dest; + exit = EDGE_SUCC (header, 1); + bbs[n_bbs++] = header; + gcc_assert (bbs_size > n_bbs); + header = exit->dest; } - } - loop_optimizer_finalize (loops, NULL); + if (!exit) + continue; - if (bbs_to_duplicate) - { - duplicate_blocks (bbs_to_duplicate); - VARRAY_FREE (bbs_to_duplicate); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Duplicating header of the loop %d up to edge %d->%d.\n", + loop->num, exit->src->index, exit->dest->index); + + /* Ensure that the header will have just the latch as a predecessor + inside the loop. */ + if (!single_pred_p (exit->dest)) + exit = single_pred_edge (split_edge (exit)); + + entry = loop_preheader_edge (loop); + + if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs)) + { + fprintf (dump_file, "Duplication failed.\n"); + continue; + } + + /* If the loop has the form "for (i = j; i < j + 10; i++)" then + this copying can introduce a case where we rely on undefined + signed overflow to eliminate the preheader condition, because + we assume that "j < j + 10" is true. We don't want to warn + about that case for -Wstrict-overflow, because in general we + don't warn about overflow involving loops. Prevent the + warning by setting the no_warning flag in the condition. */ + if (warn_strict_overflow > 0) + { + unsigned int i; + + for (i = 0; i < n_bbs; ++i) + { + gimple_stmt_iterator bsi; + + for (bsi = gsi_start_bb (copied_bbs[i]); + !gsi_end_p (bsi); + gsi_next (&bsi)) + { + gimple stmt = gsi_stmt (bsi); + if (gimple_code (stmt) == GIMPLE_COND) + gimple_set_no_warning (stmt, true); + else if (is_gimple_assign (stmt)) + { + enum tree_code rhs_code = gimple_assign_rhs_code (stmt); + if (TREE_CODE_CLASS (rhs_code) == tcc_comparison) + gimple_set_no_warning (stmt, true); + } + } + } + } + + /* Ensure that the latch and the preheader is simple (we know that they + are not now, since there was the loop exit condition. */ + split_edge (loop_preheader_edge (loop)); + split_edge (loop_latch_edge (loop)); } - /* Run cleanup_tree_cfg here regardless of whether we have done anything, so - that we cleanup the blocks created in order to get the loops into a - canonical shape. */ - cleanup_tree_cfg (); + free (bbs); + free (copied_bbs); + + loop_optimizer_finalize (); + return 0; } static bool @@ -331,8 +263,10 @@ gate_ch (void) return flag_tree_ch != 0; } -struct tree_opt_pass pass_ch = +struct gimple_opt_pass pass_ch = { + { + GIMPLE_PASS, "ch", /* name */ gate_ch, /* gate */ copy_loop_headers, /* execute */ @@ -340,10 +274,11 @@ struct tree_opt_pass pass_ch = NULL, /* next */ 0, /* static_pass_number */ TV_TREE_CH, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - (TODO_dump_func - | TODO_verify_ssa) /* todo_flags_finish */ + TODO_cleanup_cfg | TODO_dump_func + | TODO_verify_ssa /* todo_flags_finish */ + } };