#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "obstack.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "insn-config.h"
#include "recog.h"
#include "toplev.h"
#include "tm_p.h"
#include "timevar.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 (depth_first_search_ds);
static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
basic_block);
static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
basic_block);
static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
static bool flow_active_insn_p (rtx);
static bool
flow_active_insn_p (rtx insn)
{
if (active_insn_p (insn))
return true;
if (GET_CODE (PATTERN (insn)) == CLOBBER
&& REG_P (XEXP (PATTERN (insn), 0))
&& REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
return true;
return false;
}
bool
forwarder_block_p (basic_block bb)
{
rtx insn;
if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
|| EDGE_COUNT (bb->succs) != 1)
return false;
for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
if (INSN_P (insn) && flow_active_insn_p (insn))
return false;
return (!INSN_P (insn)
|| (JUMP_P (insn) && simplejump_p (insn))
|| !flow_active_insn_p (insn));
}
bool
can_fallthru (basic_block src, basic_block target)
{
rtx insn = BB_END (src);
rtx insn2;
edge e;
edge_iterator ei;
if (target == EXIT_BLOCK_PTR)
return true;
if (src->next_bb != target)
return 0;
FOR_EACH_EDGE (e, ei, src->succs)
if (e->dest == EXIT_BLOCK_PTR
&& e->flags & EDGE_FALLTHRU)
return 0;
insn2 = BB_HEAD (target);
if (insn2 && !active_insn_p (insn2))
insn2 = next_active_insn (insn2);
return next_active_insn (insn) == insn2;
}
bool
could_fall_through (basic_block src, basic_block target)
{
edge e;
edge_iterator ei;
if (target == EXIT_BLOCK_PTR)
return true;
FOR_EACH_EDGE (e, ei, src->succs)
if (e->dest == EXIT_BLOCK_PTR
&& e->flags & EDGE_FALLTHRU)
return 0;
return true;
}
bool
mark_dfs_back_edges (void)
{
edge_iterator *stack;
int *pre;
int *post;
int sp;
int prenum = 1;
int postnum = 1;
sbitmap visited;
bool found = false;
pre = xcalloc (last_basic_block, sizeof (int));
post = xcalloc (last_basic_block, sizeof (int));
stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
sp = 0;
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (visited);
stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
while (sp)
{
edge_iterator ei;
basic_block src;
basic_block dest;
ei = stack[sp - 1];
src = ei_edge (ei)->src;
dest = ei_edge (ei)->dest;
ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
SET_BIT (visited, dest->index);
pre[dest->index] = prenum++;
if (EDGE_COUNT (dest->succs) > 0)
{
stack[sp++] = ei_start (dest->succs);
}
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)
ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
post[src->index] = postnum++;
if (!ei_one_before_end_p (ei))
ei_next (&stack[sp - 1]);
else
sp--;
}
}
free (pre);
free (post);
free (stack);
sbitmap_free (visited);
return found;
}
void
set_edge_can_fallthru_flag (void)
{
basic_block bb;
FOR_EACH_BB (bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
e->flags &= ~EDGE_CAN_FALLTHRU;
if (e->flags & EDGE_FALLTHRU)
e->flags |= EDGE_CAN_FALLTHRU;
}
if (EDGE_COUNT (bb->succs) != 2)
continue;
if (!any_condjump_p (BB_END (bb)))
continue;
if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
continue;
invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
}
}
void
find_unreachable_blocks (void)
{
edge e;
edge_iterator ei;
basic_block *tos, *worklist, bb;
tos = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
FOR_EACH_BB (bb)
bb->flags &= ~BB_REACHABLE;
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
{
*tos++ = e->dest;
e->dest->flags |= BB_REACHABLE;
}
while (tos != worklist)
{
basic_block b = *--tos;
FOR_EACH_EDGE (e, ei, b->succs)
{
basic_block dest = e->dest;
if (!(dest->flags & BB_REACHABLE))
{
*tos++ = dest;
dest->flags |= BB_REACHABLE;
}
}
}
free (worklist);
}
struct edge_list *
create_edge_list (void)
{
struct edge_list *elist;
edge e;
int num_edges;
int block_count;
basic_block bb;
edge_iterator ei;
block_count = n_basic_blocks + 2;
num_edges = 0;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
num_edges += EDGE_COUNT (bb->succs);
}
elist = xmalloc (sizeof (struct edge_list));
elist->num_blocks = block_count;
elist->num_edges = num_edges;
elist->index_to_edge = xmalloc (sizeof (edge) * num_edges);
num_edges = 0;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
FOR_EACH_EDGE (e, ei, bb->succs)
elist->index_to_edge[num_edges++] = e;
return elist;
}
void
free_edge_list (struct edge_list *elist)
{
if (elist)
{
free (elist->index_to_edge);
free (elist);
}
}
void
print_edge_list (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 (FILE *f, struct edge_list *elist)
{
int pred, succ, index;
edge e;
basic_block bb, p, s;
edge_iterator ei;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
FOR_EACH_EDGE (e, ei, bb->succs)
{
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_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
{
int found_edge = 0;
FOR_EACH_EDGE (e, ei, p->succs)
if (e->dest == s)
{
found_edge = 1;
break;
}
FOR_EACH_EDGE (e, ei, s->preds)
if (e->src == p)
{
found_edge = 1;
break;
}
if (EDGE_INDEX (elist, p, s)
== EDGE_INDEX_NO_EDGE && found_edge != 0)
fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
p->index, s->index);
if (EDGE_INDEX (elist, p, s)
!= EDGE_INDEX_NO_EDGE && found_edge == 0)
fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
p->index, s->index, EDGE_INDEX (elist, p, s));
}
}
edge
find_edge (basic_block pred, basic_block succ)
{
edge e;
edge_iterator ei;
if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
{
FOR_EACH_EDGE (e, ei, pred->succs)
if (e->dest == succ)
return e;
}
else
{
FOR_EACH_EDGE (e, ei, succ->preds)
if (e->src == pred)
return e;
}
return NULL;
}
int
find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block 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 (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 (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_predecessors (basic_block bb)
{
edge e;
edge_iterator ei;
for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
{
if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
remove_edge (e);
else
ei_next (&ei);
}
}
void
remove_fake_edges (void)
{
basic_block bb;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
remove_fake_predecessors (bb);
}
void
remove_fake_exit_edges (void)
{
remove_fake_predecessors (EXIT_BLOCK_PTR);
}
void
add_noreturn_fake_exit_edges (void)
{
basic_block bb;
FOR_EACH_BB (bb)
if (EDGE_COUNT (bb->succs) == 0)
make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
void
connect_infinite_loops_to_exit (void)
{
basic_block unvisited_block = EXIT_BLOCK_PTR;
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,
unvisited_block);
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 (int *rts_order)
{
edge_iterator *stack;
int sp;
int postnum = 0;
sbitmap visited;
stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
sp = 0;
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (visited);
stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
while (sp)
{
edge_iterator ei;
basic_block src;
basic_block dest;
ei = stack[sp - 1];
src = ei_edge (ei)->src;
dest = ei_edge (ei)->dest;
if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
SET_BIT (visited, dest->index);
if (EDGE_COUNT (dest->succs) > 0)
stack[sp++] = ei_start (dest->succs);
else
rts_order[postnum++] = dest->index;
}
else
{
if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
rts_order[postnum++] = src->index;
if (!ei_one_before_end_p (ei))
ei_next (&stack[sp - 1]);
else
sp--;
}
}
free (stack);
sbitmap_free (visited);
}
int
flow_depth_first_order_compute (int *dfs_order, int *rc_order)
{
edge_iterator *stack;
int sp;
int dfsnum = 0;
int rcnum = n_basic_blocks - 1;
sbitmap visited;
stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
sp = 0;
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (visited);
stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
while (sp)
{
edge_iterator ei;
basic_block src;
basic_block dest;
ei = stack[sp - 1];
src = ei_edge (ei)->src;
dest = ei_edge (ei)->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 (EDGE_COUNT (dest->succs) > 0)
stack[sp++] = ei_start (dest->succs);
else if (rc_order)
rc_order[rcnum--] = dest->index;
}
else
{
if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
&& rc_order)
rc_order[rcnum--] = src->index;
if (!ei_one_before_end_p (ei))
ei_next (&stack[sp - 1]);
else
sp--;
}
}
free (stack);
sbitmap_free (visited);
gcc_assert (dfsnum == n_basic_blocks);
return dfsnum;
}
static void
flow_dfs_compute_reverse_init (depth_first_search_ds data)
{
data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
* sizeof (basic_block));
data->sp = 0;
data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
sbitmap_zero (data->visited_blocks);
return;
}
static void
flow_dfs_compute_reverse_add_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 (depth_first_search_ds data,
basic_block last_unvisited)
{
basic_block bb;
edge e;
edge_iterator ei;
while (data->sp > 0)
{
bb = data->stack[--data->sp];
FOR_EACH_EDGE (e, ei, bb->preds)
if (!TEST_BIT (data->visited_blocks,
e->src->index - (INVALID_BLOCK + 1)))
flow_dfs_compute_reverse_add_bb (data, e->src);
}
FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
return bb;
return NULL;
}
static void
flow_dfs_compute_reverse_finish (depth_first_search_ds data)
{
free (data->stack);
sbitmap_free (data->visited_blocks);
}
int
dfs_enumerate_from (basic_block bb, int reverse,
bool (*predicate) (basic_block, void *),
basic_block *rslt, int rslt_max, void *data)
{
basic_block *st, lbb;
int sp = 0, tv = 0;
st = xcalloc (rslt_max, sizeof (basic_block));
rslt[tv++] = st[sp++] = bb;
bb->flags |= BB_VISITED;
while (sp)
{
edge e;
edge_iterator ei;
lbb = st[--sp];
if (reverse)
{
FOR_EACH_EDGE (e, ei, lbb->preds)
if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
{
gcc_assert (tv != rslt_max);
rslt[tv++] = st[sp++] = e->src;
e->src->flags |= BB_VISITED;
}
}
else
{
FOR_EACH_EDGE (e, ei, lbb->succs)
if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
{
gcc_assert (tv != rslt_max);
rslt[tv++] = st[sp++] = e->dest;
e->dest->flags |= BB_VISITED;
}
}
}
free (st);
for (sp = 0; sp < tv; sp++)
rslt[sp]->flags &= ~BB_VISITED;
return tv;
}
static void
compute_dominance_frontiers_1 (bitmap *frontiers)
{
edge p;
edge_iterator ei;
basic_block b;
FOR_EACH_BB (b)
{
if (EDGE_COUNT (b->preds) >= 2)
{
FOR_EACH_EDGE (p, ei, b->preds)
{
basic_block runner = p->src;
basic_block domsb;
if (runner == ENTRY_BLOCK_PTR)
continue;
domsb = get_immediate_dominator (CDI_DOMINATORS, b);
while (runner != domsb)
{
bitmap_set_bit (frontiers[runner->index],
b->index);
runner = get_immediate_dominator (CDI_DOMINATORS,
runner);
}
}
}
}
}
void
compute_dominance_frontiers (bitmap *frontiers)
{
timevar_push (TV_DOM_FRONTIERS);
compute_dominance_frontiers_1 (frontiers);
timevar_pop (TV_DOM_FRONTIERS);
}