X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcfgloopanal.c;h=54d00ce574c7b887a7cdd4e93ac53fcc76fa9a65;hb=49e5b7e86b335f72fe60bdc578efd3bc1ffc5d5d;hp=6c625d6a9741fec7fa916eef7ef45b27b34bde43;hpb=42fe97ed1a1d59a2d77f80a2823ec938a94ecc7b;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c index 6c625d6a974..54d00ce574c 100644 --- a/gcc/cfgloopanal.c +++ b/gcc/cfgloopanal.c @@ -1,5 +1,5 @@ /* Natural loop analysis code for GNU compiler. - Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005, 2006 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" @@ -33,7 +33,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA /* Checks whether BB is executed exactly once in each LOOP iteration. */ bool -just_once_each_iteration_p (struct loop *loop, basic_block bb) +just_once_each_iteration_p (const struct loop *loop, basic_block bb) { /* It must be executed at least once each iteration. */ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) @@ -83,7 +83,9 @@ struct graph /* Dumps graph G into F. */ extern void dump_graph (FILE *, struct graph *); -void dump_graph (FILE *f, struct graph *g) + +void +dump_graph (FILE *f, struct graph *g) { int i; struct edge *e; @@ -111,10 +113,10 @@ void dump_graph (FILE *f, struct graph *g) static struct graph * new_graph (int n_vertices) { - struct graph *g = xmalloc (sizeof (struct graph)); + struct graph *g = XNEW (struct graph); g->n_vertices = n_vertices; - g->vertices = xcalloc (n_vertices, sizeof (struct vertex)); + g->vertices = XCNEWVEC (struct vertex, n_vertices); return g; } @@ -178,7 +180,7 @@ dfs (struct graph *g, int *qs, int nq, int *qt, bool forward) { if (qt) qt[tick] = v; - g->vertices[v].post = tick++; + g->vertices[v].post = tick++; if (!top) break; @@ -257,24 +259,27 @@ free_graph (struct graph *g) for parts of cycles that only "pass" through some loop -- i.e. for each cycle, we want to mark blocks that belong directly to innermost loop containing the whole cycle. - + LOOPS is the loop tree. */ #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block) #define BB_REPR(BB) ((BB)->index + 1) void -mark_irreducible_loops (struct loops *loops) +mark_irreducible_loops (void) { basic_block act; edge e; edge_iterator ei; int i, src, dest; struct graph *g; - int *queue1 = xmalloc ((last_basic_block + loops->num) * sizeof (int)); - int *queue2 = xmalloc ((last_basic_block + loops->num) * sizeof (int)); - int nq, depth; - struct loop *cloop; + int num = current_loops ? number_of_loops () : 1; + int *queue1 = XNEWVEC (int, last_basic_block + num); + int *queue2 = XNEWVEC (int, last_basic_block + num); + int nq; + unsigned depth; + struct loop *cloop, *loop; + loop_iterator li; /* Reset the flags. */ FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) @@ -285,44 +290,48 @@ mark_irreducible_loops (struct loops *loops) } /* Create the edge lists. */ - g = new_graph (last_basic_block + loops->num); + g = new_graph (last_basic_block + num); FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) FOR_EACH_EDGE (e, ei, act->succs) { - /* Ignore edges to exit. */ - if (e->dest == EXIT_BLOCK_PTR) + /* Ignore edges to exit. */ + if (e->dest == EXIT_BLOCK_PTR) continue; - /* And latch edges. */ - if (e->dest->loop_father->header == e->dest - && e->dest->loop_father->latch == act) - continue; - - /* Edges inside a single loop should be left where they are. Edges - to subloop headers should lead to representative of the subloop, - but from the same place. - - Edges exiting loops should lead from representative - of the son of nearest common ancestor of the loops in that - act lays. */ - src = BB_REPR (act); dest = BB_REPR (e->dest); - if (e->dest->loop_father->header == e->dest) - dest = LOOP_REPR (e->dest->loop_father); - - if (!flow_bb_inside_loop_p (act->loop_father, e->dest)) + if (current_loops) { - depth = find_common_loop (act->loop_father, - e->dest->loop_father)->depth + 1; - if (depth == act->loop_father->depth) - cloop = act->loop_father; - else - cloop = act->loop_father->pred[depth]; - - src = LOOP_REPR (cloop); + /* Ignore latch edges. */ + if (e->dest->loop_father->header == e->dest + && e->dest->loop_father->latch == act) + continue; + + /* Edges inside a single loop should be left where they are. Edges + to subloop headers should lead to representative of the subloop, + but from the same place. + + Edges exiting loops should lead from representative + of the son of nearest common ancestor of the loops in that + act lays. */ + + if (e->dest->loop_father->header == e->dest) + dest = LOOP_REPR (e->dest->loop_father); + + if (!flow_bb_inside_loop_p (act->loop_father, e->dest)) + { + depth = 1 + loop_depth (find_common_loop (act->loop_father, + e->dest->loop_father)); + if (depth == loop_depth (act->loop_father)) + cloop = act->loop_father; + else + cloop = VEC_index (loop_p, act->loop_father->superloops, + depth); + + src = LOOP_REPR (cloop); + } } add_edge (g, src, dest, e); @@ -337,9 +346,14 @@ mark_irreducible_loops (struct loops *loops) { queue1[nq++] = BB_REPR (act); } - for (i = 1; i < (int) loops->num; i++) - if (loops->parray[i]) - queue1[nq++] = LOOP_REPR (loops->parray[i]); + + if (current_loops) + { + FOR_EACH_LOOP (li, loop, 0) + { + queue1[nq++] = LOOP_REPR (loop); + } + } dfs (g, queue1, nq, queue2, false); for (i = 0; i < nq; i++) queue1[i] = queue2[nq - i - 1]; @@ -352,7 +366,8 @@ mark_irreducible_loops (struct loops *loops) free (queue1); free (queue2); - loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS; + if (current_loops) + current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS; } /* Counts number of insns inside LOOP. */ @@ -410,16 +425,17 @@ average_num_loop_insns (struct loop *loop) return ninsns; } -/* Returns expected number of LOOP iterations. - Compute upper bound on number of iterations in case they do not fit integer - to help loop peeling heuristics. Use exact counts if at all possible. */ -unsigned -expected_loop_iterations (const struct loop *loop) +/* Returns expected number of iterations of LOOP, according to + measured or guessed profile. No bounding is done on the + value. */ + +gcov_type +expected_loop_iterations_unbounded (const struct loop *loop) { edge e; edge_iterator ei; - if (loop->header->count) + if (loop->latch->count || loop->header->count) { gcov_type count_in, count_latch, expected; @@ -433,12 +449,11 @@ expected_loop_iterations (const struct loop *loop) count_in += e->count; if (count_in == 0) - expected = count_latch * 2; + expected = count_latch * 2; else - expected = (count_latch + count_in - 1) / count_in; + expected = (count_latch + count_in - 1) / count_in; - /* Avoid overflows. */ - return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); + return expected; } else { @@ -460,6 +475,16 @@ expected_loop_iterations (const struct loop *loop) } } +/* Returns expected number of LOOP iterations. The returned value is bounded + by REG_BR_PROB_BASE. */ + +unsigned +expected_loop_iterations (const struct loop *loop) +{ + gcov_type expected = expected_loop_iterations_unbounded (loop); + return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); +} + /* Returns the maximum level of nesting of subloops of LOOP. */ unsigned @@ -500,11 +525,13 @@ seq_cost (rtx seq) /* The properties of the target. */ unsigned target_avail_regs; /* Number of available registers. */ -unsigned target_res_regs; /* Number of reserved registers. */ -unsigned target_small_cost; /* The cost for register when there is a free one. */ -unsigned target_pres_cost; /* The cost for register when there are not too many - free ones. */ -unsigned target_spill_cost; /* The cost for register when we need to spill. */ +unsigned target_res_regs; /* Number of registers reserved for temporary + expressions. */ +unsigned target_reg_cost; /* The cost for register when there still + is some reserve, but we are approaching + the number of available registers. */ +unsigned target_spill_cost; /* The cost for register when we need + to spill. */ /* Initialize the constants for computing set costs. */ @@ -525,14 +552,20 @@ init_set_costs (void) target_res_regs = 3; - /* These are really just heuristic values. */ - + /* Set up the costs for using extra registers: + + 1) If not many free registers remain, we should prefer having an + additional move to decreasing the number of available registers. + (TARGET_REG_COST). + 2) If no registers are available, we need to spill, which may require + storing the old value to memory and loading it back + (TARGET_SPILL_COST). */ + start_sequence (); emit_move_insn (reg1, reg2); seq = get_insns (); end_sequence (); - target_small_cost = seq_cost (seq); - target_pres_cost = 2 * target_small_cost; + target_reg_cost = seq_cost (seq); start_sequence (); emit_move_insn (mem, reg1); @@ -542,26 +575,51 @@ init_set_costs (void) target_spill_cost = seq_cost (seq); } -/* Calculates cost for having SIZE new loop global variables. REGS_USED is the - number of global registers used in loop. N_USES is the number of relevant - variable uses. */ +/* Estimates cost of increased register pressure caused by making N_NEW new + registers live around the loop. N_OLD is the number of registers live + around the loop. */ unsigned -global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses) +estimate_reg_pressure_cost (unsigned n_new, unsigned n_old) { - unsigned regs_needed = regs_used + size; - unsigned cost = 0; + unsigned regs_needed = n_new + n_old; + /* If we have enough registers, we should use them and not restrict + the transformations unnecessarily. */ if (regs_needed + target_res_regs <= target_avail_regs) - cost += target_small_cost * size; - else if (regs_needed <= target_avail_regs) - cost += target_pres_cost * size; - else + return 0; + + /* If we are close to running out of registers, try to preserve them. */ + if (regs_needed <= target_avail_regs) + return target_reg_cost * n_new; + + /* If we run out of registers, it is very expensive to add another one. */ + return target_spill_cost * n_new; +} + +/* Sets EDGE_LOOP_EXIT flag for all loop exits. */ + +void +mark_loop_exit_edges (void) +{ + basic_block bb; + edge e; + + if (!current_loops) + return; + + FOR_EACH_BB (bb) { - cost += target_pres_cost * size; - cost += target_spill_cost * n_uses * (regs_needed - target_avail_regs) / regs_needed; - } + edge_iterator ei; - return cost; + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (loop_outer (bb->loop_father) + && loop_exit_edge_p (bb->loop_father, e)) + e->flags |= EDGE_LOOP_EXIT; + else + e->flags &= ~EDGE_LOOP_EXIT; + } + } }