X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firopt.c;h=ca58b2ef4eeb06915ab19343d0987be77cbe1dc5;hb=a08e6f04aa3669cff094f94a9484c7c2bb1314d0;hp=0a97728087a0cc91e0108a2714df8921de5cc967;hpb=cc3f1146d3ae570895ec956da0d3c963e7887fd2;p=libfirm

diff --git a/ir/ir/iropt.c b/ir/ir/iropt.c
index 0a9772808..ca58b2ef4 100644
--- a/ir/ir/iropt.c
+++ b/ir/ir/iropt.c
@@ -352,7 +352,7 @@ static ir_tarval *computed_value_Not(const ir_node *n)
 }  /* computed_value_Not */
 
 /**
- * Tests wether a shift shifts more bits than available in the mode
+ * Tests whether a shift shifts more bits than available in the mode
  */
 static bool is_oversize_shift(const ir_node *n)
 {
@@ -957,7 +957,7 @@ static ir_node *equivalent_node_Sub(ir_node *n)
 
 
 /**
- * Optimize an "self-inverse unary op", ie op(op(n)) = n.
+ * Optimize an "self-inverse unary op", i.e. op(op(n)) = n.
  *
  * @todo
  *   -(-a) == a, but might overflow two times.
@@ -2181,6 +2181,7 @@ restart:
 		}
 		DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_TO_ADD);
 		return n;
+#if 0
 	} else if (is_Mul(b)) { /* a - (b * C) -> a + (b * -C) */
 		ir_node *m_right = get_Mul_right(b);
 		if (is_Const(m_right)) {
@@ -2199,6 +2200,7 @@ restart:
 				return n;
 			}
 		}
+#endif
 	}
 
 	/* Beware of Sub(P, P) which cannot be optimized into a simple Minus ... */
@@ -2360,8 +2362,8 @@ restart:
 	}
 
 	if (get_mode_arithmetic(mode) == irma_twos_complement) {
+		/* c - ~X = X + (c+1) */
 		if (is_Const(a) && is_Not(b)) {
-			/* c - ~X = X + (c+1) */
 			ir_tarval *tv = get_Const_tarval(a);
 
 			tv = tarval_add(tv, get_mode_one(mode));
@@ -2374,6 +2376,24 @@ restart:
 				return n;
 			}
 		}
+		/* x-(x&y) = x & ~y */
+		if (is_And(b)) {
+			ir_node *and_left  = get_And_left(b);
+			ir_node *and_right = get_And_right(b);
+			if (and_right == a) {
+				ir_node *tmp = and_left;
+				and_left  = and_right;
+				and_right = tmp;
+			}
+			if (and_left == a) {
+				dbg_info *dbgi  = get_irn_dbg_info(n);
+				ir_node  *block = get_nodes_block(n);
+				ir_mode  *mode  = get_irn_mode(n);
+				ir_node  *notn  = new_rd_Not(dbgi, block, and_right, mode);
+				ir_node  *and   = new_rd_And(dbgi, block, a, notn, mode);
+				return and;
+			}
+		}
 	}
 	return n;
 }  /* transform_node_Sub */
@@ -2645,7 +2665,7 @@ make_tuple:
 
 		/* skip a potential Pin */
 		mem = skip_Pin(mem);
-		turn_into_tuple(n, pn_Div_max);
+		turn_into_tuple(n, pn_Div_max+1);
 		set_Tuple_pred(n, pn_Div_M,         mem);
 		set_Tuple_pred(n, pn_Div_X_regular, new_r_Jmp(blk));
 		set_Tuple_pred(n, pn_Div_X_except,  new_r_Bad(irg, mode_X));
@@ -2737,7 +2757,7 @@ make_tuple:
 
 		/* skip a potential Pin */
 		mem = skip_Pin(mem);
-		turn_into_tuple(n, pn_Mod_max);
+		turn_into_tuple(n, pn_Mod_max+1);
 		set_Tuple_pred(n, pn_Mod_M,         mem);
 		set_Tuple_pred(n, pn_Mod_X_regular, new_r_Jmp(blk));
 		set_Tuple_pred(n, pn_Mod_X_except,  new_r_Bad(irg, mode_X));
@@ -2771,7 +2791,7 @@ static ir_node *transform_node_Cond(ir_node *n)
 		   Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
 		ir_node *blk = get_nodes_block(n);
 		jmp = new_r_Jmp(blk);
