* [RFC] optimize x - y cmp 0 with undefined overflow @ 2014-05-26 10:24 Eric Botcazou 2014-05-26 12:55 ` Richard Biener 0 siblings, 1 reply; 18+ messages in thread From: Eric Botcazou @ 2014-05-26 10:24 UTC (permalink / raw) To: gcc-patches [-- Attachment #1: Type: text/plain, Size: 1967 bytes --] Hi, the motivation of this work is to get rid of the range check on Z in: function F (X : Integer; Y : Integer ) return Positive is Z : Integer; begin if X >= Y then return 1; end if; Z := Y - X; return Z; end; An equivalent C testcase is: extern void abort (void); int foo (int x, int y) { int z; if (x >= y) return 1; z = y - x; if (z <= 0) abort (); return z; } for which the call to abort is not optimized at -O2. fold_comparison knows how to optimize X +- C1 CMP C2 to X CMP C2 -+ C1 with undefined overflow so optimizing X - Y CMP 0 to X CMP Y is a generalization. Once this is done, forwprop will immediately optimize: extern void abort (void); int foo (int x, int y) { int z; if (x >= y) return 1; z = y - x; if (z <= 0) abort (); return 0; } because 'z' has a single use, but the original testcase won't be optimized. The attached patch implements the missing bits in vrp_evaluate_conditional by manual propagating the operands of a defining PLUS_EXPR or MINUS_EXPR for an SSA name in a condition; an other possibility could be DOM instead of VRP. This comes with 4 testcases: the original Ada testcase, the C equivalent, a testcase for the folding and another one for the -Wstrict-overflow warning. Tested on x86_64-suse-linux with no regressions. 2014-05-26 Eric Botcazou <ebotcazou@adacore.com> * fold-const.c (fold_comparison): Clean up and simplify X +- C1 CMP C2 to X CMP C2 -+ C1 transformation, add X - Y CMP 0 to X CMP Y. * tree-vrp.c (vrp_evaluate_conditional_warnv_with_fold): New function. (vrp_evaluate_conditional): Call it on SSA names with defining PLUS_EXPR or MINUS_EXPR if the evaluation of the condition yielded nothing. 2014-05-26 Eric Botcazou <ebotcazou@adacore.com> * gcc.dg/fold-compare-8.c: New test. * gcc.dg/Wstrict-overflow-25.c: Likewise. * gcc.dg/tree-ssa/vrp92.c: Likewise. * gnat.dg/opt38.adb: Likewise. -- Eric Botcazou [-- Attachment #2: p1.diff --] [-- Type: text/x-patch, Size: 7233 bytes --] Index: fold-const.c =================================================================== --- fold-const.c (revision 210911) +++ fold-const.c (working copy) @@ -8920,28 +8920,25 @@ 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); - /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 +- C1. */ + /* 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 - && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1)) - && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1))) - && (TREE_CODE (arg1) == INTEGER_CST - && !TREE_OVERFLOW (arg1))) + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)) + && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST + && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1)) + && TREE_CODE (arg1) == INTEGER_CST + && !TREE_OVERFLOW (arg1)) { + const enum tree_code + reverse_op = TREE_CODE (arg0) == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR; tree const1 = TREE_OPERAND (arg0, 1); tree const2 = arg1; tree variable = TREE_OPERAND (arg0, 0); - tree lhs; - int lhs_add; - lhs_add = TREE_CODE (arg0) != PLUS_EXPR; - - lhs = fold_build2_loc (loc, lhs_add ? PLUS_EXPR : MINUS_EXPR, - TREE_TYPE (arg1), const2, const1); + tree new_const + = fold_build2_loc (loc, reverse_op, TREE_TYPE (arg1), const2, const1); /* If the constant operation overflowed this can be simplified as a comparison against INT_MAX/INT_MIN. */ - if (TREE_CODE (lhs) == INTEGER_CST - && TREE_OVERFLOW (lhs)) + if (TREE_OVERFLOW (new_const)) { int const1_sgn = tree_int_cst_sgn (const1); enum tree_code code2 = code; @@ -8961,29 +8958,48 @@ fold_comparison (location_t loc, enum tr /* We now can look at the canonicalized case VARIABLE + 1 CODE2 INT_MIN and decide on the result. */ - if (code2 == LT_EXPR - || code2 == LE_EXPR - || code2 == EQ_EXPR) - return omit_one_operand_loc (loc, type, boolean_false_node, variable); - else if (code2 == NE_EXPR - || code2 == GE_EXPR - || code2 == GT_EXPR) - return omit_one_operand_loc (loc, type, boolean_true_node, variable); + switch (code2) + { + case EQ_EXPR: + case LT_EXPR: + case LE_EXPR: + return + omit_one_operand_loc (loc, type, boolean_false_node, variable); + + case NE_EXPR: + case GE_EXPR: + case GT_EXPR: + return + omit_one_operand_loc (loc, type, boolean_true_node, variable); + + default: + gcc_unreachable (); + } } - - if (TREE_CODE (lhs) == TREE_CODE (arg1) - && (TREE_CODE (lhs) != INTEGER_CST - || !TREE_OVERFLOW (lhs))) + else { if (code != EQ_EXPR && code != NE_EXPR) fold_overflow_warning ("assuming signed overflow does not occur " "when changing X +- C1 cmp C2 to " - "X cmp C1 +- C2", + "X cmp C2 -+ C1", WARN_STRICT_OVERFLOW_COMPARISON); - return fold_build2_loc (loc, code, type, variable, lhs); + return fold_build2_loc (loc, code, type, variable, new_const); } } + /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */ + if (TREE_CODE (arg0) == MINUS_EXPR + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)) + && integer_zerop (arg1)) + { + if (code != EQ_EXPR && code != NE_EXPR) + fold_overflow_warning ("assuming signed overflow does not occur " + "when changing X - Y cmp 0 to X cmp Y", + WARN_STRICT_OVERFLOW_COMPARISON); + return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), + TREE_OPERAND (arg0, 1)); + } + /* For comparisons of pointers we can decompose it to a compile time comparison of the base objects and the offsets into the object. This requires at least one operand being an ADDR_EXPR or a Index: tree-vrp.c =================================================================== --- tree-vrp.c (revision 210911) +++ tree-vrp.c (working copy) @@ -6966,6 +6966,46 @@ vrp_evaluate_conditional_warnv_with_ops return NULL_TREE; } +/* Helper function for vrp_evaluate_conditional_warnv. */ + +static tree +vrp_evaluate_conditional_warnv_with_fold (gimple stmt, enum tree_code code, + tree op0, tree op1, + bool use_equiv_p, + bool *strict_overflow_p, + bool *only_ranges) +{ + const location_t loc = gimple_location (stmt); + + fold_defer_overflow_warnings (); + + tree t = fold_binary_loc (loc, code, boolean_type_node, op0, op1); + if (!t + || !COMPARISON_CLASS_P (t) + || !is_gimple_val (TREE_OPERAND (t, 0)) + || !is_gimple_val (TREE_OPERAND (t, 1))) + { + fold_undefer_overflow_warnings (false, NULL, 0); + return NULL_TREE; + } + + tree ret = vrp_evaluate_conditional_warnv_with_ops (TREE_CODE (t), + TREE_OPERAND (t, 0), + TREE_OPERAND (t, 1), + use_equiv_p, + strict_overflow_p, + only_ranges); + if (!ret) + { + fold_undefer_overflow_warnings (false, NULL, 0); + return NULL_TREE; + } + + fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0); + + return ret; +} + /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range information. Return NULL if the conditional can not be evaluated. The ranges of all the names equivalent with the operands in COND @@ -6992,6 +7032,47 @@ vrp_evaluate_conditional (enum tree_code ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop, &only_ranges); + /* The propagation machinery doesn't handle symbolic ranges in conjunction + with PLUS_EXPR or MINUS_EXPR so we try to jump over them by propagating + their operands instead. */ + if (!ret + && TREE_CODE (op0) == SSA_NAME + && is_gimple_assign (SSA_NAME_DEF_STMT (op0))) + { + gimple def_stmt = SSA_NAME_DEF_STMT (op0); + enum tree_code def_code = gimple_assign_rhs_code (def_stmt); + if (def_code == PLUS_EXPR || def_code == MINUS_EXPR) + { + tree new_op0 = fold_build2_loc (gimple_location (def_stmt), + def_code, TREE_TYPE (op0), + gimple_assign_rhs1 (def_stmt), + gimple_assign_rhs2 (def_stmt)); + ret = vrp_evaluate_conditional_warnv_with_fold (stmt, code, + new_op0, op1, + true, &sop, + &only_ranges); + } + } + + if (!ret + && TREE_CODE (op1) == SSA_NAME + && is_gimple_assign (SSA_NAME_DEF_STMT (op1))) + { + gimple def_stmt = SSA_NAME_DEF_STMT (op1); + enum tree_code def_code = gimple_assign_rhs_code (def_stmt); + if (def_code == PLUS_EXPR || def_code == MINUS_EXPR) + { + tree new_op1 = fold_build2_loc (gimple_location (def_stmt), + def_code, TREE_TYPE (op1), + gimple_assign_rhs1 (def_stmt), + gimple_assign_rhs2 (def_stmt)); + ret = vrp_evaluate_conditional_warnv_with_fold (stmt, code, + op0, new_op1, + true, &sop, + &only_ranges); + } + } + if (ret && sop) { enum warn_strict_overflow_code wc; [-- Attachment #3: fold-compare-8.c --] [-- Type: text/x-csrc, Size: 229 bytes --] /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-original" } */ int foo (int x, int y) { return x - y < 0; } /* { dg-final { scan-tree-dump "x < y" "original" } } */ /* { dg-final { cleanup-tree-dump "original" } } */ [-- Attachment #4: Wstrict-overflow-25.c --] [-- Type: text/x-csrc, Size: 303 bytes --] /* { dg-do compile } */ /* { dg-options "-fstrict-overflow -O2 -Wstrict-overflow=3" } */ /* We can only simplify the conditional when using strict overflow semantics. */ int foo (int x, int y) { return x - y < 0; /* { dg-warning "assuming signed overflow does not occur" "correct warning" } */ } [-- Attachment #5: vrp92.c --] [-- Type: text/x-csrc, Size: 336 bytes --] /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ extern void abort (void); int foo (int x, int y) { int z; if (x >= y) return 1; z = y - x; if (z <= 0) abort (); return z; } /* { dg-final { scan-tree-dump-not "abort" "optimized" } } */ /* { dg-final { cleanup-tree-dump "optimized" } } */ [-- Attachment #6: opt38.adb --] [-- Type: text/x-adasrc, Size: 347 bytes --] -- { dg-do compile } -- { dg-options "-O2 -fdump-tree-optimized" } function Opt38 (X : Integer; Y : Integer ) return Positive is Z : Integer; begin if X >= Y then return 1; end if; Z := Y - X; return Z; end; -- { dg-final { scan-tree-dump-not "__gnat_rcheck" "optimized" } } -- { dg-final { cleanup-tree-dump "optimized" } } ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-05-26 10:24 [RFC] optimize x - y cmp 0 with undefined overflow Eric Botcazou @ 2014-05-26 12:55 ` Richard Biener 2014-05-27 9:26 ` Eric Botcazou 0 siblings, 1 reply; 18+ messages in thread From: Richard Biener @ 2014-05-26 12:55 UTC (permalink / raw) To: Eric Botcazou; +Cc: GCC Patches On Mon, May 26, 2014 at 12:22 PM, Eric Botcazou <ebotcazou@adacore.com> wrote: > Hi, > > the motivation of this work is to get rid of the range check on Z in: > > function F (X : Integer; Y : Integer ) return Positive is > Z : Integer; > begin > if X >= Y then > return 1; > end if; > Z := Y - X; > return Z; > end; > > An equivalent C testcase is: > > extern void abort (void); > > int foo (int x, int y) > { > int z; > > if (x >= y) > return 1; > > z = y - x; > if (z <= 0) > abort (); > > return z; > } > > for which the call to abort is not optimized at -O2. > > > fold_comparison knows how to optimize X +- C1 CMP C2 to X CMP C2 -+ C1 with > undefined overflow so optimizing X - Y CMP 0 to X CMP Y is a generalization. > > Once this is done, forwprop will immediately optimize: > > extern void abort (void); > > int foo (int x, int y) > { > int z; > > if (x >= y) > return 1; > > z = y - x; > if (z <= 0) > abort (); > > return 0; > } > > because 'z' has a single use, but the original testcase won't be optimized. > > > The attached patch implements the missing bits in vrp_evaluate_conditional by > manual propagating the operands of a defining PLUS_EXPR or MINUS_EXPR for an > SSA name in a condition; an other possibility could be DOM instead of VRP. > > This comes with 4 testcases: the original Ada testcase, the C equivalent, a > testcase for the folding and another one for the -Wstrict-overflow warning. > > Tested on x86_64-suse-linux with no regressions. + tree new_const + = fold_build2_loc (loc, reverse_op, TREE_TYPE (arg1), const2, const1); /* If the constant operation overflowed this can be simplified as a comparison against INT_MAX/INT_MIN. */ - if (TREE_CODE (lhs) == INTEGER_CST - && TREE_OVERFLOW (lhs)) + if (TREE_OVERFLOW (new_const)) well, either use int_const_binop above or retain the check (or use TREE_OVERFLOW_P). Bonus points for using wide-ints here and not relying on TREE_OVERFLOW. + /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */ + if (TREE_CODE (arg0) == MINUS_EXPR + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)) any good reason for using TYPE_OVERFLOW_UNDEFINED on the type of arg1 instead on the type of the MINUS (yes, they should match, but it really looks odd ... the overflow of the minus has to be undefined). Also for EQ_EXPR and NE_EXPR the transform is fine even when !TYPE_OVERFLOW_UNDEFINED (and we seem to perform it already somewhere). Please look where and try to add the undefined overflow case to it. As for the VRP pieces I don't understand what is missing here (well, compare_range_with_value and/or compare_values might not handle this case? then better fix that to improve symbolic range handling in general?). Also I have a longstanding patch in my tree that does Index: gcc/tree-vrp.c =================================================================== --- gcc/tree-vrp.c (revision 210931) +++ gcc/tree-vrp.c (working copy) @@ -6919,14 +6919,15 @@ vrp_evaluate_conditional_warnv_with_ops_ vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL; vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL; + tree res = NULL_TREE; if (vr0 && vr1) - return compare_ranges (code, vr0, vr1, strict_overflow_p); - else if (vr0 && vr1 == NULL) - return compare_range_with_value (code, vr0, op1, strict_overflow_p); - else if (vr0 == NULL && vr1) - return (compare_range_with_value + res = compare_ranges (code, vr0, vr1, strict_overflow_p); + if (!res && vr0) + res = compare_range_with_value (code, vr0, op1, strict_overflow_p); + if (!res && vr1) + res = (compare_range_with_value (swap_tree_comparison (code), vr1, op0, strict_overflow_p)); - return NULL; + return res; } /* Helper function for vrp_evaluate_conditional_warnv. */ maybe that helps as well. Thanks, Richard. > > 2014-05-26 Eric Botcazou <ebotcazou@adacore.com> > > * fold-const.c (fold_comparison): Clean up and simplify X +- C1 CMP C2 > to X CMP C2 -+ C1 transformation, add X - Y CMP 0 to X CMP Y. > * tree-vrp.c (vrp_evaluate_conditional_warnv_with_fold): New function. > (vrp_evaluate_conditional): Call it on SSA names with defining PLUS_EXPR > or MINUS_EXPR if the evaluation of the condition yielded nothing. > > > 2014-05-26 Eric Botcazou <ebotcazou@adacore.com> > > * gcc.dg/fold-compare-8.c: New test. > * gcc.dg/Wstrict-overflow-25.c: Likewise. > * gcc.dg/tree-ssa/vrp92.c: Likewise. > * gnat.dg/opt38.adb: Likewise. > > > -- > Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-05-26 12:55 ` Richard Biener @ 2014-05-27 9:26 ` Eric Botcazou 2014-05-27 9:42 ` Richard Biener 0 siblings, 1 reply; 18+ messages in thread From: Eric Botcazou @ 2014-05-27 9:26 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches > + tree new_const > + = fold_build2_loc (loc, reverse_op, TREE_TYPE (arg1), const2, > const1); > > /* If the constant operation overflowed this can be > simplified as a comparison against INT_MAX/INT_MIN. */ > - if (TREE_CODE (lhs) == INTEGER_CST > - && TREE_OVERFLOW (lhs)) > + if (TREE_OVERFLOW (new_const)) > > well, either use int_const_binop above or retain the check (or use > TREE_OVERFLOW_P). Bonus points for using wide-ints here > and not relying on TREE_OVERFLOW. The check is useless (you get either NULL_TREE or INTEGER_CST here) but I'll use int_const_binop. > + /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */ > + if (TREE_CODE (arg0) == MINUS_EXPR > + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)) > > any good reason for using TYPE_OVERFLOW_UNDEFINED on the > type of arg1 instead on the type of the MINUS (yes, they should > match, but it really looks odd ... the overflow of the minus has to be > undefined). For the sake of consistency with the X +- C1 CMP C2 case just above, but I can change both. > Also for EQ_EXPR and NE_EXPR the transform is > fine even when !TYPE_OVERFLOW_UNDEFINED (and we seem > to perform it already somewhere). Please look where and try to > add the undefined overflow case to it. Yes, but it's the same for the X +- C1 CMP C2 case, i.e. there are specific cases for X +- C1 EQ/NE C2 and X - Y EQ/NE 0 in fold_binary, so I'm not sure what you're asking. > As for the VRP pieces I don't understand what is missing here > (well, compare_range_with_value and/or compare_values might > not handle this case? then better fix that to improve symbolic > range handling in general?). Also I have a longstanding patch > in my tree that does Yes, there is an explicit non-handling of symbolic ranges for PLUS_EXPR and MINUS_EXPR in VRP (extract_range_from_binary_expr_1) and the patch works around it by propagating the code instead of the ranges, which is far easier and sufficient here. If you think that the way to go is to handle symbolic ranges for PLUS_EXPR and MINUS_EXPR instead, fine with me, I can try. -- Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-05-27 9:26 ` Eric Botcazou @ 2014-05-27 9:42 ` Richard Biener 2014-05-27 10:00 ` Eric Botcazou 2014-05-27 16:14 ` Eric Botcazou 0 siblings, 2 replies; 18+ messages in thread From: Richard Biener @ 2014-05-27 9:42 UTC (permalink / raw) To: Eric Botcazou; +Cc: GCC Patches On Tue, May 27, 2014 at 11:25 AM, Eric Botcazou <ebotcazou@adacore.com> wrote: >> + tree new_const >> + = fold_build2_loc (loc, reverse_op, TREE_TYPE (arg1), const2, >> const1); >> >> /* If the constant operation overflowed this can be >> simplified as a comparison against INT_MAX/INT_MIN. */ >> - if (TREE_CODE (lhs) == INTEGER_CST >> - && TREE_OVERFLOW (lhs)) >> + if (TREE_OVERFLOW (new_const)) >> >> well, either use int_const_binop above or retain the check (or use >> TREE_OVERFLOW_P). Bonus points for using wide-ints here >> and not relying on TREE_OVERFLOW. > > The check is useless (you get either NULL_TREE or INTEGER_CST here) but I'll > use int_const_binop. > >> + /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */ >> + if (TREE_CODE (arg0) == MINUS_EXPR >> + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)) >> >> any good reason for using TYPE_OVERFLOW_UNDEFINED on the >> type of arg1 instead on the type of the MINUS (yes, they should >> match, but it really looks odd ... the overflow of the minus has to be >> undefined). > > For the sake of consistency with the X +- C1 CMP C2 case just above, but I can > change both. > >> Also for EQ_EXPR and NE_EXPR the transform is >> fine even when !TYPE_OVERFLOW_UNDEFINED (and we seem >> to perform it already somewhere). Please look where and try to >> add the undefined overflow case to it. > > Yes, but it's the same for the X +- C1 CMP C2 case, i.e. there are specific > cases for X +- C1 EQ/NE C2 and X - Y EQ/NE 0 in fold_binary, so I'm not sure > what you're asking. I'm asking to merge them (move them to fold_comparison). >> As for the VRP pieces I don't understand what is missing here >> (well, compare_range_with_value and/or compare_values might >> not handle this case? then better fix that to improve symbolic >> range handling in general?). Also I have a longstanding patch >> in my tree that does > > Yes, there is an explicit non-handling of symbolic ranges for PLUS_EXPR and > MINUS_EXPR in VRP (extract_range_from_binary_expr_1) and the patch works > around it by propagating the code instead of the ranges, which is far easier > and sufficient here. If you think that the way to go is to handle symbolic > ranges for PLUS_EXPR and MINUS_EXPR instead, fine with me, I can try. Yeah, it would be nice to see some support. The most interesting cases will be symbolic-singleton +- CST where the offset shrinks a constant offset in a symbolic A +- CST (thus we don't get into any overflow issues). Thus handling [a + 1, a + 1] - [1, 1] -> [a, a] for example. We get the offsetted singleton symbolic ranges from conditional asserts a lot. Thanks, Richard. > -- > Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-05-27 9:42 ` Richard Biener @ 2014-05-27 10:00 ` Eric Botcazou 2014-05-27 10:12 ` Richard Biener 2014-05-27 16:14 ` Eric Botcazou 1 sibling, 1 reply; 18+ messages in thread From: Eric Botcazou @ 2014-05-27 10:00 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches > I'm asking to merge them (move them to fold_comparison). OK, I'll repost a first patch doing only the fold-const.c massaging. > Yeah, it would be nice to see some support. The most interesting cases > will be symbolic-singleton +- CST where the offset shrinks a constant offset > in a symbolic A +- CST (thus we don't get into any overflow issues). Thus > handling > > [a + 1, a + 1] - [1, 1] -> [a, a] > > for example. We get the offsetted singleton symbolic ranges from > conditional asserts a lot. For the case at hand, you have [x + 1, INF] for y and you want to evaluate the range of y - x, so you really don't want to use the range of x... -- Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-05-27 10:00 ` Eric Botcazou @ 2014-05-27 10:12 ` Richard Biener 2014-05-30 8:49 ` Eric Botcazou 0 siblings, 1 reply; 18+ messages in thread From: Richard Biener @ 2014-05-27 10:12 UTC (permalink / raw) To: Eric Botcazou; +Cc: GCC Patches On Tue, May 27, 2014 at 11:59 AM, Eric Botcazou <ebotcazou@adacore.com> wrote: >> I'm asking to merge them (move them to fold_comparison). > > OK, I'll repost a first patch doing only the fold-const.c massaging. > >> Yeah, it would be nice to see some support. The most interesting cases >> will be symbolic-singleton +- CST where the offset shrinks a constant offset >> in a symbolic A +- CST (thus we don't get into any overflow issues). Thus >> handling >> >> [a + 1, a + 1] - [1, 1] -> [a, a] >> >> for example. We get the offsetted singleton symbolic ranges from >> conditional asserts a lot. > > For the case at hand, you have [x + 1, INF] for y and you want to evaluate the > range of y - x, so you really don't want to use the range of x... Ok. That's similar to the issue I try to address with the VRP snipped I posted yesterday. I'd say we still handle "basic" symbolic range ops in extract_range_from_binary_1 but in extract_range_from_binary_expr for a symbolic op0 we try to simplify it with both [op1, op1] and with the value-range of op1 until we get a non-varying range as result. Not sure if it's worth restricting that to the case where op0s value-range refers to op1 or vice versa, and eventually only use op1 symbolically then. Richard. > -- > Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-05-27 10:12 ` Richard Biener @ 2014-05-30 8:49 ` Eric Botcazou 2014-06-02 10:36 ` Richard Biener 0 siblings, 1 reply; 18+ messages in thread From: Eric Botcazou @ 2014-05-30 8:49 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 1208 bytes --] > I'd say we still handle "basic" symbolic range ops in > extract_range_from_binary_1 > but in extract_range_from_binary_expr for a symbolic op0 we try to simplify > it with both [op1, op1] and with the value-range of op1 until we get a > non-varying range as result. Not sure if it's worth restricting that > to the case > where op0s value-range refers to op1 or vice versa, and eventually only > use op1 symbolically then. Patch along these lines attached. A bit heavy as expected, but it's VRP... It deals with my pet problem, you might want to check it does so with yours. Tested on x86_64-suse-linux with no regressions. 2014-05-30 Eric Botcazou <ebotcazou@adacore.com> * tree-vrp.c (get_single_symbol): New function. (build_symbolic_expr): Likewise. (symbolic_range_based_on_p): New predicate. (extract_range_from_binary_expr_1): Deal with single-symbolic ranges for PLUS and MINUS. Do not drop symbolic ranges at the end. (extract_range_from_binary_expr): Try harder for PLUS and MINUS if operand is symbolic and based on the other operand. 2014-05-30 Eric Botcazou <ebotcazou@adacore.com> * gcc.dg/tree-ssa/vrp93.c: New test. * gnat.dg/opt38.adb: Likewise. -- Eric Botcazou [-- Attachment #2: vrp_symbolic.diff --] [-- Type: text/x-patch, Size: 14750 bytes --] Index: tree-vrp.c =================================================================== --- tree-vrp.c (revision 211019) +++ tree-vrp.c (working copy) @@ -916,6 +916,93 @@ symbolic_range_p (value_range_t *vr) || !is_gimple_min_invariant (vr->max)); } +/* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE + otherwise. We only handle additive operations and set NEG to true if the + symbol is negated and INV to the invariant part, if any. */ + +static tree +get_single_symbol (tree t, bool *neg, tree *inv) +{ + if (TREE_CODE (t) == PLUS_EXPR + || TREE_CODE (t) == POINTER_PLUS_EXPR + || TREE_CODE (t) == MINUS_EXPR) + { + if (is_gimple_min_invariant (TREE_OPERAND (t, 0))) + { + *inv = TREE_OPERAND (t, 0); + *neg = (TREE_CODE (t) == MINUS_EXPR); + t = TREE_OPERAND (t, 1); + } + else if (is_gimple_min_invariant (TREE_OPERAND (t, 1))) + { + *inv = TREE_OPERAND (t, 1); + *neg = false; + t = TREE_OPERAND (t, 0); + } + else + return NULL_TREE; + } + else + { + *inv = NULL_TREE; + *neg = false; + } + + if (TREE_CODE (t) == NEGATE_EXPR) + { + t = TREE_OPERAND (t, 0); + *neg = true; + } + + if (TREE_CODE (t) != SSA_NAME) + return NULL_TREE; + + return t; +} + +/* The reverse operation: build a symbolic expression with TYPE + from symbol SYM, negated according to NEG, and invariant INV. */ + +static tree +build_symbolic_expr (tree type, tree sym, bool neg, tree inv) +{ + const bool pointer_p = POINTER_TYPE_P (type); + tree t = sym; + + if (neg) + t = build1 (NEGATE_EXPR, type, t); + + if (integer_zerop (inv)) + return t; + + return build2 (pointer_p ? POINTER_PLUS_EXPR : PLUS_EXPR, type, t, inv); +} + +/* Return true if value range VR involves exactly one symbol SYM. */ + +static bool +symbolic_range_based_on_p (value_range_t *vr, const_tree sym) +{ + bool neg, min_has_symbol, max_has_symbol; + tree inv; + + if (is_gimple_min_invariant (vr->min)) + min_has_symbol = false; + else if (get_single_symbol (vr->min, &neg, &inv) == sym) + min_has_symbol = true; + else + return false; + + if (is_gimple_min_invariant (vr->max)) + max_has_symbol = false; + else if (get_single_symbol (vr->max, &neg, &inv) == sym) + max_has_symbol = true; + else + return false; + + return (min_has_symbol || max_has_symbol); +} + /* Return true if value range VR uses an overflow infinity. */ static inline bool @@ -2209,7 +2296,7 @@ extract_range_from_multiplicative_op_1 ( } /* Extract range information from a binary operation CODE based on - the ranges of each of its operands, *VR0 and *VR1 with resulting + the ranges of each of its operands *VR0 and *VR1 with resulting type EXPR_TYPE. The resulting range is stored in *VR. */ static void @@ -2303,11 +2390,12 @@ extract_range_from_binary_expr_1 (value_ type = vr0.type; /* Refuse to operate on VARYING ranges, ranges of different kinds - and symbolic ranges. As an exception, we allow BIT_AND_EXPR + and symbolic ranges. As an exception, we allow BIT_{AND,IOR} because we may be able to derive a useful range even if one of the operands is VR_VARYING or symbolic range. Similarly for - divisions. TODO, we may be able to derive anti-ranges in - some cases. */ + divisions, MIN/MAX and PLUS/MINUS. + + TODO, we may be able to derive anti-ranges in some cases. */ if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR && code != TRUNC_DIV_EXPR @@ -2318,6 +2406,8 @@ extract_range_from_binary_expr_1 (value_ && code != TRUNC_MOD_EXPR && code != MIN_EXPR && code != MAX_EXPR + && code != PLUS_EXPR + && code != MINUS_EXPR && (vr0.type == VR_VARYING || vr1.type == VR_VARYING || vr0.type != vr1.type @@ -2376,50 +2466,115 @@ extract_range_from_binary_expr_1 (value_ range and see what we end up with. */ if (code == PLUS_EXPR || code == MINUS_EXPR) { - /* If we have a PLUS_EXPR with two VR_RANGE integer constant - ranges compute the precise range for such case if possible. */ - if (range_int_cst_p (&vr0) - && range_int_cst_p (&vr1)) - { - signop sgn = TYPE_SIGN (expr_type); - unsigned int prec = TYPE_PRECISION (expr_type); - wide_int type_min = wi::min_value (TYPE_PRECISION (expr_type), sgn); - wide_int type_max = wi::max_value (TYPE_PRECISION (expr_type), sgn); - wide_int wmin, wmax; + const bool minus_p = (code == MINUS_EXPR); + tree min_op0 = vr0.min; + tree min_op1 = minus_p ? vr1.max : vr1.min; + tree max_op0 = vr0.max; + tree max_op1 = minus_p ? vr1.min : vr1.max; + tree sym_min_op0 = NULL_TREE; + tree sym_min_op1 = NULL_TREE; + tree sym_max_op0 = NULL_TREE; + tree sym_max_op1 = NULL_TREE; + bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1; + + /* If we have a PLUS or MINUS with two VR_RANGEs, either constant or + single-symbolic ranges, try to compute the precise resulting range, + but only if we know that this resulting range will also be constant + or single-symbolic. */ + if (vr0.type == VR_RANGE && vr1.type == VR_RANGE + && (TREE_CODE (min_op0) == INTEGER_CST + || (sym_min_op0 + = get_single_symbol (min_op0, &neg_min_op0, &min_op0))) + && (TREE_CODE (min_op1) == INTEGER_CST + || (sym_min_op1 + = get_single_symbol (min_op1, &neg_min_op1, &min_op1))) + && (!(sym_min_op0 && sym_min_op1) + || (sym_min_op0 == sym_min_op1 + && neg_min_op0 == (minus_p ? neg_min_op1 : !neg_min_op1))) + && (TREE_CODE (max_op0) == INTEGER_CST + || (sym_max_op0 + = get_single_symbol (max_op0, &neg_max_op0, &max_op0))) + && (TREE_CODE (max_op1) == INTEGER_CST + || (sym_max_op1 + = get_single_symbol (max_op1, &neg_max_op1, &max_op1))) + && (!(sym_max_op0 && sym_max_op1) + || (sym_max_op0 == sym_max_op1 + && neg_max_op0 == (minus_p ? neg_max_op1 : !neg_max_op1)))) + { + const signop sgn = TYPE_SIGN (expr_type); + const unsigned int prec = TYPE_PRECISION (expr_type); + wide_int type_min, type_max, wmin, wmax; int min_ovf = 0; int max_ovf = 0; - if (code == PLUS_EXPR) + /* Get the lower and upper bounds of the type. */ + if (TYPE_OVERFLOW_WRAPS (expr_type)) { - wmin = wi::add (vr0.min, vr1.min); - wmax = wi::add (vr0.max, vr1.max); - - /* Check for overflow. */ - if (wi::cmp (vr1.min, 0, sgn) != wi::cmp (wmin, vr0.min, sgn)) - min_ovf = wi::cmp (vr0.min, wmin, sgn); - if (wi::cmp (vr1.max, 0, sgn) != wi::cmp (wmax, vr0.max, sgn)) - max_ovf = wi::cmp (vr0.max, wmax, sgn); + type_min = wi::min_value (prec, sgn); + type_max = wi::max_value (prec, sgn); } - else /* if (code == MINUS_EXPR) */ + else { - wmin = wi::sub (vr0.min, vr1.max); - wmax = wi::sub (vr0.max, vr1.min); + type_min = vrp_val_min (expr_type); + type_max = vrp_val_max (expr_type); + } - if (wi::cmp (0, vr1.max, sgn) != wi::cmp (wmin, vr0.min, sgn)) - min_ovf = wi::cmp (vr0.min, vr1.max, sgn); - if (wi::cmp (0, vr1.min, sgn) != wi::cmp (wmax, vr0.max, sgn)) - max_ovf = wi::cmp (vr0.max, vr1.min, sgn); + /* Combine the lower bounds, if any. */ + if (min_op0 && min_op1) + { + if (minus_p) + { + wmin = wi::sub (min_op0, min_op1); + + /* Check for overflow. */ + if (wi::cmp (0, min_op1, sgn) + != wi::cmp (wmin, min_op0, sgn)) + min_ovf = wi::cmp (min_op0, min_op1, sgn); + } + else + { + wmin = wi::add (min_op0, min_op1); + + /* Check for overflow. */ + if (wi::cmp (min_op1, 0, sgn) + != wi::cmp (wmin, min_op0, sgn)) + min_ovf = wi::cmp (min_op0, wmin, sgn); + } } + else if (min_op0) + wmin = min_op0; + else if (min_op1) + wmin = minus_p ? wi::neg (min_op1) : min_op1; + else + wmin = wi::shwi (0, prec); - /* For non-wrapping arithmetic look at possibly smaller - value-ranges of the type. */ - if (!TYPE_OVERFLOW_WRAPS (expr_type)) + /* Combine the upper bounds, if any. */ + if (max_op0 && max_op1) { - if (vrp_val_min (expr_type)) - type_min = vrp_val_min (expr_type); - if (vrp_val_max (expr_type)) - type_max = vrp_val_max (expr_type); + if (minus_p) + { + wmax = wi::sub (max_op0, max_op1); + + /* Check for overflow. */ + if (wi::cmp (0, max_op1, sgn) + != wi::cmp (wmax, max_op0, sgn)) + max_ovf = wi::cmp (max_op0, max_op1, sgn); + } + else + { + wmax = wi::add (max_op0, max_op1); + + if (wi::cmp (max_op1, 0, sgn) + != wi::cmp (wmax, max_op0, sgn)) + max_ovf = wi::cmp (max_op0, wmax, sgn); + } } + else if (max_op0) + wmax = max_op0; + else if (max_op1) + wmax = minus_p ? wi::neg (max_op1) : max_op1; + else + wmax = wi::shwi (0, prec); /* Check for type overflow. */ if (min_ovf == 0) @@ -2437,6 +2592,15 @@ extract_range_from_binary_expr_1 (value_ max_ovf = 1; } + /* If we have overflow for the constant part and the resulting + range will be symbolic, drop to VR_VARYING. */ + if ((min_ovf && sym_min_op0 != sym_min_op1) + || (max_ovf && sym_max_op0 != sym_max_op1)) + { + set_value_range_to_varying (vr); + return; + } + if (TYPE_OVERFLOW_WRAPS (expr_type)) { /* If overflow wraps, truncate the values and adjust the @@ -2450,8 +2614,7 @@ extract_range_from_binary_expr_1 (value_ min = wide_int_to_tree (expr_type, tmin); max = wide_int_to_tree (expr_type, tmax); } - else if (min_ovf == -1 - && max_ovf == 1) + else if (min_ovf == -1 && max_ovf == 1) { /* Underflow and overflow, drop to VR_VARYING. */ set_value_range_to_varying (vr); @@ -2526,20 +2689,44 @@ extract_range_from_binary_expr_1 (value_ else max = wide_int_to_tree (expr_type, wmax); } + if (needs_overflow_infinity (expr_type) && supports_overflow_infinity (expr_type)) { - if (is_negative_overflow_infinity (vr0.min) - || (code == PLUS_EXPR - ? is_negative_overflow_infinity (vr1.min) - : is_positive_overflow_infinity (vr1.max))) + if ((min_op0 && is_negative_overflow_infinity (min_op0)) + || (min_op1 + && (minus_p + ? is_positive_overflow_infinity (min_op1) + : is_negative_overflow_infinity (min_op1)))) min = negative_overflow_infinity (expr_type); - if (is_positive_overflow_infinity (vr0.max) - || (code == PLUS_EXPR - ? is_positive_overflow_infinity (vr1.max) - : is_negative_overflow_infinity (vr1.min))) + if ((max_op0 && is_positive_overflow_infinity (max_op0)) + || (max_op1 + && (minus_p + ? is_negative_overflow_infinity (max_op1) + : is_positive_overflow_infinity (max_op1)))) max = positive_overflow_infinity (expr_type); } + + /* If the result lower bound is constant, we're done; + otherwise, build the symbolic lower bound. */ + if (sym_min_op0 == sym_min_op1) + ; + else if (sym_min_op0) + min = build_symbolic_expr (expr_type, sym_min_op0, + neg_min_op0, min); + else if (sym_min_op1) + min = build_symbolic_expr (expr_type, sym_min_op1, + neg_min_op1 ^ minus_p, min); + + /* Likewise for the upper bound. */ + if (sym_max_op0 == sym_max_op1) + ; + else if (sym_max_op0) + max = build_symbolic_expr (expr_type, sym_max_op0, + neg_max_op0, max); + else if (sym_max_op1) + max = build_symbolic_expr (expr_type, sym_max_op1, + neg_max_op1 ^ minus_p, max); } else { @@ -3024,14 +3211,11 @@ extract_range_from_binary_expr_1 (value_ gcc_unreachable (); /* If either MIN or MAX overflowed, then set the resulting range to - VARYING. But we do accept an overflow infinity - representation. */ + VARYING. But we do accept an overflow infinity representation. */ if (min == NULL_TREE - || !is_gimple_min_invariant (min) - || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) + || (TREE_OVERFLOW_P (min) && !is_overflow_infinity (min)) || max == NULL_TREE - || !is_gimple_min_invariant (max) - || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) + || (TREE_OVERFLOW_P (max) && !is_overflow_infinity (max))) { set_value_range_to_varying (vr); return; @@ -3093,6 +3277,58 @@ extract_range_from_binary_expr (value_ra set_value_range_to_varying (&vr1); extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1); + + /* Try harder for PLUS and MINUS if the range of one operand is symbolic + and based on the other operand. */ + if (vr->type == VR_VARYING + && (code == PLUS_EXPR || code == MINUS_EXPR) + && TREE_CODE (op1) == SSA_NAME + && vr0.type == VR_RANGE + && symbolic_range_based_on_p (&vr0, op1)) + { + value_range_t new_vr1 = VR_INITIALIZER; + + /* Try with VR0 and [-INF, OP1]. */ + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); + if (vr->type != VR_VARYING) + return; + + /* Try with VR0 and [OP1, +INF]. */ + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); + if (vr->type != VR_VARYING) + return; + + /* Try with VR0 and [OP1, OP1]. */ + set_value_range (&new_vr1, VR_RANGE, op1, op1, NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); + } + + if (vr->type == VR_VARYING + && (code == PLUS_EXPR || code == MINUS_EXPR) + && TREE_CODE (op0) == SSA_NAME + && vr1.type == VR_RANGE + && symbolic_range_based_on_p (&vr1, op0)) + { + value_range_t new_vr0 = VR_INITIALIZER; + + /* Try with [-INF, OP0] and VR1. */ + set_value_range (&new_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &new_vr0, &vr1); + if (vr->type != VR_VARYING) + return; + + /* Try with [OP0, +INF] and VR1. */ + set_value_range (&new_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &new_vr0, &vr1); + if (vr->type != VR_VARYING) + return; + + /* Try with [OP0, OP0] and VR1. */ + set_value_range (&new_vr0, VR_RANGE, op0, op0, NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &new_vr0, &vr1); + } } /* Extract range information from a unary operation CODE based on ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-05-30 8:49 ` Eric Botcazou @ 2014-06-02 10:36 ` Richard Biener 2014-06-02 10:37 ` Richard Biener 2014-06-03 8:13 ` Eric Botcazou 0 siblings, 2 replies; 18+ messages in thread From: Richard Biener @ 2014-06-02 10:36 UTC (permalink / raw) To: Eric Botcazou; +Cc: GCC Patches On Fri, May 30, 2014 at 10:48 AM, Eric Botcazou <ebotcazou@adacore.com> wrote: >> I'd say we still handle "basic" symbolic range ops in >> extract_range_from_binary_1 >> but in extract_range_from_binary_expr for a symbolic op0 we try to simplify >> it with both [op1, op1] and with the value-range of op1 until we get a >> non-varying range as result. Not sure if it's worth restricting that >> to the case >> where op0s value-range refers to op1 or vice versa, and eventually only >> use op1 symbolically then. > > Patch along these lines attached. A bit heavy as expected, but it's VRP... > It deals with my pet problem, you might want to check it does so with yours. > > Tested on x86_64-suse-linux with no regressions. Looks mostly ok. Any reason why you are not re-creating MINUS_EXPR in build_symbolic_expr? That is, build inv - t (for non-pointers, of course)? Otherwise if a range becomes -t + inv that will no longer match get_single_symbol for further propagation? Then I'm not sure if + /* Try with VR0 and [-INF, OP1]. */ + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); + if (vr->type != VR_VARYING) + return; + + /* Try with VR0 and [OP1, +INF]. */ + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); + if (vr->type != VR_VARYING) + return; is a safe thing to do. If it does make a difference to try [-INF, OP1], [OP1, +INF] instead of just [OP1, OP1] then at least it's very suspicious ;) (or an "easy" missed optimization). So - can you fix the negate thing and drop the four cases trying the +-INF based ranges? Thanks, Richard. > > 2014-05-30 Eric Botcazou <ebotcazou@adacore.com> > > * tree-vrp.c (get_single_symbol): New function. > (build_symbolic_expr): Likewise. > (symbolic_range_based_on_p): New predicate. > (extract_range_from_binary_expr_1): Deal with single-symbolic ranges > for PLUS and MINUS. Do not drop symbolic ranges at the end. > (extract_range_from_binary_expr): Try harder for PLUS and MINUS if > operand is symbolic and based on the other operand. > > > 2014-05-30 Eric Botcazou <ebotcazou@adacore.com> > > * gcc.dg/tree-ssa/vrp93.c: New test. > * gnat.dg/opt38.adb: Likewise. > > > -- > Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-06-02 10:36 ` Richard Biener @ 2014-06-02 10:37 ` Richard Biener 2014-06-03 8:13 ` Eric Botcazou 1 sibling, 0 replies; 18+ messages in thread From: Richard Biener @ 2014-06-02 10:37 UTC (permalink / raw) To: Eric Botcazou; +Cc: GCC Patches On Mon, Jun 2, 2014 at 12:36 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Fri, May 30, 2014 at 10:48 AM, Eric Botcazou <ebotcazou@adacore.com> wrote: >>> I'd say we still handle "basic" symbolic range ops in >>> extract_range_from_binary_1 >>> but in extract_range_from_binary_expr for a symbolic op0 we try to simplify >>> it with both [op1, op1] and with the value-range of op1 until we get a >>> non-varying range as result. Not sure if it's worth restricting that >>> to the case >>> where op0s value-range refers to op1 or vice versa, and eventually only >>> use op1 symbolically then. >> >> Patch along these lines attached. A bit heavy as expected, but it's VRP... >> It deals with my pet problem, you might want to check it does so with yours. >> >> Tested on x86_64-suse-linux with no regressions. > > Looks mostly ok. Any reason why you are not re-creating > MINUS_EXPR in build_symbolic_expr? That is, build > inv - t (for non-pointers, of course)? Otherwise if a range > becomes -t + inv that will no longer match get_single_symbol > for further propagation? > > Then I'm not sure if > > + /* Try with VR0 and [-INF, OP1]. */ > + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL); > + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); > + if (vr->type != VR_VARYING) > + return; > + > + /* Try with VR0 and [OP1, +INF]. */ > + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL); > + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); > + if (vr->type != VR_VARYING) > + return; > > is a safe thing to do. If it does make a difference to try [-INF, OP1], > [OP1, +INF] instead of just [OP1, OP1] then at least it's very suspicious ;) > (or an "easy" missed optimization). > > So - can you fix the negate thing and drop the four cases trying > the +-INF based ranges? Btw, the testcases are missing in the patch so I can't have a look myself. Richard. > Thanks, > Richard. > >> >> 2014-05-30 Eric Botcazou <ebotcazou@adacore.com> >> >> * tree-vrp.c (get_single_symbol): New function. >> (build_symbolic_expr): Likewise. >> (symbolic_range_based_on_p): New predicate. >> (extract_range_from_binary_expr_1): Deal with single-symbolic ranges >> for PLUS and MINUS. Do not drop symbolic ranges at the end. >> (extract_range_from_binary_expr): Try harder for PLUS and MINUS if >> operand is symbolic and based on the other operand. >> >> >> 2014-05-30 Eric Botcazou <ebotcazou@adacore.com> >> >> * gcc.dg/tree-ssa/vrp93.c: New test. >> * gnat.dg/opt38.adb: Likewise. >> >> >> -- >> Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-06-02 10:36 ` Richard Biener 2014-06-02 10:37 ` Richard Biener @ 2014-06-03 8:13 ` Eric Botcazou 2014-06-03 11:00 ` Richard Biener 1 sibling, 1 reply; 18+ messages in thread From: Eric Botcazou @ 2014-06-03 8:13 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 3699 bytes --] > Looks mostly ok. Any reason why you are not re-creating > MINUS_EXPR in build_symbolic_expr? That is, build > inv - t (for non-pointers, of course)? It's more uniform and compare_values expects an INTEGER_CST on the RHS, although the patch was lacking a small tweak to the function: @@ -1205,19 +1292,23 @@ compare_values_warnv (tree val1, tree va STRIP_USELESS_TYPE_CONVERSION (val2); if ((TREE_CODE (val1) == SSA_NAME + || (TREE_CODE (val1) == NEGATE_EXPR + && TREE_CODE (TREE_OPERAND (val1, 0)) == SSA_NAME) || TREE_CODE (val1) == PLUS_EXPR || TREE_CODE (val1) == MINUS_EXPR) && (TREE_CODE (val2) == SSA_NAME + || (TREE_CODE (val2) == NEGATE_EXPR + && TREE_CODE (TREE_OPERAND (val2, 0)) == SSA_NAME) || TREE_CODE (val2) == PLUS_EXPR || TREE_CODE (val2) == MINUS_EXPR)) { tree n1, c1, n2, c2; enum tree_code code1, code2; - /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', + /* If VAL1 and VAL2 are of the form '[-]NAME [+-] CST' or 'NAME', return -1 or +1 accordingly. If VAL1 and VAL2 don't use the same name, return -2. */ - if (TREE_CODE (val1) == SSA_NAME) + if (TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == NEGATE_EXPR) { code1 = SSA_NAME; n1 = val1; @@ -1239,7 +1330,7 @@ compare_values_warnv (tree val1, tree va } } - if (TREE_CODE (val2) == SSA_NAME) + if (TREE_CODE (val2) == SSA_NAME || TREE_CODE (val2) == NEGATE_EXPR) { code2 = SSA_NAME; n2 = val2; @@ -1262,6 +1353,11 @@ compare_values_warnv (tree val1, tree va } /* Both values must use the same name. */ + if (TREE_CODE (n1) == NEGATE_EXPR && TREE_CODE (n2) == NEGATE_EXPR) + { + n1 = TREE_OPERAND (n1, 0); + n2 = TREE_OPERAND (n2, 0); + } if (n1 != n2) return -2; > Otherwise if a range becomes -t + inv that will no longer match > get_single_symbol for further propagation? Yes, it will, NEGATE_EXPR is handled by get_single_symbol. > Then I'm not sure if > > + /* Try with VR0 and [-INF, OP1]. */ > + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1, > NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, > &new_vr1); + if (vr->type != VR_VARYING) > + return; > + > + /* Try with VR0 and [OP1, +INF]. */ > + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type), > NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, > &new_vr1); + if (vr->type != VR_VARYING) > + return; > > is a safe thing to do. If it does make a difference to try [-INF, OP1], > [OP1, +INF] instead of just [OP1, OP1] then at least it's very suspicious ;) > (or an "easy" missed optimization). Yes, it makes a difference and is required to eliminate half-symbolic ranges (the ones deduced from x >= y). Otherwise extract_range_from_binary_expr_1 will reject the resulting range because it cannot compare the bounds. As discussed, extract_range_from_binary_expr_1 doesn't do any fiddling with the input ranges, it just computes the resulting range and see whether it can interpret it. Half-symbolic ranges cannot be interpreted and probably should not, in the general case at least, because I think it can be very delicate, so extract_range_from_binary_expr will just try all the possible combinations for PLUS and MINUS. The testcases were attached to the first message in the thread, but I presume that decent mail programs are a thing of the past. :-) Attached again. -- Eric Botcazou [-- Attachment #2: opt38.adb --] [-- Type: text/x-adasrc, Size: 345 bytes --] -- { dg-do compile } -- { dg-options "-O2 -fdump-tree-optimized" } function Opt38 (X : Integer; Y : Integer ) return Positive is Z : Integer; begin if X >= Y then return 1; end if; Z := Y - X; return Z; end; -- { dg-final { scan-tree-dump-not "gnat_rcheck" "optimized" } } -- { dg-final { cleanup-tree-dump "optimized" } } [-- Attachment #3: vrp93.c --] [-- Type: text/x-csrc, Size: 495 bytes --] /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ extern void abort (void); int foo1 (int x, int y) { int z; if (x >= y) return 1; z = y - x; if (z <= 0) abort (); return z; } unsigned int foo2 (unsigned int x, unsigned int y) { unsigned int z; if (x >= y) return 1; z = y - x; if (z == 0) abort (); return z; } /* { dg-final { scan-tree-dump-not "abort" "optimized" } } */ /* { dg-final { cleanup-tree-dump "optimized" } } */ ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-06-03 8:13 ` Eric Botcazou @ 2014-06-03 11:00 ` Richard Biener 2014-06-06 10:54 ` Eric Botcazou 0 siblings, 1 reply; 18+ messages in thread From: Richard Biener @ 2014-06-03 11:00 UTC (permalink / raw) To: Eric Botcazou; +Cc: GCC Patches On Tue, Jun 3, 2014 at 10:11 AM, Eric Botcazou <ebotcazou@adacore.com> wrote: >> Looks mostly ok. Any reason why you are not re-creating >> MINUS_EXPR in build_symbolic_expr? That is, build >> inv - t (for non-pointers, of course)? > > It's more uniform and compare_values expects an INTEGER_CST on the RHS, > although the patch was lacking a small tweak to the function: > > @@ -1205,19 +1292,23 @@ compare_values_warnv (tree val1, tree va > STRIP_USELESS_TYPE_CONVERSION (val2); > > if ((TREE_CODE (val1) == SSA_NAME > + || (TREE_CODE (val1) == NEGATE_EXPR > + && TREE_CODE (TREE_OPERAND (val1, 0)) == SSA_NAME) > || TREE_CODE (val1) == PLUS_EXPR > || TREE_CODE (val1) == MINUS_EXPR) > && (TREE_CODE (val2) == SSA_NAME > + || (TREE_CODE (val2) == NEGATE_EXPR > + && TREE_CODE (TREE_OPERAND (val2, 0)) == SSA_NAME) > || TREE_CODE (val2) == PLUS_EXPR > || TREE_CODE (val2) == MINUS_EXPR)) > { > tree n1, c1, n2, c2; > enum tree_code code1, code2; > > - /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', > + /* If VAL1 and VAL2 are of the form '[-]NAME [+-] CST' or 'NAME', > return -1 or +1 accordingly. If VAL1 and VAL2 don't use the > same name, return -2. */ > - if (TREE_CODE (val1) == SSA_NAME) > + if (TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == NEGATE_EXPR) > { > code1 = SSA_NAME; > n1 = val1; > @@ -1239,7 +1330,7 @@ compare_values_warnv (tree val1, tree va > } > } > > - if (TREE_CODE (val2) == SSA_NAME) > + if (TREE_CODE (val2) == SSA_NAME || TREE_CODE (val2) == NEGATE_EXPR) > { > code2 = SSA_NAME; > n2 = val2; > @@ -1262,6 +1353,11 @@ compare_values_warnv (tree val1, tree va > } > > /* Both values must use the same name. */ > + if (TREE_CODE (n1) == NEGATE_EXPR && TREE_CODE (n2) == NEGATE_EXPR) > + { > + n1 = TREE_OPERAND (n1, 0); > + n2 = TREE_OPERAND (n2, 0); > + } > if (n1 != n2) > return -2; Ah, ok - makes sense. >> Otherwise if a range becomes -t + inv that will no longer match >> get_single_symbol for further propagation? > > Yes, it will, NEGATE_EXPR is handled by get_single_symbol. Now spotted. >> Then I'm not sure if >> >> + /* Try with VR0 and [-INF, OP1]. */ >> + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1, >> NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, >> &new_vr1); + if (vr->type != VR_VARYING) >> + return; >> + >> + /* Try with VR0 and [OP1, +INF]. */ >> + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type), >> NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, >> &new_vr1); + if (vr->type != VR_VARYING) >> + return; >> >> is a safe thing to do. If it does make a difference to try [-INF, OP1], >> [OP1, +INF] instead of just [OP1, OP1] then at least it's very suspicious ;) >> (or an "easy" missed optimization). > > Yes, it makes a difference and is required to eliminate half-symbolic ranges > (the ones deduced from x >= y). Otherwise extract_range_from_binary_expr_1 > will reject the resulting range because it cannot compare the bounds. > > As discussed, extract_range_from_binary_expr_1 doesn't do any fiddling with > the input ranges, it just computes the resulting range and see whether it can > interpret it. Half-symbolic ranges cannot be interpreted and probably should > not, in the general case at least, because I think it can be very delicate, so > extract_range_from_binary_expr will just try all the possible combinations for > PLUS and MINUS. So when computing a range for z in z = y - x; with x = [-INF, y - 1] and y = [x + 1, +INF] (deduced from !(x >= y)) we fail to do sth sensible with [y, y] - [-INF, y - 1] or [x + 1, +INF] - [x, x] but we do sth with [x + 1, +INF] - [-INF, x]? That seems odd to me. With the patch we compute z to [1, +INF(OVF)] Going the [x + 1, +INF] - [x,x] path first we obtain [1, -x + INF] which fails the sanity checking cmp = compare_values (min, max); if (cmp == -2 || cmp == 1) { /* If the new range has its limits swapped around (MIN > MAX), then the operation caused one of them to wrap around, mark the new range VARYING. */ set_value_range_to_varying (vr); } else set_value_range (vr, type, min, max, NULL); but clearly the same reasoning you can apply that makes trying with [-INF, x] valid (it's just enlarging the range) can be applied here, too, when computing +INF - x for the upper bound. We can safely increase that to +INF making the range valid for the above test. But I wonder what code path in the routine still relies on that sanity checking to produce a valid result (so I'd rather try removing it, or taking uncomparable bounds as a valid range). Simplest would be to simply do set_value_range (vr, type, min, max, NULL); return; and be done with that in the plus/minus handling. With that the testcase optimizes ok for me. I'd say ok with that change and only trying [op0,op0] and [op1,op1]. Thanks, Richard. > > The testcases were attached to the first message in the thread, but I presume > that decent mail programs are a thing of the past. :-) Attached again. Heh ;) > -- > Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-06-03 11:00 ` Richard Biener @ 2014-06-06 10:54 ` Eric Botcazou 2014-06-06 15:45 ` Richard Biener 0 siblings, 1 reply; 18+ messages in thread From: Eric Botcazou @ 2014-06-06 10:54 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches > So when computing a range for z in > > z = y - x; > > with x = [-INF, y - 1] and y = [x + 1, +INF] (deduced from !(x >= y)) we > fail to do sth sensible with [y, y] - [-INF, y - 1] or [x + 1, +INF] - [x, > x] but we do sth with [x + 1, +INF] - [-INF, x]? That seems odd to me. > > With the patch we compute z to [1, +INF(OVF)] Right, and note the overflow. > Going the [x + 1, +INF] - [x,x] path first we obtain > > [1, -x + INF] > > which fails the sanity checking > > cmp = compare_values (min, max); > if (cmp == -2 || cmp == 1) > { > /* If the new range has its limits swapped around (MIN > MAX), > then the operation caused one of them to wrap around, mark > the new range VARYING. */ > set_value_range_to_varying (vr); > } > else > set_value_range (vr, type, min, max, NULL); > > but clearly the same reasoning you can apply that makes trying > with [-INF, x] valid (it's just enlarging the range) can be applied > here, too, when computing +INF - x for the upper bound. We can > safely increase that to +INF making the range valid for the above > test. I don't think we can enlarge to +INF because -x + INF can overflow, we can only enlarge to +INF(OVF). > But I wonder what code path in the routine still relies on that sanity > checking to produce a valid result (so I'd rather try removing it, or > taking uncomparable bounds as a valid range). > > Simplest would be to simply do > > set_value_range (vr, type, min, max, NULL); > return; > > and be done with that in the plus/minus handling. With that the > testcase optimizes ok for me. With [1, -x + INF] as the resulting range? But it can be bogus if x is itself equal to +INF (unlike the input range [x + 1, +INF] which is always correct) so this doesn't look valid to me. I don't see how we can get away without a +INF(OVF) here, but I can compute it in extract_range_from_binary_expr_1 if you prefer and try only [op0,op0] and [op1,op1]. -- Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-06-06 10:54 ` Eric Botcazou @ 2014-06-06 15:45 ` Richard Biener 2014-06-20 9:40 ` Eric Botcazou 0 siblings, 1 reply; 18+ messages in thread From: Richard Biener @ 2014-06-06 15:45 UTC (permalink / raw) To: Eric Botcazou; +Cc: GCC Patches On Fri, Jun 6, 2014 at 12:52 PM, Eric Botcazou <ebotcazou@adacore.com> wrote: >> So when computing a range for z in >> >> z = y - x; >> >> with x = [-INF, y - 1] and y = [x + 1, +INF] (deduced from !(x >= y)) we >> fail to do sth sensible with [y, y] - [-INF, y - 1] or [x + 1, +INF] - [x, >> x] but we do sth with [x + 1, +INF] - [-INF, x]? That seems odd to me. >> >> With the patch we compute z to [1, +INF(OVF)] > > Right, and note the overflow. > >> Going the [x + 1, +INF] - [x,x] path first we obtain >> >> [1, -x + INF] >> >> which fails the sanity checking >> >> cmp = compare_values (min, max); >> if (cmp == -2 || cmp == 1) >> { >> /* If the new range has its limits swapped around (MIN > MAX), >> then the operation caused one of them to wrap around, mark >> the new range VARYING. */ >> set_value_range_to_varying (vr); >> } >> else >> set_value_range (vr, type, min, max, NULL); >> >> but clearly the same reasoning you can apply that makes trying >> with [-INF, x] valid (it's just enlarging the range) can be applied >> here, too, when computing +INF - x for the upper bound. We can >> safely increase that to +INF making the range valid for the above >> test. > > I don't think we can enlarge to +INF because -x + INF can overflow, we can > only enlarge to +INF(OVF). > >> But I wonder what code path in the routine still relies on that sanity >> checking to produce a valid result (so I'd rather try removing it, or >> taking uncomparable bounds as a valid range). >> >> Simplest would be to simply do >> >> set_value_range (vr, type, min, max, NULL); >> return; >> >> and be done with that in the plus/minus handling. With that the >> testcase optimizes ok for me. > > With [1, -x + INF] as the resulting range? But it can be bogus if x is itself > equal to +INF (unlike the input range [x + 1, +INF] which is always correct) Hmm, indeed. > so this doesn't look valid to me. I don't see how we can get away without a > +INF(OVF) here, but I can compute it in extract_range_from_binary_expr_1 if > you prefer and try only [op0,op0] and [op1,op1]. Yeah, I'd prefer that. Thanks, Richard. > -- > Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-06-06 15:45 ` Richard Biener @ 2014-06-20 9:40 ` Eric Botcazou 2014-06-24 10:34 ` Richard Biener 0 siblings, 1 reply; 18+ messages in thread From: Eric Botcazou @ 2014-06-20 9:40 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches [I'm at last back to this...] > > With [1, -x + INF] as the resulting range? But it can be bogus if x is > > itself equal to +INF (unlike the input range [x + 1, +INF] which is > > always correct) > > Hmm, indeed. > > > so this doesn't look valid to me. I don't see how we can get away > > without a +INF(OVF) here, but I can compute it in > > extract_range_from_binary_expr_1 if you prefer and try only [op0,op0] > > and [op1,op1]. > > Yeah, I'd prefer that. To recap, the range of y is [x + 1, +INF] and we're trying to evaluate the range of y - x, in particular we want to prove that y - x > 0. We compute the range of y - x as [1, -x + INF] by combining [x + 1, +INF] with [x, x] and we want to massage it because compare_values will rightly choke. If overflow is undefined, we can simply change it to [1, +INF (OVF)] and be done with that. But if overflow is defined, we need to prove that -x + INF cannot wrap around (which is true if the type is unsigned) and the simplest way to do that in the general case is to recursively invoke the machinery of extract_range_from_binary_expr_1 on range_of(-x) + INF and analyze the result. This looks much more complicated implementation-wise (and would very likely buy us nothing in practice) than my scheme, where we just approximate range_of(-x) by [-INF,+INF] and don't need to implement the recursion at all. However I can change extract_range_from_binary_expr so that only one range among [-INF,x], [x,+INF] and [x,x] is tried instead of the 3 ranges in a row. I initially didn't want to do that because this breaks the separation between extract_range_from_binary_expr_1 and extract_range_from_binary_expr but, given their names, this is very likely acceptable. What do you think? -- Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-06-20 9:40 ` Eric Botcazou @ 2014-06-24 10:34 ` Richard Biener 2014-09-29 23:01 ` Eric Botcazou 0 siblings, 1 reply; 18+ messages in thread From: Richard Biener @ 2014-06-24 10:34 UTC (permalink / raw) To: Eric Botcazou; +Cc: GCC Patches On Fri, Jun 20, 2014 at 11:33 AM, Eric Botcazou <ebotcazou@adacore.com> wrote: > [I'm at last back to this...] > >> > With [1, -x + INF] as the resulting range? But it can be bogus if x is >> > itself equal to +INF (unlike the input range [x + 1, +INF] which is >> > always correct) >> >> Hmm, indeed. >> >> > so this doesn't look valid to me. I don't see how we can get away >> > without a +INF(OVF) here, but I can compute it in >> > extract_range_from_binary_expr_1 if you prefer and try only [op0,op0] >> > and [op1,op1]. >> >> Yeah, I'd prefer that. > > To recap, the range of y is [x + 1, +INF] and we're trying to evaluate the > range of y - x, in particular we want to prove that y - x > 0. > > We compute the range of y - x as [1, -x + INF] by combining [x + 1, +INF] with > [x, x] and we want to massage it because compare_values will rightly choke. > > If overflow is undefined, we can simply change it to [1, +INF (OVF)] and be > done with that. But if overflow is defined, we need to prove that -x + INF > cannot wrap around (which is true if the type is unsigned) and the simplest > way to do that in the general case is to recursively invoke the machinery > of extract_range_from_binary_expr_1 on range_of(-x) + INF and analyze the > result. This looks much more complicated implementation-wise (and would very > likely buy us nothing in practice) than my scheme, where we just approximate > range_of(-x) by [-INF,+INF] and don't need to implement the recursion at all. Hmm, indeed. Put the above into a comment so it's clear why we don't do it that way. > However I can change extract_range_from_binary_expr so that only one range > among [-INF,x], [x,+INF] and [x,x] is tried instead of the 3 ranges in a row. > I initially didn't want to do that because this breaks the separation between > extract_range_from_binary_expr_1 and extract_range_from_binary_expr but, given > their names, this is very likely acceptable. What do you think? Yeah, that sounds good to me. Thanks, Richard. > -- > Eric Botcazou ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-06-24 10:34 ` Richard Biener @ 2014-09-29 23:01 ` Eric Botcazou 0 siblings, 0 replies; 18+ messages in thread From: Eric Botcazou @ 2014-09-29 23:01 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 741 bytes --] > Yeah, that sounds good to me. Here's what I have at last commited after testing on x86-64/Linux. 2014-09-29 Eric Botcazou <ebotcazou@adacore.com> * tree-vrp.c (get_single_symbol): New function. (build_symbolic_expr): Likewise. (symbolic_range_based_on_p): New predicate. (extract_range_from_binary_expr_1): Deal with single-symbolic ranges for PLUS and MINUS. Do not drop symbolic ranges at the end. (extract_range_from_binary_expr): Try harder for PLUS and MINUS if operand is symbolic and based on the other operand. 2014-09-29 Eric Botcazou <ebotcazou@adacore.com> * gcc.dg/tree-ssa/vrp94.c: New test. * gnat.dg/opt40.adb: Likewise. -- Eric Botcazou [-- Attachment #2: vrp_symbolic-2.diff --] [-- Type: text/x-patch, Size: 16928 bytes --] Index: tree-vrp.c =================================================================== --- tree-vrp.c (revision 215656) +++ tree-vrp.c (working copy) @@ -916,6 +916,98 @@ symbolic_range_p (value_range_t *vr) || !is_gimple_min_invariant (vr->max)); } +/* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE + otherwise. We only handle additive operations and set NEG to true if the + symbol is negated and INV to the invariant part, if any. */ + +static tree +get_single_symbol (tree t, bool *neg, tree *inv) +{ + bool neg_; + tree inv_; + + if (TREE_CODE (t) == PLUS_EXPR + || TREE_CODE (t) == POINTER_PLUS_EXPR + || TREE_CODE (t) == MINUS_EXPR) + { + if (is_gimple_min_invariant (TREE_OPERAND (t, 0))) + { + neg_ = (TREE_CODE (t) == MINUS_EXPR); + inv_ = TREE_OPERAND (t, 0); + t = TREE_OPERAND (t, 1); + } + else if (is_gimple_min_invariant (TREE_OPERAND (t, 1))) + { + neg_ = false; + inv_ = TREE_OPERAND (t, 1); + t = TREE_OPERAND (t, 0); + } + else + return NULL_TREE; + } + else + { + neg_ = false; + inv_ = NULL_TREE; + } + + if (TREE_CODE (t) == NEGATE_EXPR) + { + t = TREE_OPERAND (t, 0); + neg_ = !neg_; + } + + if (TREE_CODE (t) != SSA_NAME) + return NULL_TREE; + + *neg = neg_; + *inv = inv_; + return t; +} + +/* The reverse operation: build a symbolic expression with TYPE + from symbol SYM, negated according to NEG, and invariant INV. */ + +static tree +build_symbolic_expr (tree type, tree sym, bool neg, tree inv) +{ + const bool pointer_p = POINTER_TYPE_P (type); + tree t = sym; + + if (neg) + t = build1 (NEGATE_EXPR, type, t); + + if (integer_zerop (inv)) + return t; + + return build2 (pointer_p ? POINTER_PLUS_EXPR : PLUS_EXPR, type, t, inv); +} + +/* Return true if value range VR involves exactly one symbol SYM. */ + +static bool +symbolic_range_based_on_p (value_range_t *vr, const_tree sym) +{ + bool neg, min_has_symbol, max_has_symbol; + tree inv; + + if (is_gimple_min_invariant (vr->min)) + min_has_symbol = false; + else if (get_single_symbol (vr->min, &neg, &inv) == sym) + min_has_symbol = true; + else + return false; + + if (is_gimple_min_invariant (vr->max)) + max_has_symbol = false; + else if (get_single_symbol (vr->max, &neg, &inv) == sym) + max_has_symbol = true; + else + return false; + + return (min_has_symbol || max_has_symbol); +} + /* Return true if value range VR uses an overflow infinity. */ static inline bool @@ -1199,25 +1291,30 @@ compare_values_warnv (tree val1, tree va both integers. */ gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1)) == POINTER_TYPE_P (TREE_TYPE (val2))); + /* Convert the two values into the same type. This is needed because sizetype causes sign extension even for unsigned types. */ val2 = fold_convert (TREE_TYPE (val1), val2); STRIP_USELESS_TYPE_CONVERSION (val2); if ((TREE_CODE (val1) == SSA_NAME + || (TREE_CODE (val1) == NEGATE_EXPR + && TREE_CODE (TREE_OPERAND (val1, 0)) == SSA_NAME) || TREE_CODE (val1) == PLUS_EXPR || TREE_CODE (val1) == MINUS_EXPR) && (TREE_CODE (val2) == SSA_NAME + || (TREE_CODE (val2) == NEGATE_EXPR + && TREE_CODE (TREE_OPERAND (val2, 0)) == SSA_NAME) || TREE_CODE (val2) == PLUS_EXPR || TREE_CODE (val2) == MINUS_EXPR)) { tree n1, c1, n2, c2; enum tree_code code1, code2; - /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', + /* If VAL1 and VAL2 are of the form '[-]NAME [+-] CST' or 'NAME', return -1 or +1 accordingly. If VAL1 and VAL2 don't use the same name, return -2. */ - if (TREE_CODE (val1) == SSA_NAME) + if (TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == NEGATE_EXPR) { code1 = SSA_NAME; n1 = val1; @@ -1239,7 +1336,7 @@ compare_values_warnv (tree val1, tree va } } - if (TREE_CODE (val2) == SSA_NAME) + if (TREE_CODE (val2) == SSA_NAME || TREE_CODE (val2) == NEGATE_EXPR) { code2 = SSA_NAME; n2 = val2; @@ -1262,11 +1359,15 @@ compare_values_warnv (tree val1, tree va } /* Both values must use the same name. */ + if (TREE_CODE (n1) == NEGATE_EXPR && TREE_CODE (n2) == NEGATE_EXPR) + { + n1 = TREE_OPERAND (n1, 0); + n2 = TREE_OPERAND (n2, 0); + } if (n1 != n2) return -2; - if (code1 == SSA_NAME - && code2 == SSA_NAME) + if (code1 == SSA_NAME && code2 == SSA_NAME) /* NAME == NAME */ return 0; @@ -2209,7 +2310,7 @@ extract_range_from_multiplicative_op_1 ( } /* Extract range information from a binary operation CODE based on - the ranges of each of its operands, *VR0 and *VR1 with resulting + the ranges of each of its operands *VR0 and *VR1 with resulting type EXPR_TYPE. The resulting range is stored in *VR. */ static void @@ -2303,11 +2404,12 @@ extract_range_from_binary_expr_1 (value_ type = vr0.type; /* Refuse to operate on VARYING ranges, ranges of different kinds - and symbolic ranges. As an exception, we allow BIT_AND_EXPR + and symbolic ranges. As an exception, we allow BIT_{AND,IOR} because we may be able to derive a useful range even if one of the operands is VR_VARYING or symbolic range. Similarly for - divisions. TODO, we may be able to derive anti-ranges in - some cases. */ + divisions, MIN/MAX and PLUS/MINUS. + + TODO, we may be able to derive anti-ranges in some cases. */ if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR && code != TRUNC_DIV_EXPR @@ -2318,6 +2420,8 @@ extract_range_from_binary_expr_1 (value_ && code != TRUNC_MOD_EXPR && code != MIN_EXPR && code != MAX_EXPR + && code != PLUS_EXPR + && code != MINUS_EXPR && (vr0.type == VR_VARYING || vr1.type == VR_VARYING || vr0.type != vr1.type @@ -2376,50 +2480,115 @@ extract_range_from_binary_expr_1 (value_ range and see what we end up with. */ if (code == PLUS_EXPR || code == MINUS_EXPR) { - /* If we have a PLUS_EXPR with two VR_RANGE integer constant - ranges compute the precise range for such case if possible. */ - if (range_int_cst_p (&vr0) - && range_int_cst_p (&vr1)) - { - signop sgn = TYPE_SIGN (expr_type); - unsigned int prec = TYPE_PRECISION (expr_type); - wide_int type_min = wi::min_value (TYPE_PRECISION (expr_type), sgn); - wide_int type_max = wi::max_value (TYPE_PRECISION (expr_type), sgn); - wide_int wmin, wmax; + const bool minus_p = (code == MINUS_EXPR); + tree min_op0 = vr0.min; + tree min_op1 = minus_p ? vr1.max : vr1.min; + tree max_op0 = vr0.max; + tree max_op1 = minus_p ? vr1.min : vr1.max; + tree sym_min_op0 = NULL_TREE; + tree sym_min_op1 = NULL_TREE; + tree sym_max_op0 = NULL_TREE; + tree sym_max_op1 = NULL_TREE; + bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1; + + /* If we have a PLUS or MINUS with two VR_RANGEs, either constant or + single-symbolic ranges, try to compute the precise resulting range, + but only if we know that this resulting range will also be constant + or single-symbolic. */ + if (vr0.type == VR_RANGE && vr1.type == VR_RANGE + && (TREE_CODE (min_op0) == INTEGER_CST + || (sym_min_op0 + = get_single_symbol (min_op0, &neg_min_op0, &min_op0))) + && (TREE_CODE (min_op1) == INTEGER_CST + || (sym_min_op1 + = get_single_symbol (min_op1, &neg_min_op1, &min_op1))) + && (!(sym_min_op0 && sym_min_op1) + || (sym_min_op0 == sym_min_op1 + && neg_min_op0 == (minus_p ? neg_min_op1 : !neg_min_op1))) + && (TREE_CODE (max_op0) == INTEGER_CST + || (sym_max_op0 + = get_single_symbol (max_op0, &neg_max_op0, &max_op0))) + && (TREE_CODE (max_op1) == INTEGER_CST + || (sym_max_op1 + = get_single_symbol (max_op1, &neg_max_op1, &max_op1))) + && (!(sym_max_op0 && sym_max_op1) + || (sym_max_op0 == sym_max_op1 + && neg_max_op0 == (minus_p ? neg_max_op1 : !neg_max_op1)))) + { + const signop sgn = TYPE_SIGN (expr_type); + const unsigned int prec = TYPE_PRECISION (expr_type); + wide_int type_min, type_max, wmin, wmax; int min_ovf = 0; int max_ovf = 0; - if (code == PLUS_EXPR) + /* Get the lower and upper bounds of the type. */ + if (TYPE_OVERFLOW_WRAPS (expr_type)) { - wmin = wi::add (vr0.min, vr1.min); - wmax = wi::add (vr0.max, vr1.max); - - /* Check for overflow. */ - if (wi::cmp (vr1.min, 0, sgn) != wi::cmp (wmin, vr0.min, sgn)) - min_ovf = wi::cmp (vr0.min, wmin, sgn); - if (wi::cmp (vr1.max, 0, sgn) != wi::cmp (wmax, vr0.max, sgn)) - max_ovf = wi::cmp (vr0.max, wmax, sgn); + type_min = wi::min_value (prec, sgn); + type_max = wi::max_value (prec, sgn); } - else /* if (code == MINUS_EXPR) */ + else { - wmin = wi::sub (vr0.min, vr1.max); - wmax = wi::sub (vr0.max, vr1.min); + type_min = vrp_val_min (expr_type); + type_max = vrp_val_max (expr_type); + } - if (wi::cmp (0, vr1.max, sgn) != wi::cmp (wmin, vr0.min, sgn)) - min_ovf = wi::cmp (vr0.min, vr1.max, sgn); - if (wi::cmp (0, vr1.min, sgn) != wi::cmp (wmax, vr0.max, sgn)) - max_ovf = wi::cmp (vr0.max, vr1.min, sgn); + /* Combine the lower bounds, if any. */ + if (min_op0 && min_op1) + { + if (minus_p) + { + wmin = wi::sub (min_op0, min_op1); + + /* Check for overflow. */ + if (wi::cmp (0, min_op1, sgn) + != wi::cmp (wmin, min_op0, sgn)) + min_ovf = wi::cmp (min_op0, min_op1, sgn); + } + else + { + wmin = wi::add (min_op0, min_op1); + + /* Check for overflow. */ + if (wi::cmp (min_op1, 0, sgn) + != wi::cmp (wmin, min_op0, sgn)) + min_ovf = wi::cmp (min_op0, wmin, sgn); + } } + else if (min_op0) + wmin = min_op0; + else if (min_op1) + wmin = minus_p ? wi::neg (min_op1) : min_op1; + else + wmin = wi::shwi (0, prec); - /* For non-wrapping arithmetic look at possibly smaller - value-ranges of the type. */ - if (!TYPE_OVERFLOW_WRAPS (expr_type)) + /* Combine the upper bounds, if any. */ + if (max_op0 && max_op1) { - if (vrp_val_min (expr_type)) - type_min = vrp_val_min (expr_type); - if (vrp_val_max (expr_type)) - type_max = vrp_val_max (expr_type); + if (minus_p) + { + wmax = wi::sub (max_op0, max_op1); + + /* Check for overflow. */ + if (wi::cmp (0, max_op1, sgn) + != wi::cmp (wmax, max_op0, sgn)) + max_ovf = wi::cmp (max_op0, max_op1, sgn); + } + else + { + wmax = wi::add (max_op0, max_op1); + + if (wi::cmp (max_op1, 0, sgn) + != wi::cmp (wmax, max_op0, sgn)) + max_ovf = wi::cmp (max_op0, wmax, sgn); + } } + else if (max_op0) + wmax = max_op0; + else if (max_op1) + wmax = minus_p ? wi::neg (max_op1) : max_op1; + else + wmax = wi::shwi (0, prec); /* Check for type overflow. */ if (min_ovf == 0) @@ -2437,6 +2606,15 @@ extract_range_from_binary_expr_1 (value_ max_ovf = 1; } + /* If we have overflow for the constant part and the resulting + range will be symbolic, drop to VR_VARYING. */ + if ((min_ovf && sym_min_op0 != sym_min_op1) + || (max_ovf && sym_max_op0 != sym_max_op1)) + { + set_value_range_to_varying (vr); + return; + } + if (TYPE_OVERFLOW_WRAPS (expr_type)) { /* If overflow wraps, truncate the values and adjust the @@ -2450,8 +2628,7 @@ extract_range_from_binary_expr_1 (value_ min = wide_int_to_tree (expr_type, tmin); max = wide_int_to_tree (expr_type, tmax); } - else if (min_ovf == -1 - && max_ovf == 1) + else if (min_ovf == -1 && max_ovf == 1) { /* Underflow and overflow, drop to VR_VARYING. */ set_value_range_to_varying (vr); @@ -2526,20 +2703,44 @@ extract_range_from_binary_expr_1 (value_ else max = wide_int_to_tree (expr_type, wmax); } + if (needs_overflow_infinity (expr_type) && supports_overflow_infinity (expr_type)) { - if (is_negative_overflow_infinity (vr0.min) - || (code == PLUS_EXPR - ? is_negative_overflow_infinity (vr1.min) - : is_positive_overflow_infinity (vr1.max))) + if ((min_op0 && is_negative_overflow_infinity (min_op0)) + || (min_op1 + && (minus_p + ? is_positive_overflow_infinity (min_op1) + : is_negative_overflow_infinity (min_op1)))) min = negative_overflow_infinity (expr_type); - if (is_positive_overflow_infinity (vr0.max) - || (code == PLUS_EXPR - ? is_positive_overflow_infinity (vr1.max) - : is_negative_overflow_infinity (vr1.min))) + if ((max_op0 && is_positive_overflow_infinity (max_op0)) + || (max_op1 + && (minus_p + ? is_negative_overflow_infinity (max_op1) + : is_positive_overflow_infinity (max_op1)))) max = positive_overflow_infinity (expr_type); } + + /* If the result lower bound is constant, we're done; + otherwise, build the symbolic lower bound. */ + if (sym_min_op0 == sym_min_op1) + ; + else if (sym_min_op0) + min = build_symbolic_expr (expr_type, sym_min_op0, + neg_min_op0, min); + else if (sym_min_op1) + min = build_symbolic_expr (expr_type, sym_min_op1, + neg_min_op1 ^ minus_p, min); + + /* Likewise for the upper bound. */ + if (sym_max_op0 == sym_max_op1) + ; + else if (sym_max_op0) + max = build_symbolic_expr (expr_type, sym_max_op0, + neg_max_op0, max); + else if (sym_max_op1) + max = build_symbolic_expr (expr_type, sym_max_op1, + neg_max_op1 ^ minus_p, max); } else { @@ -3024,14 +3225,11 @@ extract_range_from_binary_expr_1 (value_ gcc_unreachable (); /* If either MIN or MAX overflowed, then set the resulting range to - VARYING. But we do accept an overflow infinity - representation. */ + VARYING. But we do accept an overflow infinity representation. */ if (min == NULL_TREE - || !is_gimple_min_invariant (min) - || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) + || (TREE_OVERFLOW_P (min) && !is_overflow_infinity (min)) || max == NULL_TREE - || !is_gimple_min_invariant (max) - || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) + || (TREE_OVERFLOW_P (max) && !is_overflow_infinity (max))) { set_value_range_to_varying (vr); return; @@ -3093,6 +3291,59 @@ extract_range_from_binary_expr (value_ra set_value_range_to_varying (&vr1); extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1); + + /* Try harder for PLUS and MINUS if the range of one operand is symbolic + and based on the other operand, for example if it was deduced from a + symbolic comparison. When a bound of the range of the first operand + is invariant, we set the corresponding bound of the new range to INF + in order to avoid recursing on the range of the second operand. */ + if (vr->type == VR_VARYING + && (code == PLUS_EXPR || code == MINUS_EXPR) + && TREE_CODE (op1) == SSA_NAME + && vr0.type == VR_RANGE + && symbolic_range_based_on_p (&vr0, op1)) + { + const bool minus_p = (code == MINUS_EXPR); + value_range_t n_vr1 = VR_INITIALIZER; + + /* Try with VR0 and [-INF, OP1]. */ + if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min)) + set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL); + + /* Try with VR0 and [OP1, +INF]. */ + else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max)) + set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL); + + /* Try with VR0 and [OP1, OP1]. */ + else + set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL); + + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1); + } + + if (vr->type == VR_VARYING + && (code == PLUS_EXPR || code == MINUS_EXPR) + && TREE_CODE (op0) == SSA_NAME + && vr1.type == VR_RANGE + && symbolic_range_based_on_p (&vr1, op0)) + { + const bool minus_p = (code == MINUS_EXPR); + value_range_t n_vr0 = VR_INITIALIZER; + + /* Try with [-INF, OP0] and VR1. */ + if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min)) + set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL); + + /* Try with [OP0, +INF] and VR1. */ + else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max)) + set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL); + + /* Try with [OP0, OP0] and VR1. */ + else + set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL); + + extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1); + } } /* Extract range information from a unary operation CODE based on [-- Attachment #3: vrp94.c --] [-- Type: text/x-csrc, Size: 496 bytes --] /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ extern void abort (void); int foo1 (int x, int y) { int z; if (x >= y) return 1; z = y - x; if (z <= 0) abort (); return z; } unsigned int foo2 (unsigned int x, unsigned int y) { unsigned int z; if (x >= y) return 1; z = y - x; if (z == 0) abort (); return z; } /* { dg-final { scan-tree-dump-not "abort" "optimized" } } */ /* { dg-final { cleanup-tree-dump "optimized" } } */ [-- Attachment #4: opt40.adb --] [-- Type: text/x-adasrc, Size: 380 bytes --] -- { dg-do compile } -- { dg-options "-O2 -fdump-tree-optimized" } pragma Suppress (Overflow_Check); function Opt40 (X : Integer; Y : Integer) return Positive is Z : Integer; begin if X >= Y then return 1; end if; Z := Y - X; return Z; end; -- { dg-final { scan-tree-dump-not "gnat_rcheck" "optimized" } } -- { dg-final { cleanup-tree-dump "optimized" } } ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-05-27 9:42 ` Richard Biener 2014-05-27 10:00 ` Eric Botcazou @ 2014-05-27 16:14 ` Eric Botcazou 2014-05-27 16:19 ` Richard Biener 1 sibling, 1 reply; 18+ messages in thread From: Eric Botcazou @ 2014-05-27 16:14 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 631 bytes --] > I'm asking to merge them (move them to fold_comparison). Done (in the end the patch removes more lines than it adds :-). Tested on x86_64-suse-linux with no regressions. 2014-05-27 Eric Botcazou <ebotcazou@adacore.com> * fold-const.c (fold_comparison): Clean up and extend X +- C1 CMP C2 to X CMP C2 -+ C1 transformation to EQ_EXPR/NE_EXPR. Add X - Y CMP 0 to X CMP Y transformation. (fold_binary_loc) <EQ_EXPR/NE_EXPR>: Remove same transformations. 2014-05-27 Eric Botcazou <ebotcazou@adacore.com> * gcc.dg/fold-compare-8.c: New test. * gcc.dg/Wstrict-overflow-25.c: Likewise. -- Eric Botcazou [-- Attachment #2: p.diff --] [-- Type: text/x-patch, Size: 6975 bytes --] Index: fold-const.c =================================================================== --- fold-const.c (revision 210911) +++ fold-const.c (working copy) @@ -8904,6 +8904,7 @@ static tree fold_comparison (location_t loc, enum tree_code code, tree type, tree op0, tree op1) { + const bool equality_code = (code == EQ_EXPR || code == NE_EXPR); tree arg0, arg1, tem; arg0 = op0; @@ -8920,28 +8921,24 @@ 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); - /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 +- C1. */ + /* 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 - && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1)) - && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1))) - && (TREE_CODE (arg1) == INTEGER_CST - && !TREE_OVERFLOW (arg1))) + && (equality_code || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0))) + && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST + && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1)) + && TREE_CODE (arg1) == INTEGER_CST + && !TREE_OVERFLOW (arg1)) { + const enum tree_code + reverse_op = TREE_CODE (arg0) == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR; tree const1 = TREE_OPERAND (arg0, 1); - tree const2 = arg1; + tree const2 = fold_convert_loc (loc, TREE_TYPE (const1), arg1); tree variable = TREE_OPERAND (arg0, 0); - tree lhs; - int lhs_add; - lhs_add = TREE_CODE (arg0) != PLUS_EXPR; - - lhs = fold_build2_loc (loc, lhs_add ? PLUS_EXPR : MINUS_EXPR, - TREE_TYPE (arg1), const2, const1); + tree new_const = int_const_binop (reverse_op, const2, const1); /* If the constant operation overflowed this can be simplified as a comparison against INT_MAX/INT_MIN. */ - if (TREE_CODE (lhs) == INTEGER_CST - && TREE_OVERFLOW (lhs)) + if (TREE_OVERFLOW (new_const)) { int const1_sgn = tree_int_cst_sgn (const1); enum tree_code code2 = code; @@ -8961,29 +8958,48 @@ fold_comparison (location_t loc, enum tr /* We now can look at the canonicalized case VARIABLE + 1 CODE2 INT_MIN and decide on the result. */ - if (code2 == LT_EXPR - || code2 == LE_EXPR - || code2 == EQ_EXPR) - return omit_one_operand_loc (loc, type, boolean_false_node, variable); - else if (code2 == NE_EXPR - || code2 == GE_EXPR - || code2 == GT_EXPR) - return omit_one_operand_loc (loc, type, boolean_true_node, variable); - } + switch (code2) + { + case EQ_EXPR: + case LT_EXPR: + case LE_EXPR: + return + omit_one_operand_loc (loc, type, boolean_false_node, variable); + + case NE_EXPR: + case GE_EXPR: + case GT_EXPR: + return + omit_one_operand_loc (loc, type, boolean_true_node, variable); - if (TREE_CODE (lhs) == TREE_CODE (arg1) - && (TREE_CODE (lhs) != INTEGER_CST - || !TREE_OVERFLOW (lhs))) + default: + gcc_unreachable (); + } + } + else { - if (code != EQ_EXPR && code != NE_EXPR) + if (!equality_code) fold_overflow_warning ("assuming signed overflow does not occur " "when changing X +- C1 cmp C2 to " - "X cmp C1 +- C2", + "X cmp C2 -+ C1", WARN_STRICT_OVERFLOW_COMPARISON); - return fold_build2_loc (loc, code, type, variable, lhs); + return fold_build2_loc (loc, code, type, variable, new_const); } } + /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */ + if (TREE_CODE (arg0) == MINUS_EXPR + && (equality_code || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0))) + && integer_zerop (arg1)) + { + if (!equality_code) + fold_overflow_warning ("assuming signed overflow does not occur " + "when changing X - Y cmp 0 to X cmp Y", + WARN_STRICT_OVERFLOW_COMPARISON); + return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), + TREE_OPERAND (arg0, 1)); + } + /* For comparisons of pointers we can decompose it to a compile time comparison of the base objects and the offsets into the object. This requires at least one operand being an ADDR_EXPR or a @@ -9111,8 +9127,7 @@ fold_comparison (location_t loc, enum tr || POINTER_TYPE_OVERFLOW_UNDEFINED)) { - if (code != EQ_EXPR - && code != NE_EXPR + if (!equality_code && bitpos0 != bitpos1 && (pointer_may_wrap_p (base0, offset0, bitpos0) || pointer_may_wrap_p (base1, offset1, bitpos1))) @@ -9146,7 +9161,7 @@ fold_comparison (location_t loc, enum tr object and overflow on pointer differences is undefined as of 6.5.6/8 and /9 with respect to the signed ptrdiff_t. */ else if (bitpos0 == bitpos1 - && ((code == EQ_EXPR || code == NE_EXPR) + && (equality_code || (indirect_base0 && DECL_P (base0)) || POINTER_TYPE_OVERFLOW_UNDEFINED)) { @@ -9164,8 +9179,7 @@ fold_comparison (location_t loc, enum tr else offset1 = fold_convert_loc (loc, ssizetype, offset1); - if (code != EQ_EXPR - && code != NE_EXPR + if (!equality_code && (pointer_may_wrap_p (base0, offset0, bitpos0) || pointer_may_wrap_p (base1, offset1, bitpos1))) fold_overflow_warning (("assuming pointer wraparound does not " @@ -12888,21 +12902,6 @@ fold_binary_loc (location_t loc, type); } - /* If this is an EQ or NE comparison of a constant with a PLUS_EXPR or - a MINUS_EXPR of a constant, we can convert it into a comparison with - a revised constant as long as no overflow occurs. */ - if (TREE_CODE (arg1) == INTEGER_CST - && (TREE_CODE (arg0) == PLUS_EXPR - || TREE_CODE (arg0) == MINUS_EXPR) - && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST - && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR - ? MINUS_EXPR : PLUS_EXPR, - fold_convert_loc (loc, TREE_TYPE (arg0), - arg1), - TREE_OPERAND (arg0, 1))) - && !TREE_OVERFLOW (tem)) - return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem); - /* Similarly for a NEGATE_EXPR. */ if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == INTEGER_CST @@ -12956,13 +12955,6 @@ fold_binary_loc (location_t loc, TREE_OPERAND (arg0, 1), arg1); } - /* If we have X - Y == 0, we can convert that to X == Y and similarly - for !=. Don't do this for ordered comparisons due to overflow. */ - if (TREE_CODE (arg0) == MINUS_EXPR - && integer_zerop (arg1)) - return fold_build2_loc (loc, code, type, - TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1)); - /* Convert ABS_EXPR<x> == 0 or ABS_EXPR<x> != 0 to x == 0 or x != 0. */ if (TREE_CODE (arg0) == ABS_EXPR && (integer_zerop (arg1) || real_zerop (arg1))) ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow 2014-05-27 16:14 ` Eric Botcazou @ 2014-05-27 16:19 ` Richard Biener 0 siblings, 0 replies; 18+ messages in thread From: Richard Biener @ 2014-05-27 16:19 UTC (permalink / raw) To: Eric Botcazou; +Cc: gcc-patches On May 27, 2014 6:12:58 PM CEST, Eric Botcazou <ebotcazou@adacore.com> wrote: >> I'm asking to merge them (move them to fold_comparison). > >Done (in the end the patch removes more lines than it adds :-). That's what I like! >Tested on x86_64-suse-linux with no regressions. OK. Thanks, Richard. > >2014-05-27 Eric Botcazou <ebotcazou@adacore.com> > > * fold-const.c (fold_comparison): Clean up and extend X +- C1 CMP C2 > to X CMP C2 -+ C1 transformation to EQ_EXPR/NE_EXPR. > Add X - Y CMP 0 to X CMP Y transformation. > (fold_binary_loc) <EQ_EXPR/NE_EXPR>: Remove same transformations. > > >2014-05-27 Eric Botcazou <ebotcazou@adacore.com> > > * gcc.dg/fold-compare-8.c: New test. > * gcc.dg/Wstrict-overflow-25.c: Likewise. ^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2014-09-29 23:01 UTC | newest] Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2014-05-26 10:24 [RFC] optimize x - y cmp 0 with undefined overflow Eric Botcazou 2014-05-26 12:55 ` Richard Biener 2014-05-27 9:26 ` Eric Botcazou 2014-05-27 9:42 ` Richard Biener 2014-05-27 10:00 ` Eric Botcazou 2014-05-27 10:12 ` Richard Biener 2014-05-30 8:49 ` Eric Botcazou 2014-06-02 10:36 ` Richard Biener 2014-06-02 10:37 ` Richard Biener 2014-06-03 8:13 ` Eric Botcazou 2014-06-03 11:00 ` Richard Biener 2014-06-06 10:54 ` Eric Botcazou 2014-06-06 15:45 ` Richard Biener 2014-06-20 9:40 ` Eric Botcazou 2014-06-24 10:34 ` Richard Biener 2014-09-29 23:01 ` Eric Botcazou 2014-05-27 16:14 ` Eric Botcazou 2014-05-27 16:19 ` Richard Biener
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).