diff mbox series

Saturate overflows return from SCEV in ranger.

Message ID 20201020152039.336641-1-aldyh@redhat.com
State New
Headers show
Series Saturate overflows return from SCEV in ranger. | expand

Commit Message

Aldy Hernandez Oct. 20, 2020, 3:20 p.m. UTC 
bounds_of_var_in_loop is returning an overflowed int, which is causing
us to create a range for which we can't compare the bounds causing
an ICE in verify_range.

Overflowed bounds cause compare_values() to return -2, which we
don't handle in verify_range.

We don't represent overflowed ranges in irange, so this patch just
saturates any overflowed end-points to MIN or MAX.

Pushed.

gcc/ChangeLog:

	PR 97501/tree-optimization
	* gimple-range.cc (gimple_ranger::range_of_ssa_name_with_loop_info):
	Saturate overflows returned from SCEV.

gcc/testsuite/ChangeLog:

	* gcc.dg/pr97501.c: New test.
---
 gcc/gimple-range.cc            |  4 ++--
 gcc/testsuite/gcc.dg/pr97501.c | 14 ++++++++++++++
 2 files changed, 16 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr97501.c

Comments

Richard Biener Oct. 21, 2020, 6:19 a.m. UTC | #1 
On Tue, Oct 20, 2020 at 5:21 PM Aldy Hernandez via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> bounds_of_var_in_loop is returning an overflowed int, which is causing
> us to create a range for which we can't compare the bounds causing
> an ICE in verify_range.
>
> Overflowed bounds cause compare_values() to return -2, which we
> don't handle in verify_range.
>
> We don't represent overflowed ranges in irange, so this patch just
> saturates any overflowed end-points to MIN or MAX.

I don't think TREE_OVERFLOW means what you think it means in the
context of bounds_of_var_in_loop - look at its bottom which does

  /* Even for valid range info, sometimes overflow flag will leak in.
     As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
     drop them.  */
  if (TREE_OVERFLOW_P (*min))
    *min = drop_tree_overflow (*min);
  if (TREE_OVERFLOW_P (*max))
    *max = drop_tree_overflow (*max);

and the code explicitly checks for overflow, doing range adjustments
accordingly.

So not sure what you're trying to fix here.

Every use of TREE_OVERFLOW in the GIMPLE parts of the ME are a sign of a bug.

Richard.

> Pushed.
>
> gcc/ChangeLog:
>
>         PR 97501/tree-optimization
>         * gimple-range.cc (gimple_ranger::range_of_ssa_name_with_loop_info):
>         Saturate overflows returned from SCEV.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/pr97501.c: New test.
> ---
>  gcc/gimple-range.cc            |  4 ++--
>  gcc/testsuite/gcc.dg/pr97501.c | 14 ++++++++++++++
>  2 files changed, 16 insertions(+), 2 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/pr97501.c
>
> diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
> index e4864ba60f6..ed9609be68e 100644
> --- a/gcc/gimple-range.cc
> +++ b/gcc/gimple-range.cc
> @@ -1146,9 +1146,9 @@ gimple_ranger::range_of_ssa_name_with_loop_info (irange &r, tree name,
>        // ?? We could do better here.  Since MIN/MAX can only be an
>        // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call
>        // the ranger and solve anything not an integer.
> -      if (TREE_CODE (min) != INTEGER_CST)
> +      if (TREE_CODE (min) != INTEGER_CST || TREE_OVERFLOW (min))
>         min = vrp_val_min (type);
> -      if (TREE_CODE (max) != INTEGER_CST)
> +      if (TREE_CODE (max) != INTEGER_CST || TREE_OVERFLOW (max))
>         max = vrp_val_max (type);
>        r.set (min, max);
>      }
> diff --git a/gcc/testsuite/gcc.dg/pr97501.c b/gcc/testsuite/gcc.dg/pr97501.c
> new file mode 100644
> index 00000000000..aedac83962d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr97501.c
> @@ -0,0 +1,14 @@
> +// { dg-do compile }
> +// { dg-options "-O2" }
> +
> +static int c = 0;
> +
> +int main() {
> +  int b = 0;
> +  if (c) {
> +  for (;; b--)
> +    do
> +      b++;
> +    while (b);
> +  }
> +}
> --
> 2.26.2
>
Aldy Hernandez Oct. 21, 2020, 7:30 a.m. UTC | #2 
On 10/21/20 8:19 AM, Richard Biener wrote:
> On Tue, Oct 20, 2020 at 5:21 PM Aldy Hernandez via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>>
>> bounds_of_var_in_loop is returning an overflowed int, which is causing
>> us to create a range for which we can't compare the bounds causing
>> an ICE in verify_range.
>>
>> Overflowed bounds cause compare_values() to return -2, which we
>> don't handle in verify_range.
>>
>> We don't represent overflowed ranges in irange, so this patch just
>> saturates any overflowed end-points to MIN or MAX.
> 
> I don't think TREE_OVERFLOW means what you think it means in the
> context of bounds_of_var_in_loop - look at its bottom which does
> 
>    /* Even for valid range info, sometimes overflow flag will leak in.
>       As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
>       drop them.  */
>    if (TREE_OVERFLOW_P (*min))
>      *min = drop_tree_overflow (*min);
>    if (TREE_OVERFLOW_P (*max))
>      *max = drop_tree_overflow (*max);

