/* Natural loop analysis code for GNU compiler.
- Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004, 2005 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"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
+#include "obstack.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "expr.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))
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;
}
/* All edges should lead from a component with higher number to the
one with lower one. */
- if (g->vertices[e->src].component < g->vertices[e->dest].component)
- abort ();
+ gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component);
if (g->vertices[e->src].component != g->vertices[e->dest].component)
return;
{
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 *queue1 = XNEWVEC (int, last_basic_block + loops->num);
+ int *queue2 = XNEWVEC (int, last_basic_block + loops->num);
int nq, depth;
struct loop *cloop;
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
act->flags &= ~BB_IRREDUCIBLE_LOOP;
- for (e = act->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, act->succs)
e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
g = new_graph (last_basic_block + loops->num);
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- for (e = act->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, act->succs)
{
/* Ignore edges to exit. */
if (e->dest == EXIT_BLOCK_PTR)
expected_loop_iterations (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 = 0;
count_latch = 0;
- for (e = loop->header->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, loop->header->preds)
if (e->src == loop->latch)
count_latch = e->count;
else
count_in += e->count;
if (count_in == 0)
- return 0;
-
- expected = (count_latch + count_in - 1) / count_in;
+ expected = count_latch * 2;
+ else
+ expected = (count_latch + count_in - 1) / count_in;
/* Avoid overflows. */
return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
freq_in = 0;
freq_latch = 0;
- for (e = loop->header->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, loop->header->preds)
if (e->src == loop->latch)
freq_latch = EDGE_FREQUENCY (e);
else
freq_in += EDGE_FREQUENCY (e);
if (freq_in == 0)
- return 0;
+ return freq_latch * 2;
return (freq_latch + freq_in - 1) / freq_in;
}
}
return mx;
}
+
+/* Returns estimate on cost of computing SEQ. */
+
+static unsigned
+seq_cost (rtx seq)
+{
+ unsigned cost = 0;
+ rtx set;
+
+ for (; seq; seq = NEXT_INSN (seq))
+ {
+ set = single_set (seq);
+ if (set)
+ cost += rtx_cost (set, SET);
+ else
+ cost++;
+ }
+
+ return cost;
+}
+
+/* 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. */
+
+/* Initialize the constants for computing set costs. */
+
+void
+init_set_costs (void)
+{
+ rtx seq;
+ rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
+ rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
+ rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
+ rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
+ unsigned i;
+
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
+ && !fixed_regs[i])
+ target_avail_regs++;
+
+ target_res_regs = 3;
+
+ /* These are really just heuristic values. */
+
+ 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;
+
+ start_sequence ();
+ emit_move_insn (mem, reg1);
+ emit_move_insn (reg2, mem);
+ seq = get_insns ();
+ end_sequence ();
+ 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. */
+
+unsigned
+global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses)
+{
+ unsigned regs_needed = regs_used + size;
+ unsigned cost = 0;
+
+ 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
+ {
+ cost += target_pres_cost * size;
+ cost += target_spill_cost * n_uses * (regs_needed - target_avail_regs) / regs_needed;
+ }
+
+ return cost;
+}
+
+/* Sets EDGE_LOOP_EXIT flag for all exits of LOOPS. */
+
+void
+mark_loop_exit_edges (struct loops *loops)
+{
+ basic_block bb;
+ edge e;
+
+ if (loops->num <= 1)
+ return;
+
+ FOR_EACH_BB (bb)
+ {
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (bb->loop_father->outer
+ && loop_exit_edge_p (bb->loop_father, e))
+ e->flags |= EDGE_LOOP_EXIT;
+ else
+ e->flags &= ~EDGE_LOOP_EXIT;
+ }
+ }
+}
+
OSDN Git Service
