X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firconsconfirm.c;h=1198034fc67441f4558e1db538c326972e49c6ae;hb=2af4a97900b435e35d7c20350604e3863aff2b4c;hp=3956c17f1b7bdf140a26dfba910a09a447900472;hpb=54790c4d48ecda609d0b4668ecdb787ac65de187;p=libfirm

diff --git a/ir/ana/irconsconfirm.c b/ir/ana/irconsconfirm.c
index 3956c17f1..1198034fc 100644
--- a/ir/ana/irconsconfirm.c
+++ b/ir/ana/irconsconfirm.c
@@ -24,9 +24,7 @@
  * @date     6.2005
  * @version  $Id$
  */
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
+#include "config.h"
 
 #include "irgraph_t.h"
 #include "irnode_t.h"
@@ -36,16 +34,26 @@
 #include "iredges_t.h"
 #include "irgwalk.h"
 #include "irprintf.h"
+#include "irgopt.h"
+#include "irpass.h"
+#include "irtools.h"
+#include "array_t.h"
+#include "debug.h"
+#include "irflag.h"
 
 /**
  * Walker environment.
  */
 typedef struct _env_t {
-  unsigned num_confirms;  /**< number of inserted Confirm nodes */
-  unsigned num_consts;    /**< number of constants placed */
-  unsigned num_eq;        /**< number of equalities placed */
+	unsigned num_confirms;  /**< Number of inserted Confirm nodes. */
+	unsigned num_consts;    /**< Number of constants placed. */
+	unsigned num_eq;        /**< Number of equalities placed. */
+	unsigned num_non_null;  /**< Number of non-null Confirms. */
 } env_t;
 
+/** The debug handle. */
+DEBUG_ONLY(static firm_dbg_module_t *dbg;)
+
 /**
  * Return the effective use block of a node and it's predecessor on
  * position pos.
@@ -56,11 +64,12 @@ typedef struct _env_t {
  * This handles correctly Phi nodes.
  */
 static ir_node *get_effective_use_block(ir_node *node, int pos) {
-	/* the effective use of a Phi is in its predecessor block */
-	if (is_Phi(node))
-		return get_nodes_block(get_irn_n(node, pos));
-	else
-		return get_nodes_block(node);
+	if (is_Phi(node)) {
+		/* the effective use of a Phi argument is in its predecessor block */
+		node = get_nodes_block(node);
+		return get_Block_cfgpred_block(node, pos);
+	}
+	return get_nodes_block(node);
 }
 
 /**
@@ -100,18 +109,130 @@ static void handle_case(ir_node *block, ir_node *irn, long nr, env_t *env) {
 				ir_mode *mode = get_irn_mode(irn);
 				ir_type *tp   = get_irn_type(irn);
 				tarval *tv    = new_tarval_from_long(nr, mode);
-				c = new_r_Const_type(current_ir_graph, block, mode, tv, tp);
+				c = new_r_Const_type(current_ir_graph, tv, tp);
 			}
 
 			set_irn_n(succ, pos, c);
 			DBG_OPT_CONFIRM_C(irn, c);
-//			ir_printf("1 Replacing input %d of node %n with %n\n", pos, succ, c);
+			DB((dbg, LEVEL_2, "Replacing input %d of node %+F with %+F\n", pos, succ, c));
 
 			env->num_consts += 1;
 		}
 	}
 }  /* handle_case */
 
