X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Ffp-vrp.c;h=8f286223faef3ddb92cecff9e44460b9cc9985b4;hb=4e0288d4c454f3cded36e0b81e97be03dca528db;hp=741a5e92562767fefc3cbbb6d5d00af204ba58a7;hpb=6730cf921d356d992d35526daf57f82af7ab0816;p=libfirm

diff --git a/ir/opt/fp-vrp.c b/ir/opt/fp-vrp.c
index 741a5e925..8f286223f 100644
--- a/ir/opt/fp-vrp.c
+++ b/ir/opt/fp-vrp.c
@@ -1,30 +1,18 @@
 /*
- * Copyright (C) 1995-2010 University of Karlsruhe.  All right reserved.
- *
  * This file is part of libFirm.
- *
- * This file may be distributed and/or modified under the terms of the
- * GNU General Public License version 2 as published by the Free Software
- * Foundation and appearing in the file LICENSE.GPL included in the
- * packaging of this file.
- *
- * Licensees holding valid libFirm Professional Edition licenses may use
- * this file in accordance with the libFirm Commercial License.
- * Agreement provided with the Software.
- *
- * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
- * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE.
+ * Copyright (C) 2012 University of Karlsruhe.
  */
 
 /**
  * @file
  * @brief   Data-flow driven minimal fixpoint value range propagation
  * @author  Christoph Mallon
- * @version $Id$
  */
 #include "config.h"
 
+#include <assert.h>
+#include <stdbool.h>
+
 #include "adt/pdeq.h"
 #include "adt/obst.h"
 #include "adt/xmalloc.h"
@@ -33,9 +21,9 @@
 #include "irdom.h"
 #include "iredges.h"
 #include "irgmod.h"
-#include "irgraph.h"
+#include "irgraph_t.h"
 #include "irgwalk.h"
-#include "irnode.h"
+#include "irnode_t.h"
 #include "iroptimize.h"
 #include "irtools.h"
 #include "tv.h"
@@ -123,20 +111,25 @@ static struct obstack obst;
 
 typedef struct bitinfo
 {
-	tarval* z; // safe zeroes, 0 = bit is zero,       1 = bit maybe is 1
-	tarval* o; // safe ones,   0 = bit maybe is zero, 1 = bit is 1
+	ir_tarval* z; // safe zeroes, 0 = bit is zero,       1 = bit maybe is 1
+	ir_tarval* o; // safe ones,   0 = bit maybe is zero, 1 = bit is 1
 } bitinfo;
 
 typedef struct environment_t {
 	unsigned modified:1;     /**< Set, if the graph was modified. */
 } environment_t;
 
+static bool is_undefined(bitinfo const* const b)
+{
+	return tarval_is_null(b->z) && tarval_is_all_one(b->o);
+}
+
 static inline bitinfo* get_bitinfo(ir_node const* const irn)
 {
-	return get_irn_link(irn);
+	return (bitinfo*)get_irn_link(irn);
 }
 