-		turn_into_tuple(n, pn_Cond_max);
+		turn_into_tuple(n, pn_Cond_max+1);
 		if (ta == tarval_b_true) {
 			set_Tuple_pred(n, pn_Cond_false, new_r_Bad(irg, mode_X));
 			set_Tuple_pred(n, pn_Cond_true, jmp);
@@ -2907,6 +2927,186 @@ static ir_node *create_zero_const(ir_graph *irg, ir_mode *mode)
 	return cnst;
 }
 
+static bool is_shiftop(const ir_node *n)
+{
+	return is_Shl(n) || is_Shr(n) || is_Shrs(n) || is_Rotl(n);
+}
+
+/**
+ * normalisation: (x & c1) >> c2   to   (x >> c2) & (c1 >> c2)
+ *  (we can use:
+ *    - and, or, xor          instead of &
+ *    - Shl, Shr, Shrs, rotl  instead of >>
+ *    (with a special case for Or/Xor + Shrs)
+ *
+ * This normalisation is good for things like x-(x&y) esp. in 186.crafty.
+ */
+static ir_node *transform_node_shift_bitop(ir_node *n)
+{
+	ir_graph  *irg   = get_irn_irg(n);
+	ir_node   *right = get_binop_right(n);
+	ir_mode   *mode  = get_irn_mode(n);
+	ir_node   *left;
+	ir_node   *bitop_left;
+	ir_node   *bitop_right;
+	ir_op     *op_left;
+	ir_node   *block;
+	dbg_info  *dbgi;
+	ir_node   *new_shift;
+	ir_node   *new_bitop;
+	ir_node   *new_const;
+	ir_tarval *tv1;
+	ir_tarval *tv2;
+	ir_tarval *tv_shift;
+
+	if (is_irg_state(irg, IR_GRAPH_STATE_NORMALISATION2))
+		return n;
+
+	assert(is_Shrs(n) || is_Shr(n) || is_Shl(n) || is_Rotl(n));
+
+	if (!is_Const(right))
+		return n;
+
+	left    = get_binop_left(n);
+	op_left = get_irn_op(left);
+	if (op_left != op_And && op_left != op_Or && op_left != op_Eor)
+		return n;
+
+	/* doing it with Shrs is not legal if the Or/Eor affects the topmost bit */
+	if (is_Shrs(n) && (op_left == op_Or || op_left == op_Eor)) {
+		/* TODO: test if sign bit is affectes */
+		return n;
+	}
+
+	bitop_right = get_binop_right(left);
+	if (!is_Const(bitop_right))
+		return n;
+
+	bitop_left = get_binop_left(left);
+
+	block = get_nodes_block(n);
+	dbgi  = get_irn_dbg_info(n);
+	tv1   = get_Const_tarval(bitop_right);
+	tv2   = get_Const_tarval(right);
+
+	assert(get_tarval_mode(tv1) == mode);
+
+	if (is_Shl(n)) {
+		new_shift = new_rd_Shl(dbgi, block, bitop_left, right, mode);
+		tv_shift  = tarval_shl(tv1, tv2);
+	} else if (is_Shr(n)) {
+		new_shift = new_rd_Shr(dbgi, block, bitop_left, right, mode);
+		tv_shift  = tarval_shr(tv1, tv2);
+	} else if (is_Shrs(n)) {
+		new_shift = new_rd_Shrs(dbgi, block, bitop_left, right, mode);
+		tv_shift  = tarval_shrs(tv1, tv2);
+	} else {
+		assert(is_Rotl(n));
+		new_shift = new_rd_Rotl(dbgi, block, bitop_left, right, mode);
+		tv_shift  = tarval_rotl(tv1, tv2);
+	}
+
+	assert(get_tarval_mode(tv_shift) == mode);
+	irg       = get_irn_irg(n);
+	new_const = new_r_Const(irg, tv_shift);
+
+	if (op_left == op_And) {
+		new_bitop = new_rd_And(dbgi, block, new_shift, new_const, mode);
+	} else if (op_left == op_Or) {
+		new_bitop = new_rd_Or(dbgi, block, new_shift, new_const, mode);
+	} else {
+		assert(op_left == op_Eor);
+		new_bitop = new_rd_Eor(dbgi, block, new_shift, new_const, mode);
+	}
+
+	return new_bitop;
+}
+
+/**
+ * normalisation: (x >> c1) & c2   to   (x & (c2<<c1)) >> c1
+ *  (we can use:
+ *    - and, or, xor          instead of &
+ *    - Shl, Shr, Shrs, rotl  instead of >>
+ *    (with a special case for Or/Xor + Shrs)
+ *
+ * This normalisation is usually good for the backend since << C can often be
+ * matched as address-mode.
+ */
+static ir_node *transform_node_bitop_shift(ir_node *n)
+{
+	ir_graph  *irg   = get_irn_irg(n);
+	ir_node   *left  = get_binop_left(n);
+	ir_node   *right = get_binop_right(n);
+	ir_mode   *mode  = get_irn_mode(n);
+	ir_node   *shift_left;
+	ir_node   *shift_right;
+	ir_node   *block;
+	dbg_info  *dbg_bitop;
+	dbg_info  *dbg_shift;
+	ir_node   *new_bitop;
+	ir_node   *new_shift;
+	ir_node   *new_const;
+	ir_tarval *tv1;
+	ir_tarval *tv2;
+	ir_tarval *tv_bitop;
+
+	if (!is_irg_state(irg, IR_GRAPH_STATE_NORMALISATION2))
+		return n;
+
+	assert(is_And(n) || is_Or(n) || is_Eor(n));
+	if (!is_Const(right) || !is_shiftop(left))
+		return n;
+
+	shift_left  = get_binop_left(left);
+	shift_right = get_binop_right(left);
+	if (!is_Const(shift_right))
+		return n;
+
+	/* doing it with Shrs is not legal if the Or/Eor affects the topmost bit */
+	if (is_Shrs(left)) {
+		/* TODO this could be improved */
+		return n;
+	}
+
+	irg       = get_irn_irg(n);
+	block     = get_nodes_block(n);
+	dbg_bitop = get_irn_dbg_info(n);
+	dbg_shift = get_irn_dbg_info(left);
+	tv1       = get_Const_tarval(shift_right);
+	tv2       = get_Const_tarval(right);
+	assert(get_tarval_mode(tv2) == mode);
+
+	if (is_Shl(left)) {
+		tv_bitop = tarval_shr(tv2, tv1);
+	} else if (is_Shr(left)) {
+		tv_bitop = tarval_shl(tv2, tv1);
+	} else {
+		assert(is_Rotl(left));
+		tv_bitop = tarval_rotl(tv2, tarval_neg(tv1));
+	}
+	new_const = new_r_Const(irg, tv_bitop);
+
+	if (is_And(n)) {
+		new_bitop = new_rd_And(dbg_bitop, block, shift_left, new_const, mode);
+	} else if (is_Or(n)) {
+		new_bitop = new_rd_Or(dbg_bitop, block, shift_left, new_const, mode);
+	} else {
+		assert(is_Eor(n));
+		new_bitop = new_rd_Eor(dbg_bitop, block, shift_left, new_const, mode);
+	}
+
+	if (is_Shl(left)) {
+		new_shift = new_rd_Shl(dbg_shift, block, new_bitop, shift_right, mode);
+	} else if (is_Shr(left)) {
+		new_shift = new_rd_Shr(dbg_shift, block, new_bitop, shift_right, mode);
+	} else if (is_Rotl(left)) {
+		assert(is_Rotl(left));
+		new_shift = new_rd_Rotl(dbg_shift, block, new_bitop, shift_right, mode);
+	}
+
+	return new_shift;
+}
+
 /**
  * Transform an And.
  */
