iropt.c

/*
 * This file is part of libFirm.
 * Copyright (C) 2012 University of Karlsruhe.
 */

/**
 * @file
 * @brief   iropt --- optimizations intertwined with IR construction.
 * @author  Christian Schaefer, Goetz Lindenmaier, Michael Beck
 */
#include <string.h>
#include <stdbool.h>

#include "constbits.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 "irgopt.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_t.h"
#include "hashptr.h"
#include "irtools.h"
#include "irhooks.h"
#include "array.h"
#include "vrp.h"
#include "firm_types.h"
#include "bitfiddle.h"
#include "be.h"
#include "panic.h"
#include "firmstat_t.h"

#include "entity_t.h"

static int imprecise_float_transforms_allowed;

void ir_allow_imprecise_float_transforms(int enable)
{
	imprecise_float_transforms_allowed = enable;
}

int ir_imprecise_float_transforms_allowed(void)
{
	return imprecise_float_transforms_allowed;
}

/** Returns true if using an Add, Eor or Or instead of @p node would produce
 * the same result. */
static bool is_Or_Eor_Add(const ir_node *node)
{
	if (is_Or(node) || is_Eor(node) || is_Add(node)) {
		const ir_node *const left  = get_binop_left(node);
		const ir_node *const right = get_binop_right(node);
		const bitinfo *const bl    = get_bitinfo(left);
		const bitinfo *const br    = get_bitinfo(right);
		/* 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/Or.
		 */
		if (bl && br && tarval_is_null(tarval_and(bl->z, br->z))) {
			return true;
		}
	}
	return false;
}

/** Returns true if using an Add or Eor instead of @p node would produce the
 * same result. */
static bool is_Eor_Add(const ir_node *node)
{
	if (is_Or_Eor_Add(node))
		return true;
	if (!is_Eor(node) && !is_Add(node))
		return false;

	const ir_mode *mode = get_irn_mode(node);
	if (get_mode_arithmetic(mode) != irma_twos_complement)
		return false;

	const ir_node *const left        = get_binop_left(node);
	const ir_node *const right       = get_binop_right(node);
	const bitinfo *const bl          = get_bitinfo(left);
	const bitinfo *const br          = get_bitinfo(right);
	const int            highest_bit = (int)get_mode_size_bits(mode) - 1;

	return (bl && get_tarval_lowest_bit(bl->z) == highest_bit) ||
	       (br && get_tarval_lowest_bit(br->z) == highest_bit);
}

/**
 * If node produces a left shift with a constant value return that value.
 * This matches for x << c and x * C2 with C2 being a power of 2.
 */
static ir_tarval *is_shl_const_like(const ir_node *node)
{
	if (is_Shl(node)) {
		ir_node *right = get_Shl_right(node);
		if (is_Const(right))
			return get_Const_tarval(right);
	} else if (is_Mul(node)) {
		ir_node *right = get_Mul_right(node);
		if (is_Const(right)) {
			const ir_tarval *tv = get_Const_tarval(right);
			/* is value a power of 2? */
			if (get_tarval_popcount(tv) == 1) {
				int low_bit = get_tarval_lowest_bit(tv);
				return new_tarval_from_long(low_bit, get_tarval_mode(tv));
			}
		}
	}
	return NULL;
}

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

value_of_func value_of_ptr = default_value_of;

void set_value_of_func(value_of_func func)
{
	if (func != NULL)
		value_of_ptr = func;
	else
		value_of_ptr = default_value_of;
}

