[PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Aldy Hernandez]

It irks me that a PR named "we should track ranges for floating-point
hasn't been closed in this release.  This is an attempt to do just
that.

As mentioned in the PR, even though we track ranges for floats, it has
been suggested that avoiding recursing through SSA defs in
gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
various ranger components without the need for a heavy handed approach
(i.e. a full ranger).

I have implemented two versions of known_float_sign_p() that answer
the question whether we definitely know the sign for an operation or a
tree expression.

Both versions use get_global_range_query, which is a wrapper to query
global ranges.  This means, that no caching or propagation is done.
In the case of an SSA, we just return the global range for it (think
SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
also use get_global_range_query to resolve the operands, and then call
into range-ops, which is our lowest level component.  There is no
ranger or gori involved.  All we're doing is resolving the operation
with the ranges passed.

This is enough to avoid recursing in the case where we definitely know
the sign of a range.  Otherwise, we still recurse.

Note that instead of get_global_range_query(), we could use
get_range_query() which uses a ranger (if active in a pass), or
get_global_range_query if not.  This would allow passes that have an
active ranger (with enable_ranger) to use a full ranger.  These passes
are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
no ranger is active, get_range_query defaults to global ranges, so
there's no additional penalty.

Would this be acceptable, at least enough to close (or rename the PR ;-))?

	PR tree-optimization/68097

gcc/ChangeLog:

	* fold-const.cc (known_float_sign_p): New.
	(tree_unary_nonnegative_warnv_p): Call known_float_sign_p.
	(tree_binary_nonnegative_warnv_p): Same.
	(tree_single_nonnegative_warnv_p): Same.
---
 gcc/fold-const.cc | 51 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 51 insertions(+)

diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc
index b89cac91cae..bd74cfca996 100644
--- a/gcc/fold-const.cc
+++ b/gcc/fold-const.cc
@@ -14577,6 +14577,44 @@ tree_simple_nonnegative_warnv_p (enum tree_code code, tree type)
   return false;
 }
 
