pmap *df_map;
};
+/**
+ * A wrapper for get_Block_idom.
+ * This function returns the block itself, if the block is the start
+ * block. Returning NULL would make any != comparison true which
+ * suggests, that the start block is dominated by some other node.
+ * @param bl The block.
+ * @return The immediate dominator of the block.
+ */
+static INLINE ir_node *get_idom(ir_node *bl)
+{
+ ir_node *idom = get_Block_idom(bl);
+ return idom == NULL ? bl : idom;
+}
+
static void compute_df_local(ir_node *bl, void *data)
{
pmap *df_map = ((dom_front_info_t *) data)->df_map;
pset *df = pmap_get(df_map, bl);
int i, n;
+ /*
+ * In the case that the immediate dominator is NULL, the
+ * block is the start block and its immediate dominator
+ * must be itself, else it is inserted into its own
+ * dominance frontier.
+ */
+ if(idom == NULL)
+ idom = bl;
+
/*
* Create a new dom frot set for this node,
* if none exists.
}
}
+static void compute_df(ir_node *n, pmap *df_map)
+{
+ ir_node *y, *c;
+ const ir_edge_t *edge;
+ pset *df = pset_new_ptr_default();
+
+ /* Add local dominance frontiers */
+ foreach_block_succ(n, edge) {
+ ir_node *y = edge->src;
+
+ if(get_idom(y) != n)
+ pset_insert_ptr(df, y);
+ }
+
+ /*
+ * Go recursively down the dominance tree and add all blocks
+ * int the dominance frontiers of the children, which are not
+ * dominated by the given block.
+ */
+ for(c = get_Block_dominated_first(n); c; c = get_Block_dominated_next(c)) {
+ pset *df_c;
+ ir_node *w;
+
+ compute_df(c, df_map);
+ df_c = pmap_get(df_map, c);
+
+ for(w = pset_first(df_c); w; w = pset_next(df_c)) {
+ if(!block_dominates(n, w))
+ pset_insert_ptr(df, w);
+ }
+ }
+
+ pmap_insert(df_map, n, df);
+
+}
+
dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
{
dom_front_info_t *info = malloc(sizeof(*info));
+ edges_assure(irg);
info->df_map = pmap_create();
+ compute_df(get_irg_start_block(irg), info->df_map);
+#if 0
/*
* This must be called as a post walker, since the dom front sets
* of all predecessors must be created when a block is reached.
*/
dom_tree_walk_irg(irg, NULL, compute_df_local, info);
dom_tree_walk_irg(irg, NULL, compute_df_up, info);
+#endif
return info;
}
/*
* Fill the worklist queue and the rest of the orig blocks array.
*/
- for(it = pset_first(copies), i = 0; it; it = pset_next(copies)) {
- ir_node *copy_block = get_nodes_block(it);
+ for(it = pset_first(copy_blocks), i = 0; it; it = pset_next(copy_blocks)) {
+ ir_node *copy_block = it;
- if(!block_dominates(orig_block, copy_block)) {
- assert(block_dominates(orig_block, copy_block)
- && "The block of the copy must be dominated by the block of the value");
- }
+ assert(block_dominates(orig_block, copy_block)
+ && "The block of the copy must be dominated by the block of the value");
pdeq_putr(worklist, copy_block);
orig_blocks[i++] = copy_block;
ir_node *y;
pset *df = be_get_dominance_frontier(df_info, bl);
+ DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
+ for(y = pset_first(df); y; y = pset_next(df))
+ DBG((dbg, LEVEL_3, "\t%+F\n", y));
+
for(y = pset_first(df); y; y = pset_next(df)) {
int n_preds = get_irn_arity(y);
/* Insert phi node */
phi = new_r_Phi(irg, y, n_preds, ins, mode);
DBG((dbg, LEVEL_2, " inserting phi %+F with %d args in block %+F\n",
- phi, n_preds, bl));
+ phi, n_preds, y));
/*
* The phi node itself is also a copy of the original
{
ir_node *curr_bl;
ir_node *start_irn;
+ firm_dbg_module_t *dbg = DBG_MODULE;
+ firm_dbg_set_mask(dbg, -1);
curr_bl = get_nodes_block(usage);
+
+ DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
/*
* If the usage is in a phi node, search the copy in the
* predecessor denoted by pos.
*/
if(is_Phi(usage)) {
- curr_bl = get_nodes_block(get_irn_n(curr_bl, pos));
+ curr_bl = get_Block_cfgpred_block(curr_bl, pos);
start_irn = sched_last(curr_bl);
- }
-
- else {
+ } else {
start_irn = sched_prev(usage);
}
for(irn = start_irn; !is_Block(irn); irn = sched_prev(irn)) {
/* Take the first copy we find. */
+
+ DBG((dbg, LEVEL_1, "Is %F a copy?\n", irn));
if(pset_find_ptr(copies, irn))
return irn;
}
ir_node *irn = outs[i].irn;
int pos = outs[i].pos;
+ DBG((dbg, LEVEL_2, " %+F(%d) -> ???\n", irn, pos));
def = search_def(irn, pos, copies, copy_blocks);
DBG((dbg, LEVEL_2, " %+F(%d) -> %+F\n", irn, pos, def));
static void add_all_phis_walker(ir_node *irn, void *data)
{
if(is_Phi(irn)) {
- int i, n;
+ int i, o, n;
struct phi_collect_info *info = data;
/*
if(get_irn_n(irn, i) == info->orig) {
pset_insert_ptr(info->copies, irn);
pset_insert_ptr(info->copy_blocks, get_nodes_block(irn));
+
break;
}
}
* All phis using the original value are also copies of it
* and must be present in the copies set.
*/
- add_all_phis_using(orig, copies, copy_blocks);
+ /* add_all_phis_using(orig, copies, copy_blocks);*/
for(i = 0; i < n; ++i) {
DBG((dbg, LEVEL_1,