+ ir_relation relation;
+ ir_node *right = get_Cmp_right(node);
+
+ if (!is_Const(right) || !is_Const_null(right))
+ return false;
+ relation = get_Cmp_relation(node);
+ return relation == ir_relation_equal
+ || relation == ir_relation_less_greater
+ || (!mode_is_signed(get_irn_mode(right))
+ && relation == ir_relation_greater);
+}
+
+/**
+ * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
+ * Such pattern may arise in bitfield stores.
+ *
+ * value c4 value c4 & c2
+ * AND c3 AND c1 | c3
+ * OR c2 ===> OR
+ * AND c1
+ * OR
+ *
+ *
+ * value c2 value c1
+ * AND c1 ===> OR if (c1 | c2) == 0x111..11
+ * OR
+ */
+static ir_node *transform_node_Or_bf_store(ir_node *irn_or)
+{
+ ir_node *irn_and, *c1;
+ ir_node *or_l, *c2;
+ ir_node *and_l, *c3;
+ ir_node *value, *c4;
+ ir_node *new_and, *new_const, *block;
+ ir_mode *mode = get_irn_mode(irn_or);
+
+ ir_tarval *tv1, *tv2, *tv3, *tv4, *tv;
+
+ for (;;) {
+ ir_graph *irg;
+ irn_and = get_binop_left(irn_or);
+ c1 = get_binop_right(irn_or);
+ if (!is_Const(c1) || !is_And(irn_and))
+ return irn_or;
+
+ or_l = get_binop_left(irn_and);
+ c2 = get_binop_right(irn_and);
+ if (!is_Const(c2))
+ return irn_or;
+
+ tv1 = get_Const_tarval(c1);
+ tv2 = get_Const_tarval(c2);
+
+ tv = tarval_or(tv1, tv2);
+ if (tarval_is_all_one(tv)) {
+ /* the AND does NOT clear a bit with isn't set by the OR */
+ set_binop_left(irn_or, or_l);
+ set_binop_right(irn_or, c1);
+
+ /* check for more */
+ continue;
+ }
+
+ if (!is_Or(or_l) && !is_Or_Eor_Add(or_l))
+ return irn_or;
+
+ and_l = get_binop_left(or_l);
+ c3 = get_binop_right(or_l);
+ if (!is_Const(c3) || !is_And(and_l))
+ return irn_or;
+
+ value = get_binop_left(and_l);
+ c4 = get_binop_right(and_l);
+ if (!is_Const(c4))
+ return irn_or;
+
+ /* ok, found the pattern, check for conditions */
+ assert(mode == get_irn_mode(irn_and));
+ assert(mode == get_irn_mode(or_l));
+ assert(mode == get_irn_mode(and_l));
+
+ tv3 = get_Const_tarval(c3);
+ tv4 = get_Const_tarval(c4);
+
+ tv = tarval_or(tv4, tv2);
+ if (!tarval_is_all_one(tv)) {
+ /* have at least one 0 at the same bit position */
+ return irn_or;
+ }
+
+ if (tv3 != tarval_andnot(tv3, tv4)) {
+ /* bit in the or_mask is outside the and_mask */
+ return irn_or;
+ }
+
+ if (tv1 != tarval_andnot(tv1, tv2)) {
+ /* bit in the or_mask is outside the and_mask */
+ return irn_or;
+ }
+
+ /* ok, all conditions met */
+ block = get_irn_n(irn_or, -1);
+ irg = get_irn_irg(block);
+
+ new_and = new_r_And(block, value, new_r_Const(irg, tarval_and(tv4, tv2)), mode);
+
+ new_const = new_r_Const(irg, tarval_or(tv3, tv1));
+
+ set_binop_left(irn_or, new_and);
+ set_binop_right(irn_or, new_const);
+
+ /* check for more */
+ }
+}
+
+/**
+ * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rotl
+ */
+static ir_node *transform_node_Or_Rotl(ir_node *irn_or)
+{
+ ir_mode *mode = get_irn_mode(irn_or);
+ ir_node *shl, *shr, *block;
+ ir_node *irn, *x, *c1, *c2, *n;
+ ir_tarval *tv1, *tv2;
+
+ /* some backends can't handle rotl */
+ if (!be_get_backend_param()->support_rotl)
+ return irn_or;
+
+ if (! mode_is_int(mode))
+ return irn_or;
+
+ shl = get_binop_left(irn_or);
+ shr = get_binop_right(irn_or);
+
+ if (is_Shr(shl)) {
+ if (!is_Shl(shr))
+ return irn_or;
+
+ irn = shl;
+ shl = shr;
+ shr = irn;
+ } else if (!is_Shl(shl)) {
+ return irn_or;
+ } else if (!is_Shr(shr)) {
+ return irn_or;
+ }
+ x = get_Shl_left(shl);
+ if (x != get_Shr_left(shr))
+ return irn_or;
+
+ c1 = get_Shl_right(shl);
+ c2 = get_Shr_right(shr);
+ if (is_Const(c1) && is_Const(c2)) {
+ tv1 = get_Const_tarval(c1);
+ if (! tarval_is_long(tv1))
+ return irn_or;
+
+ tv2 = get_Const_tarval(c2);
+ if (! tarval_is_long(tv2))
+ return irn_or;
+
+ if (get_tarval_long(tv1) + get_tarval_long(tv2)
+ != (int) get_mode_size_bits(mode))
+ return irn_or;
+
+ /* yet, condition met */
+ block = get_nodes_block(irn_or);
+
+ n = new_r_Rotl(block, x, c1, mode);
+
+ DBG_OPT_ALGSIM1(irn_or, shl, shr, n, FS_OPT_OR_SHFT_TO_ROTL);
+ return n;
+ }
+
+ /* Note: the obvious rot formulation (a << x) | (a >> (32-x)) gets
+ * transformed to (a << x) | (a >> -x) by transform_node_shift_modulo() */
+ if (!ir_is_negated_value(c1, c2)) {
+ return irn_or;
+ }
+
+ /* yet, condition met */
+ block = get_nodes_block(irn_or);
+ n = new_r_Rotl(block, x, c1, mode);
+ DBG_OPT_ALGSIM0(irn_or, n, FS_OPT_OR_SHFT_TO_ROTL);
+ return n;
+}
+
+/**
+ * Prototype of a recursive transform function
+ * for bitwise distributive transformations.
+ */
+typedef ir_node* (*recursive_transform)(ir_node *n);
+
+/**
+ * makes use of distributive laws for and, or, eor
+ * and(a OP c, b OP c) -> and(a, b) OP c
+ * note, might return a different op than n
+ */
+static ir_node *transform_bitwise_distributive(ir_node *n,
+ recursive_transform trans_func)
+{
+ ir_node *oldn = n;
+ ir_node *a = get_binop_left(n);
+ ir_node *b = get_binop_right(n);
+ ir_op *op = get_irn_op(a);
+ ir_op *op_root = get_irn_op(n);
+
+ if (op != get_irn_op(b))
+ return n;
+
+ /* and(conv(a), conv(b)) -> conv(and(a,b)) */
+ if (op == op_Conv) {
+ ir_node *a_op = get_Conv_op(a);
+ ir_node *b_op = get_Conv_op(b);
+ ir_mode *a_mode = get_irn_mode(a_op);
+ ir_mode *b_mode = get_irn_mode(b_op);
+ if (a_mode == b_mode && (mode_is_int(a_mode) || a_mode == mode_b)) {
+ ir_node *blk = get_nodes_block(n);
+
+ n = exact_copy(n);
+ set_binop_left(n, a_op);
+ set_binop_right(n, b_op);
+ set_irn_mode(n, a_mode);
+ n = trans_func(n);
+ n = new_r_Conv(blk, n, get_irn_mode(oldn));
+
+ DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_CONV);
+ return n;
+ }
+ }
+
+ if (op == op_Eor) {
+ /* nothing to gain here */
+ return n;
+ }
+
+ if (op == op_Shrs || op == op_Shr || op == op_Shl
+ || op == op_And || op == op_Or || op == op_Eor) {
+ ir_node *a_left = get_binop_left(a);
+ ir_node *a_right = get_binop_right(a);
+ ir_node *b_left = get_binop_left(b);
+ ir_node *b_right = get_binop_right(b);
+ ir_node *c = NULL;
+ ir_node *op1 = NULL;
+ ir_node *op2 = NULL;
+
+ if (is_op_commutative(op)) {
+ if (a_left == b_left) {
+ c = a_left;
+ op1 = a_right;
+ op2 = b_right;
+ } else if (a_left == b_right) {
+ c = a_left;
+ op1 = a_right;
+ op2 = b_left;
+ } else if (a_right == b_left) {
+ c = a_right;
+ op1 = a_left;
+ op2 = b_right;
+ }
+ }
+ if (a_right == b_right) {
+ c = a_right;
+ op1 = a_left;
+ op2 = b_left;
+ }
+
+ if (c != NULL) {
+ /* (a sop c) & (b sop c) => (a & b) sop c */
+ ir_node *blk = get_nodes_block(n);
+
+ ir_node *new_n = exact_copy(n);
+ set_binop_left(new_n, op1);
+ set_binop_right(new_n, op2);
+ new_n = trans_func(new_n);
+
+ if (op_root == op_Eor && op == op_Or) {
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_mode *mode = get_irn_mode(c);
+
+ c = new_rd_Not(dbgi, blk, c, mode);
+ n = new_rd_And(dbgi, blk, new_n, c, mode);
+ } else {
+ n = exact_copy(a);
+ set_nodes_block(n, blk);
+ set_binop_left(n, new_n);
+ set_binop_right(n, c);
+ add_identities(n);
+ }
+
+ DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_SHIFT_AND);
+ return n;
+ }
+ }
+
+ return n;
+}
+
+/**
+ * normalisation: (x >> c1) & c2 to (x & (c2<<c1)) >> c1
+ * (we can use:
+ * - and, or, xor instead of &
+ * - Shl, Shr, Shrs, rotl instead of >>
+ * (with a special case for Or/Xor + Shrs)
+ *
+ * This normalisation is usually good for the backend since << C can often be
+ * matched as address-mode.
+ */
+static ir_node *transform_node_bitop_shift(ir_node *n)
+{
+ ir_graph *irg = get_irn_irg(n);
+ ir_node *left = get_binop_left(n);
+ ir_node *right = get_binop_right(n);
+ ir_mode *mode = get_irn_mode(n);
+ ir_node *shift_left;
+ ir_node *shift_right;
+ ir_node *block;
+ dbg_info *dbg_bitop;
+ dbg_info *dbg_shift;
+ ir_node *new_bitop;
+ ir_node *new_shift;
+ ir_node *new_const;
+ ir_tarval *tv1;
+ ir_tarval *tv2;
+ ir_tarval *tv_bitop;
+
+ if (!irg_is_constrained(irg, IR_GRAPH_CONSTRAINT_NORMALISATION2))
+ return n;
+
+ assert(is_And(n) || is_Or(n) || is_Eor(n) || is_Or_Eor_Add(n));
+ if (!is_Const(right) || !is_shiftop(left))
+ return n;
+
+ shift_left = get_binop_left(left);
+ shift_right = get_binop_right(left);
+ if (!is_Const(shift_right))
+ return n;
+
+ /* doing it with Shrs is not legal if the Or/Eor affects the topmost bit */
+ if (is_Shrs(left)) {
+ /* TODO this could be improved */
+ return n;
+ }
+
+ irg = get_irn_irg(n);
+ block = get_nodes_block(n);
+ dbg_bitop = get_irn_dbg_info(n);
+ dbg_shift = get_irn_dbg_info(left);
+ tv1 = get_Const_tarval(shift_right);
+ tv2 = get_Const_tarval(right);
+ assert(get_tarval_mode(tv2) == mode);
+
+ if (is_Shl(left)) {
+ tv_bitop = tarval_shr(tv2, tv1);
+
+ /* Check whether we have lost some bits during the right shift. */
+ if (!is_And(n)) {
+ ir_tarval *tv_back_again = tarval_shl(tv_bitop, tv1);
+
+ if (tarval_cmp(tv_back_again, tv2) != ir_relation_equal)
+ return n;
+ }
+ } else if (is_Shr(left)) {
+ if (!is_And(n)) {
+ /*
+ * TODO this can be improved by checking whether
+ * the left shift produces an overflow
+ */
+ return n;
+ }
+ tv_bitop = tarval_shl(tv2, tv1);
+ } else {
+ assert(is_Rotl(left));
+ tv_bitop = tarval_rotl(tv2, tarval_neg(tv1));
+ }
+ new_const = new_r_Const(irg, tv_bitop);
+
+ if (is_And(n)) {
+ new_bitop = new_rd_And(dbg_bitop, block, shift_left, new_const, mode);
+ } else if (is_Or(n) || is_Or_Eor_Add(n)) {
+ new_bitop = new_rd_Or(dbg_bitop, block, shift_left, new_const, mode);
+ } else {
+ assert(is_Eor(n));
+ new_bitop = new_rd_Eor(dbg_bitop, block, shift_left, new_const, mode);
+ }
+
+ if (is_Shl(left)) {
+ new_shift = new_rd_Shl(dbg_shift, block, new_bitop, shift_right, mode);
+ } else if (is_Shr(left)) {
+ new_shift = new_rd_Shr(dbg_shift, block, new_bitop, shift_right, mode);
+ } else {
+ assert(is_Rotl(left));
+ new_shift = new_rd_Rotl(dbg_shift, block, new_bitop, shift_right, mode);
+ }
+
+ return new_shift;
+}
+
+static bool complement_values(const ir_node *a, const ir_node *b)
+{
+ if (is_Not(a) && get_Not_op(a) == b)
+ return true;
+ if (is_Not(b) && get_Not_op(b) == a)
+ return true;
+ if (is_Const(a) && is_Const(b)) {
+ ir_tarval *tv_a = get_Const_tarval(a);
+ ir_tarval *tv_b = get_Const_tarval(b);
+ return tarval_not(tv_a) == tv_b;
+ }
+ return false;
+}
+
+typedef ir_tarval *(tv_fold_binop_func)(ir_tarval *a, ir_tarval *b);
+
+/**
+ * for associative operations fold:
+ * op(op(x, c0), c1) to op(x, op(c0, c1)) with constants folded.
+ * This is a "light" version of the reassociation phase
+ */
+static ir_node *fold_constant_associativity(ir_node *node,
+ tv_fold_binop_func fold)
+{
+ ir_graph *irg;
+ ir_op *op;
+ ir_node *left;
+ ir_node *right = get_binop_right(node);
+ ir_node *left_right;
+ ir_node *left_left;
+ ir_tarval *c0;
+ ir_tarval *c1;
+ ir_tarval *new_c;
+ ir_node *new_const;
+ ir_node *new_node;
+ if (!is_Const(right))
+ return node;
+
+ op = get_irn_op(node);
+ left = get_binop_left(node);
+ if (get_irn_op(left) != op)
+ return node;
+
+ left_right = get_binop_right(left);
+ if (!is_Const(left_right))
+ return node;
+
+ left_left = get_binop_left(left);
+ c0 = get_Const_tarval(left_right);
+ c1 = get_Const_tarval(right);
+ irg = get_irn_irg(node);
+ if (get_tarval_mode(c0) != get_tarval_mode(c1))
+ return node;
+ new_c = fold(c0, c1);
+ if (new_c == tarval_bad)
+ return node;
+ new_const = new_r_Const(irg, new_c);
+ new_node = exact_copy(node);
+ set_binop_left(new_node, left_left);
+ set_binop_right(new_node, new_const);
+ return new_node;
+}
+
+/**
+ * Transform an Or.
+ */
+static ir_node *transform_node_Or_(ir_node *n)
+{
+ ir_node *oldn = n;
+ ir_node *a = get_binop_left(n);
+ ir_node *b = get_binop_right(n);
+ ir_node *c;
+ ir_mode *mode;
+
+ n = fold_constant_associativity(n, tarval_or);
+ if (n != oldn)
+ return n;
+
+ if (is_Not(a) && is_Not(b)) {
+ /* ~a | ~b = ~(a&b) */
+ ir_node *block = get_nodes_block(n);
+
+ mode = get_irn_mode(n);
+ a = get_Not_op(a);
+ b = get_Not_op(b);
+ n = new_rd_And(get_irn_dbg_info(n), block, a, b, mode);
+ n = new_rd_Not(get_irn_dbg_info(n), block, n, mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_DEMORGAN);
+ return n;
+ }
+
+ /* we can combine the relations of two compares with the same operands */
+ if (is_Cmp(a) && is_Cmp(b)) {
+ ir_node *a_left = get_Cmp_left(a);
+ ir_node *a_right = get_Cmp_right(a);
+ ir_node *b_left = get_Cmp_left(b);
+ ir_node *b_right = get_Cmp_right(b);
+ if (a_left == b_left && b_left == b_right) {
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_node *block = get_nodes_block(n);
+ ir_relation a_relation = get_Cmp_relation(a);
+ ir_relation b_relation = get_Cmp_relation(b);
+ ir_relation new_relation = a_relation | b_relation;
+ return new_rd_Cmp(dbgi, block, a_left, a_right, new_relation);
+ }
+ /* Cmp(a!=b) or Cmp(c!=d) => Cmp((a^b)|(c^d) != 0) */
+ if (is_cmp_unequal(a) && is_cmp_unequal(b)
+ && !mode_is_float(get_irn_mode(a_left))
+ && !mode_is_float(get_irn_mode(b_left))) {
+ if (values_in_mode(get_irn_mode(a_left), get_irn_mode(b_left))) {
+ ir_graph *irg = get_irn_irg(n);
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_node *block = get_nodes_block(n);
+ ir_mode *a_mode = get_irn_mode(a_left);
+ ir_mode *b_mode = get_irn_mode(b_left);
+ ir_node *xora = new_rd_Eor(dbgi, block, a_left, a_right, a_mode);
+ ir_node *xorb = new_rd_Eor(dbgi, block, b_left, b_right, b_mode);
+ ir_node *conv = new_rd_Conv(dbgi, block, xora, b_mode);
+ ir_node *orn = new_rd_Or(dbgi, block, conv, xorb, b_mode);
+ ir_node *zero = create_zero_const(irg, b_mode);
+ return new_rd_Cmp(dbgi, block, orn, zero, ir_relation_less_greater);
+ }
+ if (values_in_mode(get_irn_mode(b_left), get_irn_mode(a_left))) {
+ ir_graph *irg = get_irn_irg(n);
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_node *block = get_nodes_block(n);
+ ir_mode *a_mode = get_irn_mode(a_left);
+ ir_mode *b_mode = get_irn_mode(b_left);
+ ir_node *xora = new_rd_Eor(dbgi, block, a_left, a_right, a_mode);
+ ir_node *xorb = new_rd_Eor(dbgi, block, b_left, b_right, b_mode);
+ ir_node *conv = new_rd_Conv(dbgi, block, xorb, a_mode);
+ ir_node *orn = new_rd_Or(dbgi, block, xora, conv, a_mode);
+ ir_node *zero = create_zero_const(irg, a_mode);
+ return new_rd_Cmp(dbgi, block, orn, zero, ir_relation_less_greater);
+ }
+ }
+ }
+
+ mode = get_irn_mode(n);
+ HANDLE_BINOP_PHI((eval_func) tarval_or, a, b, c, mode);
+
+ n = transform_node_Or_bf_store(n);
+ if (n != oldn)
+ return n;
+ n = transform_node_Or_Rotl(n);
+ if (n != oldn)
+ return n;
+
+ n = transform_bitwise_distributive(n, transform_node_Or_);
+ if (n != oldn)
+ return n;
+ n = transform_node_bitop_shift(n);
+ if (n != oldn)
+ return n;
+
+ return n;
+}
+
+static ir_node *transform_node_Or(ir_node *n)
+{
+ if (is_Or_Eor_Add(n)) {
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_node *block = get_nodes_block(n);
+ ir_node *left = get_Or_left(n);
+ ir_node *right = get_Or_right(n);
+ ir_mode *mode = get_irn_mode(n);
+ return new_rd_Add(dbgi, block, left, right, mode);
+ }
+ return transform_node_Or_(n);
+}
+
+/**
+ * Transform an Eor.
+ */
+static ir_node *transform_node_Eor_(ir_node *n)
+{
+ ir_node *oldn = n;
+ ir_node *a = get_binop_left(n);
+ ir_node *b = get_binop_right(n);
+ ir_mode *mode = get_irn_mode(n);
+ ir_node *c;
+
+ n = fold_constant_associativity(n, tarval_eor);
+ if (n != oldn)
+ return n;
+
+ /* we can combine the relations of two compares with the same operands */
+ if (is_Cmp(a) && is_Cmp(b)) {
+ ir_node *a_left = get_Cmp_left(a);
+ ir_node *a_right = get_Cmp_left(a);
+ ir_node *b_left = get_Cmp_left(b);
+ ir_node *b_right = get_Cmp_right(b);
+ if (a_left == b_left && b_left == b_right) {
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_node *block = get_nodes_block(n);
+ ir_relation a_relation = get_Cmp_relation(a);
+ ir_relation b_relation = get_Cmp_relation(b);
+ ir_relation new_relation = a_relation ^ b_relation;
+ return new_rd_Cmp(dbgi, block, a_left, a_right, new_relation);
+ }
+ }
+
+ HANDLE_BINOP_PHI((eval_func) tarval_eor, a, b, c, mode);
+
+ /* normalize not nodes... ~a ^ b <=> a ^ ~b */
+ if (is_Not(a) && operands_are_normalized(get_Not_op(a), b)) {
+ dbg_info *dbg = get_irn_dbg_info(n);
+ ir_node *block = get_nodes_block(n);
+ ir_node *new_not = new_rd_Not(dbg, block, b, mode);
+ ir_node *new_left = get_Not_op(a);
+ n = new_rd_Eor(dbg, block, new_left, new_not, mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
+ return n;
+ } else if (is_Not(b) && !operands_are_normalized(a, get_Not_op(b))) {
+ dbg_info *dbg = get_irn_dbg_info(n);
+ ir_node *block = get_nodes_block(n);
+ ir_node *new_not = new_rd_Not(dbg, block, a, mode);
+ ir_node *new_right = get_Not_op(b);
+ n = new_rd_Eor(dbg, block, new_not, new_right, mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
+ return n;
+ }
+
+ /* x ^ 1...1 -> ~1 */
+ if (is_Const(b) && is_Const_all_one(b)) {
+ n = new_r_Not(get_nodes_block(n), a, mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
+ return n;
+ }
+
+ n = transform_bitwise_distributive(n, transform_node_Eor_);
+ if (n != oldn)
+ return n;
+ n = transform_node_bitop_shift(n);
+ if (n != oldn)
+ return n;
+
+ return n;
+}
+
+static ir_node *transform_node_Eor(ir_node *n)
+{
+ if (is_Or_Eor_Add(n)) {
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_node *block = get_nodes_block(n);
+ ir_node *left = get_Eor_left(n);
+ ir_node *right = get_Eor_right(n);
+ ir_mode *mode = get_irn_mode(n);
+ return new_rd_Add(dbgi, block, left, right, mode);
+ }
+ return transform_node_Eor_(n);
+}
+
+/**
+ * Do the AddSub optimization, then Transform
+ * Constant folding on Phi
+ * Add(a,a) -> Mul(a, 2)
+ * Add(Mul(a, x), a) -> Mul(a, x+1)
+ * if the mode is integer or float.
+ * Transform Add(a,-b) into Sub(a,b).
+ * Reassociation might fold this further.
+ */
+static ir_node *transform_node_Add(ir_node *n)
+{
+ ir_mode *mode;
+ ir_node *a;
+ ir_node *b;
+ ir_node *c;
+ ir_node *oldn = n;
+
+ n = fold_constant_associativity(n, tarval_add);
+ if (n != oldn)
+ return n;
+
+ n = transform_node_AddSub(n);
+ if (n != oldn)
+ return n;
+
+ a = get_Add_left(n);
+ b = get_Add_right(n);
+ mode = get_irn_mode(n);
+
+ if (mode_is_reference(mode)) {
+ ir_mode *lmode = get_irn_mode(a);
+
+ if (is_Const(b) && is_Const_null(b) && mode_is_int(lmode)) {
+ /* an Add(a, NULL) is a hidden Conv */
+ dbg_info *dbg = get_irn_dbg_info(n);
+ return new_rd_Conv(dbg, get_nodes_block(n), a, mode);
+ }
+ }
+
+ if (is_Const(b) && get_mode_arithmetic(mode) == irma_twos_complement) {
+ ir_tarval *tv = get_Const_tarval(b);
+ ir_tarval *min = get_mode_min(mode);
+ /* if all bits are set, then this has the same effect as a Not.
+ * Note that the following == gives false for different modes which
+ * is exactly what we want */
+ if (tv == min) {
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_graph *irg = get_irn_irg(n);
+ ir_node *block = get_nodes_block(n);
+ ir_node *cnst = new_r_Const(irg, min);
+ return new_rd_Eor(dbgi, block, a, cnst, mode);
+ }
+ }
+
+ HANDLE_BINOP_PHI((eval_func) tarval_add, a, b, c, mode);
+
+ /* for FP the following 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;
+ }
+
+ if (mode_is_num(mode)) {
+ ir_graph *irg = get_irn_irg(n);
+ /* the following code leads to endless recursion when Mul are replaced
+ * by a simple instruction chain */
+ if (!irg_is_constrained(irg, IR_GRAPH_CONSTRAINT_ARCH_DEP)
+ && a == b && mode_is_int(mode)) {
+ ir_node *block = get_nodes_block(n);
+
+ n = new_rd_Mul(
+ get_irn_dbg_info(n),
+ block,
+ a,
+ new_r_Const_long(irg, mode, 2),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_A);
+ return n;
+ }
+ if (is_Minus(a)) {
+ n = new_rd_Sub(
+ get_irn_dbg_info(n),
+ get_nodes_block(n),
+ b,
+ get_Minus_op(a),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
+ return n;
+ }
+ if (is_Minus(b)) {
+ n = new_rd_Sub(
+ get_irn_dbg_info(n),
+ get_nodes_block(n),
+ a,
+ get_Minus_op(b),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
+ return n;
+ }
+ if (get_mode_arithmetic(mode) == irma_twos_complement) {
+ /* Here we rely on constants be on the RIGHT side */
+ if (is_Not(a)) {
+ ir_node *op = get_Not_op(a);
+
+ if (is_Const(b) && is_Const_one(b)) {
+ /* ~x + 1 = -x */
+ ir_node *blk = get_nodes_block(n);
+ n = new_rd_Minus(get_irn_dbg_info(n), blk, op, mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_PLUS_1);
+ return n;
+ }
+ }
+ }
+ }
+
+ if (is_Or_Eor_Add(n)) {
+ n = transform_node_Or_(n);
+ if (n != oldn)
+ return n;
+ n = transform_node_Eor_(n);
+ if (n != oldn)
+ return n;
+ }
+
+ return n;
+}
+
+/**
+ * returns -cnst or NULL if impossible
+ */
+static ir_node *const_negate(ir_node *cnst)
+{
+ ir_tarval *tv = tarval_neg(get_Const_tarval(cnst));
+ dbg_info *dbgi = get_irn_dbg_info(cnst);
+ ir_graph *irg = get_irn_irg(cnst);
+ if (tv == tarval_bad) return NULL;
+ return new_rd_Const(dbgi, irg, tv);
+}
+