+/* Return true if T is of type floating point and has a known sign.
+   If so, set the sign in SIGN.  */
+
+static bool
+known_float_sign_p (bool &sign, tree t)
+{
+  if (!frange::supports_p (TREE_TYPE (t)))
+    return false;
+
+  frange r;
+  return (get_global_range_query ()->range_of_expr (r, t)
+	  && r.signbit_p (sign));
+}
+
+/* Return true if TYPE is a floating-point type and (CODE OP0 OP1) has
+   a known sign.  If so, set the sign in SIGN.  */
+
+static bool
+known_float_sign_p (bool &sign, enum tree_code code, tree type, tree op0,
+		    tree op1 = NULL_TREE)
+{
+  if (!frange::supports_p (type))
+    return false;
+
+  range_op_handler handler (code, type);
+  if (handler)
+    {
+      frange res, r0, r1;
+      get_global_range_query ()->range_of_expr (r0, op0);
+      if (op1)
+	get_global_range_query ()->range_of_expr (r1, op1);
+      else
+	r1.set_varying (type);
+      return handler.fold_range (res, type, r0, r1) && res.signbit_p (sign);
+    }
+  return false;
+}
+
 /* Return true if (CODE OP0) is known to be non-negative.  If the return
    value is based on the assumption that signed overflow is undefined,
    set *STRICT_OVERFLOW_P to true; otherwise, don't change
@@ -14589,6 +14627,10 @@ tree_unary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
   if (TYPE_UNSIGNED (type))
     return true;
 
+  bool sign;
+  if (known_float_sign_p (sign, code, type, op0))
+    return !sign;
+
   switch (code)
     {
     case ABS_EXPR:
@@ -14656,6 +14698,10 @@ tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
   if (TYPE_UNSIGNED (type))
     return true;
 
+  bool sign;
+  if (known_float_sign_p (sign, code, type, op0, op1))
+    return !sign;
+
   switch (code)
     {
     case POINTER_PLUS_EXPR:
@@ -14778,6 +14824,8 @@ tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
 bool
 tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth)
 {
+  bool sign;
+
   if (TYPE_UNSIGNED (TREE_TYPE (t)))
     return true;
 
@@ -14796,6 +14844,9 @@ tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth)
       return RECURSE (TREE_OPERAND (t, 1)) && RECURSE (TREE_OPERAND (t, 2));
 
     case SSA_NAME:
+      if (known_float_sign_p (sign, t))
+	return !sign;
+
       /* Limit the depth of recursion to avoid quadratic behavior.
 	 This is expected to catch almost all occurrences in practice.
 	 If this code misses important cases that unbounded recursion
-- 
2.38.1

Re: [PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Richard Biener]

On Sat, Nov 12, 2022 at 7:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> It irks me that a PR named "we should track ranges for floating-point
> hasn't been closed in this release.  This is an attempt to do just
> that.
>
> As mentioned in the PR, even though we track ranges for floats, it has
> been suggested that avoiding recursing through SSA defs in
> gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
> various ranger components without the need for a heavy handed approach
> (i.e. a full ranger).
>
> I have implemented two versions of known_float_sign_p() that answer
> the question whether we definitely know the sign for an operation or a
> tree expression.
>
> Both versions use get_global_range_query, which is a wrapper to query
> global ranges.  This means, that no caching or propagation is done.
> In the case of an SSA, we just return the global range for it (think
> SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
> also use get_global_range_query to resolve the operands, and then call
> into range-ops, which is our lowest level component.  There is no
> ranger or gori involved.  All we're doing is resolving the operation
> with the ranges passed.
>
> This is enough to avoid recursing in the case where we definitely know
> the sign of a range.  Otherwise, we still recurse.
>
> Note that instead of get_global_range_query(), we could use
> get_range_query() which uses a ranger (if active in a pass), or
> get_global_range_query if not.  This would allow passes that have an
> active ranger (with enable_ranger) to use a full ranger.  These passes
> are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
> no ranger is active, get_range_query defaults to global ranges, so
> there's no additional penalty.
>
> Would this be acceptable, at least enough to close (or rename the PR ;-))?

I think the checks would belong to the gimple_stmt_nonnegative_warnv_p function
only (that's the SSA name entry from the fold-const.cc ones)?

I also notice the use of 'bool' for the "sign".  That's not really
descriptive.  We
have SIGNED and UNSIGNED (aka enum signop), not sure if that's the
perfect match vs. NEGATIVE and NONNEGATIVE.  Maybe the functions
name is just bad and they should be known_float_negative_p?

>         PR tree-optimization/68097
>
> gcc/ChangeLog:
>
>         * fold-const.cc (known_float_sign_p): New.
>         (tree_unary_nonnegative_warnv_p): Call known_float_sign_p.
>         (tree_binary_nonnegative_warnv_p): Same.
>         (tree_single_nonnegative_warnv_p): Same.
> ---
>  gcc/fold-const.cc | 51 +++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 51 insertions(+)
>
> diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc
> index b89cac91cae..bd74cfca996 100644
> --- a/gcc/fold-const.cc
> +++ b/gcc/fold-const.cc
> @@ -14577,6 +14577,44 @@ tree_simple_nonnegative_warnv_p (enum tree_code code, tree type)
>    return false;
>  }
>
> +/* Return true if T is of type floating point and has a known sign.
> +   If so, set the sign in SIGN.  */
> +
> +static bool
> +known_float_sign_p (bool &sign, tree t)
> +{
> +  if (!frange::supports_p (TREE_TYPE (t)))
> +    return false;
> +
> +  frange r;
> +  return (get_global_range_query ()->range_of_expr (r, t)
> +         && r.signbit_p (sign));
> +}
> +
> +/* Return true if TYPE is a floating-point type and (CODE OP0 OP1) has
> +   a known sign.  If so, set the sign in SIGN.  */
> +
> +static bool
> +known_float_sign_p (bool &sign, enum tree_code code, tree type, tree op0,
> +                   tree op1 = NULL_TREE)
> +{
> +  if (!frange::supports_p (type))
> +    return false;
> +
> +  range_op_handler handler (code, type);
> +  if (handler)
> +    {
> +      frange res, r0, r1;
> +      get_global_range_query ()->range_of_expr (r0, op0);
> +      if (op1)
> +       get_global_range_query ()->range_of_expr (r1, op1);
> +      else
> +       r1.set_varying (type);
> +      return handler.fold_range (res, type, r0, r1) && res.signbit_p (sign);
> +    }
> +  return false;
> +}
> +
>  /* Return true if (CODE OP0) is known to be non-negative.  If the return
>     value is based on the assumption that signed overflow is undefined,
>     set *STRICT_OVERFLOW_P to true; otherwise, don't change
> @@ -14589,6 +14627,10 @@ tree_unary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
>    if (TYPE_UNSIGNED (type))
>      return true;
>
> +  bool sign;
> +  if (known_float_sign_p (sign, code, type, op0))
> +    return !sign;
> +
>    switch (code)
>      {
>      case ABS_EXPR:
> @@ -14656,6 +14698,10 @@ tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
>    if (TYPE_UNSIGNED (type))
>      return true;
>
> +  bool sign;
> +  if (known_float_sign_p (sign, code, type, op0, op1))
> +    return !sign;
> +
>    switch (code)
>      {
>      case POINTER_PLUS_EXPR:
> @@ -14778,6 +14824,8 @@ tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
>  bool
>  tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth)
>  {
> +  bool sign;
> +
>    if (TYPE_UNSIGNED (TREE_TYPE (t)))
>      return true;
>
> @@ -14796,6 +14844,9 @@ tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth)
>        return RECURSE (TREE_OPERAND (t, 1)) && RECURSE (TREE_OPERAND (t, 2));
>
>      case SSA_NAME:
> +      if (known_float_sign_p (sign, t))
> +       return !sign;
> +
>        /* Limit the depth of recursion to avoid quadratic behavior.
>          This is expected to catch almost all occurrences in practice.
>          If this code misses important cases that unbounded recursion
> --
> 2.38.1
>

Re: [PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 3095 bytes --]



On 11/14/22 10:12, Richard Biener wrote:
> On Sat, Nov 12, 2022 at 7:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>> It irks me that a PR named "we should track ranges for floating-point
>> hasn't been closed in this release.  This is an attempt to do just
>> that.
>>
>> As mentioned in the PR, even though we track ranges for floats, it has
>> been suggested that avoiding recursing through SSA defs in
>> gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
>> various ranger components without the need for a heavy handed approach
>> (i.e. a full ranger).
>>
>> I have implemented two versions of known_float_sign_p() that answer
>> the question whether we definitely know the sign for an operation or a
>> tree expression.
>>
>> Both versions use get_global_range_query, which is a wrapper to query
>> global ranges.  This means, that no caching or propagation is done.
>> In the case of an SSA, we just return the global range for it (think
>> SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
>> also use get_global_range_query to resolve the operands, and then call
>> into range-ops, which is our lowest level component.  There is no
>> ranger or gori involved.  All we're doing is resolving the operation
>> with the ranges passed.
>>
>> This is enough to avoid recursing in the case where we definitely know
>> the sign of a range.  Otherwise, we still recurse.
>>
>> Note that instead of get_global_range_query(), we could use
>> get_range_query() which uses a ranger (if active in a pass), or
>> get_global_range_query if not.  This would allow passes that have an
>> active ranger (with enable_ranger) to use a full ranger.  These passes
>> are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
>> no ranger is active, get_range_query defaults to global ranges, so
>> there's no additional penalty.
>>
>> Would this be acceptable, at least enough to close (or rename the PR ;-))?
> 
> I think the checks would belong to the gimple_stmt_nonnegative_warnv_p function
> only (that's the SSA name entry from the fold-const.cc ones)?

That was my first approach, but I thought I'd cover the unary and binary 
operators as well, since they had other callers.  But I'm happy with 
just the top-level tweak.  It's a lot less code :).

> 
> I also notice the use of 'bool' for the "sign".  That's not really
> descriptive.  We
> have SIGNED and UNSIGNED (aka enum signop), not sure if that's the
> perfect match vs. NEGATIVE and NONNEGATIVE.  Maybe the functions
> name is just bad and they should be known_float_negative_p?

The bool sign is to keep in line with real.*, and was suggested by Jeff 
(in real.* not here).  I'm happy to change the entire frange API to use 
sgnop.  It is cleaner.  If that's acceptable, I could do that as a 
follow-up.

How's this, pending tests once I figure out why my trees have been 
broken all day :-/.

Aldy

p.s. First it was sphinx failure, now I'm seeing this:
/home/aldyh/src/clean/gcc/match.pd:7935:8 error: return statement not 
allowed in C expression
        return NULL_TREE;
        ^

[-- Attachment #2: 0001-PR68097-Try-to-avoid-recursing-for-floats-in-gimple_.patch --]
[-- Type: text/x-patch, Size: 1794 bytes --]

From 6e36626aec81bf97f8f54116a291574c16cbc205 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Sat, 12 Nov 2022 11:58:07 +0100
Subject: [PATCH] [PR68097] Try to avoid recursing for floats in
 gimple_stmt_nonnegative_warnv_p.

It irks me that a PR named "we should track ranges for floating-point
hasn't been closed in this release.  This is an attempt to do just
that.

As mentioned in the PR, even though we track ranges for floats, it has
been suggested that avoiding recursing through SSA defs in
gimple_assign_nonnegative_warnv_p is also a goal.  This patch uses a
global range query (no on-demand lookups, just global ranges and
minimal folding) to determine if the range of a statement is known to
be non-negative.

	PR tree-optimization/68097

gcc/ChangeLog:

	* gimple-fold.cc (gimple_stmt_nonnegative_warnv_p): Call
	range_of_stmt for floats.
---
 gcc/gimple-fold.cc | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
index 0a212e6d0d4..79cc4d7f569 100644
--- a/gcc/gimple-fold.cc
+++ b/gcc/gimple-fold.cc
@@ -68,6 +68,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-strlen.h"
 #include "varasm.h"
 #include "internal-fn.h"
+#include "gimple-range.h"
 
 enum strlen_range_kind {
   /* Compute the exact constant string length.  */
