[RFA,PATCH] Bail in bounds_of_var_in_loop if no step found.

[RFA,PATCH] Bail in bounds_of_var_in_loop if no step found.

[Aldy Hernandez]

[Neither Andrew nor I are familiar with the SCEV code.  We treat it as a
black box :).  So we could use a SCEV expert here.]

In bounds_of_var_in_loop, evolution_part_in_loop_num is returning NULL:

   step = evolution_part_in_loop_num (chrec, loop->num);

and we ICE while trying to calculate the range for STEP.

This is for:

(gdb) dd stmt
qx.0_3 = PHI <qx.0_1(3)>
(gdb) dd var
qx.0_3

It looks like NULL is a perfectly valid response from
evolution_part_in_loop_num.  Should we just bail if NULL?

If bailing is the correct solution, the following patch fixes the PR and
passes tests.

Thanks.
Aldy

gcc/ChangeLog:

	PR tree-optimization/97396
	* vr-values.c (bounds_of_var_in_loop): Bail on no step.

gcc/testsuite/ChangeLog:

	* gcc.dg/pr97396.c: New test.
---
 gcc/testsuite/gcc.dg/pr97396.c | 23 +++++++++++++++++++++++
 gcc/vr-values.c                |  2 ++
 2 files changed, 25 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr97396.c

diff --git a/gcc/testsuite/gcc.dg/pr97396.c b/gcc/testsuite/gcc.dg/pr97396.c
new file mode 100644
index 00000000000..d992c11f238
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr97396.c
@@ -0,0 +1,23 @@
+// { dg-do compile }
+// { dg-options "-O1 -ftree-vrp" }
+// { dg-additional-options "-m32" { target { i?86-*-* x86_64-*-* } } }
+
+unsigned int
+po (char *os, unsigned int al)
+{
+  for (;;)
+    {
+      int qx = 0;
+
+      while (al < 1)
+        {
+          char *cw;
+
+          cw = os + qx;
+          if (cw)
+            return al + qx;
+
+          qx += sizeof *cw;
+        }
+    }
+}
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index da0b249278b..16f6c629f29 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -1827,6 +1827,8 @@ bounds_of_var_in_loop (tree *min, tree *max, range_query *query,
 
   init = initial_condition_in_loop_num (chrec, loop->num);
   step = evolution_part_in_loop_num (chrec, loop->num);
+  if (step == NULL_TREE)
+    return false;
 
   /* If INIT is an SSA with a singleton range, set INIT to said
      singleton, otherwise leave INIT alone.  */
-- 
2.25.4

Re: [RFA,PATCH] Bail in bounds_of_var_in_loop if no step found.

[Richard Biener]

On October 13, 2020 5:17:48 PM GMT+02:00, Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>[Neither Andrew nor I are familiar with the SCEV code.  We treat it as
>a
>black box :).  So we could use a SCEV expert here.]
>
>In bounds_of_var_in_loop, evolution_part_in_loop_num is returning NULL:
>
>   step = evolution_part_in_loop_num (chrec, loop->num);

It means that Var doesn't vary in the loop. 
That is, chrec isn't a polynomial chrec. 

>and we ICE while trying to calculate the range for STEP.
>
>This is for:
>
>(gdb) dd stmt
>qx.0_3 = PHI <qx.0_1(3)>
>(gdb) dd var
>qx.0_3
>
>It looks like NULL is a perfectly valid response from
>evolution_part_in_loop_num.  Should we just bail if NULL?
>
>If bailing is the correct solution, the following patch fixes the PR
>and
>passes tests.
>
>Thanks.
>Aldy
>
>gcc/ChangeLog:
>
>	PR tree-optimization/97396
>	* vr-values.c (bounds_of_var_in_loop): Bail on no step.
>
>gcc/testsuite/ChangeLog:
>
>	* gcc.dg/pr97396.c: New test.
>---
> gcc/testsuite/gcc.dg/pr97396.c | 23 +++++++++++++++++++++++
> gcc/vr-values.c                |  2 ++
> 2 files changed, 25 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/pr97396.c
>
>diff --git a/gcc/testsuite/gcc.dg/pr97396.c
>b/gcc/testsuite/gcc.dg/pr97396.c
>new file mode 100644
>index 00000000000..d992c11f238
>--- /dev/null
>+++ b/gcc/testsuite/gcc.dg/pr97396.c
>@@ -0,0 +1,23 @@
>+// { dg-do compile }
>+// { dg-options "-O1 -ftree-vrp" }
>+// { dg-additional-options "-m32" { target { i?86-*-* x86_64-*-* } } }
>+
>+unsigned int
>+po (char *os, unsigned int al)
>+{
>+  for (;;)
>+    {
>+      int qx = 0;
>+
>+      while (al < 1)
>+        {
>+          char *cw;
>+
>+          cw = os + qx;
>+          if (cw)
>+            return al + qx;
>+
>+          qx += sizeof *cw;
>+        }
>+    }
>+}
>diff --git a/gcc/vr-values.c b/gcc/vr-values.c
>index da0b249278b..16f6c629f29 100644
>--- a/gcc/vr-values.c
>+++ b/gcc/vr-values.c
>@@ -1827,6 +1827,8 @@ bounds_of_var_in_loop (tree *min, tree *max,
>range_query *query,
> 
>   init = initial_condition_in_loop_num (chrec, loop->num);
>   step = evolution_part_in_loop_num (chrec, loop->num);
>+  if (step == NULL_TREE)
>+    return false;
> 
>   /* If INIT is an SSA with a singleton range, set INIT to said
>      singleton, otherwise leave INIT alone.  */

Re: [RFA,PATCH] Bail in bounds_of_var_in_loop if no step found.

[Aldy Hernandez]

On 10/13/20 6:02 PM, Richard Biener wrote:
> On October 13, 2020 5:17:48 PM GMT+02:00, Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>> [Neither Andrew nor I are familiar with the SCEV code.  We treat it as
>> a
>> black box :).  So we could use a SCEV expert here.]
>>
>> In bounds_of_var_in_loop, evolution_part_in_loop_num is returning NULL:
>>
>>    step = evolution_part_in_loop_num (chrec, loop->num);
> 
> It means that Var doesn't vary in the loop.
> That is, chrec isn't a polynomial chrec.

