* @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 <assert.h>
-
-#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;
/**
* 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):
* 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.
* 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
* 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 */
projects / libfirm / blobdiff