X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firopt.c;h=02ed4e83d026f7b7d6ea38c964dbde9d13a39abc;hb=b23a433074a5148302ec95041241ce029cdadb89;hp=21cd60e4e9cd54eee8842730a9c44cbb092022b8;hpb=930f2dd6bb1a970ce54f485775945c855b3b30a5;p=libfirm

diff --git a/ir/ir/iropt.c b/ir/ir/iropt.c
index 21cd60e4e..02ed4e83d 100644
--- a/ir/ir/iropt.c
+++ b/ir/ir/iropt.c
@@ -1121,7 +1121,7 @@ static ir_node *equivalent_node_Or(ir_node *n) {
 }  /* equivalent_node_Or */
 
 /**
- * Optimize a & 0b1...1 = 0b1...1 & a =  a & a = a.
+ * Optimize a & 0b1...1 = 0b1...1 & a = a & a = (a|X) & a = a.
  */
 static ir_node *equivalent_node_And(ir_node *n) {
 	ir_node *oldn = n;
@@ -1132,13 +1132,35 @@ static ir_node *equivalent_node_And(ir_node *n) {
 	if (a == b) {
 		n = a;    /* And has it's own neutral element */
 		DBG_OPT_ALGSIM0(oldn, n, FS_OPT_AND);
-	} else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
+		return n;
+	}
+	if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
 		n = b;
 		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
-	} else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
+		return n;
+	}
+	if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
 		n = a;
 		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
+		return n;
 	}
+	if (is_Or(a)) {
+		if (b == get_Or_left(a) || b == get_Or_right(a)) {
+			/* (a|X) & a */
+			n = b;
+			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
+			return n;
+		}
+	}
+	if (is_Or(b)) {
+		if (a == get_Or_left(b) || a == get_Or_right(b)) {
+			/* a & (a|X) */
+			n = a;
+			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
+			return n;
+		}
+	}
+
 	return n;
 }  /* equivalent_node_And */
 
@@ -1675,30 +1697,6 @@ static ir_op_ops *firm_set_default_equivalent_node(ir_opcode code, ir_op_ops *op
 #undef CASE
 }  /* firm_set_default_equivalent_node */
 
-/**
- * Do node specific optimizations of nodes predecessors.
- */
-static void optimize_preds(ir_node *n) {
-	switch (get_irn_opcode(n)) {
-
-	case iro_Cmp: {	/* We don't want Cast as input to Cmp. */
-		ir_node *a = get_Cmp_left(n), *b = get_Cmp_right(n);
-
-		if (get_irn_op(a) == op_Cast) {
-			a = get_Cast_op(a);
-			set_Cmp_left(n, a);
-		}
-		if (get_irn_op(b) == op_Cast) {
-			b = get_Cast_op(b);
-			set_Cmp_right(n, b);
-		}
-		break;
-	}
-
-	default: break;
-	} /* end switch */
-}  /* optimize_preds */
-
 /**
  * Returns non-zero if a node is a Phi node
  * with all predecessors constant.
@@ -2025,23 +2023,44 @@ static ir_node *transform_node_Add(ir_node *n) {
 				}
 			}
 		}
-		/* Here we rely on constants be on the RIGHT side */
-		if (get_mode_arithmetic(mode) == irma_twos_complement &&
-		         is_Not(a) && classify_Const(b) == CNST_ONE) {
-			/* ~x + 1 = -x */
-			ir_node *op = get_Not_op(a);
-			ir_node *blk = get_irn_n(n, -1);
-			n = new_rd_Minus(get_irn_dbg_info(n), current_ir_graph, blk, op, mode);
-			DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_PLUS_1);
-			return n;
+		if (get_mode_arithmetic(mode) == irma_twos_complement) {
+			/* Here we rely on constants be on the RIGHT side */
+			if (is_Not(a)) {
+				ir_node *op = get_Not_op(a);
+
+				if (classify_Const(b) == CNST_ONE) {
+					/* ~x + 1 = -x */
+					ir_node *blk = get_irn_n(n, -1);
+					n = new_rd_Minus(get_irn_dbg_info(n), current_ir_graph, blk, op, mode);
+					DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_PLUS_1);
+					return n;
+				}
+				if (op == b) {
+					/* ~x + x = -1 */
+					ir_node *blk = get_irn_n(n, -1);
+					n = new_r_Const(current_ir_graph, blk, mode, get_mode_minus_one(mode));
+					DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_X_NOT_X);
+					return n;
+				}
+			}
+			if (is_Not(b)) {
+				ir_node *op = get_Not_op(b);
+
+				if (op == a) {
+					/* ~x + x = -1 */
+					ir_node *blk = get_irn_n(n, -1);
+					n = new_r_Const(current_ir_graph, blk, mode, get_mode_minus_one(mode));
+					DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_X_NOT_X);
+					return n;
+				}
+			}
 		}
 	}
 	return n;
 }  /* transform_node_Add */
 
 /* returns -cnst */
