iropt.c

/*
 * Copyright (C) 1995-2008 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.
 */

/**
 * @file
 * @brief   iropt --- optimizations intertwined with IR construction.
 * @author  Christian Schaefer, Goetz Lindenmaier, Michael Beck
 * @version $Id$
 */
#include "config.h"

#include <string.h>

#include "irnode_t.h"
#include "irgraph_t.h"
#include "iredges_t.h"
#include "irmode_t.h"
#include "iropt_t.h"
#include "ircons_t.h"
#include "irgmod.h"
#include "irvrfy.h"
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
#include "irhooks.h"
#include "irarch.h"
#include "hashptr.h"
#include "opt_confirms.h"
#include "opt_polymorphy.h"
#include "irtools.h"
#include "irhooks.h"
#include "array_t.h"
#include "vrp.h"
#include "firm_types.h"

/* Make types visible to allow most efficient access */
#include "entity_t.h"

/**
 * Returns the tarval of a Const node or tarval_bad for all other nodes.
 */
static tarval *default_value_of(const ir_node *n) {
	if (is_Const(n))
		return get_Const_tarval(n); /* might return tarval_bad */
	else
		return tarval_bad;
}

value_of_func value_of_ptr = default_value_of;

/* * Set a new value_of function. */
void set_value_of_func(value_of_func func) {
	if (func != NULL)
		value_of_ptr = func;
	else
		value_of_ptr = default_value_of;
}

/**
 * Return the value of a Constant.
 */
static tarval *computed_value_Const(const ir_node *n) {
	return get_Const_tarval(n);
}  /* computed_value_Const */

/**
 * Return the value of a 'sizeof', 'alignof' or 'offsetof' SymConst.
 */
static tarval *computed_value_SymConst(const ir_node *n) {
	ir_type   *type;
	ir_entity *ent;

	switch (get_SymConst_kind(n)) {
	case symconst_type_size:
		type = get_SymConst_type(n);
		if (get_type_state(type) == layout_fixed)
			return new_tarval_from_long(get_type_size_bytes(type), get_irn_mode(n));
		break;
	case symconst_type_align:
		type = get_SymConst_type(n);
		if (get_type_state(type) == layout_fixed)
			return new_tarval_from_long(get_type_alignment_bytes(type), get_irn_mode(n));
		break;
	case symconst_ofs_ent:
		ent  = get_SymConst_entity(n);
		type = get_entity_owner(ent);
		if (get_type_state(type) == layout_fixed)
			return new_tarval_from_long(get_entity_offset(ent), get_irn_mode(n));
		break;
	default:
		break;
	}
	return tarval_bad;
}  /* computed_value_SymConst */

/**
 * Return the value of an Add.
 */
static tarval *computed_value_Add(const ir_node *n) {
	ir_node *a = get_Add_left(n);
	ir_node *b = get_Add_right(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad))
		return tarval_add(ta, tb);

	return tarval_bad;
}  /* computed_value_Add */

/**
 * Return the value of a Sub.
 * Special case: a - a
 */
static tarval *computed_value_Sub(const ir_node *n) {
	ir_mode *mode = get_irn_mode(n);
	ir_node *a    = get_Sub_left(n);
	ir_node *b    = get_Sub_right(n);
	tarval  *ta;
	tarval  *tb;

	/* NaN - NaN != 0 */
	if (! mode_is_float(mode)) {
		/* a - a = 0 */
		if (a == b)
			return get_mode_null(mode);
	}

	ta = value_of(a);
	tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad))
		return tarval_sub(ta, tb, mode);

	return tarval_bad;
}  /* computed_value_Sub */

/**
 * Return the value of a Carry.
 * Special : a op 0, 0 op b
 */
static tarval *computed_value_Carry(const ir_node *n) {
	ir_node *a = get_binop_left(n);
	ir_node *b = get_binop_right(n);
	ir_mode *m = get_irn_mode(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		tarval_add(ta, tb);
		return tarval_carry() ? get_mode_one(m) : get_mode_null(m);
	} else {
		if (tarval_is_null(ta) || tarval_is_null(tb))
			return get_mode_null(m);
	}
	return tarval_bad;
}  /* computed_value_Carry */

