/* 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.
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"
/* 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))
/* 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;
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;
}
{
if (qt)
qt[tick] = v;
- g->vertices[v].post = tick++;
+ g->vertices[v].post = tick++;
if (!top)
break;
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)
}
/* 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);
{
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];
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. */
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;
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
{
}
}
+/* 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
/* 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. */
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);
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;
+ }
+ }
}
OSDN Git Service