-static ir_node* const_negate(ir_node* cnst)
-{
+static ir_node *const_negate(ir_node *cnst) {
 	tarval   *tv    = tarval_neg(get_Const_tarval(cnst));
 	dbg_info *dbgi  = get_irn_dbg_info(cnst);
 	ir_graph *irg   = get_irn_irg(cnst);
@@ -2294,11 +2313,26 @@ restart:
 
 		add = new_r_Add(current_ir_graph, blk, y, b, mode);
 
-		set_Sub_left(n, x);
-		set_Sub_right(n, add);
-		DBG_OPT_ALGSIM0(n, n, FS_OPT_SUB_SUB_X_Y_Z);
+		n = new_rd_Sub(get_irn_dbg_info(n), current_ir_graph, blk, x, add, mode);
+		DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_SUB_X_Y_Z);
 		return n;
 	}
+
+	if (get_mode_arithmetic(mode) == irma_twos_complement) {
+		if (is_Const(a) && is_Not(b)) {
+			/* c - ~X = X + (c+1) */
+			tarval *tv = get_Const_tarval(a);
+
+			tv = tarval_add(tv, get_mode_one(mode));
+			if (tv != tarval_bad) {
+				ir_node *blk = get_irn_n(n, -1);
+				ir_node *c = new_r_Const(current_ir_graph, blk, mode, tv);
+				n = new_rd_Add(get_irn_dbg_info(n), current_ir_graph, blk, get_Not_op(b), c, mode);
+				DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_C_NOT_X);
+				return n;
+			}
+		}
+	}
 	return n;
 }  /* transform_node_Sub */
 
@@ -2836,7 +2870,6 @@ static ir_node *transform_bitwise_distributive(ir_node *n,
 				set_binop_right(n, c);
 			}
 
-
 			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_SHIFT_AND);
 			return n;
 		}
