[Bug tree-optimization/107986] New: [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[Bug tree-optimization/107986] New: [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[rguenth at gcc dot gnu.org]

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

            Bug ID: 107986
           Summary: [12/13 Regression] Bogus -Warray-bounds diagnostic
                    with std::sort
           Product: gcc
           Version: 12.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
  Target Milestone: ---

PR104165 comment 2 talks about a test case reduced in
https://bugzilla.redhat.com/show_bug.cgi?id=2051783:

#include <algorithm>

bool cond;
int foo;

int func (void)
{
  int a[3], qa = 0;
  for(int i = 0; i < 3; i++)
    if (cond)
      a[qa++] = foo;

  std::sort (a, a + qa);
  return 0;
}

which still warns with both GCC 12 and 13 at -O2 -Wall like

In file included from
/home/rguenther/install/gcc-13/usr/local/include/c++/13.0.0/algorithm:61,
                 from t.C:1:
In function 'void std::__final_insertion_sort(_RandomAccessIterator,
_RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare =
__gnu_cxx::__ops::_Iter_less_iter]',
    inlined from 'void std::__final_insertion_sort(_RandomAccessIterator,
_RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare =
__gnu_cxx::__ops::_Iter_less_iter]' at
/home/rguenther/install/gcc-13/usr/local/include/c++/13.0.0/bits/stl_algo.h:1854:5,
    inlined from 'void std::__sort(_RandomAccessIterator,
_RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare =
__gnu_cxx::__ops::_Iter_less_iter]' at
/home/rguenther/install/gcc-13/usr/local/include/c++/13.0.0/bits/stl_algo.h:1950:31,
    inlined from 'void std::__sort(_RandomAccessIterator,
_RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare =
__gnu_cxx::__ops::_Iter_less_iter]' at
/home/rguenther/install/gcc-13/usr/local/include/c++/13.0.0/bits/stl_algo.h:1942:5,
    inlined from 'void std::sort(_RAIter, _RAIter) [with _RAIter = int*]' at
/home/rguenther/install/gcc-13/usr/local/include/c++/13.0.0/bits/stl_algo.h:4860:1,
    inlined from 'int func()' at t.C:13:13:
/home/rguenther/install/gcc-13/usr/local/include/c++/13.0.0/bits/stl_algo.h:1859:32:
warning: array subscript 16 is outside array bounds of 'int [3]'
[-Warray-bounds=]
 1859 |           std::__insertion_sort(__first, __first + int(_S_threshold),
__comp);
      |          
~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
t.C: In function 'int func()':
t.C:8:7: note: at offset 64 into object 'a' of size 12
    8 |   int a[3], qa = 0;
      |       ^

I'll also note the lack of a non-included location in t.C.

[Bug tree-optimization/107986] [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-12-06
      Known to fail|                            |12.2.0, 13.0
     Ever confirmed|0                           |1
           Keywords|                            |diagnostic
             Status|UNCONFIRMED                 |NEW
   Target Milestone|---                         |12.3
             Blocks|                            |56456
      Known to work|                            |11.3.0


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56456
[Bug 56456] [meta-bug] bogus/missing -Warray-bounds

[Bug tree-optimization/107986] [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |85316
                 CC|                            |aldyh at gcc dot gnu.org
           Keywords|                            |missed-optimization

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
One of the reasons we diagnose this is that we fail to compute a range
for 'qa_7'.  Before the VRP pass that diagnoses the -Warray-bounds violation we
have

  <bb 6> [local count: 1073741824]:
  # qa_7 = PHI <0(2), qa_6(5)>
  # RANGE [irange] int [0, 3] NONZERO 0x3
  # i_8 = PHI <0(2), i_16(5)>
  if (i_8 != 3)
    goto <bb 3>; [75.00%]
  else
    goto <bb 7>; [25.00%]

  <bb 7> [local count: 268435456]:
  # RANGE [irange] long unsigned int [0, 2147483647][18446744071562067968,
+INF]
  _3 = (long unsigned int) qa_7;
  # RANGE [irange] long unsigned int [0, 8589934588][18446744065119617024,
18446744073709551612] NONZERO 0xfffffffffffffffc
  _4 = _3 * 4;
  # PT = { D.18799 } (escaped)
  # ALIGN = 4, MISALIGN = 0
  _5 = &a + _4;
  if (&a != _5)
    goto <bb 8>; [53.47%]
  else
    goto <bb 17>; [46.53%]

  <bb 8> [local count: 143532440]:
  _11 = (signed long) _4;
  # RANGE [irange] long int [-2305843009213693952, 2305843009213693951]
  _20 = _11 /[ex] 4;
  # RANGE [irange] long unsigned int [0,