@@ -2933,20 +3133,21 @@ static ir_node *transform_node_And(ir_node *n)
 			ir_relation new_relation = a_relation & b_relation;
 			return new_rd_Cmp(dbgi, block, a_left, a_right, new_relation);
 		}
-		/* Cmp(a==0) and Cmp(b==0) can be optimized to Cmp(a|b==0) */
-		if (is_Const(a_right) && is_Const_null(a_right)
-				&& is_Const(b_right) && is_Const_null(b_right)
-				&& a_relation == b_relation && a_relation == ir_relation_equal
-				&& !mode_is_float(get_irn_mode(a_left))
-				&& !mode_is_float(get_irn_mode(b_left))) {
-			dbg_info *dbgi     = get_irn_dbg_info(n);
-			ir_node  *block    = get_nodes_block(n);
-			ir_mode  *mode     = get_irn_mode(a_left);
-			ir_node  *n_b_left = get_irn_mode(b_left) != mode ?
-				new_rd_Conv(dbgi, block, b_left, mode) : b_left;
-			ir_node  *or       = new_rd_Or(dbgi, block, a_left, n_b_left, mode);
-			ir_graph *irg      = get_irn_irg(n);
-			ir_node  *zero     = create_zero_const(irg, mode);
+		/* Cmp(a==b) and Cmp(c==d) can be optimized to Cmp((a^b)|(c^d)==0) */
+		if (a_relation == b_relation && a_relation == ir_relation_equal
+		    && !mode_is_float(get_irn_mode(a_left))
+		    && !mode_is_float(get_irn_mode(b_left))
+		    && values_in_mode(get_irn_mode(a_left), get_irn_mode(b_left))) {
+			dbg_info *dbgi   = get_irn_dbg_info(n);
+			ir_node  *block  = get_nodes_block(n);
+			ir_mode  *a_mode = get_irn_mode(a_left);
+			ir_mode  *b_mode = get_irn_mode(b_left);
+			ir_node  *xora   = new_rd_Eor(dbgi, block, a_left, a_right, a_mode);
+			ir_node  *xorb   = new_rd_Eor(dbgi, block, b_left, b_right, b_mode);
+			ir_node  *conv   = new_rd_Conv(dbgi, block, xorb, a_mode);
+			ir_node  *or     = new_rd_Or(dbgi, block, xora, conv, a_mode);
+			ir_graph *irg    = get_irn_irg(n);
+			ir_node  *zero   = create_zero_const(irg, a_mode);
 			return new_rd_Cmp(dbgi, block, or, zero, ir_relation_equal);
 		}
 	}
