X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firopt.c;h=481f9cd661191f007cb8888de66c0bb26ad13a8e;hb=357886575cb0becb5bd9be376fde49b57edd5385;hp=3fa187a723391e2246fdfbfe24e384363137cc75;hpb=6f068af98daa4725d60e5d23a8f98ec2841cfa44;p=libfirm

diff --git a/ir/ir/iropt.c b/ir/ir/iropt.c
index 3fa187a72..481f9cd66 100644
--- a/ir/ir/iropt.c
+++ b/ir/ir/iropt.c
@@ -327,6 +327,28 @@ static ir_tarval *computed_value_Not(const ir_node *n)
 	return tarval_bad;
 }  /* computed_value_Not */
 
+/**
+ * Tests wether a shift shifts more bits than available in the mode
+ */
+static bool is_oversize_shift(const ir_node *n)
+{
+	ir_node   *count = get_binop_right(n);
+	ir_mode   *mode  = get_irn_mode(n);
+	ir_tarval *tv    = value_of(count);
+	long       modulo_shift;
+	long       shiftval;
+	if (tv == tarval_bad)
+		return false;
+	if (!tarval_is_long(tv))
+		return false;
+	shiftval     = get_tarval_long(tv);
+	modulo_shift = get_mode_modulo_shift(mode);
+	if (shiftval < 0 || (modulo_shift > 0 && shiftval >= modulo_shift))
+		return false;
+
+	return shiftval >= (long)get_mode_size_bits(mode);
+}
+
 /**
  * Return the value of a Shl.
  */
@@ -341,6 +363,10 @@ static ir_tarval *computed_value_Shl(const ir_node *n)
 	if ((ta != tarval_bad) && (tb != tarval_bad)) {
 		return tarval_shl(ta, tb);
 	}
+
+	if (is_oversize_shift(n))
+		return get_mode_null(get_irn_mode(n));
+
 	return tarval_bad;
 }  /* computed_value_Shl */
 
@@ -358,6 +384,9 @@ static ir_tarval *computed_value_Shr(const ir_node *n)
 	if ((ta != tarval_bad) && (tb != tarval_bad)) {
 		return tarval_shr(ta, tb);
 	}
+	if (is_oversize_shift(n))
+		return get_mode_null(get_irn_mode(n));
+
 	return tarval_bad;
 }  /* computed_value_Shr */
 
@@ -395,17 +424,52 @@ static ir_tarval *computed_value_Rotl(const ir_node *n)
 	return tarval_bad;
 }  /* computed_value_Rotl */
 
+bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode)
+{
+	ir_mode *mode = get_irn_mode(node);
+	if (get_mode_arithmetic(mode) != irma_twos_complement
+	    || get_mode_arithmetic(dest_mode) != irma_twos_complement)
+	    return false;
+
+	if (is_Shl(node)) {
+		ir_node *count = get_Shl_right(node);
+		if (is_Const(count)) {
+			ir_tarval *tv = get_Const_tarval(count);
+			if (tarval_is_long(tv)) {
+				long shiftval = get_tarval_long(tv);
+				long destbits = get_mode_size_bits(dest_mode);
+				if (shiftval >= destbits
+				    && shiftval < (long)get_mode_modulo_shift(mode))
+					return true;
+			}
+		}
+	}
+	if (is_And(node)) {
+		ir_node *right = get_And_right(node);
+		if (is_Const(right)) {
+			ir_tarval *tv     = get_Const_tarval(right);
+			ir_tarval *conved = tarval_convert_to(tv, dest_mode);
+			return tarval_is_null(conved);
+		}
+	}
+	return false;
+}
+
 /**
  * Return the value of a Conv.
  */
 static ir_tarval *computed_value_Conv(const ir_node *n)
 {
-	ir_node *a = get_Conv_op(n);
-	ir_tarval *ta = value_of(a);
+	ir_node   *a    = get_Conv_op(n);
+	ir_tarval *ta   = value_of(a);
+	ir_mode   *mode = get_irn_mode(n);
 
 	if (ta != tarval_bad)
 		return tarval_convert_to(ta, get_irn_mode(n));
 
+	if (ir_zero_when_converted(a, mode))
+		return get_mode_null(mode);
+
 	return tarval_bad;
 }  /* computed_value_Conv */
 
