[Bug tree-optimization/96146] New: VRP turns a terminating loop into an infinite loop

[Bug tree-optimization/96146] New: VRP turns a terminating loop into an infinite loop

[rsandifo at gcc dot gnu.org]

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

            Bug ID: 96146
           Summary: VRP turns a terminating loop into an infinite loop
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rsandifo at gcc dot gnu.org
  Target Milestone: ---
            Target: aarch64*-*-*

Compiling the following testcase with -O3 -march=armv8.2-a+sve
turns the loop into an infinite loop:

-------------------------------------------------------
#include <arm_sve.h>

int
f (volatile int *x)
{
  for (int i = 0; i < svcntd (); ++i)
    *x = i;
}
-------------------------------------------------------

Before vrp2 we have:

-------------------------------------------------------
  # i_11 = PHI <0(5), i_7(6)>
  *x_5(D) ={v} i_11;
  i_7 = i_11 + 1;
  if (i_7 != POLY_INT_CST [2, 2])
    goto <bb 6>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 6> [local count: 850510901]:
  goto <bb 3>; [100.00%]
-------------------------------------------------------

but vrp changes the phi to:

  # i_11 = PHI <0(2), 1(3)>

The ASSERT_EXPR form is:

-------------------------------------------------------
  <bb 3> [local count: 955630225]:
  # i_11 = PHI <0(5), i_1(6)>
  *x_5(D) ={v} i_11;
  i_7 = i_11 + 1;
  if (i_7 != POLY_INT_CST [2, 2])
    goto <bb 6>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 6> [local count: 850510901]:
  i_1 = ASSERT_EXPR <i_7, i_7 != POLY_INT_CST [2, 2]>;
  goto <bb 3>; [100.00%]
-------------------------------------------------------

During the first round we have:

---------------------------------------------------------------------
Found new range for i_11: int [0, 0]
…
Found new range for i_7: int [1, 1]
…
extract_range_from_stmt visiting:
if (i_7 != POLY_INT_CST [2, 2])

Visiting conditional with predicate: if (i_7 != POLY_INT_CST [2, 2])

With known ranges
        i_7: int [1, 1]

Predicate evaluates to: 1
…
extract_range_from_stmt visiting:
i_1 = ASSERT_EXPR <i_7, i_7 != POLY_INT_CST [2, 2]>;
Intersecting
  int [-INF, 1]  EQUIVALENCES: { i_7 } (1 elements)
and
  int [1, 1]
to
  int [1, 1]  EQUIVALENCES: { i_7 } (1 elements)
Intersecting
  int [1, 1]  EQUIVALENCES: { i_7 } (1 elements)
and
  int [1, +INF]
to
  int [1, 1]  EQUIVALENCES: { i_7 } (1 elements)
Found new range for i_1: int [1, 1]  EQUIVALENCES: { } (0 elements)
---------------------------------------------------------------------

and the second time round:

---------------------------------------------------------------------
Found new range for i_11: int [0, 1]
…
Found new range for i_7: int [1, 2]
…
extract_range_from_stmt visiting:
if (i_7 != POLY_INT_CST [2, 2])

Visiting conditional with predicate: if (i_7 != POLY_INT_CST [2, 2])

With known ranges
        i_7: int [1, 2]

Predicate evaluates to: DON'T KNOW
…

------extract_range_from_stmt visiting:
i_1 = ASSERT_EXPR <i_7, i_7 != POLY_INT_CST [2, 2]>;
Intersecting
  int [-INF, 1]  EQUIVALENCES: { i_7 } (1 elements)
and
  int [1, 2]
to
  int [1, 1]  EQUIVALENCES: { i_7 } (1 elements)
Intersecting
  int [1, 1]  EQUIVALENCES: { i_7 } (1 elements)
and
  int [1, +INF]
to
  int [1, 1]  EQUIVALENCES: { i_7 } (1 elements)
---------------------------------------------------------------

which re-establishes the [1, 1] range, and so the simulation
stops there.

The bug doesn't occur for s/int/unsigned int/, or for svcntw()
instead of svcntd().

[Bug tree-optimization/96146] VRP turns a terminating loop into an infinite loop

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

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

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---

i_1 = ASSERT_EXPR <i_7, i_7 != POLY_INT_CST [2, 2]>;
Intersecting
  int [-INF, 1]  EQUIVALENCES: { i_7 } (1 elements)

so somehow we derive from i_7 != POLY_INT_CST [2, 2] that i_7 must
be [-INF, 1] - that looks wrong?

This goes via extract_range_for_var_from_comparison_expr and likely
compare_values goes off in

      if (limit_vr
          && limit_vr->kind () == VR_RANGE
          && compare_values (limit_vr->min (), limit_vr->max ()) == 0)
        {
          min = limit_vr->min ();
          max = limit_vr->max ();
        }

where min/max are then POLY_INT_CST [2, 2] and the anti-range we build
from that is canonicalized in odd ways.

I think VRP all over the place assumes integer typed constants are
INTEGER_CSTs so maybe sth else is off with POLY_INT_CSTs ...

CCing VRP people.

[Bug tree-optimization/96146] VRP turns a terminating loop into an infinite loop

[rsandifo at gcc dot gnu.org]

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

