[RFA,PR,tree-optimization/98028] Use relationship between operands to simplify SUB_OVERFLOW

Message ID b4f0b223-d463-4f7f-a97e-bf0dc6406978@gmail.com
State New
Headers
Series [RFA,PR,tree-optimization/98028] Use relationship between operands to simplify SUB_OVERFLOW |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_gcc_check--master-arm success Test passed
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed
linaro-tcwg-bot/tcwg_simplebootstrap_build--master-aarch64-bootstrap success Build passed

Commit Message

Jeffrey Law Feb. 12, 2025, 12:20 a.m. UTC
  So this is a fairly old regression, but with all the ranger work that's 
been done, it's become easy to resolve.

The basic idea here is to use known relationships between two operands 
of a SUB_OVERFLOW IFN to statically compute the overflow state and 
ultimately allow turning the IFN into simple arithmetic (or for the 
tests in this BZ elide the arithmetic entirely).

The regression example is when the two inputs are known equal.  In that 
case the subtraction will never overflow.    But there's a few other 
cases we can handle as well.

a == b -> never overflows
a > b  -> never overflows when A and B are unsigned
a >= b -> never overflows when A and B are unsigned
a < b  -> always overflows when A and B are unsigned

Bootstrapped and regression tested on x86, and regression tested on the 
usual cross platforms.

OK for the trunk?

Jeff
PR tree-optimization/98028
gcc/
	* vr-values.cc (check_for_binary_op_overflow): Try to use a known
	relationship betwen op0/op1 to statically determine overflow state.

gcc/testsuite
	* gcc.dg/tree-ssa/pr98028.c: New test.
  

Comments

Andrew MacLeod Feb. 12, 2025, 2:17 p.m. UTC | #1
The patch is mostly fine, although you probably want to change the 
condition to check for a non-null stmt as well... ie

-   if (subcode == MINUS_EXPR)
+  if (s && subcode == MINUS_EXPR)

because it looks like the stmt defaults to NULL and I suspect the 
relation query will trap if S is null.

I defer to the release managers about whether it goes in trunk now or 
stage 1 :-)

Andrew

On 2/11/25 19:20, Jeff Law wrote:
> So this is a fairly old regression, but with all the ranger work 
> that's been done, it's become easy to resolve.
>
> The basic idea here is to use known relationships between two operands 
> of a SUB_OVERFLOW IFN to statically compute the overflow state and 
> ultimately allow turning the IFN into simple arithmetic (or for the 
> tests in this BZ elide the arithmetic entirely).
>
> The regression example is when the two inputs are known equal.  In 
> that case the subtraction will never overflow.    But there's a few 
> other cases we can handle as well.
>
> a == b -> never overflows
> a > b  -> never overflows when A and B are unsigned
> a >= b -> never overflows when A and B are unsigned
> a < b  -> always overflows when A and B are unsigned
>
> Bootstrapped and regression tested on x86, and regression tested on 
> the usual cross platforms.
>
> OK for the trunk?
>
> Jeff
  
Jeffrey Law Feb. 12, 2025, 2:54 p.m. UTC | #2
On 2/12/25 7:17 AM, Andrew MacLeod wrote:
> The patch is mostly fine, although you probably want to change the 
> condition to check for a non-null stmt as well... ie
Thanks for the reminder.  I saw that defaulting and made a mental note 
to test that we actually had a statement, then promptly forgot about it. 
  Spinning it now...

> 
> I defer to the release managers about whether it goes in trunk now or 
> stage 1 :-)
I think this easily meets the current stage's criteria.  So if you're 
comfortable with the technical bits (with the adjustment noted above), 
then I'll take the responsibility for "in or out of this release" decision.

Jeff
  
