/* Natural loop discovery code for GNU compiler.
- Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007
+ Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2010
Free Software Foundation, Inc.
This file is part of GCC.
#include "obstack.h"
#include "function.h"
#include "basic-block.h"
-#include "toplev.h"
#include "cfgloop.h"
+#include "diagnostic-core.h"
#include "flags.h"
#include "tree.h"
#include "tree-flow.h"
{
fprintf (file, "multiple latches:");
latches = get_loop_latch_edges (loop);
- for (i = 0; VEC_iterate (edge, latches, i, e); i++)
+ FOR_EACH_VEC_ELT (edge, latches, i, e)
fprintf (file, " %d", e->src->index);
VEC_free (edge, heap, latches);
fprintf (file, "\n");
loop_p loop;
/* Free the loop descriptors. */
- for (i = 0; VEC_iterate (loop_p, loops->larray, i, loop); i++)
+ FOR_EACH_VEC_ELT (loop_p, loops->larray, i, loop)
{
if (!loop)
continue;
VEC_truncate (loop_p, loop->superloops, 0);
VEC_reserve (loop_p, gc, loop->superloops, depth);
- for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++)
+ FOR_EACH_VEC_ELT (loop_p, father->superloops, i, ploop)
VEC_quick_push (loop_p, loop->superloops, ploop);
VEC_quick_push (loop_p, loop->superloops, father);
struct loop *
alloc_loop (void)
{
- struct loop *loop = GGC_CNEW (struct loop);
+ struct loop *loop = ggc_alloc_cleared_loop ();
- loop->exits = GGC_CNEW (struct loop_exit);
+ loop->exits = ggc_alloc_cleared_loop_exit ();
loop->exits->next = loop->exits->prev = loop->exits;
+ loop->can_be_parallel = false;
return loop;
}
/* If we have an abnormal predecessor, do not consider the
loop (not worth the problems). */
- FOR_EACH_EDGE (e, ei, header->preds)
- if (e->flags & EDGE_ABNORMAL)
- break;
- if (e)
+ if (bb_has_abnormal_pred (header))
continue;
FOR_EACH_EDGE (e, ei, header->preds)
profile is usually too flat and unreliable for this (and it is mostly based
on the loop structure of the program, so it does not make much sense to
derive the loop structure from it). */
-
+
static edge
find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches)
{
edge e, me = NULL;
gcov_type mcount = 0, tcount = 0;
- for (i = 0; VEC_iterate (edge, latches, i, e); i++)
+ FOR_EACH_VEC_ELT (edge, latches, i, e)
{
if (e->count > mcount)
{
latch = e;
/* Verify that it dominates all the latch edges. */
- for (i = 0; VEC_iterate (edge, latches, i, e); i++)
+ FOR_EACH_VEC_ELT (edge, latches, i, e)
if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
return NULL;
if (!bb || !flow_bb_inside_loop_p (loop, bb))
continue;
- for (i = 0; VEC_iterate (edge, latches, i, e); i++)
+ FOR_EACH_VEC_ELT (edge, latches, i, e)
if (e != latch
&& PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
return NULL;
edge_iterator ei;
edge e, new_entry;
struct loop *new_loop;
-
+
mfb_reis_set = pointer_set_create ();
FOR_EACH_EDGE (e, ei, loop->header->preds)
{
fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
mfb_reis_set = pointer_set_create ();
- for (i = 0; VEC_iterate (edge, latches, i, e); i++)
+ FOR_EACH_VEC_ELT (edge, latches, i, e)
pointer_set_insert (mfb_reis_set, e);
latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
NULL);
return tovisit;
}
+/* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
+
+basic_block *
+get_loop_body_in_custom_order (const struct loop *loop,
+ int (*bb_comparator) (const void *, const void *))
+{
+ basic_block *bbs = get_loop_body (loop);
+
+ qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
+
+ return bbs;
+}
+
/* Get body of a LOOP in breadth first sort order. */
basic_block *
edge e;
edge_iterator ei;
- if (!bitmap_bit_p (visited, bb->index))
- {
- /* This basic block is now visited */
- bitmap_set_bit (visited, bb->index);
- blocks[i++] = bb;
- }
+ if (bitmap_set_bit (visited, bb->index))
+ /* This basic block is now visited */
+ blocks[i++] = bb;
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (flow_bb_inside_loop_p (loop, e->dest))
{
- if (!bitmap_bit_p (visited, e->dest->index))
- {
- bitmap_set_bit (visited, e->dest->index);
- blocks[i++] = e->dest;
- }
+ if (bitmap_set_bit (visited, e->dest->index))
+ blocks[i++] = e->dest;
}
}
for (; exit; exit = next)
{
next = exit->next_e;
-
+
exit->next->prev = exit->prev;
exit->prev->next = exit->next;
aloop != cloop;
aloop = loop_outer (aloop))
{
- exit = GGC_NEW (struct loop_exit);
+ exit = ggc_alloc_loop_exit ();
exit->e = e;
exit->next = aloop->exits->next;
exit->next_e = exits;
exits = exit;
}
- }
+ }
if (!exits && new_edge)
return;
loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
gcc_assert (current_loops->exits == NULL);
- current_loops->exits = htab_create_alloc (2 * number_of_loops (),
- loop_exit_hash,
- loop_exit_eq,
- loop_exit_free,
- ggc_calloc, ggc_free);
+ current_loops->exits = htab_create_ggc (2 * number_of_loops (),
+ loop_exit_hash, loop_exit_eq,
+ loop_exit_free);
FOR_EACH_BB (bb)
{
bb->loop_father = loop;
bb->loop_depth = loop_depth (loop);
loop->num_nodes++;
- for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
+ FOR_EACH_VEC_ELT (loop_p, loop->superloops, i, ploop)
ploop->num_nodes++;
FOR_EACH_EDGE (e, ei, bb->succs)
gcc_assert (loop != NULL);
loop->num_nodes--;
- for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
+ FOR_EACH_VEC_ELT (loop_p, loop->superloops, i, ploop)
ploop->num_nodes--;
bb->loop_father = NULL;
bb->loop_depth = 0;
for (i = 0; i < loop->num_nodes; i++)
bbs[i]->loop_father = outer;
+ free (bbs);
delete_loop (loop);
}
-- loop latches have only single successor that is header of their loop
-- irreducible loops are correctly marked
*/
-void
+DEBUG_FUNCTION void
verify_loop_structure (void)
{
unsigned *sizes, i, j;
if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
&& EDGE_COUNT (loop->header->preds) != 2)
{
- error ("loop %d's header does not have exactly 2 entries", i);
+ error ("loop %d%'s header does not have exactly 2 entries", i);
err = 1;
}
if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
{
if (!single_succ_p (loop->latch))
{
- error ("loop %d's latch does not have exactly 1 successor", i);
+ error ("loop %d%'s latch does not have exactly 1 successor", i);
err = 1;
}
if (single_succ (loop->latch) != loop->header)
{
- error ("loop %d's latch does not have header as successor", i);
+ error ("loop %d%'s latch does not have header as successor", i);
err = 1;
}
if (loop->latch->loop_father != loop)
{
- error ("loop %d's latch does not belong directly to it", i);
+ error ("loop %d%'s latch does not belong directly to it", i);
err = 1;
}
}
if (loop->header->loop_father != loop)
{
- error ("loop %d's header does not belong directly to it", i);
+ error ("loop %d%'s header does not belong directly to it", i);
err = 1;
}
if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
&& (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
{
- error ("loop %d's latch is marked as part of irreducible region", i);
+ error ("loop %d%'s latch is marked as part of irreducible region", i);
err = 1;
}
}
exit = get_exit_descriptions (e);
if (!exit)
{
- error ("Exit %d->%d not recorded",
+ error ("exit %d->%d not recorded",
e->src->index, e->dest->index);
err = 1;
}
if (eloops != 0)
{
- error ("Wrong list of exited loops for edge %d->%d",
+ error ("wrong list of exited loops for edge %d->%d",
e->src->index, e->dest->index);
err = 1;
}
if (n_exits != htab_elements (current_loops->exits))
{
- error ("Too many loop exits recorded");
+ error ("too many loop exits recorded");
err = 1;
}
else
return NULL;
}
+
+/* Returns true when BB has an incoming edge exiting LOOP. */
+
+bool
+loop_exits_to_bb_p (struct loop *loop, basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (loop_exit_edge_p (loop, e))
+ return true;
+
+ return false;
+}
+
+/* Returns true when BB has an outgoing edge exiting LOOP. */
+
+bool
+loop_exits_from_bb_p (struct loop *loop, basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (loop_exit_edge_p (loop, e))
+ return true;
+
+ return false;
+}
OSDN Git Service
