iropt.c

/*
 * Copyright (C) 1995-2011 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
 */
#include "config.h"

#include <string.h>
#include <stdbool.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 "irverify.h"
#include "iroptimize.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 "irtools.h"
#include "irhooks.h"
#include "array_t.h"
#include "vrp.h"
#include "firm_types.h"
#include "bitfiddle.h"
#include "be.h"

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

static bool is_Or_Eor_Add(const ir_node *node)
{
	if (is_Or(node) || is_Eor(node) || is_Add(node)) {
		ir_node  *left      = get_binop_left(node);
		ir_node  *right     = get_binop_right(node);
		vrp_attr *vrp_left  = vrp_get_info(left);
		vrp_attr *vrp_right = vrp_get_info(right);
		if (vrp_left != NULL && vrp_right != NULL) {
			ir_tarval *vrp_val
				= tarval_and(vrp_left->bits_not_set, vrp_right->bits_not_set);
			return tarval_is_null(vrp_val);
		}
	}
	return false;
}

/**
 * Returns the tarval of a Const node or tarval_bad for all other nodes.
 */
static ir_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 ir_tarval *computed_value_Const(const ir_node *n)
{
	return get_Const_tarval(n);
}

/**
 * Return the value of a 'sizeof', 'alignof' or 'offsetof' SymConst.
 */
static ir_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;
}

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

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

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

	/* x+~x => -1 */
	if ((is_Not(a) && get_Not_op(a) == b)
	    || (is_Not(b) && get_Not_op(b) == a)) {
		return get_mode_all_one(get_irn_mode(n));
	}

	return tarval_bad;
}

/**
 * Return the value of a Sub.
 * Special case: a - a
 */
static ir_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);
	ir_tarval *ta;
	ir_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;
}

/**
 * Return the value of a Carry.
 * Special : a op 0, 0 op b
 */
static ir_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);
	ir_tarval *ta = value_of(a);
	ir_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;
}

/**
 * Return the value of a Borrow.
 * Special : a op 0
 */
static ir_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);
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);

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

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

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

	return tarval_bad;
}

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

	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;
}

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

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_and (ta, tb);
	}

	if (tarval_is_null(ta)) return ta;
	if (tarval_is_null(tb)) return tb;

	/* x&~x => 0 */
	if ((is_Not(a) && get_Not_op(a) == b)
	    || (is_Not(b) && get_Not_op(b) == a)) {
		return get_mode_null(get_irn_mode(n));
	}

	return tarval_bad;
}

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

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_or (ta, tb);
	}

	if (tarval_is_all_one(ta)) return ta;
	if (tarval_is_all_one(tb)) return tb;

	/* x|~x => -1 */
	if ((is_Not(a) && get_Not_op(a) == b)
	    || (is_Not(b) && get_Not_op(b) == a)) {
		return get_mode_all_one(get_irn_mode(n));
	}
	return tarval_bad;
}

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

	ir_tarval *ta, *tb;

	if (a == b)
		return get_mode_null(get_irn_mode(n));
	/* x^~x => -1 */
	if ((is_Not(a) && get_Not_op(a) == b)
	    || (is_Not(b) && get_Not_op(b) == a)) {
		return get_mode_all_one(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;
}

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

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

	return tarval_bad;
}

/**
 * Tests whether a shift shifts more bits than available in the mode
 */
static bool is_oversize_shift(const ir_node *n)
{
	ir_node   *count = get_binop_right(n);
	ir_mode   *mode  = get_irn_mode(n);
	ir_tarval *tv    = value_of(count);
	long       modulo_shift;
	long       shiftval;
	if (tv == tarval_bad)
		return false;
	if (!tarval_is_long(tv))
		return false;
	shiftval     = get_tarval_long(tv);
	modulo_shift = get_mode_modulo_shift(mode);
	if (shiftval < 0 || (modulo_shift > 0 && shiftval >= modulo_shift))
		return false;

	return shiftval >= (long)get_mode_size_bits(mode);
}

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

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

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

	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));

	return tarval_bad;
}

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

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

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shr(ta, tb);
	}
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));

	return tarval_bad;
}

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

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

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

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

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

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

bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode)
{
	ir_mode *mode = get_irn_mode(node);
	if (get_mode_arithmetic(mode) != irma_twos_complement
	    || get_mode_arithmetic(dest_mode) != irma_twos_complement)
	    return false;

	if (is_Shl(node)) {
		ir_node *count = get_Shl_right(node);
		if (is_Const(count)) {
			ir_tarval *tv = get_Const_tarval(count);
			if (tarval_is_long(tv)) {
				long shiftval = get_tarval_long(tv);
				long destbits = get_mode_size_bits(dest_mode);
				if (shiftval >= destbits
				    && shiftval < (long)get_mode_modulo_shift(mode))
					return true;
			}
		}
	}
	if (is_And(node)) {
		ir_node *right = get_And_right(node);
		if (is_Const(right)) {
			ir_tarval *tv     = get_Const_tarval(right);
			ir_tarval *conved = tarval_convert_to(tv, dest_mode);
			return tarval_is_null(conved);
		}
	}
	return false;
}

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

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

	if (ir_zero_when_converted(a, mode))
		return get_mode_null(mode);

	return tarval_bad;
}

