X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fgvn_pre.c;h=b3e09c691cded2061f61210785e7861b902c2003;hb=74c0b452c2665b803968a21b556ae2be4a270737;hp=87b072521187e734c23c2f1424871395ffa4e98f;hpb=1ce363f80e6a204d4011f85813362d9bd1d0e7e4;p=libfirm diff --git a/ir/opt/gvn_pre.c b/ir/opt/gvn_pre.c index 87b072521..b3e09c691 100644 --- a/ir/opt/gvn_pre.c +++ b/ir/opt/gvn_pre.c @@ -21,61 +21,42 @@ * @file * @brief Global Value Numbering Partial Redundancy Elimination * (VanDrunen Hosking 2004) - * @author Michael Beck, Rubino Geiss + * @author Michael Beck * @version $Id$ - * @summary - * - * Currently completely broken because our sets do NOT preserve - * the topological sort! + * @brief */ -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif +#include "config.h" #include "iroptimize.h" - -#include - -#include "irgraph_t.h" -#include "irgwalk.h" +#include "irflag.h" #include "irdom.h" #include "irouts.h" -#include "pset.h" -#include "set.h" #include "irgopt.h" -#include "iropt_t.h" -#include "irprintf.h" -#include "irnode_t.h" +#include "irgwalk.h" #include "ircons.h" #include "irgmod.h" +#include "valueset.h" +#include "irnodemap.h" +#include "irnodeset.h" +#include "iredges.h" +#include "iropt_dbg.h" #include "debug.h" -#include "xmalloc.h" - -/** The debug module handle. */ -DEBUG_ONLY(static firm_dbg_module_t *dbg;) +#include "irpass.h" - -/** A value set. */ -typedef struct set value_set; - -/** A node set. */ -typedef struct pset node_set; - -/** An entry in the value set. */ -typedef struct value_entry { - ir_node *node; /**< the node */ - ir_node *value; /**< the value of the node */ -} value_entry; +#include "irgraph_t.h" +#include "irnode_t.h" +#include "iropt_t.h" /** Additional info we need for every block. */ typedef struct block_info { - node_set *nodes; /**< The set of nodes per block. */ - value_set *avail_out; /**< The Avail_out set for a block. */ - node_set *antic_in; /**< The Antic_in set for a block. */ - value_set *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. */ - struct block_info *next; /**< Links all entries, so we can recover the sets easily. */ + ir_valueset_t *exp_gen; /**< The set of expression per block. */ + ir_valueset_t *avail_out; /**< The Avail_out set for a block. */ + 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. */ + 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; /** @@ -84,251 +65,206 @@ typedef struct block_info { * find an already replace node else. */ typedef struct elim_pair { - ir_node *old_node; /**< The old node that will be replaced. */ - ir_node *new_node; /**< The new node. */ - struct elim_pair *next; /**< Links all entries in a list. */ + ir_node *old_node; /**< The old node that will be replaced. */ + ir_node *new_node; /**< The new node. */ + struct elim_pair *next; /**< Links all entries in a list. */ + int reason; /**< The reason for the replacement. */ } elim_pair; /** The environment for the GVN-PRE algorithm */ typedef struct pre_env { - struct obstack *obst; /**< The obstack to allocate on. */ - node_set *trans_set; /**< The set of all translated values. */ - 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. */ - elim_pair *pairs; /**< A list of node pairs that must be eliminated. */ - char changes; /**< Non-zero, if calculation of Antic_in has changed. */ - char first_iter; /**< non-zero for first iteration */ + 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 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; -/* ---------- Functions for Node sets ---------- */ - -#define node_set_first(s) pset_first(s) -#define node_set_next(s) pset_next(s) -#define node_set_break(s) pset_break(s) -#define node_set_foreach(v, s) for ((v) = node_set_first(s); (v); (v) = node_set_next(s)) - -/** - * Creates a new node set. - */ -static node_set *new_node_set(void) { - return new_pset(identities_cmp, 8); -} - -/** - * Deletes a node set. - */ -static void del_node_set(node_set *set) { - del_pset(set); -} - -/** - * Add a node to the set. - */ -static ir_node *node_add(node_set *set, ir_node *node) { - return identify_remember(set, node); -} - -/** - * Remove a node from a node set. - */ -static void node_set_remove(node_set *set, ir_node *node) { - pset_remove(set, node, ir_node_hash(node)); -} - -/** - * Return the number of entries in a node set. - */ -static int node_set_count(node_set *set) { - return pset_count(set); -} - -#if 0 -/** computes dst = dst \/ src for node sets */ -static void node_union(node_set *dst, node_set *src) -{ - ir_node *entry; - node_set_foreach(entry, src) { - node_add(dst, entry); - } -} -#endif - -/** - * Lookup a node in a node set. - */ -static ir_node *node_lookup(node_set *set, ir_node *n) -{ - return pset_find(set, n, ir_node_hash(n)); -} +static ir_nodemap_t value_map; +/** The debug module handle. */ +DEBUG_ONLY(static firm_dbg_module_t *dbg;) /* ---------- Functions for Value sets ---------- */ -#define value_set_foreach(v, s) for ((v) = set_first(s); (v); (v) = set_next(s)) - -/** - * calculate a hash value for a value represented by a node - */ -static unsigned value_hash(ir_node *value) { - return ir_node_hash(value); -} - -/** - * Compare two value entries. - */ -static int value_cmp(const void *elt, const void *key, size_t size) +/** computes dst = dst \/ src for value sets */ +static void value_union(ir_valueset_t *dst, ir_valueset_t *src) { - const value_entry *e1 = elt; - const value_entry *e2 = key; - (void) size; + ir_valueset_iterator_t iter; + ir_node *value, *expr; - return identities_cmp(e1->value, e2->value); + foreach_valueset(src, value, expr, iter) { + ir_valueset_insert(dst, value, expr); + } } -/** Create a new value set. */ -static value_set *new_value_set(void) { - return new_set(value_cmp, 8); -} -/** Deletes a value set. */ -static void del_value_set(value_set *set) { - del_set(set); -} +/* ---------- Functions for Values ---------- */ /** - * Add a node node representing the value value to the set. + * Add a node e representing the value v to the set. + * + * @param e a node representing an expression + * @param v a node representing a value + * + * @return the final value for the expression e */ -static value_entry *value_add(value_set *set, ir_node *node, ir_node *value) +static ir_node *add(ir_node *e, ir_node *v) { - value_entry key; - key.node = node; - key.value = value; - return set_insert(set, &key, sizeof(key), value_hash(value)); -} - -/** computes dst = dst \/ src for value sets */ -static void value_union(value_set *dst, value_set *src) -{ - value_entry *entry; - value_set_foreach(entry, src) - value_add(dst, entry->node, entry->value); -} - -/** computes dst = dst \/ (value_set)src for value sets */ -static void value_union_nodes(value_set *dst, node_set *src) -{ - ir_node *n; - node_set_foreach(n, src) - value_add(dst, n, n); -} + if (is_Proj(v)) { + ir_node *pred = get_Proj_pred(v); + ir_node *v_pred = identify_remember(pred); + + if (v_pred != pred) { + /* must create a new value here */ + v = new_r_Proj(v_pred, get_irn_mode(v), get_Proj_proj(v)); + } + } + v = identify_remember(v); + ir_nodemap_insert(&value_map, e, v); + return v; +} /* add */ /** * Lookup a value in a value set. + * + * @param e a node representing an expression + * + * @return a node representing the value or NULL if + * the given expression is not available */ -static ir_node *value_lookup(value_set *value_set, ir_node *n) +static ir_node *lookup(ir_node *e) { - value_entry key, *e; - - key.value = n; - e = set_find(value_set, &key, sizeof(key), value_hash(n)); - return e ? e->node : NULL; -} + ir_node *value = ir_nodemap_get(&value_map, e); + if (value != NULL) + return identify_remember(value); + return NULL; +} /* lookup */ /** - * Add or replace a value in a set by an node computing the same - * value in a dominator block. + * Return the block info of a block. * - * @return non-zero if a replacement took place + * @param block the block */ -static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value) +static block_info *get_block_info(ir_node *block) { - value_entry *e = value_add(set, node, value); - - if (e->node != node) { - /* node must dominate old one here */ - assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node))); - - e->node = node; - return 1; - } - return 0; -} + return get_irn_link(block); +} /* get_block_info */ /** - * Returns non-zero if a node is movable. + * Allocate a block info for a block. + * + * @param block the block + * @param env the environment */ -static int is_nice_value(ir_node *n) { - ir_mode *mode; - - while (is_Proj(n)) - n = get_Proj_pred(n); - mode = get_irn_mode(n); - /* - * FIXME: For now, we cannot handle Div/even if it's movable. - * That should be fixed. - */ - if (!mode_is_data(mode)) - return 0; - if (is_irn_constlike(n)) - return 0; - return (get_irn_pinned(n) != op_pin_state_pinned); -} +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); + info->avail_out = ir_valueset_new(16); + info->antic_in = ir_valueset_new(16); + info->new_set = NULL; + info->avail = NULL; + info->block = block; + info->next = env->list; + env->list = info; + info->not_found = 0; +} /* alloc_blk_info */ -#ifdef DEBUG_libfirm /** - * Dump a set. + * Returns non-zero if a node is movable and a possible candidate for PRE. + * + * @param n the node */ -static void dump_node_set(node_set *set, char *txt, ir_node *block) +static int is_nice_value(ir_node *n) { - ir_node *n; - int i; - - DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block)); - i = 0; - node_set_foreach(n, set) { - if ((i & 3) == 3) - DB((dbg, LEVEL_2, "\n")); - DB((dbg, LEVEL_2, " %+F,", n)); - ++i; - } - DB((dbg, LEVEL_2, "\n}\n")); -} /* dump_set */ + ir_mode *mode; + + while (is_Proj(n)) + n = get_Proj_pred(n); + if (get_irn_pinned(n) == op_pin_state_pinned) + return 0; + mode = get_irn_mode(n); + if (!mode_is_data(mode)) { + if (! is_Div(n) && ! is_Mod(n) && ! is_DivMod(n)) + return 0; + if (! is_NoMem(get_fragile_op_mem(n))) + return 0; + } + return 1; +} /* is_nice_value */ +#ifdef DEBUG_libfirm /** * Dump a value set. + * + * @param set the set to dump + * @param txt a text to describe the set + * @param block the owner block of the set */ -static void dump_value_set(value_set *set, char *txt, ir_node *block) +static void dump_value_set(ir_valueset_t *set, char *txt, ir_node *block) { - value_entry *e; - int i; - - DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block)); - i = 0; - value_set_foreach(e, set) { - if ((i & 3) == 3) - DB((dbg, LEVEL_2, "\n")); - if (e->node != e->value) - DB((dbg, LEVEL_2, " %+F(%+F),", e->node, e->value)); - else - DB((dbg, LEVEL_2, " %+F,", e->node)); - ++i; - } - DB((dbg, LEVEL_2, "\n}\n")); -} /* dump_set */ + ir_valueset_iterator_t iter; + ir_node *value, *expr; + int i; + + DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block)); + i = 0; + foreach_valueset(set, value, expr, iter) { + if ((i & 3) == 3) + DB((dbg, LEVEL_2, "\n")); + if (value != expr) + DB((dbg, LEVEL_2, " %+F(%+F),", expr, value)); + else + DB((dbg, LEVEL_2, " %+F,", expr)); + ++i; + } + DB((dbg, LEVEL_2, "\n}\n")); +} /* dump_value_set */ #else -#define dump_node_set(set, txt, block) #define dump_value_set(set, txt, block) #endif /* DEBUG_libfirm */ - /** - * Return the block info of a block + * Topological walker. Allocates block info for every block and place nodes in topological + * order into the nodes set. */ -static block_info *get_block_info(ir_node *block) { - return get_irn_link(block); -} +static void topo_walker(ir_node *irn, void *ctx) +{ + pre_env *env = ctx; + ir_node *block; + block_info *info; + ir_node *value; + + if (is_Block(irn)) { + /* the topological walker ensures that blocks are visited before anything else */ + alloc_blk_info(irn, env); + return; + } + /* GVN step: remember the value */ + value = add(irn, irn); + + /* no need to put constants into the sets: they are always redundant */ + if (! is_nice_value(irn) || is_irn_constlike(irn)) + return; + + /* Do not put mode_T nodes info the sets, or PhiT will be created + (which are not allowed in Firm). Instead, put the Proj's here only. */ + if (get_irn_mode(irn) == mode_T) + return; + + /* place this node into the set of possible nodes of its block */ + block = get_nodes_block(irn); + info = get_block_info(block); + + ir_valueset_insert(info->exp_gen, value, irn); +} /* topo_walker */ /** * Computes Avail_out(block): @@ -339,421 +275,248 @@ static block_info *get_block_info(ir_node *block) { * Precondition: * This function must be called in the top-down dominance order: * Then, it computes Leader(Nodes(block)) instead of Nodes(block) ! + * + * @param block the block + * @param ctx walker context */ static void compute_avail_top_down(ir_node *block, void *ctx) { - pre_env *env = ctx; - block_info *dom_info; - block_info *info = get_block_info(block); - ir_node *dom_blk; - - /* we don't need the end block Avail */ - if (block == env->end_block) - return; - - /* - * First add all nodes from the dominator. - * This must be done to ensure that Antic_out contains the leader - * for every node. The root has no dominator. - */ - if (block != env->start_block) { - dom_blk = get_Block_idom(block); - assert(is_Block(dom_blk)); - - dom_info = get_block_info(dom_blk); - assert(dom_info); - - value_union(info->avail_out, dom_info->avail_out); - } - value_union_nodes(info->avail_out, info->nodes); - - dump_value_set(info->avail_out, "Avail_out", block); -} + pre_env *env = ctx; + block_info *dom_info; + block_info *info = get_block_info(block); + ir_node *dom_blk; + + /* we don't need the end block Avail */ + if (block == env->end_block) + return; + + /* + * First add all nodes from the dominator. + * This must be done to ensure that Antic_out contains the leader + * for every node. The root has no dominator. + */ + if (block != env->start_block) { + dom_blk = get_Block_idom(block); + assert(is_Block(dom_blk)); + + dom_info = get_block_info(dom_blk); + assert(dom_info); + + value_union(info->avail_out, dom_info->avail_out); + } + value_union(info->avail_out, info->exp_gen); -/** - * returns non-zero if a tree node must be copied because of - * a phi_translate. - */ -static int need_copy(ir_node *node, ir_node *block) -{ - int i, arity; - - /* Phi always stop the recursion */ - if (is_Phi(node)) - return get_irn_intra_n(node, -1) == block; - - if (! is_nice_value(node)) - return 0; - - /* check predecessor */ - arity = get_irn_intra_arity(node); - for (i = 0; i < arity; ++i) { - ir_node *pred = get_irn_intra_n(node, i); - ir_node *local_bl = get_irn_intra_n(pred, -1); - ir_node *leader = value_lookup(get_block_info(local_bl)->avail_out, pred); - - pred = leader != NULL ? leader : pred; - if (need_copy(pred, block)) - return 1; - } - return 0; -} + dump_value_set(info->avail_out, "Avail_out", block); +} /* compute_avail_top_down */ /** - * Translate a node + * 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 ir_node *translate(ir_node *node, ir_node *block, int pos, pre_env *env) +static int is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *set) { - int i, arity, need_new; - ir_node *res, *nn, **in; - - /* Phi always stop the recursion */ - if (is_Phi(node)) { - if (get_irn_intra_n(node, -1) == block) - return get_Phi_pred(node, pos); - return node; - } - - if (! is_nice_value(node)) - return node; - - arity = get_irn_intra_arity(node); - if (arity > 0) { - NEW_ARR_A(ir_node *, in, arity); - i = arity - 1; - need_new = 0; - do { - ir_node *pred = get_irn_intra_n(node, i); - ir_node *pred_blk = get_irn_intra_n(pred, -1); - ir_node *leader = value_lookup(get_block_info(pred_blk)->avail_out, pred); - in[i] = translate(leader ? leader : pred, block, pos, env); - need_new |= (in[i] != pred); - --i; - } while(i >= 0); - if (! need_new) - return node; - - /* create a copy */ - nn = new_ir_node( - get_irn_dbg_info(node), - current_ir_graph, - get_Block_cfgpred_block(block, pos), - get_irn_op(node), - get_irn_mode(node), - arity, - in); - /* We need the attribute copy here, because the Hash value of a - node might depend on that. */ - copy_node_attr(node, nn); - res = node_add(env->trans_set, nn); - if (nn != res) { - obstack_free(env->obst, nn); - } else { - DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res)); - } + int i; - return res; - } - return node; -} + if (is_Phi(n)) + return 1; -#if 0 -/** - * Implements phi_translate. - */ -static ir_node *deep_phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env) -{ - struct obstack *old; - ir_node *res; + if (! is_nice_value(n)) + return 0; - if (! need_copy(node, block)) - return node; + for (i = get_irn_arity(n) - 1; i >= 0; --i) { + ir_node *pred = get_irn_n(n, i); + ir_node *value; - /* 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; - res = translate(node, block, pos, env); - current_ir_graph->obst = old; + if (get_nodes_block(pred) != block) + continue; - return res; -} /* phi_translate */ -#endif + if (is_Phi(pred)) + continue; -/** - * Implements phi_translate. - */ -static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env) -{ - ir_node *nn, *res; - int i, arity; - struct obstack *old; - - if (is_Phi(node)) { - if (get_irn_intra_n(node, -1) == block) - return get_Phi_pred(node, pos); - return node; - } - - arity = get_irn_intra_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_bl = get_irn_intra_n(pred, -1); - ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred); - - leader = leader != NULL ? leader : pred; - if (is_Phi(leader) && get_irn_intra_n(pred, -1) == block) - break; - } - if (i >= arity) { - /* no Phi in the predecessors */ - 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_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); - - set_irn_n(nn, -1, get_irn_intra_n(node, -1)); - for (i = 0; i < arity; ++i) { - ir_node *pred = get_irn_intra_n(node, i); - ir_node *pred_bl = get_irn_intra_n(pred, -1); - ir_node *leader = value_lookup(get_block_info(pred_bl)->avail_out, pred); - - 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)); - else - set_irn_n(nn, i, leader); - } - res = node_add(env->trans_set, nn); - current_ir_graph->obst = old; - - if (nn != res) - obstack_free(env->obst, nn); - else { - DB((dbg, LEVEL_2, "--> Translate %+F in <%+F,%d> into %+F\n", node, block, pos, res)); - } - return res; -} /* phi_translate */ + if (! is_nice_value(pred)) + return 0; -/** - * check if a node n is clean in block block. - */ -static int _is_clean(ir_node *n, ir_node *block) -{ - int i; - - if (get_nodes_block(n) != block) - return 1; - if (is_Phi(n)) - return 1; - - if (irn_visited(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; - } - return 1; -bad: - mark_irn_visited(n); - return 0; -} + value = lookup(pred); + if (! value) + return 0; + if (! ir_valueset_lookup(set, value)) + return 0; + } + return 1; +} /* is_clean_in_block */ /** - * check if a node n is clean. + * 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 translated the valueset containing the other already translated nodes + * + * @return a node representing the translated value */ -static int is_clean(ir_node *n) +static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *translated) { - int res = _is_clean(n, get_nodes_block(n)); - return res; -} + ir_node *nn; + int i, arity; + + if (is_Phi(node)) { + if (get_nodes_block(node) == block) { + /* a Phi inside our block */ + return get_Phi_pred(node, pos); + } + /* already outside */ + return node; + } -/** - * Clean a node set. - * This function is called for node sets with is_clean - * nodes only, so we must just remove nodes that don't - * have available inputs - */ -static void clean_node_set(node_set *set, ir_node *blk) -{ - ir_node *n, *pred, *pred_blk; - int i; - -restart: - for (n = node_set_first(set); n; n = node_set_next(set)) { - for (i = get_irn_intra_arity(n) - 1; i >= 0; --i) { - pred = get_irn_intra_n(n, i); - - pred_blk = get_irn_intra_n(pred, -1); - if (block_dominates(pred_blk, blk)) - continue; - /* pred do not dominate it, but may be in the set */ - if (node_lookup(set, pred) != NULL) - continue; - /* we found a node that must be removed */ - node_set_break(set); - node_set_remove(set, n); - DB((dbg, LEVEL_2, "<-- Cleaning %+F\n", n)); - goto restart; - } - } -} + 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_n(node, i); + ir_node *leader = lookup(pred); + ir_node *trans; + + leader = leader != NULL ? leader : pred; + trans = ir_valueset_lookup(translated, leader); + + if ((trans != NULL && trans != leader) || (is_Phi(leader) && get_nodes_block(leader) == block)) + break; + } + if (i >= arity) { + /* no translation needed */ + return node; + } + + nn = new_ir_node( + get_irn_dbg_info(node), + current_ir_graph, + 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(current_ir_graph, node, nn); + + for (i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(node, i); + ir_node *leader = lookup(pred); + ir_node *trans; + + leader = leader != NULL ? leader : pred; + trans = 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, trans); + } + nn = optimize_node(nn); + return nn; +} /* phi_translate */ /** - * computes Antic_in(block): + * Block-walker, computes Antic_in(block). + * + * @param block the block + * @param ctx the walker environment */ static void compute_antic(ir_node *block, void *ctx) { - pre_env *env = ctx; - block_info *succ_info; - block_info *info = get_block_info(block); - ir_node *succ; - int size; - - /* no need for computations in start block */ - if (block == env->start_block) - return; - - size = node_set_count(info->antic_in); - - /* the end block has no successor */ - if (block != env->end_block) { - int n_succ = get_Block_n_cfg_outs(block); - - if (n_succ == 1) { - ir_node *node, *list; - int i, 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; - } - } - 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 */ - list = NULL; - node_set_foreach(node, succ_info->antic_in) { - set_irn_link(node, list); - list = node; - } - for (node = list; node; node = get_irn_link(node)) { - ir_node *trans = phi_translate(node, succ, pos, env); - - if (is_clean(trans)) - node_add(info->antic_in, trans); - } - } - else { - ir_node *n, *succ0; - block_info *succ0_info; - int i; - - assert(n_succ > 1); - - /* Select a successor to compute the disjoint of all Nodes - sets, it might be useful to select the block with the - smallest number of nodes. For simplicity we choose the - first one. */ - succ0 = get_Block_cfg_out(block, 0); - succ0_info = get_block_info(succ0); - node_set_foreach(n, succ0_info->antic_in) { - /* we need the disjoint */ - for (i = 1; i < n_succ; ++i) { - ir_node *succ = get_Block_cfg_out(block, i); - block_info *succ_info = get_block_info(succ); - if (node_lookup(succ_info->antic_in, n) == NULL) - break; - } - if (i >= n_succ) { - /* we found a node that is common in all Antic_in(succ(b)), - put it in Antic_in(b) */ - node_add(info->antic_in, n); - } - } - } - - /* - * This step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b). - * It is enough to do this in the first iteration, because - * the set info->nodes is not changed anymore. - */ - if (env->first_iter) { - ir_node *n; - node_set_foreach(n, info->nodes) { - if (is_clean(n)) - node_add(info->antic_in, n); - } - } - } - -// clean_node_set(info->antic_in, block); - (void) clean_node_set; - - dump_node_set(info->antic_in, "Antic_in", block); - if (size != node_set_count(info->antic_in)) { - /* the Antic_in set has changed */ - env->changes |= 1; - } -} /* compute_antic */ + pre_env *env = ctx; + block_info *succ_info; + block_info *info = get_block_info(block); + ir_node *succ, *value, *expr; + size_t size; + ir_valueset_iterator_t iter; + + /* no need for computations in start block */ + if (block == env->start_block) + return; + + size = ir_valueset_size(info->antic_in); + + /* the end block has no successor */ + if (block != env->end_block) { + int n_succ; + + /* + * This step puts all generated expression from the current + * current block into Antic_in. + * It is enough to do this in the first iteration only, because + * the set info->exp_gen is not changed anymore. + */ + if (env->first_iter) { + foreach_valueset(info->exp_gen, value, expr, iter) { + ir_valueset_insert(info->antic_in, value, expr); + } + } + + n_succ = get_Block_n_cfg_outs(block); + if (n_succ == 1) { + int pos = -1; + + /* find blocks position in succ's block predecessors */ + succ = get_Block_cfg_out(block, 0); + 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, info->antic_in); + + if (is_clean_in_block(trans, block, info->antic_in)) + ir_valueset_insert(info->antic_in, value, trans); + } + } else { /* n_succ > 1 */ + ir_node *succ0; + block_info *succ0_info; + int i; + + assert(n_succ > 1); + + /* Select a successor to compute the disjoint of all Nodes + sets, it might be useful to select the block with the + smallest number of nodes. For simplicity we choose the + first one. */ + succ0 = get_Block_cfg_out(block, 0); + succ0_info = get_block_info(succ0); + foreach_valueset(succ0_info->antic_in, value, expr, iter) { + /* we need the disjoint */ + for (i = 1; i < n_succ; ++i) { + ir_node *succ = get_Block_cfg_out(block, i); + block_info *succ_info = get_block_info(succ); + if (ir_valueset_lookup(succ_info->antic_in, value) == NULL) + break; + } + 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. */ + if (is_clean_in_block(expr, block, info->antic_in)) + ir_valueset_insert(info->antic_in, value, expr); + } + } + } + } -/** - * allocate a block info - */ -static void alloc_blk_info(ir_node *block, void *ctx) -{ - int i; - pre_env *env = ctx; - block_info *info = obstack_alloc(env->obst, sizeof(*info)); - - set_irn_link(block, info); - info->nodes = new_node_set(); - info->antic_in = new_node_set(); - info->avail_out = new_value_set(); - info->avail = NULL; - info->not_found = 0; - info->new_set = NULL; - info->next = env->list; - env->list = info; - - /* fill the nodes set, we will need it later */ - for (i = get_irn_n_outs(block) - 1; i >= 0; --i) { - ir_node *n = get_irn_out(block, i); - - set_irn_link(n, NULL); - - /* we cannot optimize pinned nodes, so do not remember them */ - if (is_nice_value(n)) - node_add(info->nodes, n); - } -} + /* we do not need a clean here, because we ensure that only cleaned nodes are in exp_gen + * and all other sets */ + + dump_value_set(info->antic_in, "Antic_in", block); + if (size != ir_valueset_size(info->antic_in)) { + /* the Antic_in set has changed */ + env->changes |= 1; + } +} /* compute_antic */ /** * Perform insertion of partially redundant values. @@ -767,216 +530,257 @@ static void alloc_blk_info(ir_node *block, void *ctx) * 2c. Insert a new Phi merging the values of the predecessors. * 2d. Insert the new Phi, and the new expressions, into the * NEW_SETS set. + * + * @param block the block + * @param ctx the walker environment */ static void insert_nodes(ir_node *block, void *ctx) { - pre_env *env = ctx; - value_entry *entry; - ir_node *e, *idom, *first_s, *worklist; - block_info *curr_info, *idom_info; - int pos, arity = get_irn_intra_arity(block); - int all_same, by_some, updated; - - /* ensure that even the start block has a new_set */ - curr_info = get_block_info(block); - if (curr_info->new_set) - del_value_set(curr_info->new_set); - curr_info->new_set = new_value_set(); - - if (block == env->start_block) - return; - - idom = get_Block_idom(block); - idom_info = get_block_info(idom); - - /* update the new_sets */ - updated = 0; - dump_value_set(idom_info->new_set, "[New Set]", idom); - value_set_foreach(entry, idom_info->new_set) { - updated |= value_add_or_replace(curr_info->avail_out, entry->node, entry->value); - } - if (updated) { - dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block); - } - - if (arity <= 1) - return; - - /* convert the set into a list. This allows the removal of - * elements from the set */ - worklist = NULL; - node_set_foreach(e, curr_info->antic_in) { - set_irn_link(e, worklist); - worklist = e; - } - - for (e = worklist; e != NULL; e = get_irn_link(e)) { - ir_mode *mode; - - /* If the value was already computed in the dominator, then - it is totally redundant. Hence we have nothing to insert. */ - if (value_lookup(idom_info->avail_out, e)) { -// DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom)); - continue; - } - - by_some = 0; - all_same = 1; - first_s = NULL; - mode = NULL; - - /* for all predecessor blocks */ - for (pos = 0; pos < arity; ++pos) { - block_info *pred_info; - ir_node *pred_blk = get_Block_cfgpred_block(block, pos); - ir_node *e_prime, *v_prime, *e_dprime; - - /* ignore bad blocks. */ - if (is_Bad(pred_blk)) - continue; - - e_prime = phi_translate(e, block, pos, env); - v_prime = e_prime; - - pred_info = get_block_info(pred_blk); - e_dprime = value_lookup(pred_info->avail_out, v_prime); - - if (e_dprime == NULL) { - all_same = 0; - pred_info->avail = e_prime; - pred_info->not_found = 1; - } - else { - mode = get_irn_mode(e_dprime); - e_dprime = e_dprime; - pred_info->avail = e_dprime; - pred_info->not_found = 0; - by_some = 1; - if (first_s == NULL) - first_s = e_dprime; - else if (first_s != e_dprime) - all_same = 0; - - DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", e, block, e_dprime, pred_blk)); - } /* if */ - } /* for */ - - /* 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; - - DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", e, block)); - - in = xmalloc(arity * sizeof(*in)); - /* for all predecessor blocks */ - for (pos = 0; pos < arity; ++pos) { - ir_node *pred_blk = get_Block_cfgpred_block(block, pos); - block_info *pred_info = get_block_info(pred_blk); - - /* ignore bad blocks. */ - if (is_Bad(pred_blk)) { - in[pos] = new_Bad(); - continue; - } - - /* ignore blocks that already have the expression */ - if (pred_info->not_found) { - ir_node *e_prime = pred_info->avail; - ir_node *nn; - if (!is_Phi(e_prime)) { - mode = get_irn_mode(e_prime); - nn = new_ir_node( - get_irn_dbg_info(e_prime), - current_ir_graph, pred_blk, - get_irn_op(e_prime), - mode, - get_irn_arity(e_prime), - get_irn_in(e_prime) + 1); - copy_node_attr(e_prime, nn); - - DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk)); - pred_info->avail = value_add(pred_info->avail_out, nn, e_prime)->node; - } - } - in[pos] = pred_info->avail; - } /* for */ - phi = new_r_Phi(current_ir_graph, block, arity, in, mode); - free(in); - value_add_or_replace(curr_info->avail_out, phi, e); - value_add(curr_info->new_set, phi, e); - DB((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, e)); - - /* the good case: we really replace an instruction */ - node_set_remove(curr_info->antic_in, e); - - env->changes |= 1; - } /* if */ + pre_env *env = ctx; + ir_node *value, *expr, *idom, *first_s, *worklist; + block_info *curr_info, *idom_info; + int pos, arity = get_irn_arity(block); + int all_same, by_some, updated; + ir_valueset_iterator_t iter; + + /* ensure that even the start block has a new_set */ + curr_info = get_block_info(block); + if (curr_info->new_set) + ir_valueset_del(curr_info->new_set); + curr_info->new_set = ir_valueset_new(16); + + if (block == env->start_block) + return; + + idom = get_Block_idom(block); + idom_info = get_block_info(idom); + + /* update the new_sets */ + updated = 0; + dump_value_set(idom_info->new_set, "[New Set]", idom); + foreach_valueset(idom_info->new_set, value, expr, iter) { + ir_valueset_insert(curr_info->new_set, value, expr); + updated |= ir_valueset_replace(curr_info->avail_out, value, expr); + } + if (updated) { + dump_value_set(curr_info->avail_out, "Updated [Avail_out]", block); + } + + if (arity <= 1) + return; + + /* convert the set into a list. This allows the removal of + * elements from the set */ + worklist = NULL; + foreach_valueset(curr_info->antic_in, value, expr, iter) { + ir_mode *mode; + + /* If the value was already computed in the dominator, then + it is totally redundant. Hence we have nothing to insert. */ + if (ir_valueset_lookup(idom_info->avail_out, value)) { + // DB((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom)); + continue; + } + + by_some = 0; + all_same = 1; + first_s = NULL; + mode = NULL; + + /* for all predecessor blocks */ + for (pos = 0; pos < arity; ++pos) { + block_info *pred_info; + ir_node *pred_blk = get_Block_cfgpred_block(block, pos); + ir_node *e_prime, *v_prime, *e_dprime; + + /* ignore bad blocks. */ + if (is_Bad(pred_blk)) + continue; + + 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); + + if (e_dprime == NULL) { + pred_info->avail = e_prime; + pred_info->not_found = 1; + all_same = 0; + } else { + pred_info->avail = e_dprime; + pred_info->not_found = 0; + mode = get_irn_mode(e_dprime); + e_dprime = e_dprime; + by_some = 1; + if (first_s == NULL) + first_s = e_dprime; + else if (first_s != e_dprime) + all_same = 0; + + DB((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", expr, block, e_dprime, pred_blk)); + } /* if */ + } /* for */ + + /* 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, *l, **in; + + DB((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", expr, block)); + + 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); + block_info *pred_info = get_block_info(pred_blk); + + /* ignore bad blocks. */ + if (is_Bad(pred_blk)) { + in[pos] = new_Bad(); + continue; + } + + /* ignore blocks that already have the expression */ + if (pred_info->not_found) { + ir_node *e_prime = pred_info->avail; + ir_node *nn; + if (!is_Phi(e_prime)) { + ir_node *proj_pred = NULL; + if (is_Proj(e_prime)) { + ir_node *pred = get_Proj_pred(e_prime); + mode = get_irn_mode(pred); + nn = new_ir_node( + get_irn_dbg_info(pred), + current_ir_graph, pred_blk, + get_irn_op(pred), + mode, + get_irn_arity(pred), + get_irn_in(pred) + 1); + copy_node_attr(current_ir_graph, pred, nn); + + DB((dbg, LEVEL_1, "New node %+F in block %+F created\n", nn, pred_blk)); + proj_pred = nn; + } + mode = get_irn_mode(e_prime); + nn = new_ir_node( + get_irn_dbg_info(e_prime), + current_ir_graph, pred_blk, + get_irn_op(e_prime), + mode, + get_irn_arity(e_prime), + get_irn_in(e_prime) + 1); + copy_node_attr(current_ir_graph, e_prime, nn); + if (proj_pred != NULL) { + set_Proj_pred(nn, proj_pred); + } + + 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(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_1, "New %+F for redundant %+F created\n", phi, expr)); + ir_valueset_remove_iterator(curr_info->antic_in, &iter); + env->changes |= 1; + } /* if */ } /* node_set_foreach */ } /* insert_nodes */ /** - * Do the elimination step: collect all changes + * Walker, change nodes by its value if different. + * * We cannot do the changes right here, as this would change * the hash values of the nodes in the avail_out set! + * + * @param irn the node + * @param ctx the walker environment */ -static void collect_elim_pairs(ir_node *block, void *ctx) +static void eliminate(ir_node *irn, void *ctx) { - pre_env *env = ctx; - block_info *curr_info = get_block_info(block); - ir_node *v; - - dump_node_set(curr_info->nodes, "Updating nodes", block); - node_set_foreach(v, curr_info->nodes) { - ir_node *l = value_lookup(curr_info->avail_out, v); - - assert(l); - if (l != v) { - elim_pair *p = obstack_alloc(env->obst, sizeof(*p)); - - p->old_node = v; - p->new_node = l; - p->next = env->pairs; - env->pairs = p; - } - } -} + pre_env *env = ctx; + + 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); + + if (expr != NULL && expr != irn) { + elim_pair *p = OALLOC(env->obst, elim_pair); + + p->old_node = irn; + p->new_node = expr; + p->next = env->pairs; + p->reason = get_irn_idx(expr) >= env->last_idx ? FS_OPT_GVN_PARTLY : FS_OPT_GVN_FULLY; + env->pairs = p; + } + } + } +} /* eliminate */ /** * Do all the recorded changes and optimize * newly created Phi's. + * + * @param pairs list of elimination pairs */ static void eliminate_nodes(elim_pair *pairs) { - elim_pair *p; - - for (p = pairs; p != NULL; p = p->next) { - 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, ...) - * which we can optimize here - */ - if (is_Phi(p->new_node)) { - int i; - ir_node *res = NULL; - - for (i = get_irn_intra_arity(p->new_node) - 1; i >= 0; --i) { - ir_node *pred = get_irn_n(p->new_node, i); - - if (pred != p->old_node) { - if (res) { - res = NULL; - break; - } - res = pred; - } - } - if (res) - p->new_node = res; - } - exchange(p->old_node, p->new_node); - } -} + 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, ...) + * which we can optimize here + */ + if (is_Phi(p->new_node)) { + int i; + ir_node *res = NULL; + + 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) { + if (res) { + res = NULL; + break; + } + res = pred; + } + } + 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); + } +} /* eliminate_nodes */ /* * Argh: Endless loops cause problems, because the @@ -984,107 +788,118 @@ 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) { - struct obstack obst; - pre_env a_env; - optimization_state_t state; - block_info *p; - unsigned antic_iter, insert_iter; - - assert(!"COMPLETELY BROKEN YET, DO NOT USE"); - - /* register a debug mask */ - FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre"); - firm_dbg_set_mask(dbg, SET_LEVEL_2); - - obstack_init(&obst); - a_env.obst = &obst; - a_env.trans_set = new_node_set(); - a_env.list = NULL; - a_env.start_block = get_irg_start_block(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); - - /* we need dominator for Antic_out calculation */ - if (get_irg_dom_state(irg) != dom_consistent) - compute_doms(irg); - if (get_irg_postdom_state(irg) != dom_consistent) - compute_postdoms(irg); - /* we get all nodes of a block by following outs */ - if (get_irg_outs_state(irg) != outs_consistent) - compute_irg_outs(irg); - - /* - * Switch on GCSE. We need it to correctly compute - * the leader of a node by hashing. - */ - save_optimization_state(&state); - set_opt_global_cse(1); - - DB((dbg, LEVEL_1, "Doing GVN-PRE for %e\n", get_irg_entity(irg))); - printf("Doing GVN-PRE for %s\n", get_entity_name(get_irg_entity(irg))); - - /* allocate block info for all blocks */ - irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env); - - /* compute the available value sets for all blocks */ - dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env); - - /* compute the anticipated value sets for all blocks */ - inc_irg_visited(irg); - antic_iter = 0; - a_env.first_iter = 1; - do { - DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter)); - a_env.changes = 0; - irg_block_walk_graph(irg, compute_antic, NULL, &a_env); -// postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env); - a_env.first_iter = 0; - DB((dbg, LEVEL_1, "------------------------\n")); - } while (a_env.changes != 0); - - /* compute redundant expressions */ - insert_iter = 0; - do { - DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter)); - a_env.changes = 0; - dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env); - DB((dbg, LEVEL_1, "------------------------\n")); - } while (a_env.changes != 0); - - /* last step: eliminate nodes */ - dom_tree_walk_irg(irg, collect_elim_pairs, NULL, &a_env); - eliminate_nodes(a_env.pairs); - - restore_optimization_state(&state); - - /* clean up: delete all sets */ - for (p = a_env.list; p != NULL; p = p->next) { - if (p->antic_in) - del_node_set(p->antic_in); - if (p->avail_out) - del_value_set(p->avail_out); - if (p->nodes) - del_node_set(p->nodes); - if (p->new_set) - del_value_set(p->new_set); - } - del_node_set(a_env.trans_set); - obstack_free(&obst, NULL); - set_irg_pinned(irg, op_pin_state_pinned); - - if (a_env.pairs) { - set_irg_outs_inconsistent(irg); - set_irg_loopinfo_inconsistent(irg); - } + struct obstack obst; + pre_env a_env; + optimization_state_t state; + block_info *bl_info; + unsigned antic_iter, insert_iter; + ir_node *value, *expr; + + /* register a debug mask */ + FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre"); + + /* edges will crash if enabled due to our allocate on other obstack trick */ + edges_deactivate(irg); + + new_identities(irg); + ir_nodemap_init(&value_map); + + obstack_init(&obst); + a_env.obst = &obst; + a_env.list = NULL; + a_env.start_block = get_irg_start_block(irg); + a_env.end_block = get_irg_end_block(irg); + a_env.pairs = NULL; + + /* critical edges MUST be removed */ + remove_critical_cf_edges(irg); + + /* we need dominator for Antic_out calculation */ + assure_doms(irg); + assure_postdoms(irg); + /* we get all nodes of a block by following outs */ + assure_irg_outs(irg); + + /* + * Switch on GCSE. We need it to correctly compute + * 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 %+F\n", irg)); + + /* allocate block info for all blocks */ + 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_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); + + /* compute the anticipated value sets for all blocks */ + antic_iter = 0; + a_env.first_iter = 1; + + /* we use the visited flag to mark non-clean nodes */ + inc_irg_visited(irg); + do { + DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter)); + a_env.changes = 0; + postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env); + a_env.first_iter = 0; + DB((dbg, LEVEL_1, "------------------------\n")); + } while (a_env.changes != 0); + + /* compute redundant expressions */ + insert_iter = 0; + a_env.last_idx = get_irg_last_idx(irg); + do { + DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter)); + a_env.changes = 0; + dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env); + DB((dbg, LEVEL_1, "------------------------\n")); + } while (a_env.changes != 0); + + /* last step: eliminate nodes */ + irg_walk_graph(irg, NULL, eliminate, &a_env); + eliminate_nodes(a_env.pairs); + + /* clean up: delete all sets */ + for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) { + ir_valueset_del(bl_info->exp_gen); + ir_valueset_del(bl_info->avail_out); + ir_valueset_del(bl_info->antic_in); + if (bl_info->new_set) + ir_valueset_del(bl_info->new_set); + } + ir_nodemap_destroy(&value_map); + obstack_free(&obst, 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 */