[2/2] Add VREL_OTHER for FP unsupported relations.

This patch adds VREL_OTHER to represent another relation we do not 
understand.  It is used to represent the class fo relations arising from 
floating point that are currently not represented. IN GCC 14 we will 
determine exactly how to represent them, but for this release, this 
should prevent us from getting things wrong at least.

if intersection produces UNDEFINED and either of the relations feeding 
it were <, <=, >, or >=   then it turns it to VR_OTHER.   the prevents 
false sides of branches from combining to produce  UNDEFINED when they 
end up being a known NAN.

Union is adjusted such that < >, or <= >= also produce VREL_OTHER.   < > 
cannot be properly represented, and <= >= was producing VARYING, which 
is also not correct.

Form the testcase:

     <bb 2> :
     cmp1_10 = x_8(D) <= y_9(D);
     cmp2_11 = x_8(D) >= y_9(D);
     _3 = cmp1_10 & cmp2_11;
     if (_3 != 0)
       goto <bb 3>; [INV]
     else
       goto <bb 4>; [INV]

Relational : (x_8(D) == y_9(D))
     <bb 3> :
     // predicted unlikely by early return (on trees) predictor.
     goto <bb 6>; [INV]


     <bb 4> :
     _4 = ~cmp1_10;
     _5 = ~cmp2_11;
     _1 = cmp1_10 | cmp2_11;
     _6 = ~_1;
     if (_1 != 0)
       goto <bb 6>; [INV]
     else
       goto <bb 5>; [INV]

Relational : (x_8(D) unknown fp y_9(D))
     <bb 5> :
     // predicted unlikely by early return (on trees) predictor.


The intersection "fix" is represented by the relation between x and y in 
BB5.  Without the patch, ti would be UNDEFINED and we do not want that.

The union fix is what prevents us from folding the condition in bb_4.  
Without it, x<=y union x >=y comes out VARYING, when in fact I believe 
it represents everything except a NAN.

So with this fix, all the unrepresentative relations get lumped into 
VREL_OTHER so we at least don't get it wrong.  For next release we can 
take the time to figure out exactly how we want to proceed.

This is currently in testing on x86_64-pc-linux-gnu, and assuming it 
bootstraps with no regressions (a combined patch did before splitting it 
in 2), OK for trunk?   OR does it need more tweaking?

Andrew

Sorry should have mention the PR

On 1/23/23 12:44, Andrew MacLeod wrote:
> This patch adds VREL_OTHER to represent another relation we do not 
> understand.  It is used to represent the class fo relations arising 
> from floating point that are currently not represented. IN GCC 14 we 
> will determine exactly how to represent them, but for this release, 
> this should prevent us from getting things wrong at least.
>
> if intersection produces UNDEFINED and either of the relations feeding 
> it were <, <=, >, or >=   then it turns it to VR_OTHER.   the prevents 
> false sides of branches from combining to produce  UNDEFINED when they 
> end up being a known NAN.
>
> Union is adjusted such that < >, or <= >= also produce VREL_OTHER.   < 
> > cannot be properly represented, and <= >= was producing VARYING, 
> which is also not correct.
>
> Form the testcase:
>
>     <bb 2> :
>     cmp1_10 = x_8(D) <= y_9(D);
>     cmp2_11 = x_8(D) >= y_9(D);
>     _3 = cmp1_10 & cmp2_11;
>     if (_3 != 0)
>       goto <bb 3>; [INV]
>     else
>       goto <bb 4>; [INV]
>
> Relational : (x_8(D) == y_9(D))
>     <bb 3> :
>     // predicted unlikely by early return (on trees) predictor.
>     goto <bb 6>; [INV]
>
>
>     <bb 4> :
>     _4 = ~cmp1_10;
>     _5 = ~cmp2_11;
>     _1 = cmp1_10 | cmp2_11;
>     _6 = ~_1;
>     if (_1 != 0)
>       goto <bb 6>; [INV]
>     else
>       goto <bb 5>; [INV]
>
> Relational : (x_8(D) unknown fp y_9(D))
>     <bb 5> :
>     // predicted unlikely by early return (on trees) predictor.
>
>
> The intersection "fix" is represented by the relation between x and y 
> in BB5.  Without the patch, ti would be UNDEFINED and we do not want 
> that.
>
> The union fix is what prevents us from folding the condition in bb_4.  
> Without it, x<=y union x >=y comes out VARYING, when in fact I believe 
> it represents everything except a NAN.
>
> So with this fix, all the unrepresentative relations get lumped into 
> VREL_OTHER so we at least don't get it wrong.  For next release we can 
> take the time to figure out exactly how we want to proceed.
>
> This is currently in testing on x86_64-pc-linux-gnu, and assuming it 
> bootstraps with no regressions (a combined patch did before splitting 
> it in 2), OK for trunk?   OR does it need more tweaking?
>
> Andrew