That's what I thought, but it is:

(gdb) p chrec
$6 = <polynomial_chrec 0x7ffff0e2a820>
(gdb) dd chrec
{0, +, 1}_2

evolution_part_in_loop_num() is returning NULL deep in 
chrec_component_in_loop_num():

      default:
=>    if (right)
         return NULL_TREE;
       else
         return chrec;

Do you have any suggestions?

Thanks.
Aldy

Re: [RFA,PATCH] Bail in bounds_of_var_in_loop if no step found.

[Richard Biener]

On Tue, Oct 13, 2020 at 6:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 10/13/20 6:02 PM, Richard Biener wrote:
> > On October 13, 2020 5:17:48 PM GMT+02:00, Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> >> [Neither Andrew nor I are familiar with the SCEV code.  We treat it as
> >> a
> >> black box :).  So we could use a SCEV expert here.]
> >>
> >> In bounds_of_var_in_loop, evolution_part_in_loop_num is returning NULL:
> >>
> >>    step = evolution_part_in_loop_num (chrec, loop->num);

(*)

> >
> > It means that Var doesn't vary in the loop.
> > That is, chrec isn't a polynomial chrec.
>
> That's what I thought, but it is:
>
> (gdb) p chrec
> $6 = <polynomial_chrec 0x7ffff0e2a820>
> (gdb) dd chrec
> {0, +, 1}_2
>
> evolution_part_in_loop_num() is returning NULL deep in
> chrec_component_in_loop_num():
>
>       default:
> =>    if (right)
>          return NULL_TREE;
>        else
>          return chrec;
>
> Do you have any suggestions?

I can only guess (w/o a testcase) that loop->num at (*) is not 2 and thus that
chrec does not evolve in the loop we're asking.  But this doesn't make much
sense with the constraints we are calling this function (a loop header PHI
with loop == the loop and stmt a loop header PHI and var the PHIs lhs).

OK, so looking at the testcase you're doing

492           class loop *l = loop_containing_stmt (phi);
493           if (l)
494             {
495               range_of_ssa_name_with_loop_info (loop_range,
phi_def, l, phi);

but 'l' isn't a loop, it's the loop tree root.  Change to

  if (l && loop_outer (l))

Richard.

>
> Thanks.
> Aldy
>

Re: [RFA,PATCH] Bail in bounds_of_var_in_loop if no step found.

[Aldy Hernandez]

On 10/14/20 9:43 AM, Richard Biener wrote:
> On Tue, Oct 13, 2020 at 6:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 10/13/20 6:02 PM, Richard Biener wrote:
>>> On October 13, 2020 5:17:48 PM GMT+02:00, Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>>>> [Neither Andrew nor I are familiar with the SCEV code.  We treat it as
>>>> a
>>>> black box :).  So we could use a SCEV expert here.]
>>>>
>>>> In bounds_of_var_in_loop, evolution_part_in_loop_num is returning NULL:
>>>>
>>>>     step = evolution_part_in_loop_num (chrec, loop->num);
> 
> (*)
> 
>>>
>>> It means that Var doesn't vary in the loop.
>>> That is, chrec isn't a polynomial chrec.
>>
>> That's what I thought, but it is:
>>
>> (gdb) p chrec
>> $6 = <polynomial_chrec 0x7ffff0e2a820>
>> (gdb) dd chrec
>> {0, +, 1}_2
>>
>> evolution_part_in_loop_num() is returning NULL deep in
>> chrec_component_in_loop_num():
>>
>>        default:
>> =>    if (right)
>>           return NULL_TREE;
>>         else
>>           return chrec;
>>
>> Do you have any suggestions?
> 
> I can only guess (w/o a testcase) that loop->num at (*) is not 2 and thus that
> chrec does not evolve in the loop we're asking.  But this doesn't make much
> sense with the constraints we are calling this function (a loop header PHI
> with loop == the loop and stmt a loop header PHI and var the PHIs lhs).
> 
> OK, so looking at the testcase you're doing
> 
> 492           class loop *l = loop_containing_stmt (phi);
> 493           if (l)
> 494             {
> 495               range_of_ssa_name_with_loop_info (loop_range,
> phi_def, l, phi);
> 
> but 'l' isn't a loop, it's the loop tree root.  Change to
> 
>    if (l && loop_outer (l))

Woah.  I did not expect that.

A quick peek shows that all users of bounds_of_var_in_loop (through 
adjust_range_with_scev) predicate the call with:

	&& l->header == gimple_bb (phi))