/**
 * Return the value of a Borrow.
 * Special : a op 0
 */
static tarval *computed_value_Borrow(const ir_node *n) {
	ir_node *a = get_binop_left(n);
	ir_node *b = get_binop_right(n);
	ir_mode *m = get_irn_mode(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_cmp(ta, tb) == pn_Cmp_Lt ? get_mode_one(m) : get_mode_null(m);
	} else if (tarval_is_null(ta)) {
		return get_mode_null(m);
	}
	return tarval_bad;
}  /* computed_value_Borrow */

/**
 * Return the value of an unary Minus.
 */
static tarval *computed_value_Minus(const ir_node *n) {
	ir_node *a = get_Minus_op(n);
	tarval *ta = value_of(a);

	if (ta != tarval_bad)
		return tarval_neg(ta);

	return tarval_bad;
}  /* computed_value_Minus */

/**
 * Return the value of a Mul.
 */
static tarval *computed_value_Mul(const ir_node *n) {
	ir_node *a = get_Mul_left(n);
	ir_node *b = get_Mul_right(n);
	ir_mode *mode;

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	mode = get_irn_mode(n);
	if (mode != get_irn_mode(a)) {
		/* n * n = 2n bit multiplication */
		ta = tarval_convert_to(ta, mode);
		tb = tarval_convert_to(tb, mode);
	}

	if (ta != tarval_bad && tb != tarval_bad) {
		return tarval_mul(ta, tb);
	} else {
		/* a * 0 != 0 if a == NaN or a == Inf */
		if (!mode_is_float(mode)) {
			/* a*0 = 0 or 0*b = 0 */
			if (ta == get_mode_null(mode))
				return ta;
			if (tb == get_mode_null(mode))
				return tb;
		}
	}
	return tarval_bad;
}  /* computed_value_Mul */

/**
 * Return the value of an Abs.
 */
static tarval *computed_value_Abs(const ir_node *n) {
	ir_node *a = get_Abs_op(n);
	tarval *ta = value_of(a);

	if (ta != tarval_bad)
		return tarval_abs(ta);

	return tarval_bad;
}  /* computed_value_Abs */

/**
 * Return the value of an And.
 * Special case: a & 0, 0 & b
 */
static tarval *computed_value_And(const ir_node *n) {
	ir_node *a = get_And_left(n);
	ir_node *b = get_And_right(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_and (ta, tb);
	} else {
		if (tarval_is_null(ta)) return ta;
		if (tarval_is_null(tb)) return tb;
	}
	return tarval_bad;
}  /* computed_value_And */

/**
 * Return the value of an Or.
 * Special case: a | 1...1, 1...1 | b
 */
static tarval *computed_value_Or(const ir_node *n) {
	ir_node *a = get_Or_left(n);
	ir_node *b = get_Or_right(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_or (ta, tb);
	} else {
		if (tarval_is_all_one(ta)) return ta;
		if (tarval_is_all_one(tb)) return tb;
	}
	return tarval_bad;
}  /* computed_value_Or */

/**
 * Return the value of an Eor.
 */
static tarval *computed_value_Eor(const ir_node *n) {
	ir_node *a = get_Eor_left(n);
	ir_node *b = get_Eor_right(n);

	tarval *ta, *tb;

	if (a == b)
		return get_mode_null(get_irn_mode(n));

	ta = value_of(a);
	tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_eor(ta, tb);
	}
	return tarval_bad;
}  /* computed_value_Eor */

/**
 * Return the value of a Not.
 */
static tarval *computed_value_Not(const ir_node *n) {
	ir_node *a = get_Not_op(n);
	tarval *ta = value_of(a);

	if (ta != tarval_bad)
		return tarval_not(ta);

	return tarval_bad;
}  /* computed_value_Not */

/**
 * Return the value of a Shl.
 */
static tarval *computed_value_Shl(const ir_node *n) {
	ir_node *a = get_Shl_left(n);
	ir_node *b = get_Shl_right(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shl(ta, tb);
	}
	return tarval_bad;
}  /* computed_value_Shl */