int value_not_null(const ir_node *n, const ir_node **confirm)
{
	if (confirm)
		*confirm = NULL;

	/* walk confirm sequence and look for matching confirms */
	for (;;) {
		/* -x != 0  =>  x != 0 */
		if (is_Minus(n)) {
			n = get_Minus_op(n);
			continue;
		}
		/* we can ignore Sels/Members: either the base pointer points to null or
		 * if it does not then members addresses cannot be at NULL or we have
		 * undefined behavior because we are obviously not pointing to an
		 * object. */
		if (is_Sel(n)) {
			n = get_Sel_ptr(n);
			continue;
		} else if (is_Member(n)) {
			n = get_Member_ptr(n);
			continue;
		}

		if (!is_Confirm(n))
			break;

		ir_node *bound = get_Confirm_bound(n);
		if (!is_Const(bound)) {
			n = get_Confirm_value(n);
			continue;
		}
		ir_tarval  *tv       = get_Const_tarval(bound);
		ir_mode    *mode     = get_irn_mode(n);
		ir_tarval  *null     = get_mode_null(mode);
		ir_relation relation = tarval_cmp(tv, null);

		switch (get_Confirm_relation(n)) {
		case ir_relation_equal: /* n == C && C != 0 ==> n != 0 */
			if (relation != ir_relation_equal)
				goto confirmed;
			break;
		case ir_relation_less_greater: /* n != C /\ C == 0 ==> n != 0 */
			if (relation == ir_relation_equal)
				goto confirmed;
			break;
		case ir_relation_less: /* n <  C /\ C <= 0 ==> n != 0 */
			if (relation == ir_relation_less || relation == ir_relation_equal)
				goto confirmed;
			break;
		case ir_relation_less_equal: /* n <= C /\ C <  0 ==> n != 0 */
			if (relation == ir_relation_less)
				goto confirmed;
			break;
		case ir_relation_greater_equal: /* n >= C /\ C >  0 ==> n != 0 */
			if (relation == ir_relation_greater)
				goto confirmed;
			break;
		case ir_relation_greater: /* n >  C /\ C >= 0 ==> n != 0 */
			if (relation == ir_relation_greater
			    || relation == ir_relation_equal) {
confirmed:
				if (confirm)
					*confirm = n;
				return true;
			}
			break;
		default:
			break;
		}
		n = get_Confirm_value(n);
	}

	if (is_Const(n)) {
		ir_tarval *tv = get_Const_tarval(n);
		return !tarval_is_null(tv);
	}

	/* global entities are never NULL */
	if (is_Address(n))
		return true;

	/* the frame pointer is never NULL */
	if (is_Proj(n) && is_Start(get_Proj_pred(n))
	    && get_Proj_num(n) == pn_Start_P_frame_base)
	    return true;

	/* alloc never returns NULL (but throws an exception in the error case) */
	if (is_Alloc(n))
		return true;

	const bitinfo *bi = get_bitinfo(n);
	if (bi != NULL && !tarval_is_null(bi->o))
		return true;

	/* for all we know the value may be null */
	return false;
}

/**
 * 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 an Offset.
 */
static ir_tarval *computed_value_Offset(const ir_node *n)
{
	const ir_entity *ent  = get_Offset_entity(n);
	const ir_type   *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));
	return tarval_unknown;
}

/**
 * Return the value of an Align.
 */
static ir_tarval *computed_value_Align(const ir_node *n)
{
	ir_type *const type = get_Align_type(n);
	if (get_type_state(type) == layout_fixed)
		return new_tarval_from_long(get_type_alignment_bytes(type), get_irn_mode(n));
	return tarval_unknown;
}

/**
 * Return the value of a Size.
 */
static ir_tarval *computed_value_Size(const ir_node *n)
{
	ir_type *const type = get_Size_type(n);
	if (get_type_state(type) == layout_fixed)
		return new_tarval_from_long(get_type_size_bytes(type), get_irn_mode(n));
	return tarval_unknown;
}

static bool complement_values(const ir_node *a, const ir_node *b)
{
	if (is_Eor(a) && is_Eor(b) && get_Eor_left(a) == get_Eor_left(b)) {
		a = get_Eor_right(a);
		b = get_Eor_right(b);
	}
	if ((is_Not(a) && get_Not_op(a) == b) ||
	    (is_Not(b) && get_Not_op(b) == a))
		return true;
	if (is_Const(a) && is_Const(b)) {
		ir_tarval *const tv_a = get_Const_tarval(a);
		ir_tarval *const tv_b = get_Const_tarval(b);
		return tarval_is_all_one(tarval_eor(tv_a, tv_b));
	}
	return false;
}

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

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

	/* x+~x => -1 */
	if (complement_values(a, b))
		return get_mode_all_one(get_irn_mode(n));
	/* x + -x => 0 */
	if (ir_is_negated_value(a, b)) {
		ir_mode *mode = get_irn_mode(n);
		if (get_mode_arithmetic(mode) == irma_twos_complement)
			return get_mode_null(mode);
	}

	return tarval_unknown;
}

