#include "config.h"
#include "system.h"
#include "rtl.h"
#include "hard-reg-set.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 *));
static void
flow_loops_cfg_dump (loops, file)
const struct loops *loops;
FILE *file;
{
int i;
if (! loops->num || ! file || ! loops->cfg.dom)
return;
for (i = 0; i < n_basic_blocks; i++)
{
edge succ;
fprintf (file, ";; %d succs { ", i);
for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
fprintf (file, "%d ", succ->dest->index);
flow_nodes_print ("} dom", loops->cfg.dom[i], file);
}
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);
}
}
static int
flow_loop_nested_p (outer, loop)
struct loop *outer;
struct loop *loop;
{
return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
}
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;
{
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" : "", 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, ";; 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);
if (loop_dump_aux)
loop_dump_aux (loop, file, verbose);
}
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;
{
int i, j;
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->array[i];
flow_loop_dump (loop, file, loop_dump_aux, verbose);
if (loop->shared)
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;
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");
}
}
}
if (verbose)
flow_loops_cfg_dump (loops, file);
}
void
flow_loops_free (loops)
struct loops *loops;
{
if (loops->array)
{
int i;
if (! loops->num)
abort ();
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);
}
free (loops->array);
loops->array = NULL;
if (loops->cfg.dom)
sbitmap_vector_free (loops->cfg.dom);
if (loops->cfg.dfs_order)
free (loops->cfg.dfs_order);
if (loops->shared_headers)
sbitmap_free (loops->shared_headers);
}
}
static int
flow_loop_entry_edges_find (header, nodes, entry_edges)
basic_block header;
const sbitmap nodes;
edge **entry_edges;
{
edge e;
int num_entries;
*entry_edges = NULL;
num_entries = 0;
for (e = header->pred; e; e = e->pred_next)
{
basic_block src = e->src;
if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
num_entries++;
}
if (! num_entries)
abort ();
*entry_edges = (edge *) xmalloc (num_entries * sizeof (edge));
num_entries = 0;
for (e = header->pred; e; e = e->pred_next)
{
basic_block src = e->src;
if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
(*entry_edges)[num_entries++] = e;
}
return num_entries;
}
static int
flow_loop_exit_edges_find (nodes, exit_edges)
const sbitmap nodes;
edge **exit_edges;
{
edge e;
int node;
int num_exits;
*exit_edges = NULL;
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));
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;
}
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;
sbitmap_zero (nodes);
SET_BIT (nodes, header->index);
num_nodes++;
header->loop_depth++;
if (! TEST_BIT (nodes, latch->index))
{
SET_BIT (nodes, latch->index);
latch->loop_depth++;
num_nodes++;
stack[sp++] = latch;
}
while (sp)
{
basic_block node;
edge e;
node = stack[--sp];
for (e = node->pred; e; e = e->pred_next)
{
basic_block ancestor = e->src;
if (ancestor != ENTRY_BLOCK_PTR
&& ! TEST_BIT (nodes, ancestor->index))
{
SET_BIT (nodes, ancestor->index);
ancestor->loop_depth++;
num_nodes++;
stack[sp++] = ancestor;
}
}
}
free (stack);
return num_nodes;
}
static void
flow_loop_pre_header_scan (loop)
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; ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next;
num++)
ebb = ebb->pred->src;
loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge));
loop->num_pre_header_edges = num;
for (e = loop->entry_edges[0]; num; e = e->src->pred)
loop->pre_header_edges[--num] = e;
}
static basic_block
flow_loop_pre_header_find (header, dom)
basic_block header;
const sbitmap *dom;
{
basic_block pre_header;
edge e;
pre_header = NULL;
for (e = header->pred; e; e = e->pred_next)
{
basic_block node = e->src;
if (node != ENTRY_BLOCK_PTR
&& ! TEST_BIT (dom[node->index], header->index))
{
if (pre_header == NULL)
pre_header = node;
else
{
pre_header = NULL;
break;
}
}
}
return pre_header;
}
static void
flow_loop_tree_node_add (prevloop, loop)
struct loop *prevloop;
struct loop *loop;
{
if (flow_loop_nested_p (prevloop, loop))
{
prevloop->inner = loop;
loop->outer = prevloop;
return;
}
for (; prevloop->outer; prevloop = prevloop->outer)
if (flow_loop_nested_p (prevloop->outer, loop))
{
prevloop->next = loop;
loop->outer = prevloop->outer;
return;
}
prevloop->next = loop;
loop->outer = NULL;
}
static void
flow_loops_tree_build (loops)
struct loops *loops;
{
int i;
int num_loops;
num_loops = loops->num;
if (! num_loops)
return;
loops->tree_root = &loops->array[0];
loops->tree_root->outer = loops->tree_root->inner
= loops->tree_root->next = NULL;
for (i = 1; i < num_loops; i++)
flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
}
static int
flow_loop_level_compute (loop, depth)
struct loop *loop;
int depth;
{
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, depth + 1) + 1;
level = MAX (ilevel, level);
}
loop->level = level;
loop->depth = depth;
return level;
}
static int
flow_loops_level_compute (loops)
struct loops *loops;
{
int levels = 0;
struct loop *loop;
int level;
for (loop = loops->tree_root; loop; loop = loop->next)
{
level = flow_loop_level_compute (loop, 1);
levels = MAX (levels, level);
}
return levels;
}
int
flow_loop_scan (loops, loop, flags)
struct loops *loops;
struct loop *loop;
int flags;
{
if ((flags & LOOP_EXITS_DOMS) && ! loop->exit_edges)
flags |= LOOP_EXIT_EDGES;
if (flags & LOOP_ENTRY_EDGES)
loop->num_entries = flow_loop_entry_edges_find (loop->header, loop->nodes,
&loop->entry_edges);
if (flags & LOOP_EXIT_EDGES)
loop->num_exits
= flow_loop_exit_edges_find (loop->nodes, &loop->exit_edges);
if (flags & LOOP_EXITS_DOMS)
{
int j;
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]);
if (! TEST_BIT (loop->exits_doms, loop->header->index))
abort ();
}
if (flags & LOOP_PRE_HEADER)
{
loop->pre_header
= flow_loop_pre_header_find (loop->header, loops->cfg.dom);
flow_loop_pre_header_scan (loop);
}
return 1;
}
int
flow_loops_find (loops, flags)
struct loops *loops;
int flags;
{
int i;
int b;
int num_loops;
edge e;
sbitmap headers;
sbitmap *dom;
int *dfs_order;
int *rc_order;
if (! (flags & LOOP_TREE))
abort ();
memset (loops, 0, sizeof *loops);
if (n_basic_blocks == 0)
return 0;
dfs_order = NULL;
rc_order = NULL;
dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
num_loops = 0;
for (b = 0; b < n_basic_blocks; b++)
{
basic_block header;
header = BASIC_BLOCK (b);
header->loop_depth = 0;
for (e = header->pred; e; e = e->pred_next)
{
basic_block latch = e->src;
if (b != header->index)
abort ();
if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
num_loops++;
}
}
if (num_loops)
{
dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
flow_depth_first_order_compute (dfs_order, rc_order);
loops->cfg.dom = dom;
loops->cfg.dfs_order = dfs_order;
loops->cfg.rc_order = rc_order;
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 = 0;
for (b = n_basic_blocks - 1; b >= 0; b--)
{
basic_block latch;
latch = BASIC_BLOCK (rc_order[b]);
for (e = latch->succ; e; e = e->succ_next)
{
basic_block header = e->dest;
if (header != EXIT_BLOCK_PTR
&& TEST_BIT (dom[latch->index], header->index))
{
struct loop *loop;
loop = loops->array + num_loops;
loop->header = header;
loop->latch = latch;
loop->num = num_loops;
num_loops++;
}
}
}
for (i = 0; i < num_loops; i++)
{
struct loop *loop = &loops->array[i];
if (TEST_BIT (headers, loop->header->index))
SET_BIT (loops->shared_headers, loop->header->index);
SET_BIT (headers, loop->header->index);
loop->nodes = sbitmap_alloc (n_basic_blocks);
loop->num_nodes
= flow_loop_nodes_find (loop->header, loop->latch, loop->nodes);
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);
}
for (i = 0; i < num_loops; i++)
if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
loops->array[i].shared = 1;
sbitmap_free (headers);
}
else
sbitmap_vector_free (dom);
loops->num = num_loops;
flow_loops_tree_build (loops);
loops->levels = flow_loops_level_compute (loops);
return num_loops;
}
int
flow_loops_update (loops, flags)
struct loops *loops;
int flags;
{
if (loops->array)
flow_loops_free (loops);
return flow_loops_find (loops, flags);
}
int
flow_loop_outside_edge_p (loop, e)
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);
}