/**
 * Return the value of a Shr.
 */
static tarval *computed_value_Shr(const ir_node *n) {
	ir_node *a = get_Shr_left(n);
	ir_node *b = get_Shr_right(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shr(ta, tb);
	}
	return tarval_bad;
}  /* computed_value_Shr */

/**
 * Return the value of a Shrs.
 */
static tarval *computed_value_Shrs(const ir_node *n) {
	ir_node *a = get_Shrs_left(n);
	ir_node *b = get_Shrs_right(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shrs(ta, tb);
	}
	return tarval_bad;
}  /* computed_value_Shrs */

/**
 * Return the value of a Rotl.
 */
static tarval *computed_value_Rotl(const ir_node *n) {
	ir_node *a = get_Rotl_left(n);
	ir_node *b = get_Rotl_right(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_rotl(ta, tb);
	}
	return tarval_bad;
}  /* computed_value_Rotl */

/**
 * Return the value of a Conv.
 */
static tarval *computed_value_Conv(const ir_node *n) {
	ir_node *a = get_Conv_op(n);
	tarval *ta = value_of(a);

	if (ta != tarval_bad)
		return tarval_convert_to(ta, get_irn_mode(n));

	return tarval_bad;
}  /* computed_value_Conv */

/**
 * Calculate the value of a Mux: can be evaluated, if the
 * sel and the right input are known.
 */
static tarval *computed_value_Mux(const ir_node *n) {
	ir_node *sel = get_Mux_sel(n);
	tarval *ts = value_of(sel);

	if (ts == get_tarval_b_true()) {
		ir_node *v = get_Mux_true(n);
		return value_of(v);
	}
	else if (ts == get_tarval_b_false()) {
		ir_node *v = get_Mux_false(n);
		return value_of(v);
	}
	return tarval_bad;
}  /* computed_value_Mux */

/**
 * Calculate the value of a Confirm: can be evaluated,
 * if it has the form Confirm(x, '=', Const).
 */
static tarval *computed_value_Confirm(const ir_node *n) {
	/*
	 * Beware: we might produce Phi(Confirm(x == true), Confirm(x == false)).
	 * Do NOT optimize them away (jump threading wants them), so wait until
	 * remove_confirm is activated.
	 */
	if (get_opt_remove_confirm()) {
		if (get_Confirm_cmp(n) == pn_Cmp_Eq) {
			tarval *tv = value_of(get_Confirm_bound(n));
			if (tv != tarval_bad)
				return tv;
		}
	}
	return value_of(get_Confirm_value(n));
}  /* computed_value_Confirm */

/**
 * Return the value of a Proj(Cmp).
 *
 * This performs a first step of unreachable code elimination.
 * Proj can not be computed, but folding a Cmp above the Proj here is
 * not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
 * only 1 is used.
 * There are several case where we can evaluate a Cmp node, see later.
 */
