/* Natural loop discovery code for GNU compiler.
- Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2012
- Free Software Foundation, Inc.
+ Copyright (C) 2000-2014 Free Software Foundation, Inc.
This file is part of GCC.
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "vec.h"
+#include "machmode.h"
+#include "hard-reg-set.h"
+#include "input.h"
#include "function.h"
+#include "predict.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "diagnostic-core.h"
#include "flags.h"
#include "tree.h"
-#include "tree-flow.h"
-#include "pointer-set.h"
-#include "ggc.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
#include "dumpfile.h"
static void flow_loops_cfg_dump (FILE *);
if (!file)
return;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
edge succ;
edge_iterator ei;
void
flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
{
- loop_iterator li;
struct loop *loop;
if (!current_loops || ! file)
return;
- fprintf (file, ";; %d loops found\n", number_of_loops ());
+ fprintf (file, ";; %d loops found\n", number_of_loops (cfun));
- FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
+ FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
{
flow_loop_dump (loop, file, loop_dump_aux, verbose);
}
struct loop *
alloc_loop (void)
{
- struct loop *loop = ggc_alloc_cleared_loop ();
+ struct loop *loop = ggc_cleared_alloc<struct loop> ();
- loop->exits = ggc_alloc_cleared_loop_exit ();
+ loop->exits = ggc_cleared_alloc<loop_exit> ();
loop->exits->next = loop->exits->prev = loop->exits;
loop->can_be_parallel = false;
-
+ loop->nb_iterations_upper_bound = 0;
+ loop->nb_iterations_estimate = 0;
return loop;
}
/* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
(including the root of the loop tree). */
-static void
-init_loops_structure (struct loops *loops, unsigned num_loops)
+void
+init_loops_structure (struct function *fn,
+ struct loops *loops, unsigned num_loops)
{
struct loop *root;
/* Dummy loop containing whole function. */
root = alloc_loop ();
- root->num_nodes = n_basic_blocks;
- root->latch = EXIT_BLOCK_PTR;
- root->header = ENTRY_BLOCK_PTR;
- ENTRY_BLOCK_PTR->loop_father = root;
- EXIT_BLOCK_PTR->loop_father = root;
+ root->num_nodes = n_basic_blocks_for_fn (fn);
+ root->latch = EXIT_BLOCK_PTR_FOR_FN (fn);
+ root->header = ENTRY_BLOCK_PTR_FOR_FN (fn);
+ ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
+ EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
loops->larray->quick_push (root);
loops->tree_root = root;
}
+/* Returns whether HEADER is a loop header. */
+
+bool
+bb_loop_header_p (basic_block header)
+{
+ edge_iterator ei;
+ edge e;
+
+ /* If we have an abnormal predecessor, do not consider the
+ loop (not worth the problems). */
+ if (bb_has_abnormal_pred (header))
+ return false;
+
+ /* 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. */
+ FOR_EACH_EDGE (e, ei, header->preds)
+ {
+ basic_block latch = e->src;
+ if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun)
+ && dominated_by_p (CDI_DOMINATORS, latch, header))
+ return true;
+ }
+
+ return false;
+}
+
/* Find all the natural loops in the function and save in LOOPS structure and
recalculate loop_father information in basic block structures.
- Return the number of natural loops found. */
+ If LOOPS is non-NULL then the loop structures for already recorded loops
+ will be re-used and their number will not change. We assume that no
+ stale loops exist in LOOPS.
+ When LOOPS is NULL it is allocated and re-built from scratch.
+ Return the built LOOPS structure. */
-int
+struct loops *
flow_loops_find (struct loops *loops)
{
- int b;
- int num_loops;
- edge e;
- sbitmap headers;
- int *dfs_order;
+ bool from_scratch = (loops == NULL);
int *rc_order;
- basic_block header;
- basic_block bb;
+ int b;
+ unsigned i;
/* Ensure that the dominators are computed. */
calculate_dominance_info (CDI_DOMINATORS);
- /* Taking care of this degenerate case makes the rest of
- this code simpler. */
- if (n_basic_blocks == NUM_FIXED_BLOCKS)
+ if (!loops)
{
- init_loops_structure (loops, 1);
- return 1;
+ loops = ggc_cleared_alloc<struct loops> ();
+ init_loops_structure (cfun, loops, 1);
}
- dfs_order = NULL;
- rc_order = NULL;
+ /* Ensure that loop exits were released. */
+ gcc_assert (loops->exits == NULL);
- /* Count the number of loop headers. This should be the
- same as the number of natural loops. */
- headers = sbitmap_alloc (last_basic_block);
- bitmap_clear (headers);
+ /* Taking care of this degenerate case makes the rest of
+ this code simpler. */
+ if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
+ return loops;
- num_loops = 0;
- FOR_EACH_BB (header)
- {
- edge_iterator ei;
+ /* The root loop node contains all basic-blocks. */
+ loops->tree_root->num_nodes = n_basic_blocks_for_fn (cfun);
- /* If we have an abnormal predecessor, do not consider the
- loop (not worth the problems). */
- if (bb_has_abnormal_pred (header))
- continue;
+ /* Compute depth first search order of the CFG so that outer
+ natural loops will be found before inner natural loops. */
+ rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ pre_and_rev_post_order_compute (NULL, rc_order, false);
- FOR_EACH_EDGE (e, ei, header->preds)
+ /* Gather all loop headers in reverse completion order and allocate
+ loop structures for loops that are not already present. */
+ auto_vec<loop_p> larray (loops->larray->length ());
+ for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++)
+ {
+ basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]);
+ if (bb_loop_header_p (header))
{
- basic_block latch = e->src;
-
- gcc_assert (!(e->flags & EDGE_ABNORMAL));
+ struct loop *loop;
- /* 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
- && dominated_by_p (CDI_DOMINATORS, latch, header))
+ /* The current active loop tree has valid loop-fathers for
+ header blocks. */
+ if (!from_scratch
+ && header->loop_father->header == header)
{
- /* Shared headers should be eliminated by now. */
- bitmap_set_bit (headers, header->index);
- num_loops++;
+ loop = header->loop_father;
+ /* If we found an existing loop remove it from the
+ loop tree. It is going to be inserted again
+ below. */
+ flow_loop_tree_node_remove (loop);
}
+ else
+ {
+ /* Otherwise allocate a new loop structure for the loop. */
+ loop = alloc_loop ();
+ /* ??? We could re-use unused loop slots here. */
+ loop->num = loops->larray->length ();
+ vec_safe_push (loops->larray, loop);
+ loop->header = header;
+
+ if (!from_scratch
+ && dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "flow_loops_find: discovered new "
+ "loop %d with header %d\n",
+ loop->num, header->index);
+ }
+ /* Reset latch, we recompute it below. */
+ loop->latch = NULL;
+ larray.safe_push (loop);
}
- }
- /* Allocate loop structures. */
- init_loops_structure (loops, num_loops + 1);
+ /* Make blocks part of the loop root node at start. */
+ header->loop_father = loops->tree_root;
+ }
- /* Find and record information about all the natural loops
- in the CFG. */
- FOR_EACH_BB (bb)
- bb->loop_father = loops->tree_root;
+ free (rc_order);
- if (num_loops)
+ /* Now iterate over the loops found, insert them into the loop tree
+ and assign basic-block ownership. */
+ for (i = 0; i < larray.length (); ++i)
{
- /* Compute depth first search order of the CFG so that outer
- natural loops will be found before inner natural loops. */
- 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);
+ struct loop *loop = larray[i];
+ basic_block header = loop->header;
+ edge_iterator ei;
+ edge e;
- num_loops = 1;
+ flow_loop_tree_node_add (header->loop_father, loop);
+ loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
- for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
+ /* Look for the latch for this header block, if it has just a
+ single one. */
+ FOR_EACH_EDGE (e, ei, header->preds)
{
- 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 (!bitmap_bit_p (headers, rc_order[b]))
- continue;
-
- header = BASIC_BLOCK (rc_order[b]);
-
- loop = alloc_loop ();
- loops->larray->quick_push (loop);
-
- loop->header = header;
- loop->num = num_loops;
- num_loops++;
-
- flow_loop_tree_node_add (header->loop_father, loop);
- loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
+ basic_block latch = e->src;
- /* Look for the latch for this header block, if it has just a
- single one. */
- FOR_EACH_EDGE (e, ei, header->preds)
+ if (flow_bb_inside_loop_p (loop, latch))
{
- basic_block latch = e->src;
-
- if (flow_bb_inside_loop_p (loop, latch))
+ if (loop->latch != NULL)
{
- if (loop->latch != NULL)
- {
- /* More than one latch edge. */
- loop->latch = NULL;
- break;
- }
- loop->latch = latch;
+ /* More than one latch edge. */
+ loop->latch = NULL;
+ break;
}
+ loop->latch = latch;
}
}
-
- free (dfs_order);
- free (rc_order);
}
- sbitmap_free (headers);
-
- loops->exits = NULL;
- return loops->larray->length ();
+ return loops;
}
/* Ratio of frequencies of edges so that one of more latch edges is
/* Callback for make_forwarder_block. Returns true if the edge E is marked
in the set MFB_REIS_SET. */
-static struct pointer_set_t *mfb_reis_set;
+static hash_set<edge> *mfb_reis_set;
static bool
mfb_redirect_edges_in_set (edge e)
{
- return pointer_set_contains (mfb_reis_set, e);
+ return mfb_reis_set->contains (e);
}
/* Creates a subloop of LOOP with latch edge LATCH. */
edge e, new_entry;
struct loop *new_loop;
- mfb_reis_set = pointer_set_create ();
+ mfb_reis_set = new hash_set<edge>;
FOR_EACH_EDGE (e, ei, loop->header->preds)
{
if (e != latch)
- pointer_set_insert (mfb_reis_set, e);
+ mfb_reis_set->add (e);
}
new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
NULL);
- pointer_set_destroy (mfb_reis_set);
+ delete mfb_reis_set;
loop->header = new_entry->src;
if (dump_file)
fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
- mfb_reis_set = pointer_set_create ();
+ mfb_reis_set = new hash_set<edge>;
FOR_EACH_VEC_ELT (latches, i, e)
- pointer_set_insert (mfb_reis_set, e);
+ mfb_reis_set->add (e);
latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
NULL);
- pointer_set_destroy (mfb_reis_set);
+ delete mfb_reis_set;
loop->header = latch->dest;
loop->latch = latch->src;
block. This would cause problems if the entry edge was the one from the
entry block. To avoid having to handle this case specially, split
such entry edge. */
- e = find_edge (ENTRY_BLOCK_PTR, loop->header);
+ e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
if (e)
split_edge (e);
void
disambiguate_loops_with_multiple_latches (void)
{
- loop_iterator li;
struct loop *loop;
- FOR_EACH_LOOP (li, loop, 0)
+ FOR_EACH_LOOP (loop, 0)
{
if (!loop->latch)
disambiguate_multiple_latches (loop);
{
struct loop *source_loop;
- if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
+ if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
+ || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
return 0;
source_loop = bb->loop_father;
body = XNEWVEC (basic_block, loop->num_nodes);
- if (loop->latch == EXIT_BLOCK_PTR)
+ if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
{
/* There may be blocks unreachable from EXIT_BLOCK, hence we need to
special-case the fake loop that contains the whole function. */
- gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
+ gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun));
body[tv++] = loop->header;
- body[tv++] = EXIT_BLOCK_PTR;
- FOR_EACH_BB (bb)
+ body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun);
+ FOR_EACH_BB_FN (bb, cfun)
body[tv++] = bb;
}
else
tovisit = XNEWVEC (basic_block, loop->num_nodes);
- gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
tv = 0;
fill_sons_in_loop (loop, loop->header, tovisit, &tv);
unsigned int vc = 1;
gcc_assert (loop->num_nodes);
- gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
blocks = XNEWVEC (basic_block, loop->num_nodes);
visited = BITMAP_ALLOC (NULL);
/* Hash function for struct loop_exit. */
-static hashval_t
-loop_exit_hash (const void *ex)
+hashval_t
+loop_exit_hasher::hash (loop_exit *exit)
{
- const struct loop_exit *const exit = (const struct loop_exit *) ex;
-
return htab_hash_pointer (exit->e);
}
/* Equality function for struct loop_exit. Compares with edge. */
-static int
-loop_exit_eq (const void *ex, const void *e)
+bool
+loop_exit_hasher::equal (loop_exit *exit, edge e)
{
- const struct loop_exit *const exit = (const struct loop_exit *) ex;
-
return exit->e == e;
}
/* Frees the list of loop exit descriptions EX. */
-static void
-loop_exit_free (void *ex)
+void
+loop_exit_hasher::remove (loop_exit *exit)
{
- struct loop_exit *exit = (struct loop_exit *) ex, *next;
-
+ loop_exit *next;
for (; exit; exit = next)
{
next = exit->next_e;
static struct loop_exit *
get_exit_descriptions (edge e)
{
- return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e,
- htab_hash_pointer (e));
+ return current_loops->exits->find_with_hash (e, htab_hash_pointer (e));
}
/* Updates the lists of loop exits in that E appears.
void
rescan_loop_exit (edge e, bool new_edge, bool removed)
{
- void **slot;
struct loop_exit *exits = NULL, *exit;
struct loop *aloop, *cloop;
aloop != cloop;
aloop = loop_outer (aloop))
{
- exit = ggc_alloc_loop_exit ();
+ exit = ggc_alloc<loop_exit> ();
exit->e = e;
exit->next = aloop->exits->next;
if (!exits && new_edge)
return;
- slot = htab_find_slot_with_hash (current_loops->exits, e,
- htab_hash_pointer (e),
- exits ? INSERT : NO_INSERT);
+ loop_exit **slot
+ = current_loops->exits->find_slot_with_hash (e, htab_hash_pointer (e),
+ exits ? INSERT : NO_INSERT);
if (!slot)
return;
if (exits)
{
if (*slot)
- loop_exit_free (*slot);
+ loop_exit_hasher::remove (*slot);
*slot = exits;
}
else
- htab_clear_slot (current_loops->exits, slot);
+ current_loops->exits->clear_slot (slot);
}
/* For each loop, record list of exit edges, and start maintaining these
loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
gcc_assert (current_loops->exits == NULL);
- current_loops->exits = htab_create_ggc (2 * number_of_loops (),
- loop_exit_hash, loop_exit_eq,
- loop_exit_free);
+ current_loops->exits
+ = hash_table<loop_exit_hasher>::create_ggc (2 * number_of_loops (cfun));
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
FOR_EACH_EDGE (e, ei, bb->succs)
{
/* Dumps information about the exit in *SLOT to FILE.
Callback for htab_traverse. */
-static int
-dump_recorded_exit (void **slot, void *file)
+int
+dump_recorded_exit (loop_exit **slot, FILE *file)
{
- struct loop_exit *exit = (struct loop_exit *) *slot;
+ struct loop_exit *exit = *slot;
unsigned n = 0;
edge e = exit->e;
for (; exit != NULL; exit = exit->next_e)
n++;
- fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n",
+ fprintf (file, "Edge %d->%d exits %u loops\n",
e->src->index, e->dest->index, n);
return 1;
{
if (!current_loops->exits)
return;
- htab_traverse (current_loops->exits, dump_recorded_exit, file);
+ current_loops->exits->traverse<FILE *, dump_recorded_exit> (file);
}
/* Releases lists of loop exits. */
release_recorded_exits (void)
{
gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
- htab_delete (current_loops->exits);
+ current_loops->exits->empty ();
current_loops->exits = NULL;
loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
}
edge_iterator ei;
struct loop_exit *exit;
- gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
/* If we maintain the lists of exits, use them. Otherwise we must
scan the body of the loop. */
unsigned i, n;
basic_block * body;
- gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
body = get_loop_body (loop);
n = 0;
{
unsigned *sizes, i, j;
sbitmap irreds;
- basic_block *bbs, bb;
+ basic_block bb, *bbs;
struct loop *loop;
int err = 0;
edge e;
- unsigned num = number_of_loops ();
- loop_iterator li;
+ unsigned num = number_of_loops (cfun);
struct loop_exit *exit, *mexit;
bool dom_available = dom_info_available_p (CDI_DOMINATORS);
- sbitmap visited = sbitmap_alloc (last_basic_block);
+ sbitmap visited;
+
+ if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
+ {
+ error ("loop verification on loop tree that needs fixup");
+ err = 1;
+ }
/* We need up-to-date dominators, compute or verify them. */
if (!dom_available)
else
verify_dominators (CDI_DOMINATORS);
- /* Check sizes. */
- sizes = XCNEWVEC (unsigned, num);
- sizes[0] = 2;
-
- FOR_EACH_BB (bb)
- for (loop = bb->loop_father; loop; loop = loop_outer (loop))
- sizes[loop->num]++;
-
- FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
+ /* Check the headers. */
+ FOR_EACH_BB_FN (bb, cfun)
+ if (bb_loop_header_p (bb))
+ {
+ if (bb->loop_father->header == NULL)
+ {
+ error ("loop with header %d marked for removal", bb->index);
+ err = 1;
+ }
+ else if (bb->loop_father->header != bb)
+ {
+ error ("loop with header %d not in loop tree", bb->index);
+ err = 1;
+ }
+ }
+ else if (bb->loop_father->header == bb)
+ {
+ error ("non-loop with header %d not marked for removal", bb->index);
+ err = 1;
+ }
+
+ /* Check the recorded loop father and sizes of loops. */
+ visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ bitmap_clear (visited);
+ bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
+ FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
{
- i = loop->num;
+ unsigned n;
- if (loop->num_nodes != sizes[i])
+ if (loop->header == NULL)
{
- error ("size of loop %d should be %d, not %d",
- i, sizes[i], loop->num_nodes);
+ error ("removed loop %d in loop tree", loop->num);
err = 1;
+ continue;
}
- }
-
- /* Check get_loop_body. */
- FOR_EACH_LOOP (li, loop, 0)
- {
- 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, loop->num);
- err = 1;
- }
- free (bbs);
- }
- bitmap_clear (visited);
- FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
- {
- bbs = get_loop_body (loop);
+ n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
+ if (loop->num_nodes != n)
+ {
+ error ("size of loop %d should be %d, not %d",
+ loop->num, n, loop->num_nodes);
+ err = 1;
+ }
- for (j = 0; j < loop->num_nodes; j++)
+ for (j = 0; j < n; j++)
{
bb = bbs[j];
+ if (!flow_bb_inside_loop_p (loop, bb))
+ {
+ error ("bb %d does not belong to loop %d",
+ bb->index, loop->num);
+ err = 1;
+ }
+
/* Ignore this block if it is in an inner loop. */
if (bitmap_bit_p (visited, bb->index))
continue;
err = 1;
}
}
- free (bbs);
}
+ free (bbs);
+ sbitmap_free (visited);
/* Check headers and latches. */
- FOR_EACH_LOOP (li, loop, 0)
+ FOR_EACH_LOOP (loop, 0)
{
i = loop->num;
-
+ if (loop->header == NULL)
+ continue;
+ if (!bb_loop_header_p (loop->header))
+ {
+ error ("loop %d%'s header is not a loop header", i);
+ err = 1;
+ }
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);
err = 1;
}
+ if (loop->latch)
+ {
+ if (!find_edge (loop->latch, loop->header))
+ {
+ error ("loop %d%'s latch does not have an edge to its header", i);
+ err = 1;
+ }
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, loop->header))
+ {
+ error ("loop %d%'s latch is not dominated by its header", i);
+ err = 1;
+ }
+ }
if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
{
if (!single_succ_p (loop->latch))
if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
{
/* Record old info. */
- irreds = sbitmap_alloc (last_basic_block);
- FOR_EACH_BB (bb)
+ irreds = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ FOR_EACH_BB_FN (bb, cfun)
{
edge_iterator ei;
if (bb->flags & BB_IRREDUCIBLE_LOOP)
mark_irreducible_loops ();
/* Compare. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
edge_iterator ei;
}
/* Check the recorded loop exits. */
- FOR_EACH_LOOP (li, loop, 0)
+ FOR_EACH_LOOP (loop, 0)
{
if (!loop->exits || loop->exits->e != NULL)
{
{
unsigned n_exits = 0, eloops;
+ sizes = XCNEWVEC (unsigned, num);
memset (sizes, 0, sizeof (unsigned) * num);
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
edge_iterator ei;
if (bb->loop_father == current_loops->tree_root)
eloops++;
for (loop = bb->loop_father;
- loop != e->dest->loop_father;
+ loop != e->dest->loop_father
+ /* When a loop exit is also an entry edge which
+ can happen when avoiding CFG manipulations
+ then the last loop exited is the outer loop
+ of the loop entered. */
+ && loop != loop_outer (e->dest->loop_father);
loop = loop_outer (loop))
{
eloops--;
}
}
- if (n_exits != htab_elements (current_loops->exits))
+ if (n_exits != current_loops->exits->elements ())
{
error ("too many loop exits recorded");
err = 1;
}
- FOR_EACH_LOOP (li, loop, 0)
+ FOR_EACH_LOOP (loop, 0)
{
eloops = 0;
for (exit = loop->exits->next; exit->e; exit = exit->next)
err = 1;
}
}
+
+ free (sizes);
}
gcc_assert (!err);
- sbitmap_free (visited);
- free (sizes);
if (!dom_available)
free_dominance_info (CDI_DOMINATORS);
}
location_t
get_loop_location (struct loop *loop)
{
- rtx insn = NULL;
+ rtx_insn *insn = NULL;
struct niter_desc *desc = NULL;
edge exit;
return DECL_SOURCE_LOCATION (current_function_decl);
}
+/* Records that every statement in LOOP is executed I_BOUND times.
+ REALISTIC is true if I_BOUND is expected to be close to the real number
+ of iterations. UPPER is true if we are sure the loop iterates at most
+ I_BOUND times. */
+
+void
+record_niter_bound (struct loop *loop, const widest_int &i_bound,
+ bool realistic, bool upper)
+{
+ /* Update the bounds only when there is no previous estimation, or when the
+ current estimation is smaller. */
+ if (upper
+ && (!loop->any_upper_bound
+ || wi::ltu_p (i_bound, loop->nb_iterations_upper_bound)))
+ {
+ loop->any_upper_bound = true;
+ loop->nb_iterations_upper_bound = i_bound;
+ }
+ if (realistic
+ && (!loop->any_estimate
+ || wi::ltu_p (i_bound, loop->nb_iterations_estimate)))
+ {
+ loop->any_estimate = true;
+ loop->nb_iterations_estimate = i_bound;
+ }
+
+ /* If an upper bound is smaller than the realistic estimate of the
+ number of iterations, use the upper bound instead. */
+ if (loop->any_upper_bound
+ && loop->any_estimate
+ && wi::ltu_p (loop->nb_iterations_upper_bound,
+ loop->nb_iterations_estimate))
+ loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
+}
+
+/* Similar to get_estimated_loop_iterations, but returns the estimate only
+ if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
+ on the number of iterations of LOOP could not be derived, returns -1. */
+
+HOST_WIDE_INT
+get_estimated_loop_iterations_int (struct loop *loop)
+{
+ widest_int nit;
+ HOST_WIDE_INT hwi_nit;
+
+ if (!get_estimated_loop_iterations (loop, &nit))
+ return -1;
+
+ if (!wi::fits_shwi_p (nit))
+ return -1;
+ hwi_nit = nit.to_shwi ();
+
+ return hwi_nit < 0 ? -1 : hwi_nit;
+}
+
+/* Returns an upper bound on the number of executions of statements
+ in the LOOP. For statements before the loop exit, this exceeds
+ the number of execution of the latch by one. */
+
+HOST_WIDE_INT
+max_stmt_executions_int (struct loop *loop)
+{
+ HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
+ HOST_WIDE_INT snit;
+
+ if (nit == -1)
+ return -1;
+
+ snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
+
+ /* If the computation overflows, return -1. */
+ return snit < 0 ? -1 : snit;
+}
+
+/* Sets NIT to the estimated number of executions of the latch of the
+ LOOP. If we have no reliable estimate, the function returns false, otherwise
+ returns true. */
+
+bool
+get_estimated_loop_iterations (struct loop *loop, widest_int *nit)
+{
+ /* Even if the bound is not recorded, possibly we can derrive one from
+ profile. */
+ if (!loop->any_estimate)
+ {
+ if (loop->header->count)
+ {
+ *nit = gcov_type_to_wide_int
+ (expected_loop_iterations_unbounded (loop) + 1);
+ return true;
+ }
+ return false;
+ }
+
+ *nit = loop->nb_iterations_estimate;
+ return true;
+}
+
+/* Sets NIT to an upper bound for the maximum number of executions of the
+ latch of the LOOP. If we have no reliable estimate, the function returns
+ false, otherwise returns true. */
+
+bool
+get_max_loop_iterations (struct loop *loop, widest_int *nit)
+{
+ if (!loop->any_upper_bound)
+ return false;
+
+ *nit = loop->nb_iterations_upper_bound;
+ return true;
+}
+
+/* Similar to get_max_loop_iterations, but returns the estimate only
+ if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
+ on the number of iterations of LOOP could not be derived, returns -1. */
+
+HOST_WIDE_INT
+get_max_loop_iterations_int (struct loop *loop)
+{
+ widest_int nit;
+ HOST_WIDE_INT hwi_nit;
+
+ if (!get_max_loop_iterations (loop, &nit))
+ return -1;
+
+ if (!wi::fits_shwi_p (nit))
+ return -1;
+ hwi_nit = nit.to_shwi ();
+
+ return hwi_nit < 0 ? -1 : hwi_nit;
+}
+
+/* Returns the loop depth of the loop BB belongs to. */
+
+int
+bb_loop_depth (const_basic_block bb)
+{
+ return bb->loop_father ? loop_depth (bb->loop_father) : 0;
+}
+
+/* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
+
+void
+mark_loop_for_removal (loop_p loop)
+{
+ loop->former_header = loop->header;
+ loop->header = NULL;
+ loop->latch = NULL;
+ loops_state_set (LOOPS_NEED_FIXUP);
+}
+
projects / gcc.git / blobdiff