@@ -3070,6 +3271,8 @@ static ir_node *transform_node_And(ir_node *n)
 	}
 
 	n = transform_bitwise_distributive(n, transform_node_And);
+	if (is_And(n))
+		n = transform_node_bitop_shift(n);
 
 	return n;
 }  /* transform_node_And */
@@ -3156,6 +3359,9 @@ static ir_node *transform_node_Eor(ir_node *n)
 	}
 
 	n = transform_bitwise_distributive(n, transform_node_Eor);
+	if (is_Eor(n))
+		n = transform_node_bitop_shift(n);
+
 	return n;
 }  /* transform_node_Eor */
 
@@ -3614,30 +3820,51 @@ static ir_node *transform_node_Cmp(ir_node *n)
 	}
 
 	/* Remove unnecessary conversions */
-	/* TODO handle conv+constant */
 	if (is_Conv(left) && is_Conv(right)) {
-		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_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)
 				&& mode_left != mode_b && mode_right != mode_b) {
-			ir_node  *block = get_nodes_block(n);
+			ir_node *block = get_nodes_block(n);
 
 			if (mode_left == mode_right) {
-				left  = op_left;
-				right = op_right;
+				left    = op_left;
+				right   = op_right;
 				changed = true;
 				DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CONV_CONV);
 			} else if (smaller_mode(mode_left, mode_right)) {
-				left  = new_r_Conv(block, op_left, mode_right);
-				right = op_right;
+				left    = new_r_Conv(block, op_left, mode_right);
+				right   = op_right;
 				changed = true;
 				DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CONV);
 			} else if (smaller_mode(mode_right, mode_left)) {
-				left  = op_left;
-				right = new_r_Conv(block, op_right, mode_left);
+				left    = op_left;
+				right   = new_r_Conv(block, op_right, mode_left);
+				changed = true;
+				DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CONV);
+			}
+			mode = get_irn_mode(left);
+		}
+	}
+	if (is_Conv(left) && is_Const(right)) {
+		ir_node   *op_left   = get_Conv_op(left);
+		ir_mode   *mode_left = get_irn_mode(op_left);
+		if (smaller_mode(mode_left, mode) && mode_left != mode_b) {
+			ir_tarval *tv        = get_Const_tarval(right);
+			tarval_int_overflow_mode_t last_mode
+				= tarval_get_integer_overflow_mode();
+			ir_tarval *new_tv;
+			tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD);
+			new_tv = tarval_convert_to(tv, mode_left);
+			tarval_set_integer_overflow_mode(last_mode);
+			if (new_tv != tarval_bad) {
+				ir_graph *irg = get_irn_irg(n);
+				left    = op_left;
+				right   = new_r_Const(irg, new_tv);
+				mode    = get_irn_mode(left);
 				changed = true;
 				DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CONV);
 			}