static tarval *computed_value_Proj_Cmp(const ir_node *n) {
	ir_node *a   = get_Proj_pred(n);
	ir_node *aa  = get_Cmp_left(a);
	ir_node *ab  = get_Cmp_right(a);
	long proj_nr = get_Proj_proj(n);

	/*
	 * BEWARE: a == a is NOT always True for floating Point values, as
	 * NaN != NaN is defined, so we must check this here.
	 */
	if (aa == ab && (
		!mode_is_float(get_irn_mode(aa)) || proj_nr == pn_Cmp_Lt ||  proj_nr == pn_Cmp_Gt)
		) { /* 1.: */

		/* This is a trick with the bits used for encoding the Cmp
		   Proj numbers, the following statement is not the same:
		return new_tarval_from_long (proj_nr == pn_Cmp_Eq, mode_b) */
		return new_tarval_from_long (proj_nr & pn_Cmp_Eq, mode_b);
	}
	tarval *taa = value_of(aa);
	tarval *tab = value_of(ab);
	ir_mode *mode = get_irn_mode(aa);

	/*
	 * The predecessors of Cmp are target values.  We can evaluate
	 * the Cmp.
	 */
	if ((taa != tarval_bad) && (tab != tarval_bad)) {
		/* strange checks... */
		pn_Cmp flags = tarval_cmp(taa, tab);
		if (flags != pn_Cmp_False) {
			return new_tarval_from_long (proj_nr & flags, mode_b);
		}
	}
	/* for integer values, we can check against MIN/MAX */
	else if (mode_is_int(mode)) {
		/* MIN <=/> x.  This results in true/false. */
		if (taa == get_mode_min(mode)) {
			/* a compare with the MIN value */
			if (proj_nr == pn_Cmp_Le)
				return get_tarval_b_true();
			else if (proj_nr == pn_Cmp_Gt)
				return get_tarval_b_false();
		}
		/* x >=/< MIN.  This results in true/false. */
		else
			if (tab == get_mode_min(mode)) {
				/* a compare with the MIN value */
				if (proj_nr == pn_Cmp_Ge)
					return get_tarval_b_true();
				else if (proj_nr == pn_Cmp_Lt)
					return get_tarval_b_false();
			}
		/* MAX >=/< x.  This results in true/false. */
			else if (taa == get_mode_max(mode)) {
				if (proj_nr == pn_Cmp_Ge)
					return get_tarval_b_true();
				else if (proj_nr == pn_Cmp_Lt)
					return get_tarval_b_false();
			}
		/* x <=/> MAX.  This results in true/false. */
			else if (tab == get_mode_max(mode)) {
				if (proj_nr == pn_Cmp_Le)
					return get_tarval_b_true();
				else if (proj_nr == pn_Cmp_Gt)
					return get_tarval_b_false();
			}

		pn_Cmp cmp_result = vrp_cmp(aa, ab);
		if (cmp_result != pn_Cmp_False) {
			if (cmp_result == pn_Cmp_Lg) {
				if( proj_nr == pn_Cmp_Eq) {
				return get_tarval_b_false();
				} else if(proj_nr == pn_Cmp_Lg) {
					return get_tarval_b_true();
				}
			} else {
				return new_tarval_from_long(cmp_result & proj_nr, mode_b);
			}
		}
	}
	/*
	 * The predecessors are Allocs or (void*)(0) constants.  Allocs never
	 * return NULL, they raise an exception.   Therefore we can predict
	 * the Cmp result.
	 */
	else {
		ir_node *aaa = skip_Proj(aa);
		ir_node *aba = skip_Proj(ab);

		if (   (   (/* aa is ProjP and aaa is Alloc */
						is_Proj(aa)
						&& mode_is_reference(get_irn_mode(aa))
						&& is_Alloc(aaa))
					&& (   (/* ab is NULL */
							mode_is_reference(get_irn_mode(ab))
							&& tarval_is_null(tab))
						|| (/* ab is other Alloc */
							is_Proj(ab)
							&& mode_is_reference(get_irn_mode(ab))
							&& is_Alloc(aba)
							&& (aaa != aba))))
				|| (/* aa is NULL and aba is Alloc */
					mode_is_reference(get_irn_mode(aa))
					&& tarval_is_null(taa)
					&& is_Proj(ab)
					&& mode_is_reference(get_irn_mode(ab))
					&& is_Alloc(aba)))
			/* 3.: */
			return new_tarval_from_long(proj_nr & pn_Cmp_Lg, mode_b);
	}
	return computed_value_Cmp_Confirm(a, aa, ab, proj_nr);
}  /* computed_value_Proj_Cmp */

/**
 * Return the value of a floating point Quot.
 */
static tarval *do_computed_value_Quot(const ir_node *a, const ir_node *b) {
	tarval  *ta = value_of(a);
	tarval  *tb = value_of(b);

	/* cannot optimize 0 / b = 0 because of NaN */
	if (ta != tarval_bad && tb != tarval_bad)
		return tarval_quo(ta, tb);
	return tarval_bad;
}  /* do_computed_value_Quot */

/**
 * Calculate the value of an integer Div of two nodes.
 * Special case: 0 / b
 */