+/**
+ * Handle a mode_b input of Cond nodes.
+ *
+ * @param block     the block which is entered by the branch
+ * @param selector  the mode_b node expressing the branch condition
+ * @param pnc       the true/false condition branch
+ * @param env       statistical environment
+ */
+static void handle_modeb(ir_node *block, ir_node *selector, pn_Cond pnc, env_t *env) {
+	ir_node *cond, *old, *cond_block = NULL, *other_blk = NULL, *con = NULL;
+	ir_node *c_b = NULL, *c_o = NULL;
+	const ir_edge_t *edge, *next;
+
+	for (edge = get_irn_out_edge_first(selector); edge; edge = next) {
+		ir_node *user     = get_edge_src_irn(edge);
+		int     pos       = get_edge_src_pos(edge);
+		ir_node *user_blk = get_effective_use_block(user, pos);
+
+		next = get_irn_out_edge_next(selector, edge);
+		if (block_dominates(block, user_blk)) {
+			/*
+			 * Ok, we found a usage of selector in a block
+			 * dominated by the branch block.
+			 * We can replace the input with true/false.
+			 */
+			if (con == NULL) {
+				con = new_Const(pnc == pn_Cond_true ? tarval_b_true : tarval_b_false);
+			}
+			old = get_irn_n(user, pos);
+			set_irn_n(user, pos, con);
+			DBG_OPT_CONFIRM_C(old, con);
+
+			DB((dbg, LEVEL_2, "Replacing input %d of node %+F with %+F\n", pos, user, con));
+
+			env->num_consts += 1;
+		} else {
+			int i, n;
+
+			/* get the other block */
+			if (other_blk == NULL) {
+				/* we have already tested, that block has only ONE Cond predecessor */
+				cond = get_Proj_pred(get_Block_cfgpred(block, 0));
+				cond_block = get_nodes_block(cond);
+				foreach_out_edge(cond, edge) {
+					ir_node *proj = get_edge_src_irn(edge);
+					if (get_Proj_proj(proj) == (long)pnc)
+						continue;
+					edge = get_irn_out_edge_first(proj);
+					other_blk = get_edge_src_irn(edge);
+					break;
+				}
+				assert(other_blk);
+
+			 	/*
+				 * Note the special case here: if block is a then, there might be no else
+				 * block. In that case the other_block is the user_blk itself and pred_block
+				 * is the cond_block ...
+				 *
+				 * Best would be to introduce a block here, removing this critical edge.
+				 * For some reasons I cannot repair dominance here, so I have to remove
+				 * ALL critical edges...
+				 * FIXME: This should not be needed if we could repair dominance ...
+				 */
+			}
+
+			n = get_Block_n_cfgpreds(user_blk);
+
+			/*
+			 * We have found a user in a non-dominated block:
+			 * check, if all its block predecessors are dominated.
+			 * If yes, place a Phi.
+			 */
+			for (i = n - 1; i >= 0; --i) {
+				ir_node *pred_blk = get_Block_cfgpred_block(user_blk, i);
+
+				if (!block_dominates(block, pred_blk) &&
+				    !block_dominates(other_blk, pred_blk)) {
+					/* can't do anything */
+					break;
+				}
+			}
+			if (i < 0) {
+				ir_node *phi, **in;
+
+				NEW_ARR_A(ir_node *, in, n);
+				/* ok, ALL predecessors are either dominated by block OR other block */
+				if (c_b == NULL) {
+					ir_node *c_true  = new_Const(tarval_b_true);
+					ir_node *c_false = new_Const(tarval_b_false);
+					if (pnc == pn_Cond_true) {
+						c_b = c_true;
+						c_o = c_false;
+					} else {
+						c_b = c_false;
+						c_o = c_true;
+					}
+				}
+				for (i = n - 1; i >= 0; --i) {
+					ir_node *pred_blk = get_Block_cfgpred_block(user_blk, i);
+
+					if (block_dominates(block, pred_blk))
+						in[i] = c_b;
+					else
+						in[i] = c_o;
+				}
+				phi = new_r_Phi(user_blk, n, in, mode_b);
+				set_irn_n(user, pos, phi);
+			}
+		}
+	}
+}
+
 /**
  * Handle an IF-branch.
  *
@@ -128,7 +249,7 @@ static void handle_if(ir_node *block, ir_node *cmp, pn_Cmp pnc, env_t *env) {
 	const ir_edge_t *edge, *next;
 
 	/* Beware of Bads */
-	if (is_Bad(left) ||is_Bad(right))
+	if (is_Bad(left) || is_Bad(right))
 		return;
 
 	op = get_irn_op(left);