Jakub Jelinek Feb. 12, 2025, 3:18 p.m. UTC | #3
On Tue, Feb 11, 2025 at 05:20:49PM -0700, Jeff Law wrote:
> So this is a fairly old regression, but with all the ranger work that's been
> done, it's become easy to resolve.
> 
> The basic idea here is to use known relationships between two operands of a
> SUB_OVERFLOW IFN to statically compute the overflow state and ultimately
> allow turning the IFN into simple arithmetic (or for the tests in this BZ
> elide the arithmetic entirely).
> 
> The regression example is when the two inputs are known equal.  In that case
> the subtraction will never overflow.    But there's a few other cases we can
> handle as well.
> 
> a == b -> never overflows
> a > b  -> never overflows when A and B are unsigned
> a >= b -> never overflows when A and B are unsigned
> a < b  -> always overflows when A and B are unsigned

Is that really the case?
I mean, .SUB_OVERFLOW etc. can have 3 arbitrary types, the type into which
we are trying to write the result and the 2 types of arguments.
Consider:

int
foo (unsigned x, unsigned y)
{
  return __builtin_sub_overflow_p (x, y, (signed char) 0);
}

int
bar (unsigned int x, unsigned long long y)
{
  return __builtin_sub_overflow_p (x, y, (_BitInt(33)) 0);
}

int
main ()
{
  __builtin_printf ("%d\n", foo (16, 16));
  __builtin_printf ("%d\n", foo (65536, 65536));
  __builtin_printf ("%d\n", foo (65536, 16));
  __builtin_printf ("%d\n", bar (0, ~0U));
  __builtin_printf ("%d\n", bar (0, ~0ULL));
}

The a == b case is probably ok, although unsure if the relation query
won't be upset if op0 and op1 have different types (say signed long long vs.
unsigned int), given that result in infinite precision should be 0 and
that will fit into any type.
But the a > b and a >= b cases clearly can overflow if the result type
(element type of the COMPLEX_TYPE result of the ifn) can't represent all the
values of op0's type, so if say __builtin_add_overflow_p with second
argument 0 would also overflow.
And the a < b case can also overflow or not overflow depending on the types
as shown in the test.

So, I think you want to:
a) see with Andrew or check yourself whether relation query can deal with
   operands with different types; if not, restrict just to the case
   where they are compatible
b) either restrict the a > b, a >= b and a < b new optimizations to
   cases where the result and operand types are the same, or add further
   checks; for the a > b and a >= b case there won't be overflow if
   result type can fit all the values in a's type, or as we are in the
   ranger we can just check if the range maximum of op0
   fits into the result type (or even use ranges of both op0 and op1
   for that, we know that the result will be always non-negative given the
   a > b or a >= b relations, so check if maximum of op0 minus minimum of
   op1 will fit into the result type); if yes, it never overflows, otherwise
   we don't know.  Also, unsure why this is about TYPE_UNSIGNED only;
   even for signed operands, if a > b or a >= b, the infinite precision
   result is still non-negative.
   What the a > b and a >= b relations bring into the picture for MINUS_EXPR
   is simply that we don't need to check 2 arith_overflowed_p cases
   but just one; the vr0max vs. vr1min, as for the vr0min vs. vr1max case
   we know it doesn't overflow unless the first one overflows.
   For the a < b case again similarly.

	Jakub
  
Jeffrey Law Feb. 12, 2025, 3:29 p.m. UTC | #4
On 2/12/25 8:18 AM, Jakub Jelinek wrote:
> On Tue, Feb 11, 2025 at 05:20:49PM -0700, Jeff Law wrote:
>> So this is a fairly old regression, but with all the ranger work that's been
>> done, it's become easy to resolve.
>>
>> The basic idea here is to use known relationships between two operands of a
>> SUB_OVERFLOW IFN to statically compute the overflow state and ultimately
>> allow turning the IFN into simple arithmetic (or for the tests in this BZ
>> elide the arithmetic entirely).
>>
>> The regression example is when the two inputs are known equal.  In that case
>> the subtraction will never overflow.    But there's a few other cases we can
>> handle as well.
>>
>> a == b -> never overflows
>> a > b  -> never overflows when A and B are unsigned
>> a >= b -> never overflows when A and B are unsigned
>> a < b  -> always overflows when A and B are unsigned
> 
> Is that really the case?
> I mean, .SUB_OVERFLOW etc. can have 3 arbitrary types, the type into which
> we are trying to write the result and the 2 types of arguments.
So if the types are allowed to vary within a statement (I guess as an 
IFN they can unlike most gimple operations).

