X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fcondeval.c;h=850becec6ce45ff9f8dc25e7a70bf0df6c63416b;hb=afbbc0b1ccd684c4c24bfd43d0f994123245f39f;hp=9926b8c275b87243bebeff42579f79f0d44fb8d8;hpb=82caacf18daf84d2fab123eb22d133b6cfbfcb3e;p=libfirm

diff --git a/ir/opt/condeval.c b/ir/opt/condeval.c
index 9926b8c27..850becec6 100644
--- a/ir/opt/condeval.c
+++ b/ir/opt/condeval.c
@@ -31,7 +31,7 @@
 #include "iroptimize.h"
 
 #include <assert.h>
-#include "array.h"
+#include "array_t.h"
 #include "debug.h"
 #include "ircons.h"
 #include "irgmod.h"
@@ -46,7 +46,7 @@
 #include "tv.h"
 #include "opt_confirms.h"
 
-//#define AVOID_PHIB
+#undef AVOID_PHIB
 
 DEBUG_ONLY(static firm_dbg_module_t *dbg);
 
@@ -69,7 +69,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;
@@ -77,11 +81,20 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
 	ir_node *phi;
 	ir_node **in;
 
-	// This is needed because we create bads sometimes
+	/* This is needed because we create bads sometimes */
 	if(is_Bad(block))
 		return new_Bad();
 
-	// already processed this block?
+	/* 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)) {
 		ir_node *value = (ir_node*) get_irn_link(block);
 		return value;
@@ -90,18 +103,18 @@ 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));
 
-	// blocks with only 1 pred need no phi
+	/* a Block with only 1 predecessor needs no Phi */
 	n_cfgpreds = get_Block_n_cfgpreds(block);
 	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);
 		return value;
 	}
 
-	// create a new phi
+	/* create a new Phi */
 	NEW_ARR_A(ir_node*, in, n_cfgpreds);
 	for(i = 0; i < n_cfgpreds; ++i)
 		in[i] = new_Unknown(mode);
@@ -110,10 +123,10 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
 	set_irn_link(block, phi);
 	mark_irn_visited(block);
 
-	// set phi preds
+	/* 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,57 +139,49 @@ 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];
-
-		assert(get_irn_mode(value) == mode || is_Bad(value));
+	mode = get_irn_mode(orig_val);
+	set_irn_link(orig_block, orig_val);
+	mark_irn_visited(orig_block);
 
-		set_irn_link(value_block, value);
-		mark_irn_visited(value_block);
-	}
-
-	// Only fix the users of the first, i.e. the original node
-	value = vals[0];
+	ssa_second_def_block = second_block;
+	ssa_second_def       = second_val;
 
-	foreach_out_edge_safe(value, edge, next) {
+	/* Only fix the users of the first, i.e. the original node */
+	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);
 		ir_node *newval;
 
-		// ignore keeps
-		if(get_irn_op(user) == op_End)
-			continue;
-
-		if (user_block == blocks[1])
+		/* ignore keeps */
+		if (is_End(user))
 			continue;
 
 		DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j)));
 
 		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
+		/* don't fix newly created Phis from the SSA construction */
 		if (newval != user) {
 			DB((dbg, LEVEL_4, ">>>> Setting input %d of %+F to %+F\n", j, user, newval));
 			set_irn_n(user, j, newval);
@@ -199,10 +204,10 @@ static void split_critical_edge(ir_node *block, int pos) {
 typedef struct condeval_env_t {
 	ir_node       *true_block;
 	ir_node       *cmp;        /**< The Compare node that might be partial evaluated */
-	pn_Cmp         pnc;        /**< The Compare mode of teh Compare node. */
+	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
@@ -217,7 +222,7 @@ static ir_node *copy_and_fix_node(const condeval_env_t *env, ir_node *block,
 	/* we can evaluate Phis right now, all other nodes get copied */
 	if (is_Phi(node)) {
 		copy = get_Phi_pred(node, j);
-		/* we might have to evaluate a phi-cascades */
+		/* we might have to evaluate a Phi-cascade */
 		if(get_irn_visited(copy) >= env->visited_nr) {
 			copy = get_irn_link(copy);
 		}
@@ -240,6 +245,7 @@ static ir_node *copy_and_fix_node(const condeval_env_t *env, ir_node *block,
 			} 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);
 		}
 	}
@@ -271,7 +277,7 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block,
 		if (mode == mode_X || is_Cond(node))
 			continue;
 #ifdef AVOID_PHIB
-		/* we may not copy mode_b nodes, because this could produce phi with
+		/* we may not copy mode_b nodes, because this could produce Phi with
 		 * mode_bs which can't be handled in all backends. Instead we duplicate
 		 * the node and move it to its users */
 		if (mode == mode_b) {
@@ -305,7 +311,7 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block,
 		copy = copy_and_fix_node(env, block, copy_block, j, node);
 
 		/* we might hit values in blocks that have already been processed by a
-		 * recursive find_phi_with_const call */
+		 * recursive find_phi_with_const() call */
 		assert(get_irn_visited(copy) <= env->visited_nr);
 		if(get_irn_visited(copy) >= env->visited_nr) {
 			ir_node *prev_copy = get_irn_link(copy);
@@ -316,9 +322,8 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block,
 
 	/* 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 +342,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);
 	}
 }
 
@@ -407,13 +409,12 @@ static tarval *get_Const_or_Confirm_tarval(const ir_node *node) {
 	return get_Const_tarval(node);
 }
 
-static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value)
+static ir_node *find_const_or_confirm(condeval_env_t *env, ir_node *jump, ir_node *value)
 {
 	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) {
@@ -426,12 +427,12 @@ static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value)
 			env->true_block, block
 		));
 
-		// adjust true_block to point directly towards our jump
+		/* adjust true_block to point directly towards our jump */
 		add_pred(env->true_block, jump);
 
 		split_critical_edge(env->true_block, 0);
 
-		// we need a bigger visited nr when going back
+		/* we need a bigger visited nr when going back */
 		env->visited_nr++;
 
 		return block;
@@ -440,7 +441,7 @@ static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value)
 	if(is_Phi(value)) {
 		int i, arity;
 
-		/* the phi has to be in the same block as the jump */
+		/* the Phi has to be in the same Block as the Jmp */
 		if(get_nodes_block(value) != block) {
 			return NULL;
 		}
@@ -451,7 +452,7 @@ static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value)
 			ir_node *phi_pred = get_Phi_pred(value, i);
 			ir_node *cfgpred  = get_Block_cfgpred(block, i);
 
-			copy_block = find_const(env, cfgpred, phi_pred);
+			copy_block = find_const_or_confirm(env, cfgpred, phi_pred);
 			if(copy_block == NULL)
 				continue;
 
@@ -476,10 +477,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);
@@ -493,12 +493,12 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 			env->true_block, block
 		));
 