static tarval *do_computed_value_Div(const ir_node *a, const ir_node *b) {
	tarval        *ta = value_of(a);
	tarval        *tb;
	const ir_node *dummy;

	/* Compute c1 / c2 or 0 / a, a != 0 */
	if (tarval_is_null(ta) && value_not_zero(b, &dummy))
		return ta;  /* 0 / b == 0 */
	tb = value_of(b);
	if (ta != tarval_bad && tb != tarval_bad)
		return tarval_div(ta, tb);
	return tarval_bad;
}  /* do_computed_value_Div */

/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
static tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b) {
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	/* Compute a % 1 or c1 % c2 */
	if (tarval_is_one(tb))
		return get_mode_null(get_irn_mode(a));
	if (ta != tarval_bad && tb != tarval_bad)
		return tarval_mod(ta, tb);
	return tarval_bad;
}  /* do_computed_value_Mod */

/**
 * Return the value of a Proj(DivMod).
 */
static tarval *computed_value_Proj_DivMod(const ir_node *n) {
	long proj_nr = get_Proj_proj(n);

	/* compute either the Div or the Mod part */
	if (proj_nr == pn_DivMod_res_div) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
	} else if (proj_nr == pn_DivMod_res_mod) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
	}
	return tarval_bad;
}  /* computed_value_Proj_DivMod */

/**
 * Return the value of a Proj(Div).
 */
static tarval *computed_value_Proj_Div(const ir_node *n) {
	long proj_nr = get_Proj_proj(n);

	if (proj_nr == pn_Div_res) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Div(get_Div_left(a), get_Div_right(a));
	}
	return tarval_bad;
}  /* computed_value_Proj_Div */

/**
 * Return the value of a Proj(Mod).
 */
static tarval *computed_value_Proj_Mod(const ir_node *n) {
	long proj_nr = get_Proj_proj(n);

	if (proj_nr == pn_Mod_res) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Mod(get_Mod_left(a), get_Mod_right(a));
	}
	return tarval_bad;
}  /* computed_value_Proj_Mod */

/**
 * Return the value of a Proj(Quot).
 */
static tarval *computed_value_Proj_Quot(const ir_node *n) {
	long proj_nr = get_Proj_proj(n);

	if (proj_nr == pn_Quot_res) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Quot(get_Quot_left(a), get_Quot_right(a));
	}
	return tarval_bad;
}  /* computed_value_Proj_Quot */

/**
 * Return the value of a Proj.
 */
static tarval *computed_value_Proj(const ir_node *proj) {
	ir_node *n = get_Proj_pred(proj);

	if (n->op->ops.computed_value_Proj != NULL)
		return n->op->ops.computed_value_Proj(proj);
	return tarval_bad;
}  /* computed_value_Proj */

/**
 * If the parameter n can be computed, return its value, else tarval_bad.
 * Performs constant folding.
 *
 * @param n  The node this should be evaluated
 */
tarval *computed_value(const ir_node *n) {
	if(mode_is_int(get_irn_mode(n)) && tarval_is_all_one(
				tarval_or(n->vrp.bits_set, n->vrp.bits_not_set))) {
		return n->vrp.bits_set;
	}
	if (n->op->ops.computed_value)
		return n->op->ops.computed_value(n);
	return tarval_bad;
}  /* computed_value */

/**
 * Set the default computed_value evaluator in an ir_op_ops.
 *
 * @param code   the opcode for the default operation
 * @param ops    the operations initialized
 *
 * @return
 *    The operations.
 */
static ir_op_ops *firm_set_default_computed_value(ir_opcode code, ir_op_ops *ops)
{
#define CASE(a)                                        \
	case iro_##a:                                      \
		ops->computed_value      = computed_value_##a; \
		break
#define CASE_PROJ(a)                                        \
	case iro_##a:                                           \
		ops->computed_value_Proj = computed_value_Proj_##a; \
		break

	switch (code) {
	CASE(Const);
	CASE(SymConst);
	CASE(Add);
	CASE(Sub);
	CASE(Carry);
	CASE(Borrow);
	CASE(Minus);
	CASE(Mul);
	CASE(Abs);
	CASE(And);
	CASE(Or);
	CASE(Eor);
	CASE(Not);
	CASE(Shl);
	CASE(Shr);
	CASE(Shrs);
	CASE(Rotl);
	CASE(Conv);
	CASE(Mux);
	CASE(Confirm);
	CASE_PROJ(Cmp);
	CASE_PROJ(DivMod);
	CASE_PROJ(Div);
	CASE_PROJ(Mod);
	CASE_PROJ(Quot);
	CASE(Proj);
	default:
		/* leave NULL */;
	}

	return ops;
#undef CASE_PROJ
#undef CASE
}  /* firm_set_default_computed_value */