@@ -4621,20 +4848,19 @@ static ir_node *transform_node_Or_Rotl(ir_node *irn_or)
 	return n;
 }  /* transform_node_Or_Rotl */
 
-static bool is_cmp_unequal_zero(const ir_node *node)
+static bool is_cmp_unequal(const ir_node *node)
 {
 	ir_relation relation = get_Cmp_relation(node);
 	ir_node    *left     = get_Cmp_left(node);
 	ir_node    *right    = get_Cmp_right(node);
 	ir_mode    *mode     = get_irn_mode(left);
 
-	if (!is_Const(right) || !is_Const_null(right))
-		return false;
-	if (mode_is_signed(mode)) {
-		return relation == ir_relation_less_greater;
-	} else {
+	if (relation == ir_relation_less_greater)
+		return true;
+
+	if (!mode_is_signed(mode) && is_Const(right) && is_Const_null(right))
 		return relation == ir_relation_greater;
-	}
+	return false;
 }
 
 /**
@@ -4674,18 +4900,21 @@ static ir_node *transform_node_Or(ir_node *n)
 			ir_relation new_relation = a_relation | b_relation;
 			return new_rd_Cmp(dbgi, block, a_left, a_right, new_relation);
 		}
-		/* Cmp(a!=0) or Cmp(b!=0) => Cmp(a|b != 0) */
-		if (is_cmp_unequal_zero(a) && is_cmp_unequal_zero(b)
-				&& !mode_is_float(get_irn_mode(a_left))
-				&& !mode_is_float(get_irn_mode(b_left))) {
-			ir_graph *irg      = get_irn_irg(n);
-			dbg_info *dbgi     = get_irn_dbg_info(n);
-			ir_node  *block    = get_nodes_block(n);
-			ir_mode  *mode     = get_irn_mode(a_left);
-			ir_node  *n_b_left = get_irn_mode(b_left) != mode ?
-				new_rd_Conv(dbgi, block, b_left, mode) : b_left;
-			ir_node  *or   = new_rd_Or(dbgi, block, a_left, n_b_left, mode);
-			ir_node  *zero = create_zero_const(irg, mode);
+		/* Cmp(a!=b) or Cmp(c!=d) => Cmp((a^b)|(c^d) != 0) */
+		if (is_cmp_unequal(a) && is_cmp_unequal(b)
+		    && !mode_is_float(get_irn_mode(a_left))
+		    && !mode_is_float(get_irn_mode(b_left))
+		    && values_in_mode(get_irn_mode(a_left), get_irn_mode(b_left))) {
+			ir_graph *irg    = get_irn_irg(n);
+			dbg_info *dbgi   = get_irn_dbg_info(n);
+			ir_node  *block  = get_nodes_block(n);
+			ir_mode  *a_mode = get_irn_mode(a_left);
+			ir_mode  *b_mode = get_irn_mode(b_left);
+			ir_node  *xora   = new_rd_Eor(dbgi, block, a_left, a_right, a_mode);
+			ir_node  *xorb   = new_rd_Eor(dbgi, block, b_left, b_right, b_mode);
+			ir_node  *conv   = new_rd_Conv(dbgi, block, xorb, a_mode);
+			ir_node  *or     = new_rd_Or(dbgi, block, xora, conv, a_mode);
+			ir_node  *zero   = create_zero_const(irg, a_mode);
 			return new_rd_Cmp(dbgi, block, or, zero, ir_relation_less_greater);
 		}
 	}
@@ -4699,6 +4928,8 @@ static ir_node *transform_node_Or(ir_node *n)
 		return n;
 
 	n = transform_bitwise_distributive(n, transform_node_Or);
+	if (is_Or(n))
+		n = transform_node_bitop_shift(n);
 
 	return n;
 }  /* transform_node_Or */
@@ -4798,91 +5029,6 @@ static ir_node *transform_node_shift(ir_node *n)
 	return transform_node(irn);
 }
 