-		// adjust true_block to point directly towards our jump
+		/* adjust true_block to point directly towards our jump */
 		add_pred(env->true_block, jump);
 
 		split_critical_edge(env->true_block, 0);
 
-		// we need a bigger visited nr when going back
+		/* we need a bigger visited nr when going back */
 		env->visited_nr++;
 
 		return block;
@@ -506,7 +506,7 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 	if(is_Phi(value)) {
 		int i, arity;
 
-		// the phi has to be in the same block as the jump
+		/* the Phi has to be in the same Block as the Jmp */
 		if(get_nodes_block(value) != block)
 			return NULL;
 
@@ -528,7 +528,7 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 				env->cnst_pos  = i;
 			}
 
-			// return now as we can't process more possibilities in 1 run
+			/* return now as we can't process more possibilities in 1 run */
 			return copy_block;
 		}
 	}
@@ -566,12 +566,12 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
 			pnc = get_negated_pnc(pnc, get_irn_mode(right));
 		}
 
-		// (recursively) look if a pred of a phi is a constant
+		/* (recursively) look if a pred of a Phi is a constant or a Confirm */
 		env->cmp  = cmp;
 		env->pnc  = pnc;
 		env->cnst = right;
 
-		return find_const(env, jump, left);
+		return find_const_or_confirm(env, jump, left);
 	}
 
 	return NULL;
@@ -616,7 +616,7 @@ static void cond_eval(ir_node* block, void* data)
 		return;
 
 	selector = get_Cond_selector(cond);
-	// TODO handle switch Conds
+	/* TODO handle switch Conds */
 	if (get_irn_mode(selector) != mode_b)
 		return;
 
@@ -669,7 +669,7 @@ static void cond_eval(ir_node* block, void* data)
 		return;
 	}
 
-	// (recursively) look if a pred of a phi is a constant
+	/* (recursively) look if a pred of a Phi is a constant or a Confirm */
 	env.true_block = block;
 	inc_irg_visited(current_ir_graph);
 	env.visited_nr = get_irg_visited(current_ir_graph);
@@ -679,12 +679,12 @@ static void cond_eval(ir_node* block, void* data)
 		return;
 
 	/* we have to remove the edge towards the pred as the pred now
-	 * jumps into the true_block. We also have to shorten phis
+	 * jumps into the true_block. We also have to shorten Phis
 	 * in our block because of this */
 	bad      = new_Bad();
 	cnst_pos = env.cnst_pos;
 
-	/* shorten phis */
+	/* shorten Phis */
 	foreach_out_edge_safe(env.cnst_pred, edge, next) {
 		ir_node *node = get_edge_src_irn(edge);
 
@@ -710,8 +710,7 @@ void opt_cond_eval(ir_graph* irg)
 	normalize_proj_nodes(irg);
 
 	edges_assure(irg);
-	set_using_irn_link(irg);
-	set_using_irn_visited(irg);
+	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
 
 	changed = 0;
 	do {
@@ -720,8 +719,7 @@ void opt_cond_eval(ir_graph* irg)
 		changed |= rerun;
 	} while (rerun);
 
-	clear_using_irn_visited(irg);
-	clear_using_irn_link(irg);
+	ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
 
 	if (changed) {
 		/* control flow changed, some blocks may become dead */
@@ -734,5 +732,4 @@ void opt_cond_eval(ir_graph* irg)
 		 * to call optimize_df() an dead code. */
 		optimize_cf(irg);
 	}
-
 }