#include "beirgmod.h"
#define DBG_MODULE firm_dbg_register("firm.be.irgmod")
+#define DBG_LEVEL 0
struct _dom_front_info_t {
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, DBG_LEVEL);
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);
}
* This is neccessary, since the outs would be modified while
* interating on them what could bring the outs module in trouble.
*/
- DBG((dbg, LEVEL_2, " Users of %+F\n", orig));
outs = malloc(n_outs * sizeof(outs[0]));
foreach_out_edge(orig, edge) {
outs[i].irn = get_edge_src_irn(edge);
int pos = outs[i].pos;
def = search_def(irn, pos, copies, copy_blocks);
- DBG((dbg, LEVEL_2, " %+F(%d) -> %+F\n", irn, pos, def));
+ DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
if(def != NULL)
set_irn_n(irn, pos, def);
free(outs);
}
-struct phi_collect_info {
- const ir_node *orig;
- pset *copies;
- pset *copy_blocks;
-};
-
-static void add_all_phis_walker(ir_node *irn, void *data)
+/**
+ * Remove phis which are not neccesary.
+ * During place_phi_functions() phi functions are put on the dominance
+ * frontiers blindly. However some of them will never be used (these
+ * have at least one predecessor which is NULL, see search_def() for
+ * this case). Since place_phi_functions() enters them into the
+ * schedule, we have to remove them from there.
+ *
+ * @param copies The set of all copies made (including the phi functions).
+ */
+static void remove_odd_phis(pset *copies)
{
- if(is_Phi(irn)) {
- int i, n;
- struct phi_collect_info *info = data;
+ ir_node *irn;
- /*
- * Look at all operands of the phi. If one of them is the original
- * node, insert the phi into the copies and copy_blocks set.
- */
- for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
- 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;
- }
- }
+ for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
+ if(is_Phi(irn)) {
+ int i, n;
+ int illegal = 0;
+ assert(sched_is_scheduled(irn) && "phi must be scheduled");
+ for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
+ illegal = is_Bad(get_irn_n(irn, i));
+ if(illegal)
+ sched_remove(irn);
+ }
}
}
-/**
- * Add all phis using a node to a set.
- * @param orig The node the phis shall use.
- * @param copies The set where the phis shall be put into.
- * @param copy_blocks The set the blocks of the phis shall be put into.
- */
-static void add_all_phis_using(const ir_node *orig, pset *copies, pset *copy_blocks)
-{
- struct phi_collect_info info;
-
- info.copies = copies;
- info.copy_blocks = copy_blocks;
- info.orig = orig;
- irg_walk_graph(get_irn_irg(orig), add_all_phis_walker, NULL, &info);
-}
-
void be_introduce_copies(dom_front_info_t *info, ir_node *orig, int n, ir_node *copy_nodes[])
{
pset *copies = pset_new_ptr(2 * n);
firm_dbg_module_t *dbg = DBG_MODULE;
int i;
- firm_dbg_set_mask(dbg, -1);
+ firm_dbg_set_mask(dbg, DBG_LEVEL);
DBG((dbg, LEVEL_1, "Introducing following copies of %+F\n", orig));
/* Fill the sets. */
* 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);
-
for(i = 0; i < n; ++i) {
DBG((dbg, LEVEL_1,
" %+F in block %+F\n", copy_nodes[i], get_nodes_block(copy_nodes[i])));
*/
place_phi_functions(orig, copies, copy_blocks, info);
fix_usages(orig, copies, copy_blocks);
+ remove_odd_phis(copies);
/* reset the optimizations */
set_optimize(save_optimize);
projects / libfirm / blobdiff