#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "obstack.h"
#include "basic-block.h"
#include "toplev.h"
#include "et-forest.h"
#include "timevar.h"
enum dom_state dom_computed[2];
typedef unsigned int TBB;
struct dom_info
{
TBB *dfs_parent;
TBB *key;
TBB *path_min;
TBB *bucket;
TBB *next_bucket;
TBB *dom;
TBB *set_chain;
unsigned int *set_size;
TBB *set_child;
TBB *dfs_order;
basic_block *dfs_to_bb;
unsigned int dfsnum;
unsigned int nodes;
bitmap fake_exit_edge;
};
static void init_dom_info (struct dom_info *, enum cdi_direction);
static void free_dom_info (struct dom_info *);
static void calc_dfs_tree_nonrec (struct dom_info *, basic_block,
enum cdi_direction);
static void calc_dfs_tree (struct dom_info *, enum cdi_direction);
static void compress (struct dom_info *, TBB);
static TBB eval (struct dom_info *, TBB);
static void link_roots (struct dom_info *, TBB, TBB);
static void calc_idoms (struct dom_info *, enum cdi_direction);
void debug_dominance_info (enum cdi_direction);
static unsigned n_bbs_in_dom_tree[2];
#define init_ar(var, type, num, content) \
do \
{ \
unsigned int i = 1; \
if (! (content)) \
(var) = XCNEWVEC (type, num); \
else \
{ \
(var) = XNEWVEC (type, (num)); \
for (i = 0; i < num; i++) \
(var)[i] = (content); \
} \
} \
while (0)
static void
init_dom_info (struct dom_info *di, enum cdi_direction dir)
{
unsigned int num = n_basic_blocks;
init_ar (di->dfs_parent, TBB, num, 0);
init_ar (di->path_min, TBB, num, i);
init_ar (di->key, TBB, num, i);
init_ar (di->dom, TBB, num, 0);
init_ar (di->bucket, TBB, num, 0);
init_ar (di->next_bucket, TBB, num, 0);
init_ar (di->set_chain, TBB, num, 0);
init_ar (di->set_size, unsigned int, num, 1);
init_ar (di->set_child, TBB, num, 0);
init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
init_ar (di->dfs_to_bb, basic_block, num, 0);
di->dfsnum = 1;
di->nodes = 0;
di->fake_exit_edge = dir ? BITMAP_ALLOC (NULL) : NULL;
}
#undef init_ar
static void
free_dom_info (struct dom_info *di)
{
free (di->dfs_parent);
free (di->path_min);
free (di->key);
free (di->dom);
free (di->bucket);
free (di->next_bucket);
free (di->set_chain);
free (di->set_size);
free (di->set_child);
free (di->dfs_order);
free (di->dfs_to_bb);
BITMAP_FREE (di->fake_exit_edge);
}
static void
calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb,
enum cdi_direction reverse)
{
edge e;
TBB child_i, my_i = 0;
edge_iterator *stack;
edge_iterator ei, einext;
int sp;
basic_block en_block;
basic_block ex_block;
stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
sp = 0;
if (reverse)
{
ei = ei_start (bb->preds);
en_block = EXIT_BLOCK_PTR;
ex_block = ENTRY_BLOCK_PTR;
}
else
{
ei = ei_start (bb->succs);
en_block = ENTRY_BLOCK_PTR;
ex_block = EXIT_BLOCK_PTR;
}
while (1)
{
basic_block bn;
while (!ei_end_p (ei))
{
e = ei_edge (ei);
if (reverse)
{
bn = e->src;
if (bn == ex_block || di->dfs_order[bn->index])
{
ei_next (&ei);
continue;
}
bb = e->dest;
einext = ei_start (bn->preds);
}
else
{
bn = e->dest;
if (bn == ex_block || di->dfs_order[bn->index])
{
ei_next (&ei);
continue;
}
bb = e->src;
einext = ei_start (bn->succs);
}
gcc_assert (bn != en_block);
if (bb != en_block)
my_i = di->dfs_order[bb->index];
else
my_i = di->dfs_order[last_basic_block];
child_i = di->dfs_order[bn->index] = di->dfsnum++;
di->dfs_to_bb[child_i] = bn;
di->dfs_parent[child_i] = my_i;
stack[sp++] = ei;
ei = einext;
}
if (!sp)
break;
ei = stack[--sp];
ei_next (&ei);
}
free (stack);
}
static void
calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse)
{
basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
di->dfs_order[last_basic_block] = di->dfsnum;
di->dfs_to_bb[di->dfsnum] = begin;
di->dfsnum++;
calc_dfs_tree_nonrec (di, begin, reverse);
if (reverse)
{
basic_block b;
bool saw_unconnected = false;
FOR_EACH_BB_REVERSE (b)
{
if (EDGE_COUNT (b->succs) > 0)
{
if (di->dfs_order[b->index] == 0)
saw_unconnected = true;
continue;
}
bitmap_set_bit (di->fake_exit_edge, b->index);
di->dfs_order[b->index] = di->dfsnum;
di->dfs_to_bb[di->dfsnum] = b;
di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
di->dfsnum++;
calc_dfs_tree_nonrec (di, b, reverse);
}
if (saw_unconnected)
{
FOR_EACH_BB_REVERSE (b)
{
if (di->dfs_order[b->index])
continue;
bitmap_set_bit (di->fake_exit_edge, b->index);
di->dfs_order[b->index] = di->dfsnum;
di->dfs_to_bb[di->dfsnum] = b;
di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
di->dfsnum++;
calc_dfs_tree_nonrec (di, b, reverse);
}
}
}
di->nodes = di->dfsnum - 1;
gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
}
static void
compress (struct dom_info *di, TBB v)
{
TBB parent = di->set_chain[v];
if (di->set_chain[parent])
{
compress (di, parent);
if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
di->path_min[v] = di->path_min[parent];
di->set_chain[v] = di->set_chain[parent];
}
}
static inline TBB
eval (struct dom_info *di, TBB v)
{
TBB rep = di->set_chain[v];
if (!rep)
return di->path_min[v];
if (di->set_chain[rep])
{
compress (di, v);
rep = di->set_chain[v];
}
if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
return di->path_min[v];
else
return di->path_min[rep];
}
static void
link_roots (struct dom_info *di, TBB v, TBB w)
{
TBB s = w;
while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
{
if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
>= 2 * di->set_size[di->set_child[s]])
{
di->set_chain[di->set_child[s]] = s;
di->set_child[s] = di->set_child[di->set_child[s]];
}
else
{
di->set_size[di->set_child[s]] = di->set_size[s];
s = di->set_chain[s] = di->set_child[s];
}
}
di->path_min[s] = di->path_min[w];
di->set_size[v] += di->set_size[w];
if (di->set_size[v] < 2 * di->set_size[w])
{
TBB tmp = s;
s = di->set_child[v];
di->set_child[v] = tmp;
}
while (s)
{
di->set_chain[s] = v;
s = di->set_child[s];
}
}
static void
calc_idoms (struct dom_info *di, enum cdi_direction reverse)
{
TBB v, w, k, par;
basic_block en_block;
edge_iterator ei, einext;
if (reverse)
en_block = EXIT_BLOCK_PTR;
else
en_block = ENTRY_BLOCK_PTR;
v = di->nodes;
while (v > 1)
{
basic_block bb = di->dfs_to_bb[v];
edge e;
par = di->dfs_parent[v];
k = v;
ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
if (reverse)
{
if (bitmap_bit_p (di->fake_exit_edge, bb->index))
{
einext = ei;
einext.index = 0;
goto do_fake_exit_edge;
}
}
while (!ei_end_p (ei))
{
TBB k1;
basic_block b;
e = ei_edge (ei);
b = (reverse) ? e->dest : e->src;
einext = ei;
ei_next (&einext);
if (b == en_block)
{
do_fake_exit_edge:
k1 = di->dfs_order[last_basic_block];
}
else
k1 = di->dfs_order[b->index];
if (k1 > v)
k1 = di->key[eval (di, k1)];
if (k1 < k)
k = k1;
ei = einext;
}
di->key[v] = k;
link_roots (di, par, v);
di->next_bucket[v] = di->bucket[k];
di->bucket[k] = v;
for (w = di->bucket[par]; w; w = di->next_bucket[w])
{
k = eval (di, w);
if (di->key[k] < di->key[w])
di->dom[w] = k;
else
di->dom[w] = par;
}
di->bucket[par] = 0;
v--;
}
di->dom[1] = 0;
for (v = 2; v <= di->nodes; v++)
if (di->dom[v] != di->key[v])
di->dom[v] = di->dom[di->dom[v]];
}
static void
assign_dfs_numbers (struct et_node *node, int *num)
{
struct et_node *son;
node->dfs_num_in = (*num)++;
if (node->son)
{
assign_dfs_numbers (node->son, num);
for (son = node->son->right; son != node->son; son = son->right)
assign_dfs_numbers (son, num);
}
node->dfs_num_out = (*num)++;
}
static void
compute_dom_fast_query (enum cdi_direction dir)
{
int num = 0;
basic_block bb;
gcc_assert (dom_info_available_p (dir));
if (dom_computed[dir] == DOM_OK)
return;
FOR_ALL_BB (bb)
{
if (!bb->dom[dir]->father)
assign_dfs_numbers (bb->dom[dir], &num);
}
dom_computed[dir] = DOM_OK;
}
void
calculate_dominance_info (enum cdi_direction dir)
{
struct dom_info di;
basic_block b;
if (dom_computed[dir] == DOM_OK)
return;
timevar_push (TV_DOMINANCE);
if (!dom_info_available_p (dir))
{
gcc_assert (!n_bbs_in_dom_tree[dir]);
FOR_ALL_BB (b)
{
b->dom[dir] = et_new_tree (b);
}
n_bbs_in_dom_tree[dir] = n_basic_blocks;
init_dom_info (&di, dir);
calc_dfs_tree (&di, dir);
calc_idoms (&di, dir);
FOR_EACH_BB (b)
{
TBB d = di.dom[di.dfs_order[b->index]];
if (di.dfs_to_bb[d])
et_set_father (b->dom[dir], di.dfs_to_bb[d]->dom[dir]);
}
free_dom_info (&di);
dom_computed[dir] = DOM_NO_FAST_QUERY;
}
compute_dom_fast_query (dir);
timevar_pop (TV_DOMINANCE);
}
void
free_dominance_info (enum cdi_direction dir)
{
basic_block bb;
if (!dom_info_available_p (dir))
return;
FOR_ALL_BB (bb)
{
et_free_tree_force (bb->dom[dir]);
bb->dom[dir] = NULL;
}
et_free_pools ();
n_bbs_in_dom_tree[dir] = 0;
dom_computed[dir] = DOM_NONE;
}
basic_block
get_immediate_dominator (enum cdi_direction dir, basic_block bb)
{
struct et_node *node = bb->dom[dir];
gcc_assert (dom_computed[dir]);
if (!node->father)
return NULL;
return node->father->data;
}
inline void
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
basic_block dominated_by)
{
struct et_node *node = bb->dom[dir];
gcc_assert (dom_computed[dir]);
if (node->father)
{
if (node->father->data == dominated_by)
return;
et_split (node);
}
if (dominated_by)
et_set_father (node, dominated_by->dom[dir]);
if (dom_computed[dir] == DOM_OK)
dom_computed[dir] = DOM_NO_FAST_QUERY;
}
int
get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
{
int n;
struct et_node *node = bb->dom[dir], *son = node->son, *ason;
gcc_assert (dom_computed[dir]);
if (!son)
{
*bbs = NULL;
return 0;
}
for (ason = son->right, n = 1; ason != son; ason = ason->right)
n++;
*bbs = XNEWVEC (basic_block, n);
(*bbs)[0] = son->data;
for (ason = son->right, n = 1; ason != son; ason = ason->right)
(*bbs)[n++] = ason->data;
return n;
}
unsigned
get_dominated_by_region (enum cdi_direction dir, basic_block *region,
unsigned n_region, basic_block *doms)
{
unsigned n_doms = 0, i;
basic_block dom;
for (i = 0; i < n_region; i++)
region[i]->flags |= BB_DUPLICATED;
for (i = 0; i < n_region; i++)
for (dom = first_dom_son (dir, region[i]);
dom;
dom = next_dom_son (dir, dom))
if (!(dom->flags & BB_DUPLICATED))
doms[n_doms++] = dom;
for (i = 0; i < n_region; i++)
region[i]->flags &= ~BB_DUPLICATED;
return n_doms;
}
void
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
basic_block to)
{
struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son;
gcc_assert (dom_computed[dir]);
if (!bb_node->son)
return;
while (bb_node->son)
{
son = bb_node->son;
et_split (son);
et_set_father (son, to_node);
}
if (dom_computed[dir] == DOM_OK)
dom_computed[dir] = DOM_NO_FAST_QUERY;
}
basic_block
nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
{
gcc_assert (dom_computed[dir]);
if (!bb1)
return bb2;
if (!bb2)
return bb1;
return et_nca (bb1->dom[dir], bb2->dom[dir])->data;
}
basic_block
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
{
unsigned i, first;
bitmap_iterator bi;
basic_block dom;
first = bitmap_first_set_bit (blocks);
dom = BASIC_BLOCK (first);
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
if (dom != BASIC_BLOCK (i))
dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
return dom;
}
bool
dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2)
{
struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir];
gcc_assert (dom_computed[dir]);
if (dom_computed[dir] == DOM_OK)
return (n1->dfs_num_in >= n2->dfs_num_in
&& n1->dfs_num_out <= n2->dfs_num_out);
return et_below (n1, n2);
}
unsigned
bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
{
struct et_node *n = bb->dom[dir];
gcc_assert (dom_computed[dir] == DOM_OK);
return n->dfs_num_in;
}
unsigned
bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
{
struct et_node *n = bb->dom[dir];
gcc_assert (dom_computed[dir] == DOM_OK);
return n->dfs_num_out;
}
void
verify_dominators (enum cdi_direction dir)
{
int err = 0;
basic_block bb;
gcc_assert (dom_info_available_p (dir));
FOR_EACH_BB (bb)
{
basic_block dom_bb;
basic_block imm_bb;
dom_bb = recount_dominator (dir, bb);
imm_bb = get_immediate_dominator (dir, bb);
if (dom_bb != imm_bb)
{
if ((dom_bb == NULL) || (imm_bb == NULL))
error ("dominator of %d status unknown", bb->index);
else
error ("dominator of %d should be %d, not %d",
bb->index, dom_bb->index, imm_bb->index);
err = 1;
}
}
if (dir == CDI_DOMINATORS)
{
FOR_EACH_BB (bb)
{
if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR))
{
error ("ENTRY does not dominate bb %d", bb->index);
err = 1;
}
}
}
gcc_assert (!err);
}
basic_block
recount_dominator (enum cdi_direction dir, basic_block bb)
{
basic_block dom_bb = NULL;
edge e;
edge_iterator ei;
gcc_assert (dom_computed[dir]);
if (dir == CDI_DOMINATORS)
{
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR))
continue;
if (!dominated_by_p (dir, e->src, bb))
dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
}
}
else
{
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (!dominated_by_p (dir, e->dest, bb))
dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
}
}
return dom_bb;
}
void
iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
{
int i, changed = 1;
basic_block old_dom, new_dom;
gcc_assert (dom_computed[dir]);
for (i = 0; i < n; i++)
set_immediate_dominator (dir, bbs[i], NULL);
while (changed)
{
changed = 0;
for (i = 0; i < n; i++)
{
old_dom = get_immediate_dominator (dir, bbs[i]);
new_dom = recount_dominator (dir, bbs[i]);
if (old_dom != new_dom)
{
changed = 1;
set_immediate_dominator (dir, bbs[i], new_dom);
}
}
}
for (i = 0; i < n; i++)
gcc_assert (get_immediate_dominator (dir, bbs[i]));
}
void
add_to_dominance_info (enum cdi_direction dir, basic_block bb)
{
gcc_assert (dom_computed[dir]);
gcc_assert (!bb->dom[dir]);
n_bbs_in_dom_tree[dir]++;
bb->dom[dir] = et_new_tree (bb);
if (dom_computed[dir] == DOM_OK)
dom_computed[dir] = DOM_NO_FAST_QUERY;
}
void
delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
{
gcc_assert (dom_computed[dir]);
et_free_tree (bb->dom[dir]);
bb->dom[dir] = NULL;
n_bbs_in_dom_tree[dir]--;
if (dom_computed[dir] == DOM_OK)
dom_computed[dir] = DOM_NO_FAST_QUERY;
}
basic_block
first_dom_son (enum cdi_direction dir, basic_block bb)
{
struct et_node *son = bb->dom[dir]->son;
return son ? son->data : NULL;
}
basic_block
next_dom_son (enum cdi_direction dir, basic_block bb)
{
struct et_node *next = bb->dom[dir]->right;
return next->father->son == next ? NULL : next->data;
}
bool
dom_info_available_p (enum cdi_direction dir)
{
return dom_computed[dir] != DOM_NONE;
}
void
debug_dominance_info (enum cdi_direction dir)
{
basic_block bb, bb2;
FOR_EACH_BB (bb)
if ((bb2 = get_immediate_dominator (dir, bb)))
fprintf (stderr, "%i %i\n", bb->index, bb2->index);
}