#include "config.h"
#include "system.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "errors.h"
#include "et-forest.h"
struct dominance_info
{
et_forest_t forest;
varray_type varray;
};
#define BB_NODE(info, bb) \
((et_forest_node_t)VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2))
#define SET_BB_NODE(info, bb, node) \
(VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2) = (node))
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;
};
static void init_dom_info PARAMS ((struct dom_info *));
static void free_dom_info PARAMS ((struct dom_info *));
static void calc_dfs_tree_nonrec PARAMS ((struct dom_info *,
basic_block,
enum cdi_direction));
static void calc_dfs_tree PARAMS ((struct dom_info *,
enum cdi_direction));
static void compress PARAMS ((struct dom_info *, TBB));
static TBB eval PARAMS ((struct dom_info *, TBB));
static void link_roots PARAMS ((struct dom_info *, TBB, TBB));
static void calc_idoms PARAMS ((struct dom_info *,
enum cdi_direction));
void debug_dominance_info PARAMS ((dominance_info));
#define init_ar(var, type, num, content) \
do \
{ \
unsigned int i = 1; \
if (! (content)) \
(var) = (type *) xcalloc ((num), sizeof (type)); \
else \
{ \
(var) = (type *) xmalloc ((num) * sizeof (type)); \
for (i = 0; i < num; i++) \
(var)[i] = (content); \
} \
} \
while (0)
static void
init_dom_info (di)
struct dom_info *di;
{
unsigned int num = n_basic_blocks + 1 + 1;
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;
}
#undef init_ar
static void
free_dom_info (di)
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);
}
static void
calc_dfs_tree_nonrec (di, bb, reverse)
struct dom_info *di;
basic_block bb;
enum cdi_direction reverse;
{
edge e;
TBB child_i, my_i = 0;
edge *stack;
int sp;
basic_block en_block;
basic_block ex_block;
stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge));
sp = 0;
if (reverse)
{
e = bb->pred;
en_block = EXIT_BLOCK_PTR;
ex_block = ENTRY_BLOCK_PTR;
}
else
{
e = bb->succ;
en_block = ENTRY_BLOCK_PTR;
ex_block = EXIT_BLOCK_PTR;
}
while (1)
{
basic_block bn;
while (e)
{
edge e_next;
if (reverse)
{
bn = e->src;
if (bn == ex_block || di->dfs_order[bn->index])
{
e = e->pred_next;
continue;
}
bb = e->dest;
e_next = bn->pred;
}
else
{
bn = e->dest;
if (bn == ex_block || di->dfs_order[bn->index])
{
e = e->succ_next;
continue;
}
bb = e->src;
e_next = bn->succ;
}
if (bn == en_block)
abort ();
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++] = e;
e = e_next;
}
if (!sp)
break;
e = stack[--sp];
if (reverse)
e = e->pred_next;
else
e = e->succ_next;
}
free (stack);
}
static void
calc_dfs_tree (di, reverse)
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;
FOR_EACH_BB_REVERSE (b)
{
if (di->dfs_order[b->index])
continue;
di->dfs_order[b->index] = di->dfsnum;
di->dfs_to_bb[di->dfsnum] = b;
di->dfsnum++;
calc_dfs_tree_nonrec (di, b, reverse);
}
}
di->nodes = di->dfsnum - 1;
if (di->nodes != (unsigned int) n_basic_blocks + 1)
abort ();
}
static void
compress (di, v)
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 (di, v)
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 (di, v, w)
struct dom_info *di;
TBB v, 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 (di, reverse)
struct dom_info *di;
enum cdi_direction reverse;
{
TBB v, w, k, par;
basic_block en_block;
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, e_next;
par = di->dfs_parent[v];
k = v;
if (reverse)
e = bb->succ;
else
e = bb->pred;
for (; e; e = e_next)
{
TBB k1;
basic_block b;
if (reverse)
{
b = e->dest;
e_next = e->succ_next;
}
else
{
b = e->src;
e_next = e->pred_next;
}
if (b == en_block)
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;
}
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]];
}
dominance_info
calculate_dominance_info (reverse)
enum cdi_direction reverse;
{
struct dom_info di;
dominance_info info;
basic_block b;
info = xmalloc (sizeof (struct dominance_info));
info->forest = et_forest_create ();
VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info");
SET_BB_NODE (info, ENTRY_BLOCK_PTR, et_forest_add_node (info->forest,
ENTRY_BLOCK_PTR));
SET_BB_NODE (info, EXIT_BLOCK_PTR, et_forest_add_node (info->forest,
EXIT_BLOCK_PTR));
FOR_EACH_BB (b)
SET_BB_NODE (info, b, et_forest_add_node (info->forest, b));
init_dom_info (&di);
calc_dfs_tree (&di, reverse);
calc_idoms (&di, reverse);
FOR_EACH_BB (b)
{
TBB d = di.dom[di.dfs_order[b->index]];
if (di.dfs_to_bb[d])
et_forest_add_edge (info->forest, BB_NODE (info, di.dfs_to_bb[d]), BB_NODE (info, b));
}
free_dom_info (&di);
return info;
}
void
free_dominance_info (info)
dominance_info info;
{
basic_block bb;
FOR_EACH_BB (bb)
if (bb->index < (int)(info->varray->num_elements - 2)
&& BB_NODE (info, bb))
delete_from_dominance_info (info, bb);
delete_from_dominance_info (info, ENTRY_BLOCK_PTR);
delete_from_dominance_info (info, EXIT_BLOCK_PTR);
et_forest_delete (info->forest);
VARRAY_GROW (info->varray, 0);
free (info);
}
basic_block
get_immediate_dominator (dom, bb)
dominance_info dom;
basic_block bb;
{
return et_forest_node_value (dom->forest,
et_forest_parent (dom->forest,
BB_NODE (dom, bb)));
}
inline void
set_immediate_dominator (dom, bb, dominated_by)
dominance_info dom;
basic_block bb, dominated_by;
{
void *aux_bb_node;
et_forest_node_t bb_node = BB_NODE (dom, bb);
aux_bb_node = et_forest_parent (dom->forest, bb_node);
if (aux_bb_node)
et_forest_remove_edge (dom->forest, aux_bb_node, bb_node);
if (dominated_by != NULL)
{
if (bb == dominated_by)
abort ();
if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node))
abort ();
}
}
int
get_dominated_by (dom, bb, bbs)
dominance_info dom;
basic_block bb;
basic_block **bbs;
{
int n, i;
*bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
n = et_forest_enumerate_sons (dom->forest, BB_NODE (dom, bb), (et_forest_node_t *)*bbs);
for (i = 0; i < n; i++)
(*bbs)[i] = et_forest_node_value (dom->forest, (et_forest_node_t)(*bbs)[i]);
return n;
}
void
redirect_immediate_dominators (dom, bb, to)
dominance_info dom;
basic_block bb;
basic_block to;
{
et_forest_node_t *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
et_forest_node_t node = BB_NODE (dom, bb);
et_forest_node_t node2 = BB_NODE (dom, to);
int n = et_forest_enumerate_sons (dom->forest, node, bbs);
int i;
for (i = 0; i < n; i++)
{
et_forest_remove_edge (dom->forest, node, bbs[i]);
et_forest_add_edge (dom->forest, node2, bbs[i]);
}
free (bbs);
}
basic_block
nearest_common_dominator (dom, bb1, bb2)
dominance_info dom;
basic_block bb1;
basic_block bb2;
{
if (!bb1)
return bb2;
if (!bb2)
return bb1;
return et_forest_node_value (dom->forest,
et_forest_common_ancestor (dom->forest,
BB_NODE (dom, bb1),
BB_NODE (dom,
bb2)));
}
bool
dominated_by_p (dom, bb1, bb2)
dominance_info dom;
basic_block bb1;
basic_block bb2;
{
return nearest_common_dominator (dom, bb1, bb2) == bb2;
}
void
verify_dominators (dom)
dominance_info dom;
{
int err = 0;
basic_block bb;
FOR_EACH_BB (bb)
{
basic_block dom_bb;
dom_bb = recount_dominator (dom, bb);
if (dom_bb != get_immediate_dominator (dom, bb))
{
error ("dominator of %d should be %d, not %d",
bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index);
err = 1;
}
}
if (err)
abort ();
}
basic_block
recount_dominator (dom, bb)
dominance_info dom;
basic_block bb;
{
basic_block dom_bb = NULL;
edge e;
for (e = bb->pred; e; e = e->pred_next)
{
if (!dominated_by_p (dom, e->src, bb))
dom_bb = nearest_common_dominator (dom, dom_bb, e->src);
}
return dom_bb;
}
void
iterate_fix_dominators (dom, bbs, n)
dominance_info dom;
basic_block *bbs;
int n;
{
int i, changed = 1;
basic_block old_dom, new_dom;
while (changed)
{
changed = 0;
for (i = 0; i < n; i++)
{
old_dom = get_immediate_dominator (dom, bbs[i]);
new_dom = recount_dominator (dom, bbs[i]);
if (old_dom != new_dom)
{
changed = 1;
set_immediate_dominator (dom, bbs[i], new_dom);
}
}
}
}
void
add_to_dominance_info (dom, bb)
dominance_info dom;
basic_block bb;
{
VARRAY_GROW (dom->varray, last_basic_block + 3);
#ifdef ENABLE_CHECKING
if (BB_NODE (dom, bb))
abort ();
#endif
SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
}
void
delete_from_dominance_info (dom, bb)
dominance_info dom;
basic_block bb;
{
et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
SET_BB_NODE (dom, bb, NULL);
}
void
debug_dominance_info (dom)
dominance_info dom;
{
basic_block bb, bb2;
FOR_EACH_BB (bb)
if ((bb2 = get_immediate_dominator (dom, bb)))
fprintf (stderr, "%i %i\n", bb->index, bb2->index);
}