#include "config.h"
#include "system.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "insn-config.h"
#include "recog.h"
#include "toplev.h"
#include "obstack.h"
#include "tm_p.h"
struct depth_first_search_dsS {
basic_block *stack;
unsigned int sp;
sbitmap visited_blocks;
};
typedef struct depth_first_search_dsS *depth_first_search_ds;
static void flow_dfs_compute_reverse_init
PARAMS ((depth_first_search_ds));
static void flow_dfs_compute_reverse_add_bb
PARAMS ((depth_first_search_ds, basic_block));
static basic_block flow_dfs_compute_reverse_execute
PARAMS ((depth_first_search_ds));
static void flow_dfs_compute_reverse_finish
PARAMS ((depth_first_search_ds));
static void remove_fake_successors PARAMS ((basic_block));
static bool need_fake_edge_p PARAMS ((rtx));
static bool keep_with_call_p PARAMS ((rtx));
bool
forwarder_block_p (bb)
basic_block bb;
{
rtx insn;
if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
|| !bb->succ || bb->succ->succ_next)
return false;
for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
if (INSN_P (insn) && active_insn_p (insn))
return false;
return (!INSN_P (insn)
|| (GET_CODE (insn) == JUMP_INSN && simplejump_p (insn))
|| !active_insn_p (insn));
}
bool
can_fallthru (src, target)
basic_block src, target;
{
rtx insn = src->end;
rtx insn2 = target->head;
if (src->index + 1 == target->index && !active_insn_p (insn2))
insn2 = next_active_insn (insn2);
return next_active_insn (insn) == insn2;
}
bool
mark_dfs_back_edges ()
{
edge *stack;
int *pre;
int *post;
int sp;
int prenum = 1;
int postnum = 1;
sbitmap visited;
bool found = false;
pre = (int *) xcalloc (n_basic_blocks, sizeof (int));
post = (int *) xcalloc (n_basic_blocks, sizeof (int));
stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
visited = sbitmap_alloc (n_basic_blocks);
sbitmap_zero (visited);
stack[sp++] = ENTRY_BLOCK_PTR->succ;
while (sp)
{
edge e;
basic_block src;
basic_block dest;
e = stack[sp - 1];
src = e->src;
dest = e->dest;
e->flags &= ~EDGE_DFS_BACK;
if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
SET_BIT (visited, dest->index);
pre[dest->index] = prenum++;
if (dest->succ)
{
stack[sp++] = dest->succ;
}
else
post[dest->index] = postnum++;
}
else
{
if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
&& pre[src->index] >= pre[dest->index]
&& post[dest->index] == 0)
e->flags |= EDGE_DFS_BACK, found = true;
if (! e->succ_next && src != ENTRY_BLOCK_PTR)
post[src->index] = postnum++;
if (e->succ_next)
stack[sp - 1] = e->succ_next;
else
sp--;
}
}
free (pre);
free (post);
free (stack);
sbitmap_free (visited);
return found;
}
static bool
need_fake_edge_p (insn)
rtx insn;
{
if (!INSN_P (insn))
return false;
if ((GET_CODE (insn) == CALL_INSN
&& !SIBLING_CALL_P (insn)
&& !find_reg_note (insn, REG_NORETURN, NULL)
&& !find_reg_note (insn, REG_ALWAYS_RETURN, NULL)
&& !CONST_OR_PURE_CALL_P (insn)))
return true;
return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
&& MEM_VOLATILE_P (PATTERN (insn)))
|| (GET_CODE (PATTERN (insn)) == PARALLEL
&& asm_noperands (insn) != -1
&& MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
|| GET_CODE (PATTERN (insn)) == ASM_INPUT);
}
static bool
keep_with_call_p (insn)
rtx insn;
{
rtx set;
if (INSN_P (insn) && (set = single_set (insn)) != NULL)
{
if (GET_CODE (SET_DEST (set)) == REG
&& fixed_regs[REGNO (SET_DEST (set))]
&& general_operand (SET_SRC (set), VOIDmode))
return true;
if (GET_CODE (SET_SRC (set)) == REG
&& FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
return true;
}
return false;
}
int
flow_call_edges_add (blocks)
sbitmap blocks;
{
int i;
int blocks_split = 0;
int bb_num = 0;
basic_block *bbs;
bool check_last_block = false;
bbs = xmalloc (n_basic_blocks * sizeof (*bbs));
if (! blocks)
{
for (i = 0; i < n_basic_blocks; i++)
bbs[bb_num++] = BASIC_BLOCK (i);
check_last_block = true;
}
else
EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
{
bbs[bb_num++] = BASIC_BLOCK (i);
if (i == n_basic_blocks - 1)
check_last_block = true;
});
if (check_last_block)
{
basic_block bb = BASIC_BLOCK (n_basic_blocks - 1);
rtx insn = bb->end;
while (insn != bb->head
&& keep_with_call_p (insn))
insn = PREV_INSN (insn);
if (need_fake_edge_p (insn))
{
edge e;
for (e = bb->succ; e; e = e->succ_next)
if (e->dest == EXIT_BLOCK_PTR)
break;
insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
commit_edge_insertions ();
}
}
for (i = 0; i < bb_num; i++)
{
basic_block bb = bbs[i];
rtx insn;
rtx prev_insn;
for (insn = bb->end; ; insn = prev_insn)
{
prev_insn = PREV_INSN (insn);
if (need_fake_edge_p (insn))
{
edge e;
rtx split_at_insn = insn;
if (GET_CODE (insn) == CALL_INSN)
while (split_at_insn != bb->end
&& keep_with_call_p (NEXT_INSN (split_at_insn)))
split_at_insn = NEXT_INSN (split_at_insn);
#ifdef ENABLE_CHECKING
if (split_at_insn == bb->end)
for (e = bb->succ; e; e = e->succ_next)
if (e->dest == EXIT_BLOCK_PTR)
abort ();
#endif
e = split_block (bb, split_at_insn);
if (e)
blocks_split++;
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
if (insn == bb->head)
break;
}
}
if (blocks_split)
verify_flow_info ();
free (bbs);
return blocks_split;
}
void
find_unreachable_blocks ()
{
edge e;
int i, n;
basic_block *tos, *worklist;
n = n_basic_blocks;
tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
for (i = 0; i < n; ++i)
BASIC_BLOCK (i)->flags &= ~BB_REACHABLE;
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
{
*tos++ = e->dest;
e->dest->flags |= BB_REACHABLE;
}
while (tos != worklist)
{
basic_block b = *--tos;
for (e = b->succ; e; e = e->succ_next)
if (!(e->dest->flags & BB_REACHABLE))
{
*tos++ = e->dest;
e->dest->flags |= BB_REACHABLE;
}
}
free (worklist);
}
struct edge_list *
create_edge_list ()
{
struct edge_list *elist;
edge e;
int num_edges;
int x;
int block_count;
block_count = n_basic_blocks + 2;
num_edges = 0;
for (x = 0; x < n_basic_blocks; x++)
{
basic_block bb = BASIC_BLOCK (x);
for (e = bb->succ; e; e = e->succ_next)
num_edges++;
}
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
num_edges++;
elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
elist->num_blocks = block_count;
elist->num_edges = num_edges;
elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
num_edges = 0;
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
elist->index_to_edge[num_edges++] = e;
for (x = 0; x < n_basic_blocks; x++)
{
basic_block bb = BASIC_BLOCK (x);
for (e = bb->succ; e; e = e->succ_next)
elist->index_to_edge[num_edges++] = e;
}
return elist;
}
void
free_edge_list (elist)
struct edge_list *elist;
{
if (elist)
{
free (elist->index_to_edge);
free (elist);
}
}
void
print_edge_list (f, elist)
FILE *f;
struct edge_list *elist;
{
int x;
fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
elist->num_blocks - 2, elist->num_edges);
for (x = 0; x < elist->num_edges; x++)
{
fprintf (f, " %-4d - edge(", x);
if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
fprintf (f, "entry,");
else
fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
fprintf (f, "exit)\n");
else
fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
}
}
void
verify_edge_list (f, elist)
FILE *f;
struct edge_list *elist;
{
int x, pred, succ, index;
edge e;
for (x = 0; x < n_basic_blocks; x++)
{
basic_block bb = BASIC_BLOCK (x);
for (e = bb->succ; e; e = e->succ_next)
{
pred = e->src->index;
succ = e->dest->index;
index = EDGE_INDEX (elist, e->src, e->dest);
if (index == EDGE_INDEX_NO_EDGE)
{
fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
continue;
}
if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
fprintf (f, "*p* Pred for index %d should be %d not %d\n",
index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
fprintf (f, "*p* Succ for index %d should be %d not %d\n",
index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
}
}
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
{
pred = e->src->index;
succ = e->dest->index;
index = EDGE_INDEX (elist, e->src, e->dest);
if (index == EDGE_INDEX_NO_EDGE)
{
fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
continue;
}
if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
fprintf (f, "*p* Pred for index %d should be %d not %d\n",
index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
fprintf (f, "*p* Succ for index %d should be %d not %d\n",
index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
}
for (pred = 0; pred < n_basic_blocks; pred++)
for (succ = 0; succ < n_basic_blocks; succ++)
{
basic_block p = BASIC_BLOCK (pred);
basic_block s = BASIC_BLOCK (succ);
int found_edge = 0;
for (e = p->succ; e; e = e->succ_next)
if (e->dest == s)
{
found_edge = 1;
break;
}
for (e = s->pred; e; e = e->pred_next)
if (e->src == p)
{
found_edge = 1;
break;
}
if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
== EDGE_INDEX_NO_EDGE && found_edge != 0)
fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
pred, succ);
if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
!= EDGE_INDEX_NO_EDGE && found_edge == 0)
fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred),
BASIC_BLOCK (succ)));
}
for (succ = 0; succ < n_basic_blocks; succ++)
{
basic_block p = ENTRY_BLOCK_PTR;
basic_block s = BASIC_BLOCK (succ);
int found_edge = 0;
for (e = p->succ; e; e = e->succ_next)
if (e->dest == s)
{
found_edge = 1;
break;
}
for (e = s->pred; e; e = e->pred_next)
if (e->src == p)
{
found_edge = 1;
break;
}
if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
== EDGE_INDEX_NO_EDGE && found_edge != 0)
fprintf (f, "*** Edge (entry, %d) appears to not have an index\n",
succ);
if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
!= EDGE_INDEX_NO_EDGE && found_edge == 0)
fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n",
succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR,
BASIC_BLOCK (succ)));
}
for (pred = 0; pred < n_basic_blocks; pred++)
{
basic_block p = BASIC_BLOCK (pred);
basic_block s = EXIT_BLOCK_PTR;
int found_edge = 0;
for (e = p->succ; e; e = e->succ_next)
if (e->dest == s)
{
found_edge = 1;
break;
}
for (e = s->pred; e; e = e->pred_next)
if (e->src == p)
{
found_edge = 1;
break;
}
if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
== EDGE_INDEX_NO_EDGE && found_edge != 0)
fprintf (f, "*** Edge (%d, exit) appears to not have an index\n",
pred);
if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
!= EDGE_INDEX_NO_EDGE && found_edge == 0)
fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n",
pred, EDGE_INDEX (elist, BASIC_BLOCK (pred),
EXIT_BLOCK_PTR));
}
}
int
find_edge_index (edge_list, pred, succ)
struct edge_list *edge_list;
basic_block pred, succ;
{
int x;
for (x = 0; x < NUM_EDGES (edge_list); x++)
if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
&& INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
return x;
return (EDGE_INDEX_NO_EDGE);
}
void
flow_nodes_print (str, nodes, file)
const char *str;
const sbitmap nodes;
FILE *file;
{
int node;
if (! nodes)
return;
fprintf (file, "%s { ", str);
EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
fputs ("}\n", file);
}
void
flow_edge_list_print (str, edge_list, num_edges, file)
const char *str;
const edge *edge_list;
int num_edges;
FILE *file;
{
int i;
if (! edge_list)
return;
fprintf (file, "%s { ", str);
for (i = 0; i < num_edges; i++)
fprintf (file, "%d->%d ", edge_list[i]->src->index,
edge_list[i]->dest->index);
fputs ("}\n", file);
}
static void
remove_fake_successors (bb)
basic_block bb;
{
edge e;
for (e = bb->succ; e;)
{
edge tmp = e;
e = e->succ_next;
if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
remove_edge (tmp);
}
}
void
remove_fake_edges ()
{
int x;
for (x = 0; x < n_basic_blocks; x++)
remove_fake_successors (BASIC_BLOCK (x));
remove_fake_successors (ENTRY_BLOCK_PTR);
}
void
add_noreturn_fake_exit_edges ()
{
int x;
for (x = 0; x < n_basic_blocks; x++)
if (BASIC_BLOCK (x)->succ == NULL)
make_single_succ_edge (BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
}
void
connect_infinite_loops_to_exit ()
{
basic_block unvisited_block;
struct depth_first_search_dsS dfs_ds;
flow_dfs_compute_reverse_init (&dfs_ds);
flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
while (1)
{
unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
if (!unvisited_block)
break;
make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
}
flow_dfs_compute_reverse_finish (&dfs_ds);
return;
}
void
flow_reverse_top_sort_order_compute (rts_order)
int *rts_order;
{
edge *stack;
int sp;
int postnum = 0;
sbitmap visited;
stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
visited = sbitmap_alloc (n_basic_blocks);
sbitmap_zero (visited);
stack[sp++] = ENTRY_BLOCK_PTR->succ;
while (sp)
{
edge e;
basic_block src;
basic_block dest;
e = stack[sp - 1];
src = e->src;
dest = e->dest;
if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
SET_BIT (visited, dest->index);
if (dest->succ)
stack[sp++] = dest->succ;
else
rts_order[postnum++] = dest->index;
}
else
{
if (! e->succ_next && src != ENTRY_BLOCK_PTR)
rts_order[postnum++] = src->index;
if (e->succ_next)
stack[sp - 1] = e->succ_next;
else
sp--;
}
}
free (stack);
sbitmap_free (visited);
}
int
flow_depth_first_order_compute (dfs_order, rc_order)
int *dfs_order;
int *rc_order;
{
edge *stack;
int sp;
int dfsnum = 0;
int rcnum = n_basic_blocks - 1;
sbitmap visited;
stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
visited = sbitmap_alloc (n_basic_blocks);
sbitmap_zero (visited);
stack[sp++] = ENTRY_BLOCK_PTR->succ;
while (sp)
{
edge e;
basic_block src;
basic_block dest;
e = stack[sp - 1];
src = e->src;
dest = e->dest;
if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
SET_BIT (visited, dest->index);
if (dfs_order)
dfs_order[dfsnum] = dest->index;
dfsnum++;
if (dest->succ)
stack[sp++] = dest->succ;
else if (rc_order)
rc_order[rcnum--] = dest->index;
}
else
{
if (! e->succ_next && src != ENTRY_BLOCK_PTR
&& rc_order)
rc_order[rcnum--] = src->index;
if (e->succ_next)
stack[sp - 1] = e->succ_next;
else
sp--;
}
}
free (stack);
sbitmap_free (visited);
if (dfsnum > n_basic_blocks)
abort ();
if (dfsnum < n_basic_blocks)
abort ();
return dfsnum;
}
struct dfst_node
{
unsigned nnodes;
struct dfst_node **node;
struct dfst_node *up;
};
void
flow_preorder_transversal_compute (pot_order)
int *pot_order;
{
edge e;
edge *stack;
int i;
int max_successors;
int sp;
sbitmap visited;
struct dfst_node *node;
struct dfst_node *dfst;
stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
dfst = (struct dfst_node *) xcalloc (n_basic_blocks,
sizeof (struct dfst_node));
for (i = 0; i < n_basic_blocks; i++)
{
max_successors = 0;
for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
max_successors++;
dfst[i].node
= (max_successors
? (struct dfst_node **) xcalloc (max_successors,
sizeof (struct dfst_node *))
: NULL);
}
visited = sbitmap_alloc (n_basic_blocks);
sbitmap_zero (visited);
stack[sp++] = ENTRY_BLOCK_PTR->succ;
while (sp)
{
basic_block src;
basic_block dest;
e = stack[sp - 1];
src = e->src;
dest = e->dest;
if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
SET_BIT (visited, dest->index);
if (src != ENTRY_BLOCK_PTR)
{
dfst[src->index].node[dfst[src->index].nnodes++]
= &dfst[dest->index];
dfst[dest->index].up = &dfst[src->index];
}
if (dest->succ)
stack[sp++] = dest->succ;
}
else if (e->succ_next)
stack[sp - 1] = e->succ_next;
else
sp--;
}
free (stack);
sbitmap_free (visited);
i = 0;
node = &dfst[0];
pot_order[i++] = 0;
while (node)
{
if (node->nnodes)
{
node = node->node[--node->nnodes];
pot_order[i++] = node - dfst;
}
else
node = node->up;
}
for (i = 0; i < n_basic_blocks; i++)
if (dfst[i].node)
free (dfst[i].node);
free (dfst);
}
static void
flow_dfs_compute_reverse_init (data)
depth_first_search_ds data;
{
data->stack = (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
* sizeof (basic_block));
data->sp = 0;
data->visited_blocks = sbitmap_alloc (n_basic_blocks - (INVALID_BLOCK + 1));
sbitmap_zero (data->visited_blocks);
return;
}
static void
flow_dfs_compute_reverse_add_bb (data, bb)
depth_first_search_ds data;
basic_block bb;
{
data->stack[data->sp++] = bb;
SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
}
static basic_block
flow_dfs_compute_reverse_execute (data)
depth_first_search_ds data;
{
basic_block bb;
edge e;
int i;
while (data->sp > 0)
{
bb = data->stack[--data->sp];
for (e = bb->pred; e; e = e->pred_next)
if (!TEST_BIT (data->visited_blocks,
e->src->index - (INVALID_BLOCK + 1)))
flow_dfs_compute_reverse_add_bb (data, e->src);
}
for (i = n_basic_blocks - (INVALID_BLOCK + 1); --i >= 0; )
if (!TEST_BIT (data->visited_blocks, i))
return BASIC_BLOCK (i + (INVALID_BLOCK + 1));
return NULL;
}
static void
flow_dfs_compute_reverse_finish (data)
depth_first_search_ds data;
{
free (data->stack);
sbitmap_free (data->visited_blocks);
}