Interesting.

If these values "leaked" in.  Should they have been fixed at the source, 
instead of after the fact?  You mention below that every use of 
TREE_OVERFLOW in the ME is a bug, should we clean them up before 
arriving in gimple, or are there legitimate uses of it?

> 
> and the code explicitly checks for overflow, doing range adjustments
> accordingly.

Well, not all overflows are adjusted:

   /* Like in PR19590, scev can return a constant function.  */
   if (is_gimple_min_invariant (chrec))
     {
       *min = *max = chrec;
       return true;
     }

Are these min/max not adjusted for overflow by design, or is this an 
oversight?

If the latter, we could instead what I do below.  What do you think?

Thanks for the feedback.
Aldy

diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index b790d62d75f..c5520e0700b 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -1156,9 +1156,9 @@ gimple_ranger::range_of_ssa_name_with_loop_info 
(irange &r, tree name,
        // ?? We could do better here.  Since MIN/MAX can only be an
        // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call
        // the ranger and solve anything not an integer.
-      if (TREE_CODE (min) != INTEGER_CST || TREE_OVERFLOW (min))
+      if (TREE_CODE (min) != INTEGER_CST)
  	min = vrp_val_min (type);
-      if (TREE_CODE (max) != INTEGER_CST || TREE_OVERFLOW (max))
+      if (TREE_CODE (max) != INTEGER_CST)
  	max = vrp_val_max (type);
        r.set (min, max);
      }
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 67c88006f13..7778ceccf0a 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -1844,7 +1844,7 @@ bounds_of_var_in_loop (tree *min, tree *max, 
range_query *query,
    if (is_gimple_min_invariant (chrec))
      {
        *min = *max = chrec;
-      return true;
+      goto fix_overflow;
      }

    if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
@@ -1964,6 +1964,7 @@ bounds_of_var_in_loop (tree *min, tree *max, 
range_query *query,
    else
      *min = init;

+ fix_overflow:
    /* Even for valid range info, sometimes overflow flag will leak in.
       As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
       drop them.  */
Richard Biener Oct. 21, 2020, 7:59 a.m. UTC | #3 
On Wed, Oct 21, 2020 at 9:30 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 10/21/20 8:19 AM, Richard Biener wrote:
> > On Tue, Oct 20, 2020 at 5:21 PM Aldy Hernandez via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >>
> >> bounds_of_var_in_loop is returning an overflowed int, which is causing
> >> us to create a range for which we can't compare the bounds causing
> >> an ICE in verify_range.
> >>
> >> Overflowed bounds cause compare_values() to return -2, which we
> >> don't handle in verify_range.
> >>
> >> We don't represent overflowed ranges in irange, so this patch just
> >> saturates any overflowed end-points to MIN or MAX.
> >
> > I don't think TREE_OVERFLOW means what you think it means in the
> > context of bounds_of_var_in_loop - look at its bottom which does
> >
> >    /* Even for valid range info, sometimes overflow flag will leak in.
> >       As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
> >       drop them.  */
> >    if (TREE_OVERFLOW_P (*min))
> >      *min = drop_tree_overflow (*min);
> >    if (TREE_OVERFLOW_P (*max))
> >      *max = drop_tree_overflow (*max);
>
> Interesting.
>
> If these values "leaked" in.  Should they have been fixed at the source,
> instead of after the fact?  You mention below that every use of
> TREE_OVERFLOW in the ME is a bug, should we clean them up before
> arriving in gimple, or are there legitimate uses of it?

There are no legitimate uses in GIMPLE.  They are (ab-)used by
GENERIC folding for propagating overflow (also used in FE
diagnostics).  Generally the better way is to use wide_ints overflow
handling which also "sticks".

> >
> > and the code explicitly checks for overflow, doing range adjustments
> > accordingly.
>
> Well, not all overflows are adjusted:
>
>    /* Like in PR19590, scev can return a constant function.  */
>    if (is_gimple_min_invariant (chrec))
>      {
>        *min = *max = chrec;
>        return true;
>      }
>
> Are these min/max not adjusted for overflow by design, or is this an
> oversight?

Ah, that's an oversight here.  And yes, "fixing" it in scalar evolution
analysis itself (dropping the flag there) would be best

>
> If the latter, we could instead what I do below.  What do you think?

Yeah, though *cough* goto ... (well, not so bad I guess)

Thanks,
Richard.

> Thanks for the feedback.
> Aldy
>
> diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
> index b790d62d75f..c5520e0700b 100644
> --- a/gcc/gimple-range.cc
> +++ b/gcc/gimple-range.cc
> @@ -1156,9 +1156,9 @@ gimple_ranger::range_of_ssa_name_with_loop_info
> (irange &r, tree name,
>         // ?? We could do better here.  Since MIN/MAX can only be an
>         // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call
>         // the ranger and solve anything not an integer.
> -      if (TREE_CODE (min) != INTEGER_CST || TREE_OVERFLOW (min))
> +      if (TREE_CODE (min) != INTEGER_CST)
>         min = vrp_val_min (type);
> -      if (TREE_CODE (max) != INTEGER_CST || TREE_OVERFLOW (max))
> +      if (TREE_CODE (max) != INTEGER_CST)
>         max = vrp_val_max (type);
>         r.set (min, max);
>       }
> diff --git a/gcc/vr-values.c b/gcc/vr-values.c
> index 67c88006f13..7778ceccf0a 100644
> --- a/gcc/vr-values.c
> +++ b/gcc/vr-values.c
> @@ -1844,7 +1844,7 @@ bounds_of_var_in_loop (tree *min, tree *max,
> range_query *query,
>     if (is_gimple_min_invariant (chrec))
>       {
>         *min = *max = chrec;
> -      return true;
> +      goto fix_overflow;
>       }
>
>     if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
> @@ -1964,6 +1964,7 @@ bounds_of_var_in_loop (tree *min, tree *max,
> range_query *query,
>     else
>       *min = init;
>
> + fix_overflow:
>     /* Even for valid range info, sometimes overflow flag will leak in.
>        As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
>        drop them.  */
>
Aldy Hernandez Oct. 21, 2020, 8:50 a.m. UTC | #4 
On 10/21/20 9:59 AM, Richard Biener wrote:

>>>     /* Even for valid range info, sometimes overflow flag will leak in.
>>>        As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
>>>        drop them.  */
>>>     if (TREE_OVERFLOW_P (*min))
>>>       *min = drop_tree_overflow (*min);
>>>     if (TREE_OVERFLOW_P (*max))
>>>       *max = drop_tree_overflow (*max);
>>
>> Interesting.
>>
>> If these values "leaked" in.  Should they have been fixed at the source,
>> instead of after the fact?  You mention below that every use of
>> TREE_OVERFLOW in the ME is a bug, should we clean them up before
>> arriving in gimple, or are there legitimate uses of it?
> 
> There are no legitimate uses in GIMPLE.  They are (ab-)used by
> GENERIC folding for propagating overflow (also used in FE
> diagnostics).  Generally the better way is to use wide_ints overflow
> handling which also "sticks".

If there are no legitimate uses, perhaps we should drop them altogether 
as we go into GIMPLE??  I vaguely recall seeing them leak into 
value_range's.

> 
>>>
>>> and the code explicitly checks for overflow, doing range adjustments
>>> accordingly.
>>
>> Well, not all overflows are adjusted:
>>
>>     /* Like in PR19590, scev can return a constant function.  */
>>     if (is_gimple_min_invariant (chrec))
>>       {
>>         *min = *max = chrec;
>>         return true;
>>       }
>>
>> Are these min/max not adjusted for overflow by design, or is this an
>> oversight?
> 
> Ah, that's an oversight here.  And yes, "fixing" it in scalar evolution
> analysis itself (dropping the flag there) would be best

Excellent.  I've pushed the patch below after testing it.

Thanks again.
Aldy

     Adjust overflow for invariants in bounds_of_var_in_loop.

     Invariants returned from SCEV can have TREE_OVERFLOW set.  Clear the
     overflow as we do with the rest of the values returned from this
     function.

     gcc/ChangeLog:

             * gimple-range.cc 
(gimple_ranger::range_of_ssa_name_with_loop_info):
             Remove TREE_OVERFLOW special case.
             * vr-values.c (bounds_of_var_in_loop): Adjust overflow for
             invariants.

diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index b790d62d75f..c5520e0700b 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -1156,9 +1156,9 @@ gimple_ranger::range_of_ssa_name_with_loop_info 
(irange &r, tree name,
        // ?? We could do better here.  Since MIN/MAX can only be an
        // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call
        // the ranger and solve anything not an integer.
-      if (TREE_CODE (min) != INTEGER_CST || TREE_OVERFLOW (min))
+      if (TREE_CODE (min) != INTEGER_CST)
  	min = vrp_val_min (type);
-      if (TREE_CODE (max) != INTEGER_CST || TREE_OVERFLOW (max))
+      if (TREE_CODE (max) != INTEGER_CST)
  	max = vrp_val_max (type);
        r.set (min, max);
      }
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index cc0ddca2bd3..7a0e70eab64 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -1844,7 +1844,7 @@ bounds_of_var_in_loop (tree *min, tree *max, 
range_query *query,
    if (is_gimple_min_invariant (chrec))
      {
        *min = *max = chrec;
-      return true;
+      goto fix_overflow;
      }

    if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
@@ -1964,6 +1964,7 @@ bounds_of_var_in_loop (tree *min, tree *max, 
range_query *query,
    else
      *min = init;

+ fix_overflow:
    /* Even for valid range info, sometimes overflow flag will leak in.
       As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
       drop them.  */
Richard Biener Oct. 21, 2020, 9:31 a.m. UTC | #5 
On Wed, Oct 21, 2020 at 10:50 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 10/21/20 9:59 AM, Richard Biener wrote:
>
> >>>     /* Even for valid range info, sometimes overflow flag will leak in.
> >>>        As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
> >>>        drop them.  */
> >>>     if (TREE_OVERFLOW_P (*min))
> >>>       *min = drop_tree_overflow (*min);
> >>>     if (TREE_OVERFLOW_P (*max))
> >>>       *max = drop_tree_overflow (*max);
> >>
> >> Interesting.
> >>
> >> If these values "leaked" in.  Should they have been fixed at the source,
> >> instead of after the fact?  You mention below that every use of
> >> TREE_OVERFLOW in the ME is a bug, should we clean them up before
> >> arriving in gimple, or are there legitimate uses of it?
> >
> > There are no legitimate uses in GIMPLE.  They are (ab-)used by
> > GENERIC folding for propagating overflow (also used in FE
> > diagnostics).  Generally the better way is to use wide_ints overflow
> > handling which also "sticks".
>
> If there are no legitimate uses, perhaps we should drop them altogether
> as we go into GIMPLE??

We do, but they tend to creep back in by infrastructure using the
GENERIC folder.  Some key places make sure to clear them (I've tracked
down a lot of them).  But I was never bave enough to assert they do
not end up in IL operands ;)

>  I vaguely recall seeing them leak into
> value_range's.
> >
> >>>
> >>> and the code explicitly checks for overflow, doing range adjustments
> >>> accordingly.
> >>
> >> Well, not all overflows are adjusted:
> >>
> >>     /* Like in PR19590, scev can return a constant function.  */
> >>     if (is_gimple_min_invariant (chrec))
> >>       {
> >>         *min = *max = chrec;
> >>         return true;
> >>       }
> >>
> >> Are these min/max not adjusted for overflow by design, or is this an
> >> oversight?
> >
> > Ah, that's an oversight here.  And yes, "fixing" it in scalar evolution
> > analysis itself (dropping the flag there) would be best
>
> Excellent.  I've pushed the patch below after testing it.
>
> Thanks again.
> Aldy
>
>      Adjust overflow for invariants in bounds_of_var_in_loop.
>
>      Invariants returned from SCEV can have TREE_OVERFLOW set.  Clear the
>      overflow as we do with the rest of the values returned from this
>      function.
>
>      gcc/ChangeLog:
>
>              * gimple-range.cc
> (gimple_ranger::range_of_ssa_name_with_loop_info):
>              Remove TREE_OVERFLOW special case.
>              * vr-values.c (bounds_of_var_in_loop): Adjust overflow for
>              invariants.
>
> diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
> index b790d62d75f..c5520e0700b 100644
> --- a/gcc/gimple-range.cc
> +++ b/gcc/gimple-range.cc
> @@ -1156,9 +1156,9 @@ gimple_ranger::range_of_ssa_name_with_loop_info
> (irange &r, tree name,
>         // ?? We could do better here.  Since MIN/MAX can only be an
>         // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call
>         // the ranger and solve anything not an integer.
> -      if (TREE_CODE (min) != INTEGER_CST || TREE_OVERFLOW (min))
> +      if (TREE_CODE (min) != INTEGER_CST)
>         min = vrp_val_min (type);
> -      if (TREE_CODE (max) != INTEGER_CST || TREE_OVERFLOW (max))
> +      if (TREE_CODE (max) != INTEGER_CST)
>         max = vrp_val_max (type);
>         r.set (min, max);
>       }
> diff --git a/gcc/vr-values.c b/gcc/vr-values.c
> index cc0ddca2bd3..7a0e70eab64 100644
> --- a/gcc/vr-values.c
> +++ b/gcc/vr-values.c
> @@ -1844,7 +1844,7 @@ bounds_of_var_in_loop (tree *min, tree *max,
> range_query *query,
>     if (is_gimple_min_invariant (chrec))
>       {
>         *min = *max = chrec;
> -      return true;
> +      goto fix_overflow;
>       }
>
>     if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
> @@ -1964,6 +1964,7 @@ bounds_of_var_in_loop (tree *min, tree *max,
> range_query *query,
>     else
>       *min = init;
>
> + fix_overflow:
>     /* Even for valid range info, sometimes overflow flag will leak in.
>        As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
>        drop them.  */
>
diff mbox series

Patch

diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index e4864ba60f6..ed9609be68e 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -1146,9 +1146,9 @@  gimple_ranger::range_of_ssa_name_with_loop_info (irange &r, tree name,
       // ?? We could do better here.  Since MIN/MAX can only be an
       // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call
       // the ranger and solve anything not an integer.
-      if (TREE_CODE (min) != INTEGER_CST)
+      if (TREE_CODE (min) != INTEGER_CST || TREE_OVERFLOW (min))
 	min = vrp_val_min (type);
-      if (TREE_CODE (max) != INTEGER_CST)
+      if (TREE_CODE (max) != INTEGER_CST || TREE_OVERFLOW (max))
 	max = vrp_val_max (type);
       r.set (min, max);
     }
diff --git a/gcc/testsuite/gcc.dg/pr97501.c b/gcc/testsuite/gcc.dg/pr97501.c
new file mode 100644
index 00000000000..aedac83962d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr97501.c
@@ -0,0 +1,14 @@ 
+// { dg-do compile }
+// { dg-options "-O2" }
+
+static int c = 0;
+
+int main() {
+  int b = 0;
+  if (c) {
+  for (;; b--)
+    do
+      b++;
+    while (b);
+  }
+}