/**
 * Returns a equivalent block for another block.
 * If the block has only one predecessor, this is
 * the equivalent one. If the only predecessor of a block is
 * the block itself, this is a dead block.
 *
 * If both predecessors of a block are the branches of a binary
 * Cond, the equivalent block is Cond's block.
 *
 * If all predecessors of a block are bad or lies in a dead
 * block, the current block is dead as well.
 *
 * Note, that blocks are NEVER turned into Bad's, instead
 * the dead_block flag is set. So, never test for is_Bad(block),
 * always use is_dead_Block(block).
 */
static ir_node *equivalent_node_Block(ir_node *n)
{
	ir_node *oldn = n;
	int     n_preds;

	/* don't optimize dead or labeled blocks */
	if (is_Block_dead(n) || has_Block_entity(n))
		return n;

	n_preds = get_Block_n_cfgpreds(n);

	/* The Block constructor does not call optimize, but mature_immBlock()
	   calls the optimization. */
	assert(get_Block_matured(n));

	/* Straightening: a single entry Block following a single exit Block
	   can be merged, if it is not the Start block. */
	/* !!! Beware, all Phi-nodes of n must have been optimized away.
	   This should be true, as the block is matured before optimize is called.
	   But what about Phi-cycles with the Phi0/Id that could not be resolved?
	   Remaining Phi nodes are just Ids. */
	if (n_preds == 1) {
		ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));

		if (is_Jmp(pred)) {
			ir_node *predblock = get_nodes_block(pred);
			if (predblock == oldn) {
				/* Jmp jumps into the block it is in -- deal self cycle. */
				n = set_Block_dead(n);
				DBG_OPT_DEAD_BLOCK(oldn, n);
			} else if (get_opt_control_flow_straightening()) {
				n = predblock;
				DBG_OPT_STG(oldn, n);
			}
		} else if (is_Cond(pred)) {
			ir_node *predblock = get_nodes_block(pred);
			if (predblock == oldn) {
				/* Jmp jumps into the block it is in -- deal self cycle. */
				n = set_Block_dead(n);
				DBG_OPT_DEAD_BLOCK(oldn, n);
			}
		}
	} else if ((n_preds == 2) &&
	           (get_opt_control_flow_weak_simplification())) {
		/* Test whether Cond jumps twice to this block
		 * The more general case which more than 2 predecessors is handles
		 * in optimize_cf(), we handle only this special case for speed here.
		 */
		ir_node *a = get_Block_cfgpred(n, 0);
		ir_node *b = get_Block_cfgpred(n, 1);

		if (is_Proj(a) && is_Proj(b)) {
			ir_node *cond = get_Proj_pred(a);

		    if (cond == get_Proj_pred(b) && is_Cond(cond) &&
		        get_irn_mode(get_Cond_selector(cond)) == mode_b) {
				/* Also a single entry Block following a single exit Block.  Phis have
				   twice the same operand and will be optimized away. */
				n = get_nodes_block(cond);
				DBG_OPT_IFSIM1(oldn, a, b, n);
			}
		}
	} else if (get_opt_unreachable_code() &&
	           (n != get_irg_start_block(current_ir_graph)) &&
	           (n != get_irg_end_block(current_ir_graph))    ) {
		int i;

		/* If all inputs are dead, this block is dead too, except if it is
		   the start or end block.  This is one step of unreachable code
		   elimination */
		for (i = get_Block_n_cfgpreds(n) - 1; i >= 0; --i) {
			ir_node *pred = get_Block_cfgpred(n, i);
			ir_node *pred_blk;

			if (is_Bad(pred)) continue;
			pred_blk = get_nodes_block(skip_Proj(pred));

			if (is_Block_dead(pred_blk)) continue;

			if (pred_blk != n) {
				/* really found a living input */
				break;
			}
		}
		if (i < 0) {
			n = set_Block_dead(n);
			DBG_OPT_DEAD_BLOCK(oldn, n);
		}
	}

	return n;
}  /* equivalent_node_Block */

