#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "toplev.h"
+#include "cfgloop.h"
+#include "flags.h"
/* Ratio of frequencies of edges so that one of more latch edges is
considered to belong to inner loop with same header. */
static int flow_loop_nodes_find PARAMS ((basic_block, struct loop *));
static void flow_loop_pre_header_scan PARAMS ((struct loop *));
static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
- const sbitmap *));
+ dominance_info));
static int flow_loop_level_compute PARAMS ((struct loop *));
static int flow_loops_level_compute PARAMS ((struct loops *));
+static void establish_preds PARAMS ((struct loop *));
static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
edge, int));
static void canonicalize_loop_headers PARAMS ((void));
static bool glb_enum_p PARAMS ((basic_block, void *));
static void redirect_edge_with_latch_update PARAMS ((edge, basic_block));
-static void flow_loop_free PARAMS ((struct loop *));
\f
/* Dump loop related CFG information. */
}
}
-/* 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. */
bool
flow_loop_nested_p (outer, loop)
int verbose;
{
basic_block *bbs;
- int i;
+ unsigned i;
if (! loop || ! loop->header)
return;
}
/* Free data allocated for LOOP. */
-static void
+void
flow_loop_free (loop)
struct loop *loop;
{
{
if (loops->parray)
{
- int i;
+ unsigned i;
if (! loops->num)
abort ();
loops->parray = NULL;
if (loops->cfg.dom)
- sbitmap_vector_free (loops->cfg.dom);
+ free_dominance_info (loops->cfg.dom);
if (loops->cfg.dfs_order)
free (loops->cfg.dfs_order);
{
edge e;
basic_block node, *bbs;
- int num_exits, i;
+ unsigned num_exits, i;
loop->exit_edges = NULL;
loop->num_exits = 0;
basic_block *stack;
int sp;
int num_nodes = 1;
- int findex, lindex;
header->loop_father = loop;
header->loop_depth = loop->depth;
- findex = lindex = header->index;
if (loop->latch->loop_father != loop)
{
static basic_block
flow_loop_pre_header_find (header, dom)
basic_block header;
- const sbitmap *dom;
+ dominance_info dom;
{
basic_block pre_header;
edge e;
basic_block node = e->src;
if (node != ENTRY_BLOCK_PTR
- && ! TEST_BIT (dom[node->index], header->index))
+ && ! dominated_by_p (dom, node, header))
{
if (pre_header == NULL)
pre_header = node;
return pre_header;
}
+static void
+establish_preds (loop)
+ struct loop *loop;
+{
+ struct loop *ploop, *father = loop->outer;
+
+ loop->depth = father->depth + 1;
+ 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;
+
+ for (ploop = loop->inner; ploop; ploop = ploop->next)
+ establish_preds (ploop);
+}
+
/* Add LOOP to the loop hierarchy tree where FATHER is father of the
- added loop. */
+ added loop. If LOOP has some children, take care of that their
+ pred field will be initialized correctly. */
void
flow_loop_tree_node_add (father, loop)
father->inner = loop;
loop->outer = father;
- loop->depth = father->depth + 1;
- loop->pred = xmalloc (sizeof (struct loop *) * loop->depth);
- memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
- loop->pred[father->depth] = father;
+ establish_preds (loop);
}
/* Remove LOOP from the loop hierarchy tree. */
insn = PREV_INSN (first_insn_after_basic_block_note (bb));
+ /* For empty block split_block will return NULL. */
+ if (bb->end == insn)
+ emit_note_after (NOTE_INSN_DELETED, insn);
+
fallthru = split_block (bb, insn);
dummy = fallthru->src;
bb = fallthru->dest;
HEADER_BLOCK (dummy) = 0;
HEADER_BLOCK (bb) = 1;
- /* Redirect back edges we want to keep. */
+ /* Redirect back edges we want to keep. */
for (e = dummy->pred; e; e = next_e)
{
next_e = e->pred_next;
static void
canonicalize_loop_headers ()
{
- sbitmap *dom;
+ dominance_info dom;
basic_block header;
edge e;
/* Compute the dominators. */
- dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
- calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
+ dom = calculate_dominance_info (CDI_DOMINATORS);
alloc_aux_for_blocks (sizeof (int));
alloc_aux_for_edges (sizeof (int));
have_abnormal_edge = 1;
if (latch != ENTRY_BLOCK_PTR
- && TEST_BIT (dom[latch->index], header->index))
+ && dominated_by_p (dom, latch, header))
{
num_latches++;
LATCH_EDGE (e) = 1;
free_aux_for_blocks ();
free_aux_for_edges ();
- sbitmap_vector_free (dom);
+ free_dominance_info (dom);
}
/* Find all the natural loops in the function and save in LOOPS structure and
int num_loops;
edge e;
sbitmap headers;
- sbitmap *dom;
+ dominance_info dom;
int *dfs_order;
int *rc_order;
- basic_block header, bb;
+ basic_block header;
+ basic_block bb;
/* This function cannot be repeatedly called with different
flags to build up the loop information. The loop tree
canonicalize_loop_headers ();
/* Compute the dominators. */
- loops->cfg.dom = dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
- calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
+ dom = loops->cfg.dom = calculate_dominance_info (CDI_DOMINATORS);
/* Count the number of loop headers. This should be the
same as the number of natural loops. */
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)
+ if (e->flags & EDGE_ABNORMAL)
+ break;
+ if (e)
+ continue;
+
for (e = header->pred; e; e = e->pred_next)
{
basic_block latch = e->src;
if (e->flags & EDGE_ABNORMAL)
- {
- if (more_latches)
- {
- RESET_BIT (headers, header->index);
- num_loops--;
- }
- break;
- }
+ abort ();
/* 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. */
- if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index],
- header->index))
+ if (latch != ENTRY_BLOCK_PTR && dominated_by_p (dom, latch, header))
{
/* Shared headers should be eliminated by now. */
if (more_latches)
basic_block latch = e->src;
if (latch != ENTRY_BLOCK_PTR
- && TEST_BIT (dom[latch->index], header->index))
+ && dominated_by_p (dom, latch, header))
{
loop->latch = latch;
break;
else
{
loops->cfg.dom = NULL;
- sbitmap_vector_free (dom);
+ free_dominance_info (dom);
}
+
+ loops->state = 0;
#ifdef ENABLE_CHECKING
verify_flow_info ();
- verify_loop_structure (loops, 0);
+ verify_loop_structure (loops);
#endif
return loops->num;
return flow_loops_find (loops, flags);
}
-/* Return non-zero if basic block BB belongs to LOOP. */
+/* Return nonzero if basic block BB belongs to LOOP. */
bool
flow_bb_inside_loop_p (loop, bb)
const struct loop *loop;
return loop == source_loop || flow_loop_nested_p (loop, source_loop);
}
-/* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
+/* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
bool
flow_loop_outside_edge_p (loop, e)
const struct loop *loop;
{
basic_block *tovisit, bb;
- int tv = 0;
+ unsigned tv = 0;
if (!loop->num_nodes)
abort ();
if (loop->latch == EXIT_BLOCK_PTR)
{
/* There may be blocks unreachable from EXIT_BLOCK. */
- if (loop->num_nodes != n_basic_blocks + 2)
+ if (loop->num_nodes != (unsigned) n_basic_blocks + 2)
abort ();
FOR_EACH_BB (bb)
tovisit[tv++] = bb;
return tovisit;
}
+/* Gets exit edges of a LOOP, returning their number in N_EDGES. */
+edge *
+get_loop_exit_edges (loop, n_edges)
+ const struct loop *loop;
+ unsigned *n_edges;
+{
+ edge *edges, e;
+ unsigned i, n;
+ basic_block * body;
+
+ if (loop->latch == EXIT_BLOCK_PTR)
+ abort ();
+
+ 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)
+ 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;
+ free (body);
+
+ return edges;
+}
+
/* Adds basic block BB to LOOP. */
void
add_bb_to_loop (bb, loop)
return loop_s;
}
+/* Cancels the LOOP; it must be innermost one. */
+void
+cancel_loop (loops, loop)
+ struct loops *loops;
+ struct loop *loop;
+{
+ basic_block *bbs;
+ unsigned i;
+
+ if (loop->inner)
+ abort ();
+
+ /* 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;
+
+ /* Remove the loop from structure. */
+ flow_loop_tree_node_remove (loop);
+
+ /* Remove loop from loops array. */
+ loops->parray[loop->num] = NULL;
+
+ /* Free loop data. */
+ flow_loop_free (loop);
+}
+
+/* Cancels LOOP and all its subloops. */
+void
+cancel_loop_tree (loops, loop)
+ struct loops *loops;
+ struct loop *loop;
+{
+ while (loop->inner)
+ cancel_loop_tree (loops, loop->inner);
+ cancel_loop (loops, loop);
+}
+
/* Checks that LOOPS are allright:
-- sizes of loops are allright
-- 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 (loops, flags)
+verify_loop_structure (loops)
struct loops *loops;
- int flags;
{
- int *sizes, i, j;
+ 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));
if (!loop)
continue;
- if ((flags & VLS_EXPECT_PREHEADERS)
+ if ((loops->state & LOOPS_HAVE_PREHEADERS)
&& (!loop->header->pred->pred_next
|| loop->header->pred->pred_next->pred_next))
{
error ("Loop %d's header does not have exactly 2 entries.", i);
err = 1;
}
- if (flags & VLS_EXPECT_SIMPLE_LATCHES)
+ if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
{
if (!loop->latch->succ
|| loop->latch->succ->succ_next)
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)
+ {
+ 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)
+ if (e->flags & EDGE_IRREDUCIBLE_LOOP)
+ e->flags |= EDGE_ALL_FLAGS + 1;
+ }
+
+ /* Recount it. */
+ mark_irreducible_loops (loops);
+
+ /* Compare. */
+ FOR_EACH_BB (bb)
+ {
+ 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 (e = bb->succ; e; e = e->succ_next)
+ {
+ 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);
}
if (err)
/* Returns latch edge of LOOP. */
edge
loop_latch_edge (loop)
- struct loop *loop;
+ const struct loop *loop;
{
edge e;
/* Returns preheader edge of LOOP. */
edge
loop_preheader_edge (loop)
- struct loop *loop;
+ const struct loop *loop;
{
edge e;
OSDN Git Service