/**
 * 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);
	const ir_node *a    = get_Sub_left(n);
	const ir_node *b    = get_Sub_right(n);

	/* a - a == 0 (not possible for float because NaN - NaN == NaN */
	if (get_mode_arithmetic(mode) == irma_twos_complement &&
	    (a == b ||
	     (is_Confirm(a) && is_Confirm(b) &&
	      get_Confirm_relation(a) == ir_relation_equal &&
	      get_Confirm_relation(b) == ir_relation_equal &&
	      get_Confirm_bound(a) == get_Confirm_value(b) &&
	      get_Confirm_bound(b) == get_Confirm_value(a)))) {
		return get_mode_null(mode);
	}

	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_sub(ta, tb, mode);

	return tarval_unknown;
}

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

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

	return tarval_unknown;
}

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

	if (ta != tarval_unknown && tb != tarval_unknown) {
		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 (tarval_is_null(ta))
				return ta;
			if (tarval_is_null(tb))
				return tb;
		}
	}
	return tarval_unknown;
}

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

	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_and(ta, tb);

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

	/* x&~x => 0 */
	if (complement_values(a, b))
		return get_mode_null(get_irn_mode(n));

	return tarval_unknown;
}

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

	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_or(ta, tb);

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

	/* x|~x => ~0 */
	if (complement_values(a, b))
		return get_mode_all_one(get_irn_mode(n));

	return tarval_unknown;
}

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

	/* a ^ a == 0 */
	if (a == b ||
	    (is_Confirm(a) && is_Confirm(b) &&
	     get_Confirm_relation(a) == ir_relation_equal &&
	     get_Confirm_relation(b) == ir_relation_equal &&
	     get_Confirm_bound(a) == get_Confirm_value(b) &&
	     get_Confirm_bound(b) == get_Confirm_value(a))) {
		return get_mode_null(get_irn_mode(n));
	}

	/* x^~x => ~0 */
	if (complement_values(a, b))
		return get_mode_all_one(get_irn_mode(n));

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

	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_eor(ta, tb);
	return tarval_unknown;
}

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

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

	return tarval_unknown;
}

/**
 * Tests whether a shift shifts more bits than available in the mode
 */
static bool is_oversize_shift(const ir_node *n)
{
	const ir_node *count = get_binop_right(n);
	ir_tarval     *tv    = value_of(count);
	if (!tarval_is_constant(tv))
		return false;
	/* adjust for modulo shift */
	ir_mode *mode         = get_irn_mode(n);
	unsigned modulo_shift = get_mode_modulo_shift(mode);
	if (modulo_shift > 0) {
		if (modulo_shift <= get_mode_size_bits(mode))
			return false;
		ir_tarval *modulo_shift_val
			= new_tarval_from_long(modulo_shift, get_tarval_mode(tv));
		tv = tarval_mod(tv, modulo_shift_val);
	}
	if (!tarval_is_long(tv))
		return false;

	long shiftval = get_tarval_long(tv);
	return shiftval < 0 || shiftval >= (long)get_mode_size_bits(mode);
}

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

	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_shl(ta, tb);
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));

	return tarval_unknown;
}

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

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

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

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

bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode)
{
	const 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;

	ir_tarval *tv = is_shl_const_like(node);
	if (tv != NULL && 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)
{
	const ir_node *a    = get_Conv_op(n);
	ir_tarval     *ta   = value_of(a);
	ir_mode       *mode = get_irn_mode(n);

	if (ta != tarval_unknown)
		return tarval_convert_to(ta, mode);
	if (ir_zero_when_converted(a, mode))
		return get_mode_null(mode);

	return tarval_unknown;
}

static ir_tarval *computed_value_Bitcast(const ir_node *n)
{
	const ir_node *op = get_Bitcast_op(n);
	ir_tarval     *ta = value_of(op);
	if (ta == tarval_unknown)
		return tarval_unknown;

	ir_mode *mode = get_irn_mode(n);
	return tarval_bitcast(ta, mode);
}

/**
 * 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)
{
	const ir_node   *sel = get_Mux_sel(n);
	const 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_unknown;
}

/**
 * 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)
{
	const ir_node     *bound    = get_Confirm_bound(n);
	const ir_node     *value    = get_Confirm_value(n);
	const ir_relation  possible = ir_get_possible_cmp_relations(value, bound);
	const ir_relation  relation = get_Confirm_relation(n);

	switch (possible & relation) {
	case ir_relation_false:
		return tarval_bad;

	case ir_relation_equal: {
		ir_tarval *tv = value_of(bound);
		if (tarval_is_constant(tv))
			return tv;
		break;
	}
	}

	return value_of(value);
}

static ir_node *get_commutative_other_op(const ir_node *const node, const ir_node *const op)
{
	assert(is_op_commutative(get_irn_op(node)));
	ir_node *const l = get_binop_left(node);
	ir_node *const r = get_binop_right(node);
	if (l == op)
		return r;
	if (r == op)
		return l;
	return NULL;
}

/**
 * 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;
	const ir_tarval *tv_l     = value_of(left);
	const ir_tarval *tv_r     = value_of(right);

	/* both values known - evaluate them */
	if (tv_l != tarval_unknown && tv_r != tarval_unknown) {
		possible = tarval_cmp(tv_l, tv_r);
		/* we can return now, won't get any better */
		return possible;
	}

	/* NaN never compares successfully to anything */
	if (tarval_is_nan(tv_l) || tarval_is_nan(tv_r)) {
		return ir_relation_unordered;
	}

	/* 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 */
	const ir_mode *mode = get_irn_mode(left);
	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 */
	ir_tarval       *min = get_mode_min(mode);
	const ir_tarval *max = get_mode_max(mode);
	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;

	/* Try to use bit information. */
	const bitinfo *const bl = get_bitinfo(left);
	const bitinfo *const br = get_bitinfo(right);
	if (bl != NULL && br != NULL) {
		ir_tarval *const l_o   = bl->o;
		ir_tarval *const l_z   = bl->z;
		ir_tarval *const r_o   = br->o;
		ir_tarval *const r_z   = br->z;
		if (get_mode_arithmetic(mode) == irma_twos_complement) {
			/* Compute min/max values of operands. */
			ir_tarval *l_max = tarval_and(l_z, tarval_ornot(l_o, min));
			ir_tarval *l_min = tarval_or(l_o, tarval_and(l_z, min));
			ir_tarval *r_max = tarval_and(r_z, tarval_ornot(r_o, min));
			ir_tarval *r_min = tarval_or(r_o, tarval_and(r_z, min));

			if (!(tarval_cmp(l_max, r_min) & ir_relation_greater)) {
				possible &= ~ir_relation_greater;
			}
			if (!(tarval_cmp(l_min, r_max) & ir_relation_less)) {
				possible &= ~ir_relation_less;
			}
		}

		if (!tarval_is_null(tarval_andnot(l_o, r_z))
		    || !tarval_is_null(tarval_andnot(r_o, l_z))) {
			possible &= ~ir_relation_equal;
		}
	}

	/* 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;
	if (is_And(left) && !mode_is_signed(mode) && get_commutative_other_op(left, right))
		possible &= ~ir_relation_greater;
	if (is_And(right) && !mode_is_signed(mode) && get_commutative_other_op(right, left))
		possible &= ~ir_relation_less;
	/* 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;
}

/**
 * Checks whether we can use @p relation instead of @p cmp_relation,
 * if only some relations are @p possible.
 *
 * @param relation      The relation to check for
 * @param cmp_relation  The current relation of the Cmp
 * @param possible      The possible relations of the Cmp
 */
static bool is_relation(ir_relation relation, ir_relation cmp_relation, ir_relation possible)
{
	ir_relation min           = cmp_relation & possible;
	ir_relation possible_bits = relation & ~possible;

	return (min | possible_bits) == relation;
}

/**
 * Check whether we can use @p relation or its ordered complement instead of @p
 * cmp_relation, if only some relations are @p possible.
 *
 * @param relation      The relation to check for
 * @param cmp_relation  The current relation of the Cmp
 * @param possible      The possible relations of the Cmp
 * @return The replacement relation or ir_relation_false, if neither is
 *         possible.
 */
static ir_relation get_complementary_relations(ir_relation const relation, ir_relation const cmp_relation, ir_relation const possible)
{
	assert(possible != ir_relation_false);
	if (is_relation(relation, cmp_relation, possible))
		return relation;
	ir_relation const compl = relation ^ ir_relation_less_equal_greater;
	if (is_relation(compl, cmp_relation, possible))
		return compl;
	return ir_relation_false;
}

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

	/* we have some special rules for == 0 and != 0 */
	ir_relation const rel_eq = get_complementary_relations(ir_relation_equal, relation, possible);
	if (rel_eq != ir_relation_false && is_Const(right) && is_Const_null(right) && value_not_null(left, NULL))
		return rel_eq != ir_relation_equal ? tarval_b_true : tarval_b_false;

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

/**
 * some people want to call compute_cmp directly, in this case we have to
 * test the constant folding flag again
 */
static ir_tarval *compute_cmp_ext(const ir_node *cmp)
{
	if (!get_opt_constant_folding())
		return tarval_unknown;
	return computed_value_Cmp(cmp);
}

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

	/* cannot optimize 0 / b = 0 because of NaN */
	if (tarval_is_null(ta)) {
		ir_mode *mode = get_irn_mode(a);
		if (get_mode_arithmetic(mode) == irma_twos_complement
		    && value_not_null(b, NULL)) {
			return ta;  /* 0 / b == 0 if b != 0 */
		}
	}
	if (a == b) {
		ir_mode *mode = get_irn_mode(a);
		/* a/a => 1 */
		if (get_mode_arithmetic(mode) == irma_twos_complement)
			return get_mode_one(mode);
	}
	ir_tarval *tb = value_of(b);
	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_div(ta, tb);
	return tarval_unknown;
}

