/* Natural loop analysis code for GNU compiler.
- Copyright (C) 2002, 2003 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
static rtx test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT);
static bool constant_iterations (struct loop_desc *, unsigned HOST_WIDE_INT *,
bool *);
-static bool simple_loop_exit_p (struct loops *, struct loop *, edge, regset,
+static bool simple_loop_exit_p (struct loop *, edge, regset,
rtx *, struct loop_desc *);
static rtx variable_initial_value (rtx, regset, rtx, rtx *, enum machine_mode);
static rtx variable_initial_values (edge, rtx, enum machine_mode);
static bool simple_condition_p (struct loop *, rtx, regset,
struct loop_desc *);
-static basic_block simple_increment (struct loops *, struct loop *, rtx *,
- struct loop_desc *);
+static basic_block simple_increment (struct loop *, rtx *, struct loop_desc *);
static rtx count_strange_loop_iterations (rtx, rtx, enum rtx_code,
int, rtx, enum machine_mode,
enum machine_mode);
/* Checks whether BB is executed exactly once in each LOOP iteration. */
bool
-just_once_each_iteration_p (struct loops *loops, struct loop *loop, basic_block bb)
+just_once_each_iteration_p (struct loop *loop, basic_block bb)
{
/* It must be executed at least once each iteration. */
- if (!dominated_by_p (loops->cfg.dom, loop->latch, bb))
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
return false;
/* And just once. */
iteration. Fills in DESC->stride and returns block in that DESC->var is
modified. */
static basic_block
-simple_increment (struct loops *loops, struct loop *loop,
- rtx *simple_increment_regs, struct loop_desc *desc)
+simple_increment (struct loop *loop, rtx *simple_increment_regs,
+ struct loop_desc *desc)
{
rtx mod_insn, mod_insn1, set, set_src, set_add;
basic_block mod_bb, mod_bb1;
mod_bb = BLOCK_FOR_INSN (mod_insn);
/* Check that it is executed exactly once each iteration. */
- if (!just_once_each_iteration_p (loops, loop, mod_bb))
+ if (!just_once_each_iteration_p (loop, mod_bb))
return NULL;
/* mod_insn must be a simple increment/decrement. */
return NULL;
mod_bb1 = BLOCK_FOR_INSN (mod_insn1);
- if (!dominated_by_p (loops->cfg.dom, mod_bb, mod_bb1))
+ if (!dominated_by_p (CDI_DOMINATORS, mod_bb, mod_bb1))
return NULL;
if (mod_bb1 == mod_bb)
{
}
}
- if (rtl_dump_file)
+ if (dump_file)
{
- fprintf (rtl_dump_file, "; Number of iterations: ");
- print_simple_rtl (rtl_dump_file, exp);
- fprintf (rtl_dump_file, "\n");
+ fprintf (dump_file, "; Number of iterations: ");
+ print_simple_rtl (dump_file, exp);
+ fprintf (dump_file, "\n");
}
return exp;
exp = simplify_gen_relational (cond, SImode,
GET_MODE (desc->var), exp, desc->lim);
- if (rtl_dump_file)
+ if (dump_file)
{
- fprintf (rtl_dump_file, "; Conditional to continue loop at "
+ fprintf (dump_file, "; Conditional to continue loop at "
HOST_WIDE_INT_PRINT_UNSIGNED "th iteration: ", iter);
- print_simple_rtl (rtl_dump_file, exp);
- fprintf (rtl_dump_file, "\n");
+ print_simple_rtl (dump_file, exp);
+ fprintf (dump_file, "\n");
}
return exp;
}
description joined to it in in DESC. INVARIANT_REGS and SINGLE_SET_REGS
are results of blocks_{invariant,single_set}_regs over BODY. */
static bool
-simple_loop_exit_p (struct loops *loops, struct loop *loop, edge exit_edge,
+simple_loop_exit_p (struct loop *loop, edge exit_edge,
regset invariant_regs, rtx *single_set_regs,
struct loop_desc *desc)
{
return false;
/* It must be tested (at least) once during any iteration. */
- if (!dominated_by_p (loops->cfg.dom, loop->latch, exit_bb))
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
return false;
/* It must end in a simple conditional jump. */
/* Var must be simply incremented or decremented in exactly one insn that
is executed just once every iteration. */
- if (!(mod_bb = simple_increment (loops, loop, single_set_regs, desc)))
+ if (!(mod_bb = simple_increment (loop, single_set_regs, desc)))
return false;
/* OK, it is simple loop. Now just fill in remaining info. */
- desc->postincr = !dominated_by_p (loops->cfg.dom, exit_bb, mod_bb);
+ desc->postincr = !dominated_by_p (CDI_DOMINATORS, exit_bb, mod_bb);
desc->neg = !fallthru_out;
/* Find initial value of var and alternative values for lim. */
/* Tests whether LOOP is simple for loop. Returns simple loop description
in DESC. */
bool
-simple_loop_p (struct loops *loops, struct loop *loop, struct loop_desc *desc)
+simple_loop_p (struct loop *loop, struct loop_desc *desc)
{
unsigned i;
basic_block *body;
{
for (e = body[i]->succ; e; e = e->succ_next)
if (!flow_bb_inside_loop_p (loop, e->dest)
- && simple_loop_exit_p (loops, loop, e,
+ && simple_loop_exit_p (loop, e,
invariant_regs, single_set_regs, &act))
{
/* Prefer constant iterations; the less the better. */
}
desc->n_branches = n_branches;
- if (rtl_dump_file && any)
+ if (dump_file && any)
{
- fprintf (rtl_dump_file, "; Simple loop %i\n", loop->num);
+ fprintf (dump_file, "; Simple loop %i\n", loop->num);
if (desc->postincr)
- fprintf (rtl_dump_file,
+ fprintf (dump_file,
"; does postincrement after loop exit condition\n");
- fprintf (rtl_dump_file, "; Induction variable:");
- print_simple_rtl (rtl_dump_file, desc->var);
- fputc ('\n', rtl_dump_file);
+ fprintf (dump_file, "; Induction variable:");
+ print_simple_rtl (dump_file, desc->var);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Initial values:");
- print_simple_rtl (rtl_dump_file, desc->var_alts);
- fputc ('\n', rtl_dump_file);
+ fprintf (dump_file, "; Initial values:");
+ print_simple_rtl (dump_file, desc->var_alts);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Stride:");
- print_simple_rtl (rtl_dump_file, desc->stride);
- fputc ('\n', rtl_dump_file);
+ fprintf (dump_file, "; Stride:");
+ print_simple_rtl (dump_file, desc->stride);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Compared with:");
- print_simple_rtl (rtl_dump_file, desc->lim);
- fputc ('\n', rtl_dump_file);
+ fprintf (dump_file, "; Compared with:");
+ print_simple_rtl (dump_file, desc->lim);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Alternative values:");
- print_simple_rtl (rtl_dump_file, desc->lim_alts);
- fputc ('\n', rtl_dump_file);
+ fprintf (dump_file, "; Alternative values:");
+ print_simple_rtl (dump_file, desc->lim_alts);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Exit condition:");
+ fprintf (dump_file, "; Exit condition:");
if (desc->neg)
- fprintf (rtl_dump_file, "(negated)");
- fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
+ fprintf (dump_file, "(negated)");
+ fprintf (dump_file, "%s\n", GET_RTX_NAME (desc->cond));
- fprintf (rtl_dump_file, "; Number of branches:");
- fprintf (rtl_dump_file, "%d\n", desc->n_branches);
+ fprintf (dump_file, "; Number of branches:");
+ fprintf (dump_file, "%d\n", desc->n_branches);
- fputc ('\n', rtl_dump_file);
+ fputc ('\n', dump_file);
}
free (body);
return any;
}
+/* Structure representing edge of a graph. */
+
+struct edge
+{
+ int src, dest; /* Source and destination. */
+ struct edge *pred_next, *succ_next;
+ /* Next edge in predecessor and successor lists. */
+ void *data; /* Data attached to the edge. */
+};
+
+/* Structure representing vertex of a graph. */
+
+struct vertex
+{
+ struct edge *pred, *succ;
+ /* Lists of predecessors and successors. */
+ int component; /* Number of dfs restarts before reaching the
+ vertex. */
+ int post; /* Postorder number. */
+};
+
+/* Structure representing a graph. */
+
+struct graph
+{
+ int n_vertices; /* Number of vertices. */
+ struct vertex *vertices;
+ /* The vertices. */
+};
+
+/* Dumps graph G into F. */
+
+extern void dump_graph (FILE *, struct graph *);
+void dump_graph (FILE *f, struct graph *g)
+{
+ int i;
+ struct edge *e;
+
+ for (i = 0; i < g->n_vertices; i++)
+ {
+ if (!g->vertices[i].pred
+ && !g->vertices[i].succ)
+ continue;
+
+ fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
+ for (e = g->vertices[i].pred; e; e = e->pred_next)
+ fprintf (f, " %d", e->src);
+ fprintf (f, "\n");
+
+ fprintf (f, "\t->");
+ for (e = g->vertices[i].succ; e; e = e->succ_next)
+ fprintf (f, " %d", e->dest);
+ fprintf (f, "\n");
+ }
+}
+
+/* Creates a new graph with N_VERTICES vertices. */
+
+static struct graph *
+new_graph (int n_vertices)
+{
+ struct graph *g = xmalloc (sizeof (struct graph));
+
+ g->n_vertices = n_vertices;
+ g->vertices = xcalloc (n_vertices, sizeof (struct vertex));
+
+ return g;
+}
+
+/* Adds an edge from F to T to graph G, with DATA attached. */
+
+static void
+add_edge (struct graph *g, int f, int t, void *data)
+{
+ struct edge *e = xmalloc (sizeof (struct edge));
+
+ e->src = f;
+ e->dest = t;
+ e->data = data;
+
+ e->pred_next = g->vertices[t].pred;
+ g->vertices[t].pred = e;
+
+ e->succ_next = g->vertices[f].succ;
+ g->vertices[f].succ = e;
+}
+
+/* Runs dfs search over vertices of G, from NQ vertices in queue QS.
+ The vertices in postorder are stored into QT. If FORWARD is false,
+ backward dfs is run. */
+
+static void
+dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
+{
+ int i, tick = 0, v, comp = 0, top;
+ struct edge *e;
+ struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices);
+
+ for (i = 0; i < g->n_vertices; i++)
+ {
+ g->vertices[i].component = -1;
+ g->vertices[i].post = -1;
+ }
+
+#define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
+#define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
+#define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
+#define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
+
+ for (i = 0; i < nq; i++)
+ {
+ v = qs[i];
+ if (g->vertices[v].post != -1)
+ continue;
+
+ g->vertices[v].component = comp++;
+ e = FST_EDGE (v);
+ top = 0;
+
+ while (1)
+ {
+ while (e && g->vertices[EDGE_DEST (e)].component != -1)
+ e = NEXT_EDGE (e);
+
+ if (!e)
+ {
+ if (qt)
+ qt[tick] = v;
+ g->vertices[v].post = tick++;
+
+ if (!top)
+ break;
+
+ e = stack[--top];
+ v = EDGE_SRC (e);
+ e = NEXT_EDGE (e);
+ continue;
+ }
+
+ stack[top++] = e;
+ v = EDGE_DEST (e);
+ e = FST_EDGE (v);
+ g->vertices[v].component = comp - 1;
+ }
+ }
+
+ free (stack);
+}
+
+/* Marks the edge E in graph G irreducible if it connects two vertices in the
+ same scc. */
+
+static void
+check_irred (struct graph *g, struct edge *e)
+{
+ edge real = e->data;
+
+ /* 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 ();
+
+ if (g->vertices[e->src].component != g->vertices[e->dest].component)
+ return;
+
+ real->flags |= EDGE_IRREDUCIBLE_LOOP;
+ if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
+ real->src->flags |= BB_IRREDUCIBLE_LOOP;
+}
+
+/* Runs CALLBACK for all edges in G. */
+
+static void
+for_each_edge (struct graph *g,
+ void (callback) (struct graph *, struct edge *))
+{
+ struct edge *e;
+ int i;
+
+ for (i = 0; i < g->n_vertices; i++)
+ for (e = g->vertices[i].succ; e; e = e->succ_next)
+ callback (g, e);
+}
+
+/* Releases the memory occupied by G. */
+
+static void
+free_graph (struct graph *g)
+{
+ struct edge *e, *n;
+ int i;
+
+ for (i = 0; i < g->n_vertices; i++)
+ for (e = g->vertices[i].succ; e; e = n)
+ {
+ n = e->succ_next;
+ free (e);
+ }
+ free (g->vertices);
+ free (g);
+}
+
/* Marks blocks and edges that are part of non-recognized loops; i.e. we
throw away all latch edges and mark blocks inside any remaining cycle.
Everything is a bit complicated due to fact we do not want to do this
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. */
+ 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)
{
- int *dfs_in, *closed, *mr, *mri, *n_edges, *stack;
- unsigned i;
- edge **edges, e;
- edge *estack;
basic_block act;
- int stack_top, tick, depth;
+ edge e;
+ 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;
/* Reset the flags. */
e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
- /* The first last_basic_block + 1 entries are for real blocks (including
- entry); then we have loops->num - 1 fake blocks for loops to that we
- assign edges leading from loops (fake loop 0 is not interesting). */
- dfs_in = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- closed = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- mr = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- mri = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- n_edges = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- edges = xmalloc ((last_basic_block + loops->num) * sizeof (edge *));
- stack = xmalloc ((n_basic_blocks + loops->num) * sizeof (int));
- estack = xmalloc ((n_basic_blocks + loops->num) * sizeof (edge));
-
/* Create the edge lists. */
- for (i = 0; i < last_basic_block + loops->num; i++)
- n_edges[i] = 0;
+ 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)
{
/* 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. */
- if (act->loop_father == e->dest->loop_father
- || act->loop_father == e->dest->loop_father->outer)
- {
- n_edges[act->index + 1]++;
- continue;
- }
- /* Edges exiting loops remain. They should lead from representative
+ 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. */
- 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];
- n_edges[cloop->num + last_basic_block]++;
- }
- for (i = 0; i < last_basic_block + loops->num; i++)
- {
- edges[i] = xmalloc (n_edges[i] * sizeof (edge));
- n_edges[i] = 0;
- }
+ src = BB_REPR (act);
+ dest = BB_REPR (e->dest);
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- for (e = act->succ; e; e = e->succ_next)
- {
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
- if (e->dest->loop_father->header == e->dest
- && e->dest->loop_father->latch == act)
- continue;
- if (act->loop_father == e->dest->loop_father
- || act->loop_father == e->dest->loop_father->outer)
+ 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))
{
- edges[act->index + 1][n_edges[act->index + 1]++] = e;
- continue;
+ 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);
}
- 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];
- i = cloop->num + last_basic_block;
- edges[i][n_edges[i]++] = e;
+
+ add_edge (g, src, dest, e);
}
- /* Compute dfs numbering, starting from loop headers, and mark found
- loops. */
- tick = 0;
- for (i = 0; i < last_basic_block + loops->num; i++)
+ /* Find the strongly connected components. Use the algorithm of Tarjan --
+ first determine the postorder dfs numbering in reversed graph, then
+ run the dfs on the original graph in the order given by decreasing
+ numbers assigned by the previous pass. */
+ nq = 0;
+ FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
- dfs_in[i] = -1;
- closed[i] = 0;
- mr[i] = last_basic_block + loops->num;
- mri[i] = -1;
+ queue1[nq++] = BB_REPR (act);
}
-
- stack_top = 0;
- for (i = 0; i < loops->num; i++)
+ for (i = 1; i < (int) loops->num; i++)
if (loops->parray[i])
- {
- stack[stack_top] = loops->parray[i]->header->index + 1;
- estack[stack_top] = NULL;
- stack_top++;
- }
+ queue1[nq++] = LOOP_REPR (loops->parray[i]);
+ dfs (g, queue1, nq, queue2, false);
+ for (i = 0; i < nq; i++)
+ queue1[i] = queue2[nq - i - 1];
+ dfs (g, queue1, nq, NULL, true);
- while (stack_top)
- {
- int idx, sidx;
+ /* Mark the irreducible loops. */
+ for_each_edge (g, check_irred);
- idx = stack[stack_top - 1];
- if (dfs_in[idx] < 0)
- dfs_in[idx] = tick++;
+ free_graph (g);
+ free (queue1);
+ free (queue2);
- while (n_edges[idx])
- {
- e = edges[idx][--n_edges[idx]];
- sidx = e->dest->loop_father->header == e->dest
- ? e->dest->loop_father->num + last_basic_block
- : e->dest->index + 1;
- if (closed[sidx])
- {
- if (mri[sidx] != -1 && !closed[mri[sidx]])
- {
- if (mr[sidx] < mr[idx])
- {
- mr[idx] = mr[sidx];
- mri[idx] = mri[sidx];
- }
-
- if (mr[sidx] <= dfs_in[idx])
- e->flags |= EDGE_IRREDUCIBLE_LOOP;
- }
- continue;
- }
- if (dfs_in[sidx] < 0)
- {
- stack[stack_top] = sidx;
- estack[stack_top] = e;
- stack_top++;
- goto next;
- }
- if (dfs_in[sidx] < mr[idx])
- {
- mr[idx] = dfs_in[sidx];
- mri[idx] = sidx;
- }
- e->flags |= EDGE_IRREDUCIBLE_LOOP;
- }
-
- /* Return back. */
- closed[idx] = 1;
- e = estack[stack_top - 1];
- stack_top--;
- if (e)
- {
- /* Propagate information back. */
- sidx = stack[stack_top - 1];
- if (mr[sidx] > mr[idx])
- {
- mr[sidx] = mr[idx];
- mri[sidx] = mri[idx];
- }
- if (mr[idx] <= dfs_in[sidx])
- e->flags |= EDGE_IRREDUCIBLE_LOOP;
- }
- /* Mark the block if relevant. */
- if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx])
- BASIC_BLOCK (idx - 1)->flags |= BB_IRREDUCIBLE_LOOP;
-next:;
- }
-
- free (stack);
- free (estack);
- free (dfs_in);
- free (closed);
- free (mr);
- free (mri);
- for (i = 0; i < last_basic_block + loops->num; i++)
- free (edges[i]);
- free (edges);
- free (n_edges);
loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
}
OSDN Git Service
