X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fgvn_pre.c;h=bd2c6606534c6b561a7c35fdcf5a26ba1f0208f5;hb=0b437c919ef3a7c1b4e94c56685ff1580a63efd5;hp=bde998bbc1b8dacd5842fa00d41e82cab8cf8fa2;hpb=90da162af19a38679eb09ed58fcc5f25dd4c560d;p=libfirm

diff --git a/ir/opt/gvn_pre.c b/ir/opt/gvn_pre.c
index bde998bbc..bd2c66065 100644
--- a/ir/opt/gvn_pre.c
+++ b/ir/opt/gvn_pre.c
@@ -39,6 +39,8 @@
 #include "valueset.h"
 #include "irnodemap.h"
 #include "irnodeset.h"
+#include "iredges.h"
+#include "iropt_dbg.h"
 #include "debug.h"
 
 #include "irgraph_t.h"
@@ -65,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 */
@@ -74,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;
@@ -101,17 +105,36 @@ 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)
 {
+	if (is_Proj(v)) {
+		ir_node *pred = get_Proj_pred(v);
+		ir_node *v_pred = identify_remember(value_table, pred);
+
+		if (v_pred != pred) {
+			/* must create a new value here */
+			v = new_r_Proj(current_ir_graph, get_nodes_block(v_pred), v_pred, get_irn_mode(v), get_Proj_proj(v));
+		}
+	}
 	v = 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)
 {
@@ -119,32 +142,22 @@ static ir_node *lookup(ir_node *e)
 	if (value != NULL)
 		return identify_remember(value_table, value);
 	return NULL;
-}
+}  /* lookup */
 
 /**
- * Add or replace a value in a set by an node computing the same
- * value in a dominator block.
- */
-static ir_node *lookup_or_add(ir_node *e)
-{
-	ir_node *x = lookup(e);
-
-	if (x == NULL) {
-		x = add(e, e);
-	}
-	return x;
-}
-
-
-/**
- * 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));
@@ -158,49 +171,37 @@ 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;
 
 	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))
+	if (get_irn_pinned(n) == op_pin_state_pinned)
 		return 0;
-	return (get_irn_pinned(n) != op_pin_state_pinned);
+	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 ir_nodeset_t set.
- */
-static void dump_node_set(ir_nodeset_t *set, char *txt, ir_node *block)
-{
-	ir_nodeset_iterator_t iter;
-	ir_node *n;
-	int i;
-
-	DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
-	i = 0;
-	foreach_ir_nodeset(set, n, iter) {
-		if ((i & 3) == 3)
-			DB((dbg, LEVEL_2, "\n"));
-		DB((dbg, LEVEL_2, " %+F,", n));
-		++i;
-	}
-	DB((dbg, LEVEL_2, "\n}\n"));
-}  /* dump_node_set */
-
 /**
  * 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;
@@ -221,9 +222,7 @@ static void dump_value_set(ir_valueset_t *set, char *txt, ir_node *block) {
 	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 */
 
@@ -249,6 +248,11 @@ static void topo_walker(ir_node *irn, void *ctx) {
 	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);
@@ -265,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)
 {
@@ -294,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)
 {
@@ -322,22 +332,31 @@ 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)
 {
-	ir_node *nn, *res;
+	ir_node *nn;
 	int i, arity;
 	struct obstack *old;
 
@@ -355,7 +374,6 @@ static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *e
 	/* 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_nodes_block(pred);
 		ir_node *leader  = lookup(pred);
 
 		leader = leader != NULL ? leader : pred;
@@ -387,7 +405,6 @@ static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *e
 	set_nodes_block(nn, get_nodes_block(node));
 	for (i = 0; i < arity; ++i) {
 		ir_node *pred    = get_irn_intra_n(node, i);
-		ir_node *pred_bl = get_irn_intra_n(pred, -1);
 		ir_node *leader  = lookup(pred);
 
 		leader = leader != NULL ? leader : pred;
@@ -401,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;
@@ -419,8 +439,21 @@ static void compute_antic(ir_node *block, void *ctx) {
 
 	/* the end block has no successor */
 	if (block != env->end_block) {
-		int n_succ = get_Block_n_cfg_outs(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 i, pos = -1;
 
@@ -450,18 +483,6 @@ static void compute_antic(ir_node *block, void *ctx) {
 
 			assert(n_succ > 1);
 
-			/*
-			 * 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);
-				}
-			}
-
 			/* 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
@@ -507,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)
 {
@@ -622,6 +646,22 @@ static void insert_nodes(ir_node *block, void *ctx)
 					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(pred, nn);
+
+							DB((dbg, LEVEL_2, "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),
@@ -631,6 +671,9 @@ static void insert_nodes(ir_node *block, void *ctx)
 							get_irn_arity(e_prime),
 							get_irn_in(e_prime) + 1);
 						copy_node_attr(e_prime, nn);
+						if (proj_pred != NULL) {
+							set_Proj_pred(nn, proj_pred);
+						}
 
 						DB((dbg, LEVEL_2, "New node %+F in block %+F created\n", nn, pred_blk));
 						ir_valueset_insert(pred_info->avail_out, add(nn, lookup(expr)), nn);
@@ -645,6 +688,7 @@ static void insert_nodes(ir_node *block, void *ctx)
 			ir_valueset_insert(curr_info->new_set, value, phi);
 			free(in);
 			DB((dbg, LEVEL_2, "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 */
@@ -655,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;
@@ -673,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;
 			}
 		}
@@ -682,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;
@@ -710,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 */
@@ -724,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);
@@ -772,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);
 
@@ -784,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"));
@@ -792,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;
@@ -825,5 +887,4 @@ void do_gvn_pre(ir_graph *irg)
 		set_irg_loopinfo_inconsistent(irg);
 
 	}
-	dump_ir_block_graph(irg, "-gvn");
 }  /* do_gvn_pre */