/**
 * 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 *tb = value_of(b);
	/* a % 1 == 0 */
	/* a % -1 == 0 */
	ir_mode *mode = get_irn_mode(a);
	if (tarval_is_one(tb)
	    || (mode_is_signed(mode) && tarval_is_all_one(tb)))
		return get_mode_null(mode);

	/* constant folding */
	ir_tarval *ta = value_of(a);
	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_mod(ta, tb);

	/* 0 % b == 0 if b != 0 */
	/* a % a == 0 if a != 0 */
	if (tarval_is_null(ta) || a == b) {
		assert(get_mode_arithmetic(mode) == irma_twos_complement);
		if (value_not_null(b, NULL))
			return get_mode_null(mode);
	}

	return tarval_unknown;
}

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

	const ir_node *div   = get_Proj_pred(n);
	const ir_node *left  = get_Div_left(div);
	const ir_node *right = get_Div_right(div);
	return do_computed_value_Div(left, right);
}

/**
 * Return the value of a Proj(Mod).
 */
static ir_tarval *computed_value_Proj_Mod(const ir_node *n)
{
	unsigned proj_nr = get_Proj_num(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_unknown;
}

/**
 * Return the value of a Proj.
 */
static ir_tarval *computed_value_Proj(const ir_node *proj)
{
	const 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_unknown;
}

/**
 * If the parameter n can be computed, return its value, else tarval_unknown.
 * Performs constant folding.
 *
 * @param n  The node this should be evaluated
 */
ir_tarval *computed_value(const ir_node *n)
{