/**
 * Calculate the value of a Mux: can be evaluated, if the
 * sel and the right input are known.
 */
static ir_tarval *computed_value_Mux(const ir_node *n)
{
	ir_node *sel = get_Mux_sel(n);
	ir_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;
}

/**
 * Calculate the value of a Confirm: can be evaluated,
 * if it has the form Confirm(x, '=', Const).
 */
static ir_tarval *computed_value_Confirm(const ir_node *n)
{
	if (get_Confirm_relation(n) == ir_relation_equal) {
		ir_tarval *tv = value_of(get_Confirm_bound(n));
		if (tv != tarval_bad)
			return tv;
	}
	return value_of(get_Confirm_value(n));
}

/**
 * gives a (conservative) estimation of possible relation when comparing
 * left+right
 */
ir_relation ir_get_possible_cmp_relations(const ir_node *left,
                                          const ir_node *right)
{
	ir_relation possible = ir_relation_true;
	ir_tarval  *tv_l     = value_of(left);
	ir_tarval  *tv_r     = value_of(right);
	ir_mode    *mode     = get_irn_mode(left);
	ir_tarval  *min      = mode == mode_b ? tarval_b_false : get_mode_min(mode);
	ir_tarval  *max      = mode == mode_b ? tarval_b_true  : get_mode_max(mode);

	/* both values known - evaluate them */
	if ((tv_l != tarval_bad) && (tv_r != tarval_bad)) {
		possible = tarval_cmp(tv_l, tv_r);
		/* we can return now, won't get any better */
		return possible;
	}
	/* a == a is never less or greater (but might be equal or unordered) */
	if (left == right)
		possible &= ~ir_relation_less_greater;
	/* unordered results only happen for float compares */
	if (!mode_is_float(mode))
		possible &= ~ir_relation_unordered;
	/* values can never be less than the least representable number or
	 * greater than the greatest representable number */
	if (tv_l == min)
		possible &= ~ir_relation_greater;
	if (tv_l == max)
		possible &= ~ir_relation_less;
	if (tv_r == max)
		possible &= ~ir_relation_greater;
	if (tv_r == min)
		possible &= ~ir_relation_less;
	/* maybe vrp can tell us more */
	possible &= vrp_cmp(left, right);
	/* Alloc nodes never return null (but throw an exception) */
	if (is_Alloc(left) && tarval_is_null(tv_r))
		possible &= ~ir_relation_equal;
	/* stuff known through confirm nodes */
	if (is_Confirm(left) && get_Confirm_bound(left) == right) {
		possible &= get_Confirm_relation(left);
	}
	if (is_Confirm(right) && get_Confirm_bound(right) == left) {
		ir_relation relation = get_Confirm_relation(right);
		relation = get_inversed_relation(relation);
		possible &= relation;
	}

	return possible;
}

static ir_tarval *compute_cmp(const ir_node *cmp)
{
	ir_node    *left     = get_Cmp_left(cmp);
	ir_node    *right    = get_Cmp_right(cmp);
	ir_relation possible = ir_get_possible_cmp_relations(left, right);
	ir_relation relation = get_Cmp_relation(cmp);

	/* if none of the requested relations is possible, return false */
	if ((possible & relation) == ir_relation_false)
		return tarval_b_false;
	/* if possible relations are a subset of the requested ones return true */
	if ((possible & ~relation) == ir_relation_false)
		return tarval_b_true;

	return computed_value_Cmp_Confirm(cmp, left, right, relation);
}

/**
 * Return the value of a Cmp.
 *
 * The basic idea here is to determine which relations are possible and which
 * one are definitely impossible.
 */
static ir_tarval *computed_value_Cmp(const ir_node *cmp)
{
	/* we can't construct Constb after lowering mode_b nodes */
	if (is_irg_state(get_irn_irg(cmp), IR_GRAPH_STATE_MODEB_LOWERED))
		return tarval_bad;

	return compute_cmp(cmp);
}

/**
 * Calculate the value of an integer Div.
 * Special case: 0 / b
 */
