+ if (rr == left && (is_Add(right) || is_Or_Eor_Add(right))) {
+ ir_node *tmp = rl;
+ rl = rr;
+ rr = tmp;
+ }
+ if (rl == left) {
+ ir_graph *irg = get_irn_irg(n);
+ left = rr;
+ right = create_zero_const(irg, mode);
+ changed = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
+ }
+ }
+
+ if (is_And(left) && is_Const(right)) {
+ ir_node *ll = get_binop_left(left);
+ ir_node *lr = get_binop_right(left);
+ if (is_Shr(ll) && is_Const(lr)) {
+ /* Cmp((x >>u c1) & c2, c3) = Cmp(x & (c2 << c1), c3 << c1) */
+ ir_node *block = get_nodes_block(n);
+ ir_mode *mode = get_irn_mode(left);
+
+ ir_node *llr = get_Shr_right(ll);
+ if (is_Const(llr)) {
+ dbg_info *dbg = get_irn_dbg_info(left);
+ ir_graph *irg = get_irn_irg(left);
+
+ ir_tarval *c1 = get_Const_tarval(llr);
+ ir_tarval *c2 = get_Const_tarval(lr);
+ ir_tarval *c3 = get_Const_tarval(right);
+ ir_tarval *mask = tarval_shl(c2, c1);
+ ir_tarval *value = tarval_shl(c3, c1);
+
+ left = new_rd_And(dbg, block, get_Shr_left(ll), new_r_Const(irg, mask), mode);
+ right = new_r_Const(irg, value);
+ changed = true;
+ }
+ }
+ }
+ /* Cmp(Eor(x, y), 0) <=> Cmp(x, y) at least for the ==0,!=0
+ * cases */
+ if (is_Const(right) && is_Const_null(right) &&
+ (is_Eor(left) || is_Or_Eor_Add(left))) {
+ right = get_Eor_right(left);
+ left = get_Eor_left(left);
+ changed = true;
+ }
+ }
+ }
+
+ if (mode_is_int(mode) && is_And(left)) {
+ /* a complicated Cmp(And(1bit, val), 1bit) "bit-testing" can be replaced
+ * by the simpler Cmp(And(1bit, val), 0) negated pnc */
+ if (relation == ir_relation_equal
+ || (mode_is_signed(mode) && relation == ir_relation_less_greater)
+ || (!mode_is_signed(mode) && (relation & ir_relation_less_equal) == ir_relation_less)) {
+ ir_node *and0 = get_And_left(left);
+ ir_node *and1 = get_And_right(left);
+ if (and1 == right) {
+ ir_node *tmp = and0;
+ and0 = and1;
+ and1 = tmp;
+ }
+ if (and0 == right && is_single_bit(and0)) {
+ ir_graph *irg = get_irn_irg(n);
+ relation =
+ relation == ir_relation_equal ? ir_relation_less_greater
+ : ir_relation_equal;
+ right = create_zero_const(irg, mode);
+ changed |= 1;
+ goto is_bittest;
+ }
+ }
+
+ if (is_Const(right) && is_Const_null(right) &&
+ (relation == ir_relation_equal
+ || (relation == ir_relation_less_greater)
+ || (!mode_is_signed(mode) && relation == ir_relation_greater))) {
+is_bittest: {
+ /* instead of flipping the bit before the bit-test operation negate
+ * pnc */
+ ir_node *and0 = get_And_left(left);
+ ir_node *and1 = get_And_right(left);
+ if (is_Const(and1)) {
+ ir_tarval *tv = get_Const_tarval(and1);
+ if (tarval_is_single_bit(tv)) {
+ ir_node *flipped = flips_bit(and0, tv);
+ if (flipped != NULL) {
+ dbg_info *dbgi = get_irn_dbg_info(left);
+ ir_node *block = get_nodes_block(left);
+ relation = get_negated_relation(relation);
+ left = new_rd_And(dbgi, block, flipped, and1, mode);
+ changed |= 1;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /* replace mode_b compares with ands/ors */
+ if (mode == mode_b) {
+ ir_node *block = get_nodes_block(n);
+ ir_node *bres;
+
+ switch (relation) {
+ case ir_relation_less_equal:
+ bres = new_r_Or(block, new_r_Not(block, left, mode_b), right, mode_b);
+ break;
+ case ir_relation_less:
+ bres = new_r_And(block, new_r_Not(block, left, mode_b), right, mode_b);
+ break;
+ case ir_relation_greater_equal:
+ bres = new_r_Or(block, left, new_r_Not(block, right, mode_b), mode_b);
+ break;
+ case ir_relation_greater:
+ bres = new_r_And(block, left, new_r_Not(block, right, mode_b), mode_b);
+ break;
+ case ir_relation_less_greater:
+ bres = new_r_Eor(block, left, right, mode_b);
+ break;
+ case ir_relation_equal:
+ bres = new_r_Not(block, new_r_Eor(block, left, right, mode_b), mode_b);
+ break;
+ default:
+#ifdef DEBUG_libfirm
+ ir_fprintf(stderr, "Optimisation warning, unexpected mode_b Cmp %+F\n", n);
+#endif
+ bres = NULL;
+ }
+ if (bres != NULL) {
+ DBG_OPT_ALGSIM0(n, bres, FS_OPT_CMP_TO_BOOL);
+ return bres;
+ }
+ }
+
+ /*
+ * First step: normalize the compare op
+ * by placing the constant on the right side
+ * or moving the lower address node to the left.
+ */
+ if (!operands_are_normalized(left, right)) {
+ ir_node *t = left;
+ left = right;
+ right = t;
+
+ relation = get_inversed_relation(relation);
+ changed = true;
+ }
+
+ /*
+ * Second step: Try to reduce the magnitude
+ * of a constant. This may help to generate better code
+ * later and may help to normalize more compares.
+ * Of course this is only possible for integer values.
+ */
+ tv = value_of(right);
+ if (tv != tarval_bad) {
+ ir_mode *mode = get_irn_mode(right);
+
+ /* cmp(mux(x, cf, ct), c2) can be eliminated:
+ * cmp(ct,c2) | cmp(cf,c2) | result
+ * -----------|------------|--------
+ * true | true | True
+ * false | false | False
+ * true | false | x
+ * false | true | not(x)
+ */
+ if (is_Mux(left)) {
+ ir_node *mux_true = get_Mux_true(left);
+ ir_node *mux_false = get_Mux_false(left);
+ if (is_Const(mux_true) && is_Const(mux_false)) {
+ /* we can fold true/false constant separately */
+ ir_tarval *tv_true = get_Const_tarval(mux_true);
+ ir_tarval *tv_false = get_Const_tarval(mux_false);
+ ir_relation r_true = tarval_cmp(tv_true, tv);
+ ir_relation r_false = tarval_cmp(tv_false, tv);
+ if (r_true != ir_relation_false
+ || r_false != ir_relation_false) {
+ bool rel_true = (r_true & relation) != 0;
+ bool rel_false = (r_false & relation) != 0;
+ ir_node *cond = get_Mux_sel(left);
+ if (rel_true == rel_false) {
+ relation = rel_true ? ir_relation_true
+ : ir_relation_false;
+ } else if (rel_true) {
+ return cond;
+ } else {
+ dbg_info *dbgi = get_irn_dbg_info(n);
+ ir_node *block = get_nodes_block(n);
+ ir_node *notn = new_rd_Not(dbgi, block, cond, mode_b);
+ return notn;
+ }
+ }
+ }
+ }
+
+ /* TODO extend to arbitrary constants */
+ if (is_Conv(left) && tarval_is_null(tv)) {
+ ir_node *op = get_Conv_op(left);
+ ir_mode *op_mode = get_irn_mode(op);
+
+ /*
+ * UpConv(x) REL 0 ==> x REL 0
+ * Don't do this for float values as it's unclear whether it is a
+ * win. (on the other side it makes detection/creation of fabs hard)
+ */
+ if (get_mode_size_bits(mode) > get_mode_size_bits(op_mode) &&
+ ((relation == ir_relation_equal || relation == ir_relation_less_greater) ||
+ mode_is_signed(mode) || !mode_is_signed(op_mode)) &&
+ !mode_is_float(mode)) {
+ tv = get_mode_null(op_mode);
+ left = op;
+ mode = op_mode;
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CONV);
+ }
+ }
+
+ if (tv != tarval_bad) {
+ /* the following optimization is possible on modes without Overflow
+ * on Unary Minus or on == and !=:
+ * -a CMP c ==> a swap(CMP) -c
+ *
+ * Beware: for two-complement Overflow may occur, so only == and != can
+ * be optimized, see this:
+ * -MININT < 0 =/=> MININT > 0 !!!
+ */
+ if (is_Minus(left) &&
+ (!mode_overflow_on_unary_Minus(mode) ||
+ (mode_is_int(mode) && (relation == ir_relation_equal || relation == ir_relation_less_greater)))) {
+ tv = tarval_neg(tv);
+
+ if (tv != tarval_bad) {
+ left = get_Minus_op(left);
+ relation = get_inversed_relation(relation);
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
+ }
+ } else if (is_Not(left) && (relation == ir_relation_equal || relation == ir_relation_less_greater)) {
+ /* Not(a) ==/!= c ==> a ==/!= Not(c) */
+ tv = tarval_not(tv);
+
+ if (tv != tarval_bad) {
+ left = get_Not_op(left);
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
+ }
+ }
+
+ /* for integer modes, we have more */
+ if (mode_is_int(mode) && !is_Const(left)) {
+ /* c > 0 : a < c ==> a <= (c-1) a >= c ==> a > (c-1) */
+ if ((relation == ir_relation_less || relation == ir_relation_greater_equal) &&
+ tarval_cmp(tv, get_mode_null(mode)) == ir_relation_greater) {
+ tv = tarval_sub(tv, get_mode_one(mode), NULL);
+
+ if (tv != tarval_bad) {
+ relation ^= ir_relation_equal;
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CNST_MAGN);
+ }
+ }
+ /* c < 0 : a > c ==> a >= (c+1) a <= c ==> a < (c+1) */
+ else if ((relation == ir_relation_greater || relation == ir_relation_less_equal) &&
+ tarval_cmp(tv, get_mode_null(mode)) == ir_relation_less) {
+ tv = tarval_add(tv, get_mode_one(mode));
+
+ if (tv != tarval_bad) {
+ relation ^= ir_relation_equal;
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CNST_MAGN);
+ }
+ }
+
+ /* the following reassociations work only for == and != */
+ if (relation == ir_relation_equal || relation == ir_relation_less_greater) {
+ if (tv != tarval_bad) {
+ /* a-c1 == c2 ==> a == c2+c1, a-c1 != c2 ==> a != c2+c1 */
+ if (is_Sub(left)) {
+ ir_node *c1 = get_Sub_right(left);
+ ir_tarval *tv2 = value_of(c1);
+
+ if (tv2 != tarval_bad) {
+ tv2 = tarval_add(tv, value_of(c1));
+
+ if (tv2 != tarval_bad) {
+ left = get_Sub_left(left);
+ tv = tv2;
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
+ }
+ }
+ }
+ /* a+c1 == c2 ==> a == c2-c1, a+c1 != c2 ==> a != c2-c1 */
+ else if (is_Add(left) || is_Or_Eor_Add(left)) {
+ ir_node *a_l = get_binop_left(left);
+ ir_node *a_r = get_binop_right(left);
+ ir_node *a;
+ ir_tarval *tv2;
+
+ if (is_Const(a_l)) {
+ a = a_r;
+ tv2 = value_of(a_l);
+ } else {
+ a = a_l;
+ tv2 = value_of(a_r);
+ }
+
+ if (tv2 != tarval_bad) {
+ tv2 = tarval_sub(tv, tv2, NULL);
+
+ if (tv2 != tarval_bad) {
+ left = a;
+ tv = tv2;
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
+ }
+ }
+ }
+ /* -a == c ==> a == -c, -a != c ==> a != -c */
+ else if (is_Minus(left)) {
+ ir_tarval *tv2 = tarval_sub(get_mode_null(mode), tv, NULL);
+
+ if (tv2 != tarval_bad) {
+ left = get_Minus_op(left);
+ tv = tv2;
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
+ }
+ }
+ }
+ }
+ }
+
+ if (relation == ir_relation_equal || relation == ir_relation_less_greater) {
+ switch (get_irn_opcode(left)) {
+ ir_node *c1;
+
+ case iro_And:
+ c1 = get_And_right(left);
+ if (is_Const(c1)) {
+ /*
+ * And(x, C1) == C2 ==> FALSE if C2 & C1 != C2
+ * And(x, C1) != C2 ==> TRUE if C2 & C1 != C2
+ */
+ ir_tarval *mask = tarval_and(get_Const_tarval(c1), tv);
+ if (mask != tv) {
+ /* TODO: move to constant evaluation */
+ ir_graph *irg = get_irn_irg(n);
+ tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
+ c1 = new_r_Const(irg, tv);
+ DBG_OPT_CSTEVAL(n, c1);
+ return c1;
+ }
+
+ if (tarval_is_single_bit(tv)) {
+ /*
+ * optimization for AND:
+ * Optimize:
+ * And(x, C) == C ==> And(x, C) != 0
+ * And(x, C) != C ==> And(X, C) == 0
+ *
+ * if C is a single Bit constant.
+ */
+
+ /* check for Constant's match. We have check hare the tarvals,
+ because our const might be changed */
+ if (get_Const_tarval(c1) == tv) {
+ /* fine: do the transformation */
+ tv = get_mode_null(get_tarval_mode(tv));
+ relation ^= ir_relation_less_equal_greater;
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CNST_MAGN);
+ }
+ }
+ }
+ break;
+ case iro_Or:
+ c1 = get_Or_right(left);
+ if (is_Const(c1) && tarval_is_null(tv)) {
+ /*
+ * Or(x, C) == 0 && C != 0 ==> FALSE
+ * Or(x, C) != 0 && C != 0 ==> TRUE
+ */
+ if (! tarval_is_null(get_Const_tarval(c1))) {
+ /* TODO: move to constant evaluation */
+ ir_graph *irg = get_irn_irg(n);
+ tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
+ c1 = new_r_Const(irg, tv);
+ DBG_OPT_CSTEVAL(n, c1);
+ return c1;
+ }
+ }
+ break;
+ case iro_Shl:
+ /*
+ * optimize x << c1 == c into x & (-1 >>u c1) == c >> c1 if c & (-1 << c1) == c
+ * FALSE else
+ * optimize x << c1 != c into x & (-1 >>u c1) != c >> c1 if c & (-1 << c1) == c
+ * TRUE else
+ */
+ c1 = get_Shl_right(left);
+ if (is_Const(c1)) {
+ ir_graph *irg = get_irn_irg(c1);
+ ir_tarval *tv1 = get_Const_tarval(c1);
+ ir_mode *mode = get_irn_mode(left);
+ ir_tarval *minus1 = get_mode_all_one(mode);
+ ir_tarval *amask = tarval_shr(minus1, tv1);
+ ir_tarval *cmask = tarval_shl(minus1, tv1);
+ ir_node *sl, *blk;
+
+ if (tarval_and(tv, cmask) != tv) {
+ /* condition not met */
+ tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
+ c1 = new_r_Const(irg, tv);
+ DBG_OPT_CSTEVAL(n, c1);
+ return c1;
+ }
+ sl = get_Shl_left(left);
+ blk = get_nodes_block(n);
+ left = new_rd_And(get_irn_dbg_info(left), blk, sl, new_r_Const(irg, amask), mode);
+ tv = tarval_shr(tv, tv1);
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_SHF_TO_AND);
+ }
+ break;
+ case iro_Shr:
+ /*
+ * optimize x >>u c1 == c into x & (-1 << c1) == c << c1 if c & (-1 >>u c1) == c
+ * FALSE else
+ * optimize x >>u c1 != c into x & (-1 << c1) != c << c1 if c & (-1 >>u c1) == c
+ * TRUE else
+ */
+ c1 = get_Shr_right(left);
+ if (is_Const(c1)) {
+ ir_graph *irg = get_irn_irg(c1);
+ ir_tarval *tv1 = get_Const_tarval(c1);
+ ir_mode *mode = get_irn_mode(left);
+ ir_tarval *minus1 = get_mode_all_one(mode);
+ ir_tarval *amask = tarval_shl(minus1, tv1);
+ ir_tarval *cmask = tarval_shr(minus1, tv1);
+ ir_node *sl, *blk;
+
+ if (tarval_and(tv, cmask) != tv) {
+ /* condition not met */
+ tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
+ c1 = new_r_Const(irg, tv);
+ DBG_OPT_CSTEVAL(n, c1);
+ return c1;
+ }
+ sl = get_Shr_left(left);
+ blk = get_nodes_block(n);
+ left = new_rd_And(get_irn_dbg_info(left), blk, sl, new_r_Const(irg, amask), mode);
+ tv = tarval_shl(tv, tv1);
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_SHF_TO_AND);
+ }
+ break;
+ case iro_Shrs:
+ /*
+ * optimize x >>s c1 == c into x & (-1 << c1) == c << c1 if (c >>s (BITS - c1)) \in {0,-1}
+ * FALSE else
+ * optimize x >>s c1 != c into x & (-1 << c1) != c << c1 if (c >>s (BITS - c1)) \in {0,-1}
+ * TRUE else
+ */
+ c1 = get_Shrs_right(left);
+ if (is_Const(c1)) {
+ ir_graph *irg = get_irn_irg(c1);
+ ir_tarval *tv1 = get_Const_tarval(c1);
+ ir_mode *mode = get_irn_mode(left);
+ ir_tarval *minus1 = get_mode_all_one(mode);
+ ir_tarval *amask = tarval_shl(minus1, tv1);
+ ir_tarval *cond = new_tarval_from_long(get_mode_size_bits(mode), get_tarval_mode(tv1));
+ ir_node *sl, *blk;
+
+ cond = tarval_sub(cond, tv1, NULL);
+ cond = tarval_shrs(tv, cond);
+
+ if (!tarval_is_all_one(cond) && !tarval_is_null(cond)) {
+ /* condition not met */
+ tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
+ c1 = new_r_Const(irg, tv);
+ DBG_OPT_CSTEVAL(n, c1);
+ return c1;
+ }
+ sl = get_Shrs_left(left);
+ blk = get_nodes_block(n);
+ left = new_rd_And(get_irn_dbg_info(left), blk, sl, new_r_Const(irg, amask), mode);
+ tv = tarval_shl(tv, tv1);
+ changedc = true;
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_SHF_TO_AND);
+ }
+ break;
+ }
+ }