Re: [PATCH] [ranger] x == -0.0 does not mean we can replace x with -0.0

[Aldy Hernandez <aldyh@redhat.com>]

I think we can model the signed zero problem by keeping track of a
sign property, similar to how we keep track of a NAN property.  The
property can be yes, no, or unknown, and would apply to the entire
range.

[0.0, 0.0] SIGN     => -0.0 singleton
[0.0, 0.0] !SIGN    => +0.0 singleton
[0.0, 0.0] VARYING  => [-0.0, +0.0] sign unknown

frange::singleton_p() would return the appropriate zero if the sign
bit is definitely known, otherwise it would return NULL, which would
keep VRP from propagating it.

This is a sample of how I envision it working with __builtin_signbit:

=========== BB 2 ============
Imports: x_3(D)
Exports: _1  x_3(D)
         _1 : x_3(D)(I)
x_3(D)  [frange] float VARYING
    <bb 2> :
    _1 = __builtin_signbit (x_3(D));
    if (_1 == 0)
      goto <bb 3>; [INV]
    else
      goto <bb 4>; [INV]

2->3  (T) _1 :  [irange] int [0, 0] NONZERO 0x0
2->3  (T) x_3(D) :      [frange] float [0.0,  Inf] !SIGN
2->4  (F) _1 :  [irange] int [-INF, -1][1, +INF]
2->4  (F) x_3(D) :      [frange] float [ -Inf, 0.0] SIGN

That is, on the TRUE side x_3 can be assumed to be positive, including
the zero.  On the FALSE side x_3 is negative, also including the zero.

We can keep the endpoints in sync with the sign bit for free, since we
have endpoints.  So, setting the sign bit on a range to either yes or
no, would automatically intersect it to [-INF, 0] or [0, +INF]
respectively.

With this in play, VRP could propagate a 0.0 if it knows the sign.  For example:

  if (x == 0.0 && __builtin_signbit (x) == 0)
    bark(x);

...would generate:

=========== BB 2 ============
Imports: x_3(D)
Exports: x_3(D)
x_3(D)  [frange] float VARYING
    <bb 2> :
    if (x_3(D) == 0.0)
      goto <bb 3>; [INV]
    else
      goto <bb 5>; [INV]

2->3  (T) x_3(D) :      [frange] float [0.0, 0.0] !NAN

=========== BB 3 ============
Imports: x_3(D)
Exports: _1  x_3(D)
         _1 : x_3(D)(I)
x_3(D)  [frange] float [0.0, 0.0] !NAN
    <bb 3> :
    _1 = __builtin_signbit (x_3(D));
    if (_1 == 0)
      goto <bb 4>; [INV]
    else
      goto <bb 5>; [INV]

3->4  (T) _1 :  [irange] int [0, 0] NONZERO 0x0
3->4  (T) x_3(D) :      [frange] float [0.0, 0.0] !NAN !SIGN
3->5  (F) _1 :  [irange] int [-INF, -1][1, +INF]
3->5  (F) x_3(D) :      [frange] float [0.0, 0.0] !NAN SIGN

=========== BB 4 ============
x_3(D)  [frange] float [0.0, 0.0] !NAN !SIGN
    <bb 4> :
    bark (0.0);

That is, on the 2->3 edge we know x_3 is 0.0 and !NAN, but have no
information on the sign bit.  Then out of BB3, we know both that x_3
is 0.0 as well as the appropriate sign.  Ultimately this leads us to
propagate +0.0 in BB4.

I have most^Wall of it coded without regressions, with the exception
of how to coerce the range-op machinery to play nice with builtins
(details below).  But I wanted to make sure we're all on the same
page.

A couple questions:

Can I safely assume that +0.0 in the source (say, x = 0.0) has the
sign bit cleared, and vice versa for -0.0?

What's the deal with __builtin_signbit?  Can I fold it to 0/1, or must
I return the actual signbit, because I see differing behavior whether
we fold a known value or not:

abulafia:~$ cat a.c
float nzero = -0.0;

main(){
    printf("0x%x\n", __builtin_signbit(-0.0));
    printf("0x%x\n", __builtin_signbit(nzero));
}
abulafia:~$ gcc a.c -w && ./a.out
0x1
0x80000000

When Andrew comes back from PTO, we'll need to talk about propagating
builtins.  Currently range-ops' op1_range is used to unwind back from
conditionals.  For example:

    _1 = x_9 + 5
    if (_1 == 0)

On the TRUE side we use op1_range to solve:

    0 = x_9 + 5;

We currently only handle assignments and conditionals.  We would need
to ability to wind back through builtins since __builtin_signbit is
not part of the IL:

    _1 = __builtin_signbit (x_3(D));
    if (_1 == 0)

We have no way to augment the range for x_3 when examining the
builtin.    We do have a way of folding the builtin on a forward
analysis, but that's a separate thing.

Thoughts?
Aldy

On Mon, Aug 29, 2022 at 3:22 PM Jakub Jelinek <jakub@redhat.com> wrote:
>
> On Mon, Aug 29, 2022 at 03:13:21PM +0200, Aldy Hernandez wrote:
> > It seems to me we can do this optimization regardless, but then treat
> > positive and negative zero the same throughout the frange class.
> > Particularly, in frange::singleton_p().  We should never return TRUE
> > for any version of 0.0.  This will keep VRP from propagating an
> > incorrect 0.0, since all VRP does is propagate when a range is
> > provably a singleton.  Also, frange::zero_p() shall return true for
> > any version of 0.0.
>
> Well, I think for HONOR_SIGNED_ZEROS it would be nice if frange was able to
> differentiate between 0.0 and -0.0.
> One reason is e.g. to be able to optimize copysign/signbit - if we can
> prove that the sign bit on some value will be always cleared or always set,
> we can fold those.
> On the other side, with -fno-signed-zeros it is invalid to use
> copysign/signbit on values that could be zero (well, nothing guarantees
> whether the sign bit is set or clear), so for MODE_HAS_SIGNED_ZEROS &&
> !HONOR_SIGNED_ZEROS it is best to treat contains_p as {-0.0,0.0} being
> one thing (just not singleton_p) and not bother with details like whether
> a range ends or starts with -0.0 or 0.0, either of them would work the same.
> And for !MODE_HAS_SIGNED_ZEROS, obviously 0.0 can be singleton_p.
>
>         Jakub
>