/* Natural loop discovery code for GNU compiler.
- Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 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 "function.h"
#include "basic-block.h"
#include "toplev.h"
#include "cfgloop.h"
#define HEADER_BLOCK(B) (* (int *) (B)->aux)
#define LATCH_EDGE(E) (*(int *) (E)->aux)
-static void flow_loops_cfg_dump (const struct loops *, FILE *);
-static void flow_loop_entry_edges_find (struct loop *);
-static void flow_loop_exit_edges_find (struct loop *);
-static int flow_loop_nodes_find (basic_block, struct loop *);
-static void flow_loop_pre_header_scan (struct loop *);
-static basic_block flow_loop_pre_header_find (basic_block);
-static int flow_loop_level_compute (struct loop *);
-static int flow_loops_level_compute (struct loops *);
+static void flow_loops_cfg_dump (FILE *);
static void establish_preds (struct loop *);
static void canonicalize_loop_headers (void);
static bool glb_enum_p (basic_block, void *);
/* Dump loop related CFG information. */
static void
-flow_loops_cfg_dump (const struct loops *loops, FILE *file)
+flow_loops_cfg_dump (FILE *file)
{
- int i;
basic_block bb;
- if (! loops->num || ! file)
+ if (!file)
return;
FOR_EACH_BB (bb)
{
edge succ;
+ edge_iterator ei;
fprintf (file, ";; %d succs { ", bb->index);
- for (succ = bb->succ; succ; succ = succ->succ_next)
+ FOR_EACH_EDGE (succ, ei, bb->succs)
fprintf (file, "%d ", succ->dest->index);
fprintf (file, "}\n");
}
-
- /* Dump the DFS node order. */
- if (loops->cfg.dfs_order)
- {
- fputs (";; DFS order: ", file);
- for (i = 0; i < n_basic_blocks; i++)
- fprintf (file, "%d ", loops->cfg.dfs_order[i]);
-
- fputs ("\n", file);
- }
-
- /* Dump the reverse completion node order. */
- if (loops->cfg.rc_order)
- {
- fputs (";; RC order: ", file);
- for (i = 0; i < n_basic_blocks; i++)
- fprintf (file, "%d ", loops->cfg.rc_order[i]);
-
- fputs ("\n", file);
- }
}
/* Return nonzero if the nodes of LOOP are a subset of OUTER. */
bool
flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
{
- return loop->depth > outer->depth
- && loop->pred[outer->depth] == outer;
+ return (loop->depth > outer->depth
+ && loop->pred[outer->depth] == outer);
+}
+
+/* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
+ loops within LOOP. */
+
+struct loop *
+superloop_at_depth (struct loop *loop, unsigned depth)
+{
+ gcc_assert (depth <= (unsigned) loop->depth);
+
+ if (depth == (unsigned) loop->depth)
+ return loop;
+
+ return loop->pred[depth];
}
/* Dump the loop information specified by LOOP to the stream FILE
if (! loop || ! loop->header)
return;
- fprintf (file, ";;\n;; Loop %d:%s\n", loop->num,
- loop->invalid ? " invalid" : "");
+ fprintf (file, ";;\n;; Loop %d\n", loop->num);
- fprintf (file, ";; header %d, latch %d, pre-header %d\n",
- loop->header->index, loop->latch->index,
- loop->pre_header ? loop->pre_header->index : -1);
- fprintf (file, ";; depth %d, level %d, outer %ld\n",
- loop->depth, loop->level,
- (long) (loop->outer ? loop->outer->num : -1));
+ fprintf (file, ";; header %d, latch %d\n",
+ loop->header->index, loop->latch->index);
+ fprintf (file, ";; depth %d, outer %ld\n",
+ loop->depth, (long) (loop->outer ? loop->outer->num : -1));
- if (loop->pre_header_edges)
- flow_edge_list_print (";; pre-header edges", loop->pre_header_edges,
- loop->num_pre_header_edges, file);
-
- flow_edge_list_print (";; entry edges", loop->entry_edges,
- loop->num_entries, file);
fprintf (file, ";; nodes:");
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
fprintf (file, " %d", bbs[i]->index);
free (bbs);
fprintf (file, "\n");
- flow_edge_list_print (";; exit edges", loop->exit_edges,
- loop->num_exits, file);
if (loop_dump_aux)
loop_dump_aux (loop, file, verbose);
}
-/* Dump the loop information specified by LOOPS to the stream FILE,
+/* Dump the loop information about loops to the stream FILE,
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
void
-flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
+flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
{
- int i;
- int num_loops;
+ unsigned i;
- num_loops = loops->num;
- if (! num_loops || ! file)
+ if (!current_loops || ! file)
return;
- fprintf (file, ";; %d loops found, %d levels\n",
- num_loops, loops->levels);
+ fprintf (file, ";; %d loops found\n", current_loops->num);
- for (i = 0; i < num_loops; i++)
+ for (i = 0; i < current_loops->num; i++)
{
- struct loop *loop = loops->parray[i];
+ struct loop *loop = current_loops->parray[i];
if (!loop)
continue;
}
if (verbose)
- flow_loops_cfg_dump (loops, file);
+ flow_loops_cfg_dump (file);
}
/* Free data allocated for LOOP. */
void
flow_loop_free (struct loop *loop)
{
- if (loop->pre_header_edges)
- free (loop->pre_header_edges);
- if (loop->entry_edges)
- free (loop->entry_edges);
- if (loop->exit_edges)
- free (loop->exit_edges);
if (loop->pred)
free (loop->pred);
free (loop);
{
unsigned i;
- if (! loops->num)
- abort ();
+ gcc_assert (loops->num);
/* Free the loop descriptors. */
for (i = 0; i < loops->num; i++)
free (loops->parray);
loops->parray = NULL;
-
- if (loops->cfg.dfs_order)
- free (loops->cfg.dfs_order);
- if (loops->cfg.rc_order)
- free (loops->cfg.rc_order);
-
- }
-}
-
-/* Find the entry edges into the LOOP. */
-
-static void
-flow_loop_entry_edges_find (struct loop *loop)
-{
- edge e;
- int num_entries;
-
- num_entries = 0;
- for (e = loop->header->pred; e; e = e->pred_next)
- {
- if (flow_loop_outside_edge_p (loop, e))
- num_entries++;
- }
-
- if (! num_entries)
- abort ();
-
- loop->entry_edges = xmalloc (num_entries * sizeof (edge *));
-
- num_entries = 0;
- for (e = loop->header->pred; e; e = e->pred_next)
- {
- if (flow_loop_outside_edge_p (loop, e))
- loop->entry_edges[num_entries++] = e;
}
-
- loop->num_entries = num_entries;
-}
-
-/* Find the exit edges from the LOOP. */
-
-static void
-flow_loop_exit_edges_find (struct loop *loop)
-{
- edge e;
- basic_block node, *bbs;
- unsigned num_exits, i;
-
- loop->exit_edges = NULL;
- loop->num_exits = 0;
-
- /* Check all nodes within the loop to see if there are any
- successors not in the loop. Note that a node may have multiple
- exiting edges. */
- num_exits = 0;
- bbs = get_loop_body (loop);
- for (i = 0; i < loop->num_nodes; i++)
- {
- node = bbs[i];
- for (e = node->succ; e; e = e->succ_next)
- {
- basic_block dest = e->dest;
-
- if (!flow_bb_inside_loop_p (loop, dest))
- num_exits++;
- }
- }
-
- if (! num_exits)
- {
- free (bbs);
- return;
- }
-
- loop->exit_edges = xmalloc (num_exits * sizeof (edge *));
-
- /* Store all exiting edges into an array. */
- num_exits = 0;
- for (i = 0; i < loop->num_nodes; i++)
- {
- node = bbs[i];
- for (e = node->succ; e; e = e->succ_next)
- {
- basic_block dest = e->dest;
-
- if (!flow_bb_inside_loop_p (loop, dest))
- loop->exit_edges[num_exits++] = e;
- }
- }
- free (bbs);
- loop->num_exits = num_exits;
}
/* Find the nodes contained within the LOOP with header HEADER.
Return the number of nodes within the loop. */
-static int
+int
flow_loop_nodes_find (basic_block header, struct loop *loop)
{
basic_block *stack;
if (loop->latch->loop_father != loop)
{
- stack = xmalloc (n_basic_blocks * sizeof (basic_block));
+ stack = XNEWVEC (basic_block, n_basic_blocks);
sp = 0;
num_nodes++;
stack[sp++] = loop->latch;
{
basic_block node;
edge e;
+ edge_iterator ei;
node = stack[--sp];
- for (e = node->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, node->preds)
{
basic_block ancestor = e->src;
return num_nodes;
}
-/* Find the root node of the loop pre-header extended basic block and
- the edges along the trace from the root node to the loop header. */
-
-static void
-flow_loop_pre_header_scan (struct loop *loop)
-{
- int num;
- basic_block ebb;
- edge e;
-
- loop->num_pre_header_edges = 0;
- if (loop->num_entries != 1)
- return;
-
- ebb = loop->entry_edges[0]->src;
- if (ebb == ENTRY_BLOCK_PTR)
- return;
-
- /* Count number of edges along trace from loop header to
- root of pre-header extended basic block. Usually this is
- only one or two edges. */
- for (num = 1; ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next;
- num++)
- ebb = ebb->pred->src;
-
- loop->pre_header_edges = xmalloc (num * sizeof (edge));
- loop->num_pre_header_edges = num;
-
- /* Store edges in order that they are followed. The source of the first edge
- is the root node of the pre-header extended basic block and the
- destination of the last last edge is the loop header. */
- for (e = loop->entry_edges[0]; num; e = e->src->pred)
- loop->pre_header_edges[--num] = e;
-}
-
-/* Return the block for the pre-header of the loop with header
- HEADER. Return NULL if there is no pre-header. */
+/* For each loop that has just a single exit, record the exit edge. */
-static basic_block
-flow_loop_pre_header_find (basic_block header)
+void
+mark_single_exit_loops (void)
{
- basic_block pre_header;
+ basic_block bb;
edge e;
+ struct loop *loop;
+ unsigned i;
- /* If block p is a predecessor of the header and is the only block
- that the header does not dominate, then it is the pre-header. */
- pre_header = NULL;
- for (e = header->pred; e; e = e->pred_next)
+ for (i = 1; i < current_loops->num; i++)
{
- basic_block node = e->src;
+ loop = current_loops->parray[i];
+ if (loop)
+ set_single_exit (loop, NULL);
+ }
- if (node != ENTRY_BLOCK_PTR
- && ! dominated_by_p (CDI_DOMINATORS, node, header))
+ FOR_EACH_BB (bb)
+ {
+ edge_iterator ei;
+ if (bb->loop_father == current_loops->tree_root)
+ continue;
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
- if (pre_header == NULL)
- pre_header = node;
- else
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
+ continue;
+
+ for (loop = bb->loop_father;
+ loop != e->dest->loop_father;
+ loop = loop->outer)
{
- /* There are multiple edges into the header from outside
- the loop so there is no pre-header block. */
- pre_header = NULL;
- break;
+ /* If we have already seen an exit, mark this by the edge that
+ surely does not occur as any exit. */
+ if (single_exit (loop))
+ set_single_exit (loop, single_succ_edge (ENTRY_BLOCK_PTR));
+ else
+ set_single_exit (loop, e);
}
}
}
- return pre_header;
+ for (i = 1; i < current_loops->num; i++)
+ {
+ loop = current_loops->parray[i];
+ if (!loop)
+ continue;
+
+ if (single_exit (loop) == single_succ_edge (ENTRY_BLOCK_PTR))
+ set_single_exit (loop, NULL);
+ }
+
+ current_loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
}
static void
struct loop *ploop, *father = loop->outer;
loop->depth = father->depth + 1;
+
+ /* Remember the current loop depth if it is the largest seen so far. */
+ cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
+
if (loop->pred)
free (loop->pred);
- loop->pred = xmalloc (sizeof (struct loop *) * loop->depth);
+ loop->pred = XNEWVEC (struct loop *, loop->depth);
memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
loop->pred[father->depth] = father;
loop->pred = NULL;
}
-/* Helper function to compute loop nesting depth and enclosed loop level
- for the natural loop specified by LOOP. Returns the loop level. */
-
-static int
-flow_loop_level_compute (struct loop *loop)
-{
- struct loop *inner;
- int level = 1;
-
- if (! loop)
- return 0;
-
- /* Traverse loop tree assigning depth and computing level as the
- maximum level of all the inner loops of this loop. The loop
- level is equivalent to the height of the loop in the loop tree
- and corresponds to the number of enclosed loop levels (including
- itself). */
- for (inner = loop->inner; inner; inner = inner->next)
- {
- int ilevel = flow_loop_level_compute (inner) + 1;
-
- if (ilevel > level)
- level = ilevel;
- }
-
- loop->level = level;
- return level;
-}
-
-/* Compute the loop nesting depth and enclosed loop level for the loop
- hierarchy tree specified by LOOPS. Return the maximum enclosed loop
- level. */
-
-static int
-flow_loops_level_compute (struct loops *loops)
-{
- return flow_loop_level_compute (loops->tree_root);
-}
-
-/* Scan a single natural loop specified by LOOP collecting information
- about it specified by FLAGS. */
-
-int
-flow_loop_scan (struct loop *loop, int flags)
-{
- if (flags & LOOP_ENTRY_EDGES)
- {
- /* Find edges which enter the loop header.
- Note that the entry edges should only
- enter the header of a natural loop. */
- flow_loop_entry_edges_find (loop);
- }
-
- if (flags & LOOP_EXIT_EDGES)
- {
- /* Find edges which exit the loop. */
- flow_loop_exit_edges_find (loop);
- }
-
- if (flags & LOOP_PRE_HEADER)
- {
- /* Look to see if the loop has a pre-header node. */
- loop->pre_header = flow_loop_pre_header_find (loop->header);
-
- /* Find the blocks within the extended basic block of
- the loop pre-header. */
- flow_loop_pre_header_scan (loop);
- }
-
- return 1;
-}
-
/* A callback to update latch and header info for basic block JUMP created
by redirecting an edge. */
{
alloc_aux_for_block (jump, sizeof (int));
HEADER_BLOCK (jump) = 0;
- alloc_aux_for_edge (jump->pred, sizeof (int));
- LATCH_EDGE (jump->pred) = 0;
+ alloc_aux_for_edge (single_pred_edge (jump), sizeof (int));
+ LATCH_EDGE (single_pred_edge (jump)) = 0;
+ set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump));
}
/* A callback for make_forwarder block, to redirect all edges except for
basic_block header;
edge e;
- /* Compute the dominators. */
- calculate_dominance_info (CDI_DOMINATORS);
-
alloc_aux_for_blocks (sizeof (int));
alloc_aux_for_edges (sizeof (int));
/* Split blocks so that each loop has only single latch. */
FOR_EACH_BB (header)
{
+ edge_iterator ei;
int num_latches = 0;
int have_abnormal_edge = 0;
- for (e = header->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, header->preds)
{
basic_block latch = e->src;
HEADER_BLOCK (header) = num_latches;
}
- free_dominance_info (CDI_DOMINATORS);
-
- if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest))
+ if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR)))
{
basic_block bb;
/* We could not redirect edges freely here. On the other hand,
we can simply split the edge from entry block. */
- bb = split_edge (ENTRY_BLOCK_PTR->succ);
+ bb = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
- alloc_aux_for_edge (bb->succ, sizeof (int));
- LATCH_EDGE (bb->succ) = 0;
+ alloc_aux_for_edge (single_succ_edge (bb), sizeof (int));
+ LATCH_EDGE (single_succ_edge (bb)) = 0;
alloc_aux_for_block (bb, sizeof (int));
HEADER_BLOCK (bb) = 0;
}
{
int max_freq, is_heavy;
edge heavy, tmp_edge;
+ edge_iterator ei;
if (HEADER_BLOCK (header) <= 1)
continue;
is_heavy = 1;
heavy = NULL;
max_freq = 0;
- for (e = header->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, header->preds)
if (LATCH_EDGE (e) &&
EDGE_FREQUENCY (e) > max_freq)
max_freq = EDGE_FREQUENCY (e);
- for (e = header->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, header->preds)
if (LATCH_EDGE (e) &&
EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
{
free_aux_for_blocks ();
free_aux_for_edges ();
+
+#ifdef ENABLE_CHECKING
+ verify_dominators (CDI_DOMINATORS);
+#endif
+}
+
+/* Initialize all the parallel_p fields of the loops structure to true. */
+
+static void
+initialize_loops_parallel_p (struct loops *loops)
+{
+ unsigned int i;
+
+ for (i = 0; i < loops->num; i++)
+ {
+ struct loop *loop = loops->parray[i];
+ loop->parallel_p = true;
+ }
}
/* Find all the natural loops in the function and save in LOOPS structure and
- recalculate loop_depth information in basic block structures. FLAGS
- controls which loop information is collected. Return the number of natural
- loops found. */
+ recalculate loop_depth information in basic block structures.
+ Return the number of natural loops found. */
int
-flow_loops_find (struct loops *loops, int flags)
+flow_loops_find (struct loops *loops)
{
- int i;
int b;
int num_loops;
edge e;
basic_block header;
basic_block bb;
- /* This function cannot be repeatedly called with different
- flags to build up the loop information. The loop tree
- must always be built if this function is called. */
- if (! (flags & LOOP_TREE))
- abort ();
-
memset (loops, 0, sizeof *loops);
+ /* We are going to recount the maximum loop depth,
+ so throw away the last count. */
+ cfun->max_loop_depth = 0;
+
/* Taking care of this degenerate case makes the rest of
this code simpler. */
- if (n_basic_blocks == 0)
+ if (n_basic_blocks == NUM_FIXED_BLOCKS)
return 0;
dfs_order = NULL;
rc_order = NULL;
+ /* Ensure that the dominators are computed. */
+ calculate_dominance_info (CDI_DOMINATORS);
+
/* Join loops with shared headers. */
canonicalize_loop_headers ();
- /* Compute the dominators. */
- calculate_dominance_info (CDI_DOMINATORS);
-
/* Count the number of loop headers. This should be the
same as the number of natural loops. */
headers = sbitmap_alloc (last_basic_block);
num_loops = 0;
FOR_EACH_BB (header)
{
+ edge_iterator ei;
int more_latches = 0;
header->loop_depth = 0;
/* If we have an abnormal predecessor, do not consider the
loop (not worth the problems). */
- for (e = header->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, header->preds)
if (e->flags & EDGE_ABNORMAL)
break;
if (e)
continue;
- for (e = header->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, header->preds)
{
basic_block latch = e->src;
- if (e->flags & EDGE_ABNORMAL)
- abort ();
+ gcc_assert (!(e->flags & EDGE_ABNORMAL));
/* Look for back edges where a predecessor is dominated
by this block. A natural loop has a single entry
&& dominated_by_p (CDI_DOMINATORS, latch, header))
{
/* Shared headers should be eliminated by now. */
- if (more_latches)
- abort ();
+ gcc_assert (!more_latches);
more_latches = 1;
SET_BIT (headers, header->index);
num_loops++;
}
/* Allocate loop structures. */
- loops->parray = xcalloc (num_loops + 1, sizeof (struct loop *));
+ loops->parray = XCNEWVEC (struct loop *, num_loops + 1);
/* Dummy loop containing whole function. */
- loops->parray[0] = xcalloc (1, sizeof (struct loop));
+ loops->parray[0] = XCNEW (struct loop);
loops->parray[0]->next = NULL;
loops->parray[0]->inner = NULL;
loops->parray[0]->outer = NULL;
loops->parray[0]->depth = 0;
loops->parray[0]->pred = NULL;
- loops->parray[0]->num_nodes = n_basic_blocks + 2;
+ loops->parray[0]->num_nodes = n_basic_blocks;
loops->parray[0]->latch = EXIT_BLOCK_PTR;
loops->parray[0]->header = ENTRY_BLOCK_PTR;
ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
{
/* Compute depth first search order of the CFG so that outer
natural loops will be found before inner natural loops. */
- dfs_order = xmalloc (n_basic_blocks * sizeof (int));
- rc_order = xmalloc (n_basic_blocks * sizeof (int));
- flow_depth_first_order_compute (dfs_order, rc_order);
-
- /* Save CFG derived information to avoid recomputing it. */
- loops->cfg.dfs_order = dfs_order;
- loops->cfg.rc_order = rc_order;
+ dfs_order = XNEWVEC (int, n_basic_blocks);
+ rc_order = XNEWVEC (int, n_basic_blocks);
+ pre_and_rev_post_order_compute (dfs_order, rc_order, false);
num_loops = 1;
- for (b = 0; b < n_basic_blocks; b++)
+ for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
{
struct loop *loop;
+ edge_iterator ei;
/* Search the nodes of the CFG in reverse completion order
so that we can find outer loops first. */
header = BASIC_BLOCK (rc_order[b]);
- loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
+ loop = loops->parray[num_loops] = XCNEW (struct loop);
loop->header = header;
loop->num = num_loops;
num_loops++;
/* Look for the latch for this header block. */
- for (e = header->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, header->preds)
{
basic_block latch = e->src;
loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
}
- /* Assign the loop nesting depth and enclosed loop level for each
- loop. */
- loops->levels = flow_loops_level_compute (loops);
-
- /* Scan the loops. */
- for (i = 1; i < num_loops; i++)
- flow_loop_scan (loops->parray[i], flags);
-
loops->num = num_loops;
- }
- else
- {
- free_dominance_info (CDI_DOMINATORS);
+ initialize_loops_parallel_p (loops);
+
+ free (dfs_order);
+ free (rc_order);
}
sbitmap_free (headers);
loops->state = 0;
-#ifdef ENABLE_CHECKING
- verify_flow_info ();
- verify_loop_structure (loops);
-#endif
-
return loops->num;
}
-/* Update the information regarding the loops in the CFG
- specified by LOOPS. */
-
-int
-flow_loops_update (struct loops *loops, int flags)
-{
- /* One day we may want to update the current loop data. For now
- throw away the old stuff and rebuild what we need. */
- if (loops->parray)
- flow_loops_free (loops);
-
- return flow_loops_find (loops, flags);
-}
-
/* Return nonzero if basic block BB belongs to LOOP. */
bool
flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
return loop == source_loop || flow_loop_nested_p (loop, source_loop);
}
-/* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
-
-bool
-flow_loop_outside_edge_p (const struct loop *loop, edge e)
-{
- if (e->dest != loop->header)
- abort ();
- return !flow_bb_inside_loop_p (loop, e->src);
-}
-
/* Enumeration predicate for get_loop_body. */
static bool
glb_enum_p (basic_block bb, void *glb_header)
basic_block *tovisit, bb;
unsigned tv = 0;
- if (!loop->num_nodes)
- abort ();
+ gcc_assert (loop->num_nodes);
- tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
+ tovisit = XCNEWVEC (basic_block, loop->num_nodes);
tovisit[tv++] = loop->header;
if (loop->latch == EXIT_BLOCK_PTR)
{
/* There may be blocks unreachable from EXIT_BLOCK. */
- if (loop->num_nodes != (unsigned) n_basic_blocks + 2)
- abort ();
+ gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
FOR_EACH_BB (bb)
tovisit[tv++] = bb;
tovisit[tv++] = EXIT_BLOCK_PTR;
loop->header) + 1;
}
- if (tv != loop->num_nodes)
- abort ();
+ gcc_assert (tv == loop->num_nodes);
return tovisit;
}
basic_block *tovisit;
int tv;
- if (!loop->num_nodes)
- abort ();
+ gcc_assert (loop->num_nodes);
- tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
+ tovisit = XCNEWVEC (basic_block, loop->num_nodes);
- if (loop->latch == EXIT_BLOCK_PTR)
- abort ();
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
tv = 0;
fill_sons_in_loop (loop, loop->header, tovisit, &tv);
- if (tv != (int) loop->num_nodes)
- abort ();
+ gcc_assert (tv == (int) loop->num_nodes);
return tovisit;
}
-/* Gets exit edges of a LOOP, returning their number in N_EDGES. */
-edge *
-get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges)
+/* Get body of a LOOP in breadth first sort order. */
+
+basic_block *
+get_loop_body_in_bfs_order (const struct loop *loop)
{
- edge *edges, e;
- unsigned i, n;
- basic_block * body;
+ basic_block *blocks;
+ basic_block bb;
+ bitmap visited;
+ unsigned int i = 0;
+ unsigned int vc = 1;
- if (loop->latch == EXIT_BLOCK_PTR)
- abort ();
+ gcc_assert (loop->num_nodes);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+
+ blocks = XCNEWVEC (basic_block, loop->num_nodes);
+ visited = BITMAP_ALLOC (NULL);
+
+ bb = loop->header;
+ while (i < loop->num_nodes)
+ {
+ 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;
+ }
+
+ 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;
+ }
+ }
+ }
+
+ gcc_assert (i >= vc);
+
+ bb = blocks[vc++];
+ }
+
+ BITMAP_FREE (visited);
+ return blocks;
+}
+
+/* Returns the list of the exit edges of a LOOP. */
+
+VEC (edge, heap) *
+get_loop_exit_edges (const struct loop *loop)
+{
+ VEC (edge, heap) *edges = NULL;
+ edge e;
+ unsigned i;
+ basic_block *body;
+ edge_iterator ei;
+
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
body = get_loop_body (loop);
- n = 0;
for (i = 0; i < loop->num_nodes; i++)
- for (e = body[i]->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, body[i]->succs)
if (!flow_bb_inside_loop_p (loop, e->dest))
- n++;
- edges = xmalloc (n * sizeof (edge));
- *n_edges = n;
- n = 0;
- for (i = 0; i < loop->num_nodes; i++)
- for (e = body[i]->succ; e; e = e->succ_next)
- if (!flow_bb_inside_loop_p (loop, e->dest))
- edges[n++] = e;
+ VEC_safe_push (edge, heap, edges, e);
free (body);
return edges;
unsigned i, n;
basic_block * body;
- if (loop->latch == EXIT_BLOCK_PTR)
- abort ();
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
body = get_loop_body (loop);
n = 0;
for (i = 0; i < loop->num_nodes; i++)
- if (body[i]->succ && body[i]->succ->succ_next)
+ if (EDGE_COUNT (body[i]->succs) >= 2)
n++;
free (body);
{
int i;
+ gcc_assert (bb->loop_father == NULL);
bb->loop_father = loop;
bb->loop_depth = loop->depth;
loop->num_nodes++;
for (i = 0; i < loop->depth; i++)
loop->pred[i]->num_nodes++;
- }
+}
/* Remove basic block BB from loops. */
void
int i;
struct loop *loop = bb->loop_father;
+ gcc_assert (loop != NULL);
loop->num_nodes--;
for (i = 0; i < loop->depth; i++)
loop->pred[i]->num_nodes--;
bb->loop_father = NULL;
bb->loop_depth = 0;
- }
+}
/* Finds nearest common ancestor in loop tree for given loops. */
struct loop *
}
/* Cancels the LOOP; it must be innermost one. */
-void
-cancel_loop (struct loops *loops, struct loop *loop)
+
+static void
+cancel_loop (struct loop *loop)
{
basic_block *bbs;
unsigned i;
- if (loop->inner)
- abort ();
+ gcc_assert (!loop->inner);
/* Move blocks up one level (they should be removed as soon as possible). */
bbs = get_loop_body (loop);
flow_loop_tree_node_remove (loop);
/* Remove loop from loops array. */
- loops->parray[loop->num] = NULL;
+ current_loops->parray[loop->num] = NULL;
/* Free loop data. */
flow_loop_free (loop);
/* Cancels LOOP and all its subloops. */
void
-cancel_loop_tree (struct loops *loops, struct loop *loop)
+cancel_loop_tree (struct loop *loop)
{
while (loop->inner)
- cancel_loop_tree (loops, loop->inner);
- cancel_loop (loops, loop);
+ cancel_loop_tree (loop->inner);
+ cancel_loop (loop);
}
-/* Checks that LOOPS are all right:
+/* Checks that information about loops is correct
-- sizes of loops are all right
-- results of get_loop_body really belong to the loop
-- loop header have just single entry edge and single latch edge
-- irreducible loops are correctly marked
*/
void
-verify_loop_structure (struct loops *loops)
+verify_loop_structure (void)
{
unsigned *sizes, i, j;
sbitmap irreds;
edge e;
/* Check sizes. */
- sizes = xcalloc (loops->num, sizeof (int));
+ sizes = XCNEWVEC (unsigned, current_loops->num);
sizes[0] = 2;
FOR_EACH_BB (bb)
for (loop = bb->loop_father; loop; loop = loop->outer)
sizes[loop->num]++;
- for (i = 0; i < loops->num; i++)
+ for (i = 0; i < current_loops->num; i++)
{
- if (!loops->parray[i])
- continue;
+ if (!current_loops->parray[i])
+ continue;
- if (loops->parray[i]->num_nodes != sizes[i])
+ if (current_loops->parray[i]->num_nodes != sizes[i])
{
- error ("Size of loop %d should be %d, not %d.",
- i, sizes[i], loops->parray[i]->num_nodes);
+ error ("size of loop %d should be %d, not %d",
+ i, sizes[i], current_loops->parray[i]->num_nodes);
err = 1;
}
}
- free (sizes);
-
/* Check get_loop_body. */
- for (i = 1; i < loops->num; i++)
+ for (i = 1; i < current_loops->num; i++)
{
- loop = loops->parray[i];
+ loop = current_loops->parray[i];
if (!loop)
continue;
bbs = get_loop_body (loop);
for (j = 0; j < loop->num_nodes; j++)
if (!flow_bb_inside_loop_p (loop, bbs[j]))
{
- error ("Bb %d do not belong to loop %d.",
+ error ("bb %d do not belong to loop %d",
bbs[j]->index, i);
err = 1;
}
}
/* Check headers and latches. */
- for (i = 1; i < loops->num; i++)
+ for (i = 1; i < current_loops->num; i++)
{
- loop = loops->parray[i];
+ loop = current_loops->parray[i];
if (!loop)
continue;
- if ((loops->state & LOOPS_HAVE_PREHEADERS)
- && (!loop->header->pred->pred_next
- || loop->header->pred->pred_next->pred_next))
+ if ((current_loops->state & 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 & LOOPS_HAVE_SIMPLE_LATCHES)
+ if (current_loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
{
- if (!loop->latch->succ
- || loop->latch->succ->succ_next)
+ 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 (loop->latch->succ->dest != loop->header)
+ 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 & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
+ if ((current_loops->state & 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;
}
}
/* Check irreducible loops. */
- if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
+ if (current_loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
{
/* Record old info. */
irreds = sbitmap_alloc (last_basic_block);
FOR_EACH_BB (bb)
{
+ edge_iterator ei;
if (bb->flags & BB_IRREDUCIBLE_LOOP)
SET_BIT (irreds, bb->index);
else
RESET_BIT (irreds, bb->index);
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
if (e->flags & EDGE_IRREDUCIBLE_LOOP)
e->flags |= EDGE_ALL_FLAGS + 1;
}
/* Recount it. */
- mark_irreducible_loops (loops);
+ mark_irreducible_loops ();
/* Compare. */
FOR_EACH_BB (bb)
{
+ edge_iterator ei;
+
if ((bb->flags & BB_IRREDUCIBLE_LOOP)
&& !TEST_BIT (irreds, bb->index))
{
- error ("Basic block %d should be marked irreducible.", bb->index);
+ error ("basic block %d should be marked irreducible", bb->index);
err = 1;
}
else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
&& TEST_BIT (irreds, bb->index))
{
- error ("Basic block %d should not be marked irreducible.", bb->index);
+ error ("basic block %d should not be marked irreducible", bb->index);
err = 1;
}
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
&& !(e->flags & (EDGE_ALL_FLAGS + 1)))
{
- error ("Edge from %d to %d should be marked irreducible.",
+ error ("edge from %d to %d should be marked irreducible",
e->src->index, e->dest->index);
err = 1;
}
else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
&& (e->flags & (EDGE_ALL_FLAGS + 1)))
{
- error ("Edge from %d to %d should not be marked irreducible.",
+ error ("edge from %d to %d should not be marked irreducible",
e->src->index, e->dest->index);
err = 1;
}
free (irreds);
}
- if (err)
- abort ();
+ /* Check the single_exit. */
+ if (current_loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+ {
+ memset (sizes, 0, sizeof (unsigned) * current_loops->num);
+ FOR_EACH_BB (bb)
+ {
+ edge_iterator ei;
+ if (bb->loop_father == current_loops->tree_root)
+ continue;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
+ continue;
+
+ for (loop = bb->loop_father;
+ loop != e->dest->loop_father;
+ loop = loop->outer)
+ {
+ sizes[loop->num]++;
+ if (single_exit (loop)
+ && single_exit (loop) != e)
+ {
+ error ("wrong single exit %d->%d recorded for loop %d",
+ single_exit (loop)->src->index,
+ single_exit (loop)->dest->index,
+ loop->num);
+ error ("right exit is %d->%d",
+ e->src->index, e->dest->index);
+ err = 1;
+ }
+ }
+ }
+ }
+
+ for (i = 1; i < current_loops->num; i++)
+ {
+ loop = current_loops->parray[i];
+ if (!loop)
+ continue;
+
+ if (sizes[i] == 1
+ && !single_exit (loop))
+ {
+ error ("single exit not recorded for loop %d", loop->num);
+ err = 1;
+ }
+
+ if (sizes[i] != 1
+ && single_exit (loop))
+ {
+ error ("loop %d should not have single exit (%d -> %d)",
+ loop->num,
+ single_exit (loop)->src->index,
+ single_exit (loop)->dest->index);
+ err = 1;
+ }
+ }
+ }
+
+ gcc_assert (!err);
+
+ free (sizes);
}
/* Returns latch edge of LOOP. */
edge
loop_latch_edge (const struct loop *loop)
{
- edge e;
-
- for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
- continue;
-
- return e;
+ return find_edge (loop->latch, loop->header);
}
/* Returns preheader edge of LOOP. */
loop_preheader_edge (const struct loop *loop)
{
edge e;
+ edge_iterator ei;
- for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next)
- continue;
+ FOR_EACH_EDGE (e, ei, loop->header->preds)
+ if (e->src != loop->latch)
+ break;
return e;
}
+
+/* Returns true if E is an exit of LOOP. */
+
+bool
+loop_exit_edge_p (const struct loop *loop, edge e)
+{
+ return (flow_bb_inside_loop_p (loop, e->src)
+ && !flow_bb_inside_loop_p (loop, e->dest));
+}
+
+/* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
+ or more than one exit. */
+
+edge
+single_exit (const struct loop *loop)
+{
+ return loop->single_exit_;
+}
+
+/* Records E as a single exit edge of LOOP. */
+
+void
+set_single_exit (struct loop *loop, edge e)
+{
+ loop->single_exit_ = e;
+}
OSDN Git Service