2305843009213693951][16140901064495857664, +INF]
  __n.3_21 = (long unsigned int) _20;
  # RANGE [irange] int [0, 63] NONZERO 0x3f
  _22 = __builtin_clzl (__n.3_21);
  # RANGE [irange] int [0, 63] NONZERO 0x3f
  _23 = 63 - _22;
  # RANGE [irange] long int [0, 63] NONZERO 0x3f
  _24 = (long int) _23;
  # RANGE [irange] long int [0, 126] NONZERO 0x7e
  _25 = _24 * 2;
  # USE = nonlocal escaped null { D.18799 } (escaped)
  # CLB = nonlocal escaped null { D.18799 } (escaped)
  std::__introsort_loop.isra (&a, _5, _25);
  if (_11 > 64)
    goto <bb 9>; [50.00%]
  else
    goto <bb 15>; [50.00%]

and we fail to eliminate this last conditional.  We also fail to
eliminate the (long)(((unsigned long)qa_37) * 4) /[ex] 4 round-trip
(because of possible overflow).

So even proving qa_7 is [0, +INF] would help a bit (not the diagnostic),
realizing qa_7 is [0, 3] like i_8 would be even better.  A testcase
for this could look like

void bar ();
void foo (int *a)
{
  int qa = 0;
  for (int i = 0; i < 3; i++)
    if (a[i])
      a[qa++] = 0;
  if (qa > 3)
    bar ();
}

where we should be able to eliminate the call to bar ().


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85316
[Bug 85316] [meta-bug] VRP range propagation missed cases

