[RFC] optimize x - y cmp 0 with undefined overflow
diff mbox

Message ID CAFiYyc2OVqjwKMXn0Rz7-mN97xdV2=+11RvPO=619C6FOktQUA@mail.gmail.com
State New
Headers show

Commit Message

Richard Biener May 26, 2014, 12:55 p.m. UTC
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


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

Comments

Eric Botcazou May 27, 2014, 9:25 a.m. UTC | #1
> +      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.
Richard Biener May 27, 2014, 9:41 a.m. UTC | #2
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
Eric Botcazou May 27, 2014, 9:59 a.m. UTC | #3
> 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...
Richard Biener May 27, 2014, 10:12 a.m. UTC | #4
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

Patch
diff mbox

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. */