[Bug c++/107699] New: False positive -Warray-bounds, non-existent offset reported by GCC

[Bug c++/107699] New: False positive -Warray-bounds, non-existent offset reported by GCC

[carlosgalvezp at gmail dot com]

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

            Bug ID: 107699
           Summary: False positive -Warray-bounds, non-existent offset
                    reported by GCC
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: carlosgalvezp at gmail dot com
  Target Milestone: ---

Hi,

The following code:

#include <array>
#include <algorithm>

std::size_t getCount();

int foo()
{
    std::array<int, 3> data{3, 2, 1};
    std::sort(data.begin(), data.begin() + getCount());
    return data.front();
}

Built with -Wall -O3 triggers:

In file included from
/opt/compiler-explorer/gcc-trunk-20221115/include/c++/13.0.0/algorithm:61,
                 from <source>:2:
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
/opt/compiler-explorer/gcc-trunk-20221115/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
/opt/compiler-explorer/gcc-trunk-20221115/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
/opt/compiler-explorer/gcc-trunk-20221115/include/c++/13.0.0/bits/stl_algo.h:1942:5,
    inlined from 'void std::sort(_RAIter, _RAIter) [with _RAIter = int*]' at
/opt/compiler-explorer/gcc-trunk-20221115/include/c++/13.0.0/bits/stl_algo.h:4860:18,
    inlined from 'int foo()' at <source>:9:14:
/opt/compiler-explorer/gcc-trunk-20221115/include/c++/13.0.0/bits/stl_algo.h:1859:32:
warning: array subscript 16 is outside array bounds of 'std::array<int, 3> [1]'
[-Warray-bounds]
 1859 |           std::__insertion_sort(__first, __first + int(_S_threshold),
__comp);
      |          
~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>: In function 'int foo()':
<source>:8:24: note: at offset 64 into object 'data' of size 12
    8 |     std::array<int, 3> data{3, 2, 1};
      |                        ^~~~
Compiler returned: 0

Repro: https://godbolt.org/z/Ma8KK1MKE

There is nowhere in the code any "offset 64". The compiler cannot possibly know
if there is OOB or not, since that depends on the function "getCount" which is
implemented in a separate translation unit.

Therefore the warning violates what the documentation says:
"It warns about subscripts to arrays that are always out of bounds"

This is not true in this case. It's not "always" out of bounds.

[Bug tree-optimization/107699] False positive -Warray-bounds, non-existent offset reported by GCC

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2022-11-16
                 CC|                            |msebor at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org

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

if (&MEM <int[3]> [(void *)&data + 64B] != __i_32)

and the code is confused about the <int[3]> type and the address-taken
special allowing taking the address of one after the array.  All the
second-guessing whats the "array access" performed here (none!) is wrong.

If the address is inside or one after the object then it's OK.

Here we guess an element size of 12, visible by

warning: array subscript 16 is outside array bounds of 'std::array<int, 3> [1]'

but no idea where the [1] comes from.  The code might try to match
some useful cases but it should give up in a more forgiving way when it
gets totally wrong in cases like this.

[Bug tree-optimization/107699] 12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|False positive              |12/13 Regression] False
                   |-Warray-bounds,             |positive -Warray-bounds,
                   |non-existent offset         |non-existent offset
                   |reported by GCC             |reported by GCC
   Target Milestone|---                         |12.3
           Priority|P3                          |P2
      Known to work|                            |11.3.1

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[carlosgalvezp at gmail dot com]

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

