X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fgvn_pre.c;h=996eb34a32d9e32227d0b9a1c1f94b1b7a7aac98;hb=b27ae245166bb695bc4e418ff416d91bc37d0f28;hp=90c13b2075fa74e0323b35d58c64c28056297328;hpb=d5dc732caa60b3ccaca0d6f36d6c4ad6e601f92f;p=libfirm diff --git a/ir/opt/gvn_pre.c b/ir/opt/gvn_pre.c index 90c13b207..996eb34a3 100644 --- a/ir/opt/gvn_pre.c +++ b/ir/opt/gvn_pre.c @@ -23,12 +23,11 @@ * (VanDrunen Hosking 2004) * @author Michael Beck * @version $Id$ - * @summary + * @brief */ -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif +#include "config.h" +#include "iroptimize.h" #include "irflag.h" #include "irdom.h" #include "irouts.h" @@ -42,6 +41,7 @@ #include "iredges.h" #include "iropt_dbg.h" #include "debug.h" +#include "irpass.h" #include "irgraph_t.h" #include "irnode_t.h" @@ -54,8 +54,9 @@ typedef struct block_info { ir_valueset_t *antic_in; /**< The Antic_in set for a block. */ ir_valueset_t *new_set; /**< The set of all new values for a block. */ ir_node *avail; /**< The get_map(avail, block) result. */ - int not_found; /**< Non-zero, if avail was not found in this block. */ + ir_node *block; /**< The Block of the block info. */ struct block_info *next; /**< Links all entries, so we can recover the sets easily. */ + int not_found; /**< Non-zero, if avail was not found in this block. */ } block_info; /** @@ -75,14 +76,13 @@ typedef struct pre_env { struct obstack *obst; /**< The obstack to allocate on. */ ir_node *start_block; /**< The start block of the current graph. */ ir_node *end_block; /**< The end block of the current graph */ - block_info *list; /**< Links all block info entires for easier recovery. */ + block_info *list; /**< Links all block info entries for easier recovery. */ elim_pair *pairs; /**< A list of node pairs that must be eliminated. */ unsigned last_idx; /**< last node index of "old" nodes, all higher indexes are newly created once. */ char changes; /**< Non-zero, if calculation of Antic_in has changed. */ char first_iter; /**< non-zero for first iteration */ } pre_env; -static pset *value_table; static ir_nodemap_t value_map; /** The debug module handle. */ @@ -116,14 +116,14 @@ static ir_node *add(ir_node *e, ir_node *v) { if (is_Proj(v)) { ir_node *pred = get_Proj_pred(v); - ir_node *v_pred = identify_remember(value_table, pred); + ir_node *v_pred = identify_remember(pred); if (v_pred != pred) { /* must create a new value here */ - v = new_r_Proj(current_ir_graph, get_nodes_block(v_pred), v_pred, get_irn_mode(v), get_Proj_proj(v)); + v = new_r_Proj(v_pred, get_irn_mode(v), get_Proj_proj(v)); } } - v = identify_remember(value_table, v); + v = identify_remember(v); ir_nodemap_insert(&value_map, e, v); return v; } /* add */ @@ -138,20 +138,21 @@ static ir_node *add(ir_node *e, ir_node *v) */ static ir_node *lookup(ir_node *e) { - ir_node *value = ir_nodemap_get(&value_map, e); + ir_node *value = (ir_node*)ir_nodemap_get(&value_map, e); if (value != NULL) - return identify_remember(value_table, value); + return identify_remember(value); return NULL; -} /* lookup */ +} /** * Return the block info of a block. * * @param block the block */ -static block_info *get_block_info(ir_node *block) { - return get_irn_link(block); -} /* get_block_info */ +static block_info *get_block_info(ir_node *block) +{ + return (block_info*)get_irn_link(block); +} /** * Allocate a block info for a block. @@ -159,8 +160,9 @@ static block_info *get_block_info(ir_node *block) { * @param block the block * @param env the environment */ -static void alloc_blk_info(ir_node *block, pre_env *env) { - block_info *info = obstack_alloc(env->obst, sizeof(*info)); +static void alloc_blk_info(ir_node *block, pre_env *env) +{ + block_info *info = OALLOC(env->obst, block_info); set_irn_link(block, info); info->exp_gen = ir_valueset_new(16); @@ -168,9 +170,10 @@ static void alloc_blk_info(ir_node *block, pre_env *env) { info->antic_in = ir_valueset_new(16); info->new_set = NULL; info->avail = NULL; - info->not_found = 0; + info->block = block; info->next = env->list; env->list = info; + info->not_found = 0; } /* alloc_blk_info */ /** @@ -178,7 +181,8 @@ static void alloc_blk_info(ir_node *block, pre_env *env) { * * @param n the node */ -static int is_nice_value(ir_node *n) { +static int is_nice_value(ir_node *n) +{ ir_mode *mode; while (is_Proj(n)) @@ -187,7 +191,7 @@ static int is_nice_value(ir_node *n) { return 0; mode = get_irn_mode(n); if (!mode_is_data(mode)) { - if (! is_Div(n) && ! is_Mod(n) && ! is_DivMod(n)) + if (! is_Div(n) && ! is_Mod(n)) return 0; if (! is_NoMem(get_fragile_op_mem(n))) return 0; @@ -203,7 +207,8 @@ static int is_nice_value(ir_node *n) { * @param txt a text to describe the set * @param block the owner block of the set */ -static void dump_value_set(ir_valueset_t *set, char *txt, ir_node *block) { +static void dump_value_set(ir_valueset_t *set, const char *txt, ir_node *block) +{ ir_valueset_iterator_t iter; ir_node *value, *expr; int i; @@ -227,11 +232,12 @@ static void dump_value_set(ir_valueset_t *set, char *txt, ir_node *block) { #endif /* DEBUG_libfirm */ /** - * Topological walker. Allocates block info for every block and place nodes in topological - * order into the nodes set. + * Topological walker. Allocates block info for every block and place nodes in + * topological order into the nodes set. */ -static void topo_walker(ir_node *irn, void *ctx) { - pre_env *env = ctx; +static void topo_walker(ir_node *irn, void *ctx) +{ + pre_env *env = (pre_env*)ctx; ir_node *block; block_info *info; ir_node *value; @@ -258,7 +264,7 @@ static void topo_walker(ir_node *irn, void *ctx) { info = get_block_info(block); ir_valueset_insert(info->exp_gen, value, irn); -} /* topo_walker */ +} /** * Computes Avail_out(block): @@ -275,7 +281,7 @@ static void topo_walker(ir_node *irn, void *ctx) { */ static void compute_avail_top_down(ir_node *block, void *ctx) { - pre_env *env = ctx; + pre_env *env = (pre_env*)ctx; block_info *dom_info; block_info *info = get_block_info(block); ir_node *dom_blk; @@ -301,64 +307,61 @@ static void compute_avail_top_down(ir_node *block, void *ctx) value_union(info->avail_out, info->exp_gen); dump_value_set(info->avail_out, "Avail_out", block); -} /* compute_avail_top_down */ +} /** * check if a node n is clean in block block. * * @param n the node * @param block the block + * @param set a value set, containing the already processed predecessors */ -static int _is_clean(ir_node *n, ir_node *block) +static int is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *set) { int i; - if (get_nodes_block(n) != block) - return 1; if (is_Phi(n)) return 1; - if (irn_visited(n)) + if (! is_nice_value(n)) return 0; - if (! is_nice_value(n)) - goto bad; for (i = get_irn_arity(n) - 1; i >= 0; --i) { ir_node *pred = get_irn_n(n, i); - if (! _is_clean(pred, block)) - goto bad; + ir_node *value; + + if (get_nodes_block(pred) != block) + continue; + + if (is_Phi(pred)) + continue; + + if (! is_nice_value(pred)) + return 0; + + value = lookup(pred); + if (! value) + return 0; + if (! ir_valueset_lookup(set, value)) + return 0; } return 1; -bad: - mark_irn_visited(n); - return 0; -} /* _is_clean */ - -/** - * check if a node n is clean. - * - * @param n the node to check - */ -static int is_clean(ir_node *n) { - int res = _is_clean(n, get_nodes_block(n)); - return res; -} /* is_clean */ +} /* is_clean_in_block */ /** * Implements phi_translate. Translate a expression above a Phi. * - * @param node the node - * @param block the block in which the node is translated - * @param pos the input number of the destination block - * @param env the environment + * @param node the node + * @param block the block in which the node is translated + * @param pos the input number of the destination block + * @param translated the valueset containing the other already translated nodes * * @return a node representing the translated value */ -static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env) +static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *translated) { - ir_node *nn; - int i, arity; - struct obstack *old; + ir_node *nn; + int i, arity; if (is_Phi(node)) { if (get_nodes_block(node) == block) { @@ -369,51 +372,53 @@ static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *e return node; } - arity = get_irn_intra_arity(node); + arity = get_irn_arity(node); /* check if the node has at least one Phi predecessor */ for (i = 0; i < arity; ++i) { - ir_node *pred = get_irn_intra_n(node, i); + ir_node *pred = get_irn_n(node, i); ir_node *leader = lookup(pred); + ir_node *trans; leader = leader != NULL ? leader : pred; - if (is_Phi(leader) && get_nodes_block(pred) == block) + trans = (ir_node*)ir_valueset_lookup(translated, leader); + + if ((trans != NULL && trans != leader) || (is_Phi(leader) && get_nodes_block(leader) == block)) break; } if (i >= arity) { - /* no Phi in the predecessors */ + /* no translation needed */ return node; } - /* Create a copy of the node in the pos'th predecessor block. - Use our environmental obstack, as these nodes are always - temporary. */ - old = current_ir_graph->obst; - current_ir_graph->obst = env->obst; nn = new_ir_node( get_irn_dbg_info(node), current_ir_graph, - NULL, + get_nodes_block(node), get_irn_op(node), get_irn_mode(node), arity, get_irn_in(node)); /* We need the attribute copy here, because the Hash value of a node might depend on that. */ - copy_node_attr(node, nn); + copy_node_attr(current_ir_graph, node, nn); - set_nodes_block(nn, get_nodes_block(node)); for (i = 0; i < arity; ++i) { - ir_node *pred = get_irn_intra_n(node, i); + ir_node *pred = get_irn_n(node, i); ir_node *leader = lookup(pred); + ir_node *trans; leader = leader != NULL ? leader : pred; - if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block) - set_irn_n(nn, i, get_Phi_pred(leader, pos)); + trans = (ir_node*)ir_valueset_lookup(translated, leader); + if (trans == NULL) + trans = leader; + + if (is_Phi(trans) && get_nodes_block(trans) == block) + set_irn_n(nn, i, get_Phi_pred(trans, pos)); else - set_irn_n(nn, i, leader); + set_irn_n(nn, i, trans); } - current_ir_graph->obst = old; + nn = optimize_node(nn); return nn; } /* phi_translate */ @@ -423,8 +428,9 @@ static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *e * @param block the block * @param ctx the walker environment */ -static void compute_antic(ir_node *block, void *ctx) { - pre_env *env = ctx; +static void compute_antic(ir_node *block, void *ctx) +{ + pre_env *env = (pre_env*)ctx; block_info *succ_info; block_info *info = get_block_info(block); ir_node *succ, *value, *expr; @@ -455,25 +461,20 @@ static void compute_antic(ir_node *block, void *ctx) { n_succ = get_Block_n_cfg_outs(block); if (n_succ == 1) { - int i, pos = -1; + int pos = -1; /* find blocks position in succ's block predecessors */ succ = get_Block_cfg_out(block, 0); - for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) { - if (get_Block_cfgpred_block(succ, i) == block) { - pos = i; - break; - } - } + pos = get_Block_cfgpred_pos(succ, block); assert(pos >= 0); succ_info = get_block_info(succ); /* translate into list: we cannot insert into a set we iterate * and succ might be equal to block for endless loops */ foreach_valueset(succ_info->antic_in, value, expr, iter) { - ir_node *trans = phi_translate(expr, succ, pos, env); + ir_node *trans = phi_translate(expr, succ, pos, info->antic_in); - if (is_clean(trans)) + if (is_clean_in_block(trans, block, info->antic_in)) ir_valueset_insert(info->antic_in, value, trans); } } else { /* n_succ > 1 */ @@ -500,7 +501,8 @@ static void compute_antic(ir_node *block, void *ctx) { if (i >= n_succ) { /* we found a value that is common in all Antic_in(succ(b)), put it in Antic_in(b) if the value is NOT already represented. */ - ir_valueset_insert(info->antic_in, value, expr); + if (is_clean_in_block(expr, block, info->antic_in)) + ir_valueset_insert(info->antic_in, value, expr); } } } @@ -534,10 +536,10 @@ static void compute_antic(ir_node *block, void *ctx) { */ static void insert_nodes(ir_node *block, void *ctx) { - pre_env *env = ctx; + pre_env *env = (pre_env*)ctx; ir_node *value, *expr, *idom, *first_s, *worklist; block_info *curr_info, *idom_info; - int pos, arity = get_irn_intra_arity(block); + int pos, arity = get_irn_arity(block); int all_same, by_some, updated; ir_valueset_iterator_t iter; @@ -595,13 +597,13 @@ static void insert_nodes(ir_node *block, void *ctx) if (is_Bad(pred_blk)) continue; - e_prime = phi_translate(expr, block, pos, env); + e_prime = phi_translate(expr, block, pos, curr_info->avail_out); v_prime = lookup(e_prime); if (v_prime == NULL) v_prime = value; pred_info = get_block_info(pred_blk); - e_dprime = ir_valueset_lookup(pred_info->avail_out, v_prime); + e_dprime = (ir_node*)ir_valueset_lookup(pred_info->avail_out, v_prime); if (e_dprime == NULL) { pred_info->avail = e_prime; @@ -625,11 +627,11 @@ static void insert_nodes(ir_node *block, void *ctx) /* If it's not the same value already existing along every predecessor, and it's defined by some predecessor, it is partially redundant. */ if (! all_same && by_some) { - ir_node *phi, **in; + ir_node *phi, *l, **in; DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", expr, block)); - in = xmalloc(arity * sizeof(*in)); + in = XMALLOCN(ir_node*, arity); /* for all predecessor blocks */ for (pos = 0; pos < arity; ++pos) { ir_node *pred_blk = get_Block_cfgpred_block(block, pos); @@ -637,7 +639,8 @@ static void insert_nodes(ir_node *block, void *ctx) /* ignore bad blocks. */ if (is_Bad(pred_blk)) { - in[pos] = new_Bad(); + ir_graph *irg = get_irn_irg(pred_blk); + in[pos] = new_r_Bad(irg, mode_X); continue; } @@ -657,9 +660,9 @@ static void insert_nodes(ir_node *block, void *ctx) mode, get_irn_arity(pred), get_irn_in(pred) + 1); - copy_node_attr(pred, nn); + copy_node_attr(current_ir_graph, pred, nn); - DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk)); + DB((dbg, LEVEL_1, "New node %+F in block %+F created\n", nn, pred_blk)); proj_pred = nn; } mode = get_irn_mode(e_prime); @@ -670,24 +673,32 @@ static void insert_nodes(ir_node *block, void *ctx) mode, get_irn_arity(e_prime), get_irn_in(e_prime) + 1); - copy_node_attr(e_prime, nn); + copy_node_attr(current_ir_graph, e_prime, nn); if (proj_pred != NULL) { set_Proj_pred(nn, proj_pred); } - DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk)); - ir_valueset_insert(pred_info->avail_out, add(nn, lookup(expr)), nn); + DB((dbg, LEVEL_1, "New node %+F in block %+F created\n", nn, pred_blk)); + l = lookup(expr); + if (l == NULL) { + l = add(expr, value); + } + ir_valueset_insert(pred_info->avail_out, add(nn, l), nn); pred_info->avail = nn; } } in[pos] = pred_info->avail; } /* for */ - phi = new_r_Phi(current_ir_graph, block, arity, in, mode); - value = add(phi, lookup(expr)); + phi = new_r_Phi(block, arity, in, mode); + l = lookup(expr); + if (l == NULL) { + l = add(expr, value); + } + value = add(phi, l); ir_valueset_replace(curr_info->avail_out, value, phi); ir_valueset_insert(curr_info->new_set, value, phi); free(in); - DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, expr)); + DB((dbg, LEVEL_1, "New %+F for redundant %+F created\n", phi, expr)); ir_valueset_remove_iterator(curr_info->antic_in, &iter); env->changes |= 1; } /* if */ @@ -703,19 +714,20 @@ static void insert_nodes(ir_node *block, void *ctx) * @param irn the node * @param ctx the walker environment */ -static void eliminate(ir_node *irn, void *ctx) { - pre_env *env = ctx; +static void eliminate(ir_node *irn, void *ctx) +{ + pre_env *env = (pre_env*)ctx; - if (is_no_Block(irn)) { + if (!is_Block(irn)) { ir_node *block = get_nodes_block(irn); block_info *bl = get_block_info(block); ir_node *value = lookup(irn); if (value != NULL) { - ir_node *expr = ir_valueset_lookup(bl->avail_out, value); + ir_node *expr = (ir_node*)ir_valueset_lookup(bl->avail_out, value); if (expr != NULL && expr != irn) { - elim_pair *p = obstack_alloc(env->obst, sizeof(*p)); + elim_pair *p = OALLOC(env->obst, elim_pair); p->old_node = irn; p->new_node = expr; @@ -733,10 +745,14 @@ static void eliminate(ir_node *irn, void *ctx) { * * @param pairs list of elimination pairs */ -static void eliminate_nodes(elim_pair *pairs) { +static void eliminate_nodes(elim_pair *pairs) +{ elim_pair *p; for (p = pairs; p != NULL; p = p->next) { + /* might be already changed */ + p->new_node = skip_Id(p->new_node); + DB((dbg, LEVEL_2, "Replacing %+F by %+F\n", p->old_node, p->new_node)); /* * PRE tends to create Phi(self, self, ... , x, self, self, ...) @@ -746,7 +762,7 @@ static void eliminate_nodes(elim_pair *pairs) { int i; ir_node *res = NULL; - for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) { + for (i = get_irn_arity(p->new_node) - 1; i >= 0; --i) { ir_node *pred = get_irn_n(p->new_node, i); if (pred != p->old_node) { @@ -757,8 +773,10 @@ static void eliminate_nodes(elim_pair *pairs) { res = pred; } } - if (res) + if (res) { + exchange(p->new_node, res); p->new_node = res; + } } DBG_OPT_GVN_PRE(p->old_node, p->new_node, p->reason); exchange(p->old_node, p->new_node); @@ -771,7 +789,7 @@ static void eliminate_nodes(elim_pair *pairs) { * references the origin. These nodes are translated again and again... * * The current fix is to use post-dominance. This simple ignores - * endless loops, ie we cannot optimize them. + * endless loops, i.e. we cannot optimize them. */ void do_gvn_pre(ir_graph *irg) { @@ -788,7 +806,7 @@ void do_gvn_pre(ir_graph *irg) /* edges will crash if enabled due to our allocate on other obstack trick */ edges_deactivate(irg); - value_table = new_identities(); + new_identities(irg); ir_nodemap_init(&value_map); obstack_init(&obst); @@ -798,10 +816,6 @@ void do_gvn_pre(ir_graph *irg) a_env.end_block = get_irg_end_block(irg); a_env.pairs = NULL; - /* Move Proj's into the same block as their args, - else we would assign the result to wrong blocks */ - normalize_proj_nodes(irg); - /* critical edges MUST be removed */ remove_critical_cf_edges(irg); @@ -813,26 +827,26 @@ void do_gvn_pre(ir_graph *irg) /* * Switch on GCSE. We need it to correctly compute - * the leader of a node by hashing. + * the value of a node, which is independent from + * its block. */ save_optimization_state(&state); set_opt_global_cse(1); - DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg))); + DB((dbg, LEVEL_1, "Doing GVN-PRE for %+F\n", irg)); /* allocate block info for all blocks */ - irg_walk_blkwise_graph(irg, NULL, topo_walker, &a_env); + irg_walk_blkwise_dom_top_down(irg, NULL, topo_walker, &a_env); /* clean the exp_gen set. Doing this here saves the cleanup in the iteration. */ for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) { ir_valueset_iterator_t iter; foreach_valueset(bl_info->exp_gen, value, expr, iter) { - if (!is_clean(expr)) + if (!is_clean_in_block(expr, bl_info->block, bl_info->exp_gen)) ir_valueset_remove_iterator(bl_info->exp_gen, &iter); } } - /* compute the available value sets for all blocks */ dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env); @@ -872,18 +886,16 @@ void do_gvn_pre(ir_graph *irg) if (bl_info->new_set) ir_valueset_del(bl_info->new_set); } - del_identities(value_table); ir_nodemap_destroy(&value_map); obstack_free(&obst, NULL); - value_table = NULL; /* pin the graph again: This is needed due to the use of set_opt_global_cse(1) */ set_irg_pinned(irg, op_pin_state_pinned); restore_optimization_state(&state); - - if (a_env.pairs) { - set_irg_outs_inconsistent(irg); - set_irg_loopinfo_inconsistent(irg); - - } } /* do_gvn_pre */ + +/* Creates an ir_graph pass for do_gvn_pre. */ +ir_graph_pass_t *do_gvn_pre_pass(const char *name) +{ + return def_graph_pass(name ? name : "gvn_pre", do_gvn_pre); +} /* do_gvn_pre_pass */