If this check is similar to the loop_outer(l) you suggest, could we 
perhaps push this check (and/or the loop_outer one) into 
bounds_of_var_in_loop itself and remove it from all the callers?  It 
seems cleaner to have this check in one place, than in three different 
places.  That is, unless the l->header check is altogether a different 
thing than loop_outer(l).

Thanks so much for looking at this.
Aldy

Re: [RFA,PATCH] Bail in bounds_of_var_in_loop if no step found.

[Richard Biener]

On Wed, Oct 14, 2020 at 4:19 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 10/14/20 9:43 AM, Richard Biener wrote:
> > On Tue, Oct 13, 2020 at 6:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >>
> >>
> >> On 10/13/20 6:02 PM, Richard Biener wrote:
> >>> On October 13, 2020 5:17:48 PM GMT+02:00, Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> >>>> [Neither Andrew nor I are familiar with the SCEV code.  We treat it as
> >>>> a
> >>>> black box :).  So we could use a SCEV expert here.]
> >>>>
> >>>> In bounds_of_var_in_loop, evolution_part_in_loop_num is returning NULL:
> >>>>
> >>>>     step = evolution_part_in_loop_num (chrec, loop->num);
> >
> > (*)
> >
> >>>
> >>> It means that Var doesn't vary in the loop.
> >>> That is, chrec isn't a polynomial chrec.
> >>
> >> That's what I thought, but it is:
> >>
> >> (gdb) p chrec
> >> $6 = <polynomial_chrec 0x7ffff0e2a820>
> >> (gdb) dd chrec
> >> {0, +, 1}_2
> >>
> >> evolution_part_in_loop_num() is returning NULL deep in
> >> chrec_component_in_loop_num():
> >>
> >>        default:
> >> =>    if (right)
> >>           return NULL_TREE;
> >>         else
> >>           return chrec;
> >>
> >> Do you have any suggestions?
> >
> > I can only guess (w/o a testcase) that loop->num at (*) is not 2 and thus that
> > chrec does not evolve in the loop we're asking.  But this doesn't make much
> > sense with the constraints we are calling this function (a loop header PHI
> > with loop == the loop and stmt a loop header PHI and var the PHIs lhs).
> >
> > OK, so looking at the testcase you're doing
> >
> > 492           class loop *l = loop_containing_stmt (phi);
> > 493           if (l)
> > 494             {
> > 495               range_of_ssa_name_with_loop_info (loop_range,
> > phi_def, l, phi);
> >
> > but 'l' isn't a loop, it's the loop tree root.  Change to
> >
> >    if (l && loop_outer (l))
>
> Woah.  I did not expect that.
>
> A quick peek shows that all users of bounds_of_var_in_loop (through
> adjust_range_with_scev) predicate the call with:
>
>         && l->header == gimple_bb (phi))
>
> If this check is similar to the loop_outer(l) you suggest, could we
> perhaps push this check (and/or the loop_outer one) into
> bounds_of_var_in_loop itself and remove it from all the callers?  It
> seems cleaner to have this check in one place, than in three different
> places.  That is, unless the l->header check is altogether a different
> thing than loop_outer(l).

The code also works for stmts other than PHIs (or stmts in other blocks
than the loop header), so IMHO is not appropriate for bounds_of_var_in_loop.

Richard.

>
> Thanks so much for looking at this.
> Aldy
>

Re: [RFA,PATCH] Bail in bounds_of_var_in_loop if no step found.

[Aldy Hernandez]

