/* Natural loop discovery code for GNU compiler.
- Copyright (C) 2000, 2001 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
+#include "obstack.h"
+#include "function.h"
#include "basic-block.h"
-
-static void flow_loops_cfg_dump PARAMS ((const struct loops *,
- FILE *));
-static int flow_loop_nested_p PARAMS ((struct loop *,
- struct loop *));
-static int flow_loop_entry_edges_find PARAMS ((basic_block, const sbitmap,
- edge **));
-static int flow_loop_exit_edges_find PARAMS ((const sbitmap, edge **));
-static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
-static void flow_loop_pre_header_scan PARAMS ((struct loop *));
-static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
- const sbitmap *));
-static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
-static void flow_loops_tree_build PARAMS ((struct loops *));
-static int flow_loop_level_compute PARAMS ((struct loop *, int));
-static int flow_loops_level_compute PARAMS ((struct loops *));
+#include "toplev.h"
+#include "cfgloop.h"
+#include "flags.h"
+#include "tree.h"
+#include "tree-flow.h"
+
+/* Ratio of frequencies of edges so that one of more latch edges is
+ considered to belong to inner loop with same header. */
+#define HEAVY_EDGE_RATIO 8
+
+#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 int flow_loop_nodes_find (basic_block, struct loop *);
+static int flow_loop_level_compute (struct loop *);
+static void flow_loops_level_compute (struct loops *);
+static void establish_preds (struct loop *);
+static void canonicalize_loop_headers (void);
+static bool glb_enum_p (basic_block, void *);
\f
/* Dump loop related CFG information. */
static void
-flow_loops_cfg_dump (loops, file)
- const struct loops *loops;
- FILE *file;
+flow_loops_cfg_dump (const struct loops *loops, FILE *file)
{
int i;
+ basic_block bb;
- if (! loops->num || ! file || ! loops->cfg.dom)
+ if (! loops->num || ! file)
return;
- for (i = 0; i < n_basic_blocks; i++)
+ FOR_EACH_BB (bb)
{
edge succ;
+ edge_iterator ei;
- fprintf (file, ";; %d succs { ", i);
- for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
+ fprintf (file, ";; %d succs { ", bb->index);
+ FOR_EACH_EDGE (succ, ei, bb->succs)
fprintf (file, "%d ", succ->dest->index);
- flow_nodes_print ("} dom", loops->cfg.dom[i], file);
+ fprintf (file, "}\n");
}
/* Dump the DFS node 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 non-zero if the nodes of LOOP are a subset of OUTER. */
+/* Return nonzero if the nodes of LOOP are a subset of OUTER. */
-static int
-flow_loop_nested_p (outer, loop)
- struct loop *outer;
- struct loop *loop;
+bool
+flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
{
- return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
+ 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
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
void
-flow_loop_dump (loop, file, loop_dump_aux, verbose)
- const struct loop *loop;
- FILE *file;
- void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
- int verbose;
+flow_loop_dump (const struct loop *loop, FILE *file,
+ void (*loop_dump_aux) (const struct loop *, FILE *, int),
+ int verbose)
{
+ basic_block *bbs;
+ unsigned i;
+
if (! loop || ! loop->header)
return;
- if (loop->first->head && loop->last->end)
- fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n",
- loop->num, INSN_UID (loop->first->head),
- INSN_UID (loop->last->end),
- loop->shared ? " shared" : "",
- loop->invalid ? " invalid" : "");
- else
- fprintf (file, ";;\n;; Loop %d:%s%s\n", loop->num,
- loop->shared ? " shared" : "",
+ fprintf (file, ";;\n;; Loop %d:%s\n", loop->num,
loop->invalid ? " invalid" : "");
- fprintf (file, ";; header %d, latch %d, pre-header %d, first %d, last %d\n",
- loop->header->index, loop->latch->index,
- loop->pre_header ? loop->pre_header->index : -1,
- loop->first->index, loop->last->index);
+ fprintf (file, ";; header %d, latch %d\n",
+ loop->header->index, loop->latch->index);
fprintf (file, ";; depth %d, level %d, outer %ld\n",
loop->depth, loop->level,
(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, ";; %d", loop->num_nodes);
- flow_nodes_print (" nodes", loop->nodes, file);
- flow_edge_list_print (";; exit edges", loop->exit_edges,
- loop->num_exits, file);
- if (loop->exits_doms)
- flow_nodes_print (";; exit doms", loop->exits_doms, 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");
+
if (loop_dump_aux)
loop_dump_aux (loop, file, verbose);
}
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
void
-flow_loops_dump (loops, file, loop_dump_aux, verbose)
- const struct loops *loops;
- FILE *file;
- void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
- int verbose;
+flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
{
int i;
int num_loops;
if (! num_loops || ! file)
return;
- fprintf (file, ";; %d loops found, %d levels\n",
- num_loops, loops->levels);
+ fprintf (file, ";; %d loops found\n", num_loops);
for (i = 0; i < num_loops; i++)
{
- struct loop *loop = &loops->array[i];
+ struct loop *loop = loops->parray[i];
- flow_loop_dump (loop, file, loop_dump_aux, verbose);
-
- if (loop->shared)
- {
- int j;
+ if (!loop)
+ continue;
- for (j = 0; j < i; j++)
- {
- struct loop *oloop = &loops->array[j];
-
- if (loop->header == oloop->header)
- {
- int disjoint;
- int smaller;
-
- smaller = loop->num_nodes < oloop->num_nodes;
-
- /* If the union of LOOP and OLOOP is different than
- the larger of LOOP and OLOOP then LOOP and OLOOP
- must be disjoint. */
- disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
- smaller ? oloop : loop);
- fprintf (file,
- ";; loop header %d shared by loops %d, %d %s\n",
- loop->header->index, i, j,
- disjoint ? "disjoint" : "nested");
- }
- }
- }
+ flow_loop_dump (loop, file, loop_dump_aux, verbose);
}
if (verbose)
flow_loops_cfg_dump (loops, file);
}
+/* Free data allocated for LOOP. */
+void
+flow_loop_free (struct loop *loop)
+{
+ if (loop->pred)
+ free (loop->pred);
+ free (loop);
+}
+
/* Free all the memory allocated for LOOPS. */
void
-flow_loops_free (loops)
- struct loops *loops;
+flow_loops_free (struct loops *loops)
{
- if (loops->array)
+ if (loops->parray)
{
- int i;
+ unsigned i;
- if (! loops->num)
- abort ();
+ gcc_assert (loops->num);
/* Free the loop descriptors. */
for (i = 0; i < loops->num; i++)
{
- struct loop *loop = &loops->array[i];
-
- if (loop->pre_header_edges)
- free (loop->pre_header_edges);
- if (loop->nodes)
- sbitmap_free (loop->nodes);
- if (loop->entry_edges)
- free (loop->entry_edges);
- if (loop->exit_edges)
- free (loop->exit_edges);
- if (loop->exits_doms)
- sbitmap_free (loop->exits_doms);
+ struct loop *loop = loops->parray[i];
+
+ if (!loop)
+ continue;
+
+ flow_loop_free (loop);
}
- free (loops->array);
- loops->array = NULL;
- if (loops->cfg.dom)
- sbitmap_vector_free (loops->cfg.dom);
+ 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);
- if (loops->shared_headers)
- sbitmap_free (loops->shared_headers);
}
}
-/* Find the entry edges into the loop with header HEADER and nodes
- NODES and store in ENTRY_EDGES array. Return the number of entry
- edges from the loop. */
+/* Find the nodes contained within the LOOP with header HEADER.
+ Return the number of nodes within the loop. */
static int
-flow_loop_entry_edges_find (header, nodes, entry_edges)
- basic_block header;
- const sbitmap nodes;
- edge **entry_edges;
+flow_loop_nodes_find (basic_block header, struct loop *loop)
{
- edge e;
- int num_entries;
+ basic_block *stack;
+ int sp;
+ int num_nodes = 1;
- *entry_edges = NULL;
+ header->loop_father = loop;
+ header->loop_depth = loop->depth;
- num_entries = 0;
- for (e = header->pred; e; e = e->pred_next)
+ if (loop->latch->loop_father != loop)
{
- basic_block src = e->src;
-
- if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
- num_entries++;
- }
+ stack = xmalloc (n_basic_blocks * sizeof (basic_block));
+ sp = 0;
+ num_nodes++;
+ stack[sp++] = loop->latch;
+ loop->latch->loop_father = loop;
+ loop->latch->loop_depth = loop->depth;
- if (! num_entries)
- abort ();
+ while (sp)
+ {
+ basic_block node;
+ edge e;
+ edge_iterator ei;
- *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *));
+ node = stack[--sp];
- num_entries = 0;
- for (e = header->pred; e; e = e->pred_next)
- {
- basic_block src = e->src;
+ FOR_EACH_EDGE (e, ei, node->preds)
+ {
+ basic_block ancestor = e->src;
- if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
- (*entry_edges)[num_entries++] = e;
+ if (ancestor != ENTRY_BLOCK_PTR
+ && ancestor->loop_father != loop)
+ {
+ ancestor->loop_father = loop;
+ ancestor->loop_depth = loop->depth;
+ num_nodes++;
+ stack[sp++] = ancestor;
+ }
+ }
+ }
+ free (stack);
}
-
- return num_entries;
+ return num_nodes;
}
-/* Find the exit edges from the loop using the bitmap of loop nodes
- NODES and store in EXIT_EDGES array. Return the number of
- exit edges from the loop. */
+/* For each loop in the lOOPS tree that has just a single exit
+ record the exit edge. */
-static int
-flow_loop_exit_edges_find (nodes, exit_edges)
- const sbitmap nodes;
- edge **exit_edges;
+void
+mark_single_exit_loops (struct loops *loops)
{
+ basic_block bb;
edge e;
- int node;
- int num_exits;
-
- *exit_edges = NULL;
-
- /* 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 ????? A node can have one jumping edge and one fallthru
- edge so only one of these can exit the loop. */
- num_exits = 0;
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
- for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
- {
- basic_block dest = e->dest;
-
- if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
- num_exits++;
- }
- });
-
- if (! num_exits)
- return 0;
-
- *exit_edges = (edge *) xmalloc (num_exits * sizeof (edge *));
-
- /* Store all exiting edges into an array. */
- num_exits = 0;
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
- for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
- {
- basic_block dest = e->dest;
-
- if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
- (*exit_edges)[num_exits++] = e;
- }
- });
-
- return num_exits;
-}
-
-/* Find the nodes contained within the loop with header HEADER and
- latch LATCH and store in NODES. Return the number of nodes within
- the loop. */
-
-static int
-flow_loop_nodes_find (header, latch, nodes)
- basic_block header;
- basic_block latch;
- sbitmap nodes;
-{
- basic_block *stack;
- int sp;
- int num_nodes = 0;
-
- stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
- sp = 0;
-
- /* Start with only the loop header in the set of loop nodes. */
- sbitmap_zero (nodes);
- SET_BIT (nodes, header->index);
- num_nodes++;
- header->loop_depth++;
+ struct loop *loop;
+ unsigned i;
- /* Push the loop latch on to the stack. */
- if (! TEST_BIT (nodes, latch->index))
+ for (i = 1; i < loops->num; i++)
{
- SET_BIT (nodes, latch->index);
- latch->loop_depth++;
- num_nodes++;
- stack[sp++] = latch;
+ loop = loops->parray[i];
+ if (loop)
+ loop->single_exit = NULL;
}
- while (sp)
+ FOR_EACH_BB (bb)
{
- basic_block node;
- edge e;
-
- node = stack[--sp];
- for (e = node->pred; e; e = e->pred_next)
+ edge_iterator ei;
+ if (bb->loop_father == loops->tree_root)
+ continue;
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
- basic_block ancestor = e->src;
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
- /* If each ancestor not marked as part of loop, add to set of
- loop nodes and push on to stack. */
- if (ancestor != ENTRY_BLOCK_PTR
- && ! TEST_BIT (nodes, ancestor->index))
+ 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)
{
- SET_BIT (nodes, ancestor->index);
- ancestor->loop_depth++;
- num_nodes++;
- stack[sp++] = ancestor;
+ /* If we have already seen an exit, mark this by the edge that
+ surely does not occur as any exit. */
+ if (loop->single_exit)
+ loop->single_exit = EDGE_SUCC (ENTRY_BLOCK_PTR, 0);
+ else
+ loop->single_exit = e;
}
}
}
- free (stack);
- 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 (loop)
- struct loop *loop;
-{
- int num = 0;
- basic_block ebb;
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
- loop->num_pre_header_edges = 0;
+ if (loop->single_exit == EDGE_SUCC (ENTRY_BLOCK_PTR, 0))
+ loop->single_exit = NULL;
+ }
- if (loop->num_entries != 1)
- return;
+ loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
+}
- ebb = loop->entry_edges[0]->src;
+static void
+establish_preds (struct loop *loop)
+{
+ struct loop *ploop, *father = loop->outer;
- if (ebb != ENTRY_BLOCK_PTR)
- {
- edge e;
+ loop->depth = father->depth + 1;
- /* 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. */
- num++;
- while (ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next)
- {
- ebb = ebb->pred->src;
- num++;
- }
+ /* Remember the current loop depth if it is the largest seen so far. */
+ cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
- loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge *));
- loop->num_pre_header_edges = num;
+ if (loop->pred)
+ free (loop->pred);
+ loop->pred = xmalloc (sizeof (struct loop *) * loop->depth);
+ memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
+ loop->pred[father->depth] = father;
- /* 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;
- }
- }
+ for (ploop = loop->inner; ploop; ploop = ploop->next)
+ establish_preds (ploop);
}
-/* Return the block for the pre-header of the loop with header
- HEADER where DOM specifies the dominator information. Return NULL if
- there is no pre-header. */
+/* Add LOOP to the loop hierarchy tree where FATHER is father of the
+ added loop. If LOOP has some children, take care of that their
+ pred field will be initialized correctly. */
-static basic_block
-flow_loop_pre_header_find (header, dom)
- basic_block header;
- const sbitmap *dom;
+void
+flow_loop_tree_node_add (struct loop *father, struct loop *loop)
{
- basic_block pre_header;
- edge e;
-
- /* 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)
- {
- basic_block node = e->src;
+ loop->next = father->inner;
+ father->inner = loop;
+ loop->outer = father;
- if (node != ENTRY_BLOCK_PTR
- && ! TEST_BIT (dom[node->index], header->index))
- {
- if (pre_header == NULL)
- pre_header = node;
- else
- {
- /* There are multiple edges into the header from outside
- the loop so there is no pre-header block. */
- pre_header = NULL;
- break;
- }
- }
- }
- return pre_header;
+ establish_preds (loop);
}
-/* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
- previously added. The insertion algorithm assumes that the loops
- are added in the order found by a depth first search of the CFG. */
+/* Remove LOOP from the loop hierarchy tree. */
-static void
-flow_loop_tree_node_add (prevloop, loop)
- struct loop *prevloop;
- struct loop *loop;
+void
+flow_loop_tree_node_remove (struct loop *loop)
{
+ struct loop *prev, *father;
- if (flow_loop_nested_p (prevloop, loop))
- {
- prevloop->inner = loop;
- loop->outer = prevloop;
- return;
- }
+ father = loop->outer;
+ loop->outer = NULL;
- while (prevloop->outer)
+ /* Remove loop from the list of sons. */
+ if (father->inner == loop)
+ father->inner = loop->next;
+ else
{
- if (flow_loop_nested_p (prevloop->outer, loop))
- {
- prevloop->next = loop;
- loop->outer = prevloop->outer;
- return;
- }
- prevloop = prevloop->outer;
+ for (prev = father->inner; prev->next != loop; prev = prev->next);
+ prev->next = loop->next;
}
- prevloop->next = loop;
- loop->outer = NULL;
-}
-
-/* Build the loop hierarchy tree for LOOPS. */
-
-static void
-flow_loops_tree_build (loops)
- struct loops *loops;
-{
- int i;
- int num_loops;
-
- num_loops = loops->num;
- if (! num_loops)
- return;
-
- /* Root the loop hierarchy tree with the first loop found.
- Since we used a depth first search this should be the
- outermost loop. */
- loops->tree_root = &loops->array[0];
- loops->tree_root->outer = loops->tree_root->inner = loops->tree_root->next = NULL;
-
- /* Add the remaining loops to the tree. */
- for (i = 1; i < num_loops; i++)
- flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
+ loop->depth = -1;
+ free (loop->pred);
+ loop->pred = NULL;
}
/* Helper function to compute loop nesting depth and enclosed loop level
- for the natural loop specified by LOOP at the loop depth DEPTH.
- Returns the loop level. */
+ for the natural loop specified by LOOP. Returns the loop level. */
static int
-flow_loop_level_compute (loop, depth)
- struct loop *loop;
- int depth;
+flow_loop_level_compute (struct loop *loop)
{
struct loop *inner;
int level = 1;
itself). */
for (inner = loop->inner; inner; inner = inner->next)
{
- int ilevel;
-
- ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
+ int ilevel = flow_loop_level_compute (inner) + 1;
if (ilevel > level)
level = ilevel;
}
+
loop->level = level;
- loop->depth = depth;
return level;
}
hierarchy tree specified by LOOPS. Return the maximum enclosed loop
level. */
-static int
-flow_loops_level_compute (loops)
- struct loops *loops;
+static void
+flow_loops_level_compute (struct loops *loops)
{
- struct loop *loop;
- int level;
- int levels = 0;
+ flow_loop_level_compute (loops->tree_root);
+}
- /* Traverse all the outer level loops. */
- for (loop = loops->tree_root; loop; loop = loop->next)
- {
- level = flow_loop_level_compute (loop, 1);
- if (level > levels)
- levels = level;
- }
- return levels;
+/* A callback to update latch and header info for basic block JUMP created
+ by redirecting an edge. */
+
+static void
+update_latch_info (basic_block jump)
+{
+ alloc_aux_for_block (jump, sizeof (int));
+ HEADER_BLOCK (jump) = 0;
+ alloc_aux_for_edge (EDGE_PRED (jump, 0), sizeof (int));
+ LATCH_EDGE (EDGE_PRED (jump, 0)) = 0;
+ set_immediate_dominator (CDI_DOMINATORS, jump, EDGE_PRED (jump, 0)->src);
}
-/* Scan a single natural loop specified by LOOP collecting information
- about it specified by FLAGS. */
+/* A callback for make_forwarder block, to redirect all edges except for
+ MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
+ whether to redirect it. */
-int
-flow_loop_scan (loops, loop, flags)
- struct loops *loops;
- struct loop *loop;
- int flags;
+static edge mfb_kj_edge;
+static bool
+mfb_keep_just (edge e)
+{
+ return e != mfb_kj_edge;
+}
+
+/* A callback for make_forwarder block, to redirect the latch edges into an
+ entry part. E is the edge for that we should decide whether to redirect
+ it. */
+
+static bool
+mfb_keep_nonlatch (edge e)
+{
+ return LATCH_EDGE (e);
+}
+
+/* Takes care of merging natural loops with shared headers. */
+
+static void
+canonicalize_loop_headers (void)
{
- /* Determine prerequisites. */
- if ((flags & LOOP_EXITS_DOMS) && ! loop->exit_edges)
- flags |= LOOP_EXIT_EDGES;
+ basic_block header;
+ edge e;
+
+ alloc_aux_for_blocks (sizeof (int));
+ alloc_aux_for_edges (sizeof (int));
- if (flags & LOOP_ENTRY_EDGES)
+ /* Split blocks so that each loop has only single latch. */
+ FOR_EACH_BB (header)
{
- /* Find edges which enter the loop header.
- Note that the entry edges should only
- enter the header of a natural loop. */
- loop->num_entries
- = flow_loop_entry_edges_find (loop->header,
- loop->nodes,
- &loop->entry_edges);
+ edge_iterator ei;
+ int num_latches = 0;
+ int have_abnormal_edge = 0;
+
+ FOR_EACH_EDGE (e, ei, header->preds)
+ {
+ basic_block latch = e->src;
+
+ if (e->flags & EDGE_ABNORMAL)
+ have_abnormal_edge = 1;
+
+ if (latch != ENTRY_BLOCK_PTR
+ && dominated_by_p (CDI_DOMINATORS, latch, header))
+ {
+ num_latches++;
+ LATCH_EDGE (e) = 1;
+ }
+ }
+ if (have_abnormal_edge)
+ HEADER_BLOCK (header) = 0;
+ else
+ HEADER_BLOCK (header) = num_latches;
}
- if (flags & LOOP_EXIT_EDGES)
+ if (HEADER_BLOCK (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest))
{
- /* Find edges which exit the loop. */
- loop->num_exits
- = flow_loop_exit_edges_find (loop->nodes,
- &loop->exit_edges);
+ 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 (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
+
+ alloc_aux_for_edge (EDGE_SUCC (bb, 0), sizeof (int));
+ LATCH_EDGE (EDGE_SUCC (bb, 0)) = 0;
+ alloc_aux_for_block (bb, sizeof (int));
+ HEADER_BLOCK (bb) = 0;
}
- if (flags & LOOP_EXITS_DOMS)
+ FOR_EACH_BB (header)
{
- int j;
-
- /* Determine which loop nodes dominate all the exits
- of the loop. */
- loop->exits_doms = sbitmap_alloc (n_basic_blocks);
- sbitmap_copy (loop->exits_doms, loop->nodes);
- for (j = 0; j < loop->num_exits; j++)
- sbitmap_a_and_b (loop->exits_doms, loop->exits_doms,
- loops->cfg.dom[loop->exit_edges[j]->src->index]);
-
- /* The header of a natural loop must dominate
- all exits. */
- if (! TEST_BIT (loop->exits_doms, loop->header->index))
- abort ();
+ int max_freq, is_heavy;
+ edge heavy, tmp_edge;
+ edge_iterator ei;
+
+ if (HEADER_BLOCK (header) <= 1)
+ continue;
+
+ /* Find a heavy edge. */
+ is_heavy = 1;
+ heavy = NULL;
+ max_freq = 0;
+ FOR_EACH_EDGE (e, ei, header->preds)
+ if (LATCH_EDGE (e) &&
+ EDGE_FREQUENCY (e) > max_freq)
+ max_freq = EDGE_FREQUENCY (e);
+ FOR_EACH_EDGE (e, ei, header->preds)
+ if (LATCH_EDGE (e) &&
+ EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
+ {
+ if (heavy)
+ {
+ is_heavy = 0;
+ break;
+ }
+ else
+ heavy = e;
+ }
+
+ if (is_heavy)
+ {
+ /* Split out the heavy edge, and create inner loop for it. */
+ mfb_kj_edge = heavy;
+ tmp_edge = make_forwarder_block (header, mfb_keep_just,
+ update_latch_info);
+ alloc_aux_for_block (tmp_edge->dest, sizeof (int));
+ HEADER_BLOCK (tmp_edge->dest) = 1;
+ alloc_aux_for_edge (tmp_edge, sizeof (int));
+ LATCH_EDGE (tmp_edge) = 0;
+ HEADER_BLOCK (header)--;
+ }
+
+ if (HEADER_BLOCK (header) > 1)
+ {
+ /* Create a new latch block. */
+ tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
+ update_latch_info);
+ alloc_aux_for_block (tmp_edge->dest, sizeof (int));
+ HEADER_BLOCK (tmp_edge->src) = 0;
+ HEADER_BLOCK (tmp_edge->dest) = 1;
+ alloc_aux_for_edge (tmp_edge, sizeof (int));
+ LATCH_EDGE (tmp_edge) = 1;
+ }
}
- 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, loops->cfg.dom);
+ free_aux_for_blocks ();
+ free_aux_for_edges ();
- /* Find the blocks within the extended basic block of
- the loop pre-header. */
- flow_loop_pre_header_scan (loop);
+#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;
}
- return 1;
}
-/* 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.
+/* Find all the natural loops in the function and save in LOOPS structure and
+ recalculate loop_depth information in basic block structures.
Return the number of natural loops found. */
int
-flow_loops_find (loops, flags)
- struct loops *loops;
- int flags;
+flow_loops_find (struct loops *loops)
{
- int i;
int b;
int num_loops;
edge e;
sbitmap headers;
- sbitmap *dom;
int *dfs_order;
int *rc_order;
+ 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);
- 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. */
dfs_order = NULL;
rc_order = NULL;
- /* Compute the dominators. */
- dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
+ /* Ensure that the dominators are computed. */
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ /* Join loops with shared headers. */
+ canonicalize_loop_headers ();
- /* Count the number of loop edges (back edges). This should be the
+ /* Count the number of loop headers. This should be the
same as the number of natural loops. */
+ headers = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (headers);
num_loops = 0;
- for (b = 0; b < n_basic_blocks; b++)
+ FOR_EACH_BB (header)
{
- basic_block header;
+ edge_iterator ei;
+ int more_latches = 0;
- header = BASIC_BLOCK (b);
header->loop_depth = 0;
- for (e = header->pred; e; e = e->pred_next)
+ /* 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)
+ continue;
+
+ FOR_EACH_EDGE (e, ei, header->preds)
{
basic_block latch = e->src;
+ 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
node (header) that dominates all the nodes in the
loop. It also has single back edge to the header
- from a latch node. Note that multiple natural loops
- may share the same header. */
- if (b != header->index)
- abort ();
-
- if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
- num_loops++;
+ from a latch node. */
+ if (latch != ENTRY_BLOCK_PTR
+ && dominated_by_p (CDI_DOMINATORS, latch, header))
+ {
+ /* Shared headers should be eliminated by now. */
+ 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 *));
+
+ /* Dummy loop containing whole function. */
+ loops->parray[0] = xcalloc (1, sizeof (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]->latch = EXIT_BLOCK_PTR;
+ loops->parray[0]->header = ENTRY_BLOCK_PTR;
+ ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
+ EXIT_BLOCK_PTR->loop_father = loops->parray[0];
+
+ loops->tree_root = loops->parray[0];
+
+ /* Find and record information about all the natural loops
+ in the CFG. */
+ loops->num = 1;
+ FOR_EACH_BB (bb)
+ bb->loop_father = loops->tree_root;
+
if (num_loops)
{
/* Compute depth first search order of the CFG so that outer
natural loops will be found before inner natural loops. */
- dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
- rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
+ 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.dom = dom;
loops->cfg.dfs_order = dfs_order;
loops->cfg.rc_order = rc_order;
- /* Allocate loop structures. */
- loops->array
- = (struct loop *) xcalloc (num_loops, sizeof (struct loop));
-
- headers = sbitmap_alloc (n_basic_blocks);
- sbitmap_zero (headers);
-
- loops->shared_headers = sbitmap_alloc (n_basic_blocks);
- sbitmap_zero (loops->shared_headers);
+ num_loops = 1;
- /* Find and record information about all the natural loops
- in the CFG. */
- num_loops = 0;
for (b = 0; b < n_basic_blocks; b++)
{
- basic_block header;
+ struct loop *loop;
+ edge_iterator ei;
/* Search the nodes of the CFG in reverse completion order
so that we can find outer loops first. */
+ if (!TEST_BIT (headers, rc_order[b]))
+ continue;
+
header = BASIC_BLOCK (rc_order[b]);
- /* Look for all the possible latch blocks for this header. */
- for (e = header->pred; e; e = e->pred_next)
+ loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
+
+ loop->header = header;
+ loop->num = num_loops;
+ num_loops++;
+
+ /* Look for the latch for this header block. */
+ FOR_EACH_EDGE (e, ei, header->preds)
{
basic_block latch = e->src;
- /* Look for back edges where a predecessor is dominated
- by this block. A natural loop has a single entry
- node (header) that dominates all the nodes in the
- loop. It also has single back edge to the header
- from a latch node. Note that multiple natural loops
- may share the same header. */
if (latch != ENTRY_BLOCK_PTR
- && TEST_BIT (dom[latch->index], header->index))
+ && dominated_by_p (CDI_DOMINATORS, latch, header))
{
- struct loop *loop;
-
- loop = loops->array + num_loops;
-
- loop->header = header;
loop->latch = latch;
- loop->num = num_loops;
-
- num_loops++;
+ break;
}
}
+
+ flow_loop_tree_node_add (header->loop_father, loop);
+ loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
}
- for (i = 0; i < num_loops; i++)
+ /* Assign the loop nesting depth and enclosed loop level for each
+ loop. */
+ flow_loops_level_compute (loops);
+
+ loops->num = num_loops;
+ initialize_loops_parallel_p (loops);
+ }
+
+ sbitmap_free (headers);
+
+ loops->state = 0;
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+ verify_loop_structure (loops);
+#endif
+
+ return loops->num;
+}
+
+/* Return nonzero if basic block BB belongs to LOOP. */
+bool
+flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
+{
+ struct loop *source_loop;
+
+ if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
+ return 0;
+
+ source_loop = bb->loop_father;
+ 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)
+{
+ gcc_assert (e->dest == loop->header);
+ 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)
+{
+ return bb != (basic_block) glb_header;
+}
+
+/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
+ order against direction of edges from latch. Specially, if
+ header != latch, latch is the 1-st block. */
+basic_block *
+get_loop_body (const struct loop *loop)
+{
+ basic_block *tovisit, bb;
+ unsigned tv = 0;
+
+ gcc_assert (loop->num_nodes);
+
+ tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
+ tovisit[tv++] = loop->header;
+
+ if (loop->latch == EXIT_BLOCK_PTR)
+ {
+ /* There may be blocks unreachable from EXIT_BLOCK. */
+ gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks + 2);
+ FOR_EACH_BB (bb)
+ tovisit[tv++] = bb;
+ tovisit[tv++] = EXIT_BLOCK_PTR;
+ }
+ else if (loop->latch != loop->header)
+ {
+ tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
+ tovisit + 1, loop->num_nodes - 1,
+ loop->header) + 1;
+ }
+
+ gcc_assert (tv == loop->num_nodes);
+ return tovisit;
+}
+
+/* Fills dominance descendants inside LOOP of the basic block BB into
+ array TOVISIT from index *TV. */
+
+static void
+fill_sons_in_loop (const struct loop *loop, basic_block bb,
+ basic_block *tovisit, int *tv)
+{
+ basic_block son, postpone = NULL;
+
+ tovisit[(*tv)++] = bb;
+ for (son = first_dom_son (CDI_DOMINATORS, bb);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ {
+ if (!flow_bb_inside_loop_p (loop, son))
+ continue;
+
+ if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
{
- struct loop *loop = &loops->array[i];
-
- /* Keep track of blocks that are loop headers so
- that we can tell which loops should be merged. */
- if (TEST_BIT (headers, loop->header->index))
- SET_BIT (loops->shared_headers, loop->header->index);
- SET_BIT (headers, loop->header->index);
-
- /* Find nodes contained within the loop. */
- loop->nodes = sbitmap_alloc (n_basic_blocks);
- loop->num_nodes
- = flow_loop_nodes_find (loop->header, loop->latch, loop->nodes);
-
- /* Compute first and last blocks within the loop.
- These are often the same as the loop header and
- loop latch respectively, but this is not always
- the case. */
- loop->first
- = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
- loop->last
- = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
-
- flow_loop_scan (loops, loop, flags);
+ postpone = son;
+ continue;
}
+ fill_sons_in_loop (loop, son, tovisit, tv);
+ }
+
+ if (postpone)
+ fill_sons_in_loop (loop, postpone, tovisit, tv);
+}
+
+/* Gets body of a LOOP (that must be different from the outermost loop)
+ sorted by dominance relation. Additionally, if a basic block s dominates
+ the latch, then only blocks dominated by s are be after it. */
+
+basic_block *
+get_loop_body_in_dom_order (const struct loop *loop)
+{
+ basic_block *tovisit;
+ int tv;
+
+ gcc_assert (loop->num_nodes);
+
+ tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
+
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+
+ tv = 0;
+ fill_sons_in_loop (loop, loop->header, tovisit, &tv);
+
+ gcc_assert (tv == (int) loop->num_nodes);
+
+ return tovisit;
+}
+
+/* Get body of a LOOP in breadth first sort order. */
+
+basic_block *
+get_loop_body_in_bfs_order (const struct loop *loop)
+{
+ basic_block *blocks;
+ basic_block bb;
+ bitmap visited;
+ unsigned int i = 0;
+ unsigned int vc = 1;
- /* Natural loops with shared headers may either be disjoint or
- nested. Disjoint loops with shared headers cannot be inner
- loops and should be merged. For now just mark loops that share
- headers. */
- for (i = 0; i < num_loops; i++)
- if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
- loops->array[i].shared = 1;
+ gcc_assert (loop->num_nodes);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
- sbitmap_free (headers);
+ blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
+ 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++];
}
- else
+
+ BITMAP_FREE (visited);
+ return blocks;
+}
+
+/* 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)
+{
+ edge *edges, e;
+ unsigned i, n;
+ 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_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_EACH_EDGE (e, ei, body[i]->succs)
+ if (!flow_bb_inside_loop_p (loop, e->dest))
+ edges[n++] = e;
+ free (body);
+
+ return edges;
+}
+
+/* Counts the number of conditional branches inside LOOP. */
+
+unsigned
+num_loop_branches (const struct loop *loop)
+{
+ unsigned i, n;
+ basic_block * body;
+
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+
+ body = get_loop_body (loop);
+ n = 0;
+ for (i = 0; i < loop->num_nodes; i++)
+ if (EDGE_COUNT (body[i]->succs) >= 2)
+ n++;
+ free (body);
+
+ return n;
+}
+
+/* Adds basic block BB to LOOP. */
+void
+add_bb_to_loop (basic_block bb, struct loop *loop)
+{
+ int i;
+
+ 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
+remove_bb_from_loops (basic_block bb)
+{
+ int i;
+ struct loop *loop = bb->loop_father;
+
+ 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 *
+find_common_loop (struct loop *loop_s, struct loop *loop_d)
+{
+ if (!loop_s) return loop_d;
+ if (!loop_d) return loop_s;
+
+ if (loop_s->depth < loop_d->depth)
+ loop_d = loop_d->pred[loop_s->depth];
+ else if (loop_s->depth > loop_d->depth)
+ loop_s = loop_s->pred[loop_d->depth];
+
+ while (loop_s != loop_d)
{
- sbitmap_vector_free (dom);
+ loop_s = loop_s->outer;
+ loop_d = loop_d->outer;
}
+ return loop_s;
+}
- loops->num = num_loops;
+/* Cancels the LOOP; it must be innermost one. */
+void
+cancel_loop (struct loops *loops, struct loop *loop)
+{
+ basic_block *bbs;
+ unsigned i;
+
+ gcc_assert (!loop->inner);
- /* Build the loop hierarchy tree. */
- flow_loops_tree_build (loops);
+ /* Move blocks up one level (they should be removed as soon as possible). */
+ bbs = get_loop_body (loop);
+ for (i = 0; i < loop->num_nodes; i++)
+ bbs[i]->loop_father = loop->outer;
- /* Assign the loop nesting depth and enclosed loop level for each
- loop. */
- loops->levels = flow_loops_level_compute (loops);
+ /* Remove the loop from structure. */
+ flow_loop_tree_node_remove (loop);
- return num_loops;
+ /* Remove loop from loops array. */
+ loops->parray[loop->num] = NULL;
+
+ /* Free loop data. */
+ flow_loop_free (loop);
}
-/* Update the information regarding the loops in the CFG
- specified by LOOPS. */
-int
-flow_loops_update (loops, flags)
- struct loops *loops;
- int flags;
+/* Cancels LOOP and all its subloops. */
+void
+cancel_loop_tree (struct loops *loops, struct loop *loop)
+{
+ while (loop->inner)
+ cancel_loop_tree (loops, loop->inner);
+ cancel_loop (loops, loop);
+}
+
+/* Checks that LOOPS are all right:
+ -- 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
+ -- loop latches have only single successor that is header of their loop
+ -- irreducible loops are correctly marked
+ */
+void
+verify_loop_structure (struct loops *loops)
+{
+ unsigned *sizes, i, j;
+ sbitmap irreds;
+ basic_block *bbs, bb;
+ struct loop *loop;
+ int err = 0;
+ edge e;
+
+ /* Check sizes. */
+ sizes = xcalloc (loops->num, sizeof (int));
+ 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++)
+ {
+ if (!loops->parray[i])
+ continue;
+
+ if (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);
+ err = 1;
+ }
+ }
+
+ /* Check get_loop_body. */
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = 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.",
+ bbs[j]->index, i);
+ err = 1;
+ }
+ free (bbs);
+ }
+
+ /* Check headers and latches. */
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ if ((loops->state & LOOPS_HAVE_PREHEADERS)
+ && EDGE_COUNT (loop->header->preds) != 2)
+ {
+ error ("Loop %d's header does not have exactly 2 entries.", i);
+ err = 1;
+ }
+ if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
+ {
+ if (EDGE_COUNT (loop->latch->succs) != 1)
+ {
+ error ("Loop %d's latch does not have exactly 1 successor.", i);
+ err = 1;
+ }
+ if (EDGE_SUCC (loop->latch, 0)->dest != loop->header)
+ {
+ 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);
+ err = 1;
+ }
+ }
+ if (loop->header->loop_father != loop)
+ {
+ error ("Loop %d's header does not belong directly to it.", i);
+ err = 1;
+ }
+ if ((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);
+ err = 1;
+ }
+ }
+
+ /* Check irreducible loops. */
+ if (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_EACH_EDGE (e, ei, bb->succs)
+ if (e->flags & EDGE_IRREDUCIBLE_LOOP)
+ e->flags |= EDGE_ALL_FLAGS + 1;
+ }
+
+ /* Recount it. */
+ mark_irreducible_loops (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);
+ 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);
+ err = 1;
+ }
+ 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.",
+ 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.",
+ e->src->index, e->dest->index);
+ err = 1;
+ }
+ e->flags &= ~(EDGE_ALL_FLAGS + 1);
+ }
+ }
+ free (irreds);
+ }
+
+ /* Check the single_exit. */
+ if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+ {
+ memset (sizes, 0, sizeof (unsigned) * loops->num);
+ FOR_EACH_BB (bb)
+ {
+ edge_iterator ei;
+ if (bb->loop_father == 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 (loop->single_exit
+ && loop->single_exit != e)
+ {
+ error ("Wrong single exit %d->%d recorded for loop %d.",
+ loop->single_exit->src->index,
+ loop->single_exit->dest->index,
+ loop->num);
+ error ("Right exit is %d->%d.",
+ e->src->index, e->dest->index);
+ err = 1;
+ }
+ }
+ }
+ }
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ if (sizes[i] == 1
+ && !loop->single_exit)
+ {
+ error ("Single exit not recorded for loop %d.", loop->num);
+ err = 1;
+ }
+
+ if (sizes[i] != 1
+ && loop->single_exit)
+ {
+ error ("Loop %d should not have single exit (%d -> %d).",
+ loop->num,
+ loop->single_exit->src->index,
+ loop->single_exit->dest->index);
+ err = 1;
+ }
+ }
+ }
+
+ gcc_assert (!err);
+
+ free (sizes);
+}
+
+/* Returns latch edge of LOOP. */
+edge
+loop_latch_edge (const struct loop *loop)
{
- /* 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->array)
- flow_loops_free (loops);
+ return find_edge (loop->latch, loop->header);
+}
- return flow_loops_find (loops, flags);
+/* Returns preheader edge of LOOP. */
+edge
+loop_preheader_edge (const struct loop *loop)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, loop->header->preds)
+ if (e->src != loop->latch)
+ break;
+
+ return e;
}
-/* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
+/* Returns true if E is an exit of LOOP. */
-int
-flow_loop_outside_edge_p (loop, e)
- const struct loop *loop;
- edge e;
+bool
+loop_exit_edge_p (const struct loop *loop, edge e)
{
- if (e->dest != loop->header)
- abort ();
- return (e->src == ENTRY_BLOCK_PTR) || ! TEST_BIT (loop->nodes, e->src->index);
+ return (flow_bb_inside_loop_p (loop, e->src)
+ && !flow_bb_inside_loop_p (loop, e->dest));
}
OSDN Git Service