-static int set_bitinfo(ir_node* const irn, tarval* const z, tarval* const o)
+static int set_bitinfo(ir_node* const irn, ir_tarval* const z, ir_tarval* const o)
 {
 	bitinfo* b = get_bitinfo(irn);
 	if (b == NULL) {
@@ -144,6 +137,10 @@ static int set_bitinfo(ir_node* const irn, tarval* const z, tarval* const o)
 		set_irn_link(irn, b);
 	} else if (z == b->z && o == b->o) {
 		return 0;
+	} else {
+		/* Assert monotonicity. */
+		assert(tarval_is_null(tarval_andnot(b->z, z)));
+		assert(tarval_is_null(tarval_andnot(o, b->o)));
 	}
 	b->z = z;
 	b->o = o;
@@ -158,71 +155,65 @@ static int mode_is_intb(ir_mode const* const m)
 
 static int transfer(ir_node* const irn)
 {
-	ir_mode* const m = get_irn_mode(irn);
-	tarval*        z;
-	tarval*        o;
+	ir_tarval* const f = get_tarval_b_false();
+	ir_tarval* const t = get_tarval_b_true();
+	ir_mode*   const m = get_irn_mode(irn);
+	ir_tarval*       z;
+	ir_tarval*       o;
+
+	if (is_Bad(irn)) return 0;
 
 	if (m == mode_X) {
+		bitinfo* const b = get_bitinfo(get_nodes_block(irn));
+
 		DB((dbg, LEVEL_3, "transfer %+F\n", irn));
-		switch (get_irn_opcode(irn)) {
+
+		/* Unreachble blocks might have no bitinfo. */
+		if (b == NULL || b->z == f) {
+unreachable_X:
+			z = f;
+			o = t;
+		} else switch (get_irn_opcode(irn)) {
 			case iro_Proj: {
 				ir_node* const pred = get_Proj_pred(irn);
 				if (is_Start(pred)) {
-					z = get_tarval_b_true();
-					o = get_tarval_b_false();
+					goto result_unknown_X;
 				} else if (is_Cond(pred)) {
-					ir_node* const selector = get_Cond_selector(pred);
-					bitinfo* const b        = get_bitinfo(selector);
-					tarval*  const bz       = b->z;
-					tarval*  const bo       = b->o;
-					if (get_irn_mode(selector) == mode_b) {
-						if (bz == bo) {
-							if ((bz == get_tarval_b_true()) == get_Proj_proj(irn)) {
-								z = o = get_tarval_b_true();
-							} else {
-								z = o = get_tarval_b_false();
-							}
+					ir_node*   const selector = get_Cond_selector(pred);
+					bitinfo*   const b        = get_bitinfo(selector);
+					if (is_undefined(b))
+						goto unreachable_X;
+					if (b->z == b->o) {
+						if ((b->z == t) == get_Proj_proj(irn)) {
+							z = o = t;
 						} else {
-							goto result_unknown_X;
+							z = o = f;
 						}
 					} else {
-						long const val = get_Proj_proj(irn);
-						if (val != get_Cond_default_proj(pred)) {
-							tarval* const tv = new_tarval_from_long(val, get_irn_mode(selector));
-							if (!tarval_is_null(tarval_andnot(tv, bz)) ||
-									!tarval_is_null(tarval_andnot(bo, tv))) {
-								// At least one bit differs.
-								z = o = get_tarval_b_false();
-#if 0 // TODO must handle default Proj
-							} else if (bz == bo && bz == tv) {
-								z = o = get_tarval_b_true();
-#endif
-							} else {
-								goto result_unknown_X;
-							}
-						} else {
-							goto cannot_analyse_X;
-						}
+						goto result_unknown_X;
 					}
+				} else if (is_Switch(pred)) {
+					ir_node* const selector = get_Switch_selector(pred);
+					bitinfo* const b        = get_bitinfo(selector);
+					if (is_undefined(b))
+						goto unreachable_X;
+					/* TODO */
+					goto cannot_analyse_X;
 				} else {
 					goto cannot_analyse_X;
 				}
 				break;
 			}
 
-			case iro_Jmp: {
-				bitinfo* const b = get_bitinfo(get_nodes_block(irn));
-				z = b->z;
-				o = b->o;
-				break;
-			}
+			case iro_Jmp:
+				goto result_unknown_X;
 
 			default:
 cannot_analyse_X:
 				DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
 result_unknown_X:
-				z = get_tarval_b_true();
-				o = get_tarval_b_false();
+				z = t;
+				o = f;
 				break;
 		}
 	} else if (is_Block(irn)) {
@@ -233,296 +224,370 @@ result_unknown_X:
 		DB((dbg, LEVEL_3, "transfer %+F\n", irn));
 		for (i = 0; i != arity; ++i) {
 			bitinfo* const b = get_bitinfo(get_Block_cfgpred(irn, i));
-			if (b != NULL && b->z == get_tarval_b_true()) {
+			if (b != NULL && b->z == t) {
 				reachable = 1;
 				break;
 			}
 		}
 
-		o = get_tarval_b_false();
-		z = reachable || irn == get_irg_start_block(get_irn_irg(irn)) ? get_tarval_b_true() : o;
+		if (!reachable) {
+			ir_graph *const irg = get_Block_irg(irn);
+			reachable =
+				irn == get_irg_start_block(irg) ||
+				irn == get_irg_end_block(irg);
+		}
+
+		if (reachable) {
+			z = t;
+			o = f;
+		} else {
+			z = f;
+			o = t;
+		}
 	} else if (mode_is_intb(m)) {
+		bitinfo* const b = get_bitinfo(get_nodes_block(irn));
+
 		DB((dbg, LEVEL_3, "transfer %+F\n", irn));
-		switch (get_irn_opcode(irn)) {
-			case iro_Const: {
-				z = o = get_Const_tarval(irn);
-				break;
-			}
 
-			case iro_Shl: {
-				bitinfo* const l  = get_bitinfo(get_Shl_left(irn));
-				bitinfo* const r  = get_bitinfo(get_Shl_right(irn));
-				tarval*  const rz = r->z;
-				if (rz == r->o) {
-					z = tarval_shl(l->z, rz);
-					o = tarval_shl(l->o, rz);
-				} else {
-					goto cannot_analyse;
+		if (b == NULL || b->z == f) {
+undefined:
+			z = get_tarval_null(m);
+			o = get_tarval_all_one(m);
+		} else if (is_Phi(irn)) {
+			ir_node* const block = get_nodes_block(irn);
+			int      const arity = get_Phi_n_preds(irn);
+			int            i;
+
+			z = get_tarval_null(m);
+			o = get_tarval_all_one(m);
+			for (i = 0; i != arity; ++i) {
+				bitinfo* const b_cfg = get_bitinfo(get_Block_cfgpred(block, i));
+				if (b_cfg != NULL && b_cfg->z != f) {
+					bitinfo* const b = get_bitinfo(get_Phi_pred(irn, i));
+					/* Only use input if it's not undefined. */
+					if (!is_undefined(b)) {
+						z = tarval_or( z, b->z);
+						o = tarval_and(o, b->o);
+					}
 				}
-				break;
+			}
+		} else {
+			int const arity = get_irn_arity(irn);
+			int       i;
+
+			/* Undefined if any input is undefined. */
+			for (i = 0; i != arity; ++i) {
+				ir_node* const pred   = get_irn_n(irn, i);
+				bitinfo* const pred_b = get_bitinfo(pred);
+				if (pred_b != NULL && is_undefined(pred_b))
+					goto undefined;
 			}
 
-			case iro_Shr: {
-				bitinfo* const l  = get_bitinfo(get_Shr_left(irn));
-				bitinfo* const r  = get_bitinfo(get_Shr_right(irn));
-				tarval*  const rz = r->z;
-				if (rz == r->o) {
-					z = tarval_shr(l->z, rz);
-					o = tarval_shr(l->o, rz);
-				} else {
-					goto cannot_analyse;
+			switch (get_irn_opcode(irn)) {
+				case iro_Const: {
+					z = o = get_Const_tarval(irn);
+					break;
 				}
-				break;
-			}
 
-			case iro_Shrs: {
-				bitinfo* const l  = get_bitinfo(get_Shrs_left(irn));
-				bitinfo* const r  = get_bitinfo(get_Shrs_right(irn));
-				tarval*  const rz = r->z;
-				if (rz == r->o) {
-					z = tarval_shrs(l->z, rz);
-					o = tarval_shrs(l->o, rz);
-				} else {
-					goto cannot_analyse;
+				case iro_Confirm: {
+					ir_node* const v = get_Confirm_value(irn);
+					bitinfo* const b = get_bitinfo(v);
+					/* TODO Use bound and relation. */
+					z = b->z;
+					o = b->o;
+					if ((get_Confirm_relation(irn) & ~ir_relation_unordered) == ir_relation_equal) {
+						bitinfo* const bound_b = get_bitinfo(get_Confirm_bound(irn));
+						z = tarval_and(z, bound_b->z);
+						o = tarval_or( o, bound_b->o);
+					}
+					break;
 				}
-				break;
-			}
 
-			case iro_Rotl: {
-				bitinfo* const l  = get_bitinfo(get_Rotl_left(irn));
-				bitinfo* const r  = get_bitinfo(get_Rotl_right(irn));
-				tarval*  const rz = r->z;
-				if (rz == r->o) {
-					z = tarval_rotl(l->z, rz);
-					o = tarval_rotl(l->o, rz);
-				} else {
-					goto cannot_analyse;
+				case iro_Shl: {
+					bitinfo*   const l  = get_bitinfo(get_Shl_left(irn));
+					bitinfo*   const r  = get_bitinfo(get_Shl_right(irn));
+					ir_tarval* const rz = r->z;
+					if (rz == r->o) {
+						z = tarval_shl(l->z, rz);
+						o = tarval_shl(l->o, rz);
+					} else {
+						goto cannot_analyse;
+					}
+					break;
 				}
-				break;
-			}
 
-			case iro_Add: {
-				bitinfo* const l  = get_bitinfo(get_Add_left(irn));
-				bitinfo* const r  = get_bitinfo(get_Add_right(irn));
-				tarval*  const lz = l->z;
-				tarval*  const lo = l->o;
-				tarval*  const rz = r->z;
-				tarval*  const ro = r->o;
-				if (lz == lo && rz == ro) {
-					z = o = tarval_add(lz, rz);
-				} else {
-					// TODO improve: can only do lower disjoint bits
-					/* Determine where any of the operands has zero bits, i.e. where no
-					 * carry out is generated if there is not carry in */
-					tarval* const no_c_in_no_c_out = tarval_and(lz, rz);
-					/* Generate a mask of the lower consecutive zeroes: x | -x.  In this
-					 * range the addition is disjoint and therefore Add behaves like Or.
-					 */
-					tarval* const low_zero_mask = tarval_or(no_c_in_no_c_out, tarval_neg(no_c_in_no_c_out));
-					tarval* const low_one_mask  = tarval_not(low_zero_mask);
-					z = tarval_or( tarval_or(lz, rz), low_zero_mask);
-					o = tarval_and(tarval_or(lo, ro), low_one_mask);
+				case iro_Shr: {
+					bitinfo*   const l  = get_bitinfo(get_Shr_left(irn));
+					bitinfo*   const r  = get_bitinfo(get_Shr_right(irn));
+					ir_tarval* const rz = r->z;
+					if (rz == r->o) {
+						z = tarval_shr(l->z, rz);
+						o = tarval_shr(l->o, rz);
+					} else {
+						goto cannot_analyse;
+					}
+					break;
 				}
-				break;
-			}
 
-			case iro_Sub: {
-				bitinfo* const l = get_bitinfo(get_Sub_left(irn));
-				bitinfo* const r = get_bitinfo(get_Sub_right(irn));
-				if (l != NULL && r != NULL) { // Sub might subtract pointers.
-					tarval* const lz = l->z;
-					tarval* const lo = l->o;
-					tarval* const rz = r->z;
-					tarval* const ro = r->o;
-					if (lz == lo && rz == ro) {
-						z = o = tarval_sub(lz, rz, NULL);
-					} else if (tarval_is_null(tarval_andnot(rz, lo))) {
-						/* Every possible one of the subtrahend is backed by a safe one of the
-						 * minuend, i.e. there are no borrows. */
-						// TODO extend no-borrow like carry for Add above
-						z = tarval_andnot(lz, ro);
-						o = tarval_andnot(lo, rz);
+				case iro_Shrs: {
+					bitinfo*   const l  = get_bitinfo(get_Shrs_left(irn));
+					bitinfo*   const r  = get_bitinfo(get_Shrs_right(irn));
+					ir_tarval* const rz = r->z;
+					if (rz == r->o) {
+						z = tarval_shrs(l->z, rz);
+						o = tarval_shrs(l->o, rz);
 					} else {
 						goto cannot_analyse;
 					}
-				} else {
-					goto cannot_analyse;
+					break;
 				}
-				break;
-			}
 
-			case iro_Mul: {
-				bitinfo* const l  = get_bitinfo(get_Mul_left(irn));
-				bitinfo* const r  = get_bitinfo(get_Mul_right(irn));
-				tarval*  const lz = l->z;
-				tarval*  const lo = l->o;
-				tarval*  const rz = r->z;
-				tarval*  const ro = r->o;
-				if (lz == lo && rz == ro) {
-					z = o = tarval_mul(lz, rz);
-				} else {
-					// TODO improve
-					// Determine safe lower zeroes: x | -x.
-					tarval* const lzn = tarval_or(lz, tarval_neg(lz));
-					tarval* const rzn = tarval_or(rz, tarval_neg(rz));
-					// Concatenate safe lower zeroes.
-					if (tarval_cmp(lzn, rzn) == pn_Cmp_Lt) {
-						z = tarval_mul(tarval_eor(lzn, tarval_shl(lzn, get_tarval_one(m))), rzn);
+				case iro_Rotl: {
+					bitinfo*   const l  = get_bitinfo(get_Rotl_left(irn));
+					bitinfo*   const r  = get_bitinfo(get_Rotl_right(irn));
+					ir_tarval* const rz = r->z;
+					if (rz == r->o) {
+						z = tarval_rotl(l->z, rz);
+						o = tarval_rotl(l->o, rz);
 					} else {
-						z = tarval_mul(tarval_eor(rzn, tarval_shl(rzn, get_tarval_one(m))), lzn);
+						goto cannot_analyse;
 					}
-					o = get_tarval_null(m);
+					break;
 				}
-				break;
-			}
 
-			case iro_Minus: {
-				bitinfo* const b = get_bitinfo(get_Minus_op(irn));
-				if (b->z == b->o) {
-					z = o = tarval_neg(b->z);
-				} else {
-					goto cannot_analyse;
+				case iro_Add: {
+					bitinfo*   const l  = get_bitinfo(get_Add_left(irn));
+					bitinfo*   const r  = get_bitinfo(get_Add_right(irn));
+					ir_tarval* const lz = l->z;
+					ir_tarval* const lo = l->o;
+					ir_tarval* const rz = r->z;
+					ir_tarval* const ro = r->o;
+					if (lz == lo && rz == ro) {
+						z = o = tarval_add(lz, rz);
+					} else {
+						// TODO improve: can only do lower disjoint bits
+						/* Determine where any of the operands has zero bits, i.e. where no
+						 * carry out is generated if there is not carry in */
+						ir_tarval* const no_c_in_no_c_out = tarval_and(lz, rz);
+						/* Generate a mask of the lower consecutive zeroes: x | -x.  In this
+						 * range the addition is disjoint and therefore Add behaves like Or.
+						 */
+						ir_tarval* const low_zero_mask = tarval_or(no_c_in_no_c_out, tarval_neg(no_c_in_no_c_out));
+						ir_tarval* const low_one_mask  = tarval_not(low_zero_mask);
+						z = tarval_or( tarval_or(lz, rz), low_zero_mask);
+						o = tarval_and(tarval_or(lo, ro), low_one_mask);
+					}
+					break;
 				}
-				break;
-			}
 
-			case iro_And: {
-				bitinfo* const l = get_bitinfo(get_And_left(irn));
-				bitinfo* const r = get_bitinfo(get_And_right(irn));
-				z = tarval_and(l->z, r->z);
-				o = tarval_and(l->o, r->o);
-				break;
-			}
+				case iro_Sub: {
+					bitinfo* const l = get_bitinfo(get_Sub_left(irn));
+					bitinfo* const r = get_bitinfo(get_Sub_right(irn));
+					if (l != NULL && r != NULL) { // Sub might subtract pointers.
+						ir_tarval* const lz = l->z;
+						ir_tarval* const lo = l->o;
+						ir_tarval* const rz = r->z;
+						ir_tarval* const ro = r->o;
+						if (lz == lo && rz == ro) {
+							z = o = tarval_sub(lz, rz, NULL);
+						} else if (tarval_is_null(tarval_andnot(rz, lo))) {
+							/* Every possible one of the subtrahend is backed by a safe one of the
+							 * minuend, i.e. there are no borrows. */
+							// TODO extend no-borrow like carry for Add above
+							z = tarval_andnot(lz, ro);
+							o = tarval_andnot(lo, rz);
+						} else {
+							goto cannot_analyse;
+						}
+					} else {
+						goto cannot_analyse;
+					}
+					break;
+				}
 
-			case iro_Or: {
-				bitinfo* const l = get_bitinfo(get_Or_left(irn));
-				bitinfo* const r = get_bitinfo(get_Or_right(irn));
-				z = tarval_or(l->z, r->z);
-				o = tarval_or(l->o, r->o);
-				break;
-			}
+				case iro_Mul: {
+					bitinfo*   const l  = get_bitinfo(get_Mul_left(irn));
+					bitinfo*   const r  = get_bitinfo(get_Mul_right(irn));
+					ir_tarval* const lz = l->z;
+					ir_tarval* const lo = l->o;
+					ir_tarval* const rz = r->z;
+					ir_tarval* const ro = r->o;
+					if (lz == lo && rz == ro) {
+						z = o = tarval_mul(lz, rz);
+					} else {
+						// TODO improve
+						// Determine safe lower zeroes: x | -x.
+						ir_tarval* const lzn = tarval_or(lz, tarval_neg(lz));
+						ir_tarval* const rzn = tarval_or(rz, tarval_neg(rz));
+						// Concatenate safe lower zeroes.
+						if (tarval_cmp(lzn, rzn) == ir_relation_less) {
+							z = tarval_mul(tarval_eor(lzn, tarval_shl_unsigned(lzn, 1)), rzn);
+						} else {
+							z = tarval_mul(tarval_eor(rzn, tarval_shl_unsigned(rzn, 1)), lzn);
+						}
+						o = get_tarval_null(m);
+					}
+					break;
+				}
 
-			case iro_Eor: {
-				bitinfo* const l  = get_bitinfo(get_Eor_left(irn));
-				bitinfo* const r  = get_bitinfo(get_Eor_right(irn));
-				tarval*  const lz = l->z;
-				tarval*  const lo = l->o;
-				tarval*  const rz = r->z;
-				tarval*  const ro = r->o;
-				z = tarval_or(tarval_andnot(lz, ro), tarval_andnot(rz, lo));
-				o = tarval_or(tarval_andnot(ro, lz), tarval_andnot(lo, rz));
-				break;
-			}
+				case iro_Minus: {
+					bitinfo* const b = get_bitinfo(get_Minus_op(irn));
+					if (b->z == b->o) {
+						z = o = tarval_neg(b->z);
+					} else {
+						goto cannot_analyse;
+					}
+					break;
+				}
 
-			case iro_Not: {
-				bitinfo* const b = get_bitinfo(get_Not_op(irn));
-				z = tarval_not(b->o);
-				o = tarval_not(b->z);
-				break;
-			}
+				case iro_And: {
+					bitinfo* const l = get_bitinfo(get_And_left(irn));
+					bitinfo* const r = get_bitinfo(get_And_right(irn));
+					z = tarval_and(l->z, r->z);
+					o = tarval_and(l->o, r->o);
+					break;
+				}
 
-			case iro_Conv: {
-				bitinfo* const b = get_bitinfo(get_Conv_op(irn));
-				if (b == NULL) // Happens when converting from float values.
-					goto result_unknown;
-				z = tarval_convert_to(b->z, m);
-				o = tarval_convert_to(b->o, m);
-				break;
-			}
+				case iro_Or: {
+					bitinfo* const l = get_bitinfo(get_Or_left(irn));
+					bitinfo* const r = get_bitinfo(get_Or_right(irn));
+					z = tarval_or(l->z, r->z);
+					o = tarval_or(l->o, r->o);
+					break;
+				}
 
-			case iro_Mux: {
-				bitinfo* const f = get_bitinfo(get_Mux_false(irn));
-				bitinfo* const t = get_bitinfo(get_Mux_true(irn));
-				bitinfo* const c = get_bitinfo(get_Mux_sel(irn));
-				if (c->o == get_tarval_b_true()) {
-					z = t->z;
-					o = t->o;
-				} else if (c->z == get_tarval_b_false()) {
-					z = f->z;
-					o = f->o;
-				} else {
-					z = tarval_or( f->z, t->z);
-					o = tarval_and(f->o, t->o);
+				case iro_Eor: {
+					bitinfo*   const l  = get_bitinfo(get_Eor_left(irn));
+					bitinfo*   const r  = get_bitinfo(get_Eor_right(irn));
+					ir_tarval* const lz = l->z;
+					ir_tarval* const lo = l->o;
+					ir_tarval* const rz = r->z;
+					ir_tarval* const ro = r->o;
+					z = tarval_or(tarval_andnot(lz, ro), tarval_andnot(rz, lo));
+					o = tarval_or(tarval_andnot(ro, lz), tarval_andnot(lo, rz));
+					break;
 				}
-				break;
-			}
 
-			case iro_Phi: {
-				ir_node* const block = get_nodes_block(irn);
-				int      const arity = get_Phi_n_preds(irn);
-				int            i;
-
-				z = get_tarval_null(m);
-				o = get_tarval_all_one(m);
-				for (i = 0; i != arity; ++i) {
-					bitinfo* const b_cfg = get_bitinfo(get_Block_cfgpred(block, i));
-					if (b_cfg != NULL && b_cfg->z != get_tarval_b_false()) {
-						bitinfo* const b = get_bitinfo(get_Phi_pred(irn, i));
-						z = tarval_or( z, b->z);
-						o = tarval_and(o, b->o);
+				case iro_Not: {
+					bitinfo* const b = get_bitinfo(get_Not_op(irn));
+					z = tarval_not(b->o);
+					o = tarval_not(b->z);
+					break;
+				}
+
+				case iro_Conv: {
+					bitinfo* const b = get_bitinfo(get_Conv_op(irn));
+					if (b == NULL) // Happens when converting from float values.
+						goto result_unknown;
+					z = tarval_convert_to(b->z, m);
+					o = tarval_convert_to(b->o, m);
+					break;
+				}
+
+				case iro_Mux: {
+					bitinfo* const bf = get_bitinfo(get_Mux_false(irn));
+					bitinfo* const bt = get_bitinfo(get_Mux_true(irn));
+					bitinfo* const c  = get_bitinfo(get_Mux_sel(irn));
+					if (c->o == t) {
+						z = bt->z;
+						o = bt->o;
+					} else if (c->z == f) {
+						z = bf->z;
+						o = bf->o;
+					} else {
+						z = tarval_or( bf->z, bt->z);
+						o = tarval_and(bf->o, bt->o);
 					}
+					break;
 				}
-				break;
-			}
 
-			case iro_Proj: {
-				ir_node* const pred = get_Proj_pred(irn);
-				if (is_Cmp(pred)) { // TODO generalize
-					bitinfo* const l = get_bitinfo(get_Cmp_left(pred));
-					bitinfo* const r = get_bitinfo(get_Cmp_right(pred));
-					if (l == NULL || r == NULL)
+				case iro_Cmp: {
+					bitinfo* const l = get_bitinfo(get_Cmp_left(irn));
+					bitinfo* const r = get_bitinfo(get_Cmp_right(irn));
+					if (l == NULL || r == NULL) {
 						goto result_unknown; // Cmp compares something we cannot evaluate.
-					switch (get_Proj_proj(irn)) {
-						case pn_Cmp_Lg: {
-							tarval* const lz = l->z;
-							tarval* const lo = l->o;
-							tarval* const rz = r->z;
-							tarval* const ro = r->o;
-							if (!tarval_is_null(tarval_andnot(ro, lz)) ||
-									!tarval_is_null(tarval_andnot(lo, rz))) {
-								// At least one bit differs.
-								z = o = get_tarval_b_true();
-							} else if (lz == lo && rz == ro && lz == rz) {
-								z = o = get_tarval_b_false();
-							} else {
-								goto result_unknown;
-							}
-							break;
-						}
-
-						case pn_Cmp_Eq: {
-							tarval* const lz = l->z;
-							tarval* const lo = l->o;
-							tarval* const rz = r->z;
-							tarval* const ro = r->o;
-							if (!tarval_is_null(tarval_andnot(ro, lz)) ||
-									!tarval_is_null(tarval_andnot(lo, rz))) {
-								// At least one bit differs.
-								z = o = get_tarval_b_false();
-							} else if (lz == lo && rz == ro && lz == rz) {
-								z = o = get_tarval_b_true();
-							} else {
-								goto result_unknown;
-							}
-							break;
+					} else {
+						ir_tarval*  const lz       = l->z;
+						ir_tarval*  const lo       = l->o;
+						ir_tarval*  const rz       = r->z;
+						ir_tarval*  const ro       = r->o;
+						ir_relation const relation = get_Cmp_relation(irn);
+						switch (relation) {
+							case ir_relation_less_greater:
+								if (!tarval_is_null(tarval_andnot(ro, lz)) ||
+										!tarval_is_null(tarval_andnot(lo, rz))) {
+									// At least one bit differs.
+									z = o = t;
+								} else if (lz == lo && rz == ro && lz == rz) {
+									z = o = f;
+								} else {
+									goto result_unknown;
+								}
+								break;
+
+							case ir_relation_equal:
+								if (!tarval_is_null(tarval_andnot(ro, lz)) ||
+										!tarval_is_null(tarval_andnot(lo, rz))) {
+									// At least one bit differs.
+									z = o = f;
+								} else if (lz == lo && rz == ro && lz == rz) {
+									z = o = t;
+								} else {
+									goto result_unknown;
+								}
+								break;
+
+							case ir_relation_less_equal:
+							case ir_relation_less:
+								/* TODO handle negative values */
+								if (tarval_is_negative(lz) || tarval_is_negative(lo) ||
+										tarval_is_negative(rz) || tarval_is_negative(ro))
+									goto result_unknown;
+
+								if (tarval_cmp(lz, ro) & relation) {
+									/* Left upper bound is smaller(/equal) than right lower bound. */
+									z = o = t;
+								} else if (!(tarval_cmp(lo, rz) & relation)) {
+									/* Left lower bound is not smaller(/equal) than right upper bound. */
+									z = o = f;
+								} else {
+									goto result_unknown;
+								}
+								break;
+
+							case ir_relation_greater_equal:
+							case ir_relation_greater:
+								/* TODO handle negative values */
+								if (tarval_is_negative(lz) || tarval_is_negative(lo) ||
+										tarval_is_negative(rz) || tarval_is_negative(ro))
+									goto result_unknown;
+
+								if (!(tarval_cmp(lz, ro) & relation)) {
+									/* Left upper bound is not greater(/equal) than right lower bound. */
+									z = o = f;
+								} else if (tarval_cmp(lo, rz) & relation) {
+									/* Left lower bound is greater(/equal) than right upper bound. */
+									z = o = t;
+								} else {
+									goto result_unknown;
+								}
+								break;
+
+							default:
+								goto cannot_analyse;
 						}
-
-						default:
-							goto cannot_analyse;
 					}
-				} else {
-					goto cannot_analyse;
+					break;
 				}
-				break;
-			}
 
-			default: {
+				default: {
 cannot_analyse:
-				DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
+					DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
 result_unknown:
-				z = get_tarval_all_one(m);
-				o = get_tarval_null(m);
-				break;
+					z = get_tarval_all_one(m);
+					o = get_tarval_null(m);
+					break;
+				}
 			}
 		}
 	} else {
@@ -534,7 +599,7 @@ result_unknown:
 
 static void first_round(ir_node* const irn, void* const env)
 {
-	pdeq* const q = env;
+	pdeq* const q = (pdeq*)env;
 
 	transfer(irn);
 	if (is_Phi(irn) || is_Block(irn)) {
@@ -546,13 +611,52 @@ static void first_round(ir_node* const irn, void* const env)
 	}
 }
 
+static ir_node *make_bad_block(ir_graph *irg)
+{
+	ir_node *bad = new_r_Bad(irg, mode_BB);
+	bitinfo *bb  = get_bitinfo(bad);
+	if (bb == NULL) {
+		ir_tarval* const f = get_tarval_b_false();
+		ir_tarval* const t = get_tarval_b_true();
+		set_bitinfo(bad, f, t); /* Undefined. */
+	}
+	return bad;
+}
+
 static void apply_result(ir_node* const irn, void* ctx)
 {
-	bitinfo* const b = get_bitinfo(irn);
-	tarval*        z;
-	tarval*        o;
-	environment_t* env = ctx;
+	environment_t* env = (environment_t*)ctx;
+	ir_node*       block;
+	bitinfo*       block_b;
+	bitinfo*       b;
+	ir_tarval*     z;
+	ir_tarval*     o;
+
+	if (is_Block(irn)) {
+		block_b = get_bitinfo(irn);
+		/* Trivially unreachable blocks have no info. */
+		if (block_b == NULL || block_b->z == get_tarval_b_false()) {
+			ir_node  *bad = make_bad_block(get_irn_irg(irn));
+			exchange(irn, bad);
+			env->modified = 1;
+		}
+		return;
+	}
+
+	block   = get_nodes_block(irn);
+	block_b = get_bitinfo(block);
+	/* Trivially unreachable blocks have no info. */
+	if (block_b == NULL || block_b->z == get_tarval_b_false()) {
+		/* Unreachable blocks might be replaced before the nodes in them. */
+		ir_mode  *mode = get_irn_mode(irn);
+		ir_graph *irg  = get_irn_irg(irn);
+		ir_node  *bad  = new_r_Bad(irg, mode);
+		exchange(irn, bad);
+		env->modified = 1;
+		return;
+	}
 
+	b = get_bitinfo(irn);
 	if (!b) return;
 	if (is_Const(irn)) return; // It cannot get any better than a Const.
 
@@ -570,14 +674,11 @@ static void apply_result(ir_node* const irn, void* ctx)
 			ir_graph *irg = get_irn_irg(irn);
 			n = new_r_Const(irg, z);
 		} else if (m == mode_X) {
-			ir_node*  const block = get_nodes_block(irn);
-			ir_graph* const irg   = get_Block_irg(block);
+			ir_graph* const irg = get_Block_irg(block);
 			if (z == get_tarval_b_true()) {
-				// Might produce an endless loop, so keep the block.
-				add_End_keepalive(get_irg_end(irg), block);
 				n = new_r_Jmp(block);
 			} else {
-				n = new_r_Bad(irg);
+				n = new_r_Bad(irg, mode_X);
 				/* Transferring analysis information to the bad node makes it a
 				 * candidate for replacement. */
 				goto exchange_only;
@@ -597,16 +698,52 @@ exchange_only:
 			ir_node*       const r  = get_And_right(irn);
 			bitinfo const* const bl = get_bitinfo(l);
 			bitinfo const* const br = get_bitinfo(r);
-			if (bl->z == bl->o) {
-				if (tarval_is_null(tarval_andnot(br->z, bl->z))) {
-					DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
-					exchange(irn, r);
-					env->modified = 1;
-				}
-			} else if (br->z == br->o) {
-				if (tarval_is_null(tarval_andnot(bl->z, br->z))) {
-					DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
-					exchange(irn, l);
+			if (tarval_is_null(tarval_andnot(br->z, bl->o))) {
+				DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
+				exchange(irn, r);
+				env->modified = 1;
+			} else if (tarval_is_null(tarval_andnot(bl->z, br->o))) {
+				DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
+				exchange(irn, l);
+				env->modified = 1;
+			}
+			break;
+		}
+
+		case iro_Eor: {
+			ir_node*       const l  = get_Eor_left(irn);
+			ir_node*       const r  = get_Eor_right(irn);
+			bitinfo const* const bl = get_bitinfo(l);
+			bitinfo const* const br = get_bitinfo(r);
+			/* if each bit is guaranteed to be zero on either the left or right
+			 * then an Add will have the same effect as the Eor. Change it for
+			 * normalisation */
+			if (tarval_is_null(tarval_and(bl->z, br->z))) {
+				dbg_info      *dbgi     = get_irn_dbg_info(irn);
+				ir_node       *block    = get_nodes_block(irn);
+				ir_mode       *mode     = get_irn_mode(irn);
+				ir_node       *new_node = new_rd_Add(dbgi, block, l, r, mode);
+				bitinfo const *bi       = get_bitinfo(irn);
+				DB((dbg, LEVEL_2, "%+F(%+F, %+F) normalised to Add\n", irn, l, r));
+				set_bitinfo(new_node, bi->z, bi->o);
+				exchange(irn, new_node);
+				env->modified = 1;
+			}
+			break;
+		}
+
+		case iro_Minus: {
+			ir_mode *mode = get_irn_mode(irn);
+
+			/* If all bits except the highest bit are zero the Minus is superfluous. */
+			if (get_mode_arithmetic(mode) == irma_twos_complement) {
+				ir_node         *const op  = get_Minus_op(irn);
+				bitinfo   const *const b   = get_bitinfo(op);
+				ir_tarval       *const min = get_mode_min(mode);
+
+				if (b->z == min) {
+					DB((dbg, LEVEL_2, "%+F(%+F) is superfluous\n", irn, op));
+					exchange(irn, op);
 					env->modified = 1;
 				}
 			}
@@ -618,19 +755,31 @@ exchange_only:
 			ir_node*       const r  = get_Or_right(irn);
 			bitinfo const* const bl = get_bitinfo(l);
 			bitinfo const* const br = get_bitinfo(r);
-			if (bl->z == bl->o) {
-				if (tarval_is_null(tarval_andnot(bl->o, br->o))) {
-					DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
-					exchange(irn, r);
-					env->modified = 1;
-				}
-			} else if (br->z == br->o) {
-				if (tarval_is_null(tarval_andnot(br->o, bl->o))) {
-					DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
-					exchange(irn, l);
-					env->modified = 1;
-				}
+			if (tarval_is_null(tarval_andnot(bl->z, br->o))) {
+				DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
+				exchange(irn, r);
+				env->modified = 1;
+			} else if (tarval_is_null(tarval_andnot(br->z, bl->o))) {
+				DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
+				exchange(irn, l);
+				env->modified = 1;
 			}
+
+			/* if each bit is guaranteed to be zero on either the left or right
+			 * then an Add will have the same effect as the Or. Change it for
+			 * normalisation */
+			if (tarval_is_null(tarval_and(bl->z, br->z))) {
+				dbg_info      *dbgi     = get_irn_dbg_info(irn);
+				ir_node       *block    = get_nodes_block(irn);
+				ir_mode       *mode     = get_irn_mode(irn);
+				ir_node       *new_node = new_rd_Add(dbgi, block, l, r, mode);
+				bitinfo const *bi       = get_bitinfo(irn);
+				DB((dbg, LEVEL_2, "%+F(%+F, %+F) normalised to Add\n", irn, l, r));
+				set_bitinfo(new_node, bi->z, bi->o);
+				exchange(irn, new_node);
+				env->modified = 1;
+			}
+
 			break;
 		}
 	}
@@ -642,7 +791,6 @@ static void queue_users(pdeq* const q, ir_node* const n)
 		/* When the state of a control flow node changes, not only queue its
 		 * successor blocks, but also the Phis in these blocks, because the Phis
 		 * must reconsider this input path. */
-		ir_edge_t const* e;
 		foreach_out_edge(n, e) {
 			ir_node*  const  src = get_edge_src_irn(e);
 			pdeq_putr(q, src);
@@ -654,7 +802,6 @@ static void queue_users(pdeq* const q, ir_node* const n)
 			}
 		}
 	} else {
-		ir_edge_t const* e;
 		foreach_out_edge(n, e) {
 			ir_node* const src = get_edge_src_irn(e);
 			if (get_irn_mode(src) == mode_T) {
@@ -688,26 +835,35 @@ void fixpoint_vrp(ir_graph* const irg)
 	FIRM_DBG_REGISTER(dbg, "firm.opt.fp-vrp");
 	DB((dbg, LEVEL_1, "===> Performing constant propagation on %+F\n", irg));
 
-	obstack_init(&obst);
+	assure_irg_properties(irg,
+		IR_GRAPH_PROPERTY_NO_BADS
+		| IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
+		| IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
+		| IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
 
-	edges_assure(irg);
-	assure_doms(irg);
+	obstack_init(&obst);
 
 	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
 
 	{
 		pdeq* const q = new_pdeq();
 
-		/* We need this extra step because the dom tree does not contain unreachable
-		   blocks in Firm. Moreover build phi list. */
-		irg_walk_graph(irg, clear_links, build_phi_lists, NULL);
+		/* We need this extra step because the dom tree does not contain
+		 * unreachable blocks in Firm. Moreover build phi list. */
+		irg_walk_anchors(irg, clear_links, build_phi_lists, NULL);
+
+		{
+			ir_tarval* const f = get_tarval_b_false();
+			ir_tarval* const t = get_tarval_b_true();
+			set_bitinfo(get_irg_end_block(irg), t, f); /* Reachable. */
+		}
 
 		/* TODO Improve iteration order. Best is reverse postorder in data flow
 		 * direction and respecting loop nesting for fastest convergence. */
-		irg_walk_blkwise_dom_top_down(irg, firm_clear_link, first_round, q);
+		irg_walk_blkwise_dom_top_down(irg, NULL, first_round, q);
 
 		while (!pdeq_empty(q)) {
-			ir_node* const n = pdeq_getl(q);
+			ir_node* const n = (ir_node*)pdeq_getl(q);
 			if (transfer(n))
 				queue_users(q, n);
 		}
@@ -719,18 +875,11 @@ void fixpoint_vrp(ir_graph* const irg)
 	env.modified = 0;
 	irg_walk_graph(irg, NULL, apply_result, &env);
 
-	if (env.modified) {
-		/* control flow might changed */
-		set_irg_outs_inconsistent(irg);
-		set_irg_extblk_inconsistent(irg);
-		set_irg_doms_inconsistent(irg);
-		set_irg_loopinfo_inconsistent(irg);
-		set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
-	}
-
 	ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
 
 	obstack_free(&obst, NULL);
+	confirm_irg_properties(irg,
+		env.modified ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL);
 }
 
 ir_graph_pass_t *fixpoint_vrp_irg_pass(const char *name)