@@ -2849,14 +2882,14 @@ static ir_node *transform_bitwise_distributive(ir_node *n,
  * Transform an And.
  */
 static ir_node *transform_node_And(ir_node *n) {
-	ir_node *c, *oldn;
+	ir_node *c, *oldn = n;
 	ir_node *a = get_And_left(n);
 	ir_node *b = get_And_right(n);
 
 	HANDLE_BINOP_PHI(tarval_and, a,b,c);
 
 	/* we can evaluate 2 Projs of the same Cmp */
-	if(get_irn_mode(n) == mode_b && is_Proj(a) && is_Proj(b)) {
+	if (get_irn_mode(n) == mode_b && is_Proj(a) && is_Proj(b)) {
 		ir_node *pred_a = get_Proj_pred(a);
 		ir_node *pred_b = get_Proj_pred(b);
 		if(pred_a == pred_b) {
@@ -2871,6 +2904,45 @@ static ir_node *transform_node_And(ir_node *n) {
 			                   new_pnc);
 		}
 	}
+	if (is_Or(a)) {
+		if (is_Not(b)) {
+			ir_node *op = get_Not_op(b);
+			if (is_And(op)) {
+				ir_node *ba = get_And_left(op);
+				ir_node *bb = get_And_right(op);
+
+				/* it's enough to test the following cases due to normalization! */
+				if (get_Or_left(a) == ba && get_Or_right(a) == bb) {
+					/* (a|b) & ~(a&b) = a^b */
+					ir_node *block = get_nodes_block(n);
+
+					n = new_rd_Eor(get_irn_dbg_info(n), current_ir_graph, block, ba, bb, get_irn_mode(n));
+					DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_TO_EOR);
+					return n;
+				}
+			}
+		}
+	}
+	if (is_Or(b)) {
+		if (is_Not(a)) {
+			ir_node *op = get_Not_op(a);
+			if (is_And(op)) {
+				ir_node *aa = get_And_left(op);
+				ir_node *ab = get_And_right(op);
+
+				/* it's enough to test the following cases due to normalization! */
+				if (get_Or_left(b) == aa && get_Or_right(b) == ab) {
+					/* (a|b) & ~(a&b) = a^b */
+					ir_node *block = get_nodes_block(n);
+
+					n = new_rd_Eor(get_irn_dbg_info(n), current_ir_graph, block, aa, ab, get_irn_mode(n));
+					DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_TO_EOR);
+					return n;
+				}
+			}
+		}
+
+	}
 
 	n = transform_bitwise_distributive(n, transform_node_And);
 
@@ -2969,6 +3041,7 @@ static ir_node *transform_node_Not(ir_node *n) {
  * Transform a Minus.
  * Optimize:
  *   -(~x) = x + 1
+ *   -(a-b) = b - a
  */
 static ir_node *transform_node_Minus(ir_node *n) {
 	ir_node *c, *oldn = n;
@@ -2978,15 +3051,52 @@ static ir_node *transform_node_Minus(ir_node *n) {
 	HANDLE_UNOP_PHI(tarval_neg,a,c);
 
 	mode = get_irn_mode(a);
-	if (get_mode_arithmetic(mode) == irma_twos_complement && is_Not(a)) {
-		/* -(~x) = x + 1 */
-		ir_node *op   = get_Not_op(a);
-		tarval *tv    = get_mode_one(mode);
-		ir_node *blk  = get_irn_n(n, -1);
-		ir_node *c    = new_r_Const(current_ir_graph, blk, mode, tv);
-		n = new_rd_Add(get_irn_dbg_info(n), current_ir_graph, blk, op, c, mode);
-		DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_MINUS_NOT);
-	} else if (is_Sub(a)) {
+	if (get_mode_arithmetic(mode) == irma_twos_complement) {
+		/* the following rules are only to twos-complement */
+		if (is_Not(a)) {
+			/* -(~x) = x + 1 */
+			ir_node *op   = get_Not_op(a);
+			tarval *tv    = get_mode_one(mode);
+			ir_node *blk  = get_irn_n(n, -1);
+			ir_node *c    = new_r_Const(current_ir_graph, blk, mode, tv);
+			n = new_rd_Add(get_irn_dbg_info(n), current_ir_graph, blk, op, c, mode);
+			DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_MINUS_NOT);
+			return n;
+		}
+		if (is_Shr(a)) {
+			ir_node *c = get_Shr_right(a);
+
+			if (is_Const(c)) {
+				tarval *tv = get_Const_tarval(c);
+
+				if (tarval_is_long(tv) && get_tarval_long(tv) == get_mode_size_bits(mode) - 1) {
+					/* -(a >>u (size-1)) = a >>s (size-1) */
+					ir_node *v = get_Shr_left(a);
+
+					n = new_rd_Shrs(get_irn_dbg_info(n), current_ir_graph, get_irn_n(n, -1), v, c, mode);
+					DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_PREDICATE);
+					return n;
+				}
+			}
+		}
+		if (is_Shrs(a)) {
+			ir_node *c = get_Shrs_right(a);
+
+			if (is_Const(c)) {
+				tarval *tv = get_Const_tarval(c);
+
+				if (tarval_is_long(tv) && get_tarval_long(tv) == get_mode_size_bits(mode) - 1) {
+					/* -(a >>s (size-1)) = a >>u (size-1) */
+					ir_node *v = get_Shrs_left(a);
+
+					n = new_rd_Shr(get_irn_dbg_info(n), current_ir_graph, get_irn_n(n, -1), v, c, mode);
+					DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_PREDICATE);
+					return n;
+				}
+			}
+		}
+	}
+	if (is_Sub(a)) {
 		/* - (a-b) = b - a */
 		ir_node *la  = get_Sub_left(a);
 		ir_node *ra  = get_Sub_right(a);
@@ -2994,6 +3104,7 @@ static ir_node *transform_node_Minus(ir_node *n) {
 
 		n = new_rd_Sub(get_irn_dbg_info(n), current_ir_graph, blk, ra, la, mode);
 		DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_MINUS_SUB);
+		return n;
 	}
 
 	return n;
@@ -3221,41 +3332,118 @@ static ir_node *transform_node_Proj_Cmp(ir_node *proj) {
 	/* Remove unnecessary conversions */
 	/* TODO handle constants */
 	if (is_Conv(left) && is_Conv(right)) {
-		ir_mode* mode        = get_irn_mode(left);
-		ir_node* op_left     = get_Conv_op(left);
-		ir_node* op_right    = get_Conv_op(right);
-		ir_mode* mode_left   = get_irn_mode(op_left);
-		ir_mode* mode_right  = get_irn_mode(op_right);
+		ir_mode *mode        = get_irn_mode(left);
+		ir_node *op_left     = get_Conv_op(left);
+		ir_node *op_right    = get_Conv_op(right);
+		ir_mode *mode_left   = get_irn_mode(op_left);
+		ir_mode *mode_right  = get_irn_mode(op_right);
 
 		if (smaller_mode(mode_left, mode) && smaller_mode(mode_right, mode)) {
-			ir_graph* irg   = current_ir_graph;
-			ir_node*  block = get_nodes_block(n);
-			ir_node*  new_left;
-			ir_node*  new_right;
+			ir_graph *irg   = current_ir_graph;
+			ir_node  *block = get_nodes_block(n);
 
 			if (mode_left == mode_right) {
-				new_left  = op_left;
-				new_right = op_right;
+				left  = op_left;
+				right = op_right;
+				changed |= 1;
 			} else if (smaller_mode(mode_left, mode_right)) {
-				new_left  = new_r_Conv(irg, block, op_left, mode_right);
-				new_right = op_right;
+				left  = new_r_Conv(irg, block, op_left, mode_right);
+				right = op_right;
+				changed |= 1;
 			} else if (smaller_mode(mode_right, mode_left)) {
-				new_left  = op_left;
-				new_right = new_r_Conv(irg, block, op_right, mode_left);
-			} else {
-				goto no_remove_conv;
+				left  = op_left;
+				right = new_r_Conv(irg, block, op_right, mode_left);
+				changed |= 1;
 			}
-			left  = new_left;
-			right = new_right;
-			set_Cmp_left( n, left);
-			set_Cmp_right(n, right);
-no_remove_conv:;
+		}
+	}
+
+	/* remove Casts */
+	if (is_Cast(left))
+		left = get_Cast_op(left);
+	if (is_Cast(right))
+		right = get_Cast_op(right);
+
+	/* remove operation of both sides if possible */
+	if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
+		ir_opcode lop = get_irn_opcode(left);
+
+		if (lop == get_irn_opcode(right)) {
+			ir_node *ll, *lr, *rl, *rr;
+
+			/* same operation on both sides, try to remove */
+			switch (lop) {
+			case iro_Not:
+			case iro_Minus:
+				/* ~a CMP ~b => a CMP b, -a CMP -b ==> a CMP b */
+				left  = get_unop_op(left);
+				right = get_unop_op(right);
+				changed |= 1;
+				break;
+			case iro_Add:
+				ll = get_Add_left(left);
+				lr = get_Add_right(left);
+				rl = get_Add_left(right);
+				rr = get_Add_right(right);
+
+				if (ll == rl) {
+					/* X + a CMP X + b ==> a CMP b */
+					left  = lr;
+					right = rr;
+					changed |= 1;
+				} else if (ll == rr) {
+					/* X + a CMP b + X ==> a CMP b */
+					left  = lr;
+					right = rl;
+					changed |= 1;
+				} else if (lr == rl) {
+					/* a + X CMP X + b ==> a CMP b */
+					left  = ll;
+					right = rr;
+					changed |= 1;
+				} else if (lr == rr) {
+					/* a + X CMP b + X ==> a CMP b */
+					left  = ll;
+					right = rl;
+					changed |= 1;
+				}
+				break;
+			case iro_Sub:
+				ll = get_Sub_left(left);
+				lr = get_Sub_right(left);
+				rl = get_Sub_left(right);
+				rr = get_Sub_right(right);
+
+				if (ll == rl) {
+					/* X - a CMP X - b ==> a CMP b */
+					left  = lr;
+					right = rr;
+					changed |= 1;
+				} else if (lr == rr) {
+					/* a - X CMP b - X ==> a CMP b */
+					left  = ll;
+					right = rl;
+					changed |= 1;
+				}
+				break;
+			case iro_Rot:
+				if (get_Rot_right(left) == get_Rot_right(right)) {
+					/* a ROT X CMP b ROT X */
+					left  = get_Rot_left(left);
+					right = get_Rot_left(right);
+					changed |= 1;
+				}
+				break;
+			default:
+				break;
+			}
+
 		}
 	}
 
 	if (get_irn_mode(left) == mode_b) {
-		ir_graph* irg   = current_ir_graph;
-		ir_node*  block = get_nodes_block(n);
+		ir_graph *irg   = current_ir_graph;
+		ir_node  *block = get_nodes_block(n);
 
 		switch (proj_nr) {
 			case pn_Cmp_Le: return new_r_Or( irg, block, new_r_Not(irg, block, left, mode_b), right, mode_b);
@@ -3272,14 +3460,14 @@ no_remove_conv:;
 
 	/*
 	 * First step: normalize the compare op
-	 * by placing the constant on the right site
+	 * by placing the constant on the right side
 	 * or moving the lower address node to the left.
 	 * We ignore the case that both are constants
 	 * this case should be optimized away.
 	 */
-	if (get_irn_op(right) == op_Const) {
+	if (is_Const(right)) {
 		c = right;
-	} else if (get_irn_op(left) == op_Const) {
+	} else if (is_Const(left)) {
 		c     = left;
 		left  = right;
 		right = c;
@@ -3315,16 +3503,23 @@ no_remove_conv:;
 			 * be optimized, see this:
 			 * -MININT < 0 =/=> MININT > 0 !!!
 			 */
-			if (get_opt_constant_folding() && get_irn_op(left) == op_Minus &&
+			if (is_Minus(left) &&
 				(!mode_overflow_on_unary_Minus(mode) ||
 				(mode_is_int(mode) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)))) {
-				left = get_Minus_op(left);
 				tv = tarval_neg(tv);
 
 				if (tv != tarval_bad) {
+					left = get_Minus_op(left);
 					proj_nr = get_inversed_pnc(proj_nr);
 					changed |= 2;
 				}
+			} else if (is_Not(left) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)) {
+				tv = tarval_not(tv);
+
+				if (tv != tarval_bad) {
+					left = get_Not_op(left);
+					changed |= 2;
+				}
 			}
 
 			/* for integer modes, we have more */
@@ -3361,14 +3556,12 @@ no_remove_conv:;
 				if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
 
 					/* a-b == 0  ==>  a == b,  a-b != 0  ==>  a != b */
-					if (classify_tarval(tv) == TV_CLASSIFY_NULL && get_irn_op(left) == op_Sub) {
-						right = get_Sub_right(left);
+					if (classify_tarval(tv) == TV_CLASSIFY_NULL && is_Sub(left)) {
+						right =get_Sub_right(left);
 						left  = get_Sub_left(left);
 
 						tv = value_of(right);
-						if (tv != tarval_bad) {
-							changed = 1;
-						}
+						changed = 1;
 					}
 
 					if (tv != tarval_bad) {
@@ -3446,8 +3639,7 @@ no_remove_conv:;
 			 *
 			 * if C is a single Bit constant.
 			 */
-			if ((proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) &&
-				(get_irn_op(left) == op_And)) {
+			if ((proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) && is_And(left)) {
 				if (tarval_is_single_bit(tv)) {
 					/* check for Constant's match. We have check hare the tarvals,
 					   because our const might be changed */
@@ -3472,8 +3664,7 @@ no_remove_conv:;
 			right = new_Const(mode, tv);
 
 		/* create a new compare */
-		n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block,
-			left, right);
+		n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block, left, right);
 
 		set_Proj_pred(proj, n);
 		set_Proj_proj(proj, proj_nr);
@@ -4733,8 +4924,6 @@ ir_node *optimize_node(ir_node *n) {
 	    (iro == iro_Block)  )  /* Flags tested local. */
 		n = equivalent_node(n);
 
-	optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
-
 	/* Common Subexpression Elimination.
 	 *
 	 * Checks whether n is already available.
@@ -4826,8 +5015,6 @@ ir_node *optimize_in_place_2(ir_node *n) {
 	    (iro == iro_Block)  )  /* Flags tested local. */
 		n = equivalent_node(n);
 
-	optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
-
 	/** common subexpression elimination **/
 	/* Checks whether n is already available. */
 	/* The block input is used to distinguish different subexpressions.  Right