/**
 * Returns a equivalent node for a Jmp, a Bad :-)
 * Of course this only happens if the Block of the Jmp is dead.
 */
static ir_node *equivalent_node_Jmp(ir_node *n) {
	ir_node *oldn = n;

	/* unreachable code elimination */
	if (is_Block_dead(get_nodes_block(n))) {
		n = get_irg_bad(current_ir_graph);
		DBG_OPT_DEAD_BLOCK(oldn, n);
	}
	return n;
}  /* equivalent_node_Jmp */

/** Raise is handled in the same way as Jmp. */
#define equivalent_node_Raise   equivalent_node_Jmp


/* We do not evaluate Cond here as we replace it by a new node, a Jmp.
   See transform_node_Proj_Cond(). */

/**
 * Optimize operations that are commutative and have neutral 0,
 * so a op 0 = 0 op a = a.
 */
static ir_node *equivalent_node_neutral_zero(ir_node *n) {
	ir_node *oldn = n;

	ir_node *a = get_binop_left(n);
	ir_node *b = get_binop_right(n);

	tarval *tv;
	ir_node *on;

	/* After running compute_node there is only one constant predecessor.
	   Find this predecessors value and remember the other node: */
	if ((tv = value_of(a)) != tarval_bad) {
		on = b;
	} else if ((tv = value_of(b)) != tarval_bad) {
		on = a;
	} else
		return n;

	/* If this predecessors constant value is zero, the operation is
	 * unnecessary. Remove it.
	 *
	 * Beware: If n is a Add, the mode of on and n might be different
	 * which happens in this rare construction: NULL + 3.
	 * Then, a Conv would be needed which we cannot include here.
	 */
	if (tarval_is_null(tv) && get_irn_mode(on) == get_irn_mode(n)) {
		n = on;

		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
	}

	return n;
}  /* equivalent_node_neutral_zero */

/**
 * Eor is commutative and has neutral 0.
 */
static ir_node *equivalent_node_Eor(ir_node *n) {
	ir_node *oldn = n;
	ir_node *a;
	ir_node *b;

	n = equivalent_node_neutral_zero(n);
	if (n != oldn) return n;

	a = get_Eor_left(n);
	b = get_Eor_right(n);

	if (is_Eor(a)) {
		ir_node *aa = get_Eor_left(a);
		ir_node *ab = get_Eor_right(a);

		if (aa == b) {
			/* (a ^ b) ^ a -> b */
			n = ab;
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
			return n;
		} else if (ab == b) {
			/* (a ^ b) ^ b -> a */
			n = aa;
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
			return n;
		}
	}
	if (is_Eor(b)) {
		ir_node *ba = get_Eor_left(b);
		ir_node *bb = get_Eor_right(b);

		if (ba == a) {
			/* a ^ (a ^ b) -> b */
			n = bb;
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
			return n;
		} else if (bb == a) {
			/* a ^ (b ^ a) -> b */
			n = ba;
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
			return n;
		}
	}
	return n;
}

/*
 * Optimize a - 0 and (a - x) + x (for modes with wrap-around).
 *
 * The second one looks strange, but this construct
 * is used heavily in the LCC sources :-).
 *
 * Beware: The Mode of an Add may be different than the mode of its
 * predecessors, so we could not return a predecessors in all cases.
 */
static ir_node *equivalent_node_Add(ir_node *n) {
	ir_node *oldn = n;
	ir_node *left, *right;
	ir_mode *mode = get_irn_mode(n);

	n = equivalent_node_neutral_zero(n);
	if (n != oldn)
		return n;

	/* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
	if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
		return n;

	left  = get_Add_left(n);
	right = get_Add_right(n);

	if (is_Sub(left)) {
		if (get_Sub_right(left) == right) {