@@ -169,7 +290,7 @@ static void handle_if(ir_node *block, ir_node *cmp, pn_Cmp pnc, env_t *env) {
 				set_irn_n(user, pos, right);
 				DBG_OPT_CONFIRM(left, right);
 
-//				ir_printf("2 Replacing input %d of node %n with %n\n", pos, user, right);
+				DB((dbg, LEVEL_2, "Replacing input %d of node %+F with %+F\n", pos, user, right));
 
 				env->num_eq += 1;
 			} else if (block_dominates(blk, cond_block)) {
@@ -212,12 +333,11 @@ static void handle_if(ir_node *block, ir_node *cmp, pn_Cmp pnc, env_t *env) {
 	} else { /* not pn_Cmp_Eq cases */
 		ir_node *c = NULL;
 
-		for (edge = get_irn_out_edge_first(left); edge; edge = next) {
+		foreach_out_edge_safe(left, edge, next) {
 			ir_node *succ = get_edge_src_irn(edge);
 			int     pos   = get_edge_src_pos(edge);
 			ir_node *blk  = get_effective_use_block(succ, pos);
 
-			next = get_irn_out_edge_next(left, edge);
 			if (block_dominates(block, blk)) {
 				/*
 				 * Ok, we found a usage of left in a block
@@ -225,22 +345,56 @@ static void handle_if(ir_node *block, ir_node *cmp, pn_Cmp pnc, env_t *env) {
 				 * We can replace the input with a Confirm(left, pnc, right).
 				 */
 				if (! c)
-					c = new_r_Confirm(current_ir_graph, block, left, right, pnc);
+					c = new_r_Confirm(block, left, right, pnc);
 
 				pos = get_edge_src_pos(edge);
 				set_irn_n(succ, pos, c);
-//				ir_printf("3 Replacing input %d of node %n with %n\n", pos, user, c);
+				DB((dbg, LEVEL_2, "Replacing input %d of node %+F with %+F\n", pos, succ, c));
 
 				env->num_confirms += 1;
 			}
 		}
+
+		if (! is_Const(right)) {
+			/* also construct inverse Confirms */
+			ir_node *rc = NULL;
+
+			pnc = get_inversed_pnc(pnc);
+			foreach_out_edge_safe(right, edge, next) {
+				ir_node *succ = get_edge_src_irn(edge);
+				int     pos;
+				ir_node *blk;
+
+				if (succ == c)
+					continue;
+
+				pos  = get_edge_src_pos(edge);
+				blk  = get_effective_use_block(succ, pos);
+
+				if (block_dominates(block, blk)) {
+					/*
+					 * Ok, we found a usage of right in a block
+					 * dominated by the branch block.
+					 * We can replace the input with a Confirm(right, pnc^-1, left).
+					 */
+					if (! rc)
+						rc = new_r_Confirm(block, right, left, pnc);
+
+					pos = get_edge_src_pos(edge);
+					set_irn_n(succ, pos, rc);
+					DB((dbg, LEVEL_2, "Replacing input %d of node %+F with %+F\n", pos, succ, rc));
+
+					env->num_confirms += 1;
+				}
+			}
+		}
 	}
 }  /* handle_if */
 
 /**
- * Pre-walker: Called for every block to insert Confirm nodes
+ * Pre-block-walker: Called for every block to insert Confirm nodes
  */
-static void insert_Confirm(ir_node *block, void *env) {
+static void insert_Confirm_in_block(ir_node *block, void *env) {
 	ir_node *cond, *proj, *selector;
 	ir_mode *mode;
 
@@ -252,11 +406,11 @@ static void insert_Confirm(ir_node *block, void *env) {
 		return;
 
 	proj = get_Block_cfgpred(block, 0);
-	if (get_irn_op(proj) != op_Proj)
+	if (! is_Proj(proj))
 		return;
 
 	cond = get_Proj_pred(proj);
-	if (get_irn_op(cond) != op_Cond)
+	if (! is_Cond(cond))
 		return;
 
 	selector = get_Cond_selector(cond);
@@ -266,32 +420,131 @@ static void insert_Confirm(ir_node *block, void *env) {
 		ir_node *cmp;
 		pn_Cmp pnc;
 
+		handle_modeb(block, selector, get_Proj_proj(proj), env);
+
 		/* this should be an IF, check this */
-		if (get_irn_op(selector) != op_Proj)
+		if (! is_Proj(selector))
 			return;
 
 		cmp = get_Proj_pred(selector);
-		if (get_irn_op(cmp) != op_Cmp)
+		if (! is_Cmp(cmp))
 			return;
 
 		pnc = get_Proj_proj(selector);
 
 		if (get_Proj_proj(proj) != pn_Cond_true) {
 			/* it's the false branch */
+			mode = get_irn_mode(get_Cmp_left(cmp));
 			pnc = get_negated_pnc(pnc, mode);
 		}
-//		ir_printf("At %n using %n Confirm %=\n", block, cmp, pnc);
+		DB((dbg, LEVEL_2, "At %+F using %+F Confirm %=\n", block, cmp, pnc));
 
 		handle_if(block, cmp, pnc, env);
 	} else if (mode_is_int(mode)) {
 		long proj_nr = get_Proj_proj(proj);
 
 		/* this is a CASE, but we cannot handle the default case */
-		if (proj_nr == get_Cond_defaultProj(cond))
+		if (proj_nr == get_Cond_default_proj(cond))
 			return;
 
 		handle_case(block, get_Cond_selector(cond), proj_nr, env);
 	}
+}  /* insert_Confirm_in_block */
+
+/**
+ * Checks if a node is a non-null Confirm.
+ */
+static int is_non_null_Confirm(const ir_node *ptr) {
+	for (;;) {
+		if (! is_Confirm(ptr))
+			break;
+		if (get_Confirm_cmp(ptr) == pn_Cmp_Lg) {
+			ir_node *bound = get_Confirm_bound(ptr);
+
+			if (is_Const(bound) && is_Const_null(bound))
+				return 1;
+		}
+		ptr = get_Confirm_value(ptr);
+	}
+	/*
+	 * While a SymConst is not a Confirm, it is non-null
+	 * anyway. This helps to reduce the number of
+	 * constructed Confirms.
+	 */
+	if (is_SymConst_addr_ent(ptr))
+		return 1;
+	return 0;
+}  /* is_non_null_Confirm */
+
+/**
+ * The given pointer will be dereferenced, add non-null Confirms.
+ *
+ * @param ptr    a node representing an address
+ * @param block  the block of the dereferencing instruction
+ * @param env    environment
+ */
+static void insert_non_null(ir_node *ptr, ir_node *block, env_t *env) {
+	const ir_edge_t *edge, *next;
+	ir_node         *c = NULL;
+
+	foreach_out_edge_safe(ptr, edge, next) {
+		ir_node *succ = get_edge_src_irn(edge);
+		int     pos;
+		ir_node *blk;
+
+
+		/* for now, we place a Confirm only in front of a Cmp */
+		if (! is_Cmp(succ))
+			continue;
+
+		pos = get_edge_src_pos(edge);
+		blk = get_effective_use_block(succ, pos);
+
+		if (block_dominates(block, blk)) {
+			/*
+			 * Ok, we found a usage of ptr in a block
+			 * dominated by the Load/Store block.
+			 * We can replace the input with a Confirm(ptr, !=, NULL).
+			 */
+			if (c == NULL) {
+				ir_mode *mode = get_irn_mode(ptr);
+				c = new_Const(get_mode_null(mode));
+
+				c = new_r_Confirm(block, ptr, c, pn_Cmp_Lg);
+			}
+
+			set_irn_n(succ, pos, c);
+			DB((dbg, LEVEL_2, "Replacing input %d of node %+F with %+F\n", pos, succ, c));
+
+			env->num_non_null += 1;
+			env->num_confirms += 1;
+		}
+	}
+}  /* insert_non_null */
+
+/**
+ * Pre-walker: Called for every node to insert Confirm nodes
+ */
+static void insert_Confirm(ir_node *node, void *env) {
+	ir_node *ptr;
+
+	switch (get_irn_opcode(node)) {
+	case iro_Block:
+		insert_Confirm_in_block(node, env);
+		break;
+	case iro_Load:
+		ptr = get_Load_ptr(node);
+		if (! is_non_null_Confirm(ptr))
+			insert_non_null(ptr, get_nodes_block(node), env);
+		break;
+	case iro_Store:
+		ptr = get_Store_ptr(node);
+		if (! is_non_null_Confirm(ptr))
+			insert_non_null(ptr, get_nodes_block(node), env);
+		break;
+	default:
+		break;
+	}
 }  /* insert_Confirm */
 
 /*
@@ -301,6 +554,11 @@ void construct_confirms(ir_graph *irg) {
 	env_t env;
 	int edges_active = edges_activated(irg);
 
+
+	FIRM_DBG_REGISTER(dbg, "firm.ana.confirm");
+
+	remove_critical_cf_edges(irg);
+
 	/* we need dominance info */
 	assure_doms(irg);
 
@@ -315,9 +573,15 @@ void construct_confirms(ir_graph *irg) {
 	env.num_confirms = 0;
 	env.num_consts   = 0;
 	env.num_eq       = 0;
-
-	/* now, visit all blocks and add Confirms where possible */
-	irg_block_walk_graph(irg, insert_Confirm, NULL, &env);
+	env.num_non_null = 0;
+
+	if (get_opt_global_null_ptr_elimination()) {
+		/* do global NULL test elimination */
+		irg_walk_graph(irg, insert_Confirm, NULL, &env);
+	} else {
+		/* now, visit all blocks and add Confirms where possible */
+		irg_block_walk_graph(irg, insert_Confirm_in_block, NULL, &env);
+	}
 
 	if (env.num_confirms | env.num_consts | env.num_eq) {
 		/* we have add nodes or changed DF edges */
@@ -327,39 +591,54 @@ void construct_confirms(ir_graph *irg) {
 		set_irg_loopinfo_inconsistent(irg);
 	}
 
-#if 0
-	printf("# Confirms inserted : %u\n", env.num_confirms);
-	printf("# Const replacements: %u\n", env.num_consts);
-	printf("# node equalities   : %u\n", env.num_eq);
-#endif
+	DB((dbg, LEVEL_1, "# Confirms inserted : %u\n", env.num_confirms));
+	DB((dbg, LEVEL_1, "# Const replacements: %u\n", env.num_consts));
+	DB((dbg, LEVEL_1, "# node equalities   : %u\n", env.num_eq));
+	DB((dbg, LEVEL_1, "# non-null Confirms : %u\n", env.num_non_null));
 
 	/* deactivate edges if they where off */
 	if (! edges_active)
 		edges_deactivate(irg);
 }  /* construct_confirms */
 
+/* Construct a pass. */
+ir_graph_pass_t *construct_confirms_pass(const char *name) {
+	return def_graph_pass(name ? name : "confirm", construct_confirms);
+}  /* construct_confirms_pass */
+
+#if 0
 /**
  * Post-walker: Remove Confirm nodes
  */
 static void rem_Confirm(ir_node *n, void *env) {
 	(void) env;
-	if (get_irn_op(n) == op_Confirm) {
+	if (is_Confirm(n)) {
 		ir_node *value = get_Confirm_value(n);
 		if (value != n)
 			exchange(n, value);
 		else {
 			/*
-			 * Strange: a Confirm is it's own bound. This can happen
+			 * Strange: a Confirm is its own bound. This can happen
 			 * in dead blocks when Phi nodes are already removed.
 			 */
 			exchange(n, new_Bad());
 		}
 	}
 }  /* rem_Confirm */
+#endif
 
 /*
  * Remove all Confirm nodes from a graph.
  */
 void remove_confirms(ir_graph *irg) {
-	irg_walk_graph(irg, NULL, rem_Confirm, NULL);
+	int rem = get_opt_remove_confirm();
+
+	set_opt_remove_confirm(1);
+	optimize_graph_df(irg);
+	set_opt_remove_confirm(rem);
 }  /* remove_confirms */
+
+/* Construct a pass. */
+ir_graph_pass_t *remove_confirms_pass(const char *name) {
+	return def_graph_pass(name ? name : "rem_confirm", remove_confirms);
+}  /* remove_confirms_pass */