X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fgvn_pre.c;h=bd2c6606534c6b561a7c35fdcf5a26ba1f0208f5;hb=44faeb9742640d3498eb4482f98eb1255607c4d6;hp=a9498d8c0bff2381eba3ae13ba830513bfb5b69d;hpb=5b290ce8b5b89f119a6242a982bd60d6156648e0;p=libfirm

diff --git a/ir/opt/gvn_pre.c b/ir/opt/gvn_pre.c
index a9498d8c0..bd2c66065 100644
--- a/ir/opt/gvn_pre.c
+++ b/ir/opt/gvn_pre.c
@@ -40,6 +40,7 @@
 #include "irnodemap.h"
 #include "irnodeset.h"
 #include "iredges.h"
+#include "iropt_dbg.h"
 #include "debug.h"
 
 #include "irgraph_t.h"
@@ -66,6 +67,7 @@ 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. */
+	int     reason;         /**< The reason for the replacement. */
 } elim_pair;
 
 /** The environment for the GVN-PRE algorithm */
@@ -75,6 +77,7 @@ typedef struct pre_env {
 	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. */
+	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;
@@ -102,7 +105,12 @@ static void value_union(ir_valueset_t *dst, ir_valueset_t *src)
 /* ----------  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 ir_node *add(ir_node *e, ir_node *v)
 {
@@ -118,10 +126,15 @@ static ir_node *add(ir_node *e, ir_node *v)
 	v = identify_remember(value_table, 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 *lookup(ir_node *e)
 {
@@ -129,17 +142,22 @@ static ir_node *lookup(ir_node *e)
 	if (value != NULL)
 		return identify_remember(value_table, value);
 	return NULL;
-}
+}  /* lookup */
 
 /**
- * Return the block info of a block
+ * Return the block info of a block.
+ *
+ * @param block  the block
  */
 static block_info *get_block_info(ir_node *block) {
 	return get_irn_link(block);
-}
+}  /* get_block_info */
 
 /**
- * allocate a block info
+ * Allocate a block info for a block.
+ *
+ * @param block   the block
+ * @param env     the environment
  */
 static void alloc_blk_info(ir_node *block, pre_env *env) {
 	block_info *info = obstack_alloc(env->obst, sizeof(*info));
@@ -153,10 +171,12 @@ static void alloc_blk_info(ir_node *block, pre_env *env) {
 	info->not_found = 0;
 	info->next      = env->list;
 	env->list       = info;
-}
+}  /* alloc_blk_info */
 
 /**
  * Returns non-zero if a node is movable and a possible candidate for PRE.
+ *
+ * @param n  the node
  */
 static int is_nice_value(ir_node *n) {
 	ir_mode *mode;
@@ -178,6 +198,10 @@ static int is_nice_value(ir_node *n) {
 #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(ir_valueset_t *set, char *txt, ir_node *block) {
 	ir_valueset_iterator_t iter;
@@ -245,6 +269,9 @@ static void topo_walker(ir_node *irn, void *ctx) {
  * 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)
 {
@@ -274,10 +301,13 @@ static void compute_avail_top_down(ir_node *block, void *ctx)
 	value_union(info->avail_out, info->exp_gen);
 
 	dump_value_set(info->avail_out, "Avail_out", block);
-}
+}  /* compute_avail_top_down */
 
 /**
  * check if a node n is clean in block block.
+ *
+ * @param n      the node
+ * @param block  the block
  */
 static int _is_clean(ir_node *n, ir_node *block)
 {
@@ -302,18 +332,27 @@ static int _is_clean(ir_node *n, ir_node *block)
 bad:
 	mark_irn_visited(n);
 	return 0;
-}
+}  /* _is_clean */
 
 /**
  * check if a node n is clean.
+ *
+ * @param n  the node to check
  */
 static int is_clean(ir_node *n) {
 	int res = _is_clean(n, get_nodes_block(n));
 	return res;
-}
+}  /* is_clean */
 
 /**
- * Implements phi_translate.
+ * Implements phi_translate. Translate a expression above a Phi.
+ *
+ * @param node   the node
+ * @param block  the block in which the node is translated
+ * @param pos    the input number of the destination block
+ * @param env    the environment
+ *
+ * @return a node representing the translated value
  */
 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
 {
@@ -379,7 +418,10 @@ static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *e
 }  /* 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;
@@ -486,6 +528,9 @@ static void compute_antic(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)
 {
@@ -654,6 +699,9 @@ static void insert_nodes(ir_node *block, void *ctx)
  *
  * 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 eliminate(ir_node *irn, void *ctx) {
 	pre_env *env = ctx;
@@ -672,6 +720,7 @@ static void eliminate(ir_node *irn, void *ctx) {
 				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;
 			}
 		}
@@ -681,6 +730,8 @@ static void eliminate(ir_node *irn, void *ctx) {
 /**
  * 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;
@@ -709,6 +760,7 @@ static void eliminate_nodes(elim_pair *pairs) {
 			if (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 */
@@ -723,15 +775,15 @@ static void eliminate_nodes(elim_pair *pairs) {
  */
 void do_gvn_pre(ir_graph *irg)
 {
-	struct obstack obst;
-	pre_env a_env;
+	struct obstack       obst;
+	pre_env              a_env;
 	optimization_state_t state;
-	block_info *bl_info;
-	unsigned antic_iter, insert_iter;
+	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");
-	firm_dbg_set_mask(dbg, SET_LEVEL_2);
 
 	/* edges will crash if enabled due to our allocate on other obstack trick */
 	edges_deactivate(irg);
@@ -771,6 +823,17 @@ void do_gvn_pre(ir_graph *irg)
 	/* allocate block info for all blocks */
 	irg_walk_blkwise_graph(irg, NULL, topo_walker, &a_env);
 
+	/* clean the exp_gen set. Doing this here saves the cleanup in the iteration. */
+	inc_irg_visited(irg);
+	for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) {
+		ir_valueset_iterator_t iter;
+
+		foreach_valueset(bl_info->exp_gen, value, expr, iter) {
+			if (!is_clean(expr))
+				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);
 
@@ -783,7 +846,6 @@ void do_gvn_pre(ir_graph *irg)
 	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"));
@@ -791,6 +853,7 @@ void do_gvn_pre(ir_graph *irg)
 
 	/* 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;