@@ -9234,6 +9235,15 @@ bool
 gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p,
 				 int depth)
 {
+  tree type = gimple_range_type (stmt);
+  if (type && frange::supports_p (type))
+    {
+      frange r;
+      bool sign;
+      return (get_global_range_query ()->range_of_stmt (r, stmt)
+	      && r.signbit_p (sign)
+	      && sign == false);
+    }
   switch (gimple_code (stmt))
     {
     case GIMPLE_ASSIGN:
-- 
2.38.1

Re: [PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Richard Biener]

On Mon, Nov 14, 2022 at 8:05 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 11/14/22 10:12, Richard Biener wrote:
> > On Sat, Nov 12, 2022 at 7:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >> It irks me that a PR named "we should track ranges for floating-point
> >> hasn't been closed in this release.  This is an attempt to do just
> >> that.
> >>
> >> As mentioned in the PR, even though we track ranges for floats, it has
> >> been suggested that avoiding recursing through SSA defs in
> >> gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
> >> various ranger components without the need for a heavy handed approach
> >> (i.e. a full ranger).
> >>
> >> I have implemented two versions of known_float_sign_p() that answer
> >> the question whether we definitely know the sign for an operation or a
> >> tree expression.
> >>
> >> Both versions use get_global_range_query, which is a wrapper to query
> >> global ranges.  This means, that no caching or propagation is done.
> >> In the case of an SSA, we just return the global range for it (think
> >> SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
> >> also use get_global_range_query to resolve the operands, and then call
> >> into range-ops, which is our lowest level component.  There is no
> >> ranger or gori involved.  All we're doing is resolving the operation
> >> with the ranges passed.
> >>
> >> This is enough to avoid recursing in the case where we definitely know
> >> the sign of a range.  Otherwise, we still recurse.
> >>
> >> Note that instead of get_global_range_query(), we could use
> >> get_range_query() which uses a ranger (if active in a pass), or
> >> get_global_range_query if not.  This would allow passes that have an
> >> active ranger (with enable_ranger) to use a full ranger.  These passes
> >> are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
> >> no ranger is active, get_range_query defaults to global ranges, so
> >> there's no additional penalty.
> >>
> >> Would this be acceptable, at least enough to close (or rename the PR ;-))?
> >
> > I think the checks would belong to the gimple_stmt_nonnegative_warnv_p function
> > only (that's the SSA name entry from the fold-const.cc ones)?
>
> That was my first approach, but I thought I'd cover the unary and binary
> operators as well, since they had other callers.  But I'm happy with
> just the top-level tweak.  It's a lot less code :).

@@ -9234,6 +9235,15 @@ bool
 gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p,
                                 int depth)
 {
+  tree type = gimple_range_type (stmt);
+  if (type && frange::supports_p (type))
+    {
+      frange r;
+      bool sign;
+      return (get_global_range_query ()->range_of_stmt (r, stmt)
+             && r.signbit_p (sign)
+             && sign == false);
+    }

the above means we never fall through to the switch below if
frange::supports_p (type) - that's eventually good enough, I
don't think we ever call this very function directly but it gets
invoked via recursion through operands only.  But of course
I wonder what types are not supported by frange and whether
the manual processing we fall through to does anything meaningful
for those?

I won't ask you to thoroughly answer this now but please put in
a comment reflecting the above before the switch stmt.

   switch (gimple_code (stmt))


Otherwise OK, in case you tree gets back to bootstrapping ;)

> >
> > I also notice the use of 'bool' for the "sign".  That's not really
> > descriptive.  We
> > have SIGNED and UNSIGNED (aka enum signop), not sure if that's the
> > perfect match vs. NEGATIVE and NONNEGATIVE.  Maybe the functions
> > name is just bad and they should be known_float_negative_p?
>
> The bool sign is to keep in line with real.*, and was suggested by Jeff
> (in real.* not here).  I'm happy to change the entire frange API to use
> sgnop.  It is cleaner.  If that's acceptable, I could do that as a
> follow-up.
>
> How's this, pending tests once I figure out why my trees have been
> broken all day :-/.
>
> Aldy
>
> p.s. First it was sphinx failure, now I'm seeing this:
> /home/aldyh/src/clean/gcc/match.pd:7935:8 error: return statement not
> allowed in C expression
>         return NULL_TREE;
>         ^

Supposedly somebody pushed and reverted this transient error?  Yep,
Tamar did.

Richard.

Re: [PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 5892 bytes --]



On 11/15/22 08:15, Richard Biener wrote:
> On Mon, Nov 14, 2022 at 8:05 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 11/14/22 10:12, Richard Biener wrote:
>>> On Sat, Nov 12, 2022 at 7:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>
>>>> It irks me that a PR named "we should track ranges for floating-point
>>>> hasn't been closed in this release.  This is an attempt to do just
>>>> that.
>>>>
>>>> As mentioned in the PR, even though we track ranges for floats, it has
>>>> been suggested that avoiding recursing through SSA defs in
>>>> gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
>>>> various ranger components without the need for a heavy handed approach
>>>> (i.e. a full ranger).
>>>>
>>>> I have implemented two versions of known_float_sign_p() that answer
>>>> the question whether we definitely know the sign for an operation or a
>>>> tree expression.
>>>>
>>>> Both versions use get_global_range_query, which is a wrapper to query
>>>> global ranges.  This means, that no caching or propagation is done.
>>>> In the case of an SSA, we just return the global range for it (think
>>>> SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
>>>> also use get_global_range_query to resolve the operands, and then call
>>>> into range-ops, which is our lowest level component.  There is no
>>>> ranger or gori involved.  All we're doing is resolving the operation
>>>> with the ranges passed.
>>>>
>>>> This is enough to avoid recursing in the case where we definitely know
>>>> the sign of a range.  Otherwise, we still recurse.
>>>>
>>>> Note that instead of get_global_range_query(), we could use
>>>> get_range_query() which uses a ranger (if active in a pass), or
>>>> get_global_range_query if not.  This would allow passes that have an
>>>> active ranger (with enable_ranger) to use a full ranger.  These passes
>>>> are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
>>>> no ranger is active, get_range_query defaults to global ranges, so
>>>> there's no additional penalty.
>>>>
>>>> Would this be acceptable, at least enough to close (or rename the PR ;-))?
>>>
>>> I think the checks would belong to the gimple_stmt_nonnegative_warnv_p function
>>> only (that's the SSA name entry from the fold-const.cc ones)?
>>
>> That was my first approach, but I thought I'd cover the unary and binary
>> operators as well, since they had other callers.  But I'm happy with
>> just the top-level tweak.  It's a lot less code :).
> 
> @@ -9234,6 +9235,15 @@ bool
>   gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p,
>                                   int depth)
>   {
> +  tree type = gimple_range_type (stmt);
> +  if (type && frange::supports_p (type))
> +    {
> +      frange r;
> +      bool sign;
> +      return (get_global_range_query ()->range_of_stmt (r, stmt)
> +             && r.signbit_p (sign)
> +             && sign == false);
> +    }
> 
> the above means we never fall through to the switch below if
> frange::supports_p (type) - that's eventually good enough, I
> don't think we ever call this very function directly but it gets
> invoked via recursion through operands only.  But of course

Woah, sorry.  That was not intended.  For that matter, the patch as 
posted caused:

FAIL: gcc.dg/builtins-10.c (test for excess errors)
FAIL: gcc.dg/builtins-57.c (test for excess errors)
FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O1  (test for excess errors)
FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O2  (test for excess errors)
FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O2 -flto 
-fno-use-linker-plugin -flto-partition=none  (test for excess errors)
FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O3 -g  (test for excess errors)
FAIL: gcc.dg/torture/builtin-nonneg-1.c   -Os  (test for excess errors)
FAIL: gcc.dg/torture/builtin-power-1.c   -O1  (test for excess errors)
FAIL: gcc.dg/torture/builtin-power-1.c   -O2  (test for excess errors)
FAIL: gcc.dg/torture/builtin-power-1.c   -O2 -flto 
-fno-use-linker-plugin -flto-partition=none  (test for excess errors)
FAIL: gcc.dg/torture/builtin-power-1.c   -O3 -g  (test for excess errors)
FAIL: gcc.dg/torture/builtin-power-1.c   -Os  (test for excess errors)

Note that ranger folding calls this function, though it won't run the 
risk of endless recursion because range_of_stmt uses the LHS, and only 
use global ranges to solve the LHS.

Also, frange::supports_p() does not support all floats:

   static bool supports_p (const_tree type)
   {
     // ?? Decimal floats can have multiple representations for the
     // same number.  Supporting them may be as simple as just
     // disabling them in singleton_p.  No clue.
     return SCALAR_FLOAT_TYPE_P (type) && !DECIMAL_FLOAT_TYPE_P (type);
   }

Finally, my patch is more conservative than what the *nonnegative_warn* 
friends do.  We only return true when we're sure about the sign bit and 
it's FALSE.  As I mentioned elsewhere, tree_call_nonnegative_warn_p() 
always returns true for:

     CASE_CFN_ACOS:
     CASE_CFN_ACOS_FN:
     CASE_CFN_ACOSH:
     CASE_CFN_ACOSH_FN:
     CASE_CFN_CABS:
     CASE_CFN_CABS_FN:
...
...
       /* Always true.  */
       return true;

This means that we'll return true for a NAN, but we're incorrectly 
assuming the NAN will be +NAN.  In my proposed patch, we don't make such 
assumptions.  We only return true if the range is non-negative, 
including the NAN.

> I wonder what types are not supported by frange and whether
> the manual processing we fall through to does anything meaningful
> for those?
> 
> I won't ask you to thoroughly answer this now but please put in
> a comment reflecting the above before the switch stmt.
> 
>     switch (gimple_code (stmt))
> 
> 
> Otherwise OK, in case you tree gets back to bootstrapping ;)

Updated patch that passes test.

OK?  And if so, can I close the PR?

Thanks.
Aldy

[-- Attachment #2: 0001-PR68097-Try-to-avoid-recursing-for-floats-in-gimple_.patch --]
[-- Type: text/x-patch, Size: 1776 bytes --]

From 8f589cff22e80eda7cc3837080dbc9ae8280da8c Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Sat, 12 Nov 2022 11:58:07 +0100
Subject: [PATCH] [PR68097] Try to avoid recursing for floats in
 gimple_stmt_nonnegative_warnv_p.

It irks me that a PR named "we should track ranges for floating-point
hasn't been closed in this release.  This is an attempt to do just
that.

As mentioned in the PR, even though we track ranges for floats, it has
been suggested that avoiding recursing through SSA defs in
gimple_assign_nonnegative_warnv_p is also a goal.  This patch uses a
global range query (no on-demand lookups, just global ranges and
minimal folding) to determine if the range of a statement is known to
be non-negative.

	PR tree-optimization/68097

gcc/ChangeLog:

	* gimple-fold.cc (gimple_stmt_nonnegative_warnv_p): Call
	range_of_stmt for floats.
---
 gcc/gimple-fold.cc | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
index 0a212e6d0d4..c4ebe9a3b52 100644
--- a/gcc/gimple-fold.cc
+++ b/gcc/gimple-fold.cc
@@ -68,6 +68,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-strlen.h"
 #include "varasm.h"
 #include "internal-fn.h"
+#include "gimple-range.h"
 
 enum strlen_range_kind {
   /* Compute the exact constant string length.  */
@@ -9234,6 +9235,15 @@ bool
 gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p,
 				 int depth)
 {
+  tree type = gimple_range_type (stmt);
+  if (type && frange::supports_p (type))
+    {
+      frange r;
+      bool sign;
+      if (get_global_range_query ()->range_of_stmt (r, stmt)
+	  && r.signbit_p (sign))
+	return !sign;
+    }
   switch (gimple_code (stmt))
     {
     case GIMPLE_ASSIGN:
-- 
2.38.1

Re: [PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Aldy Hernandez]

On Mon, Nov 14, 2022 at 10:12 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Sat, Nov 12, 2022 at 7:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > It irks me that a PR named "we should track ranges for floating-point
> > hasn't been closed in this release.  This is an attempt to do just
> > that.
> >
> > As mentioned in the PR, even though we track ranges for floats, it has
> > been suggested that avoiding recursing through SSA defs in
> > gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
> > various ranger components without the need for a heavy handed approach
> > (i.e. a full ranger).
> >
> > I have implemented two versions of known_float_sign_p() that answer
> > the question whether we definitely know the sign for an operation or a
> > tree expression.
> >
> > Both versions use get_global_range_query, which is a wrapper to query
> > global ranges.  This means, that no caching or propagation is done.
> > In the case of an SSA, we just return the global range for it (think
> > SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
> > also use get_global_range_query to resolve the operands, and then call
> > into range-ops, which is our lowest level component.  There is no
> > ranger or gori involved.  All we're doing is resolving the operation
> > with the ranges passed.
> >
> > This is enough to avoid recursing in the case where we definitely know
> > the sign of a range.  Otherwise, we still recurse.
> >
> > Note that instead of get_global_range_query(), we could use
> > get_range_query() which uses a ranger (if active in a pass), or
> > get_global_range_query if not.  This would allow passes that have an
> > active ranger (with enable_ranger) to use a full ranger.  These passes
> > are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
> > no ranger is active, get_range_query defaults to global ranges, so
> > there's no additional penalty.
> >
> > Would this be acceptable, at least enough to close (or rename the PR ;-))?
>
> I think the checks would belong to the gimple_stmt_nonnegative_warnv_p function
> only (that's the SSA name entry from the fold-const.cc ones)?
>
> I also notice the use of 'bool' for the "sign".  That's not really
> descriptive.  We
> have SIGNED and UNSIGNED (aka enum signop), not sure if that's the
> perfect match vs. NEGATIVE and NONNEGATIVE.  Maybe the functions
> name is just bad and they should be known_float_negative_p?

Yeah, SIGNED and UNSIGNED doesn't seem to be much clearer than "bool signbit".

For instance, we have the following in frange:

  void set_nan (tree type, bool sign);
  void update_nan (bool sign);
  bool maybe_isnan (bool sign) const;
  bool signbit_p (bool &signbit) const;

I'm OK changing them to enum signop if you prefer.  I'm just not
totally convinced it's more readable.

??

Aldy

Re: [PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Richard Biener]

On Tue, Nov 15, 2022 at 2:52 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> On Mon, Nov 14, 2022 at 10:12 AM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > On Sat, Nov 12, 2022 at 7:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> > >
> > > It irks me that a PR named "we should track ranges for floating-point
> > > hasn't been closed in this release.  This is an attempt to do just
> > > that.
> > >
> > > As mentioned in the PR, even though we track ranges for floats, it has
> > > been suggested that avoiding recursing through SSA defs in
> > > gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
> > > various ranger components without the need for a heavy handed approach
> > > (i.e. a full ranger).
> > >
> > > I have implemented two versions of known_float_sign_p() that answer
> > > the question whether we definitely know the sign for an operation or a
> > > tree expression.
> > >
> > > Both versions use get_global_range_query, which is a wrapper to query
> > > global ranges.  This means, that no caching or propagation is done.
> > > In the case of an SSA, we just return the global range for it (think
> > > SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
> > > also use get_global_range_query to resolve the operands, and then call
> > > into range-ops, which is our lowest level component.  There is no
> > > ranger or gori involved.  All we're doing is resolving the operation
> > > with the ranges passed.
> > >
> > > This is enough to avoid recursing in the case where we definitely know
> > > the sign of a range.  Otherwise, we still recurse.
> > >
> > > Note that instead of get_global_range_query(), we could use
> > > get_range_query() which uses a ranger (if active in a pass), or
> > > get_global_range_query if not.  This would allow passes that have an
> > > active ranger (with enable_ranger) to use a full ranger.  These passes
> > > are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
> > > no ranger is active, get_range_query defaults to global ranges, so
> > > there's no additional penalty.
> > >
> > > Would this be acceptable, at least enough to close (or rename the PR ;-))?
> >
> > I think the checks would belong to the gimple_stmt_nonnegative_warnv_p function
> > only (that's the SSA name entry from the fold-const.cc ones)?
> >
> > I also notice the use of 'bool' for the "sign".  That's not really
> > descriptive.  We
> > have SIGNED and UNSIGNED (aka enum signop), not sure if that's the
> > perfect match vs. NEGATIVE and NONNEGATIVE.  Maybe the functions
> > name is just bad and they should be known_float_negative_p?
>
> Yeah, SIGNED and UNSIGNED doesn't seem to be much clearer than "bool signbit".
>
> For instance, we have the following in frange:
>
>   void set_nan (tree type, bool sign);
>   void update_nan (bool sign);
>   bool maybe_isnan (bool sign) const;
>   bool signbit_p (bool &signbit) const;
>
> I'm OK changing them to enum signop if you prefer.  I'm just not
> totally convinced it's more readable.
>
> ??

I think when talking about 'signbit' or 'sign' the old usual 'unsigned' type is
better than bool.    signbit_p feels a bit redundant (the _p).

We could have another enum like signop just I think the obvious
candidates { POSITIVE, NEGATIVE } or { NEGATIVE, NONNEGATIVE }
aren't too great.  The obvious alternative is to follow the existing uns_p
(unsigned?) parameters and not use bool sign but bool unsigned_p,
there 'true' and 'false' are obvious.  For 'signbit_p' it would then be
bool signbit_p (unsigned &signbit) being the true value of the bit
(and the return value indicates the UNKNOWN case).

Richard.

>
> Aldy
>

Re: [PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Richard Biener]

On Tue, Nov 15, 2022 at 11:46 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 11/15/22 08:15, Richard Biener wrote:
> > On Mon, Nov 14, 2022 at 8:05 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >>
> >>
> >> On 11/14/22 10:12, Richard Biener wrote:
> >>> On Sat, Nov 12, 2022 at 7:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>>>
> >>>> It irks me that a PR named "we should track ranges for floating-point
> >>>> hasn't been closed in this release.  This is an attempt to do just
> >>>> that.
> >>>>
> >>>> As mentioned in the PR, even though we track ranges for floats, it has
> >>>> been suggested that avoiding recursing through SSA defs in
> >>>> gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
> >>>> various ranger components without the need for a heavy handed approach
> >>>> (i.e. a full ranger).
> >>>>
> >>>> I have implemented two versions of known_float_sign_p() that answer
> >>>> the question whether we definitely know the sign for an operation or a
> >>>> tree expression.
> >>>>
> >>>> Both versions use get_global_range_query, which is a wrapper to query
> >>>> global ranges.  This means, that no caching or propagation is done.
> >>>> In the case of an SSA, we just return the global range for it (think
> >>>> SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
> >>>> also use get_global_range_query to resolve the operands, and then call
> >>>> into range-ops, which is our lowest level component.  There is no
> >>>> ranger or gori involved.  All we're doing is resolving the operation
> >>>> with the ranges passed.
> >>>>
> >>>> This is enough to avoid recursing in the case where we definitely know
> >>>> the sign of a range.  Otherwise, we still recurse.
> >>>>
> >>>> Note that instead of get_global_range_query(), we could use
> >>>> get_range_query() which uses a ranger (if active in a pass), or
> >>>> get_global_range_query if not.  This would allow passes that have an
> >>>> active ranger (with enable_ranger) to use a full ranger.  These passes
> >>>> are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
> >>>> no ranger is active, get_range_query defaults to global ranges, so
> >>>> there's no additional penalty.
> >>>>
> >>>> Would this be acceptable, at least enough to close (or rename the PR ;-))?
> >>>
> >>> I think the checks would belong to the gimple_stmt_nonnegative_warnv_p function
> >>> only (that's the SSA name entry from the fold-const.cc ones)?
> >>
> >> That was my first approach, but I thought I'd cover the unary and binary
> >> operators as well, since they had other callers.  But I'm happy with
> >> just the top-level tweak.  It's a lot less code :).
> >
> > @@ -9234,6 +9235,15 @@ bool
> >   gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p,
> >                                   int depth)
> >   {
> > +  tree type = gimple_range_type (stmt);
> > +  if (type && frange::supports_p (type))
> > +    {
> > +      frange r;
> > +      bool sign;
> > +      return (get_global_range_query ()->range_of_stmt (r, stmt)
> > +             && r.signbit_p (sign)
> > +             && sign == false);
> > +    }
> >
> > the above means we never fall through to the switch below if
> > frange::supports_p (type) - that's eventually good enough, I
> > don't think we ever call this very function directly but it gets
> > invoked via recursion through operands only.  But of course
>
> Woah, sorry.  That was not intended.  For that matter, the patch as
> posted caused:
>
> FAIL: gcc.dg/builtins-10.c (test for excess errors)
> FAIL: gcc.dg/builtins-57.c (test for excess errors)
> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O1  (test for excess errors)
> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O2  (test for excess errors)
> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O2 -flto
> -fno-use-linker-plugin -flto-partition=none  (test for excess errors)
> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O3 -g  (test for excess errors)
> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -Os  (test for excess errors)
> FAIL: gcc.dg/torture/builtin-power-1.c   -O1  (test for excess errors)
> FAIL: gcc.dg/torture/builtin-power-1.c   -O2  (test for excess errors)
> FAIL: gcc.dg/torture/builtin-power-1.c   -O2 -flto
> -fno-use-linker-plugin -flto-partition=none  (test for excess errors)
> FAIL: gcc.dg/torture/builtin-power-1.c   -O3 -g  (test for excess errors)
> FAIL: gcc.dg/torture/builtin-power-1.c   -Os  (test for excess errors)

Did you investigate why?  Because the old patch removed the recursion
while the new keeps it in case the global range isn't present which isn't
as nice.

> Note that ranger folding calls this function, though it won't run the
> risk of endless recursion because range_of_stmt uses the LHS, and only
> use global ranges to solve the LHS.
>
> Also, frange::supports_p() does not support all floats:
>
>    static bool supports_p (const_tree type)
>    {
>      // ?? Decimal floats can have multiple representations for the
>      // same number.  Supporting them may be as simple as just
>      // disabling them in singleton_p.  No clue.
>      return SCALAR_FLOAT_TYPE_P (type) && !DECIMAL_FLOAT_TYPE_P (type);
>    }

OK, _Complex types are obviously missing, so are vector ones.

> Finally, my patch is more conservative than what the *nonnegative_warn*
> friends do.  We only return true when we're sure about the sign bit and
> it's FALSE.  As I mentioned elsewhere, tree_call_nonnegative_warn_p()
> always returns true for:
>
>      CASE_CFN_ACOS:
>      CASE_CFN_ACOS_FN:
>      CASE_CFN_ACOSH:
>      CASE_CFN_ACOSH_FN:
>      CASE_CFN_CABS:
>      CASE_CFN_CABS_FN:
> ...
> ...
>        /* Always true.  */
>        return true;
>
> This means that we'll return true for a NAN, but we're incorrectly
> assuming the NAN will be +NAN.  In my proposed patch, we don't make such
> assumptions.  We only return true if the range is non-negative,
> including the NAN.

Yep, the usual issue whether nonnegative means copysign (1, x) produces
1 or whether !(x < 0) is true.

> > I wonder what types are not supported by frange and whether
> > the manual processing we fall through to does anything meaningful
> > for those?
> >
> > I won't ask you to thoroughly answer this now but please put in
> > a comment reflecting the above before the switch stmt.
> >
> >     switch (gimple_code (stmt))
> >
> >
> > Otherwise OK, in case you tree gets back to bootstrapping ;)
>
> Updated patch that passes test.
>
> OK?  And if so, can I close the PR?

Yes, I think we now track float ranges - improvements are of course
always possible.

Richard.

> Thanks.
> Aldy

Re: [PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Aldy Hernandez]

On 11/16/22 17:04, Richard Biener wrote:
> On Tue, Nov 15, 2022 at 11:46 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 11/15/22 08:15, Richard Biener wrote:
>>> On Mon, Nov 14, 2022 at 8:05 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>
>>>>
>>>>
>>>> On 11/14/22 10:12, Richard Biener wrote:
>>>>> On Sat, Nov 12, 2022 at 7:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>>>
>>>>>> It irks me that a PR named "we should track ranges for floating-point
>>>>>> hasn't been closed in this release.  This is an attempt to do just
>>>>>> that.
>>>>>>
>>>>>> As mentioned in the PR, even though we track ranges for floats, it has
>>>>>> been suggested that avoiding recursing through SSA defs in
>>>>>> gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
>>>>>> various ranger components without the need for a heavy handed approach
>>>>>> (i.e. a full ranger).
>>>>>>
>>>>>> I have implemented two versions of known_float_sign_p() that answer
>>>>>> the question whether we definitely know the sign for an operation or a
>>>>>> tree expression.
>>>>>>
>>>>>> Both versions use get_global_range_query, which is a wrapper to query
>>>>>> global ranges.  This means, that no caching or propagation is done.
>>>>>> In the case of an SSA, we just return the global range for it (think
>>>>>> SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
>>>>>> also use get_global_range_query to resolve the operands, and then call
>>>>>> into range-ops, which is our lowest level component.  There is no
>>>>>> ranger or gori involved.  All we're doing is resolving the operation
>>>>>> with the ranges passed.
>>>>>>
>>>>>> This is enough to avoid recursing in the case where we definitely know
>>>>>> the sign of a range.  Otherwise, we still recurse.
>>>>>>
>>>>>> Note that instead of get_global_range_query(), we could use
>>>>>> get_range_query() which uses a ranger (if active in a pass), or
>>>>>> get_global_range_query if not.  This would allow passes that have an
>>>>>> active ranger (with enable_ranger) to use a full ranger.  These passes
>>>>>> are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
>>>>>> no ranger is active, get_range_query defaults to global ranges, so
>>>>>> there's no additional penalty.
>>>>>>
>>>>>> Would this be acceptable, at least enough to close (or rename the PR ;-))?
>>>>>
>>>>> I think the checks would belong to the gimple_stmt_nonnegative_warnv_p function
>>>>> only (that's the SSA name entry from the fold-const.cc ones)?
>>>>
>>>> That was my first approach, but I thought I'd cover the unary and binary
>>>> operators as well, since they had other callers.  But I'm happy with
>>>> just the top-level tweak.  It's a lot less code :).
>>>
>>> @@ -9234,6 +9235,15 @@ bool
>>>    gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p,
>>>                                    int depth)
>>>    {
>>> +  tree type = gimple_range_type (stmt);
>>> +  if (type && frange::supports_p (type))
>>> +    {
>>> +      frange r;
>>> +      bool sign;
>>> +      return (get_global_range_query ()->range_of_stmt (r, stmt)
>>> +             && r.signbit_p (sign)
>>> +             && sign == false);
>>> +    }
>>>
>>> the above means we never fall through to the switch below if
>>> frange::supports_p (type) - that's eventually good enough, I
>>> don't think we ever call this very function directly but it gets
>>> invoked via recursion through operands only.  But of course
>>
>> Woah, sorry.  That was not intended.  For that matter, the patch as
>> posted caused:
>>
>> FAIL: gcc.dg/builtins-10.c (test for excess errors)
>> FAIL: gcc.dg/builtins-57.c (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O1  (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O2  (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O2 -flto
>> -fno-use-linker-plugin -flto-partition=none  (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O3 -g  (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -Os  (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-power-1.c   -O1  (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-power-1.c   -O2  (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-power-1.c   -O2 -flto
>> -fno-use-linker-plugin -flto-partition=none  (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-power-1.c   -O3 -g  (test for excess errors)
>> FAIL: gcc.dg/torture/builtin-power-1.c   -Os  (test for excess errors)
> 
> Did you investigate why?  Because the old patch removed the recursion
> while the new keeps it in case the global range isn't present which isn't
> as nice.

For gcc.dg/builtins-10.c, there are a few calls to 
gimple_stmt_nonnegative* that are being made before we have global 
ranges (ccp1 and forwprop1), so the query returns VARYING (i.e. no known 
sign).  If you're curious, the call to gimple_stmt_nonnegative* comes 
via courtesy of match.pd:

/* Canonicalization of sequences of math builtins.  These rules represent
    IL simplifications but are not necessarily optimizations.

So ISTM, we still need to fall through if we're being called before 
global ranges are available.

After global ranges are available (evrp), we would avoid further lookups 
if it weren't for an unrelated problem I found.

foperator_abs::fold_range() is trying to set a range of [+0.0, +INF], 
but this little snpipet in the frange normalization code adds a -0.0 to 
the range:

   else if (!HONOR_SIGNED_ZEROS (m_type))
     {
       if (real_iszero (&m_max, 1))
	m_max.sign = 0;
       if (real_iszero (&m_min, 0))
	m_min.sign = 1;
     }

We end up with:

[frange] double [-0.0 (-0x0.0p+0), 
1.79769313486231570814527423731704356798070567525844996599e+308 
(0x0.fffffffffffff8p+1024)]

I must say this is beyond my paygrade :).  Jakub, it was your suggestion 
to add the snippet above.  Is this correct?  Note that this test is for 
-ffast-math.

If I comment out the code above, the regressions are fixed, both with my 
current patch or with the original one.  But as I suggested, maybe we 
want the second patch, because we may be called before global ranges are 
available.

IMHO, we could go with the second patch, and fix the ABS problem 
independently.

Yay?  Nay?

Aldy

> 
>> Note that ranger folding calls this function, though it won't run the
>> risk of endless recursion because range_of_stmt uses the LHS, and only
>> use global ranges to solve the LHS.
>>
>> Also, frange::supports_p() does not support all floats:
>>
>>     static bool supports_p (const_tree type)
>>     {
>>       // ?? Decimal floats can have multiple representations for the
>>       // same number.  Supporting them may be as simple as just
>>       // disabling them in singleton_p.  No clue.
>>       return SCALAR_FLOAT_TYPE_P (type) && !DECIMAL_FLOAT_TYPE_P (type);
>>     }
> 
> OK, _Complex types are obviously missing, so are vector ones.
> 
>> Finally, my patch is more conservative than what the *nonnegative_warn*
>> friends do.  We only return true when we're sure about the sign bit and
>> it's FALSE.  As I mentioned elsewhere, tree_call_nonnegative_warn_p()
>> always returns true for:
>>
>>       CASE_CFN_ACOS:
>>       CASE_CFN_ACOS_FN:
>>       CASE_CFN_ACOSH:
>>       CASE_CFN_ACOSH_FN:
>>       CASE_CFN_CABS:
>>       CASE_CFN_CABS_FN:
>> ...
>> ...
>>         /* Always true.  */
>>         return true;
>>
>> This means that we'll return true for a NAN, but we're incorrectly
>> assuming the NAN will be +NAN.  In my proposed patch, we don't make such
>> assumptions.  We only return true if the range is non-negative,
>> including the NAN.
> 
> Yep, the usual issue whether nonnegative means copysign (1, x) produces
> 1 or whether !(x < 0) is true.
> 
>>> I wonder what types are not supported by frange and whether
>>> the manual processing we fall through to does anything meaningful
>>> for those?
>>>
>>> I won't ask you to thoroughly answer this now but please put in
>>> a comment reflecting the above before the switch stmt.
>>>
>>>      switch (gimple_code (stmt))
>>>
>>>
>>> Otherwise OK, in case you tree gets back to bootstrapping ;)
>>
>> Updated patch that passes test.
>>
>> OK?  And if so, can I close the PR?
> 
> Yes, I think we now track float ranges - improvements are of course
> always possible.
> 
> Richard.
> 
>> Thanks.
>> Aldy
> 

Re: [PATCH] [PR68097] Try to avoid recursing for floats in tree_*_nonnegative_warnv_p.

[Richard Biener]

On Wed, Nov 16, 2022 at 6:38 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 11/16/22 17:04, Richard Biener wrote:
> > On Tue, Nov 15, 2022 at 11:46 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >>
> >>
> >> On 11/15/22 08:15, Richard Biener wrote:
> >>> On Mon, Nov 14, 2022 at 8:05 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>>>
> >>>>
> >>>>
> >>>> On 11/14/22 10:12, Richard Biener wrote:
> >>>>> On Sat, Nov 12, 2022 at 7:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>>>>>
> >>>>>> It irks me that a PR named "we should track ranges for floating-point
> >>>>>> hasn't been closed in this release.  This is an attempt to do just
> >>>>>> that.
> >>>>>>
> >>>>>> As mentioned in the PR, even though we track ranges for floats, it has
> >>>>>> been suggested that avoiding recursing through SSA defs in
> >>>>>> gimple_assign_nonnegative_warnv_p is also a goal.  We can do this with
> >>>>>> various ranger components without the need for a heavy handed approach
> >>>>>> (i.e. a full ranger).
> >>>>>>
> >>>>>> I have implemented two versions of known_float_sign_p() that answer
> >>>>>> the question whether we definitely know the sign for an operation or a
> >>>>>> tree expression.
> >>>>>>
> >>>>>> Both versions use get_global_range_query, which is a wrapper to query
> >>>>>> global ranges.  This means, that no caching or propagation is done.
> >>>>>> In the case of an SSA, we just return the global range for it (think
> >>>>>> SSA_NAME_RANGE_INFO).  In the case of a tree code with operands, we
> >>>>>> also use get_global_range_query to resolve the operands, and then call
> >>>>>> into range-ops, which is our lowest level component.  There is no
> >>>>>> ranger or gori involved.  All we're doing is resolving the operation
> >>>>>> with the ranges passed.
> >>>>>>
> >>>>>> This is enough to avoid recursing in the case where we definitely know
> >>>>>> the sign of a range.  Otherwise, we still recurse.
> >>>>>>
> >>>>>> Note that instead of get_global_range_query(), we could use
> >>>>>> get_range_query() which uses a ranger (if active in a pass), or
> >>>>>> get_global_range_query if not.  This would allow passes that have an
> >>>>>> active ranger (with enable_ranger) to use a full ranger.  These passes
> >>>>>> are currently, VRP, loop unswitching, DOM, loop versioning, etc.  If
> >>>>>> no ranger is active, get_range_query defaults to global ranges, so
> >>>>>> there's no additional penalty.
> >>>>>>
> >>>>>> Would this be acceptable, at least enough to close (or rename the PR ;-))?
> >>>>>
> >>>>> I think the checks would belong to the gimple_stmt_nonnegative_warnv_p function
> >>>>> only (that's the SSA name entry from the fold-const.cc ones)?
> >>>>
> >>>> That was my first approach, but I thought I'd cover the unary and binary
> >>>> operators as well, since they had other callers.  But I'm happy with
> >>>> just the top-level tweak.  It's a lot less code :).
> >>>
> >>> @@ -9234,6 +9235,15 @@ bool
> >>>    gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p,
> >>>                                    int depth)
> >>>    {
> >>> +  tree type = gimple_range_type (stmt);
> >>> +  if (type && frange::supports_p (type))
> >>> +    {
> >>> +      frange r;
> >>> +      bool sign;
> >>> +      return (get_global_range_query ()->range_of_stmt (r, stmt)
> >>> +             && r.signbit_p (sign)
> >>> +             && sign == false);
> >>> +    }
> >>>
> >>> the above means we never fall through to the switch below if
> >>> frange::supports_p (type) - that's eventually good enough, I
> >>> don't think we ever call this very function directly but it gets
> >>> invoked via recursion through operands only.  But of course
> >>
> >> Woah, sorry.  That was not intended.  For that matter, the patch as
> >> posted caused:
> >>
> >> FAIL: gcc.dg/builtins-10.c (test for excess errors)
> >> FAIL: gcc.dg/builtins-57.c (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O1  (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O2  (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O2 -flto
> >> -fno-use-linker-plugin -flto-partition=none  (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -O3 -g  (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-nonneg-1.c   -Os  (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-power-1.c   -O1  (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-power-1.c   -O2  (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-power-1.c   -O2 -flto
> >> -fno-use-linker-plugin -flto-partition=none  (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-power-1.c   -O3 -g  (test for excess errors)
> >> FAIL: gcc.dg/torture/builtin-power-1.c   -Os  (test for excess errors)
> >
> > Did you investigate why?  Because the old patch removed the recursion
> > while the new keeps it in case the global range isn't present which isn't
> > as nice.
>
> For gcc.dg/builtins-10.c, there are a few calls to
> gimple_stmt_nonnegative* that are being made before we have global
> ranges (ccp1 and forwprop1), so the query returns VARYING (i.e. no known
> sign).  If you're curious, the call to gimple_stmt_nonnegative* comes
> via courtesy of match.pd:
>
> /* Canonicalization of sequences of math builtins.  These rules represent
>     IL simplifications but are not necessarily optimizations.
>
> So ISTM, we still need to fall through if we're being called before
> global ranges are available.
>
> After global ranges are available (evrp), we would avoid further lookups
> if it weren't for an unrelated problem I found.
>
> foperator_abs::fold_range() is trying to set a range of [+0.0, +INF],
> but this little snpipet in the frange normalization code adds a -0.0 to
> the range:
>
>    else if (!HONOR_SIGNED_ZEROS (m_type))
>      {
>        if (real_iszero (&m_max, 1))
>         m_max.sign = 0;
>        if (real_iszero (&m_min, 0))
>         m_min.sign = 1;
>      }
>
> We end up with:
>
> [frange] double [-0.0 (-0x0.0p+0),
> 1.79769313486231570814527423731704356798070567525844996599e+308
> (0x0.fffffffffffff8p+1024)]
>
> I must say this is beyond my paygrade :).  Jakub, it was your suggestion
> to add the snippet above.  Is this correct?  Note that this test is for
> -ffast-math.
>
> If I comment out the code above, the regressions are fixed, both with my
> current patch or with the original one.  But as I suggested, maybe we
> want the second patch, because we may be called before global ranges are
> available.
>
> IMHO, we could go with the second patch, and fix the ABS problem
> independently.
>
> Yay?  Nay?

Yes, the 2nd patch is approved, I was just curious.

Richard.

> Aldy
>
> >
> >> Note that ranger folding calls this function, though it won't run the
> >> risk of endless recursion because range_of_stmt uses the LHS, and only
> >> use global ranges to solve the LHS.
> >>
> >> Also, frange::supports_p() does not support all floats:
> >>
> >>     static bool supports_p (const_tree type)
> >>     {
> >>       // ?? Decimal floats can have multiple representations for the
> >>       // same number.  Supporting them may be as simple as just
> >>       // disabling them in singleton_p.  No clue.
> >>       return SCALAR_FLOAT_TYPE_P (type) && !DECIMAL_FLOAT_TYPE_P (type);
> >>     }
> >
> > OK, _Complex types are obviously missing, so are vector ones.
> >
> >> Finally, my patch is more conservative than what the *nonnegative_warn*
> >> friends do.  We only return true when we're sure about the sign bit and
> >> it's FALSE.  As I mentioned elsewhere, tree_call_nonnegative_warn_p()
> >> always returns true for:
> >>
> >>       CASE_CFN_ACOS:
> >>       CASE_CFN_ACOS_FN:
> >>       CASE_CFN_ACOSH:
> >>       CASE_CFN_ACOSH_FN:
> >>       CASE_CFN_CABS:
> >>       CASE_CFN_CABS_FN:
> >> ...
> >> ...
> >>         /* Always true.  */
> >>         return true;
> >>
> >> This means that we'll return true for a NAN, but we're incorrectly
> >> assuming the NAN will be +NAN.  In my proposed patch, we don't make such
> >> assumptions.  We only return true if the range is non-negative,
> >> including the NAN.
> >
> > Yep, the usual issue whether nonnegative means copysign (1, x) produces
> > 1 or whether !(x < 0) is true.
> >
> >>> I wonder what types are not supported by frange and whether
> >>> the manual processing we fall through to does anything meaningful
> >>> for those?
> >>>
> >>> I won't ask you to thoroughly answer this now but please put in
> >>> a comment reflecting the above before the switch stmt.
> >>>
> >>>      switch (gimple_code (stmt))
> >>>
> >>>
> >>> Otherwise OK, in case you tree gets back to bootstrapping ;)
> >>
> >> Updated patch that passes test.
> >>
> >> OK?  And if so, can I close the PR?
> >
> > Yes, I think we now track float ranges - improvements are of course
> > always possible.
> >
> > Richard.
> >
> >> Thanks.
> >> Aldy
> >
>