-/**
- * normalisation: (x & c1) >> c2   to   (x >> c2) & (c1 >> c2)
- *  (we can use:
- *    - and, or, xor          instead of &
- *    - Shl, Shr, Shrs, rotl  instead of >>
- *    (with a special case for Or/Xor + Shrs)
- */
-static ir_node *transform_node_bitop_shift(ir_node *n)
-{
-	ir_node   *left;
-	ir_node   *right = get_binop_right(n);
-	ir_mode   *mode  = get_irn_mode(n);
-	ir_node   *bitop_left;
-	ir_node   *bitop_right;
-	ir_op     *op_left;
-	ir_node   *block;
-	dbg_info  *dbgi;
-	ir_graph  *irg;
-	ir_node   *new_shift;
-	ir_node   *new_bitop;
-	ir_node   *new_const;
-	ir_tarval *tv1;
-	ir_tarval *tv2;
-	ir_tarval *tv_shift;
-
-	assert(is_Shrs(n) || is_Shr(n) || is_Shl(n) || is_Rotl(n));
-
-	if (!is_Const(right))
-		return n;
-
-	left    = get_binop_left(n);
-	op_left = get_irn_op(left);
-	if (op_left != op_And && op_left != op_Or && op_left != op_Eor)
-		return n;
-
-	/* doing it with Shrs is not legal if the Or/Eor affects the topmost bit */
-	if (is_Shrs(n) && (op_left == op_Or || op_left == op_Eor)) {
-		/* TODO: test if sign bit is affectes */
-		return n;
-	}
-
-	bitop_right = get_binop_right(left);
-	if (!is_Const(bitop_right))
-		return n;
-
-	bitop_left = get_binop_left(left);
-
-	block = get_nodes_block(n);
-	dbgi  = get_irn_dbg_info(n);
-	tv1   = get_Const_tarval(bitop_right);
-	tv2   = get_Const_tarval(right);
-
-	assert(get_tarval_mode(tv1) == mode);
-
-	if (is_Shl(n)) {
-		new_shift = new_rd_Shl(dbgi, block, bitop_left, right, mode);
-		tv_shift  = tarval_shl(tv1, tv2);
-	} else if (is_Shr(n)) {
-		new_shift = new_rd_Shr(dbgi, block, bitop_left, right, mode);
-		tv_shift  = tarval_shr(tv1, tv2);
-	} else if (is_Shrs(n)) {
-		new_shift = new_rd_Shrs(dbgi, block, bitop_left, right, mode);
-		tv_shift  = tarval_shrs(tv1, tv2);
-	} else {
-		assert(is_Rotl(n));
-		new_shift = new_rd_Rotl(dbgi, block, bitop_left, right, mode);
-		tv_shift  = tarval_rotl(tv1, tv2);
-	}
-
-	assert(get_tarval_mode(tv_shift) == mode);
-	irg       = get_irn_irg(n);
-	new_const = new_r_Const(irg, tv_shift);
-
-	if (op_left == op_And) {
-		new_bitop = new_rd_And(dbgi, block, new_shift, new_const, mode);
-	} else if (op_left == op_Or) {
-		new_bitop = new_rd_Or(dbgi, block, new_shift, new_const, mode);
-	} else {
-		assert(op_left == op_Eor);
-		new_bitop = new_rd_Eor(dbgi, block, new_shift, new_const, mode);
-	}
-
-	return new_bitop;
-}
-
 /**
  * normalisation:
  *    (x << c1) >> c2  <=>  x OP (c2-c1) & ((-1 << c1) >> c2)
@@ -5001,7 +5147,7 @@ typedef ir_node*(*new_shift_func)(dbg_info *dbgi, ir_node *block,
  * then we can use that to minimize the value of Add(x, const) or
  * Sub(Const, x). In particular this often avoids 1 instruction in some
  * backends for the Shift(x, Sub(Const, y)) case because it can be replaced
- * by Shift(x, Minus(y)) which doesnt't need an explicit Const constructed.
+ * by Shift(x, Minus(y)) which does not need an explicit Const constructed.
  */
 static ir_node *transform_node_shift_modulo(ir_node *n,
                                             new_shift_func new_shift)
@@ -5089,7 +5235,7 @@ static ir_node *transform_node_Shr(ir_node *n)
 	if (is_Shr(n))
 		n = transform_node_shl_shr(n);
 	if (is_Shr(n))
