#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"
#include "tree.h"
#include "tree-flow.h"
#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 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 establish_preds (struct loop *);
static void canonicalize_loop_headers (void);
static bool glb_enum_p (basic_block, void *);
static void
flow_loops_cfg_dump (const struct loops *loops, FILE *file)
{
int i;
basic_block bb;
if (! loops->num || ! file)
return;
FOR_EACH_BB (bb)
{
edge succ;
edge_iterator ei;
fprintf (file, ";; %d succs { ", bb->index);
FOR_EACH_EDGE (succ, ei, bb->succs)
fprintf (file, "%d ", succ->dest->index);
fprintf (file, "}\n");
}
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);
}
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);
}
}
bool
flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
{
return (loop->depth > outer->depth
&& loop->pred[outer->depth] == outer);
}
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];
}
void
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;
fprintf (file, ";;\n;; Loop %d:%s\n", loop->num,
loop->invalid ? " invalid" : "");
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));
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);
}
void
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;
num_loops = loops->num;
if (! num_loops || ! file)
return;
fprintf (file, ";; %d loops found, %d levels\n",
num_loops, loops->levels);
for (i = 0; i < num_loops; i++)
{
struct loop *loop = loops->parray[i];
if (!loop)
continue;
flow_loop_dump (loop, file, loop_dump_aux, verbose);
}
if (verbose)
flow_loops_cfg_dump (loops, file);
}
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);
}
void
flow_loops_free (struct loops *loops)
{
if (loops->parray)
{
unsigned i;
gcc_assert (loops->num);
for (i = 0; i < loops->num; i++)
{
struct loop *loop = loops->parray[i];
if (!loop)
continue;
flow_loop_free (loop);
}
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);
}
}
static void
flow_loop_entry_edges_find (struct loop *loop)
{
edge e;
edge_iterator ei;
int num_entries;
num_entries = 0;
FOR_EACH_EDGE (e, ei, loop->header->preds)
{
if (flow_loop_outside_edge_p (loop, e))
num_entries++;
}
gcc_assert (num_entries);
loop->entry_edges = xmalloc (num_entries * sizeof (edge *));
num_entries = 0;
FOR_EACH_EDGE (e, ei, loop->header->preds)
{
if (flow_loop_outside_edge_p (loop, e))
loop->entry_edges[num_entries++] = e;
}
loop->num_entries = num_entries;
}
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;
num_exits = 0;
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
edge_iterator ei;
node = bbs[i];
FOR_EACH_EDGE (e, ei, node->succs)
{
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 *));
num_exits = 0;
for (i = 0; i < loop->num_nodes; i++)
{
edge_iterator ei;
node = bbs[i];
FOR_EACH_EDGE (e, ei, node->succs)
{
basic_block dest = e->dest;
if (!flow_bb_inside_loop_p (loop, dest))
{
e->flags |= EDGE_LOOP_EXIT;
loop->exit_edges[num_exits++] = e;
}
}
}
free (bbs);
loop->num_exits = num_exits;
}
static int
flow_loop_nodes_find (basic_block header, struct loop *loop)
{
basic_block *stack;
int sp;
int num_nodes = 1;
header->loop_father = loop;
header->loop_depth = loop->depth;
if (loop->latch->loop_father != loop)
{
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;
while (sp)
{
basic_block node;
edge e;
edge_iterator ei;
node = stack[--sp];
FOR_EACH_EDGE (e, ei, node->preds)
{
basic_block ancestor = e->src;
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_nodes;
}
void
mark_single_exit_loops (struct loops *loops)
{
basic_block bb;
edge e;
struct loop *loop;
unsigned i;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (loop)
loop->single_exit = NULL;
}
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)
{
if (loop->single_exit)
loop->single_exit = EDGE_SUCC (ENTRY_BLOCK_PTR, 0);
else
loop->single_exit = e;
}
}
}
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (!loop)
continue;
if (loop->single_exit == EDGE_SUCC (ENTRY_BLOCK_PTR, 0))
loop->single_exit = NULL;
}
loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
}
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;
for (num = 1;
EDGE_PRED (ebb, 0)->src != ENTRY_BLOCK_PTR && EDGE_COUNT (ebb->preds) == 1;
num++)
ebb = EDGE_PRED (ebb, 0)->src;
loop->pre_header_edges = xmalloc (num * sizeof (edge));
loop->num_pre_header_edges = num;
for (e = loop->entry_edges[0]; num; e = EDGE_PRED (e->src, 0))
loop->pre_header_edges[--num] = e;
}
static basic_block
flow_loop_pre_header_find (basic_block header)
{
basic_block pre_header;
edge e;
edge_iterator ei;
pre_header = NULL;
FOR_EACH_EDGE (e, ei, header->preds)
{
basic_block node = e->src;
if (node != ENTRY_BLOCK_PTR
&& ! dominated_by_p (CDI_DOMINATORS, node, header))
{
if (pre_header == NULL)
pre_header = node;
else
{
pre_header = NULL;
break;
}
}
}
return pre_header;
}
static void
establish_preds (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);
}
void
flow_loop_tree_node_add (struct loop *father, struct loop *loop)
{
loop->next = father->inner;
father->inner = loop;
loop->outer = father;
establish_preds (loop);
}
void
flow_loop_tree_node_remove (struct loop *loop)
{
struct loop *prev, *father;
father = loop->outer;
loop->outer = NULL;
if (father->inner == loop)
father->inner = loop->next;
else
{
for (prev = father->inner; prev->next != loop; prev = prev->next);
prev->next = loop->next;
}
loop->depth = -1;
free (loop->pred);
loop->pred = NULL;
}
static int
flow_loop_level_compute (struct loop *loop)
{
struct loop *inner;
int level = 1;
if (! loop)
return 0;
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;
}
static int
flow_loops_level_compute (struct loops *loops)
{
return flow_loop_level_compute (loops->tree_root);
}
int
flow_loop_scan (struct loop *loop, int flags)
{
if (flags & LOOP_ENTRY_EDGES)
{
flow_loop_entry_edges_find (loop);
}
if (flags & LOOP_EXIT_EDGES)
{
flow_loop_exit_edges_find (loop);
}
if (flags & LOOP_PRE_HEADER)
{
loop->pre_header = flow_loop_pre_header_find (loop->header);
flow_loop_pre_header_scan (loop);
}
return 1;
}
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);
}
static edge mfb_kj_edge;
static bool
mfb_keep_just (edge e)
{
return e != mfb_kj_edge;
}
static bool
mfb_keep_nonlatch (edge e)
{
return LATCH_EDGE (e);
}
static void
canonicalize_loop_headers (void)
{
basic_block header;
edge e;
alloc_aux_for_blocks (sizeof (int));
alloc_aux_for_edges (sizeof (int));
FOR_EACH_BB (header)
{
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 (HEADER_BLOCK (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest))
{
basic_block bb;
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;
}
FOR_EACH_BB (header)
{
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_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)
{
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)
{
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;
}
}
free_aux_for_blocks ();
free_aux_for_edges ();
#ifdef ENABLE_CHECKING
verify_dominators (CDI_DOMINATORS);
#endif
}
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;
}
}
int
flow_loops_find (struct loops *loops, int flags)
{
int i;
int b;
int num_loops;
edge e;
sbitmap headers;
int *dfs_order;
int *rc_order;
basic_block header;
basic_block bb;
gcc_assert (flags & LOOP_TREE);
memset (loops, 0, sizeof *loops);
if (n_basic_blocks == 0)
return 0;
dfs_order = NULL;
rc_order = NULL;
calculate_dominance_info (CDI_DOMINATORS);
canonicalize_loop_headers ();
headers = sbitmap_alloc (last_basic_block);
sbitmap_zero (headers);
num_loops = 0;
FOR_EACH_BB (header)
{
edge_iterator ei;
int more_latches = 0;
header->loop_depth = 0;
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));
if (latch != ENTRY_BLOCK_PTR
&& dominated_by_p (CDI_DOMINATORS, latch, header))
{
gcc_assert (!more_latches);
more_latches = 1;
SET_BIT (headers, header->index);
num_loops++;
}
}
}
loops->parray = xcalloc (num_loops + 1, sizeof (struct loop *));
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];
loops->num = 1;
FOR_EACH_BB (bb)
bb->loop_father = loops->tree_root;
if (num_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);
loops->cfg.dfs_order = dfs_order;
loops->cfg.rc_order = rc_order;
num_loops = 1;
for (b = 0; b < n_basic_blocks; b++)
{
struct loop *loop;
edge_iterator ei;
if (!TEST_BIT (headers, rc_order[b]))
continue;
header = BASIC_BLOCK (rc_order[b]);
loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
loop->header = header;
loop->num = num_loops;
num_loops++;
FOR_EACH_EDGE (e, ei, header->preds)
{
basic_block latch = e->src;
if (latch != ENTRY_BLOCK_PTR
&& dominated_by_p (CDI_DOMINATORS, latch, header))
{
loop->latch = latch;
break;
}
}
flow_loop_tree_node_add (header->loop_father, loop);
loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
}
loops->levels = flow_loops_level_compute (loops);
for (i = 1; i < num_loops; i++)
flow_loop_scan (loops->parray[i], flags);
loops->num = num_loops;
initialize_loops_parallel_p (loops);
}
else
{
free_dominance_info (CDI_DOMINATORS);
}
sbitmap_free (headers);
loops->state = 0;
#ifdef ENABLE_CHECKING
verify_flow_info ();
verify_loop_structure (loops);
#endif
return loops->num;
}
int
flow_loops_update (struct loops *loops, int flags)
{
if (loops->parray)
flow_loops_free (loops);
return flow_loops_find (loops, flags);
}
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);
}
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);
}
static bool
glb_enum_p (basic_block bb, void *glb_header)
{
return bb != (basic_block) glb_header;
}
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)
{
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;
}
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))
{
postpone = son;
continue;
}
fill_sons_in_loop (loop, son, tovisit, tv);
}
if (postpone)
fill_sons_in_loop (loop, postpone, tovisit, tv);
}
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;
}
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;
gcc_assert (loop->num_nodes);
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
visited = BITMAP_XMALLOC ();
bb = loop->header;
while (i < loop->num_nodes)
{
edge e;
edge_iterator ei;
if (!bitmap_bit_p (visited, bb->index))
{
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_XFREE (visited);
return blocks;
}
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;
}
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;
}
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++;
}
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;
}
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)
{
loop_s = loop_s->outer;
loop_d = loop_d->outer;
}
return loop_s;
}
void
cancel_loop (struct loops *loops, struct loop *loop)
{
basic_block *bbs;
unsigned i;
gcc_assert (!loop->inner);
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
bbs[i]->loop_father = loop->outer;
flow_loop_tree_node_remove (loop);
loops->parray[loop->num] = NULL;
flow_loop_free (loop);
}
void
cancel_loop_tree (struct loops *loops, struct loop *loop)
{
while (loop->inner)
cancel_loop_tree (loops, loop->inner);
cancel_loop (loops, loop);
}
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;
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;
}
}
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);
}
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;
}
}
if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
{
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;
}
mark_irreducible_loops (loops);
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);
}
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);
}
edge
loop_latch_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;
}
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;
}