[Bug tree-optimization/107972] New: backward propagation of finite property not performed

[Bug tree-optimization/107972] New: backward propagation of finite property not performed

[drepper.fsp+rhbz at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107972

            Bug ID: 107972
           Summary: backward propagation of finite property not performed
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: drepper.fsp+rhbz at gmail dot com
  Target Milestone: ---

Here is another example where with the help of the FP ranger capabilities the
compiler should generate better code than it does today (trunk):

double f(double a, double b)
{
  if (!__builtin_isfinite(a))
    return -1.0;

  double res = a + b;
  if (! __builtin_isfinite(res))
    __builtin_unreachable();
  return res;
}

The condition guaranteed by the __builtin_unreachable implies that neither a
nor b cannot be finite.  Hence the initial comparison can be elided.

The same is true for - and * and also for the first operand of /.

[Bug tree-optimization/107972] backward propagation of finite property not performed

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107972

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |jakub at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
For * I've posted such a patch today (but guess I should add a testcase):
https://gcc.gnu.org/pipermail/gcc-patches/2022-December/607832.html
For + and - I guess we can't do easily the sign bit computation, so we could
just in
the reverse ops do if lhs must be finite (not inf nor nan), then the operand we
compute must be finite too.

[Bug tree-optimization/107972] backward propagation of finite property not performed

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107972

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:a0ee2e522523b35ac810bd31c9769b9906f87953

commit r13-4502-ga0ee2e522523b35ac810bd31c9769b9906f87953
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Dec 6 10:26:09 2022 +0100

    range-op-float: Improve binary reverse operations

    On Mon, Dec 05, 2022 at 02:29:36PM +0100, Aldy Hernandez wrote:
    > > So like this for multiplication op1/2_range if it passes
bootstrap/regtest?
    > > For division I'll need to go to a drawing board...
    >
    > Sure, looks good to me.

    Ulrich just filed PR107972, so in the light of that PR the following patch
    attempts to do that differently.

    As for testcase, I've tried both attached testcases, but unfortunately it
    seems that in neither of the cases we actually figure out that res range
    is finite (or for last function non-zero ordered).  So there is further
    work needed on that.

    2022-12-06  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/107972
            * range-op-float.cc (frange_drop_infs): New function.
            (float_binary_op_range_finish): Add DIV_OP2 argument.  If DIV_OP2
is
            false and lhs is finite or if DIV_OP2 is true and lhs is non-zero
and
            not NAN, r must be finite too.
            (foperator_div::op2_range): Pass true to DIV_OP2 of
            float_binary_op_range_finish.

[Bug tree-optimization/107972] backward propagation of finite property not performed

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107972

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The backwards propagation fixed, but neither:
double
foo (double a, double b)
{
  if (!__builtin_isfinite (a))
    return 42.0;
  if (!__builtin_isfinite (b))
    return 42.0;
  double res = a + b;
  if (!__builtin_isfinite (res))
    __builtin_unreachable ();
  return res;
}

double
bar (double a, double b)
{
  if (!__builtin_isfinite (a))
    return 42.0;
  if (!__builtin_isfinite (b))
    return 42.0;
  double res = a - b;
  if (!__builtin_isfinite (res))
    __builtin_unreachable ();
  return res;
}

double
baz (double a, double b)
{
  if (!__builtin_isfinite (a))
    return 42.0;
  if (!__builtin_isfinite (b))
    return 42.0;
  double res = a * b;
  if (!__builtin_isfinite (res))
    __builtin_unreachable ();
  return res;
}

double
qux (double a, double b)
{
  if (!__builtin_isfinite (a))
    return 42.0;
  double res = a / b;
  if (!__builtin_isfinite (res))
    __builtin_unreachable ();
  return res;
}

double
quux (double a, double b)
{
  if (!__builtin_isfinite (b))
    return 42.0;
  double res = a / b;
  if (__builtin_isnan (res) || res == 0.0)
    __builtin_unreachable ();
  return res;
}
nor
double
foo (double a, double b)
{
  if (!__builtin_isfinite (a))
    return 42.0;
  if (!__builtin_isfinite (b))
    return 42.0;
  double res = a + b;
  __attribute__((assume (__builtin_isfinite (res))));
  return res;
}

double
bar (double a, double b)
{
  if (!__builtin_isfinite (a))
    return 42.0;
  if (!__builtin_isfinite (b))
    return 42.0;
  double res = a - b;
  __attribute__((assume (__builtin_isfinite (res))));
  return res;
}

double
baz (double a, double b)
{
  if (!__builtin_isfinite (a))
    return 42.0;
  if (!__builtin_isfinite (b))
    return 42.0;
  double res = a * b;
  __attribute__((assume (__builtin_isfinite (res))));
  return res;
}

double
qux (double a, double b)
{
  if (!__builtin_isfinite (a))
    return 42.0;
  double res = a / b;
  __attribute__((assume (__builtin_isfinite (res))));
  return res;
}

double
quux (double a, double b)
{
  if (!__builtin_isfinite (b))
    return 42.0;
  double res = a / b;
  __attribute__((assume (!__builtin_isnan (res) && res != 0.0)));
  return res;
}
avoids the 4.2e+1 cases in the output, because in neither case we properly
determine the ranges of res (that it is in foo/bar/baz/qux [-DBL_MAX,DBL_MAX]).
For quux I think we don't have a way to represent that right now, we'd need a
union of 2 ranges and after all, we also flush denormals to zero, so I think
we'd need if (!(res < 1.0)) __builtin_unreachable (); or __attribute__((assume
(res < 1.0))); so that we get [1.0, +INF] non-NAN range.
Aldy/Andrew, any ideas what's going on?