On 10/14/20 4:31 PM, Richard Biener wrote:
> On Wed, Oct 14, 2020 at 4:19 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 10/14/20 9:43 AM, Richard Biener wrote:
>>> On Tue, Oct 13, 2020 at 6:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>
>>>>
>>>>
>>>> On 10/13/20 6:02 PM, Richard Biener wrote:
>>>>> On October 13, 2020 5:17:48 PM GMT+02:00, Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>>>>>> [Neither Andrew nor I are familiar with the SCEV code.  We treat it as
>>>>>> a
>>>>>> black box :).  So we could use a SCEV expert here.]
>>>>>>
>>>>>> In bounds_of_var_in_loop, evolution_part_in_loop_num is returning NULL:
>>>>>>
>>>>>>      step = evolution_part_in_loop_num (chrec, loop->num);
>>>
>>> (*)
>>>
>>>>>
>>>>> It means that Var doesn't vary in the loop.
>>>>> That is, chrec isn't a polynomial chrec.
>>>>
>>>> That's what I thought, but it is:
>>>>
>>>> (gdb) p chrec
>>>> $6 = <polynomial_chrec 0x7ffff0e2a820>
>>>> (gdb) dd chrec
>>>> {0, +, 1}_2
>>>>
>>>> evolution_part_in_loop_num() is returning NULL deep in
>>>> chrec_component_in_loop_num():
>>>>
>>>>         default:
>>>> =>    if (right)
>>>>            return NULL_TREE;
>>>>          else
>>>>            return chrec;
>>>>
>>>> Do you have any suggestions?
>>>
>>> I can only guess (w/o a testcase) that loop->num at (*) is not 2 and thus that
>>> chrec does not evolve in the loop we're asking.  But this doesn't make much
>>> sense with the constraints we are calling this function (a loop header PHI
>>> with loop == the loop and stmt a loop header PHI and var the PHIs lhs).
>>>
>>> OK, so looking at the testcase you're doing
>>>
>>> 492           class loop *l = loop_containing_stmt (phi);
>>> 493           if (l)
>>> 494             {
>>> 495               range_of_ssa_name_with_loop_info (loop_range,
>>> phi_def, l, phi);
>>>
>>> but 'l' isn't a loop, it's the loop tree root.  Change to
>>>
>>>     if (l && loop_outer (l))
>>
>> Woah.  I did not expect that.
>>
>> A quick peek shows that all users of bounds_of_var_in_loop (through
>> adjust_range_with_scev) predicate the call with:
>>
>>          && l->header == gimple_bb (phi))
>>
>> If this check is similar to the loop_outer(l) you suggest, could we
>> perhaps push this check (and/or the loop_outer one) into
>> bounds_of_var_in_loop itself and remove it from all the callers?  It
>> seems cleaner to have this check in one place, than in three different
>> places.  That is, unless the l->header check is altogether a different
>> thing than loop_outer(l).
> 
> The code also works for stmts other than PHIs (or stmts in other blocks
> than the loop header), so IMHO is not appropriate for bounds_of_var_in_loop.

Ahhh.   Makes perfect sense.

The patch below passes tests.  I've pushed it.

Thanks.
Aldy

gcc/ChangeLog:

	PR tree-optimization/97396
	* gimple-range.cc (gimple_ranger::range_of_phi): Do not call
	range_of_ssa_name_with_loop_info with the loop tree root.

gcc/testsuite/ChangeLog:

	* gcc.dg/pr97396.c: New test.
---
  gcc/gimple-range.cc            |  2 +-
  gcc/testsuite/gcc.dg/pr97396.c | 23 +++++++++++++++++++++++
  2 files changed, 24 insertions(+), 1 deletion(-)
  create mode 100644 gcc/testsuite/gcc.dg/pr97396.c

diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 2ca86ed0e4c..999d631c5ee 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -490,7 +490,7 @@ gimple_ranger::range_of_phi (irange &r, gphi *phi)
      {
        value_range loop_range;
        class loop *l = loop_containing_stmt (phi);
-      if (l)
+      if (l && loop_outer (l))
          {
  	  range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi);
  	  if (!loop_range.varying_p ())
diff --git a/gcc/testsuite/gcc.dg/pr97396.c b/gcc/testsuite/gcc.dg/pr97396.c
new file mode 100644
index 00000000000..d992c11f238
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr97396.c
@@ -0,0 +1,23 @@
+// { dg-do compile }
+// { dg-options "-O1 -ftree-vrp" }
+// { dg-additional-options "-m32" { target { i?86-*-* x86_64-*-* } } }
+
+unsigned int
+po (char *os, unsigned int al)
+{
+  for (;;)
+    {
+      int qx = 0;
+
+      while (al < 1)
+        {
+          char *cw;
+
+          cw = os + qx;
+          if (cw)
+            return al + qx;
+
+          qx += sizeof *cw;
+        }
+    }
+}
-- 
2.26.2