-		n = transform_node_bitop_shift(n);
+		n = transform_node_shift_bitop(n);
 
 	return n;
 }  /* transform_node_Shr */
@@ -5120,7 +5266,7 @@ static ir_node *transform_node_Shrs(ir_node *n)
 	if (is_Shrs(n))
 		n = transform_node_shift_modulo(n, new_rd_Shrs);
 	if (is_Shrs(n))
-		n = transform_node_bitop_shift(n);
+		n = transform_node_shift_bitop(n);
 
 	return n;
 }  /* transform_node_Shrs */
@@ -5143,7 +5289,7 @@ static ir_node *transform_node_Shl(ir_node *n)
 	if (is_Shl(n))
 		n = transform_node_shl_shr(n);
 	if (is_Shl(n))
-		n = transform_node_bitop_shift(n);
+		n = transform_node_shift_bitop(n);
 
 	return n;
 }  /* transform_node_Shl */
@@ -5162,7 +5308,7 @@ static ir_node *transform_node_Rotl(ir_node *n)
 	n = transform_node_shift(n);
 
 	if (is_Rotl(n))
-		n = transform_node_bitop_shift(n);
+		n = transform_node_shift_bitop(n);
 
 	return n;
 }  /* transform_node_Rotl */
@@ -5238,7 +5384,7 @@ static ir_node *transform_node_End(ir_node *n)
 		/* no need to keep Bad */
 		if (is_Bad(ka))
 			continue;
-		/* dont keep unreachable code */
+		/* do not keep unreachable code */
 		block = is_Block(ka) ? ka : get_nodes_block(ka);
 		if (is_block_unreachable(block))
 			continue;
@@ -5268,16 +5414,115 @@ int ir_is_negated_value(const ir_node *a, const ir_node *b)
 	return false;
 }
 