--- Comment #2 from Carlos Galvez <carlosgalvezp at gmail dot com> ---
Looking deeply at the stacktrace, I see that std::sort ends up in this kind of
code:

      if (__last - __first > int(_S_threshold))
        {
          std::__insertion_sort(__first, __first + int(_S_threshold), __comp);

Since the __last iterator cannot be known at compile time, this "if" branch
must be generated by the compiler. But then std::sort has hardcoded this
_S_threshold = 16, and computes a pointer __first + 16, which is known to be
OOB.

The question is: should the compiler *really* warn in this type of code, in
-Wall, which is the bare-minimum warning level for all projects? While I can
see the usefulness, the sheer amount of false positives (see meta bug-tracker)
does not qualify this warning from being part of -Wall IMHO. This diagnostic
fits better as "-Wmaybe-array-bounds". 

The worst part is that people need to disable this warning globally, therefore
losing warning coverage on *true* OOB accesses happening in user code.

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[hp at gcc dot gnu.org]

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

Hans-Peter Nilsson <hp at gcc dot gnu.org> changed:

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

--- Comment #3 from Hans-Peter Nilsson <hp at gcc dot gnu.org> ---
(In reply to Carlos Galvez from comment #2)
> Since the __last iterator cannot be known at compile time, this "if" branch
> must be generated by the compiler. But then std::sort has hardcoded this
> _S_threshold = 16, and computes a pointer __first + 16, which is known to be
> OOB.
> 
> The question is: should the compiler *really* warn in this type of code, in
> -Wall, which is the bare-minimum warning level for all projects?

All analysis of the actual test-case aside, from the setting of "NEW" and "last
confirmed" of the bugzilla entry, the answer is clearly "no". ;-)

I'm not sure it happened this time, but sometimes reporters misinterpret
gcc-folks comments about the bug, to be comments related to the validity of
their test-case, when it's about what gcc did wrong.

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
At the point of the diagnostic we see

<bb 2> [local count: 1073741824]:
data._M_elems[0] = 3;
data._M_elems[1] = 2;
data._M_elems[2] = 1;
_8 = getCount ();
_1 = _8 * 4;
_2 = &data._M_elems + _1;
if (&data._M_elems != _2)
  goto <bb 3>; [53.47%]
else
  goto <bb 12>; [46.53%]

that should possibly be optimized to

if (_1 != 0)

but we cannot statically decide this jump.  There's a later dynamic jump
based on the very same _1, a check whether that's > 16, guarded by that
we diagnose

# .MEM_35 = VDEF <.MEM_34>
std::__insertion_sort.isra (&data._M_elems, &MEM <int[3]> [(void *)&data +
64B]);

where we complain about forming the (void *)&data + 64 address.

I can't see a way to suppress the diagnostic completely but it should
be possible to re-word it.

Note using a global getCount without a conditional that this bound
is inside 'data' bounds is not good programming practice.

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[carlosgalvezp at gmail dot com]

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

--- Comment #5 from Carlos Galvez <carlosgalvezp at gmail dot com> ---
> is not good programming practice.

Sure. In the real world, we have asserts for this. However this is a problem
when we build for Release mode, in which asserts are disabled and thus this
warning pops up.

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[carlosgalvezp at gmail dot com]

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

--- Comment #6 from Carlos Galvez <carlosgalvezp at gmail dot com> ---
A similar case in the real world would be this:

NumberSmallerThan3 getCount();

std::sort(data.begin(), data.begin() + static_cast<std::size_t>(getCount()));

The "NumberSmallerThan3" class holds and checks the invariant that "a number is
smaller than 3". The compiler is not aware of that.

Other real-world situation is Eigen-like code, where for performance reasons
these checks can only be applied in debug mode, not release mode. We get
warnings in release mode due to this.

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[rguenther at suse dot de]

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

--- Comment #7 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 29 Nov 2022, carlosgalvezp at gmail dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107699
> 
> --- Comment #5 from Carlos Galvez <carlosgalvezp at gmail dot com> ---
> > is not good programming practice.
> 
> Sure. In the real world, we have asserts for this. However this is a problem
> when we build for Release mode, in which asserts are disabled and thus this
> warning pops up.

Ah, fair enough - it's that GCC now figures the possibly out-of-bounds
access.  But yes, the diagnostic itself needs improvement.  With
C++23 you could try using [[assume]] to preserve the assertion.

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[carlosgalvezp at gmail dot com]

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

--- Comment #8 from Carlos Galvez <carlosgalvezp at gmail dot com> ---
I see!

In that case may I suggest to split the diagnostic into "Warray-bounds" and
"Wmaybe-array-bounds"? That way we could enable the first and disable the
second. The way it is today, we need to disable Warray-bounds entirely, which
naturally risks not catching true positives.

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:892e8c520be37d0a0f14e2ae375103c5303ed549

commit r13-4555-g892e8c520be37d0a0f14e2ae375103c5303ed549
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Dec 8 09:07:36 2022 +0100

    tree-optimization/107699 - missed &data._M_elems + _1 != &data._M_elems
folding

    The following addresses a missed folding noticed in PR107699 that can
    be fixed amending the existing &x + a != &x + b pattern to also handle
    the case of only one side having a pointer plus.  I'm moving the
    patterns next to related simpifications showing there'd be an existing
    pattern matching this if it were not gated with an explicit single_use
    constraint.  Note the new pattern also handles &x.a + a != &x.b, but
    this hints at some unification / generalization opportunities here.

            PR tree-optimization/107699
            * match.pd (&a !=/== &a.b + c -> (&a - &a.b) !=/== c): New
            pattern variant.

            * gcc.dg/tree-ssa/pr107699.c: New testcase.

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
The change fixed the missing

_2 = &data._M_elems + _1;
if (&data._M_elems != _2)
  goto <bb 3>; [53.47%]
else
  goto <bb 12>; [46.53%]

optimization only, the diagnostic is still there.

[Bug tree-optimization/107699] [12/13 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[carlosgalvezp at gmail dot com]

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

--- Comment #11 from Carlos Galvez <carlosgalvezp at gmail dot com> ---
Consider this more realistic example:

https://godbolt.org/z/jbbqbe8d9

The compiler has all the information available to ensure that getCount().get()
is smaller than 3, as enforced by the class invariant which is visible to the
compiler. Class invariants help us not having to check things all the time. For
example gsl::not_null allows us to not have to check for nullptr on every use.

[Bug tree-optimization/107699] [12/13/14 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[rguenth at gcc dot gnu.org]

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

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

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

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

[Bug tree-optimization/107699] [12/13/14 Regression] False positive -Warray-bounds, non-existent offset reported by GCC

[rguenth at gcc dot gnu.org]

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

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Carlos Galvez from comment #11)
> Consider this more realistic example:
> 
> https://godbolt.org/z/jbbqbe8d9
> 
> The compiler has all the information available to ensure that
> getCount().get() is smaller than 3, as enforced by the class invariant which
> is visible to the compiler. Class invariants help us not having to check
> things all the time. For example gsl::not_null allows us to not have to
> check for nullptr on every use.

This doesn't really change anything as the compiler doesn't see the
CTOR invoked or that 'x' isn't changed before being returned.

I think we want to somehow prevent the diagnostic on the library side.

This particular case is

  /// This is a helper function for the sort routine.
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void      
    __final_insertion_sort(_RandomAccessIterator __first,
                           _RandomAccessIterator __last, _Compare __comp)
    {     
      if (__last - __first > int(_S_threshold))
        { 
          std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
          std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
                                          __comp);
        }                 
      else
        std::__insertion_sort(__first, __last, __comp);

where we diagnose __first + int(_S_threshold) when that's visibly out-of-bounds
but __last - __first isn't constant.  I'm not exactly sure how
(I'm also not sure why we do the above thing, handling the first elements
separate from the rest...)?