X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Ffp-vrp.c;h=314358f531fb645ddf6939c0c927f4b85f51b97d;hb=b27ae245166bb695bc4e418ff416d91bc37d0f28;hp=3a4c9c014980481f975873d0a98c9ae7c4aa0007;hpb=04785d3f30729fb52721ed71fd8a8b1d597e8283;p=libfirm

diff --git a/ir/opt/fp-vrp.c b/ir/opt/fp-vrp.c
index 3a4c9c014..314358f53 100644
--- a/ir/opt/fp-vrp.c
+++ b/ir/opt/fp-vrp.c
@@ -23,9 +23,11 @@
  * @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"
@@ -34,9 +36,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"
@@ -124,20 +126,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) {
@@ -145,6 +152,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;
@@ -159,29 +170,38 @@ 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 (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();
+					ir_node*   const selector = get_Cond_selector(pred);
+					bitinfo*   const b        = get_bitinfo(selector);
+					if (is_undefined(b)) {
+						goto unreachable_X;
+					} else if (get_irn_mode(selector) == mode_b) {
+						if (b->z == b->o) {
+							if ((b->z == t) == get_Proj_proj(irn)) {
+								z = o = t;
 							} else {
-								z = o = get_tarval_b_false();
+								z = o = f;
 							}
 						} else {
 							goto result_unknown_X;
@@ -189,14 +209,14 @@ static int transfer(ir_node* const irn)
 					} 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))) {
+							ir_tarval* const tv = new_tarval_from_long(val, get_irn_mode(selector));
+							if (!tarval_is_null(tarval_andnot(tv, b->z)) ||
+									!tarval_is_null(tarval_andnot(b->o, tv))) {
 								// At least one bit differs.
-								z = o = get_tarval_b_false();
+								z = o = f;
 #if 0 // TODO must handle default Proj
-							} else if (bz == bo && bz == tv) {
-								z = o = get_tarval_b_true();
+							} else if (b->z == b->o && b->z == tv) {
+								z = o = t;
 #endif
 							} else {
 								goto result_unknown_X;
@@ -211,19 +231,15 @@ static int transfer(ir_node* const irn)
 				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)) {
@@ -234,296 +250,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(lzn, get_tarval_one(m))), rzn);
+						} else {
+							z = tarval_mul(tarval_eor(rzn, tarval_shl(rzn, get_tarval_one(m))), 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 {
@@ -535,7 +625,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)) {
@@ -547,13 +637,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.
 
@@ -568,16 +697,16 @@ static void apply_result(ir_node* const irn, void* ctx)
 		ir_mode* const m = get_irn_mode(irn);
 		ir_node*       n;
 		if (mode_is_intb(m)) {
-			n = new_Const(z);
+			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;
@@ -676,6 +805,7 @@ static void clear_links(ir_node *irn, void *env)
 
 static void build_phi_lists(ir_node *irn, void *env)
 {
+	(void) env;
 	if (is_Phi(irn))
 		add_Block_phi(get_nodes_block(irn), irn);
 }
@@ -689,6 +819,10 @@ void fixpoint_vrp(ir_graph* const irg)
 
 	obstack_init(&obst);
 
+	/* HACK: to avoid finding dead code */
+	edges_deactivate(irg);
+	edges_activate(irg);
+
 	edges_assure(irg);
 	assure_doms(irg);
 
@@ -697,16 +831,22 @@ void fixpoint_vrp(ir_graph* const irg)
 	{
 		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);
 		}
@@ -720,10 +860,8 @@ void fixpoint_vrp(ir_graph* const irg)
 
 	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);
 	}