#include "error.h"
/**
- * Mapping an address to an densed ID.
+ * Mapping an address to an dense ID.
*/
typedef struct address_entry_t {
unsigned id; /**< The ID */
memop_t *avail; /**< used locally for the avail map */
};
-#define get_block_entry(block) ((block_t *)get_irn_link(block))
-
/**
* Metadata for this pass.
*/
block_t *forward; /**< Inverse post-order list of all blocks Start->End */
block_t *backward; /**< Inverse post-order list of all blocks End->Start */
ir_node *start_bl; /**< start block of the current graph */
+ ir_node *end_bl; /**< end block of the current graph */
unsigned *curr_set; /**< current set of addresses */
unsigned curr_adr_id; /**< number for address mapping */
unsigned n_mem_ops; /**< number of memory operations (Loads/Stores) */
#define dump_curr(bl, s)
#endif /* DEBUG_libfirm */
+/** Get the block entry for a block node */
+static block_t *get_block_entry(const ir_node *block) {
+ assert(is_Block(block));
+
+ return get_irn_link(block);
+}
+
+/** Get the memop entry for a memory operation node */
+static memop_t *get_irn_memop(const ir_node *irn) {
+ assert(! is_Block(irn));
+ return get_irn_link(irn);
+}
+
/**
* Walk over the memory edges from definition to users.
*
set_irn_link(block, entry);
/* create the list in inverse order */
- env.forward = entry;
+ env.forward = entry;
+ /* remember temporary the last one */
+ env.backward = entry;
}
/**
block_t *entry = get_block_entry(block);
memop_t *last, *op;
- (void) ctx;
- entry->backward_next = env.backward;
+ (void)ctx;
- /* create the list in inverse order */
- env.backward = entry;
+ /*
+ * Do NOT link in the end block yet. We want it to be
+ * the first in the list. This is NOT guaranteed by the walker
+ * if we have endless loops.
+ */
+ if (block != env.end_bl) {
+ entry->backward_next = env.backward;
+
+ /* create the list in inverse order */
+ env.backward = entry;
+ }
/* create backward links for all memory ops */
last = NULL;
m->next = NULL;
m->flags = 0;
+ set_irn_link(irn, m);
return m;
}
* @param adr the IR-node representing the address
*/
static unsigned register_address(ir_node *adr) {
- address_entry *entry = ir_nodemap_get(&env.adr_map, adr);
+ address_entry *entry;
+
+ /* skip Confirms and Casts */
+restart:
+ if (is_Confirm(adr)) {
+ adr = get_Confirm_value(adr);
+ goto restart;
+ }
+ if (is_Cast(adr)) {
+ adr = get_Cast_op(adr);
+ goto restart;
+ }
+
+ entry = ir_nodemap_get(&env.adr_map, adr);
if (entry == NULL) {
/* new address */
for (i = get_irn_n_outs(load) - 1; i >= 0; --i) {
ir_node *proj = get_irn_out(load, i);
+ /* beware of keep edges */
+ if (is_End(proj))
+ continue;
+
switch (get_Proj_proj(proj)) {
case pn_Load_res:
m->value.value = proj;
for (i = get_irn_n_outs(store) - 1; i >= 0; --i) {
ir_node *proj = get_irn_out(store, i);
+ /* beware of keep edges */
+ if (is_End(proj))
+ continue;
+
switch (get_Proj_proj(proj)) {
case pn_Store_X_except:
m->flags |= FLAG_EXCEPTION;
for (i = get_irn_n_outs(call) - 1; i >= 0; --i) {
ir_node *proj = get_irn_out(call, i);
+ /* beware of keep edges */
+ if (is_End(proj))
+ continue;
+
switch (get_Proj_proj(proj)) {
case pn_Call_X_except:
m->flags |= FLAG_EXCEPTION;
for (i = get_irn_n_outs(div) - 1; i >= 0; --i) {
ir_node *proj = get_irn_out(div, i);
+ /* beware of keep edges */
+ if (is_End(proj))
+ continue;
+
switch (get_Proj_proj(proj)) {
case pn_Generic_X_except:
m->flags |= FLAG_EXCEPTION;
}
}
+/**
+ * Update a memop for a Phi.
+ *
+ * @param m the memop
+ */
+static void update_Phi_memop(memop_t *m) {
+ /* the Phi is it's own mem */
+ m->mem = m->node;
+}
+
/**
* Memory walker: collect all memory ops and build topological lists.
*/
entry = get_block_entry(block);
if (is_Phi(irn)) {
+ update_Phi_memop(op);
/* Phis must be always placed first */
op->next = entry->memop_forward;
entry->memop_forward = op;
}
/**
- * find a definition for a value in the given block.
+ * Add a Conv if needed.
+ */
+static ir_node *conv_to(ir_node *irn, ir_mode *mode) {
+ if (get_irn_mode(irn) != mode) {
+ ir_node *block = get_nodes_block(irn);
+ return new_r_Conv(current_ir_graph, block, irn, mode, 0);
+ }
+ return irn;
+}
+
+/**
+ * build a phi definition for a value in the given block
*
* @param block the block
* @param value the value
*
* @return the definition
*/
-static ir_node *find_definition(ir_node *block, const value_t *value) {
- ir_node *def_bl = get_nodes_block(value->value);
+static ir_node *build_phi_definition(ir_node *block, const value_t *value) {
ir_node **in, *phi;
int i, n;
memop_t *mop;
-
- if (block_dominates(def_bl, block))
- return value->value;
+ ir_mode *mode = value->mode;
/* no: we need a new Phi */
n = get_Block_n_cfgpreds(block);
while (n == 1) {
block = get_Block_cfgpred_block(block, 0);
n = get_Block_n_cfgpreds(block);
- mop = find_address(get_block_entry(block), value);
+ mop = find_address_avail(get_block_entry(block), value);
- assert(mop != NULL);
+ if (mop == NULL) {
+ /* this can only happen, if modes cannot be converted */
+ return NULL;
+ }
value = &mop->value;
}
NEW_ARR_A(ir_node *, in, n);
for (i = n - 1; i >= 0; --i) {
ir_node *pred_bl = get_Block_cfgpred_block(block, i);
- mop = find_address(get_block_entry(pred_bl), value);
- in[i] = find_definition(pred_bl, &mop->value);
+ ir_node *def_bl;
+
+ mop = find_address_avail(get_block_entry(pred_bl), value);
+ if (mop == NULL)
+ return NULL;
+
+ def_bl = get_nodes_block(mop->value.value);
+
+ if (block_dominates(def_bl, pred_bl))
+ in[i] = conv_to(mop->value.value, mode);
+ else {
+ ir_node *def = build_phi_definition(pred_bl, &mop->value);
+ if (def == NULL)
+ return NULL;
+ in[i] = conv_to(def, mode);
+ }
}
- phi = new_r_Phi(current_ir_graph, block, n, in, value->mode);
+ phi = new_r_Phi(current_ir_graph, block, n, in, mode);
DB((dbg, LEVEL_2, "Created new Phi %+F for value %+F in block %+F\n", phi, value->value, block));
return phi;
}
+/**
+ * find a definition for a value in the given block or above.
+ *
+ * @param block the block
+ * @param op the memop: the definition must dominate it
+ * @param value the value
+ *
+ * @return the definition or NULL if modes are different
+ */
+static ir_node *find_definition(ir_node *block, const memop_t *op, const value_t *value) {
+ ir_node *def_block = get_nodes_block(value->value);
+
+ if (def_block == block) {
+ /* the value is in our block: check, if it is above in the memory list */
+ const memop_t *p;
+
+ for (p = op->prev; p != NULL; p = p->prev) {
+ if (!(p->flags & FLAG_KILLED_NODE) &&
+ p->value.address == value->address) {
+ /* found */
+ assert(p->value.value == value->value);
+ return p->value.value;
+ }
+ }
+ } else if (block_dominates(def_block, block)) {
+ /* strictly dominates */
+ return value->value;
+ }
+
+ return build_phi_definition(block, value);
+}
+
/**
* Mark a Load memop to be replace by a definition
*
ir_node *pred = get_Block_cfgpred_block(bl->block, 0);
block_t *pred_bl = get_block_entry(pred);
- memcpy(env.curr_set, pred_bl->avail_out, BYTE_SIZE(env.rbs_size));
+ rbitset_cpy(env.curr_set, pred_bl->avail_out, env.rbs_size);
n = get_Block_n_cfgpreds(bl->block);
if (n > 1) {
/* more than one predecessors, calculate the join */
for (i = n - 1; i > 0; --i) {
- ir_node *pred = get_Block_cfgpred_block(bl->block, i);
- block_t *pred_bl = get_block_entry(pred);
+ ir_node *pred = skip_Proj(get_Block_cfgpred(bl->block, i));
+ block_t *pred_bl = get_block_entry(get_nodes_block(pred));
rbitset_and(env.curr_set, pred_bl->avail_out, env.rbs_size);
+ if (is_Load(pred) || is_Store(pred)) {
+ /* We reached this block by an exception from a Load or Store:
+ * the memop was NOT completed than, kill it
+ */
+ memop_t *exc_op = get_irn_memop(pred);
+ rbitset_clear(env.curr_set, exc_op->value.id);
+ }
+
}
/* sure that all values are in the map */
for (pos = env.rbs_size - 1; pos >= 0; --pos) {
/* do we have this already? */
memop_t *other = find_address(bl, &op->value);
if (other != NULL) {
- if (is_Store(other->node)) {
- /* RAW */
- DB((dbg, LEVEL_1, "RAW %+F %+F\n", op->node, other->node));
+ def = find_definition(bl->block, op, &other->value);
+ if (def != NULL) {
+#ifdef DEBUG_libfirm
+ if (is_Store(other->node)) {
+ /* RAW */
+ DB((dbg, LEVEL_1, "RAW %+F <- %+F(%+F)\n", op->node, def, other->node));
+ } else {
+ /* RAR */
+ DB((dbg, LEVEL_1, "RAR %+F <- %+F(%+F)\n", op->node, def, other->node));
+ }
+#endif
+ mark_replace_load(op, def);
} else {
- /* RAR */
- DB((dbg, LEVEL_1, "RAR %+F %+F\n", op->node, other->node));
+ /* overwrite it */
+ add_memop(bl, op);
}
- def = find_definition(bl->block, &other->value);
- mark_replace_load(op, def);
} else {
/* add this value */
kill_stores(bl, &op->value);
/* do we have this store already */
memop_t *other = find_address(bl, &op->value);
if (other != NULL) {
- if (is_Store(other->node)) {
- /* a WAW */
- DB((dbg, LEVEL_1, "WAW %+F %+F\n", op->node, other->node));
+ if (is_Store(other->node) &&
+ get_nodes_block(other->node) == get_nodes_block(op->node)) {
+ /*
+ * A WAW in the same block we can kick the first store.
+ * This is a shortcut: we know that the second Store will be anticipated
+ * then in an case.
+ */
+ DB((dbg, LEVEL_1, "WAW %+F <- %+F\n", op->node, other->node));
mark_remove_store(other);
/* FIXME: a Load might be get freed due to this killed store */
} else if (other->value.value == op->value.value) {
/* WAR */
- DB((dbg, LEVEL_1, "WAR %+F %+F\n", op->node, other->node));
+ DB((dbg, LEVEL_1, "WAR %+F <- %+F\n", op->node, other->node));
mark_remove_store(op);
} else {
/* we overwrite the value that was loaded */
}
}
}
- dump_curr(bl, "Avail_out");
- if (memcmp(bl->avail_out, env.curr_set, BYTE_SIZE(env.rbs_size)) != 0) {
+
+ /*
+ * Always copy the map as it might get updated.
+ * However, an update is NOT recorded as a change, as the set of available addresses
+ * is not modified.
+ */
+ memcpy(bl->id_2_memop_avail, bl->id_2_memop, env.rbs_size * sizeof(bl->id_2_memop[0]));
+ if (!rbitset_equal(bl->avail_out, env.curr_set, env.rbs_size)) {
/* changed */
- memcpy(bl->avail_out, env.curr_set, env.rbs_size);
+ rbitset_cpy(bl->avail_out, env.curr_set, env.rbs_size);
+ dump_curr(bl, "Avail_out*");
return 1;
}
+ dump_curr(bl, "Avail_out");
return 0;
}
*/
static int backward_antic(block_t *bl) {
memop_t *op;
- ir_node *succ = get_Block_cfg_out(bl->block, 0);
- block_t *succ_bl = get_block_entry(succ);
- int n;
-
- memcpy(env.curr_set, succ_bl->anticL_in, BYTE_SIZE(env.rbs_size));
- memcpy(bl->id_2_memop, succ_bl->id_2_memop, env.rbs_size * sizeof(bl->id_2_memop[0]));
+ int n = get_Block_n_cfg_outs(bl->block);
- n = get_Block_n_cfg_outs(bl->block);
- if (n > 1) {
+ if (n >= 1) {
+ ir_node *succ = get_Block_cfg_out(bl->block, 0);
+ block_t *succ_bl = get_block_entry(succ);
int i;
+ rbitset_cpy(env.curr_set, succ_bl->anticL_in, env.rbs_size);
+ memcpy(bl->id_2_memop, succ_bl->id_2_memop, env.rbs_size * sizeof(bl->id_2_memop[0]));
+
for (i = n - 1; i > 0; --i) {
ir_node *succ = get_Block_cfg_out(bl->block, i);
block_t *succ_bl = get_block_entry(succ);
rbitset_and(env.curr_set, succ_bl->anticL_in, env.rbs_size);
}
+ } else {
+ /* block ends with a noreturn call */
+ kill_all();
}
#if 0
}
}
dump_curr(bl, "AnticL_in");
- if (memcmp(bl->anticL_in, env.curr_set, BYTE_SIZE(env.rbs_size)) != 0) {
+ if (! rbitset_equal(bl->anticL_in, env.curr_set, env.rbs_size)) {
/* changed */
- memcpy(bl->anticL_in, env.curr_set, env.rbs_size);
+ rbitset_cpy(bl->anticL_in, env.curr_set, env.rbs_size);
return 1;
}
return 0;
ir_mode *mode;
if (def != NULL)
- DB((dbg, LEVEL_1, "Replacing %+F by definition %+F\n", load, def));
+ DB((dbg, LEVEL_1, "Replacing %+F by definition %+F\n", load, is_Proj(def) ? get_Proj_pred(def) : def));
else {
if (op->flags & FLAG_EXCEPTION) {
/* bad: this node is unused and executed for exception only */
/* a hidden cast */
dbg_info *db = get_irn_dbg_info(load);
ir_node *block = get_nodes_block(proj);
- def = new_rd_Conv(db, current_ir_graph, block, def, mode);
+ def = new_rd_Conv(db, current_ir_graph, block, def, mode, 0);
}
exchange(proj, def);
break;
++i;
} while (need_iter);
- /* copy the content of the id_2_memop map into the id_2_memop_avail map
- as it must be preserved for later use */
- for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
- memop_t **t = bl->id_2_memop_avail;
-
- bl->id_2_memop_avail = bl->id_2_memop;
- bl->id_2_memop = t;
- }
DB((dbg, LEVEL_2, "Get avail set after %d iterations\n\n", i));
}
}
/**
- * Reroute the memory. Reroute all users of old memory
+ * Reroute all memory users of old memory
* to a new memory IR-node.
*
* @param omem the old memory IR-node
* @param nmem the new memory IR-node
*/
-static void reroute_mem(ir_node *omem, ir_node *nmem) {
+static void reroute_all_mem_users(ir_node *omem, ir_node *nmem) {
int i;
for (i = get_irn_n_outs(omem) - 1; i >= 0; --i) {
int n_pos;
- ir_node *succ = get_irn_out_ex(omem, i, &n_pos);
+ ir_node *user = get_irn_out_ex(omem, i, &n_pos);
- set_irn_n(succ, n_pos, nmem);
+ set_irn_n(user, n_pos, nmem);
}
- /* all edges formally point to omem now point to nmem */
+ /* all edges previously point to omem now point to nmem */
nmem->out = omem->out;
}
+/**
+ * Reroute memory users of old memory that are dominated by a given block
+ * to a new memory IR-node.
+ *
+ * @param omem the old memory IR-node
+ * @param nmem the new memory IR-node
+ * @param pass_bl the block the memory must pass
+ */
+static void reroute_mem_through(ir_node *omem, ir_node *nmem, ir_node *pass_bl) {
+ int i, j, n = get_irn_n_outs(omem);
+ ir_def_use_edge *edges = NEW_ARR_D(ir_def_use_edge, &env.obst, n + 1);
+
+ for (i = j = 0; i < n; ++i) {
+ int n_pos;
+ ir_node *user = get_irn_out_ex(omem, i, &n_pos);
+ ir_node *use_bl = get_nodes_block(user);
+
+
+ if (is_Phi(user)) {
+ use_bl = get_Block_cfgpred_block(use_bl, n_pos);
+ }
+ if (block_dominates(pass_bl, use_bl)) {
+ /* found an user that is dominated */
+ ++j;
+ edges[j].pos = n_pos;
+ edges[j].use = user;
+
+ set_irn_n(user, n_pos, nmem);
+ }
+ }
+
+ /* Modify the out structure: we create a new out edge array on our
+ temporary obstack here. This should be no problem, as we invalidate the edges
+ at the end either. */
+ /* first entry is used for the length */
+ edges[0].pos = j;
+ nmem->out = edges;
+}
+
+
/**
* insert
*/
for (pos = rbitset_next(bl->anticL_in, pos, 1); pos != end; pos = rbitset_next(bl->anticL_in, pos + 1, 1)) {
memop_t *op = bl->id_2_memop[pos];
- int have_some;
+ int have_some, all_same;
+ ir_node *first;
assert(is_Load(op->node));
continue;
have_some = 0;
+ all_same = 1;
+ first = 0;
for (i = n - 1; i >= 0; --i) {
ir_node *pred = get_Block_cfgpred_block(block, i);
block_t *pred_bl = get_block_entry(pred);
break;
}
pred_bl->avail = NULL;
+ all_same = 0;
} else {
pred_bl->avail = e;
have_some = 1;
+ if (first == NULL)
+ first = e->node;
+ else if (first != e->node)
+ all_same = 0;
}
}
- if (have_some) {
+ if (have_some && !all_same) {
ir_mode *mode = op->value.mode;
ir_node **in, *phi;
ir_node *load, *def;
memop_t *new_op;
+ assert(last_mem != NULL);
load = new_rd_Load(db, current_ir_graph, pred, last_mem, op->value.address, mode, cons_none);
def = new_r_Proj(current_ir_graph, pred, load, mode, pn_Load_res);
DB((dbg, LEVEL_1, "Created new %+F for party redundant %+F\n", load, op->node));
new_op->prev = pred_bl->memop_backward;
pred_bl->memop_backward = new_op;
- reroute_mem(last_mem, new_op->mem);
+ if (get_nodes_block(last_mem) == pred) {
+ /* We have add a new last memory op in pred block.
+ If pred had already a last mem, reroute all memory
+ users. */
+ reroute_all_mem_users(last_mem, new_op->mem);
+ } else {
+ /* reroute only those memory going through the pre block */
+ reroute_mem_through(last_mem, new_op->mem, pred);
+ }
/* we added this load at the end, so it will be avail anyway */
add_memop_avail(pred_bl, new_op);
int i, need_iter;
/* calculate antic_out */
- DB((dbg, LEVEL_2, "Inserting Loads"));
+ DB((dbg, LEVEL_2, "Inserting Loads\n"));
i = 0;
do {
DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
/* we need landing pads */
remove_critical_cf_edges(irg);
+ dump_ir_block_graph(irg, "-XXX");
+
if (get_opt_alias_analysis()) {
assure_irg_entity_usage_computed(irg);
assure_irp_globals_entity_usage_computed();
env.n_mem_ops = 0;
env.changed = 0;
env.start_bl = get_irg_start_block(irg);
+ env.end_bl = get_irg_end_block(irg);
assure_doms(irg);
assure_irg_outs(irg);
/* first step: allocate block entries: produces an
inverse post-order list for the CFG */
+ set_irn_link(env.end_bl, NULL);
irg_out_block_walk(get_irg_start_block(irg), NULL, prepare_blocks, NULL);
+ if (get_block_entry(env.end_bl) == NULL) {
+ /*
+ * The end block is NOT reachable due to endless loops
+ * or no_return calls. Ensure that it is initialized.
+ * Note that this places the entry for the end block first, so we must fix this.
+ * env.backwards points to th last block for this purpose.
+ */
+ prepare_blocks(env.end_bl, NULL);
+
+ bl = env.forward;
+ env.forward = bl->forward_next;
+ bl->forward_next = NULL;
+
+ env.backward->forward_next = bl;
+ }
+
/* second step: find and sort all memory ops */
walk_memory_irg(irg, collect_memops, NULL, NULL);
+ if (env.n_mem_ops == 0) {
+ /* no memory ops */
+ goto end;
+ }
+
/* create the backward links */
+ env.backward = NULL;
irg_block_walk_graph(irg, NULL, collect_backward, NULL);
+ /* link the end block in */
+ bl = get_block_entry(env.end_bl);
+ bl->backward_next = env.backward;
+ env.backward = bl;
+
/* check that we really start with the start / end block */
assert(env.forward->block == env.start_bl);
- assert(env.backward->block == get_irg_end_block(irg));
+ assert(env.backward->block == env.end_bl);
/* create address sets: we know that 2 * n_mem_ops - 1 is an upper bound for all possible addresses */
env.rbs_size = 2 * env.n_mem_ops;
do_replacements(bl);
}
- set_irg_outs_inconsistent(irg);
+ /* not only invalidate but free them. We might allocate new out arrays
+ on our obstack which will be deleted yet. */
+ free_irg_outs(irg);
set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
}
+end:
ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
ir_nodemap_destroy(&env.adr_map);
projects / libfirm / blobdiff