In which case we'd need to tighten the checks.  THe simplest would be to 
ensure that both arguments have the same/equivalent types.  We could go 
farther than that, though the risk/benefit of doing more may not be great.

I'll digest the rest a bit later, but clearly pushing pause while I do so...

jeff
  
Jakub Jelinek Feb. 12, 2025, 3:44 p.m. UTC | #5
On Wed, Feb 12, 2025 at 08:29:37AM -0700, Jeff Law wrote:
> On 2/12/25 8:18 AM, Jakub Jelinek wrote:
> > On Tue, Feb 11, 2025 at 05:20:49PM -0700, Jeff Law wrote:
> > > So this is a fairly old regression, but with all the ranger work that's been
> > > done, it's become easy to resolve.
> > > 
> > > The basic idea here is to use known relationships between two operands of a
> > > SUB_OVERFLOW IFN to statically compute the overflow state and ultimately
> > > allow turning the IFN into simple arithmetic (or for the tests in this BZ
> > > elide the arithmetic entirely).
> > > 
> > > The regression example is when the two inputs are known equal.  In that case
> > > the subtraction will never overflow.    But there's a few other cases we can
> > > handle as well.
> > > 
> > > a == b -> never overflows
> > > a > b  -> never overflows when A and B are unsigned
> > > a >= b -> never overflows when A and B are unsigned
> > > a < b  -> always overflows when A and B are unsigned
> > 
> > Is that really the case?
> > I mean, .SUB_OVERFLOW etc. can have 3 arbitrary types, the type into which
> > we are trying to write the result and the 2 types of arguments.
> So if the types are allowed to vary within a statement (I guess as an IFN
> they can unlike most gimple operations).

The overflow builtins started from clang's
__builtin_{s,u}{add,sub,mul}{,l,ll}_overflow
builtins (those were added for compatibility), all of those have the 3 types
identical; but the __builtin_{add,sub,mul}_overflow{,_p} builtins allow 3
arbitrary types, whether something overflows or not is determined by
performing the operation in virtually infinite precision and then seeing if
it is representable in the target type.

I'm fine if your patch is for GCC 15 limited to the easy cases with all 3
types compatible (that is the common case).  Still, I think it would be nice
not to restrict to TYPE_UNSIGNED, just say check either that for a >= b or a > b
b is not negative (using vr1min).

And let's file a PR for GCC 16 to do it properly.

	Jakub
  
Andrew MacLeod Feb. 12, 2025, 7:59 p.m. UTC | #6
On 2/12/25 10:18, Jakub Jelinek wrote:
> On Tue, Feb 11, 2025 at 05:20:49PM -0700, Jeff Law wrote:
>> So this is a fairly old regression, but with all the ranger work that's been
>> done, it's become easy to resolve.
>>
>> The basic idea here is to use known relationships between two operands of a
>> SUB_OVERFLOW IFN to statically compute the overflow state and ultimately
>> allow turning the IFN into simple arithmetic (or for the tests in this BZ
>> elide the arithmetic entirely).
>>
>> The regression example is when the two inputs are known equal.  In that case
>> the subtraction will never overflow.    But there's a few other cases we can
>> handle as well.
>>
>> a == b -> never overflows
>> a > b  -> never overflows when A and B are unsigned
>> a >= b -> never overflows when A and B are unsigned
>> a < b  -> always overflows when A and B are unsigned
> Is that really the case?
> I mean, .SUB_OVERFLOW etc. can have 3 arbitrary types, the type into which
> we are trying to write the result and the 2 types of arguments.
> Consider:
>
> int
> foo (unsigned x, unsigned y)
> {
>    return __builtin_sub_overflow_p (x, y, (signed char) 0);
> }
>
> int
> bar (unsigned int x, unsigned long long y)
> {
>    return __builtin_sub_overflow_p (x, y, (_BitInt(33)) 0);
> }
>
> int
> main ()
> {
>    __builtin_printf ("%d\n", foo (16, 16));
>    __builtin_printf ("%d\n", foo (65536, 65536));
>    __builtin_printf ("%d\n", foo (65536, 16));
>    __builtin_printf ("%d\n", bar (0, ~0U));
>    __builtin_printf ("%d\n", bar (0, ~0ULL));
> }
>
> The a == b case is probably ok, although unsure if the relation query
> won't be upset if op0 and op1 have different types (say signed long long vs.