+static const ir_node *skip_upconv(const ir_node *node)
+{
+	while (is_Conv(node)) {
+		ir_mode       *mode    = get_irn_mode(node);
+		const ir_node *op      = get_Conv_op(node);
+		ir_mode       *op_mode = get_irn_mode(op);
+		if (!smaller_mode(op_mode, mode))
+			break;
+		node = op;
+	}
+	return node;
+}
+
+int ir_mux_is_abs(const ir_node *sel, const ir_node *mux_true,
+                  const ir_node *mux_false)
+{
+	ir_node    *cmp_left;
+	ir_node    *cmp_right;
+	ir_mode    *mode;
+	ir_relation relation;
+
+	if (!is_Cmp(sel))
+		return 0;
+
+	/**
+	 * Note further that these optimization work even for floating point
+	 * with NaN's because -NaN == NaN.
+	 * However, if +0 and -0 is handled differently, we cannot use the Abs/-Abs
+	 * transformations.
+	 */
+	mode = get_irn_mode(mux_true);
+	if (mode_honor_signed_zeros(mode))
+		return 0;
+
+	/* must be <, <=, >=, > */
+	relation = get_Cmp_relation(sel);
+	if ((relation & ir_relation_less_greater) == 0)
+		return 0;
+
+	if (!ir_is_negated_value(mux_true, mux_false))
+		return 0;
+
+	mux_true  = skip_upconv(mux_true);
+	mux_false = skip_upconv(mux_false);
+
+	/* must be x cmp 0 */
+	cmp_right = get_Cmp_right(sel);
+	if (!is_Const(cmp_right) || !is_Const_null(cmp_right))
+		return 0;
+
+	cmp_left = get_Cmp_left(sel);
+	if (cmp_left == mux_false) {
+		if (relation & ir_relation_less) {
+			return 1;
+		} else {
+			assert(relation & ir_relation_greater);
+			return -1;
+		}
+	} else if (cmp_left == mux_true) {
+		if (relation & ir_relation_less) {
+			return -1;
+		} else {
+			assert(relation & ir_relation_greater);
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
+ir_node *ir_get_abs_op(const ir_node *sel, ir_node *mux_true,
+                       ir_node *mux_false)
+{
+	ir_node *cmp_left = get_Cmp_left(sel);
+	return cmp_left == skip_upconv(mux_false) ? mux_false : mux_true;
+}
+
 /**
  * Optimize a Mux into some simpler cases.
  */
 static ir_node *transform_node_Mux(ir_node *n)
 {
-	ir_node *oldn = n, *sel = get_Mux_sel(n);
-	ir_mode *mode = get_irn_mode(n);
-	ir_node  *t   = get_Mux_true(n);
-	ir_node  *f   = get_Mux_false(n);
-	ir_graph *irg = get_irn_irg(n);
+	ir_node  *oldn = n;
+	ir_node  *sel  = get_Mux_sel(n);
+	ir_mode  *mode = get_irn_mode(n);
+	ir_node  *t    = get_Mux_true(n);
+	ir_node  *f    = get_Mux_false(n);
+	ir_graph *irg  = get_irn_irg(n);
+
+	/* implement integer abs: abs(x) = x^(x >>s 31) - (x >>s 31) */
+	if (get_mode_arithmetic(mode) == irma_twos_complement) {
+		int abs = ir_mux_is_abs(sel, t, f);
+		if (abs != 0) {
+			dbg_info *dbgi       = get_irn_dbg_info(n);
+			ir_node  *block      = get_nodes_block(n);
+			ir_node  *op         = ir_get_abs_op(sel, t, f);
+			int       bits       = get_mode_size_bits(mode);
+			ir_node  *shiftconst = new_r_Const_long(irg, mode_Iu, bits-1);
+			ir_node  *sext       = new_rd_Shrs(dbgi, block, op, shiftconst, mode);
+			ir_node  *xorn       = new_rd_Eor(dbgi, block, op, sext, mode);
+			ir_node  *res;
+			if (abs > 0) {
+				res = new_rd_Sub(dbgi, block, xorn, sext, mode);
+			} else {
+				res = new_rd_Sub(dbgi, block, sext, xorn, mode);
+			}
+			return res;
+		}
+	}
 
 	if (is_irg_state(irg, IR_GRAPH_STATE_KEEP_MUX))
 		return n;
@@ -5588,7 +5833,7 @@ static ir_node *transform_node_Load(ir_node *n)
 			ir_node  *bad   = new_r_Bad(irg, mode_X);
 			ir_mode  *mode  = get_Load_mode(n);
 			ir_node  *res   = new_r_Proj(pred_load, mode, pn_Load_res);
-			ir_node  *in[pn_Load_max] = { mem, jmp, bad, res };
+			ir_node  *in[pn_Load_max+1] = { mem, res, jmp, bad };
 			ir_node  *tuple = new_r_Tuple(block, ARRAY_SIZE(in), in);
 			return tuple;
 		}
@@ -5608,7 +5853,7 @@ static ir_node *transform_node_Load(ir_node *n)
 			ir_graph *irg   = get_irn_irg(n);
 			ir_node  *bad   = new_r_Bad(irg, mode_X);
 			ir_node  *res   = value;
-			ir_node  *in[pn_Load_max] = { mem, jmp, bad, res };
+			ir_node  *in[pn_Load_max+1] = { mem, res, jmp, bad };
 			ir_node  *tuple = new_r_Tuple(block, ARRAY_SIZE(in), in);
 			return tuple;
 		}
@@ -6071,10 +6316,23 @@ int identities_cmp(const void *elt, const void *key)
 		/* for pinned nodes, the block inputs must be equal */
 		if (get_irn_n(a, -1) != get_irn_n(b, -1))
 			return 1;
-	} else if (! get_opt_global_cse()) {
-		/* for block-local CSE both nodes must be in the same Block */
-		if (get_nodes_block(a) != get_nodes_block(b))
-			return 1;
+	} else {
+		ir_node *block_a = get_nodes_block(a);
+		ir_node *block_b = get_nodes_block(b);
+		if (! get_opt_global_cse()) {
+			/* for block-local CSE both nodes must be in the same Block */
+			if (block_a != block_b)
+				return 1;
+		} else {
+			/* The optimistic approach would be to do nothing here.
+			 * However doing GCSE optimistically produces a lot of partially dead code which appears
+			 * to be worse in practice than the missed opportunities.
+			 * So we use a very conservative variant here and only CSE if 1 value dominates the
+			 * other. */
+			if (!block_dominates(block_a, block_b)
+			    && !block_dominates(block_b, block_a))
+			    return 1;
+		}
 	}
 
 	/* compare a->in[0..ins] with b->in[0..ins] */