X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fcondeval.c;h=f55729119552f4653551e5a1cd2c307fa012c625;hb=6d3394bf4a3f3c2868634837d70389115cdca589;hp=ceba05c15c467735c806a4f37b4a05ce27fec1a7;hpb=e30e5834fd8c1c3a7d28fc66e99b91a84993bde8;p=libfirm

diff --git a/ir/opt/condeval.c b/ir/opt/condeval.c
index ceba05c15..f55729119 100644
--- a/ir/opt/condeval.c
+++ b/ir/opt/condeval.c
@@ -24,14 +24,12 @@
  * @author  Christoph Mallon, Matthias Braun
  * @version $Id$
  */
-#ifdef HAVE_CONFIG_H
 #include "config.h"
-#endif
 
 #include "iroptimize.h"
 
 #include <assert.h>
-#include "array.h"
+#include "array_t.h"
 #include "debug.h"
 #include "ircons.h"
 #include "irgmod.h"
@@ -45,6 +43,7 @@
 #include "irgraph.h"
 #include "tv.h"
 #include "opt_confirms.h"
+#include "iropt_dbg.h"
 
 #undef AVOID_PHIB
 
@@ -69,7 +68,11 @@ static void add_pred(ir_node* node, ir_node* x)
 	set_irn_in(node, n + 1, ins);
 }
 