Relation queries are purely ssa-name based, and never look at the 
type.   The only way a relation can exist between 2 different typed 
SSA_NAMES with different size/signs is if a call is made to record such 
a relation. Its not disallowed, but its unlikely to happen from within 
ranger currently (other than partial equivalences), but presumably even 
if it did, it should only come from a circumstance where the operation 
generating the relation knows it to be true.  Typically relations are 
generated as known side effects of a stmt executing.. like if (a < b), 
and all the instances I am aware of involve range-ops between operands 
of the same size..

Its easy enough to be safe an check if it matters tho I suppose.

FWIW, ==  should only come up when both the sign and # bits are the 
same.  Otherwise it is represented with a partial equivalence which 
indicates only that a certain number of bits are equal.

Andrew
  
Jeffrey Law Feb. 12, 2025, 8:42 p.m. UTC | #7
On 2/12/25 8:44 AM, Jakub Jelinek wrote:
> On Wed, Feb 12, 2025 at 08:29:37AM -0700, Jeff Law wrote:
>> On 2/12/25 8:18 AM, Jakub Jelinek wrote:
>>> On Tue, Feb 11, 2025 at 05:20:49PM -0700, Jeff Law wrote:
>>>> So this is a fairly old regression, but with all the ranger work that's been
>>>> done, it's become easy to resolve.
>>>>
>>>> The basic idea here is to use known relationships between two operands of a
>>>> SUB_OVERFLOW IFN to statically compute the overflow state and ultimately
>>>> allow turning the IFN into simple arithmetic (or for the tests in this BZ
>>>> elide the arithmetic entirely).
>>>>
>>>> The regression example is when the two inputs are known equal.  In that case
>>>> the subtraction will never overflow.    But there's a few other cases we can
>>>> handle as well.
>>>>
>>>> a == b -> never overflows
>>>> a > b  -> never overflows when A and B are unsigned
>>>> a >= b -> never overflows when A and B are unsigned
>>>> a < b  -> always overflows when A and B are unsigned
>>>
>>> Is that really the case?
>>> I mean, .SUB_OVERFLOW etc. can have 3 arbitrary types, the type into which
>>> we are trying to write the result and the 2 types of arguments.
>> So if the types are allowed to vary within a statement (I guess as an IFN
>> they can unlike most gimple operations).
> 
> The overflow builtins started from clang's
> __builtin_{s,u}{add,sub,mul}{,l,ll}_overflow
> builtins (those were added for compatibility), all of those have the 3 types
> identical; but the __builtin_{add,sub,mul}_overflow{,_p} builtins allow 3
> arbitrary types, whether something overflows or not is determined by
> performing the operation in virtually infinite precision and then seeing if
> it is representable in the target type.
> 
> I'm fine if your patch is for GCC 15 limited to the easy cases with all 3
> types compatible (that is the common case).  Still, I think it would be nice
> not to restrict to TYPE_UNSIGNED, just say check either that for a >= b or a > b
> b is not negative (using vr1min).
> 
> And let's file a PR for GCC 16 to do it properly.
The pause button was to give me time to get coffee in and brain turned 
on to walk through the cases.

Note there's code later in that function which actually does 
computations based on known ranges to try and prove/disprove overflow 
state.  There may be cases there we can improve range based analysis as 
well and there may be cases where the combination of range information 
and relationships couple be helpful.   Those all felt out of scope to me 
in terms of addressing the regression.  Happy to open a distinct issue 
on possibilities there.

