| Message ID | CAEwic4aX-p=_EzDU_j+XNrX+8v1JgDqFpYkusaq20-vNQPeaWw@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
Ping? 2012/4/5 Kai Tietz <ktietz70@googlemail.com>: > Hello, > > this patch adds some basic folding capabilities to fold-const for > equal and none-equal comparisons > on integer typed argument. > > ChangeLog > > 2012-04-05 Kai Tietz <ktietz@redhat.com> > > * fold-const.c (fold_comparison_1): New > function. > (fold_comparison): Use fold_comparison_1. > > 2012-04-05 Kai Tietz <ktietz@redhat.com> > > * gcc.dg/fold-compare-1.c: Adjust matching rule > for a == b without argument swap. > * gcc.dg/fold-compare-7.c: New test. > > Regession tested for x86_64-unknown-linux-gnu for all languages > (including Ada and Obj-C++). Ok for apply? > > Regards, > Kai > > Index: gcc/gcc/fold-const.c > =================================================================== > --- gcc.orig/gcc/fold-const.c > +++ gcc/gcc/fold-const.c > @@ -8739,6 +8739,241 @@ pointer_may_wrap_p (tree base, tree offs > return total_low > (unsigned HOST_WIDE_INT) size; > } > > +/* Sub-routine of fold_comparison. Folding of EQ_EXPR/NE_EXPR > + comparisons with integral typed arguments. */ > + > +static tree > +fold_comparison_1 (location_t loc, enum tree_code code, tree type, > + tree arg0, tree arg1) > +{ > + enum tree_code c1, c2; > + tree optype, op0, op1, opr0, opr1, tem; > + > + if (code != NE_EXPR && code != EQ_EXPR) > + return NULL_TREE; > + > + optype = TREE_TYPE (arg0); > + if (!INTEGRAL_TYPE_P (optype)) > + return NULL_TREE; > + > + c1 = TREE_CODE (arg0); > + c2 = TREE_CODE (arg1); > + > + /* Integer constant is on right-hand side. */ > + if (c1 == INTEGER_CST > + && c2 != c1) > + return fold_build2_loc (loc, code, type, arg1, arg0); > + > + if (!TREE_SIDE_EFFECTS (arg0) > + && operand_equal_p (arg0, arg1, 0)) > + { > + if (code == EQ_EXPR) > + return build_one_cst (type); > + return build_zero_cst (type); > + } > + > + > + if (c1 == NEGATE_EXPR) > + { > + op0 = TREE_OPERAND (arg0, 0); > + /* -X ==/!= -Y -> X ==/!= Y. */ > + if (c2 == c1) > + return fold_build2_loc (loc, code, type, > + op0, > + TREE_OPERAND (arg1, 0)); > + /* -X ==/!= CST -> X ==/!= CST' with CST'= -CST. */ > + else if (c2 == INTEGER_CST) > + return fold_build2_loc (loc, code, type, op0, > + fold_build1_loc (loc, NEGATE_EXPR, > + optype, arg1)); > + } > + else if (c1 == BIT_NOT_EXPR) > + { > + op0 = TREE_OPERAND (arg0, 0); > + /* ~X ==/!= ~Y -> X ==/!= Y. */ > + if (c2 == c1) > + return fold_build2_loc (loc, code, type, op0, > + TREE_OPERAND (arg1, 0)); > + /* ~X ==/!= CST -> X ==/!= CST' with CST'= ~CST. */ > + else if (c2 == INTEGER_CST) > + return fold_build2_loc (loc, code, type, op0, > + fold_build1_loc (loc, BIT_NOT_EXPR, > + optype, arg1)); > + } > + > + /* See if we can simplify case X == (Y +|-|^ Z). */ > + if (c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) > + { > + if ((c2 != PLUS_EXPR && c2 != MINUS_EXPR > + && c2 != BIT_XOR_EXPR) > + || TREE_SIDE_EFFECTS (arg0)) > + return NULL_TREE; > + > + op0 = TREE_OPERAND (arg1, 0); > + op1 = TREE_OPERAND (arg1, 1); > + > + /* Convert temporary X - Y to X + (-Y). */ > + if (c2 == MINUS_EXPR) > + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); > + > + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, > + or X ==/!= (X +|- Y) to Y ==/!= 0. */ > + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), > + optype, arg0, op0); > + if (TREE_CODE (tem) == INTEGER_CST > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c2 == BIT_XOR_EXPR)) > + return fold_build2_loc (loc, code, type, op1, tem); > + > + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, > + or X ==/!= (Y + X) to Y ==/!= 0. */ > + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), > + optype, arg0, op1); > + if (TREE_CODE (tem) == INTEGER_CST > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c2 == BIT_XOR_EXPR)) > + return fold_build2_loc (loc, code, type, op0, tem); > + } > + else if (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR) > + { > + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR > + && c1 != BIT_XOR_EXPR) > + || TREE_SIDE_EFFECTS (arg1)) > + return NULL_TREE; > + > + op0 = TREE_OPERAND (arg0, 0); > + op1 = TREE_OPERAND (arg0, 1); > + > + /* Convert temporary X - Y to X + (-Y). */ > + if (c1 == MINUS_EXPR) > + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); > + > + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, > + or X ==/!= (X +|- Y) to Y ==/!= 0. */ > + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), > + optype, arg1, op0); > + if (TREE_CODE (tem) == INTEGER_CST > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + return fold_build2_loc (loc, code, type, op1, tem); > + > + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, > + or X ==/!= (Y + X) to Y ==/!= 0. */ > + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), > + optype, arg1, op1); > + if (TREE_CODE (tem) == INTEGER_CST > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + return fold_build2_loc (loc, code, type, op0, tem); > + } > + > + /* We check if arg1 and arg2 are matching one of the patterns > + (V + W) ==/!= (X + Y), (V + W) ==/!= (X - Y), (V - W) ==/!= (X + Y), > + (V - W) ==/!= (X - Y), or (V ^ W) ==/!= (X ^ Y). */ > + > + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) > + || (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR)) > + return NULL_TREE; > + if (c1 != c2 && (c1 == BIT_XOR_EXPR || c2 == BIT_XOR_EXPR)) > + return NULL_TREE; > + > + op0 = TREE_OPERAND (arg0, 0); > + op1 = TREE_OPERAND (arg0, 1); > + opr0 = TREE_OPERAND (arg1, 0); > + opr1 = TREE_OPERAND (arg1, 1); > + > + /* Convert temporary (X - Y) to (X + (-Y)). */ > + if (c1 == MINUS_EXPR) > + { > + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); > + c1 = PLUS_EXPR; > + } > + > + /* Convert temporary (X - Y) to (X + (-Y)). */ > + if (c2 == MINUS_EXPR) > + { > + opr1 = fold_build1_loc (loc, NEGATE_EXPR, optype, opr1); > + c2 = PLUS_EXPR; > + } > + > + if (c1 != c2) > + return NULL_TREE; > + > + /* If OP0 has no side-effects, we might be able to optimize > + (OP0 + OP1) ==/!= (OP0 + OPR1) to OP1 ==/!= OPR1, > + (OP0 + OP1) ==/!= (OPR0 + OP0) to OP1 ==/!= OPR0, > + (OP0 ^ OP1) ==/!= (OP0 ^ OPR1) to OP1 ==/!= OPR1, > + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP0) to OP1 ==/!= OPR0.. */ > + if (!TREE_SIDE_EFFECTS (op0)) > + { > + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), > + optype, op0, opr0); > + if (TREE_CODE (tem) == INTEGER_CST > + && !TREE_SIDE_EFFECTS (opr0) > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + { > + if (!integer_zerop (tem)) > + tem = fold_build2_loc (loc, c1, optype, op1, tem); > + else > + tem = op1; > + > + return fold_build2_loc (loc, code, type, tem, opr1); > + } > + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), > + optype, op0, opr1); > + if (TREE_CODE (tem) == INTEGER_CST > + && !TREE_SIDE_EFFECTS (opr1) > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + { > + if (!integer_zerop (tem)) > + tem = fold_build2_loc (loc, c1, optype, op1, tem); > + else > + tem = op1; > + return fold_build2_loc (loc, code, type, tem, opr0); > + } > + } > + > + /* If OP1 has no side-effects, we might be able to optimize > + (OP0 + OP1) ==/!= (OP1 + OPR1) to OP0 ==/!= OPR1, > + (OP0 + OP1) ==/!= (OPR0 + OP1) to OP0 ==/!= OPR0, > + (OP0 ^ OP1) ==/!= (OP1 ^ OPR1) to OP0 ==/!= OPR1, > + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP1) to OP0 ==/!= OPR0.. */ > + if (!TREE_SIDE_EFFECTS (op1)) > + { > + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), > + optype, op1, opr0); > + if (TREE_CODE (tem) == INTEGER_CST > + && !TREE_SIDE_EFFECTS (opr0) > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + { > + if (!integer_zerop (tem)) > + tem = fold_build2_loc (loc, c1, optype, op0, tem); > + else > + tem = op0; > + return fold_build2_loc (loc, code, type, tem, opr1); > + } > + > + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), > + optype, op1, opr1); > + if (TREE_CODE (tem) == INTEGER_CST > + && !TREE_SIDE_EFFECTS (opr1) > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + { > + if (!integer_zerop (tem)) > + tem = fold_build2_loc (loc, c1, optype, op0, tem); > + else > + tem = op0; > + return fold_build2_loc (loc, code, type, tem, opr0); > + } > + } > + > + return NULL_TREE; > +} > + > /* Subroutine of fold_binary. This routine performs all of the > transformations that are common to the equality/inequality > operators (EQ_EXPR and NE_EXPR) and the ordering operators > @@ -8767,6 +9002,10 @@ fold_comparison (location_t loc, enum tr > if (tree_swap_operands_p (arg0, arg1, true)) > return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0); > > + tem = fold_comparison_1 (loc, code, type, arg0, arg1); > + if (tem != NULL_TREE) > + return tem; > + > /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 +- C1. */ > if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR) > && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST > Index: gcc/gcc/testsuite/gcc.dg/fold-compare-1.c > =================================================================== > --- gcc.orig/gcc/testsuite/gcc.dg/fold-compare-1.c > +++ gcc/gcc/testsuite/gcc.dg/fold-compare-1.c > @@ -41,7 +41,7 @@ int test8(int l) > return ~l >= 2; > } > > -/* { dg-final { scan-tree-dump-times "b == a" 1 "original" } } */ > +/* { dg-final { scan-tree-dump-times "b == a|a == b" 1 "original" } } */ > /* { dg-final { scan-tree-dump-times "c == d" 1 "original" } } */ > /* { dg-final { scan-tree-dump-times "e == -5" 1 "original" } } */ > /* { dg-final { scan-tree-dump-times "f == -6" 1 "original" } } */ > Index: gcc/gcc/testsuite/gcc.dg/fold-compare-7.c > =================================================================== > --- /dev/null > +++ gcc/gcc/testsuite/gcc.dg/fold-compare-7.c > @@ -0,0 +1,36 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-original" } */ > + > +int test1(int a, int elim) > +{ > + return ~elim == (elim ^ a); > +} > + > +int test2(int elim, int b) > +{ > + return -elim == (b - elim); > +} > + > +int test3(int c, int elim, int d) > +{ > + return (c + elim) != (elim + d); > +} > + > +int test4(int e, int f, int elim) > +{ > + return (e - elim) != (-elim + f); > +} > + > +int test5(int g, int h, int elim) > +{ > + return (elim ^ g) == (h ^ elim); > +} > + > +int test6(int i, int j, int elim) > +{ > + return (elim ^ i) == (j ^ ~elim); > +} > + > +/* { dg-final { scan-tree-dump-times "elim" 0 "original" } } */ > +/* { dg-final { cleanup-tree-dump "original" } } */ > +
On Thu, Apr 5, 2012 at 6:15 PM, Kai Tietz <ktietz70@googlemail.com> wrote: > Hello, > > this patch adds some basic folding capabilities to fold-const for > equal and none-equal comparisons > on integer typed argument. > > ChangeLog > > 2012-04-05 Kai Tietz <ktietz@redhat.com> > > * fold-const.c (fold_comparison_1): New > function. > (fold_comparison): Use fold_comparison_1. > > 2012-04-05 Kai Tietz <ktietz@redhat.com> > > * gcc.dg/fold-compare-1.c: Adjust matching rule > for a == b without argument swap. > * gcc.dg/fold-compare-7.c: New test. > > Regession tested for x86_64-unknown-linux-gnu for all languages > (including Ada and Obj-C++). Ok for apply? > > Regards, > Kai > > Index: gcc/gcc/fold-const.c > =================================================================== > --- gcc.orig/gcc/fold-const.c > +++ gcc/gcc/fold-const.c > @@ -8739,6 +8739,241 @@ pointer_may_wrap_p (tree base, tree offs > return total_low > (unsigned HOST_WIDE_INT) size; > } > > +/* Sub-routine of fold_comparison. Folding of EQ_EXPR/NE_EXPR > + comparisons with integral typed arguments. */ > + > +static tree > +fold_comparison_1 (location_t loc, enum tree_code code, tree type, > + tree arg0, tree arg1) Please name it more specific, like for example fold_integral_equality_comparison. > +{ > + enum tree_code c1, c2; > + tree optype, op0, op1, opr0, opr1, tem; > + > + if (code != NE_EXPR && code != EQ_EXPR) > + return NULL_TREE; > + > + optype = TREE_TYPE (arg0); > + if (!INTEGRAL_TYPE_P (optype)) > + return NULL_TREE; > + > + c1 = TREE_CODE (arg0); > + c2 = TREE_CODE (arg1); > + > + /* Integer constant is on right-hand side. */ > + if (c1 == INTEGER_CST > + && c2 != c1) > + return fold_build2_loc (loc, code, type, arg1, arg0); /* If one arg is a real or integer constant, put it last. */ if (tree_swap_operands_p (arg0, arg1, true)) return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0); in fold_comparison already ensures this. > + if (!TREE_SIDE_EFFECTS (arg0) > + && operand_equal_p (arg0, arg1, 0)) > + { > + if (code == EQ_EXPR) > + return build_one_cst (type); > + return build_zero_cst (type); > + } This is already done in a more general way in fold_comparison: /* Simplify comparison of something with itself. (For IEEE floating-point, we can only do some of these simplifications.) */ if (operand_equal_p (arg0, arg1, 0)) { switch (code) { case EQ_EXPR: ... which also shows how to fold to true/false - using constant_boolean_node. > + > + if (c1 == NEGATE_EXPR) > + { > + op0 = TREE_OPERAND (arg0, 0); > + /* -X ==/!= -Y -> X ==/!= Y. */ > + if (c2 == c1) > + return fold_build2_loc (loc, code, type, > + op0, > + TREE_OPERAND (arg1, 0)); This is already done, in a more general way but only for float types, in fold_comparison. It's beyond me why it is conditional on float types there and does not check for trapping math and NaNs (maybe that's well-defined - one would need to double-check). For integral types you'd have to care for undefined overflow (or issue a warning), and ... > + /* -X ==/!= CST -> X ==/!= CST' with CST'= -CST. */ > + else if (c2 == INTEGER_CST) > + return fold_build2_loc (loc, code, type, op0, > + fold_build1_loc (loc, NEGATE_EXPR, > + optype, arg1)); ... generalizing this the code should use negate_expr_p / negate_expr to for example handle folding -b != b - a to b != a - b (of course you'd require at least one explicit NEGATE_EXPR - similar foldings elsewhere will tell you what to do). > + } > + else if (c1 == BIT_NOT_EXPR) > + { > + op0 = TREE_OPERAND (arg0, 0); > + /* ~X ==/!= ~Y -> X ==/!= Y. */ > + if (c2 == c1) > + return fold_build2_loc (loc, code, type, op0, > + TREE_OPERAND (arg1, 0)); This can be generalized to relational comparisons as well I think. It's also already done in fold_comparison here: /* Fold ~X op ~Y as Y op X. */ if (TREE_CODE (arg0) == BIT_NOT_EXPR && TREE_CODE (arg1) == BIT_NOT_EXPR) { > + /* ~X ==/!= CST -> X ==/!= CST' with CST'= ~CST. */ > + else if (c2 == INTEGER_CST) > + return fold_build2_loc (loc, code, type, op0, > + fold_build1_loc (loc, BIT_NOT_EXPR, > + optype, arg1)); Possibly unified with having a new predicate/worker invert_expr_p / invert_expr. > + } > + > + /* See if we can simplify case X == (Y +|-|^ Z). */ > + if (c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) > + { > + if ((c2 != PLUS_EXPR && c2 != MINUS_EXPR > + && c2 != BIT_XOR_EXPR) > + || TREE_SIDE_EFFECTS (arg0)) > + return NULL_TREE; (I'm not sure why you are testing for side-effects - if you omit sth use omit_*_operand ()) > + > + op0 = TREE_OPERAND (arg1, 0); > + op1 = TREE_OPERAND (arg1, 1); Please use names like arg10 and arg11 as elsewhere in folding. > + /* Convert temporary X - Y to X + (-Y). */ > + if (c2 == MINUS_EXPR) > + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); That's not a good idea - in general we avoid building scratch trees during folding. > + > + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, > + or X ==/!= (X +|- Y) to Y ==/!= 0. */ > + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), > + optype, arg0, op0); Similar - also this code and the code below duplicates things four times. That's both expensive and hard to read. It asks for some factorization and use of explicit pattern matching instead of recursing into folding. > + if (TREE_CODE (tem) == INTEGER_CST > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c2 == BIT_XOR_EXPR)) > + return fold_build2_loc (loc, code, type, op1, tem); > + > + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, > + or X ==/!= (Y + X) to Y ==/!= 0. */ > + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), > + optype, arg0, op1); > + if (TREE_CODE (tem) == INTEGER_CST > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c2 == BIT_XOR_EXPR)) > + return fold_build2_loc (loc, code, type, op0, tem); > + } > + else if (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR) > + { > + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR > + && c1 != BIT_XOR_EXPR) > + || TREE_SIDE_EFFECTS (arg1)) > + return NULL_TREE; > + > + op0 = TREE_OPERAND (arg0, 0); > + op1 = TREE_OPERAND (arg0, 1); > + > + /* Convert temporary X - Y to X + (-Y). */ > + if (c1 == MINUS_EXPR) > + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); > + > + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, > + or X ==/!= (X +|- Y) to Y ==/!= 0. */ > + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), > + optype, arg1, op0); > + if (TREE_CODE (tem) == INTEGER_CST > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + return fold_build2_loc (loc, code, type, op1, tem); > + > + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, > + or X ==/!= (Y + X) to Y ==/!= 0. */ > + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), > + optype, arg1, op1); > + if (TREE_CODE (tem) == INTEGER_CST > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + return fold_build2_loc (loc, code, type, op0, tem); > + } > + > + /* We check if arg1 and arg2 are matching one of the patterns > + (V + W) ==/!= (X + Y), (V + W) ==/!= (X - Y), (V - W) ==/!= (X + Y), > + (V - W) ==/!= (X - Y), or (V ^ W) ==/!= (X ^ Y). */ I stopped reading here. Please try to double check what we already do, don't produce new code for everything you can think of. This patch could have needed splitting, too. Richard. > + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) > + || (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR)) > + return NULL_TREE; > + if (c1 != c2 && (c1 == BIT_XOR_EXPR || c2 == BIT_XOR_EXPR)) > + return NULL_TREE; > + > + op0 = TREE_OPERAND (arg0, 0); > + op1 = TREE_OPERAND (arg0, 1); > + opr0 = TREE_OPERAND (arg1, 0); > + opr1 = TREE_OPERAND (arg1, 1); > + > + /* Convert temporary (X - Y) to (X + (-Y)). */ > + if (c1 == MINUS_EXPR) > + { > + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); > + c1 = PLUS_EXPR; > + } > + > + /* Convert temporary (X - Y) to (X + (-Y)). */ > + if (c2 == MINUS_EXPR) > + { > + opr1 = fold_build1_loc (loc, NEGATE_EXPR, optype, opr1); > + c2 = PLUS_EXPR; > + } > + > + if (c1 != c2) > + return NULL_TREE; > + > + /* If OP0 has no side-effects, we might be able to optimize > + (OP0 + OP1) ==/!= (OP0 + OPR1) to OP1 ==/!= OPR1, > + (OP0 + OP1) ==/!= (OPR0 + OP0) to OP1 ==/!= OPR0, > + (OP0 ^ OP1) ==/!= (OP0 ^ OPR1) to OP1 ==/!= OPR1, > + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP0) to OP1 ==/!= OPR0.. */ > + if (!TREE_SIDE_EFFECTS (op0)) > + { > + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), > + optype, op0, opr0); > + if (TREE_CODE (tem) == INTEGER_CST > + && !TREE_SIDE_EFFECTS (opr0) > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + { > + if (!integer_zerop (tem)) > + tem = fold_build2_loc (loc, c1, optype, op1, tem); > + else > + tem = op1; > + > + return fold_build2_loc (loc, code, type, tem, opr1); > + } > + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), > + optype, op0, opr1); > + if (TREE_CODE (tem) == INTEGER_CST > + && !TREE_SIDE_EFFECTS (opr1) > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + { > + if (!integer_zerop (tem)) > + tem = fold_build2_loc (loc, c1, optype, op1, tem); > + else > + tem = op1; > + return fold_build2_loc (loc, code, type, tem, opr0); > + } > + } > + > + /* If OP1 has no side-effects, we might be able to optimize > + (OP0 + OP1) ==/!= (OP1 + OPR1) to OP0 ==/!= OPR1, > + (OP0 + OP1) ==/!= (OPR0 + OP1) to OP0 ==/!= OPR0, > + (OP0 ^ OP1) ==/!= (OP1 ^ OPR1) to OP0 ==/!= OPR1, > + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP1) to OP0 ==/!= OPR0.. */ > + if (!TREE_SIDE_EFFECTS (op1)) > + { > + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), > + optype, op1, opr0); > + if (TREE_CODE (tem) == INTEGER_CST > + && !TREE_SIDE_EFFECTS (opr0) > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + { > + if (!integer_zerop (tem)) > + tem = fold_build2_loc (loc, c1, optype, op0, tem); > + else > + tem = op0; > + return fold_build2_loc (loc, code, type, tem, opr1); > + } > + > + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), > + optype, op1, opr1); > + if (TREE_CODE (tem) == INTEGER_CST > + && !TREE_SIDE_EFFECTS (opr1) > + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) > + || c1 == BIT_XOR_EXPR)) > + { > + if (!integer_zerop (tem)) > + tem = fold_build2_loc (loc, c1, optype, op0, tem); > + else > + tem = op0; > + return fold_build2_loc (loc, code, type, tem, opr0); > + } > + } > + > + return NULL_TREE; > +} > + > /* Subroutine of fold_binary. This routine performs all of the > transformations that are common to the equality/inequality > operators (EQ_EXPR and NE_EXPR) and the ordering operators > @@ -8767,6 +9002,10 @@ fold_comparison (location_t loc, enum tr > if (tree_swap_operands_p (arg0, arg1, true)) > return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0); > > + tem = fold_comparison_1 (loc, code, type, arg0, arg1); > + if (tem != NULL_TREE) > + return tem; > + > /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 +- C1. */ > if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR) > && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST > Index: gcc/gcc/testsuite/gcc.dg/fold-compare-1.c > =================================================================== > --- gcc.orig/gcc/testsuite/gcc.dg/fold-compare-1.c > +++ gcc/gcc/testsuite/gcc.dg/fold-compare-1.c > @@ -41,7 +41,7 @@ int test8(int l) > return ~l >= 2; > } > > -/* { dg-final { scan-tree-dump-times "b == a" 1 "original" } } */ > +/* { dg-final { scan-tree-dump-times "b == a|a == b" 1 "original" } } */ > /* { dg-final { scan-tree-dump-times "c == d" 1 "original" } } */ > /* { dg-final { scan-tree-dump-times "e == -5" 1 "original" } } */ > /* { dg-final { scan-tree-dump-times "f == -6" 1 "original" } } */ > Index: gcc/gcc/testsuite/gcc.dg/fold-compare-7.c > =================================================================== > --- /dev/null > +++ gcc/gcc/testsuite/gcc.dg/fold-compare-7.c > @@ -0,0 +1,36 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-original" } */ > + > +int test1(int a, int elim) > +{ > + return ~elim == (elim ^ a); > +} > + > +int test2(int elim, int b) > +{ > + return -elim == (b - elim); > +} > + > +int test3(int c, int elim, int d) > +{ > + return (c + elim) != (elim + d); > +} > + > +int test4(int e, int f, int elim) > +{ > + return (e - elim) != (-elim + f); > +} > + > +int test5(int g, int h, int elim) > +{ > + return (elim ^ g) == (h ^ elim); > +} > + > +int test6(int i, int j, int elim) > +{ > + return (elim ^ i) == (j ^ ~elim); > +} > + > +/* { dg-final { scan-tree-dump-times "elim" 0 "original" } } */ > +/* { dg-final { cleanup-tree-dump "original" } } */ > +
2012/4/12 Richard Guenther <richard.guenther@gmail.com>: > On Thu, Apr 5, 2012 at 6:15 PM, Kai Tietz <ktietz70@googlemail.com> wrote: >> Hello, >> >> this patch adds some basic folding capabilities to fold-const for >> equal and none-equal comparisons >> on integer typed argument. >> >> ChangeLog >> >> 2012-04-05 Kai Tietz <ktietz@redhat.com> >> >> * fold-const.c (fold_comparison_1): New >> function. >> (fold_comparison): Use fold_comparison_1. >> >> 2012-04-05 Kai Tietz <ktietz@redhat.com> >> >> * gcc.dg/fold-compare-1.c: Adjust matching rule >> for a == b without argument swap. >> * gcc.dg/fold-compare-7.c: New test. >> >> Regession tested for x86_64-unknown-linux-gnu for all languages >> (including Ada and Obj-C++). Ok for apply? >> >> Regards, >> Kai >> >> Index: gcc/gcc/fold-const.c >> =================================================================== >> --- gcc.orig/gcc/fold-const.c >> +++ gcc/gcc/fold-const.c >> @@ -8739,6 +8739,241 @@ pointer_may_wrap_p (tree base, tree offs >> return total_low > (unsigned HOST_WIDE_INT) size; >> } >> >> +/* Sub-routine of fold_comparison. Folding of EQ_EXPR/NE_EXPR >> + comparisons with integral typed arguments. */ >> + >> +static tree >> +fold_comparison_1 (location_t loc, enum tree_code code, tree type, >> + tree arg0, tree arg1) > > Please name it more specific, like for example > fold_integral_equality_comparison. > >> +{ >> + enum tree_code c1, c2; >> + tree optype, op0, op1, opr0, opr1, tem; >> + >> + if (code != NE_EXPR && code != EQ_EXPR) >> + return NULL_TREE; >> + >> + optype = TREE_TYPE (arg0); >> + if (!INTEGRAL_TYPE_P (optype)) >> + return NULL_TREE; >> + >> + c1 = TREE_CODE (arg0); >> + c2 = TREE_CODE (arg1); >> + >> + /* Integer constant is on right-hand side. */ >> + if (c1 == INTEGER_CST >> + && c2 != c1) >> + return fold_build2_loc (loc, code, type, arg1, arg0); > > /* If one arg is a real or integer constant, put it last. */ > if (tree_swap_operands_p (arg0, arg1, true)) > return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0); > > in fold_comparison already ensures this. > >> + if (!TREE_SIDE_EFFECTS (arg0) >> + && operand_equal_p (arg0, arg1, 0)) >> + { >> + if (code == EQ_EXPR) >> + return build_one_cst (type); >> + return build_zero_cst (type); >> + } > > This is already done in a more general way in fold_comparison: Yes, was a duplicate like ... > /* Simplify comparison of something with itself. (For IEEE > floating-point, we can only do some of these simplifications.) */ > if (operand_equal_p (arg0, arg1, 0)) > { > switch (code) > { > case EQ_EXPR: > ... > > which also shows how to fold to true/false - using constant_boolean_node. like this one. So I removed from patch. >> + >> + if (c1 == NEGATE_EXPR) >> + { >> + op0 = TREE_OPERAND (arg0, 0); >> + /* -X ==/!= -Y -> X ==/!= Y. */ >> + if (c2 == c1) >> + return fold_build2_loc (loc, code, type, >> + op0, >> + TREE_OPERAND (arg1, 0)); > > This is already done, in a more general way but only for float types, > in fold_comparison. It's beyond me why it is conditional on float types > there and does not check for trapping math and NaNs (maybe that's > well-defined - one would need to double-check). For integral types > you'd have to care for undefined overflow (or issue a warning), and ... You miss here explicit a point about ==/!= comparisons. The negate can be removed for such comparisons uncoditionally, as there can't happen an overflow, which changes result of compare. It would be even a flaw for checking here for those cases about overflow. >> + /* -X ==/!= CST -> X ==/!= CST' with CST'= -CST. */ >> + else if (c2 == INTEGER_CST) >> + return fold_build2_loc (loc, code, type, op0, >> + fold_build1_loc (loc, NEGATE_EXPR, >> + optype, arg1)); > > ... generalizing this the code should use negate_expr_p / negate_expr > to for example handle folding -b != b - a to b != a - b (of course you'd > require at least one explicit NEGATE_EXPR - similar foldings elsewhere > will tell you what to do). See, above. No, it would be a failure to use negate_expr_p here, as the overflow simply doesn't matter and there is also no need to warn about it. >> + } >> + else if (c1 == BIT_NOT_EXPR) >> + { >> + op0 = TREE_OPERAND (arg0, 0); >> + /* ~X ==/!= ~Y -> X ==/!= Y. */ >> + if (c2 == c1) >> + return fold_build2_loc (loc, code, type, op0, >> + TREE_OPERAND (arg1, 0)); > > This can be generalized to relational comparisons as well I think. It's also > already done in fold_comparison here: No it isn't. As again for ==/!= comparison the overflow simply doesn't matter. Therefore I added this function to special-case (non-)equal-comparison. The overflow cases are already handled for general comparison, no need to do it twice. > /* Fold ~X op ~Y as Y op X. */ > if (TREE_CODE (arg0) == BIT_NOT_EXPR > && TREE_CODE (arg1) == BIT_NOT_EXPR) > { > > >> + /* ~X ==/!= CST -> X ==/!= CST' with CST'= ~CST. */ >> + else if (c2 == INTEGER_CST) >> + return fold_build2_loc (loc, code, type, op0, >> + fold_build1_loc (loc, BIT_NOT_EXPR, >> + optype, arg1)); > > Possibly unified with having a new predicate/worker invert_expr_p / invert_expr. Well, there is no need for an invert_expr_p (see above). Also in this case we don't need and have to warn. >> + } >> + >> + /* See if we can simplify case X == (Y +|-|^ Z). */ >> + if (c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) >> + { >> + if ((c2 != PLUS_EXPR && c2 != MINUS_EXPR >> + && c2 != BIT_XOR_EXPR) >> + || TREE_SIDE_EFFECTS (arg0)) >> + return NULL_TREE; > > (I'm not sure why you are testing for side-effects - if you omit sth use > omit_*_operand ()) Actual the use of omit_*_operand () introduces for none-volative cases NON_LVALUE_EXPR expressions, which are within comparisons vain. Also it wasn't quite clear if the following reduction of volatiles within a comparison is valid. At least for substractions we don't do this optimization, so I would assume that it would be wrong for comparisons, too. >> + >> + op0 = TREE_OPERAND (arg1, 0); >> + op1 = TREE_OPERAND (arg1, 1); > > Please use names like arg10 and arg11 as elsewhere in folding. > >> + /* Convert temporary X - Y to X + (-Y). */ >> + if (c2 == MINUS_EXPR) >> + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); > > That's not a good idea - in general we avoid building scratch trees > during folding. Well, this patterns can be of course written out explicit. But by doing this transformation simplifies later on used patterns a bit. Also it can be later on used for futher optimizations about value preditions for patterns like 'a == 1 - a' being always false for all integer values, etc. >> + >> + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, >> + or X ==/!= (X +|- Y) to Y ==/!= 0. */ >> + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), >> + optype, arg0, op0); > > Similar - also this code and the code below duplicates things four times. > That's both expensive and hard to read. It asks for some factorization > and use of explicit pattern matching instead of recursing into folding. Not quite sure what you mean here by recursion. We have actual here three cases (with op being PLUS/MINUX or XOR expression): 1) A !=/== B (which is already convered in general comparison-code) 2) A !=/== (B op C) or (A op B) !=/== C (this I duplicated in code, but could be of course factored out into a helper-routine) and 3 (A op B) !=/== (C op D) >> + if (TREE_CODE (tem) == INTEGER_CST >> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >> + || c2 == BIT_XOR_EXPR)) >> + return fold_build2_loc (loc, code, type, op1, tem); >> + >> + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, >> + or X ==/!= (Y + X) to Y ==/!= 0. */ >> + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), >> + optype, arg0, op1); >> + if (TREE_CODE (tem) == INTEGER_CST >> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >> + || c2 == BIT_XOR_EXPR)) >> + return fold_build2_loc (loc, code, type, op0, tem); >> + } >> + else if (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR) >> + { >> + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR >> + && c1 != BIT_XOR_EXPR) >> + || TREE_SIDE_EFFECTS (arg1)) >> + return NULL_TREE; >> + >> + op0 = TREE_OPERAND (arg0, 0); >> + op1 = TREE_OPERAND (arg0, 1); >> + >> + /* Convert temporary X - Y to X + (-Y). */ >> + if (c1 == MINUS_EXPR) >> + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); >> + >> + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, >> + or X ==/!= (X +|- Y) to Y ==/!= 0. */ >> + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), >> + optype, arg1, op0); >> + if (TREE_CODE (tem) == INTEGER_CST >> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >> + || c1 == BIT_XOR_EXPR)) >> + return fold_build2_loc (loc, code, type, op1, tem); >> + >> + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, >> + or X ==/!= (Y + X) to Y ==/!= 0. */ >> + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), >> + optype, arg1, op1); >> + if (TREE_CODE (tem) == INTEGER_CST >> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >> + || c1 == BIT_XOR_EXPR)) >> + return fold_build2_loc (loc, code, type, op0, tem); >> + } >> + >> + /* We check if arg1 and arg2 are matching one of the patterns >> + (V + W) ==/!= (X + Y), (V + W) ==/!= (X - Y), (V - W) ==/!= (X + Y), >> + (V - W) ==/!= (X - Y), or (V ^ W) ==/!= (X ^ Y). */ > > I stopped reading here. Please try to double check what we already do, > don't produce new code for everything you can think of. This patch could > have needed splitting, too. > > Richard. > >> + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) >> + || (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR)) >> + return NULL_TREE; >> + if (c1 != c2 && (c1 == BIT_XOR_EXPR || c2 == BIT_XOR_EXPR)) >> + return NULL_TREE; >> + >> + op0 = TREE_OPERAND (arg0, 0); >> + op1 = TREE_OPERAND (arg0, 1); >> + opr0 = TREE_OPERAND (arg1, 0); >> + opr1 = TREE_OPERAND (arg1, 1); >> + >> + /* Convert temporary (X - Y) to (X + (-Y)). */ >> + if (c1 == MINUS_EXPR) >> + { >> + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); >> + c1 = PLUS_EXPR; >> + } >> + >> + /* Convert temporary (X - Y) to (X + (-Y)). */ >> + if (c2 == MINUS_EXPR) >> + { >> + opr1 = fold_build1_loc (loc, NEGATE_EXPR, optype, opr1); >> + c2 = PLUS_EXPR; >> + } >> + >> + if (c1 != c2) >> + return NULL_TREE; >> + >> + /* If OP0 has no side-effects, we might be able to optimize >> + (OP0 + OP1) ==/!= (OP0 + OPR1) to OP1 ==/!= OPR1, >> + (OP0 + OP1) ==/!= (OPR0 + OP0) to OP1 ==/!= OPR0, >> + (OP0 ^ OP1) ==/!= (OP0 ^ OPR1) to OP1 ==/!= OPR1, >> + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP0) to OP1 ==/!= OPR0.. */ >> + if (!TREE_SIDE_EFFECTS (op0)) >> + { >> + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), >> + optype, op0, opr0); >> + if (TREE_CODE (tem) == INTEGER_CST >> + && !TREE_SIDE_EFFECTS (opr0) >> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >> + || c1 == BIT_XOR_EXPR)) >> + { >> + if (!integer_zerop (tem)) >> + tem = fold_build2_loc (loc, c1, optype, op1, tem); >> + else >> + tem = op1; >> + >> + return fold_build2_loc (loc, code, type, tem, opr1); >> + } >> + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), >> + optype, op0, opr1); >> + if (TREE_CODE (tem) == INTEGER_CST >> + && !TREE_SIDE_EFFECTS (opr1) >> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >> + || c1 == BIT_XOR_EXPR)) >> + { >> + if (!integer_zerop (tem)) >> + tem = fold_build2_loc (loc, c1, optype, op1, tem); >> + else >> + tem = op1; >> + return fold_build2_loc (loc, code, type, tem, opr0); >> + } >> + } >> + >> + /* If OP1 has no side-effects, we might be able to optimize >> + (OP0 + OP1) ==/!= (OP1 + OPR1) to OP0 ==/!= OPR1, >> + (OP0 + OP1) ==/!= (OPR0 + OP1) to OP0 ==/!= OPR0, >> + (OP0 ^ OP1) ==/!= (OP1 ^ OPR1) to OP0 ==/!= OPR1, >> + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP1) to OP0 ==/!= OPR0.. */ >> + if (!TREE_SIDE_EFFECTS (op1)) >> + { >> + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), >> + optype, op1, opr0); >> + if (TREE_CODE (tem) == INTEGER_CST >> + && !TREE_SIDE_EFFECTS (opr0) >> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >> + || c1 == BIT_XOR_EXPR)) >> + { >> + if (!integer_zerop (tem)) >> + tem = fold_build2_loc (loc, c1, optype, op0, tem); >> + else >> + tem = op0; >> + return fold_build2_loc (loc, code, type, tem, opr1); >> + } >> + >> + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), >> + optype, op1, opr1); >> + if (TREE_CODE (tem) == INTEGER_CST >> + && !TREE_SIDE_EFFECTS (opr1) >> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >> + || c1 == BIT_XOR_EXPR)) >> + { >> + if (!integer_zerop (tem)) >> + tem = fold_build2_loc (loc, c1, optype, op0, tem); >> + else >> + tem = op0; >> + return fold_build2_loc (loc, code, type, tem, opr0); >> + } >> + } >> + >> + return NULL_TREE; >> +} >> + >> /* Subroutine of fold_binary. This routine performs all of the >> transformations that are common to the equality/inequality >> operators (EQ_EXPR and NE_EXPR) and the ordering operators >> @@ -8767,6 +9002,10 @@ fold_comparison (location_t loc, enum tr >> if (tree_swap_operands_p (arg0, arg1, true)) >> return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0); >> >> + tem = fold_comparison_1 (loc, code, type, arg0, arg1); >> + if (tem != NULL_TREE) >> + return tem; >> + >> /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 +- C1. */ >> if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR) >> && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST >> Index: gcc/gcc/testsuite/gcc.dg/fold-compare-1.c >> =================================================================== >> --- gcc.orig/gcc/testsuite/gcc.dg/fold-compare-1.c >> +++ gcc/gcc/testsuite/gcc.dg/fold-compare-1.c >> @@ -41,7 +41,7 @@ int test8(int l) >> return ~l >= 2; >> } >> >> -/* { dg-final { scan-tree-dump-times "b == a" 1 "original" } } */ >> +/* { dg-final { scan-tree-dump-times "b == a|a == b" 1 "original" } } */ >> /* { dg-final { scan-tree-dump-times "c == d" 1 "original" } } */ >> /* { dg-final { scan-tree-dump-times "e == -5" 1 "original" } } */ >> /* { dg-final { scan-tree-dump-times "f == -6" 1 "original" } } */ >> Index: gcc/gcc/testsuite/gcc.dg/fold-compare-7.c >> =================================================================== >> --- /dev/null >> +++ gcc/gcc/testsuite/gcc.dg/fold-compare-7.c >> @@ -0,0 +1,36 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O2 -fdump-tree-original" } */ >> + >> +int test1(int a, int elim) >> +{ >> + return ~elim == (elim ^ a); >> +} >> + >> +int test2(int elim, int b) >> +{ >> + return -elim == (b - elim); >> +} >> + >> +int test3(int c, int elim, int d) >> +{ >> + return (c + elim) != (elim + d); >> +} >> + >> +int test4(int e, int f, int elim) >> +{ >> + return (e - elim) != (-elim + f); >> +} >> + >> +int test5(int g, int h, int elim) >> +{ >> + return (elim ^ g) == (h ^ elim); >> +} >> + >> +int test6(int i, int j, int elim) >> +{ >> + return (elim ^ i) == (j ^ ~elim); >> +} >> + >> +/* { dg-final { scan-tree-dump-times "elim" 0 "original" } } */ >> +/* { dg-final { cleanup-tree-dump "original" } } */ >> + Regards, Kai
On Mon, Apr 16, 2012 at 3:58 PM, Kai Tietz <ktietz70@googlemail.com> wrote: > 2012/4/12 Richard Guenther <richard.guenther@gmail.com>: >> On Thu, Apr 5, 2012 at 6:15 PM, Kai Tietz <ktietz70@googlemail.com> wrote: >>> Hello, >>> >>> this patch adds some basic folding capabilities to fold-const for >>> equal and none-equal comparisons >>> on integer typed argument. >>> >>> ChangeLog >>> >>> 2012-04-05 Kai Tietz <ktietz@redhat.com> >>> >>> * fold-const.c (fold_comparison_1): New >>> function. >>> (fold_comparison): Use fold_comparison_1. >>> >>> 2012-04-05 Kai Tietz <ktietz@redhat.com> >>> >>> * gcc.dg/fold-compare-1.c: Adjust matching rule >>> for a == b without argument swap. >>> * gcc.dg/fold-compare-7.c: New test. >>> >>> Regession tested for x86_64-unknown-linux-gnu for all languages >>> (including Ada and Obj-C++). Ok for apply? >>> >>> Regards, >>> Kai >>> >>> Index: gcc/gcc/fold-const.c >>> =================================================================== >>> --- gcc.orig/gcc/fold-const.c >>> +++ gcc/gcc/fold-const.c >>> @@ -8739,6 +8739,241 @@ pointer_may_wrap_p (tree base, tree offs >>> return total_low > (unsigned HOST_WIDE_INT) size; >>> } >>> >>> +/* Sub-routine of fold_comparison. Folding of EQ_EXPR/NE_EXPR >>> + comparisons with integral typed arguments. */ >>> + >>> +static tree >>> +fold_comparison_1 (location_t loc, enum tree_code code, tree type, >>> + tree arg0, tree arg1) >> >> Please name it more specific, like for example >> fold_integral_equality_comparison. >> >>> +{ >>> + enum tree_code c1, c2; >>> + tree optype, op0, op1, opr0, opr1, tem; >>> + >>> + if (code != NE_EXPR && code != EQ_EXPR) >>> + return NULL_TREE; >>> + >>> + optype = TREE_TYPE (arg0); >>> + if (!INTEGRAL_TYPE_P (optype)) >>> + return NULL_TREE; >>> + >>> + c1 = TREE_CODE (arg0); >>> + c2 = TREE_CODE (arg1); >>> + >>> + /* Integer constant is on right-hand side. */ >>> + if (c1 == INTEGER_CST >>> + && c2 != c1) >>> + return fold_build2_loc (loc, code, type, arg1, arg0); >> >> /* If one arg is a real or integer constant, put it last. */ >> if (tree_swap_operands_p (arg0, arg1, true)) >> return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0); >> >> in fold_comparison already ensures this. >> >>> + if (!TREE_SIDE_EFFECTS (arg0) >>> + && operand_equal_p (arg0, arg1, 0)) >>> + { >>> + if (code == EQ_EXPR) >>> + return build_one_cst (type); >>> + return build_zero_cst (type); >>> + } >> >> This is already done in a more general way in fold_comparison: > > Yes, was a duplicate like ... > >> /* Simplify comparison of something with itself. (For IEEE >> floating-point, we can only do some of these simplifications.) */ >> if (operand_equal_p (arg0, arg1, 0)) >> { >> switch (code) >> { >> case EQ_EXPR: >> ... >> >> which also shows how to fold to true/false - using constant_boolean_node. > > like this one. So I removed from patch. > >>> + >>> + if (c1 == NEGATE_EXPR) >>> + { >>> + op0 = TREE_OPERAND (arg0, 0); >>> + /* -X ==/!= -Y -> X ==/!= Y. */ >>> + if (c2 == c1) >>> + return fold_build2_loc (loc, code, type, >>> + op0, >>> + TREE_OPERAND (arg1, 0)); >> >> This is already done, in a more general way but only for float types, >> in fold_comparison. It's beyond me why it is conditional on float types >> there and does not check for trapping math and NaNs (maybe that's >> well-defined - one would need to double-check). For integral types >> you'd have to care for undefined overflow (or issue a warning), and ... > > You miss here explicit a point about ==/!= comparisons. The negate > can be removed for such comparisons uncoditionally, as there can't > happen an overflow, which changes result of compare. It would be even > a flaw for checking here for those cases about overflow. You miss the fact that the _negate_ can overflow. Thus, with -ftrapv you can end up removing a side-effect. >>> + /* -X ==/!= CST -> X ==/!= CST' with CST'= -CST. */ >>> + else if (c2 == INTEGER_CST) >>> + return fold_build2_loc (loc, code, type, op0, >>> + fold_build1_loc (loc, NEGATE_EXPR, >>> + optype, arg1)); >> >> ... generalizing this the code should use negate_expr_p / negate_expr >> to for example handle folding -b != b - a to b != a - b (of course you'd >> require at least one explicit NEGATE_EXPR - similar foldings elsewhere >> will tell you what to do). > > See, above. No, it would be a failure to use negate_expr_p here, as > the overflow simply doesn't matter and there is also no need to warn > about it. negate_expr_p is not about overflow but about "can we cheaply negate this?" Thus, if you have -X == Y and negate_expr_p returns true for Y you can fold it to X == negate_expr (Y). No need to only handle integer constants. >>> + } >>> + else if (c1 == BIT_NOT_EXPR) >>> + { >>> + op0 = TREE_OPERAND (arg0, 0); >>> + /* ~X ==/!= ~Y -> X ==/!= Y. */ >>> + if (c2 == c1) >>> + return fold_build2_loc (loc, code, type, op0, >>> + TREE_OPERAND (arg1, 0)); >> >> This can be generalized to relational comparisons as well I think. It's also >> already done in fold_comparison here: > > No it isn't. As again for ==/!= comparison the overflow simply > doesn't matter. Therefore I added this function to special-case > (non-)equal-comparison. The overflow cases are already handled for > general comparison, no need to do it twice. > >> /* Fold ~X op ~Y as Y op X. */ >> if (TREE_CODE (arg0) == BIT_NOT_EXPR >> && TREE_CODE (arg1) == BIT_NOT_EXPR) >> { Where do you see the overflow checking here? >> >>> + /* ~X ==/!= CST -> X ==/!= CST' with CST'= ~CST. */ >>> + else if (c2 == INTEGER_CST) >>> + return fold_build2_loc (loc, code, type, op0, >>> + fold_build1_loc (loc, BIT_NOT_EXPR, >>> + optype, arg1)); >> >> Possibly unified with having a new predicate/worker invert_expr_p / invert_expr. > > Well, there is no need for an invert_expr_p (see above). Also in this > case we don't need and have to warn. See my comment about negate_expr_p. >>> + } >>> + >>> + /* See if we can simplify case X == (Y +|-|^ Z). */ >>> + if (c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) >>> + { >>> + if ((c2 != PLUS_EXPR && c2 != MINUS_EXPR >>> + && c2 != BIT_XOR_EXPR) >>> + || TREE_SIDE_EFFECTS (arg0)) >>> + return NULL_TREE; >> >> (I'm not sure why you are testing for side-effects - if you omit sth use >> omit_*_operand ()) > > Actual the use of omit_*_operand () introduces for none-volative cases > NON_LVALUE_EXPR expressions, which are within comparisons vain. Also > it wasn't quite clear if the following reduction of volatiles within a > comparison is valid. At least for substractions we don't do this > optimization, so I would assume that it would be wrong for > comparisons, too. omit_*_operand emits COMPOUND_EXPRs, not NON_LVALUE_EXPRs. Richard. > >>> + >>> + op0 = TREE_OPERAND (arg1, 0); >>> + op1 = TREE_OPERAND (arg1, 1); >> >> Please use names like arg10 and arg11 as elsewhere in folding. >> >>> + /* Convert temporary X - Y to X + (-Y). */ >>> + if (c2 == MINUS_EXPR) >>> + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); >> >> That's not a good idea - in general we avoid building scratch trees >> during folding. > > Well, this patterns can be of course written out explicit. But by > doing this transformation simplifies later on used patterns a bit. > Also it can be later on used for futher optimizations about value > preditions for patterns like 'a == 1 - a' being always false for all > integer values, etc. > >>> + >>> + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, >>> + or X ==/!= (X +|- Y) to Y ==/!= 0. */ >>> + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), >>> + optype, arg0, op0); >> >> Similar - also this code and the code below duplicates things four times. >> That's both expensive and hard to read. It asks for some factorization >> and use of explicit pattern matching instead of recursing into folding. > > Not quite sure what you mean here by recursion. We have actual here > three cases (with op being PLUS/MINUX or XOR expression): > > 1) A !=/== B (which is already convered in general comparison-code) > > 2) A !=/== (B op C) or (A op B) !=/== C (this I duplicated in code, > but could be of course factored out into a helper-routine) > > and > > 3 (A op B) !=/== (C op D) > >>> + if (TREE_CODE (tem) == INTEGER_CST >>> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >>> + || c2 == BIT_XOR_EXPR)) >>> + return fold_build2_loc (loc, code, type, op1, tem); >>> + >>> + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, >>> + or X ==/!= (Y + X) to Y ==/!= 0. */ >>> + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), >>> + optype, arg0, op1); >>> + if (TREE_CODE (tem) == INTEGER_CST >>> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >>> + || c2 == BIT_XOR_EXPR)) >>> + return fold_build2_loc (loc, code, type, op0, tem); >>> + } >>> + else if (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR) >>> + { >>> + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR >>> + && c1 != BIT_XOR_EXPR) >>> + || TREE_SIDE_EFFECTS (arg1)) >>> + return NULL_TREE; >>> + >>> + op0 = TREE_OPERAND (arg0, 0); >>> + op1 = TREE_OPERAND (arg0, 1); >>> + >>> + /* Convert temporary X - Y to X + (-Y). */ >>> + if (c1 == MINUS_EXPR) >>> + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); >>> + >>> + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, >>> + or X ==/!= (X +|- Y) to Y ==/!= 0. */ >>> + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), >>> + optype, arg1, op0); >>> + if (TREE_CODE (tem) == INTEGER_CST >>> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >>> + || c1 == BIT_XOR_EXPR)) >>> + return fold_build2_loc (loc, code, type, op1, tem); >>> + >>> + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, >>> + or X ==/!= (Y + X) to Y ==/!= 0. */ >>> + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), >>> + optype, arg1, op1); >>> + if (TREE_CODE (tem) == INTEGER_CST >>> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >>> + || c1 == BIT_XOR_EXPR)) >>> + return fold_build2_loc (loc, code, type, op0, tem); >>> + } >>> + >>> + /* We check if arg1 and arg2 are matching one of the patterns >>> + (V + W) ==/!= (X + Y), (V + W) ==/!= (X - Y), (V - W) ==/!= (X + Y), >>> + (V - W) ==/!= (X - Y), or (V ^ W) ==/!= (X ^ Y). */ >> >> I stopped reading here. Please try to double check what we already do, >> don't produce new code for everything you can think of. This patch could >> have needed splitting, too. >> >> Richard. >> >>> + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) >>> + || (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR)) >>> + return NULL_TREE; >>> + if (c1 != c2 && (c1 == BIT_XOR_EXPR || c2 == BIT_XOR_EXPR)) >>> + return NULL_TREE; >>> + >>> + op0 = TREE_OPERAND (arg0, 0); >>> + op1 = TREE_OPERAND (arg0, 1); >>> + opr0 = TREE_OPERAND (arg1, 0); >>> + opr1 = TREE_OPERAND (arg1, 1); >>> + >>> + /* Convert temporary (X - Y) to (X + (-Y)). */ >>> + if (c1 == MINUS_EXPR) >>> + { >>> + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); >>> + c1 = PLUS_EXPR; >>> + } >>> + >>> + /* Convert temporary (X - Y) to (X + (-Y)). */ >>> + if (c2 == MINUS_EXPR) >>> + { >>> + opr1 = fold_build1_loc (loc, NEGATE_EXPR, optype, opr1); >>> + c2 = PLUS_EXPR; >>> + } >>> + >>> + if (c1 != c2) >>> + return NULL_TREE; >>> + >>> + /* If OP0 has no side-effects, we might be able to optimize >>> + (OP0 + OP1) ==/!= (OP0 + OPR1) to OP1 ==/!= OPR1, >>> + (OP0 + OP1) ==/!= (OPR0 + OP0) to OP1 ==/!= OPR0, >>> + (OP0 ^ OP1) ==/!= (OP0 ^ OPR1) to OP1 ==/!= OPR1, >>> + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP0) to OP1 ==/!= OPR0.. */ >>> + if (!TREE_SIDE_EFFECTS (op0)) >>> + { >>> + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), >>> + optype, op0, opr0); >>> + if (TREE_CODE (tem) == INTEGER_CST >>> + && !TREE_SIDE_EFFECTS (opr0) >>> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >>> + || c1 == BIT_XOR_EXPR)) >>> + { >>> + if (!integer_zerop (tem)) >>> + tem = fold_build2_loc (loc, c1, optype, op1, tem); >>> + else >>> + tem = op1; >>> + >>> + return fold_build2_loc (loc, code, type, tem, opr1); >>> + } >>> + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), >>> + optype, op0, opr1); >>> + if (TREE_CODE (tem) == INTEGER_CST >>> + && !TREE_SIDE_EFFECTS (opr1) >>> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >>> + || c1 == BIT_XOR_EXPR)) >>> + { >>> + if (!integer_zerop (tem)) >>> + tem = fold_build2_loc (loc, c1, optype, op1, tem); >>> + else >>> + tem = op1; >>> + return fold_build2_loc (loc, code, type, tem, opr0); >>> + } >>> + } >>> + >>> + /* If OP1 has no side-effects, we might be able to optimize >>> + (OP0 + OP1) ==/!= (OP1 + OPR1) to OP0 ==/!= OPR1, >>> + (OP0 + OP1) ==/!= (OPR0 + OP1) to OP0 ==/!= OPR0, >>> + (OP0 ^ OP1) ==/!= (OP1 ^ OPR1) to OP0 ==/!= OPR1, >>> + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP1) to OP0 ==/!= OPR0.. */ >>> + if (!TREE_SIDE_EFFECTS (op1)) >>> + { >>> + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), >>> + optype, op1, opr0); >>> + if (TREE_CODE (tem) == INTEGER_CST >>> + && !TREE_SIDE_EFFECTS (opr0) >>> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >>> + || c1 == BIT_XOR_EXPR)) >>> + { >>> + if (!integer_zerop (tem)) >>> + tem = fold_build2_loc (loc, c1, optype, op0, tem); >>> + else >>> + tem = op0; >>> + return fold_build2_loc (loc, code, type, tem, opr1); >>> + } >>> + >>> + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), >>> + optype, op1, opr1); >>> + if (TREE_CODE (tem) == INTEGER_CST >>> + && !TREE_SIDE_EFFECTS (opr1) >>> + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) >>> + || c1 == BIT_XOR_EXPR)) >>> + { >>> + if (!integer_zerop (tem)) >>> + tem = fold_build2_loc (loc, c1, optype, op0, tem); >>> + else >>> + tem = op0; >>> + return fold_build2_loc (loc, code, type, tem, opr0); >>> + } >>> + } >>> + >>> + return NULL_TREE; >>> +} >>> + >>> /* Subroutine of fold_binary. This routine performs all of the >>> transformations that are common to the equality/inequality >>> operators (EQ_EXPR and NE_EXPR) and the ordering operators >>> @@ -8767,6 +9002,10 @@ fold_comparison (location_t loc, enum tr >>> if (tree_swap_operands_p (arg0, arg1, true)) >>> return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0); >>> >>> + tem = fold_comparison_1 (loc, code, type, arg0, arg1); >>> + if (tem != NULL_TREE) >>> + return tem; >>> + >>> /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 +- C1. */ >>> if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR) >>> && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST >>> Index: gcc/gcc/testsuite/gcc.dg/fold-compare-1.c >>> =================================================================== >>> --- gcc.orig/gcc/testsuite/gcc.dg/fold-compare-1.c >>> +++ gcc/gcc/testsuite/gcc.dg/fold-compare-1.c >>> @@ -41,7 +41,7 @@ int test8(int l) >>> return ~l >= 2; >>> } >>> >>> -/* { dg-final { scan-tree-dump-times "b == a" 1 "original" } } */ >>> +/* { dg-final { scan-tree-dump-times "b == a|a == b" 1 "original" } } */ >>> /* { dg-final { scan-tree-dump-times "c == d" 1 "original" } } */ >>> /* { dg-final { scan-tree-dump-times "e == -5" 1 "original" } } */ >>> /* { dg-final { scan-tree-dump-times "f == -6" 1 "original" } } */ >>> Index: gcc/gcc/testsuite/gcc.dg/fold-compare-7.c >>> =================================================================== >>> --- /dev/null >>> +++ gcc/gcc/testsuite/gcc.dg/fold-compare-7.c >>> @@ -0,0 +1,36 @@ >>> +/* { dg-do compile } */ >>> +/* { dg-options "-O2 -fdump-tree-original" } */ >>> + >>> +int test1(int a, int elim) >>> +{ >>> + return ~elim == (elim ^ a); >>> +} >>> + >>> +int test2(int elim, int b) >>> +{ >>> + return -elim == (b - elim); >>> +} >>> + >>> +int test3(int c, int elim, int d) >>> +{ >>> + return (c + elim) != (elim + d); >>> +} >>> + >>> +int test4(int e, int f, int elim) >>> +{ >>> + return (e - elim) != (-elim + f); >>> +} >>> + >>> +int test5(int g, int h, int elim) >>> +{ >>> + return (elim ^ g) == (h ^ elim); >>> +} >>> + >>> +int test6(int i, int j, int elim) >>> +{ >>> + return (elim ^ i) == (j ^ ~elim); >>> +} >>> + >>> +/* { dg-final { scan-tree-dump-times "elim" 0 "original" } } */ >>> +/* { dg-final { cleanup-tree-dump "original" } } */ >>> + > > > Regards, > Kai
2012/4/16 Richard Guenther <richard.guenther@gmail.com>: > On Mon, Apr 16, 2012 at 3:58 PM, Kai Tietz <ktietz70@googlemail.com> wrote: >> 2012/4/12 Richard Guenther <richard.guenther@gmail.com>: >>> On Thu, Apr 5, 2012 at 6:15 PM, Kai Tietz <ktietz70@googlemail.com> wrote: >>>> Hello, >>>> >>>> this patch adds some basic folding capabilities to fold-const for >>>> equal and none-equal comparisons >>>> on integer typed argument. >>>> >>>> ChangeLog >>>> >>>> 2012-04-05 Kai Tietz <ktietz@redhat.com> >>>> >>>> * fold-const.c (fold_comparison_1): New >>>> function. >>>> (fold_comparison): Use fold_comparison_1. >>>> >>>> 2012-04-05 Kai Tietz <ktietz@redhat.com> >>>> >>>> * gcc.dg/fold-compare-1.c: Adjust matching rule >>>> for a == b without argument swap. >>>> * gcc.dg/fold-compare-7.c: New test. >>>> >>>> Regession tested for x86_64-unknown-linux-gnu for all languages >>>> (including Ada and Obj-C++). Ok for apply? >>>> >>>> Regards, >>>> Kai >>>> >>>> Index: gcc/gcc/fold-const.c >>>> =================================================================== >>>> --- gcc.orig/gcc/fold-const.c >>>> +++ gcc/gcc/fold-const.c >>>> @@ -8739,6 +8739,241 @@ pointer_may_wrap_p (tree base, tree offs >>>> return total_low > (unsigned HOST_WIDE_INT) size; >>>> } >>>> >>>> +/* Sub-routine of fold_comparison. Folding of EQ_EXPR/NE_EXPR >>>> + comparisons with integral typed arguments. */ >>>> + >>>> +static tree >>>> +fold_comparison_1 (location_t loc, enum tree_code code, tree type, >>>> + tree arg0, tree arg1) >>> >>> Please name it more specific, like for example >>> fold_integral_equality_comparison. >>> >>>> +{ >>>> + enum tree_code c1, c2; >>>> + tree optype, op0, op1, opr0, opr1, tem; >>>> + >>>> + if (code != NE_EXPR && code != EQ_EXPR) >>>> + return NULL_TREE; >>>> + >>>> + optype = TREE_TYPE (arg0); >>>> + if (!INTEGRAL_TYPE_P (optype)) >>>> + return NULL_TREE; >>>> + >>>> + c1 = TREE_CODE (arg0); >>>> + c2 = TREE_CODE (arg1); >>>> + >>>> + /* Integer constant is on right-hand side. */ >>>> + if (c1 == INTEGER_CST >>>> + && c2 != c1) >>>> + return fold_build2_loc (loc, code, type, arg1, arg0); >>> >>> /* If one arg is a real or integer constant, put it last. */ >>> if (tree_swap_operands_p (arg0, arg1, true)) >>> return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0); >>> >>> in fold_comparison already ensures this. >>> >>>> + if (!TREE_SIDE_EFFECTS (arg0) >>>> + && operand_equal_p (arg0, arg1, 0)) >>>> + { >>>> + if (code == EQ_EXPR) >>>> + return build_one_cst (type); >>>> + return build_zero_cst (type); >>>> + } >>> >>> This is already done in a more general way in fold_comparison: >> >> Yes, was a duplicate like ... >> >>> /* Simplify comparison of something with itself. (For IEEE >>> floating-point, we can only do some of these simplifications.) */ >>> if (operand_equal_p (arg0, arg1, 0)) >>> { >>> switch (code) >>> { >>> case EQ_EXPR: >>> ... >>> >>> which also shows how to fold to true/false - using constant_boolean_node. >> >> like this one. So I removed from patch. >> >>>> + >>>> + if (c1 == NEGATE_EXPR) >>>> + { >>>> + op0 = TREE_OPERAND (arg0, 0); >>>> + /* -X ==/!= -Y -> X ==/!= Y. */ >>>> + if (c2 == c1) >>>> + return fold_build2_loc (loc, code, type, >>>> + op0, >>>> + TREE_OPERAND (arg1, 0)); >>> >>> This is already done, in a more general way but only for float types, >>> in fold_comparison. It's beyond me why it is conditional on float types >>> there and does not check for trapping math and NaNs (maybe that's >>> well-defined - one would need to double-check). For integral types >>> you'd have to care for undefined overflow (or issue a warning), and ... >> >> You miss here explicit a point about ==/!= comparisons. The negate >> can be removed for such comparisons uncoditionally, as there can't >> happen an overflow, which changes result of compare. It would be even >> a flaw for checking here for those cases about overflow. > > You miss the fact that the _negate_ can overflow. Thus, with -ftrapv > you can end up removing a side-effect. > >>>> + /* -X ==/!= CST -> X ==/!= CST' with CST'= -CST. */ >>>> + else if (c2 == INTEGER_CST) >>>> + return fold_build2_loc (loc, code, type, op0, >>>> + fold_build1_loc (loc, NEGATE_EXPR, >>>> + optype, arg1)); >>> >>> ... generalizing this the code should use negate_expr_p / negate_expr >>> to for example handle folding -b != b - a to b != a - b (of course you'd >>> require at least one explicit NEGATE_EXPR - similar foldings elsewhere >>> will tell you what to do). >> >> See, above. No, it would be a failure to use negate_expr_p here, as >> the overflow simply doesn't matter and there is also no need to warn >> about it. > > negate_expr_p is not about overflow but about "can we cheaply negate this?" > Thus, if you have -X == Y and negate_expr_p returns true for Y you can > fold it to X == negate_expr (Y). No need to only handle integer constants. Hmm, can't confirm that. Neither by code, nor by its comment: /* Determine whether an expression T can be cheaply negated using the function negate_expr without introducing undefined overflow. */ static bool negate_expr_p (tree t) ,,, >>>> + } >>>> + else if (c1 == BIT_NOT_EXPR) >>>> + { >>>> + op0 = TREE_OPERAND (arg0, 0); >>>> + /* ~X ==/!= ~Y -> X ==/!= Y. */ >>>> + if (c2 == c1) >>>> + return fold_build2_loc (loc, code, type, op0, >>>> + TREE_OPERAND (arg1, 0)); >>> >>> This can be generalized to relational comparisons as well I think. It's also >>> already done in fold_comparison here: >> >> No it isn't. As again for ==/!= comparison the overflow simply >> doesn't matter. Therefore I added this function to special-case >> (non-)equal-comparison. The overflow cases are already handled for >> general comparison, no need to do it twice. >> >>> /* Fold ~X op ~Y as Y op X. */ >>> if (TREE_CODE (arg0) == BIT_NOT_EXPR >>> && TREE_CODE (arg1) == BIT_NOT_EXPR) >>> { > > Where do you see the overflow checking here? I assume that you mean the same behavior as present for negate_expr_p/negate_expr. >>> >>>> + /* ~X ==/!= CST -> X ==/!= CST' with CST'= ~CST. */ >>>> + else if (c2 == INTEGER_CST) >>>> + return fold_build2_loc (loc, code, type, op0, >>>> + fold_build1_loc (loc, BIT_NOT_EXPR, >>>> + optype, arg1)); >>> >>> Possibly unified with having a new predicate/worker invert_expr_p / invert_expr. >> >> Well, there is no need for an invert_expr_p (see above). Also in this >> case we don't need and have to warn. > > See my comment about negate_expr_p. > >>>> + } >>>> + >>>> + /* See if we can simplify case X == (Y +|-|^ Z). */ >>>> + if (c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) >>>> + { >>>> + if ((c2 != PLUS_EXPR && c2 != MINUS_EXPR >>>> + && c2 != BIT_XOR_EXPR) >>>> + || TREE_SIDE_EFFECTS (arg0)) >>>> + return NULL_TREE; >>> >>> (I'm not sure why you are testing for side-effects - if you omit sth use >>> omit_*_operand ()) >> >> Actual the use of omit_*_operand () introduces for none-volative cases >> NON_LVALUE_EXPR expressions, which are within comparisons vain. Also >> it wasn't quite clear if the following reduction of volatiles within a >> comparison is valid. At least for substractions we don't do this >> optimization, so I would assume that it would be wrong for >> comparisons, too. > > omit_*_operand emits COMPOUND_EXPRs, not NON_LVALUE_EXPRs. Hmm, can't confirm that. Please see as example omit_one_operand_loc. For none-side-effect-case we return for it non_lvalue_loc (loc, t), which is for AST an NON_LVALUE_EXPR (for gimple we don't do that). Regards, Kai
Index: gcc/gcc/fold-const.c =================================================================== --- gcc.orig/gcc/fold-const.c +++ gcc/gcc/fold-const.c @@ -8739,6 +8739,241 @@ pointer_may_wrap_p (tree base, tree offs return total_low > (unsigned HOST_WIDE_INT) size; } +/* Sub-routine of fold_comparison. Folding of EQ_EXPR/NE_EXPR + comparisons with integral typed arguments. */ + +static tree +fold_comparison_1 (location_t loc, enum tree_code code, tree type, + tree arg0, tree arg1) +{ + enum tree_code c1, c2; + tree optype, op0, op1, opr0, opr1, tem; + + if (code != NE_EXPR && code != EQ_EXPR) + return NULL_TREE; + + optype = TREE_TYPE (arg0); + if (!INTEGRAL_TYPE_P (optype)) + return NULL_TREE; + + c1 = TREE_CODE (arg0); + c2 = TREE_CODE (arg1); + + /* Integer constant is on right-hand side. */ + if (c1 == INTEGER_CST + && c2 != c1) + return fold_build2_loc (loc, code, type, arg1, arg0); + + if (!TREE_SIDE_EFFECTS (arg0) + && operand_equal_p (arg0, arg1, 0)) + { + if (code == EQ_EXPR) + return build_one_cst (type); + return build_zero_cst (type); + } + + + if (c1 == NEGATE_EXPR) + { + op0 = TREE_OPERAND (arg0, 0); + /* -X ==/!= -Y -> X ==/!= Y. */ + if (c2 == c1) + return fold_build2_loc (loc, code, type, + op0, + TREE_OPERAND (arg1, 0)); + /* -X ==/!= CST -> X ==/!= CST' with CST'= -CST. */ + else if (c2 == INTEGER_CST) + return fold_build2_loc (loc, code, type, op0, + fold_build1_loc (loc, NEGATE_EXPR, + optype, arg1)); + } + else if (c1 == BIT_NOT_EXPR) + { + op0 = TREE_OPERAND (arg0, 0); + /* ~X ==/!= ~Y -> X ==/!= Y. */ + if (c2 == c1) + return fold_build2_loc (loc, code, type, op0, + TREE_OPERAND (arg1, 0)); + /* ~X ==/!= CST -> X ==/!= CST' with CST'= ~CST. */ + else if (c2 == INTEGER_CST) + return fold_build2_loc (loc, code, type, op0, + fold_build1_loc (loc, BIT_NOT_EXPR, + optype, arg1)); + } + + /* See if we can simplify case X == (Y +|-|^ Z). */ + if (c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) + { + if ((c2 != PLUS_EXPR && c2 != MINUS_EXPR + && c2 != BIT_XOR_EXPR) + || TREE_SIDE_EFFECTS (arg0)) + return NULL_TREE; + + op0 = TREE_OPERAND (arg1, 0); + op1 = TREE_OPERAND (arg1, 1); + + /* Convert temporary X - Y to X + (-Y). */ + if (c2 == MINUS_EXPR) + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); + + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, + or X ==/!= (X +|- Y) to Y ==/!= 0. */ + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), + optype, arg0, op0); + if (TREE_CODE (tem) == INTEGER_CST + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) + || c2 == BIT_XOR_EXPR)) + return fold_build2_loc (loc, code, type, op1, tem); + + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, + or X ==/!= (Y + X) to Y ==/!= 0. */ + tem = fold_build2_loc (loc, (c2 == BIT_XOR_EXPR ? c2 : MINUS_EXPR), + optype, arg0, op1); + if (TREE_CODE (tem) == INTEGER_CST + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) + || c2 == BIT_XOR_EXPR)) + return fold_build2_loc (loc, code, type, op0, tem); + } + else if (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR) + { + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR + && c1 != BIT_XOR_EXPR) + || TREE_SIDE_EFFECTS (arg1)) + return NULL_TREE; + + op0 = TREE_OPERAND (arg0, 0); + op1 = TREE_OPERAND (arg0, 1); + + /* Convert temporary X - Y to X + (-Y). */ + if (c1 == MINUS_EXPR) + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); + + /* Check if we can simplify X ==/!= (X ^ Y) to Y ==/!= 0, + or X ==/!= (X +|- Y) to Y ==/!= 0. */ + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), + optype, arg1, op0); + if (TREE_CODE (tem) == INTEGER_CST + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) + || c1 == BIT_XOR_EXPR)) + return fold_build2_loc (loc, code, type, op1, tem); + + /* Check if we can simplify X ==/!= (Y ^ X) to Y ==/!= 0, + or X ==/!= (Y + X) to Y ==/!= 0. */ + tem = fold_build2_loc (loc, (c1 == BIT_XOR_EXPR ? c1 : MINUS_EXPR), + optype, arg1, op1); + if (TREE_CODE (tem) == INTEGER_CST + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) + || c1 == BIT_XOR_EXPR)) + return fold_build2_loc (loc, code, type, op0, tem); + } + + /* We check if arg1 and arg2 are matching one of the patterns + (V + W) ==/!= (X + Y), (V + W) ==/!= (X - Y), (V - W) ==/!= (X + Y), + (V - W) ==/!= (X - Y), or (V ^ W) ==/!= (X ^ Y). */ + + if ((c1 != PLUS_EXPR && c1 != MINUS_EXPR && c1 != BIT_XOR_EXPR) + || (c2 != PLUS_EXPR && c2 != MINUS_EXPR && c2 != BIT_XOR_EXPR)) + return NULL_TREE; + if (c1 != c2 && (c1 == BIT_XOR_EXPR || c2 == BIT_XOR_EXPR)) + return NULL_TREE; + + op0 = TREE_OPERAND (arg0, 0); + op1 = TREE_OPERAND (arg0, 1); + opr0 = TREE_OPERAND (arg1, 0); + opr1 = TREE_OPERAND (arg1, 1); + + /* Convert temporary (X - Y) to (X + (-Y)). */ + if (c1 == MINUS_EXPR) + { + op1 = fold_build1_loc (loc, NEGATE_EXPR, optype, op1); + c1 = PLUS_EXPR; + } + + /* Convert temporary (X - Y) to (X + (-Y)). */ + if (c2 == MINUS_EXPR) + { + opr1 = fold_build1_loc (loc, NEGATE_EXPR, optype, opr1); + c2 = PLUS_EXPR; + } + + if (c1 != c2) + return NULL_TREE; + + /* If OP0 has no side-effects, we might be able to optimize + (OP0 + OP1) ==/!= (OP0 + OPR1) to OP1 ==/!= OPR1, + (OP0 + OP1) ==/!= (OPR0 + OP0) to OP1 ==/!= OPR0, + (OP0 ^ OP1) ==/!= (OP0 ^ OPR1) to OP1 ==/!= OPR1, + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP0) to OP1 ==/!= OPR0.. */ + if (!TREE_SIDE_EFFECTS (op0)) + { + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), + optype, op0, opr0); + if (TREE_CODE (tem) == INTEGER_CST + && !TREE_SIDE_EFFECTS (opr0) + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) + || c1 == BIT_XOR_EXPR)) + { + if (!integer_zerop (tem)) + tem = fold_build2_loc (loc, c1, optype, op1, tem); + else + tem = op1; + + return fold_build2_loc (loc, code, type, tem, opr1); + } + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), + optype, op0, opr1); + if (TREE_CODE (tem) == INTEGER_CST + && !TREE_SIDE_EFFECTS (opr1) + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) + || c1 == BIT_XOR_EXPR)) + { + if (!integer_zerop (tem)) + tem = fold_build2_loc (loc, c1, optype, op1, tem); + else + tem = op1; + return fold_build2_loc (loc, code, type, tem, opr0); + } + } + + /* If OP1 has no side-effects, we might be able to optimize + (OP0 + OP1) ==/!= (OP1 + OPR1) to OP0 ==/!= OPR1, + (OP0 + OP1) ==/!= (OPR0 + OP1) to OP0 ==/!= OPR0, + (OP0 ^ OP1) ==/!= (OP1 ^ OPR1) to OP0 ==/!= OPR1, + or (OP0 ^ OP1) ==/!= (OPR0 ^ OP1) to OP0 ==/!= OPR0.. */ + if (!TREE_SIDE_EFFECTS (op1)) + { + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), + optype, op1, opr0); + if (TREE_CODE (tem) == INTEGER_CST + && !TREE_SIDE_EFFECTS (opr0) + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) + || c1 == BIT_XOR_EXPR)) + { + if (!integer_zerop (tem)) + tem = fold_build2_loc (loc, c1, optype, op0, tem); + else + tem = op0; + return fold_build2_loc (loc, code, type, tem, opr1); + } + + tem = fold_build2_loc (loc, (c1 == PLUS_EXPR ? MINUS_EXPR : c1), + optype, op1, opr1); + if (TREE_CODE (tem) == INTEGER_CST + && !TREE_SIDE_EFFECTS (opr1) + && (integer_zerop (tem) || TYPE_UNSIGNED (optype) + || c1 == BIT_XOR_EXPR)) + { + if (!integer_zerop (tem)) + tem = fold_build2_loc (loc, c1, optype, op0, tem); + else + tem = op0; + return fold_build2_loc (loc, code, type, tem, opr0); + } + } + + return NULL_TREE; +} + /* Subroutine of fold_binary. This routine performs all of the transformations that are common to the equality/inequality operators (EQ_EXPR and NE_EXPR) and the ordering operators @@ -8767,6 +9002,10 @@ fold_comparison (location_t loc, enum tr if (tree_swap_operands_p (arg0, arg1, true)) return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0); + tem = fold_comparison_1 (loc, code, type, arg0, arg1); + if (tem != NULL_TREE) + return tem; + /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 +- C1. */ if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR) && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST Index: gcc/gcc/testsuite/gcc.dg/fold-compare-1.c =================================================================== --- gcc.orig/gcc/testsuite/gcc.dg/fold-compare-1.c +++ gcc/gcc/testsuite/gcc.dg/fold-compare-1.c @@ -41,7 +41,7 @@ int test8(int l) return ~l >= 2; } -/* { dg-final { scan-tree-dump-times "b == a" 1 "original" } } */ +/* { dg-final { scan-tree-dump-times "b == a|a == b" 1 "original" } } */ /* { dg-final { scan-tree-dump-times "c == d" 1 "original" } } */ /* { dg-final { scan-tree-dump-times "e == -5" 1 "original" } } */ /* { dg-final { scan-tree-dump-times "f == -6" 1 "original" } } */ Index: gcc/gcc/testsuite/gcc.dg/fold-compare-7.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/fold-compare-7.c @@ -0,0 +1,36 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-original" } */ + +int test1(int a, int elim) +{ + return ~elim == (elim ^ a); +} + +int test2(int elim, int b) +{ + return -elim == (b - elim); +} + +int test3(int c, int elim, int d) +{ + return (c + elim) != (elim + d); +} + +int test4(int e, int f, int elim) +{ + return (e - elim) != (-elim + f); +} + +int test5(int g, int h, int elim) +{ + return (elim ^ g) == (h ^ elim); +} + +int test6(int i, int j, int elim) +{ + return (elim ^ i) == (j ^ ~elim); +} + +/* { dg-final { scan-tree-dump-times "elim" 0 "original" } } */ +/* { dg-final { cleanup-tree-dump "original" } } */ +