On Mon, Apr 16, 2012 at 3:58 PM, Kai Tietz <ktiet...@googlemail.com> wrote: > 2012/4/12 Richard Guenther <richard.guent...@gmail.com>: >> On Thu, Apr 5, 2012 at 6:15 PM, Kai Tietz <ktiet...@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 <kti...@redhat.com> >>> >>> * fold-const.c (fold_comparison_1): New >>> function. >>> (fold_comparison): Use fold_comparison_1. >>> >>> 2012-04-05 Kai Tietz <kti...@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