@@ -661,72 +725,6 @@ static ir_op_ops *firm_set_default_computed_value(ir_opcode code, ir_op_ops *ops
 #undef CASE
 }  /* firm_set_default_computed_value */
 
-/**
- * Returns a equivalent block for another block.
- * If the block has only one predecessor, this is
- * the equivalent one. If the only predecessor of a block is
- * the block itself, this is a dead block.
- *
- * If both predecessors of a block are the branches of a binary
- * Cond, the equivalent block is Cond's block.
- *
- * If all predecessors of a block are bad or lies in a dead
- * block, the current block is dead as well.
- */
-static ir_node *equivalent_node_Block(ir_node *n)
-{
-	ir_node *oldn = n;
-	int     n_preds;
-	ir_graph *irg;
-
-	/* don't optimize labeled blocks */
-	if (has_Block_entity(n))
-		return n;
-	if (!get_Block_matured(n))
-		return n;
-
-	n_preds = get_Block_n_cfgpreds(n);
-
-	irg = get_irn_irg(n);
-
-	/* Straightening: a single entry Block following a single exit Block
-	 * can be merged. */
-	if (n_preds == 1) {
-		ir_node *pred = get_Block_cfgpred(n, 0);
-
-		if (is_Jmp(pred)) {
-			ir_node *pred_block = get_nodes_block(pred);
-			DBG_OPT_STG(n, pred_block);
-			return pred_block;
-		}
-	} else if (n_preds == 2) {
-		/* Test whether Cond jumps twice to this block
-		 * The more general case which more than 2 predecessors is handles
-		 * in optimize_cf(), we handle only this special case for speed here.
-		 */
-		ir_node *a = get_Block_cfgpred(n, 0);
-		ir_node *b = get_Block_cfgpred(n, 1);
-
-		if (is_Proj(a) && is_Proj(b)) {
-			ir_node *cond = get_Proj_pred(a);
-
-		    if (cond == get_Proj_pred(b) && is_Cond(cond) &&
-		        get_irn_mode(get_Cond_selector(cond)) == mode_b) {
-				/* Also a single entry Block following a single exit Block.
-				 * Phis have twice the same operand and will be optimized away.
-				 */
-				n = get_nodes_block(cond);
-				DBG_OPT_IFSIM1(oldn, a, b, n);
-			}
-		}
-	}
-
-	return n;
-}  /* equivalent_node_Block */
-
-/* We do not evaluate Cond here as we replace it by a new node, a Jmp.
-   See transform_node_Proj_Cond(). */
-
 /**
  * Optimize operations that are commutative and have neutral 0,
  * so a op 0 = 0 op a = a.
@@ -1576,7 +1574,6 @@ static ir_op_ops *firm_set_default_equivalent_node(ir_opcode code, ir_op_ops *op
 		break
 
 	switch (code) {
-	CASE(Block);
 	CASE(Eor);
 	CASE(Add);
 	CASE(Shl);
@@ -3977,19 +3974,6 @@ static ir_node *transform_node_Cmp(ir_node *n)
 
 				/* the following reassociations work only for == and != */
 				if (relation == ir_relation_equal || relation == ir_relation_less_greater) {
-
-#if 0 /* Might be not that good in general */
-					/* a-b == 0  ==>  a == b,  a-b != 0  ==>  a != b */
-					if (tarval_is_null(tv) && is_Sub(left)) {
-						right = get_Sub_right(left);
-						left  = get_Sub_left(left);
-
-						tv = value_of(right);
-						changed = 1;
-						DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
-					}
-#endif
-
 					if (tv != tarval_bad) {
 						/* a-c1 == c2  ==>  a == c2+c1,  a-c1 != c2  ==>  a != c2+c1 */
 						if (is_Sub(left)) {
@@ -4353,35 +4337,34 @@ static ir_node *transform_node_Proj(ir_node *proj)
 	return proj;
 }  /* transform_node_Proj */
 
+static bool is_block_unreachable(const ir_node *block)
+{
+	const ir_graph *irg = get_irn_irg(block);
+	if (!is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK))
+		return false;
+	return get_Block_dom_depth(block) < 0;
+}
+
 static ir_node *transform_node_Block(ir_node *block)
 {
-	ir_graph *irg = get_irn_irg(block);
+	ir_graph *irg   = get_irn_irg(block);
+	int       arity = get_irn_arity(block);
+	ir_node  *bad   = NULL;
+	int       i;
 
 	if (!is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK))
 		return block;
-	/* don't optimize labeled blocks */
-	if (has_Block_entity(block))
-		return block;
-	if (!get_Block_matured(block))
-		return block;
-
-	/* remove blocks with only Bad inputs (or no inputs) */
-	{
-		int i;
-		int n_cfgpreds = get_Block_n_cfgpreds(block);
 
-		for (i = 0; i < n_cfgpreds; ++i) {
-			ir_node *pred = get_Block_cfgpred(block, i);
-			if (!is_Bad(pred))
-				break;
-		}
-		/* only bad unreachable inputs? It's unreachable code (unless it is the
-		 * start or end block) */
-		if (i >= n_cfgpreds && block != get_irg_start_block(irg)
-		    && block != get_irg_end_block(irg)) {
-		    return new_r_Bad(irg, mode_BB);
-		}
+	for (i = 0; i < arity; ++i) {
+		ir_node *pred       = get_Block_cfgpred(block, i);
+		ir_node *pred_block = get_nodes_block(pred);
+		if (!is_Bad(pred) && !is_block_unreachable(pred_block))
+			continue;
+		if (bad == NULL)
+			bad = new_r_Bad(irg, mode_X);
+		set_irn_n(block, i, bad);
 	}
+
 	return block;
 }
 
@@ -4397,11 +4380,11 @@ static ir_node *transform_node_Phi(ir_node *phi)
 	/* Set phi-operands for bad-block inputs to bad */
 	for (i = 0; i < n; ++i) {
 		ir_node *pred = get_Block_cfgpred(block, i);
-		if (!is_Bad(pred))
-			continue;
-		if (bad == NULL)
-			bad = new_r_Bad(irg, mode);
-		set_irn_n(phi, i, bad);
+		if (is_Bad(pred) || is_block_unreachable(get_nodes_block(pred))) {
+			if (bad == NULL)
+				bad = new_r_Bad(irg, mode);
+			set_irn_n(phi, i, bad);
+		}
 	}
 
 	/* Move Confirms down through Phi nodes. */
@@ -4728,9 +4711,11 @@ static ir_node *transform_node_shift(ir_node *n)
 {
 	ir_node *left, *right;
 	ir_mode *mode;
+	ir_mode *count_mode;
 	ir_tarval *tv1, *tv2, *res;
 	ir_node *in[2], *irn, *block;
 	ir_graph *irg;
+	int       modulo_shf;
 
 	left = get_binop_left(n);
 
@@ -4739,7 +4724,7 @@ static ir_node *transform_node_shift(ir_node *n)
 		return n;
 
 	right = get_binop_right(n);
-	tv1 = value_of(right);
+	tv1   = value_of(right);
 	if (tv1 == tarval_bad)
 		return n;
 
@@ -4747,37 +4732,55 @@ static ir_node *transform_node_shift(ir_node *n)
 	if (tv2 == tarval_bad)
 		return n;
 
-	res  = tarval_add(tv1, tv2);
-	mode = get_irn_mode(n);
-	irg  = get_irn_irg(n);
+	count_mode = get_tarval_mode(tv1);
+	if (get_tarval_mode(tv2) != count_mode) {
+		/* TODO: search bigger mode or something and convert... */
+		return n;
+	}
 
-	/* beware: a simple replacement works only, if res < modulo shift */
-	if (!is_Rotl(n)) {
-		int modulo_shf = get_mode_modulo_shift(mode);
-		if (modulo_shf > 0) {
-			ir_tarval *modulo = new_tarval_from_long(modulo_shf,
-			                                         get_tarval_mode(res));
+	mode       = get_irn_mode(n);
+	modulo_shf = get_mode_modulo_shift(mode);
 
-			assert(modulo_shf >= (int) get_mode_size_bits(mode));
+	if (modulo_shf > 0) {
+		ir_tarval *modulo_mask = new_tarval_from_long(modulo_shf-1, count_mode);
 
-			/* shifting too much */
-			if (!(tarval_cmp(res, modulo) & ir_relation_less)) {
-				if (is_Shrs(n)) {
-					ir_node  *block = get_nodes_block(n);
-					dbg_info *dbgi  = get_irn_dbg_info(n);
-					ir_mode  *smode  = get_irn_mode(right);
-					ir_node  *cnst  = new_r_Const_long(irg, smode, get_mode_size_bits(mode) - 1);
-					return new_rd_Shrs(dbgi, block, get_binop_left(left), cnst, mode);
-				}
+		/* I'm not so sure what happens in one complement... */
+		assert(get_mode_arithmetic(count_mode) == irma_twos_complement);
+		/* modulo shifts should always be a power of 2 (otherwise modulo_mask
+		 * above will be invalid) */
+		assert(modulo_shf<=0 || is_po2(modulo_shf));
 
-				return new_r_Const(irg, get_mode_null(mode));
+		tv1 = tarval_and(tv1, modulo_mask);
+		tv2 = tarval_and(tv2, modulo_mask);
+	}
+	res = tarval_add(tv1, tv2);
+	irg = get_irn_irg(n);
+
+	/* beware: a simple replacement works only, if res < modulo shift */
+	if (is_Rotl(n)) {
+		int        bits   = get_mode_size_bits(mode);
+		ir_tarval *modulo = new_tarval_from_long(bits, count_mode);
+		res = tarval_mod(res, modulo);
+	} else {
+		long       bits      = get_mode_size_bits(mode);
+		ir_tarval *mode_size = new_tarval_from_long(bits, count_mode);
+
+		/* shifting too much */
+		if (!(tarval_cmp(res, mode_size) & ir_relation_less)) {
+			if (is_Shrs(n)) {
+				ir_node  *block = get_nodes_block(n);
+				dbg_info *dbgi  = get_irn_dbg_info(n);
+				ir_mode  *smode = get_irn_mode(right);
+				ir_node  *cnst  = new_r_Const_long(irg, smode, get_mode_size_bits(mode) - 1);
+				return new_rd_Shrs(dbgi, block, get_binop_left(left), cnst, mode);
 			}
+
+			return new_r_Const(irg, get_mode_null(mode));
 		}
-	} else {
-		res = tarval_mod(res, new_tarval_from_long(get_mode_size_bits(mode), get_tarval_mode(res)));
 	}
 
 	/* ok, we can replace it */
+	assert(modulo_shf >= (int) get_mode_size_bits(mode));
 	block = get_nodes_block(n);
 
 	in[0] = get_binop_left(left);
@@ -4788,7 +4791,7 @@ static ir_node *transform_node_shift(ir_node *n)
 	DBG_OPT_ALGSIM0(n, irn, FS_OPT_REASSOC_SHIFT);
 
 	return transform_node(irn);
-}  /* transform_node_shift */
+}
 
 /**
  * normalisation: (x & c1) >> c2   to   (x >> c2) & (c1 >> c2)
@@ -5096,6 +5099,16 @@ static ir_node *transform_node_Shrs(ir_node *n)
 	ir_node *b    = get_Shrs_right(n);
 	ir_mode *mode = get_irn_mode(n);
 
+	if (is_oversize_shift(n)) {
+		ir_node  *block = get_nodes_block(n);
+		dbg_info *dbgi  = get_irn_dbg_info(n);
+		ir_mode  *cmode = get_irn_mode(b);
+		long      val   = get_mode_size_bits(cmode)-1;
+		ir_graph *irg   = get_irn_irg(n);
+		ir_node  *cnst  = new_r_Const_long(irg, cmode, val);
+		return new_rd_Shrs(dbgi, block, a, cnst, mode);
+	}
+
 	HANDLE_BINOP_PHI((eval_func) tarval_shrs, a, b, c, mode);
 	n = transform_node_shift(n);
 
@@ -5216,10 +5229,14 @@ static ir_node *transform_node_End(ir_node *n)
 
 	for (i = j = 0; i < n_keepalives; ++i) {
 		ir_node *ka = get_End_keepalive(n, i);
-		if (is_Bad(ka)) {
-			/* no need to keep Bad */
+		ir_node *block;
+		/* no need to keep Bad */
+		if (is_Bad(ka))
+			continue;
+		/* dont keep unreachable code */
+		block = is_Block(ka) ? ka : get_nodes_block(ka);
+		if (is_block_unreachable(block))
 			continue;
-		}
 		in[j++] = ka;
 	}
 	if (j != n_keepalives)
@@ -6194,18 +6211,6 @@ void visit_all_identities(ir_graph *irg, irg_walk_func visit, void *env)
 	current_ir_graph = rem;
 }  /* visit_all_identities */
 
