+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
#include <stdlib.h>
#include "pset.h"
#include "pmap.h"
#include "util.h"
+#include "debug.h"
#include "irflag_t.h"
#include "ircons_t.h"
#include "irmode_t.h"
#include "irdom_t.h"
#include "iredges_t.h"
+#include "irgopt.h"
#include "be_t.h"
#include "bearch.h"
#include "beirgmod.h"
+#define DBG_MODULE firm_dbg_register("firm.be.irgmod")
+
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;
ir_node *idom = get_Block_idom(bl);
+ 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.
+ */
+ if(!df)
+ pmap_insert(df_map, bl, pset_new_ptr(16));
+
for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
/* The predecessor block */
/* The dominance frontier set of the predecessor. */
pset *df = pmap_get(df_map, pred);
+ if(!df) {
+ df = pset_new_ptr(16);
+ pmap_insert(df_map, pred, df);
+ }
- /*
- * Create the dominance frontier set of the predecessor
- * if it didn't exist.
- */
- if(!df) {
- df = pset_new_ptr(16);
- pmap_insert(df_map, pred, df);
- }
-
+ assert(df && "dom front set must have been created for this node");
if(pred != idom && bl)
pset_insert_ptr(df, bl);
ir_node *w;
pset *df = pmap_get(df_map, y);
- for(w = pset_first(df); df; w = pset_next(df))
+ for(w = pset_first(df); w; w = pset_next(df))
if(!block_dominates(bl, w) || bl == w)
pset_insert_ptr(df, w);
}
}
+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);
- /* Perhaps both can we interwined */
- dom_tree_walk_irg(irg, compute_df_local, NULL, info);
+#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;
}
pset *phi_blocks = pset_new_ptr(8);
ir_node **ins = NULL;
void *it;
+ firm_dbg_module_t *dbg = DBG_MODULE;
/*
* Allocate an array for all blocks where the copies and the original
* value were defined.
*/
- int n_orig_blocks = pset_count(copy_blocks) + 1;
+ int n_orig_blocks = pset_count(copy_blocks);
ir_node **orig_blocks = malloc(n_orig_blocks * sizeof(orig_blocks[0]));
- /*
- * Fill the array of definition blocks.
- */
- orig_blocks[0] = get_nodes_block(orig);
-
/*
* Fill the worklist queue and the rest of the orig blocks array.
*/
- for(it = pset_first(copies), i = 1; 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;
- 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, it);
+ pdeq_putr(worklist, copy_block);
orig_blocks[i++] = copy_block;
}
while(!pdeq_empty(worklist)) {
- ir_node *irn = pdeq_getl(worklist);
- ir_node *bl = get_nodes_block(irn);
+ ir_node *bl = pdeq_getl(worklist);
ir_node *y;
- int n_preds = get_irn_arity(bl);
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);
if(!pset_find_ptr(phi_blocks, y)) {
ir_node *phi;
*/
ins = realloc(ins, n_preds * sizeof(ins[0]));
for(i = 0; i < n_preds; ++i)
- ins[0] = orig;
+ ins[i] = orig;
/* Insert phi node */
- phi = new_r_Phi(irg, bl, n_preds, ins, mode);
+ 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, y));
/*
* The phi node itself is also a copy of the original
pset_insert_ptr(copies, phi);
pset_insert_ptr(copy_blocks, y);
- /* Insert the phi node into the schedule */
- sched_add_before(sched_first(y), phi);
+ /*
+ * Insert the phi node into the schedule if it
+ * can occur there (PhiM's are not to put into a schedule.
+ */
+ if(to_appear_in_schedule(phi))
+ sched_add_before(sched_first(y), phi);
/* Insert the phi node in the phi blocks set. */
pset_insert_ptr(phi_blocks, y);
static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks)
{
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));
+ if(is_Phi(usage)) {
+ curr_bl = get_Block_cfgpred_block(curr_bl, pos);
+ start_irn = sched_last(curr_bl);
+ } else {
+ start_irn = sched_prev(usage);
+ }
/*
* Traverse the dominance tree upwards from the
ir_node *irn;
/* Look at each instruction from last to first. */
- sched_foreach_reverse(curr_bl, irn) {
+ 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;
}
-
- assert(0 && "We must have encountered a copy");
}
/* If were not done yet, look in the immediate dominator */
curr_bl = get_Block_idom(curr_bl);
+ if(curr_bl)
+ start_irn = sched_last(curr_bl);
}
return NULL;
static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
{
- int i;
+ int i = 0;
int n_outs = 0;
const ir_edge_t *edge;
- const ir_edge_t **outs;
+ firm_dbg_module_t *dbg = DBG_MODULE;
+
+ struct {
+ ir_node *irn;
+ int pos;
+ } *outs;
/* Count the number of outs. */
foreach_out_edge(orig, edge)
* 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++] = edge;
+ foreach_out_edge(orig, edge) {
+ outs[i].irn = get_edge_src_irn(edge);
+ outs[i].pos = get_edge_src_pos(edge);
+ i += 1;
+ }
/*
* Search the valid def for each out and set it.
*/
for(i = 0; i < n_outs; ++i) {
ir_node *def;
- ir_node *irn = get_edge_src_irn(outs[i]);
- int pos = get_edge_src_pos(outs[i]);
+ 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);
- set_irn_n(irn, pos, def);
+ DBG((dbg, LEVEL_2, " %+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)
+{
+ if(is_Phi(irn)) {
+ int i, o, n;
+ struct phi_collect_info *info = data;
+
+ /*
+ * 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;
+ }
+ }
+
+
+ }
+}
+
+/**
+ * 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);
pset *copy_blocks = pset_new_ptr(2 * n);
int save_optimize = get_optimize();
+ int save_normalize = get_opt_normalize();
+ firm_dbg_module_t *dbg = DBG_MODULE;
int i;
+ firm_dbg_set_mask(dbg, -1);
+ DBG((dbg, LEVEL_1, "Introducing following copies of %+F\n", orig));
+
/* Fill the sets. */
+ pset_insert_ptr(copies, orig);
+ pset_insert_ptr(copy_blocks, get_nodes_block(orig));
+
+ /*
+ * 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])));
pset_insert_ptr(copies, copy_nodes[i]);
pset_insert_ptr(copy_blocks, get_nodes_block(copy_nodes[i]));
}
* disappear.
*/
set_optimize(0);
+ set_opt_normalize(0);
/*
* Place the phi functions and reroute the usages.
/* reset the optimizations */
set_optimize(save_optimize);
+ set_opt_normalize(save_normalize);
del_pset(copies);
del_pset(copy_blocks);
}
-
-void insert_Perm_after(const be_main_session_env_t *env,
- const arch_register_class_t *cls, ir_node *pos)
-{
- const arch_env_t *arch_env = env->main_env->arch_env;
- ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
- ir_graph *irg = get_irn_irg(bl);
- pset *live_end = get_live_end(bl);
- pset *live = pset_new_ptr_default();
- ir_node *curr, *irn, *perm, **nodes;
- int i, n;
-
- /* put all live ends in the live set. */
- for(irn = pset_first(live_end); irn; irn = pset_next(live_end))
- pset_insert_ptr(live, irn);
-
- sched_foreach_reverse(bl, irn) {
-
- if(arch_irn_has_reg_class(arch_env, irn, arch_pos_make_out(0), cls))
- pset_remove_ptr(live, irn);
-
- for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
- ir_node *op = get_irn_n(irn, i);
-
- if(arch_irn_has_reg_class(arch_env, op, arch_pos_make_out(0), cls))
- pset_insert_ptr(live, op);
- }
-
- if(sched_prev(irn) == pos)
- break;
- }
-
- n = pset_count(live);
- nodes = malloc(n * sizeof(nodes[0]));
-
- for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++)
- nodes[i] = irn;
-
- curr = perm = new_Perm(env->main_env->node_factory, cls, irg, bl, n, nodes);
- sched_add_after(pos, perm);
- free(nodes);
-
- for(i = 0; i < n; ++i) {
- ir_node *copies[1];
- ir_node *perm_op = get_irn_n(perm, i);
-
- ir_mode *mode = get_irn_mode(perm_op);
- ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
- sched_add_after(curr, proj);
- curr = proj;
-
- copies[0] = proj;
- be_introduce_copies(env->dom_front, perm_op, array_size(copies), copies);
- }
-
-}
projects / libfirm / blobdiff