X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_ldst.c;h=c74ecc71fa10abf2086292c849c46cb06b85bca3;hb=289ebf2e44ddfe5e564f9b5b1467de47f5078b97;hp=64c701b82bd2e0f0937dea188794b542f567c179;hpb=ebddb7c8263778f56eff6765fbfe2ed437aba7f1;p=libfirm diff --git a/ir/opt/opt_ldst.c b/ir/opt/opt_ldst.c index 64c701b82..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; @@ -735,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); @@ -757,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 * @@ -820,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) { @@ -862,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); @@ -883,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 */ @@ -919,12 +1048,20 @@ static int forward_avail(block_t *bl) { } } } - dump_curr(bl, "Avail_out"); + + /* + * 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 */ 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; } @@ -938,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; - - 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])); + 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 @@ -1050,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; @@ -1140,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)); } @@ -1284,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)); @@ -1292,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); @@ -1305,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; @@ -1388,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)); @@ -1413,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(); @@ -1427,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); @@ -1435,8 +1577,25 @@ 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); @@ -1446,11 +1605,17 @@ int opt_ldst(ir_graph *irg) { } /* 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;