-static bool is_unreachable(ir_node *node)
-{
-	ir_op *op = get_irn_op(node);
-
-	/* Code in "Bad" blocks is unreachable and can be replaced by Bad */
-	if (op != op_Block && is_Bad(get_nodes_block(node))) {
-	    return true;
-	}
-
-	return false;
-}
-
 /**
  * These optimizations deallocate nodes from the obstack.
  * It can only be called if it is guaranteed that no other nodes
@@ -6223,15 +6228,6 @@ ir_node *optimize_node(ir_node *n)
 	/* Always optimize Phi nodes: part of the construction. */
 	if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
 
-	/* Remove nodes with dead (Bad) input.
-	   Run always for transformation induced Bads. */
-	if (is_unreachable(n)) {
-		ir_mode *mode = get_irn_mode(n);
-		edges_node_deleted(n);
-		irg_kill_node(irg, n);
-		return new_r_Bad(irg, mode);
-	}
-
 	/* constant expression evaluation / constant folding */
 	if (get_opt_constant_folding()) {
 		/* neither constants nor Tuple values can be evaluated */
@@ -6330,14 +6326,6 @@ ir_node *optimize_in_place_2(ir_node *n)
 	if (iro == iro_Deleted)
 		return n;
 
-	/* Remove nodes with dead (Bad) input.
-	   Run always for transformation induced Bads.  */
-	if (is_unreachable(n)) {
-		ir_graph *irg  = get_irn_irg(n);
-		ir_mode  *mode = get_irn_mode(n);
-		return new_r_Bad(irg, mode);
-	}
-
 	/* constant expression evaluation / constant folding */
 	if (get_opt_constant_folding()) {
 		/* neither constants nor Tuple values can be evaluated */
@@ -6410,8 +6398,6 @@ ir_node *optimize_in_place(ir_node *n)
 
 	if (get_opt_global_cse())
 		set_irg_pinned(irg, op_pin_state_floats);
-	if (get_irg_outs_state(irg) == outs_consistent)
-		set_irg_outs_inconsistent(irg);
 
 	/* FIXME: Maybe we could also test whether optimizing the node can
 	   change the control graph. */