On Mon, Jan 23, 2023 at 6:44 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> This patch adds VREL_OTHER to represent another relation we do not
> understand.  It is used to represent the class fo relations arising from
> floating point that are currently not represented. IN GCC 14 we will
> determine exactly how to represent them, but for this release, this
> should prevent us from getting things wrong at least.
>
> if intersection produces UNDEFINED and either of the relations feeding
> it were <, <=, >, or >=   then it turns it to VR_OTHER.   the prevents
> false sides of branches from combining to produce  UNDEFINED when they
> end up being a known NAN.
>
> Union is adjusted such that < >, or <= >= also produce VREL_OTHER.   < >
> cannot be properly represented, and <= >= was producing VARYING, which
> is also not correct.
>
> Form the testcase:
>
>      <bb 2> :
>      cmp1_10 = x_8(D) <= y_9(D);
>      cmp2_11 = x_8(D) >= y_9(D);
>      _3 = cmp1_10 & cmp2_11;
>      if (_3 != 0)
>        goto <bb 3>; [INV]
>      else
>        goto <bb 4>; [INV]
>
> Relational : (x_8(D) == y_9(D))
>      <bb 3> :
>      // predicted unlikely by early return (on trees) predictor.
>      goto <bb 6>; [INV]
>
>
>      <bb 4> :
>      _4 = ~cmp1_10;
>      _5 = ~cmp2_11;
>      _1 = cmp1_10 | cmp2_11;
>      _6 = ~_1;
>      if (_1 != 0)
>        goto <bb 6>; [INV]
>      else
>        goto <bb 5>; [INV]
>
> Relational : (x_8(D) unknown fp y_9(D))
>      <bb 5> :
>      // predicted unlikely by early return (on trees) predictor.
>
>
> The intersection "fix" is represented by the relation between x and y in
> BB5.  Without the patch, ti would be UNDEFINED and we do not want that.
>
> The union fix is what prevents us from folding the condition in bb_4.
> Without it, x<=y union x >=y comes out VARYING, when in fact I believe
> it represents everything except a NAN.
>
> So with this fix, all the unrepresentative relations get lumped into
> VREL_OTHER so we at least don't get it wrong.  For next release we can
> take the time to figure out exactly how we want to proceed.
>
> This is currently in testing on x86_64-pc-linux-gnu, and assuming it
> bootstraps with no regressions (a combined patch did before splitting it
> in 2), OK for trunk?   OR does it need more tweaking?

LGTM, I'd appreciate a 2nd eye though - you've gone through all the
pecularities of combining FP relations in the PRs audit trail.

Richard.

>
> Andrew