[Bug tree-optimization/107972] backward propagation of finite property not performed

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107972

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
Its because we don't go back and re-propagate into previous basic block.  Take
an integral vexample:

unsigned 
foo (unsigned a, unsigned b)
{
  unsigned res = a + b;
  if (res > 100)
    return 42
  if (a > 30 || b > 30)
    __builtin_unreachable ();
  if (res > 100)
    return 42
  return res;

The branch which restricts the range of a and b to [0,30] causes GORI to
recompute "res = a + b" on each edge, so those values are pushed along any
outgoing edges, and when we see res > 100 the second time we fold that away.

Thats all handled buy GORI which is basic-block oriented only.  At no point
(yet anyway) do we attempt to push these values back further in the CFG, so
therefore we don't touch the conditions that were encountered earlier, and
cannot eliminate the earlier compare and return.  

I have contemplated a new kind of VRP analysis pass which leverages what we did
with 'assume', propagates known values backwards and looks for opportunities
earlier in the CFG that are exposed by information determined later in the IL. 
 This sort of thing would probably require such a pass.

[Bug tree-optimization/107972] backward propagation of finite property not performed

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107972

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Jakub Jelinek from comment #3)
> The backwards propagation fixed, but neither:
<...>
> avoids the 4.2e+1 cases in the output, because in neither case we properly
> determine the ranges of res (that it is in foo/bar/baz/qux
> [-DBL_MAX,DBL_MAX]).
> For quux I think we don't have a way to represent that right now, we'd need
> a union of 2 ranges and after all, we also flush denormals to zero, so I
> think we'd need if (!(res < 1.0)) __builtin_unreachable (); or
> __attribute__((assume (res < 1.0))); so that we get [1.0, +INF] non-NAN
> range.
> Aldy/Andrew, any ideas what's going on?

Relooking at this, I am confused a bit.

First, how can we remove the 42.0 from the output?   I see no reason the caller
can't pass a NAN in for a or b, and then the first if will trigger and return
42?
Sure, once we get to the calculation of res and know its not a NAN, we also
know the first if wasn't necessary, but thats only true if we actually get past
that first If...?

Second, we do actually know res is is that range on the outgoing edge if the
if.. ie for quux:
   res_8 = a_7(D) / b_6(D);
    _2 = res_8 unord res_8;
    _3 = res_8 == 0.0;
    _4 = _2 | _3;
    if (_4 != 0)
      goto <bb 5>; [INV]
    else
      goto <bb 6>; [INV]

4->5  (T) _4 :  [irange] _Bool [1, 1]
4->5  (T) b_6(D) :      [frange] double
[-1.79769313486231570814527423731704356798070567525844996599e+308
(-0x0.fffffffffffff8p+1024),
1.79769313486231570814527423731704356798070567525844996599e+308
(0x0.fffffffffffff8p+1024)]
4->5  (T) res_8 :       [frange] double [-0.0 (-0x0.0p+0), 0.0 (0x0.0p+0)]
+-NAN
4->6  (F) _2 :  [irange] _Bool [0, 0] NONZERO 0x0
4->6  (F) _3 :  [irange] _Bool [0, 0] NONZERO 0x0
4->6  (F) _4 :  [irange] _Bool [0, 0] NONZERO 0x0
4->6  (F) b_6(D) :      [frange] double
[-1.79769313486231570814527423731704356798070567525844996599e+308
(-0x0.fffffffffffff8p+1024),
1.79769313486231570814527423731704356798070567525844996599e+308
(0x0.fffffffffffff8p+1024)]
4->6  (F) a_7(D) :      [frange] double [-Inf, +Inf]
4->6  (F) res_8 :       [frange] double [-Inf, +Inf]

We know on the edge 4->6 res_8 can't be a NAN (I think we have no way to also
represent ~0.0 right now, true)

We don't set the global that way due to some restrictions of the way we
currently remove unreachable().  there are 2 uses of res_8 in the expressions
in that block which ranger is currently not comfortable propagating the [-Inf,
+Inf] into since they precede the condition itself... it currently only deals
with this situation if there is ONE use in a condtion.  Since this has 2, it
gives up on this release. 

On the reachable edge leading to the return, in each of the 4 cases we know res
is not a NAN.   we just dont reflect it in the global always.

Next release I plan to revamp the unreachable stuff... again.  so many nooks
and crannies :-)