The regression can be resolved entirely by looking at the relationship 
between and the types of the inputs.  Hence it's a distinct block of 
code in that routine and avoids most of the complexity in that routine.

I agree that the most common cases should be all the arguments the same 
type.  I was working under the assumption that the args would be 
compatible types already, forgetting that IFNs are different in that 
regard than other gimple ops.  I wouldn't want to go any further than 
all three operands the same with the easy to reason about relation checks.


For gcc-16 I think we can extend that block fairly easily to handle 
certain mismatched size cases and we look to see if there's cases where 
the combination of a relationship between the arguments and some range 
information would allow us to capture further cases.

It may even make a good relatively early task for one of the interns 
I've got that's starting soon.  Narrow in scope, easily understood, 
doesn't require a ton of internals knowledge to reason about the cases,
easy to evaluate if the transformations are triggering, etc etc.


Jeff
  
Jakub Jelinek Feb. 12, 2025, 9:22 p.m. UTC | #8
On Wed, Feb 12, 2025 at 01:42:12PM -0700, Jeff Law wrote:
> > I'm fine if your patch is for GCC 15 limited to the easy cases with all 3
> > types compatible (that is the common case).  Still, I think it would be nice
> > not to restrict to TYPE_UNSIGNED, just say check either that for a >= b or a > b
> > b is not negative (using vr1min).
> > 
> > And let's file a PR for GCC 16 to do it properly.
> The pause button was to give me time to get coffee in and brain turned on to
> walk through the cases.
> 
> Note there's code later in that function which actually does computations
> based on known ranges to try and prove/disprove overflow state.  There may
> be cases there we can improve range based analysis as well and there may be
> cases where the combination of range information and relationships couple be
> helpful.   Those all felt out of scope to me in terms of addressing the
> regression.  Happy to open a distinct issue on possibilities there.
> 
> The regression can be resolved entirely by looking at the relationship
> between and the types of the inputs.  Hence it's a distinct block of code in
> that routine and avoids most of the complexity in that routine.

Ok.

> I agree that the most common cases should be all the arguments the same
> type.  I was working under the assumption that the args would be compatible
> types already, forgetting that IFNs are different in that regard than other
> gimple ops.  I wouldn't want to go any further than all three operands the
> same with the easy to reason about relation checks.
> 
> 
> For gcc-16 I think we can extend that block fairly easily to handle certain
> mismatched size cases and we look to see if there's cases where the
> combination of a relationship between the arguments and some range
> information would allow us to capture further cases.