[Bug tree-optimization/107986] [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> 
> void bar ();
> void foo (int *a)
> {
>   int qa = 0;
>   for (int i = 0; i < 3; i++)
>     if (a[i])
>       a[qa++] = 0;
>   if (qa > 3)
>     bar ();
> }
> 
> where we should be able to eliminate the call to bar ().

What is interesting is we can optimize away the call to bar in this slightly
modified case during vrp2:
void bar ();
bool cond;
void foo (int *a)
{
  int qa = 0;
  for (int i = 0; i < 3; i++)
    if (cond)
      a[qa++] = 0;
  if (qa > 3)
    bar ();
}

But I don't see why having the load inside the loop would make a difference
....

[Bug tree-optimization/107986] [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Note the old VRP was able to at least tell that qa was [0, +INF] by means of
iterating and saturating to +INF after too many iterations.  SCEV isn't of
help here.  Since we've lost the last lattice-based (iterating) VRP pass now
what's the plan for cases like this?

[Bug tree-optimization/107986] [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #2)
> (In reply to Richard Biener from comment #1)
> > 
> > void bar ();
> > void foo (int *a)
> > {
> >   int qa = 0;
> >   for (int i = 0; i < 3; i++)
> >     if (a[i])
> >       a[qa++] = 0;
> >   if (qa > 3)
> >     bar ();
> > }
> > 
> > where we should be able to eliminate the call to bar ().
> 
> What is interesting is we can optimize away the call to bar in this slightly
> modified case during vrp2:
> void bar ();
> bool cond;
> void foo (int *a)
> {
>   int qa = 0;
>   for (int i = 0; i < 3; i++)
>     if (cond)
>       a[qa++] = 0;
>   if (qa > 3)
>     bar ();
> }
> 
> But I don't see why having the load inside the loop would make a difference
> ....

It's because we can jump-thread the invariant condition.  The most
canonical testcase would be sth like

int foo (int *a)
{
  int qa = 0;
  for (int i = 0; i < 3; i++)
    if (a[i++])
      qa++;
  if (qa < 0 || qa > 3)
    bar ();
  return qa;
}

[Bug tree-optimization/107986] [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
At least the only increment operation(s) on TYPE_OVERFLOW_UNDEFINED typed var
result in a range from low bound of the initial value to +INF shouldn't be that
hard I'd hope (Andrew, any suggestions where to do that)?  Ditto only decrement
operation(s) on such typed vars to [-INF, high bound of initial value].
But I agree the result should be done somewhere too.

[Bug tree-optimization/107986] [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[rguenther at suse dot de]

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

--- Comment #6 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 6 Dec 2022, jakub at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107986
> 
> Jakub Jelinek <jakub at gcc dot gnu.org> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |jakub at gcc dot gnu.org
> 
> --- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> At least the only increment operation(s) on TYPE_OVERFLOW_UNDEFINED typed var
> result in a range from low bound of the initial value to +INF shouldn't be that
> hard I'd hope (Andrew, any suggestions where to do that)?  Ditto only decrement
> operation(s) on such typed vars to [-INF, high bound of initial value].
> But I agree the result should be done somewhere too.

I would guess that max_stmt_executions is still useful on these kind
of loops but of course sth still has to do the (non-iterating then?)
work to merge the ranges from the PHIs and somehow decide ignoring the
backedge is OK.

[Bug tree-optimization/107986] [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/107986] [12/13 Regression] Bogus -Warray-bounds diagnostic with std::sort

[amacleod at redhat dot com]

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

--- Comment #7 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Richard Biener from comment #3)
> Note the old VRP was able to at least tell that qa was [0, +INF] by means of
> iterating and saturating to +INF after too many iterations.  SCEV isn't of
> help here.  Since we've lost the last lattice-based (iterating) VRP pass now
> what's the plan for cases like this?



When we first process a statement we set the LHS to varying first. Then we
resolve all the inputs, and then do the final calculation of the LHS and save
that. 

This is done to prevent resolving inputs along back edges from entering a
cycle. If the back edge ever returns to this def, it will pick up the saved
varying value and stop looking..

This is conservatively correct, but it does mean in the case of PHI nodes, we
are not optimistic about the outcome if there is a cyclic dependency. 

I intend to experiment with pre-walking any back edges to look for bounds if
there is a cycle.. ie, the range increases or decreases providing an
upper/lower limit.  I just haven't gotten to it yet.    SO no iterations as
such, but a quick pattern check which may provide a bound.

in another PR (107972) I mentioned al alternative VRP which discovers things
from the bottom to the top.. Theres some possibility that pass might expose
this sort of thing too when I get to it.

[Bug tree-optimization/107986] [12/13/14 Regression] Bogus -Warray-bounds diagnostic with std::sort

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.3                        |12.4

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 12.3 is being released, retargeting bugs to GCC 12.4.

[Bug tree-optimization/107986] [12/13/14 Regression] Bogus -Warray-bounds diagnostic with std::sort

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:1cd5bc387c453126fdb4c9400096180484ecddee

commit r14-1179-g1cd5bc387c453126fdb4c9400096180484ecddee
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Wed May 24 09:52:26 2023 -0400

    Gimple range PHI analyzer and testcases

    Provide a PHI analyzer framework to provive better initial values for
    PHI nodes which formk groups with initial values and single statements
    which modify the PHI values in some predicatable way.

            PR tree-optimization/107822
            PR tree-optimization/107986
            gcc/
            * Makefile.in (OBJS): Add gimple-range-phi.o.
            * gimple-range-cache.h (ranger_cache::m_estimate): New
            phi_analyzer pointer member.
            * gimple-range-fold.cc (fold_using_range::range_of_phi): Use
            phi_analyzer if no loop info is available.
            * gimple-range-phi.cc: New file.
            * gimple-range-phi.h: New file.
            * tree-vrp.cc (execute_ranger_vrp): Utililze a phi_analyzer.

            gcc/testsuite/
            * gcc.dg/pr107822.c: New.
            * gcc.dg/pr107986-1.c: New.

[Bug tree-optimization/107986] [12/13/14 Regression] Bogus -Warray-bounds diagnostic with std::sort

[asharafutdinov at adalisk dot com]

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

Artur Sharafutdinov <asharafutdinov at adalisk dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |asharafutdinov at adalisk dot com

--- Comment #10 from Artur Sharafutdinov <asharafutdinov at adalisk dot com> ---
Similar bug affects all GCC versions starting from 10.1.

#include <algorithm>

struct A
{
    int n = 0;
};

bool operator <(const A &a, const A &b)
{
    return a.n < b.n;
}

int main()
{
    // both values may vary in range [3; 8]
    constexpr int N = 8;
    constexpr int M = 3;
    A a[N];
    for (auto i = 1; i <= M; ++i)
        std::sort(a, a + i);
}

Being built with -std=c++20 -Wall -Werror -O3, it gives the error:

<source>: In function 'int main()':
<source>:10:20: error: array subscript [8, 1152921504606846975] is outside
array bounds of 'A [8]' [-Werror=array-bounds]
   10 |     return a.n < b.n;
      |                  ~~^
<source>:17:7: note: while referencing 'a'
   17 |     A a[N];
      |       ^

[Bug tree-optimization/107986] [12/13/14 Regression] Bogus -Warray-bounds diagnostic with std::sort

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
We now diagnose

std::__insertion_sort.isra (&a, &MEM <int[3]> [(void *)&a + 64B]);

the reason is still the same, failure to compute a range for 'qa' which
we fail to SCEV analyze.  There's a duplicate bug about this.