On Mon, Jan 23, 2023 at 12:44:48PM -0500, Andrew MacLeod wrote:
> @@ -784,17 +794,28 @@ value_relation::negate ()
>  bool
>  value_relation::intersect (const value_relation &p)
>  {
> -  // Save previous value
> -  relation_kind old = related;
> +  relation_kind k;
>  
>    if (p.op1 () == op1 () && p.op2 () == op2 ())
> -    related = relation_intersect (kind (), p.kind ());
> +    k = relation_intersect (kind (), p.kind ());
>    else if (p.op2 () == op1 () && p.op1 () == op2 ())
> -    related = relation_intersect (kind (), relation_swap (p.kind ()));
> +    k = relation_intersect (kind (), relation_swap (p.kind ()));
>    else
>      return false;
>  
> -  return old != related;
> +  if (related == k)
> +    return false;
> +
> +  bool float_p = name1 && FLOAT_TYPE_P (TREE_TYPE (name1));
> +  if (float_p && p.kind () != k && k == VREL_UNDEFINED)
> +    {
> +      if (relation_lt_le_gt_ge_p (kind ())
> +	  || relation_lt_le_gt_ge_p (p.kind ()))
> +	k = VREL_OTHER;
> +    }

I don't understand this.

When at least one of the relations is VREL_{L,G}{T,E} and intersection
is VREL_UNDEFINED, it means other relation is VREL_UNDEFINED (but then
VREL_UNDEFINED is the right range to return), or one is VREL_{L,G}T
and the other is VREL_EQ (x > y && x == y, again, VREL_UNDEFINED is
the right answer, no ordered pair of x and y is greater (or less) and
equal at the same time and for unordered (at least one NaN) both
relations are false), or it is VREL_LT vs. VREL_G{T,E} or vice versa
or VREL_GT vs. VREL_L{T,E} or vice versa
(x < y && x >= y again, for ordered pairs of x and y it is never
true, if any is NaN, neither comparison is true).

I don't think you need to do anything floating point related in intersect.
It might seem to be inconsistent with union, but that is just because
VREL_OTHER is the union of VREL_LTGT, VREL_ORDERED, VREL_UNORDERED,
VREL_UNLT, VREL_UNGT, VREL_UNGT, VREL_UNGE and VREL_UNEQ, if we had
those 8 in addition to the current 8 non-PE ones you'd see that for
intersections one only gets the new codes when fp with possible
NANs and at least one of the intersection operand is one of the new
codes.  In the VREL_OTHER world, simply VREL_OTHER intersected with
anything but VREL_UNDEFINED is VREL_OTHER.

> +  // (x < y) || (x > y) produces x != y, but this is not true with floats.
> +  // (x <= y) || (x >= y) produces VARYING, which is also not true for floats.

This misses a couple of needed cases both in this comment and
in the actual implementation.  In particular, the first comment
line is right, x < y || x > y is the only one where we get
VREL_NE and want VREL_OTHER (VREL_LTGT maybe later).
x <= y || x >= y is just one of the cases which produce VREL_VARYING
and we want VREL_OTHER (VREL_ORDERED maybe later) though,
x < y || x >= y
x <= y || x > y
are the others where from the current tables you also get
VREL_VARYING but want VREL_OTHER (VREL_ORDERED eventually).

> +  // As they cannot be properly represented, use VREL_OTHER.
> +  bool float_p = name1 && FLOAT_TYPE_P (TREE_TYPE (name1));

This should be
  bool float_p = name1 && HONOR_NANS (TREE_TYPE (name1));
If it is not floating point mode, it will be false, if it is
floating point mode which doesn't have NANs in hw, it also behaves
the same relation-wise, and lastly if hw supports NANs but user
uses -ffast-math or -ffinite-math-only, the user guaranteed that
the operands will never be NAN (nor +-INF), which means that
again relation behave like the integral/pointer ones, there is
no 4th possible outcome of a comparison.

> +  if (float_p && p.kind () != k)
> +    {
> +      if (kind () == VREL_LT && p.kind () == VREL_GT)
> +	k = VREL_OTHER;
> +      else if (kind () == VREL_GT && p.kind () == VREL_LT)
> +	k = VREL_OTHER;
> +      else if (kind () == VREL_LE && p.kind () == VREL_GE)
> +	k = VREL_OTHER;
> +      else if (kind () == VREL_GE && p.kind () == VREL_LE)
> +	k = VREL_OTHER;

And as written above, this misses the VREL_LT vs. VREL_GE or
VREL_GE vs. VREL_LT or VREL_GT vs. VREL_LE or VREL_LE vs. VREL_GT
cases.
I think it is easier written as
  if (k == VREL_VARYING
      && relation_lt_le_gt_ge_p (kind ())
      && relation_lt_le_gt_ge_p (p.kind ()))
    k = VREL_OTHER;
Only when/if we'll want to differentiate between VREL_LTGT for
VREL_LT vs. VREL_GT or VREL_GT vs. VREL_LT and VREL_ORDERED
for the others we will need something different.

> --- a/gcc/value-relation.h
> +++ b/gcc/value-relation.h
> @@ -70,6 +70,7 @@ typedef enum relation_kind_t
>    VREL_GE,		// r1 >= r2
>    VREL_EQ,		// r1 == r2
>    VREL_NE,		// r1 != r2
> +  VREL_OTHER,		// unrepresentatble floating point relation.

s/unrepresentatble/unrepresentable/

>    VREL_PE8,		// 8 bit partial equivalency
>    VREL_PE16,		// 16 bit partial equivalency
>    VREL_PE32,		// 32 bit partial equivalency

Otherwise LGTM (i.e. I agree with VREL_OTHER introduction for now)
and the intersect/union tables look good too (I must say I don't understand
much the transitive table - how that compares to the intersect one, but
that isn't problem in the code, just on my side).

	Jakub

On 1/24/23 05:05, Jakub Jelinek wrote:
> On Mon, Jan 23, 2023 at 12:44:48PM -0500, Andrew MacLeod wrote:
>> @@ -784,17 +794,28 @@ value_relation::negate ()
>>   bool
>>   value_relation::intersect (const value_relation &p)
>>   {
>> -  // Save previous value
>> -  relation_kind old = related;
>> +  relation_kind k;
>>   
>>     if (p.op1 () == op1 () && p.op2 () == op2 ())
>> -    related = relation_intersect (kind (), p.kind ());
>> +    k = relation_intersect (kind (), p.kind ());
>>     else if (p.op2 () == op1 () && p.op1 () == op2 ())
>> -    related = relation_intersect (kind (), relation_swap (p.kind ()));
>> +    k = relation_intersect (kind (), relation_swap (p.kind ()));
>>     else
>>       return false;
>>   
>> -  return old != related;
>> +  if (related == k)
>> +    return false;
>> +
>> +  bool float_p = name1 && FLOAT_TYPE_P (TREE_TYPE (name1));
>> +  if (float_p && p.kind () != k && k == VREL_UNDEFINED)
>> +    {
>> +      if (relation_lt_le_gt_ge_p (kind ())
>> +	  || relation_lt_le_gt_ge_p (p.kind ()))
>> +	k = VREL_OTHER;
>> +    }
> I don't understand this.
>
> When at least one of the relations is VREL_{L,G}{T,E} and intersection
> is VREL_UNDEFINED, it means other relation is VREL_UNDEFINED (but then
> VREL_UNDEFINED is the right range to return), or one is VREL_{L,G}T
> and the other is VREL_EQ (x > y && x == y, again, VREL_UNDEFINED is
> the right answer, no ordered pair of x and y is greater (or less) and
> equal at the same time and for unordered (at least one NaN) both
> relations are false), or it is VREL_LT vs. VREL_G{T,E} or vice versa
> or VREL_GT vs. VREL_L{T,E} or vice versa
> (x < y && x >= y again, for ordered pairs of x and y it is never
> true, if any is NaN, neither comparison is true).
>
> I don't think you need to do anything floating point related in intersect.
> It might seem to be inconsistent with union, but that is just because
> VREL_OTHER is the union of VREL_LTGT, VREL_ORDERED, VREL_UNORDERED,
> VREL_UNLT, VREL_UNGT, VREL_UNGT, VREL_UNGE and VREL_UNEQ, if we had
> those 8 in addition to the current 8 non-PE ones you'd see that for
> intersections one only gets the new codes when fp with possible
> NANs and at least one of the intersection operand is one of the new
> codes.  In the VREL_OTHER world, simply VREL_OTHER intersected with
> anything but VREL_UNDEFINED is VREL_OTHER.

That is the way VREL_OTHER is implemented in the table.

So the problem is not on the true side of the IF condition as in your 
example, its on the false side. We see this commonly in code like this


if (x <= y)     // FALSE side registers x > y
   blah()
else if (x >= y)  // FALSE side registers x < y
   blah()
else
   // Here we get VREL_UNDEFINED.

But for floating point, that is not true, this would be a known NAN 
based on my understanding of this.  If I understand correctly, the 
condition on the true side is explicitly true, but the false side is 
the  "false condition Union NAN".. which we cant represent.   but I 
don't think we want to always make that VREL_OTHER either.

So it seems we have to do one of two things...   either never produce 
UNDEFINED for floating point (unless one operand is explicitly UNDEFINED 
already), or on the false side of a condition, always produce a 
VREL_OTHER since its a relation and a NAN possible.   Of course, if the 
floating point code for the range-op relation operator knows the false 
side has no NAN, it could produce the appropriate relation then.

It seems to me the "easiest" to get right is to stop producing 
VREL_UNDEFINED for intersection?

Or am I reading something wrong?

>
>> +  // (x < y) || (x > y) produces x != y, but this is not true with floats.
>> +  // (x <= y) || (x >= y) produces VARYING, which is also not true for floats.
> This misses a couple of needed cases both in this comment and
> in the actual implementation.  In particular, the first comment
> line is right, x < y || x > y is the only one where we get
> VREL_NE and want VREL_OTHER (VREL_LTGT maybe later).
> x <= y || x >= y is just one of the cases which produce VREL_VARYING
> and we want VREL_OTHER (VREL_ORDERED maybe later) though,
> x < y || x >= y
> x <= y || x > y
> are the others where from the current tables you also get
> VREL_VARYING but want VREL_OTHER (VREL_ORDERED eventually).
>
>> +  // As they cannot be properly represented, use VREL_OTHER.
>> +  bool float_p = name1 && FLOAT_TYPE_P (TREE_TYPE (name1));
> This should be
>    bool float_p = name1 && HONOR_NANS (TREE_TYPE (name1));
> If it is not floating point mode, it will be false, if it is
> floating point mode which doesn't have NANs in hw, it also behaves
> the same relation-wise, and lastly if hw supports NANs but user
> uses -ffast-math or -ffinite-math-only, the user guaranteed that
> the operands will never be NAN (nor +-INF), which means that
> again relation behave like the integral/pointer ones, there is
> no 4th possible outcome of a comparison.
>
>> +  if (float_p && p.kind () != k)
>> +    {
>> +      if (kind () == VREL_LT && p.kind () == VREL_GT)
>> +	k = VREL_OTHER;
>> +      else if (kind () == VREL_GT && p.kind () == VREL_LT)
>> +	k = VREL_OTHER;
>> +      else if (kind () == VREL_LE && p.kind () == VREL_GE)
>> +	k = VREL_OTHER;
>> +      else if (kind () == VREL_GE && p.kind () == VREL_LE)
>> +	k = VREL_OTHER;
> And as written above, this misses the VREL_LT vs. VREL_GE or
> VREL_GE vs. VREL_LT or VREL_GT vs. VREL_LE or VREL_LE vs. VREL_GT
> cases.
> I think it is easier written as
>    if (k == VREL_VARYING
>        && relation_lt_le_gt_ge_p (kind ())
>        && relation_lt_le_gt_ge_p (p.kind ()))
>      k = VREL_OTHER;
> Only when/if we'll want to differentiate between VREL_LTGT for
> VREL_LT vs. VREL_GT or VREL_GT vs. VREL_LT and VREL_ORDERED
> for the others we will need something different.
>
OK, thats the way I originally had it, but for some reason thought it 
was only these cases.  I shall fix.  I still want to make sure that if 
one of the operands is already VARYING, it also remains VARYING.
>> --- a/gcc/value-relation.h
>> +++ b/gcc/value-relation.h
>> @@ -70,6 +70,7 @@ typedef enum relation_kind_t
>>     VREL_GE,		// r1 >= r2
>>     VREL_EQ,		// r1 == r2
>>     VREL_NE,		// r1 != r2
>> +  VREL_OTHER,		// unrepresentatble floating point relation.
> s/unrepresentatble/unrepresentable/
>
>>     VREL_PE8,		// 8 bit partial equivalency
>>     VREL_PE16,		// 16 bit partial equivalency
>>     VREL_PE32,		// 32 bit partial equivalency
> Otherwise LGTM (i.e. I agree with VREL_OTHER introduction for now)
> and the intersect/union tables look good too (I must say I don't understand
> much the transitive table - how that compares to the intersect one, but
> that isn't problem in the code, just on my side).
>
The transitive table simply adds an ERROR_MARK for VREL_OTHER, which 
means it will apply no transitivity if it sees VREL_OTHER.


Attached is an adjusted patch with your comments.   Plus I left in the 
intersection generally disallowing UNDEFINED as I'm discussed above. If 
I have failed to convince you that is needed, then I am probably just 
misunderstanding and I will pull it out :-)

Andrew

On Tue, Jan 24, 2023 at 10:57:12AM -0500, Andrew MacLeod wrote:
> That is the way VREL_OTHER is implemented in the table.
> 
> So the problem is not on the true side of the IF condition as in your
> example, its on the false side. We see this commonly in code like this
> 
> 
> if (x <= y)     // FALSE side registers x > y
>   blah()
> else if (x >= y)  // FALSE side registers x < y
>   blah()
> else
>   // Here we get VREL_UNDEFINED.

In that case, I think the problem isn't in the intersection, which works
correctly, but in wherever we (again, for HONOR_NANS (type) only) make the
assumptions about the else branches.
In the above case, the first blah has VREL_LE, that is correct,
but the else of it (when the condition isn't true but is false)
isn't VREL_GT, but VREL_UNGT (aka VREL_OTHER).
So, for the HONOR_NANS (type) cases we need to adjust relation_negate
callers.
On trees, you can e.g. look at fold-const.cc (invert_tree_comparison),
though that one for HONOR_NANS (type) && flag_trapping_math punts in most
cases to preserve exceptions.  But you can see there the !honor_nans
cases where it acts like relation_negate, and then the honor_nans cases,
where VREL_*:
VARYING UNDEFINED LT LE GT GE EQ NE LTGT ORDERED UNORDERED UNLT UNLE UNGT UNGE UNEQ
negate to
UNDEFINED VARYING UNGE UNGT UNLE UNLT NE EQ UNEQ UNORDERED ORDERED GE GT LE LT LTGT
Or, in the world where VREL_OTHER is a wildcard for
LTGT ORDERED UNORDERED UNLT UNLE UNGT UNGE UNEQ
the less useful
VARYING UNDEFINED LT LE GT GE EQ NE OTHER
negates to
UNDEFINED VARYING OTHER OTHER OTHER OTHER NE EQ OTHER

But I'm afraid the above has VREL_OTHER for too many important cases,
unlike intersect where it is for none unless VREL_OTHER is involved, or just
a few ones for union.

So, I wonder if we just shouldn't do it properly immediately and instead of
VREL_OTHER introduce those
VREL_LTGT,	/* Less than or greater than.  */
VREL_ORDERED,	/* Operands not NAN.  */
VREL_UNORDERED, /* One or both operands NAN.  */
VREL_UNLT,	/* Unordered or less than.  */
VREL_UNLE,	/* Unordered or less than or equal.  */
VREL_UNGT,	/* Unordered or greater than.  */
VREL_UNGE,	/* Unordered or greater than or equal.  */
VREL_UNEQ	/* Unordered or equal.  */
In that case, rather than using relation_{negate,union,intersect} etc.
either those functions should take an argument whether it is a HONOR_NANS
(type) floating point or not and use two separate tables under the hood,
or have two sets of routines and choose which one to use in the callers.
I think one routine with an extra argument would be cleaner though.

The above would grow the tables quite a bit (though, we could for the
non-FP cases limit ourselves to a subset), but because all the VREL_*
constants are enumerals with small integers values and the arrays
should be (but aren't for some reason?) static just make the arrays
contain unsigned char and do the casts to the enum in the
relation_{negate,intersect,union} etc. wrappers.
Also, I think the rr_*_table arrays should be const, we don't want to change
them, right?  And a few other arrays too, like relation_to_code.
BTW, with the above extra 8 codes we could use the ORDERED_EXPR etc. tree
codes there.

	Jakub

On 1/25/23 06:15, Jakub Jelinek wrote:
> On Tue, Jan 24, 2023 at 10:57:12AM -0500, Andrew MacLeod wrote:
>> That is the way VREL_OTHER is implemented in the table.
>>
>> So the problem is not on the true side of the IF condition as in your
>> example, its on the false side. We see this commonly in code like this
>>
>>
>> if (x <= y)     // FALSE side registers x > y
>>    blah()
>> else if (x >= y)  // FALSE side registers x < y
>>    blah()
>> else
>>    // Here we get VREL_UNDEFINED.
> In that case, I think the problem isn't in the intersection, which works
> correctly, but in wherever we (again, for HONOR_NANS (type) only) make the
> assumptions about the else branches.
> In the above case, the first blah has VREL_LE, that is correct,
> but the else of it (when the condition isn't true but is false)
> isn't VREL_GT, but VREL_UNGT (aka VREL_OTHER).
> So, for the HONOR_NANS (type) cases we need to adjust relation_negate
> callers.
> On trees, you can e.g. look at fold-const.cc (invert_tree_comparison),
> though that one for HONOR_NANS (type) && flag_trapping_math punts in most
> cases to preserve exceptions.  But you can see there the !honor_nans
> cases where it acts like relation_negate, and then the honor_nans cases,
> where VREL_*:
> VARYING UNDEFINED LT LE GT GE EQ NE LTGT ORDERED UNORDERED UNLT UNLE UNGT UNGE UNEQ
> negate to
> UNDEFINED VARYING UNGE UNGT UNLE UNLT NE EQ UNEQ UNORDERED ORDERED GE GT LE LT LTGT
> Or, in the world where VREL_OTHER is a wildcard for
> LTGT ORDERED UNORDERED UNLT UNLE UNGT UNGE UNEQ
> the less useful
> VARYING UNDEFINED LT LE GT GE EQ NE OTHER
> negates to
> UNDEFINED VARYING OTHER OTHER OTHER OTHER NE EQ OTHER
>
> But I'm afraid the above has VREL_OTHER for too many important cases,
> unlike intersect where it is for none unless VREL_OTHER is involved, or just
> a few ones for union.

Im not sure it is quite that bad.   Floating point ranges and range-ops 
does a pretty good job of tracking NANs in the ranges. They then utilize 
any available relation in addition to that. So within floating point 
processing, all our relations are assumed to possibly include NAN, then 
the range processing in range-ops decides which variant of the relation 
is applicable.  When Aldy and I went thru this exercise initally, we 
concluded we didnt need all the various forms of relations, that its was 
completely isolated within the frange implementation.. which is ideal.

The only place this is causing real "trouble" is within ranger where we 
pre-fold a stmt based on the relation, without it ever getting to 
rangeops.  Yes,we dont represent <> or ordered or unordered in the 
relation table, but those are really very specific floating point things 
and ranger doesnt need to be aware of them anyway I don't think.  theres 
not much it can do with them.

Merge points use union and cascading conditions use intersection.  The 
current fix will eliminate ranger from making any presumptions about 
these cases early.  Those are about the only things ranger itself uses 
relations for.. everything else is deferred to range-ops which 
understands all the things like ordered/unordered etc and it will still 
fold these expression properly when evaluated.

ie  without any relational representation of unordered and unordered, we 
still fold this properly because frange tracks it all:

   if (x_2(D) unord x_2(D))
     goto <bb 3>; [INV]
   else
     goto <bb 5>; [INV]

   <bb 3> :
   if (x_2(D) ord x_2(D))
     goto <bb 4>; [INV]
   else
     goto <bb 5>; [INV]

   <bb 4> :
   link_error ();

and value relations don't need to be involved.  I am currently unaware 
of anything with floating point relations we don't track properly in the 
end.


> So, I wonder if we just shouldn't do it properly immediately and instead of
> VREL_OTHER introduce those
> VREL_LTGT,	/* Less than or greater than.  */
> VREL_ORDERED,	/* Operands not NAN.  */
> VREL_UNORDERED, /* One or both operands NAN.  */
> VREL_UNLT,	/* Unordered or less than.  */
> VREL_UNLE,	/* Unordered or less than or equal.  */
> VREL_UNGT,	/* Unordered or greater than.  */
> VREL_UNGE,	/* Unordered or greater than or equal.  */
> VREL_UNEQ	/* Unordered or equal.  */
> In that case, rather than using relation_{negate,union,intersect} etc.
> either those functions should take an argument whether it is a HONOR_NANS
> (type) floating point or not and use two separate tables under the hood,
> or have two sets of routines and choose which one to use in the callers.
> I think one routine with an extra argument would be cleaner though.
>
> The above would grow the tables quite a bit (though, we could for the
> non-FP cases limit ourselves to a subset), but because all the VREL_*
> constants are enumerals with small integers values and the arrays
> should be (but aren't for some reason?) static just make the arrays
> contain unsigned char and do the casts to the enum in the
> relation_{negate,intersect,union} etc. wrappers.
> Also, I think the rr_*_table arrays should be const, we don't want to change
> them, right?  And a few other arrays too, like relation_to_code.
> BTW, with the above extra 8 codes we could use the ORDERED_EXPR etc. tree
> codes there.
>
I am very hesitant about implementing full relations for all these 
floating point specific things when
   a) I'm not convinced we need them and

   b) its a much more invasive change at the stage of the release.  
Every floating point range-op relational entry will have to be adjusted, 
and Im not sure of the ripple effects, especially since frange does a 
lot of its won things with the relational entries.

So far this fix is for ranger to avoid doing something its not suppose 
to.  Are we aware of any cases where we aren't handling a floating point 
relation fold that we should?   I would hate to complicate all the 
relation handling if we don't need to.  It may mean we need something 
else.. but its unclear to me exactly what we do minimally need at this 
point.. I was hoping to do that early in stage 1.

Aldy understand frange better than I do, maybe he can chip in about what 
we might or might not be missing without any of those other codes...

Andrew

On Wed, Jan 25, 2023 at 09:30:44AM -0500, Andrew MacLeod wrote:
> > But I'm afraid the above has VREL_OTHER for too many important cases,
> > unlike intersect where it is for none unless VREL_OTHER is involved, or just
> > a few ones for union.
> 
> Im not sure it is quite that bad.   Floating point ranges and range-ops does
> a pretty good job of tracking NANs in the ranges. They then utilize any
> available relation in addition to that. So within floating point processing,

What I meant is that when we need to (and we have to, trying to do some
weird changes in intersect doesn't really improve anything) change the
relation_negate or its callers of a relation for floating point with
possible NANs from current inversion of VREL_{LT,GT,LE,GE} which are quite
frequent to VREL_OTHER (I don't know), it can affect a lot of code.

Now, sure, we could try to improve the situation a little bit by not
using just HONOR_NANS (type) as the decider whether we need the new 16
cases VREL_* handling (or 8 + VREL_OTHER) or whether we can use just the 8
cases VREL_* handling.  Because, if HONOR_NANS (type) and frange can prove
that neither operand is maybe_nan and neither operand is known_nan, then
we can also use just the old 8 VREL_* codes and their relationships.
And perhaps if either operand is known_nan, then on the other side we know
it is VREL_OTHER (VREL_UNORDERED), not anything else.
Though, exactly for this I'd say it is more work and something for GCC 14.

Proper handling of relation_negate is I'm afraid required for GCC 13.

	Jakub

On 1/25/23 09:48, Jakub Jelinek wrote:
> On Wed, Jan 25, 2023 at 09:30:44AM -0500, Andrew MacLeod wrote:
>>> But I'm afraid the above has VREL_OTHER for too many important cases,
>>> unlike intersect where it is for none unless VREL_OTHER is involved, or just
>>> a few ones for union.
>> Im not sure it is quite that bad.   Floating point ranges and range-ops does
>> a pretty good job of tracking NANs in the ranges. They then utilize any
>> available relation in addition to that. So within floating point processing,
> What I meant is that when we need to (and we have to, trying to do some
> weird changes in intersect doesn't really improve anything) change the
> relation_negate or its callers of a relation for floating point with
> possible NANs from current inversion of VREL_{LT,GT,LE,GE} which are quite
> frequent to VREL_OTHER (I don't know), it can affect a lot of code.
>
> Now, sure, we could try to improve the situation a little bit by not
> using just HONOR_NANS (type) as the decider whether we need the new 16
> cases VREL_* handling (or 8 + VREL_OTHER) or whether we can use just the 8
> cases VREL_* handling.  Because, if HONOR_NANS (type) and frange can prove
> that neither operand is maybe_nan and neither operand is known_nan, then
> we can also use just the old 8 VREL_* codes and their relationships.
> And perhaps if either operand is known_nan, then on the other side we know
> it is VREL_OTHER (VREL_UNORDERED), not anything else.
> Though, exactly for this I'd say it is more work and something for GCC 14.
>
> Proper handling of relation_negate is I'm afraid required for GCC 13.
>

Except we don't actually use relation_negate () anywhere...  I can 
delete the functions in class value_relation and value-relation.h/cc and 
everything compiles fine.  Its provided because I figured it would be 
used someday, but the range-ops handlers simply issues the appropriate 
relation for the LHS.. be it true or false.  they don't pick one and 
negate it to produce the other.

I think you are missing that the VREL_* relation is not the end result 
used to calculate things, merely a tag that used by the range-ops 
handlers to assist with understanding un-obvious relations between 
operands on the stmt.

This change is mostly for the benefit of the one place in ranger where 
its slightly beyond range-ops..  when we have 2 conditions feeding and 
logical && or ||, we look to see if there is any common ground/relation 
between the operands feeding the logical operation:

//   c_2 = a_6 > b_7
//   c_3 = a_6 < b_7
//   c_4 = c_2 && c_3
// c_2 and c_3 can never be true at the same time,
// Therefore c_4 can always resolve to false based purely on the relations.
void fold_using_range::relation_fold_and_or (irange& lhs_range, gimple 
*s, fur_source &src)

Range-ops is unable to do anything with this as it requires examining 
things from outside the statement, and is not easily communicated a 
simple relation to operator_logical_and.

THIs routine proceeds to look at the defintions of c_2 and c_3, tries to 
determine if there are common operands, and queries for any relations 
between them.   If it turns out, this is something, we use intersection 
or fold to determine if the result of the logical operation can be 
folded.   THis fix is almost exclusively about that.

In GCC13, I don't think there are any uses of the relation oracle 
outside of ranger and range-ops.

So, given that, perhaps the simplest thing to do is bail on all this 
change, and instead simply do the following which also fixes the PR. (im 
running it thru tests as we speak)



diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 91eb6298254..9c5359a3fc6 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -1039,6 +1039,9 @@ fold_using_range::relation_fold_and_or (irange& 
lhs_range, gimple *s,
    if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
      return;

+  if (HONOR_NANS (TREE_TYPE (ssa1_dep1)))
+    return;
+
    // Make sure they are the same dependencies, and detect the order of the
    // relationship.
    bool reverse_op2 = true;

On Wed, Jan 25, 2023 at 11:12:11AM -0500, Andrew MacLeod via Gcc-patches wrote:
> In GCC13, I don't think there are any uses of the relation oracle outside of
> ranger and range-ops.
> 
> So, given that, perhaps the simplest thing to do is bail on all this change,
> and instead simply do the following which also fixes the PR. (im running it
> thru tests as we speak)
> 
> 
> 
> diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
> index 91eb6298254..9c5359a3fc6 100644
> --- a/gcc/gimple-range-fold.cc
> +++ b/gcc/gimple-range-fold.cc
> @@ -1039,6 +1039,9 @@ fold_using_range::relation_fold_and_or (irange&
> lhs_range, gimple *s,
>    if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
>      return;
> 
> +  if (HONOR_NANS (TREE_TYPE (ssa1_dep1)))
> +    return;
> +
>    // Make sure they are the same dependencies, and detect the order of the
>    // relationship.
>    bool reverse_op2 = true;
> 
> 

If this works, maybe (does something check if ssa1_dep1 has certain
type (I assume ssa1_dep2 has to have the same) then ssa2_dep{1,2} has that
type too (or uselessly equal to that)?  Though, if this spot has both
operands of the comparison, could we for HONOR_NANS case ask frange if
any of them is maybe_nan or known_nan and punt only if anything can be NAN?

	Jakub

On 1/25/23 17:35, Jakub Jelinek wrote:
> On Wed, Jan 25, 2023 at 11:12:11AM -0500, Andrew MacLeod via Gcc-patches wrote:
>> In GCC13, I don't think there are any uses of the relation oracle outside of
>> ranger and range-ops.
>>
>> So, given that, perhaps the simplest thing to do is bail on all this change,
>> and instead simply do the following which also fixes the PR. (im running it
>> thru tests as we speak)
>>
>>
>>
>> diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
>> index 91eb6298254..9c5359a3fc6 100644
>> --- a/gcc/gimple-range-fold.cc
>> +++ b/gcc/gimple-range-fold.cc
>> @@ -1039,6 +1039,9 @@ fold_using_range::relation_fold_and_or (irange&
>> lhs_range, gimple *s,
>>     if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
>>       return;
>>
>> +  if (HONOR_NANS (TREE_TYPE (ssa1_dep1)))
>> +    return;
>> +
>>     // Make sure they are the same dependencies, and detect the order of the
>>     // relationship.
>>     bool reverse_op2 = true;
>>
>>
> If this works, maybe (does something check if ssa1_dep1 has certain
> type (I assume ssa1_dep2 has to have the same) then ssa2_dep{1,2} has that
> type too (or uselessly equal to that)?  Though, if this spot has both
> operands of the comparison, could we for HONOR_NANS case ask frange if
> any of them is maybe_nan or known_nan and punt only if anything can be NAN?


it bootstraps with no regressions.

all the ssa?dep? must have the same type, or the comparisons for 
similarity are going to fail.  ir requires the same 2 ssa-name in both 
relational expressions, which means they must all be the same type.

At this point we don't actually know ranges.. this is a higher level 
thing before any queries have happen.   we could query, but I'd punt on 
that for next release :-)  And think about how applicable it is.  Id 
like to revisit this entire situation.

Andrew



>
> 	Jakub
>

On Wed, Jan 25, 2023 at 06:23:25PM -0500, Andrew MacLeod wrote:
> > > --- a/gcc/gimple-range-fold.cc
> > > +++ b/gcc/gimple-range-fold.cc
> > > @@ -1039,6 +1039,9 @@ fold_using_range::relation_fold_and_or (irange&
> > > lhs_range, gimple *s,
> > >     if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
> > >       return;
> > > 
> > > +  if (HONOR_NANS (TREE_TYPE (ssa1_dep1)))
> > > +    return;
> > > +
> > >     // Make sure they are the same dependencies, and detect the order of the
> > >     // relationship.
> > >     bool reverse_op2 = true;
> > > 
> > > 
> > If this works, maybe (does something check if ssa1_dep1 has certain
> > type (I assume ssa1_dep2 has to have the same) then ssa2_dep{1,2} has that
> > type too (or uselessly equal to that)?  Though, if this spot has both
> > operands of the comparison, could we for HONOR_NANS case ask frange if
> > any of them is maybe_nan or known_nan and punt only if anything can be NAN?
> 
> 
> it bootstraps with no regressions.
> 
> all the ssa?dep? must have the same type, or the comparisons for similarity
> are going to fail.  ir requires the same 2 ssa-name in both relational
> expressions, which means they must all be the same type.
> 
> At this point we don't actually know ranges.. this is a higher level thing
> before any queries have happen.   we could query, but I'd punt on that for
> next release :-)  And think about how applicable it is.  Id like to revisit
> this entire situation.

LGTM for GCC 13.  For GCC 14 we should IMHO really support all 16
possible relations and deal with them correctly.

	Jakub