--- Comment #2 from rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> ---
FWIW, it doesn't look like this is specific to POLY_INT_CST.
A gimple reproducer shows a similar thing:

void __GIMPLE (ssa, startwith("vrp2"))
foo (volatile int *x)
{
  int i;

__BB(2):
  goto __BB3;

__BB(3):
  i_1 = __PHI (__BB2: 0, __BB4: i_2);
  *x = i_1;
  i_2 = i_1 + 1;
  if (i_2 != 2)
    goto __BB4;
  else
    goto __BB5;

__BB(4):
  goto __BB3;

__BB(5):
  return;
}

It works with a bound of 3 rather than 2.

[Bug tree-optimization/96146] VRP turns a terminating loop into an infinite loop

[rsandifo at gcc dot gnu.org]

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

--- Comment #3 from rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> ---
Sorry, scratch that last message.  The optimisation is of course
correct in that case. ;-)

[Bug tree-optimization/96146] VRP turns a terminating loop into an infinite loop

[rsandifo at gcc dot gnu.org]

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

rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2020-07-10
           Assignee|unassigned at gcc dot gnu.org      |rsandifo at gcc dot gnu.org

--- Comment #4 from rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> ---
Testing a patch.

[Bug tree-optimization/96146] VRP turns a terminating loop into an infinite loop

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Sandiford <rsandifo@gcc.gnu.org>:

https://gcc.gnu.org/g:505032d97d0593d5e9a6f51b107650e27fcf6b23

commit r11-2034-g505032d97d0593d5e9a6f51b107650e27fcf6b23
Author: Richard Sandiford <richard.sandiford@arm.com>
Date:   Sat Jul 11 13:25:26 2020 +0100

    value-range: Fix handling of POLY_INT_CST anti-ranges [PR96146]

    The range infrastructure has code to decompose POLY_INT_CST ranges
    to worst-case integer bounds.  However, it had the fundamental flaw
    (obvious in hindsight) that it applied to anti-ranges too, meaning
    that a range 2+2X would end up with a range of ~[2, +INF], i.e.
    [-INF, 1].  This patch decays to varying in that case instead.

    I'm still a bit uneasy about this.  ISTM that in terms of
    generality:

      SSA_NAME => POLY_INT_CST => INTEGER_CST
               => ADDR_EXPR

    I.e. an SSA_NAME could store a POLY_INT_CST and a POLY_INT_CST
    could store an INTEGER_CST (before canonicalisation).  POLY_INT_CST
    is also âas constant asâ ADDR_EXPR (well, OK, only some ADDR_EXPRs
    are run-time rather than link-time constants, whereas all POLY_INT_CSTs
    are, but still).  So it seems like we should at least be able to treat
    POLY_INT_CST as symbolic.  On the other hand, I don't have any examples
    in which that would be useful.

    gcc/
            PR tree-optimization/96146
            * value-range.cc (value_range::set): Only decompose POLY_INT_CST
            bounds to integers for VR_RANGE.  Decay to VR_VARYING for
anti-ranges
            involving POLY_INT_CSTs.

    gcc/testsuite/
            PR tree-optimization/96146
            * gcc.target/aarch64/sve/acle/general/pr96146.c: New test.

[Bug tree-optimization/96146] VRP turns a terminating loop into an infinite loop

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Richard Sandiford
<rsandifo@gcc.gnu.org>:

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

commit r10-8494-gb9475357b5b180c63b3389742452a48026f073a6
Author: Richard Sandiford <richard.sandiford@arm.com>
Date:   Tue Jul 14 19:24:56 2020 +0100

    value-range: Fix handling of POLY_INT_CST anti-ranges [PR96146]

    The range infrastructure has code to decompose POLY_INT_CST ranges
    to worst-case integer bounds.  However, it had the fundamental flaw
    (obvious in hindsight) that it applied to anti-ranges too, meaning
    that a range 2+2X would end up with a range of ~[2, +INF], i.e.
    [-INF, 1].  This patch decays to varying in that case instead.

    I'm still a bit uneasy about this.  ISTM that in terms of
    generality:

      SSA_NAME => POLY_INT_CST => INTEGER_CST
               => ADDR_EXPR

    I.e. an SSA_NAME could store a POLY_INT_CST and a POLY_INT_CST
    could store an INTEGER_CST (before canonicalisation).  POLY_INT_CST
    is also âas constant asâ ADDR_EXPR (well, OK, only some ADDR_EXPRs
    are run-time rather than link-time constants, whereas all POLY_INT_CSTs
    are, but still).  So it seems like we should at least be able to treat
    POLY_INT_CST as symbolic.  On the other hand, I don't have any examples
    in which that would be useful.

    gcc/
            PR tree-optimization/96146
            * value-range.cc (value_range::set): Only decompose POLY_INT_CST
            bounds to integers for VR_RANGE.  Decay to VR_VARYING for
anti-ranges
            involving POLY_INT_CSTs.

    gcc/testsuite/
            PR tree-optimization/96146
            * gcc.target/aarch64/sve/acle/general/pr96146.c: New test.

[Bug tree-optimization/96146] VRP turns a terminating loop into an infinite loop

[rsandifo at gcc dot gnu.org]

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

rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #7 from rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> ---
Fixed on trunk and GCC 10 branch.