X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_ldst.c;h=c74ecc71fa10abf2086292c849c46cb06b85bca3;hb=289ebf2e44ddfe5e564f9b5b1467de47f5078b97;hp=d1f9b6ef8eb1fe33f954fca2f7d2c28183ddca80;hpb=1cf669f14fb238c8cdcfe187714ff2f6579a784c;p=libfirm diff --git a/ir/opt/opt_ldst.c b/ir/opt/opt_ldst.c index d1f9b6ef8..c74ecc71f 100644 --- a/ir/opt/opt_ldst.c +++ b/ir/opt/opt_ldst.c @@ -42,7 +42,7 @@ #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 */ @@ -106,8 +106,6 @@ struct block_t { memop_t *avail; /**< used locally for the avail map */ }; -#define get_block_entry(block) ((block_t *)get_irn_link(block)) - /** * Metadata for this pass. */ @@ -117,6 +115,7 @@ typedef struct ldst_env_t { 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) */ @@ -193,6 +192,19 @@ static void dump_curr(block_t *bl, const char *s) { #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. * @@ -275,7 +287,9 @@ static void prepare_blocks(ir_node *block, void *ctx) { 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; } /** @@ -285,11 +299,19 @@ static void collect_backward(ir_node *block, void *ctx) { 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; @@ -317,6 +339,7 @@ static memop_t *alloc_memop(ir_node *irn) { m->next = NULL; m->flags = 0; + set_irn_link(irn, m); return m; } @@ -326,7 +349,20 @@ static memop_t *alloc_memop(ir_node *irn) { * @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 */ @@ -381,6 +417,10 @@ static void update_Load_memop(memop_t *m) { 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; @@ -428,6 +468,10 @@ static void update_Store_memop(memop_t *m) { 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; @@ -463,6 +507,10 @@ static void update_Call_memop(memop_t *m) { 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; @@ -486,6 +534,10 @@ static void update_DivOp_memop(memop_t *m) { 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; @@ -497,6 +549,16 @@ static void update_DivOp_memop(memop_t *m) { } } +/** + * 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. */ @@ -517,6 +579,7 @@ static void collect_memops(ir_node *irn, void *ctx) { 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; @@ -724,21 +787,29 @@ static void add_memop_avail(block_t *bl, memop_t *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); @@ -746,24 +817,73 @@ static ir_node *find_definition(ir_node *block, const value_t *value) { 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 * @@ -801,7 +921,7 @@ static int forward_avail(block_t *bl) { 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) { @@ -809,11 +929,19 @@ static int forward_avail(block_t *bl) { /* 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) { @@ -851,15 +979,22 @@ static int forward_avail(block_t *bl) { /* 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); @@ -872,14 +1007,19 @@ static int forward_avail(block_t *bl) { /* 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 */ @@ -908,12 +1048,20 @@ static int forward_avail(block_t *bl) { } } } - 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; } @@ -927,23 +1075,25 @@ static int forward_avail(block_t *bl) { */ 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 @@ -997,9 +1147,9 @@ static int backward_antic(block_t *bl) { } } 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; @@ -1017,7 +1167,7 @@ static void replace_load(memop_t *op) { 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 */ @@ -1039,7 +1189,7 @@ static void replace_load(memop_t *op) { /* 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; @@ -1129,14 +1279,6 @@ static void calcAvail(void) { ++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)); } @@ -1196,26 +1338,66 @@ static ir_node *find_last_memory(block_t *bl) { } /** - * 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 */ @@ -1233,7 +1415,8 @@ static void insert_Load(ir_node *block, void *ctx) { 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)); @@ -1241,6 +1424,8 @@ static void insert_Load(ir_node *block, void *ctx) { 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); @@ -1254,12 +1439,17 @@ static void insert_Load(ir_node *block, void *ctx) { 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; @@ -1276,6 +1466,7 @@ static void insert_Load(ir_node *block, void *ctx) { 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)); @@ -1290,7 +1481,15 @@ static void insert_Load(ir_node *block, void *ctx) { 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); @@ -1328,7 +1527,7 @@ static void insert_Loads_upwards(void) { 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)); @@ -1353,6 +1552,8 @@ int opt_ldst(ir_graph *irg) { /* 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(); @@ -1367,6 +1568,7 @@ int opt_ldst(ir_graph *irg) { 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); @@ -1375,17 +1577,45 @@ int opt_ldst(ir_graph *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; @@ -1422,9 +1652,12 @@ int opt_ldst(ir_graph *irg) { 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);