For the GCC 16 version, I think best would be (given Andrew's mail that
the relations aren't likely very useful for incompatible types) to
  relation_kind rel = VREL_VARYING;
  if (code == MINUS_EXPR
      && types_compatible_p (TREE_TYPE (op0), TREE_TYPE (op1))
    {
      rel = query->relation().query (s, op0, op1);
      /* The result of the infinite precision subtraction of
	 the same values will be always 0.  That will fit into any result
	 type.  */
      if (rel == VREL_EQ)
	return true;
    }

then do the current
  int_range_max vr0, vr1;
  if (!query->range_of_expr (vr0, op0, s) || vr0.undefined_p ())
    vr0.set_varying (TREE_TYPE (op0));
  if (!query->range_of_expr (vr1, op1, s) || vr1.undefined_p ())
    vr1.set_varying (TREE_TYPE (op1));

  tree vr0min = wide_int_to_tree (TREE_TYPE (op0), vr0.lower_bound ());
  tree vr0max = wide_int_to_tree (TREE_TYPE (op0), vr0.upper_bound ());
  tree vr1min = wide_int_to_tree (TREE_TYPE (op1), vr1.lower_bound ());
  tree vr1max = wide_int_to_tree (TREE_TYPE (op1), vr1.upper_bound ());

and then we can e.g. special case > and >=:
  /* If op1 is not negative, op0 - op1 for op0 >= op1 will be always
     in [0, op0] and so if vr0max - vr1min fits into type, there won't
     be any overflow.  */
  if ((rel == VREL_GT || rel == VREL_GE)
      && tree_int_cst_sgn (vr1min) >= 0
      && !arith_overflowed_p (MINUS_EXPR, type, vr0max, vr1min))
    return true;

Would need to think about if anything could be simplified for
VREL_G{T,E} if tree_int_cst_sgn (vr1min) < 0.

As for VREL_LT, one would need to think it through as well for both
tree_int_cst_sgn (vr1min) >= 0 and tree_int_cst_sgn (vr1min) < 0.
For the former, the infinite precision of subtraction is known given
the relation to be < 0.  Now obviously if TYPE_UNSIGNED (type) that
would imply always overflow.  But for !TYPE_UNSIGNED (type) that isn't
necessarily the case and the question is if the relation helps with the
reasoning.  Generally the code otherwise tries to check 2 boundaries
(for MULT_EXPR 4 but we don't care about that), if they both don't overflow,
it is ok, if only one overflows, we don't know, if both boundaries don't
overflow, we need to look further and check some corner cases in between.

Or just go with that even for GCC 15 (completely untested and dunno if
something needs to be done about s = NULL passed to query or not) for
now, with the advantage that it can do something even for the cases where
type is not compatible with types of arguments, and perhaps add additional
cases later?

--- gcc/vr-values.cc.jj	2025-01-13 09:12:09.461954569 +0100
+++ gcc/vr-values.cc	2025-02-12 22:18:51.696314406 +0100
@@ -85,6 +85,19 @@ check_for_binary_op_overflow (range_quer
 			      enum tree_code subcode, tree type,
 			      tree op0, tree op1, bool *ovf, gimple *s = NULL)
 {
+  relation_kind rel = VREL_VARYING;
+  /* For subtraction see if relations could simplify it.  */
+  if (code == MINUS_EXPR
+      && types_compatible_p (TREE_TYPE (op0), TREE_TYPE (op1))
+    {
+      rel = query->relation().query (s, op0, op1);
+      /* The result of the infinite precision subtraction of
+	 the same values will be always 0.  That will fit into any result
+	 type.  */
+      if (rel == VREL_EQ)
+        return true;
+    }
+
   int_range_max vr0, vr1;
   if (!query->range_of_expr (vr0, op0, s) || vr0.undefined_p ())
     vr0.set_varying (TREE_TYPE (op0));
@@ -96,6 +109,25 @@ check_for_binary_op_overflow (range_quer
   tree vr1min = wide_int_to_tree (TREE_TYPE (op1), vr1.lower_bound ());
   tree vr1max = wide_int_to_tree (TREE_TYPE (op1), vr1.upper_bound ());
 
+  /* If op1 is not negative, op0 - op1 in infinite precision for op0 >= op1
+     will be always in [0, op0] and so if vr0max - vr1min fits into type,
+     there won't be any overflow.  */
+  if ((rel == VREL_GT || rel == VREL_GE)
+      && tree_int_cst_sgn (vr1min) >= 0
+      && !arith_overflowed_p (MINUS_EXPR, type, vr0max, vr1min))
+    return true;
+
+  /* If op1 is not negative, op0 - op1 in infinite precision for op0 < op1
+     will be always in [-inf, -1] and so will always overflow if type is
+     unsigned.  */
+  if (rel == VREL_LT
+      && tree_int_cst_sgn (vr1min) >= 0
+      && TYPE_UNSIGNED (type))
+    {
+      *ovf = true;
+      return true;
+    }
+
   *ovf = arith_overflowed_p (subcode, type, vr0min,
 			     subcode == MINUS_EXPR ? vr1max : vr1min);
   if (arith_overflowed_p (subcode, type, vr0max,


	Jakub
  
Jeffrey Law Feb. 13, 2025, 11:46 p.m. UTC | #9
On 2/12/25 2:22 PM, Jakub Jelinek wrote:
> 
>> I agree that the most common cases should be all the arguments the same
>> type.  I was working under the assumption that the args would be compatible
>> types already, forgetting that IFNs are different in that regard than other
>> gimple ops.  I wouldn't want to go any further than all three operands the
>> same with the easy to reason about relation checks.
>>
>>
>> For gcc-16 I think we can extend that block fairly easily to handle certain
>> mismatched size cases and we look to see if there's cases where the
>> combination of a relationship between the arguments and some range
>> information would allow us to capture further cases.
> 
> For the GCC 16 version, I think best would be (given Andrew's mail that
> the relations aren't likely very useful for incompatible types) to
>    relation_kind rel = VREL_VARYING;
>    if (code == MINUS_EXPR
>        && types_compatible_p (TREE_TYPE (op0), TREE_TYPE (op1))
>      {
>        rel = query->relation().query (s, op0, op1);
>        /* The result of the infinite precision subtraction of
> 	 the same values will be always 0.  That will fit into any result
> 	 type.  */
>        if (rel == VREL_EQ)
> 	return true;
>      }
> 
> then do the current
>    int_range_max vr0, vr1;
>    if (!query->range_of_expr (vr0, op0, s) || vr0.undefined_p ())
>      vr0.set_varying (TREE_TYPE (op0));
>    if (!query->range_of_expr (vr1, op1, s) || vr1.undefined_p ())
>      vr1.set_varying (TREE_TYPE (op1));
> 
>    tree vr0min = wide_int_to_tree (TREE_TYPE (op0), vr0.lower_bound ());
>    tree vr0max = wide_int_to_tree (TREE_TYPE (op0), vr0.upper_bound ());
>    tree vr1min = wide_int_to_tree (TREE_TYPE (op1), vr1.lower_bound ());
>    tree vr1max = wide_int_to_tree (TREE_TYPE (op1), vr1.upper_bound ());
> 
> and then we can e.g. special case > and >=:
>    /* If op1 is not negative, op0 - op1 for op0 >= op1 will be always
>       in [0, op0] and so if vr0max - vr1min fits into type, there won't
>       be any overflow.  */
>    if ((rel == VREL_GT || rel == VREL_GE)
>        && tree_int_cst_sgn (vr1min) >= 0
>        && !arith_overflowed_p (MINUS_EXPR, type, vr0max, vr1min))
>      return true;
> 
> Would need to think about if anything could be simplified for
> VREL_G{T,E} if tree_int_cst_sgn (vr1min) < 0.
> 
> As for VREL_LT, one would need to think it through as well for both
> tree_int_cst_sgn (vr1min) >= 0 and tree_int_cst_sgn (vr1min) < 0.
> For the former, the infinite precision of subtraction is known given
> the relation to be < 0.  Now obviously if TYPE_UNSIGNED (type) that
> would imply always overflow.  But for !TYPE_UNSIGNED (type) that isn't
> necessarily the case and the question is if the relation helps with the
> reasoning.  Generally the code otherwise tries to check 2 boundaries
> (for MULT_EXPR 4 but we don't care about that), if they both don't overflow,
> it is ok, if only one overflows, we don't know, if both boundaries don't
> overflow, we need to look further and check some corner cases in between.
> 
> Or just go with that even for GCC 15 (completely untested and dunno if
> something needs to be done about s = NULL passed to query or not) for
> now, with the advantage that it can do something even for the cases where
> type is not compatible with types of arguments, and perhaps add additional
> cases later?
This is further than I wanted to go for gcc-15.  But I can support 
something like this as it's not a major extension to what I was 
suggesting.  And of course it addresses the correctness issues around 
different types.  I'll play with it a bit.

And WRT an earlier message about gcc-16.  Yea, I think opening a bug for 
additional cases would be a good idea.

Jeff
  
Jeffrey Law Feb. 15, 2025, 11:52 p.m. UTC | #10
On 2/12/25 2:22 PM, Jakub Jelinek wrote:

> 
> Or just go with that even for GCC 15 (completely untested and dunno if
> something needs to be done about s = NULL passed to query or not) for
> now, with the advantage that it can do something even for the cases where
> type is not compatible with types of arguments, and perhaps add additional
> cases later?
I added the check for s being non-null and made a trivial fix to your 
patch (IIRC you used "code" when it should have been "subcode").

Do you think there's still value in opening a new non-regression bug for 
additional cases?  I think your patch covered the ones I figured we 
would be most likely to handle.

Thanks again!

Jeff
  
Jakub Jelinek Feb. 24, 2025, 7:36 p.m. UTC | #11
On Sat, Feb 15, 2025 at 04:52:58PM -0700, Jeff Law wrote:
> On 2/12/25 2:22 PM, Jakub Jelinek wrote:
> 
> > 
> > Or just go with that even for GCC 15 (completely untested and dunno if
> > something needs to be done about s = NULL passed to query or not) for
> > now, with the advantage that it can do something even for the cases where
> > type is not compatible with types of arguments, and perhaps add additional
> > cases later?
> I added the check for s being non-null and made a trivial fix to your patch
> (IIRC you used "code" when it should have been "subcode").
> 
> Do you think there's still value in opening a new non-regression bug for
> additional cases?

I actually can't think of any further cases right now, so I think no need to
open a PR, just commit the patch ;)

	Jakub
  

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr98028.c b/gcc/testsuite/gcc.dg/tree-ssa/pr98028.c
new file mode 100644
index 00000000000..4e371b69235
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr98028.c
@@ -0,0 +1,26 @@ 
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+unsigned f1(unsigned i, unsigned j) {
+  if (j != i) __builtin_unreachable();
+  return __builtin_sub_overflow_p(i, j, (unsigned)0);
+}
+
+unsigned f2(unsigned i, unsigned j) {
+  if (j > i) __builtin_unreachable();
+  return __builtin_sub_overflow_p(i, j, (unsigned)0);
+}
+
+unsigned f3(unsigned i, unsigned j) {
+  if (j >= i) __builtin_unreachable();
+  return __builtin_sub_overflow_p(i, j, (unsigned)0);
+}
+
+unsigned f4(unsigned i, unsigned j) {
+  if (j <= i) __builtin_unreachable();
+  return __builtin_sub_overflow_p(i, j, (unsigned)0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 3 optimized } } */
+/* { dg-final { scan-tree-dump-times "return 1" 1 optimized } } */
+/* { dg-final { scan-tree-dump-not "SUB_OVERFLOW" optimized } } */
+/* { dg-final { scan-tree-dump-not "IMAGPART_EXPR" optimized } } */
diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
index ed590138fe8..29568e27c38 100644
--- a/gcc/vr-values.cc
+++ b/gcc/vr-values.cc
@@ -85,6 +85,33 @@  check_for_binary_op_overflow (range_query *query,
 			      enum tree_code subcode, tree type,
 			      tree op0, tree op1, bool *ovf, gimple *s = NULL)
 {
+  /* For MINUS_EXPR, we may know based the relationship
+     (if any) between op0 and op1.  */
+  if (subcode == MINUS_EXPR)
+    {
+      relation_kind rel = query->relation().query (s, op0, op1);
+
+      /* If the operands are equal, then the result will be zero
+	 and there is never an overflow.  */
+      if (rel == VREL_EQ)
+	return true;
+
+      /* If op0 and op1 are unsigned types, we still have a chance.  */
+      if (TYPE_UNSIGNED (TREE_TYPE (op0)) && TYPE_UNSIGNED (TREE_TYPE (op1)))
+	{
+	  /* op0 > op1 or op0 >= op1 never overflows.  */
+	  if (rel == VREL_GT || rel == VREL_GE)
+	    return true;
+
+	  /* And op0 < op1 always overflows.  */
+	  if (rel == VREL_LT)
+	    {
+	      *ovf = true;
+	      return true;
+	    }
+	}
+    }
+	
   int_range_max vr0, vr1;
   if (!query->range_of_expr (vr0, op0, s) || vr0.undefined_p ())
     vr0.set_varying (TREE_TYPE (op0));