static ir_tarval *do_computed_value_Div(const ir_node *div)
{
	const ir_node *a    = get_Div_left(div);
	const ir_node *b    = get_Div_right(div);
	const ir_mode *mode = get_Div_resmode(div);
	ir_tarval     *ta   = value_of(a);
	ir_tarval     *tb;
	const ir_node *dummy;

	/* cannot optimize 0 / b = 0 because of NaN */
	if (!mode_is_float(mode)) {
		if (tarval_is_null(ta) && value_not_zero(b, &dummy))
			return ta;  /* 0 / b == 0 if b != 0 */
	}
	tb = value_of(b);
	if (ta != tarval_bad && tb != tarval_bad)
		return tarval_div(ta, tb);
	return tarval_bad;
}

/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
{
	ir_tarval *ta = value_of(a);
	ir_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;
}

/**
 * Return the value of a Proj(Div).
 */
static ir_tarval *computed_value_Proj_Div(const ir_node *n)
{
	long proj_nr = get_Proj_proj(n);
	if (proj_nr != pn_Div_res)
		return tarval_bad;

	return do_computed_value_Div(get_Proj_pred(n));
}

/**
 * Return the value of a Proj(Mod).
 */
static ir_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 *mod = get_Proj_pred(n);
		return do_computed_value_Mod(get_Mod_left(mod), get_Mod_right(mod));
	}
	return tarval_bad;
}

/**
 * Return the value of a Proj.
 */
static ir_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;
}

/**
 * If the parameter n can be computed, return its value, else tarval_bad.
 * Performs constant folding.
 *
 * @param n  The node this should be evaluated
 */
ir_tarval *computed_value(const ir_node *n)
{
	vrp_attr *vrp = vrp_get_info(n);
	if (vrp != NULL && vrp->bits_set == vrp->bits_not_set)
		return vrp->bits_set;

	if (n->op->ops.computed_value)
		return n->op->ops.computed_value(n);
	return tarval_bad;
}

void 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(Add);
	CASE(And);
	CASE(Borrow);
	CASE(Carry);
	CASE(Cmp);
	CASE(Confirm);
	CASE(Const);
	CASE(Conv);
	CASE(Eor);
	CASE(Minus);
	CASE(Mul);
	CASE(Mux);
	CASE(Not);
	CASE(Or);
	CASE(Proj);
	CASE(Rotl);
	CASE(Shl);
	CASE(Shr);
	CASE(Shrs);
	CASE(Sub);
	CASE(SymConst);
	CASE_PROJ(Div);
	CASE_PROJ(Mod);
	default:
		/* leave NULL */
		break;
	}
#undef CASE_PROJ
#undef CASE
}

/**
 * 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);

	ir_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;
}

/**
 * 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) || is_Or_Eor_Add(a)) {
		ir_node *aa = get_binop_left(a);
		ir_node *ab = get_binop_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) || is_Or_Eor_Add(b)) {
		ir_node *ba = get_binop_left(b);
		ir_node *bb = get_binop_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)) {
		ir_graph *irg = get_irn_irg(n);
		if (get_irg_fp_model(irg) & 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) {
			/* (a - x) + x */

			n = get_Sub_left(left);
			if (mode == get_irn_mode(n)) {
				DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
				return n;
			}
		}
	}
	if (is_Sub(right)) {
		if (get_Sub_right(right) == left) {
			/* x + (a - x) */

			n = get_Sub_left(right);
			if (mode == get_irn_mode(n)) {
				DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
				return n;
			}
		}
	}
	return n;
}

/**
 * optimize operations that are not commutative but have neutral 0 on left,
 * so a op 0 = a.
 */
static ir_node *equivalent_node_left_zero(ir_node *n)
{
	ir_node *oldn = n;

	ir_node   *a  = get_binop_left(n);
	ir_node   *b  = get_binop_right(n);
	ir_tarval *tb = value_of(b);

	if (tarval_is_null(tb)) {
		n = a;

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

#define equivalent_node_Shl   equivalent_node_left_zero
#define equivalent_node_Shr   equivalent_node_left_zero
#define equivalent_node_Shrs  equivalent_node_left_zero
#define equivalent_node_Rotl  equivalent_node_left_zero

/**
 * 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 a Sub may be different than the mode of its
 * predecessors, so we could not return a predecessors in all cases.
 */
static ir_node *equivalent_node_Sub(ir_node *n)
{
	ir_node   *oldn = n;
	ir_node   *b;
	ir_mode   *mode = get_irn_mode(n);
	ir_tarval *tb;

	/* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
	if (mode_is_float(mode)) {
		ir_graph *irg = get_irn_irg(n);
		if (get_irg_fp_model(irg) & fp_strict_algebraic)
			return n;
	}

	b  = get_Sub_right(n);
	tb = value_of(b);

	/* Beware: modes might be different */
	if (tarval_is_null(tb)) {
		ir_node