-static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
+static ir_node *ssa_second_def;
+static ir_node *ssa_second_def_block;
+
+static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode,
+                                           int first)
 {
 	int i;
 	int n_cfgpreds;
@@ -78,11 +81,20 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
 	ir_node **in;
 
 	/* This is needed because we create bads sometimes */
-	if(is_Bad(block))
+	if (is_Bad(block))
 		return new_Bad();
 
+	/* the other defs can't be marked for cases where a user of the original
+	 * value is in the same block as the alternative definition.
+	 * In this case we mustn't use the alternative definition.
+	 * So we keep a flag that indicated wether we walked at least 1 block
+	 * away and may use the alternative definition */
+	if (block == ssa_second_def_block && !first) {
+		return ssa_second_def;
+	}
+
 	/* already processed this block? */
-	if(irn_visited(block)) {
+	if (irn_visited(block)) {
 		ir_node *value = (ir_node*) get_irn_link(block);
 		return value;
 	}
@@ -90,11 +102,11 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
 	irg = get_irn_irg(block);
 	assert(block != get_irg_start_block(irg));
 
-	/* a Blocks with only 1 predecessor need no Phi */
+	/* a Block with only 1 predecessor needs no Phi */
 	n_cfgpreds = get_Block_n_cfgpreds(block);
-	if(n_cfgpreds == 1) {
+	if (n_cfgpreds == 1) {
 		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
-		ir_node *value      = search_def_and_create_phis(pred_block, mode);
+		ir_node *value      = search_def_and_create_phis(pred_block, mode, 0);
 
 		set_irn_link(block, value);
 		mark_irn_visited(block);
@@ -113,7 +125,7 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
 	/* set Phi predecessors */
 	for(i = 0; i < n_cfgpreds; ++i) {
 		ir_node *pred_block = get_Block_cfgpred_block(block, i);
-		ir_node *pred_val = search_def_and_create_phis(pred_block, mode);
+		ir_node *pred_val   = search_def_and_create_phis(pred_block, mode, 0);
 
 		set_irn_n(phi, i, pred_val);
 	}
@@ -126,35 +138,30 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
  * first value (the users are determined through the out-edges of the value).
  * Uses the irn_visited flags. Works without using the dominance tree.
  */
-static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_vals)
+static void construct_ssa(ir_node *orig_block, ir_node *orig_val,
+                          ir_node *second_block, ir_node *second_val)
 {
-	int i;
 	ir_graph *irg;
 	ir_mode *mode;
 	const ir_edge_t *edge;
 	const ir_edge_t *next;
-	ir_node *value;
 
-	assert(n_vals == 2);
+	/* no need to do anything */
+	if (orig_val == second_val)
+		return;
 
-	irg = get_irn_irg(vals[0]);
+	irg = get_irn_irg(orig_val);
 	inc_irg_visited(irg);
 
-	mode = get_irn_mode(vals[0]);
-	for(i = 0; i < n_vals; ++i) {
-		ir_node *value = vals[i];
-		ir_node *value_block = blocks[i];
+	mode = get_irn_mode(orig_val);
+	set_irn_link(orig_block, orig_val);
+	mark_irn_visited(orig_block);
 
-		assert(get_irn_mode(value) == mode || is_Bad(value));
-
-		set_irn_link(value_block, value);
-		mark_irn_visited(value_block);
-	}
+	ssa_second_def_block = second_block;
+	ssa_second_def       = second_val;
 
 	/* Only fix the users of the first, i.e. the original node */
-	value = vals[0];
-
-	foreach_out_edge_safe(value, edge, next) {
+	foreach_out_edge_safe(orig_val, edge, next) {
 		ir_node *user = get_edge_src_irn(edge);
 		int j = get_edge_src_pos(edge);
 		ir_node *user_block = get_nodes_block(user);
@@ -164,16 +171,13 @@ static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_
 		if (is_End(user))
 			continue;
 
-		if (user_block == blocks[1])
-			continue;
-
 		DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j)));
 
-		if(is_Phi(user)) {
+		if (is_Phi(user)) {
 			ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
-			newval = search_def_and_create_phis(pred_block, mode);
+			newval = search_def_and_create_phis(pred_block, mode, 1);
 		} else {
-			newval = search_def_and_create_phis(user_block, mode);
+			newval = search_def_and_create_phis(user_block, mode, 1);
 		}
 
 		/* don't fix newly created Phis from the SSA construction */
@@ -202,7 +206,7 @@ typedef struct condeval_env_t {
 	pn_Cmp         pnc;        /**< The Compare mode of the Compare node. */
 	ir_node       *cnst;
 	tarval        *tv;
-	unsigned long  visited_nr;
+	ir_visited_t   visited_nr;
 
 	ir_node       *cnst_pred;   /**< the block before the constant */
 	int            cnst_pos;    /**< the pos to the constant block (needed to
@@ -218,7 +222,7 @@ static ir_node *copy_and_fix_node(const condeval_env_t *env, ir_node *block,
 	if (is_Phi(node)) {
 		copy = get_Phi_pred(node, j);
 		/* we might have to evaluate a Phi-cascade */
-		if(get_irn_visited(copy) >= env->visited_nr) {
+		if (get_irn_visited(copy) >= env->visited_nr) {
 			copy = get_irn_link(copy);
 		}
 	} else {
@@ -232,14 +236,15 @@ static ir_node *copy_and_fix_node(const condeval_env_t *env, ir_node *block,
 			ir_node *pred     = get_irn_n(copy, i);
 			ir_node *new_pred;
 
-			if(get_nodes_block(pred) != block)
+			if (get_nodes_block(pred) != block)
 				continue;
 
-			if(get_irn_visited(pred) >= env->visited_nr) {
+			if (get_irn_visited(pred) >= env->visited_nr) {
 				new_pred = get_irn_link(pred);
 			} else {
 				new_pred = copy_and_fix_node(env, block, copy_block, j, pred);
 			}
+			DB((dbg, LEVEL_2, ">> Set Pred of %+F to %+F\n", copy, new_pred));
 			set_irn_n(copy, i, new_pred);
 		}
 	}
@@ -290,7 +295,7 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block,
 				int pos             = get_edge_src_pos(edge);
 				ir_node *user_block = get_nodes_block(user);
 
-				if(user_block == block)
+				if (user_block == block)
 					continue;
 
 				cmp_copy = exact_copy(pred);
@@ -307,18 +312,17 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block,
 		/* we might hit values in blocks that have already been processed by a
 		 * recursive find_phi_with_const() call */
 		assert(get_irn_visited(copy) <= env->visited_nr);
-		if(get_irn_visited(copy) >= env->visited_nr) {
+		if (get_irn_visited(copy) >= env->visited_nr) {
 			ir_node *prev_copy = get_irn_link(copy);
-			if(prev_copy != NULL)
+			if (prev_copy != NULL)
 				set_irn_link(node, prev_copy);
 		}
 	}
 
 	/* fix data-flow (and reconstruct SSA if needed) */
 	foreach_out_edge(block, edge) {
-		ir_node *vals[2];
-		ir_node *blocks[2];
 		ir_node *node = get_edge_src_irn(edge);
+		ir_node *copy_node;
 		ir_mode *mode;
 
 		if (is_Block(node)) {
@@ -337,11 +341,8 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block,
 
 		DB((dbg, LEVEL_2, ">> Fixing users of %+F\n", node));
 
-		blocks[0] = block;
-		vals[0] = node;
-		blocks[1] = copy_block;
-		vals[1] = get_irn_link(node);
-		construct_ssa(blocks, vals, 2);
+		copy_node = get_irn_link(node);
+		construct_ssa(block, node, copy_block, copy_node);
 	}
 }
 
@@ -411,9 +412,8 @@ static ir_node *find_const_or_confirm(condeval_env_t *env, ir_node *jump, ir_nod
 {
 	ir_node *block = get_nodes_block(jump);
 
-	if (irn_visited(value))
+	if (irn_visited_else_mark(value))
 		return NULL;
-	mark_irn_visited(value);
 
 	if (is_Const_or_Confirm(value)) {
 		if (eval_cmp(env, value) <= 0) {
@@ -437,11 +437,11 @@ static ir_node *find_const_or_confirm(condeval_env_t *env, ir_node *jump, ir_nod
 		return block;
 	}
 
-	if(is_Phi(value)) {
+	if (is_Phi(value)) {
 		int i, arity;
 
 		/* the Phi has to be in the same Block as the Jmp */
-		if(get_nodes_block(value) != block) {
+		if (get_nodes_block(value) != block) {
 			return NULL;
 		}
 
@@ -452,13 +452,13 @@ static ir_node *find_const_or_confirm(condeval_env_t *env, ir_node *jump, ir_nod
 			ir_node *cfgpred  = get_Block_cfgpred(block, i);
 
 			copy_block = find_const_or_confirm(env, cfgpred, phi_pred);
-			if(copy_block == NULL)
+			if (copy_block == NULL)
 				continue;
 
 			/* copy duplicated nodes in copy_block and fix SSA */
 			copy_and_fix(env, block, copy_block, i);
 
-			if(copy_block == get_nodes_block(cfgpred)) {
+			if (copy_block == get_nodes_block(cfgpred)) {
 				env->cnst_pred = block;
 				env->cnst_pos  = i;
 			}
@@ -476,10 +476,9 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 {
 	ir_node *block = get_nodes_block(jump);
 
-	if(irn_visited(value)) {
+	if (irn_visited_else_mark(value)) {
 		return NULL;
 	}
-	mark_irn_visited(value);
 
 	if (is_Const_or_Confirm(value)) {
 		tarval *tv = get_Const_or_Confirm_tarval(value);
@@ -503,11 +502,11 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 
 		return block;
 	}
-	if(is_Phi(value)) {
+	if (is_Phi(value)) {
 		int i, arity;
 
 		/* the Phi has to be in the same Block as the Jmp */
-		if(get_nodes_block(value) != block)
+		if (get_nodes_block(value) != block)
 			return NULL;
 
 		arity = get_irn_arity(value);
@@ -517,13 +516,13 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 			ir_node *cfgpred  = get_Block_cfgpred(block, i);
 
 			copy_block = find_candidate(env, cfgpred, phi_pred);
-			if(copy_block == NULL)
+			if (copy_block == NULL)
 				continue;
 
 			/* copy duplicated nodes in copy_block and fix SSA */
 			copy_and_fix(env, block, copy_block, i);
 
-			if(copy_block == get_nodes_block(cfgpred)) {
+			if (copy_block == get_nodes_block(cfgpred)) {
 				env->cnst_pred = block;
 				env->cnst_pos  = i;
 			}
@@ -532,12 +531,12 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 			return copy_block;
 		}
 	}
-	if(is_Proj(value)) {
+	if (is_Proj(value)) {
 		ir_node *left;
 		ir_node *right;
 		int      pnc;
 		ir_node *cmp = get_Proj_pred(value);
-		if(!is_Cmp(cmp))
+		if (!is_Cmp(cmp))
 			return NULL;
 
 		left  = get_Cmp_left(cmp);
@@ -546,7 +545,7 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 
 		/* we assume that the constant is on the right side, swap left/right
 		 * if needed */
-		if(is_Const(left)) {
+		if (is_Const(left)) {
 			ir_node *t = left;
 			left       = right;
 			right      = t;
@@ -554,15 +553,15 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 			pnc        = get_inversed_pnc(pnc);
 		}
 
-		if(!is_Const(right))
+		if (!is_Const(right))
 			return 0;
 
-		if(get_nodes_block(left) != block) {
+		if (get_nodes_block(left) != block) {
 			return 0;
 		}
 
 		/* negate condition when we're looking for the false block */
-		if(env->tv == tarval_b_false) {
+		if (env->tv == tarval_b_false) {
 			pnc = get_negated_pnc(pnc, get_irn_mode(right));
 		}
 
@@ -600,10 +599,10 @@ static void cond_eval(ir_node* block, void* data)
 	ir_node *copy_block;
 	int      selector_evaluated;
 	const ir_edge_t *edge, *next;
-	ir_node* bad;
+	ir_node *bad;
 	size_t   cnst_pos;
 
-	if(get_Block_n_cfgpreds(block) != 1)
+	if (get_Block_n_cfgpreds(block) != 1)
 		return;
 
 	projx = get_Block_cfgpred(block, 0);
@@ -622,24 +621,24 @@ static void cond_eval(ir_node* block, void* data)
 
 	/* handle cases that can be immediately evaluated */
 	selector_evaluated = -1;
-	if(is_Proj(selector)) {
+	if (is_Proj(selector)) {
 		ir_node *cmp = get_Proj_pred(selector);
-		if(is_Cmp(cmp)) {
+		if (is_Cmp(cmp)) {
 			ir_node *left  = get_Cmp_left(cmp);
 			ir_node *right = get_Cmp_right(cmp);
-			if(is_Const(left) && is_Const(right)) {
+			if (is_Const(left) && is_Const(right)) {
 				int     pnc      = get_Proj_proj(selector);
 				tarval *tv_left  = get_Const_tarval(left);
 				tarval *tv_right = get_Const_tarval(right);
 
 				selector_evaluated = eval_cmp_tv(pnc, tv_left, tv_right);
-				if(selector_evaluated < 0)
+				if (selector_evaluated < 0)
 					return;
 			}
 		}
 	} else if (is_Const_or_Confirm(selector)) {
 		tarval *tv = get_Const_or_Confirm_tarval(selector);
-		if(tv == tarval_b_true) {
+		if (tv == tarval_b_true) {
 			selector_evaluated = 1;
 		} else {
 			assert(tv == tarval_b_false);
@@ -650,20 +649,21 @@ static void cond_eval(ir_node* block, void* data)
 	env.cnst_pred = NULL;
 	if (get_Proj_proj(projx) == pn_Cond_false) {
 		env.tv = tarval_b_false;
-		if(selector_evaluated >= 0)
+		if (selector_evaluated >= 0)
 			selector_evaluated = !selector_evaluated;
 	} else {
 		env.tv = tarval_b_true;
 	}
 
-	if(selector_evaluated == 0) {
+	if (selector_evaluated == 0) {
 		bad = new_Bad();
 		exchange(projx, bad);
 		*changed = 1;
 		return;
-	} else if(selector_evaluated == 1) {
+	} else if (selector_evaluated == 1) {
 		dbg_info *dbgi = get_irn_dbg_info(selector);
 		ir_node  *jmp  = new_rd_Jmp(dbgi, current_ir_graph, get_nodes_block(projx));
+		DBG_OPT_COND_EVAL(projx, jmp);
 		exchange(projx, jmp);
 		*changed = 1;
 		return;
@@ -688,7 +688,7 @@ static void cond_eval(ir_node* block, void* data)
 	foreach_out_edge_safe(env.cnst_pred, edge, next) {
 		ir_node *node = get_edge_src_irn(edge);
 
-		if(is_Phi(node))
+		if (is_Phi(node))
 			set_Phi_pred(node, cnst_pos, bad);
 	}
 
@@ -727,10 +727,10 @@ void opt_cond_eval(ir_graph* irg)
 		set_irg_doms_inconsistent(irg);
 		set_irg_extblk_inconsistent(irg);
 		set_irg_loopinfo_inconsistent(irg);
+		set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
 
 		/* Dead code might be created. Optimize it away as it is dangerous
 		 * to call optimize_df() an dead code. */
 		optimize_cf(irg);
 	}
-
 }