[Bug c++/100038] New: -Warray-bound triggers false positives

[Bug c++/100038] New: -Warray-bound triggers false positives

[nicholas.stranchfield@you-spam.com]

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

            Bug ID: 100038
           Summary: -Warray-bound triggers false positives
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: nicholas.stranchfield@you-spam.com
  Target Milestone: ---

When compiling LLVM, I noticed that GCC produces some -Warray-bounds warnings,
namely

In file included from mwe.cpp:4:
SparseBitVector.h: In function ‘int main()’:
SparseBitVector.h:129:15: warning: array subscript 2 is above array bounds of
‘const BitWord [2]’ {aka ‘const long unsigned int [2]’} [-Warray-bounds]
  129 |       if (Bits[i] != 0)
      |           ~~~~^
SparseBitVector.h:54:11: note: while referencing
‘llvm::SparseBitVectorElement<128>::Bits’
   54 |   BitWord Bits[BITWORDS_PER_ELEMENT];
      |           ^~~~
SparseBitVector.h:138:15: warning: array subscript 4294967295 is above array
bounds of ‘const BitWord [2]’ {aka ‘const long unsigned int [2]’}
[-Warray-bounds]
  138 |       if (Bits[Idx] != 0)
      |           ~~~~^
SparseBitVector.h:54:11: note: while referencing
‘llvm::SparseBitVectorElement<128>::Bits’
   54 |   BitWord Bits[BITWORDS_PER_ELEMENT];
      |           ^~~~
In file included from mwe.cpp:3:
SmallVector.h:537:7: warning: array subscript 1 is outside array bounds of ‘int
[1]’ [-Warray-bounds]
  537 |       ++EltPtr;
      |       ^~
mwe.cpp:21:29: note: while referencing ‘<anonymous>’
   21 |  VS.insert(VS.begin() + 1, 5);
      |                             ^
In file included from mwe.cpp:3:
SmallVector.h:566:7: warning: array subscript 1 is outside array bounds of ‘int
[1]’ [-Warray-bounds]
  566 |       ++EltPtr;
      |       ^~
mwe.cpp:22:6: note: while referencing ‘val’
   22 |  int val = 6;
      |      ^~~

On inspection of the source, it seems these are false positives OR some
optimization went havoc (hopefully it did not), e.g. for SparseBitVector.h we
have

struct SparseBitVectorElement {
  // ...
  BitWord Bits[BITWORDS_PER_ELEMENT]; // line 54
  // ...
  int find_first() const {
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
      if (Bits[i] != 0) // line 129
        // ...
  }
}

which looks pretty sound to me.  Searching around the internet, I'm not the
only one with these warnings, e.g. they show up in Fedora's LLVM build [0,1]
and Debian's [2].
In particular, this case looks very simple and a common theme which should not
trigger such warning.

[0]
https://kojipkgs.fedoraproject.org/packages/llvm/10.0.0/0.6.rc6.fc33/data/logs/ppc64le/build.log
[1]
https://kojipkgs.fedoraproject.org/packages/llvm/11.0.0/0.2.rc3.fc34/data/logs/s390x/build.log
[2]
https://buildd.debian.org/status/fetch.php?pkg=llvm-toolchain-11&arch=amd64&ver=1%3A11.0.1-2&stamp=1609987721&raw=0

The SmallVector related warning appeared first with GCC 9.x, while the
SparseBitVector related warnings appeared with GCC 10 (tested GCC 10.2.0) and
are absent in GCC-9.3.0.
The warnings trigger with -O2 but not with -O1 and -DNDEBUG is needed for the
SparseBitVector one.

If LLVM headers (version 10 or 11) are installed, then the following minimal
working example triggers the warnings:

g++ -I/usr/lib/llvm/11/include -DNDEBUG -O2 -Warray-bounds -o mwe.cpp.o -c
mwe.cpp
cat mwe.cpp

#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SparseBitVector.h"

#include <stdio.h>

using namespace llvm;

int main()
{
        // Trigger: SparseBitVector (lines 138, 129)
        SparseBitVector<> Vec;
        Vec.set(5);
        // force the vector
        printf("%d\n", Vec.find_first());
        printf("%d\n", Vec.find_last());

        // Trigger: SmallVector (lines 537, 566)
        SmallVector<int, 2> VS = {1, 2, 3, 4};
        VS.insert(VS.begin() + 1, 5);
        int val = 6;
        VS.insert(VS.begin() + 2, val);
        // force the vector
        for (int i : VS) {
                printf("%d\n", i);
        }
}

[Bug middle-end/100038] -Warray-bound triggers false positives

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-04-11
             Status|UNCONFIRMED                 |WAITING
           Keywords|                            |diagnostic
          Component|c++                         |middle-end

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Can you attach the preprocessor source?

[Bug middle-end/100038] -Warray-bound triggers false positives

[nicholas.stranchfield@you-spam.com]

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

--- Comment #2 from Nicholas Stranchfield <nicholas.stranchfield@you-spam.com> ---
Created attachment 50557
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50557&action=edit
gzipped output of g++-10.2.0

Sure, here you go.

[Bug middle-end/100038] -Warray-bound triggers false positives

[nicholas.stranchfield@you-spam.com]

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

--- Comment #3 from Nicholas Stranchfield <nicholas.stranchfield@you-spam.com> ---
Created attachment 50558
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50558&action=edit
gzipped output for SparseBitVector example

[Bug middle-end/100038] -Warray-bound triggers false positives

[nicholas.stranchfield@you-spam.com]

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

--- Comment #4 from Nicholas Stranchfield <nicholas.stranchfield@you-spam.com> ---
Created attachment 50559
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50559&action=edit
gzipped output for SmallVector example

[Bug middle-end/100038] -Warray-bound triggers false positives

[nicholas.stranchfield@you-spam.com]

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

--- Comment #5 from Nicholas Stranchfield <nicholas.stranchfield@you-spam.com> ---
Created attachment 50560
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50560&action=edit
Output for only the SmallVector example

Here the output for only the SmallVector.h test case.

P.S.: Sorry for the nose, mistook the attachment text area for the comment
field...

[Bug middle-end/100038] -Warray-bound triggers false positives

[nicholas.stranchfield@you-spam.com]

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

--- Comment #6 from Nicholas Stranchfield <nicholas.stranchfield@you-spam.com> ---
Created attachment 50561
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50561&action=edit
Output for only the SparseBitVector example

Here the output for only the SparseBitVector.h test case.

[Bug middle-end/100038] -Warray-bound triggers false positives

[msebor at gcc dot gnu.org]

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

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=98465
                 CC|                            |msebor at gcc dot gnu.org

--- Comment #7 from Martin Sebor <msebor at gcc dot gnu.org> ---
Confirmed with attachment 50560 and the output/IL below.  The problem is caused
by the test (presumably for self-insertion) in
SmallVectorImpl<T>::insert(iterator, const T&):

    const T *EltPtr = &Elt;
    if (I <= EltPtr && EltPtr < this->end())
      ++EltPtr;

I don't see anything in the IL to avoid it without compromising it at the same
time.  We suppressed a similar false positive in std::string::insert() in
pr98465.  It was done by keeping the equivalent test from being inlined because
the usual suppression mechanism, #pragma GCC diagnostic, doesn't work reliably
with inlining (something that will hopefully be fixed in GCC 12).  Another
alternative to consider is inserting an optimization barrier after the block
above:

    asm volatile("": : :"memory");

Another (future) alternative is to annotate the SmallVector::BeginX with some
new attribute telling the optimizer it doesn't alias unrelated objects (like
val).  This doesn't exist but it would help not just avoid warnings but also
emit more optimal code.

(As an aside, the pointer test above is strictly unspecified because it
compares the addresses of unrelated objects,  It should convert the pointers to
integers first but that wouldn't prevent the warning.)

In file included from mwe_smallvector.cpp:2:
SmallVector.h: In function ‘int main()’:
SmallVector.h:537:7: warning: array subscript 1 is outside array bounds of ‘int
[1]’ [-Warray-bounds]
mwe_smallvector.cpp:12:11: note: while referencing ‘<anonymous>’
In file included from mwe_smallvector.cpp:2:
SmallVector.h:566:7: warning: array subscript 1 is outside array bounds of ‘int
[1]’ [-Warray-bounds]
mwe_smallvector.cpp:13:6: note: while referencing ‘val’
...
int main ()
{
  ...
  int D.55243;
  ...
  <bb 3>
  _21 = VS.D.54770.BeginX;
  _1 = _21 + 4;
  ...

  <bb 10> [local count: 32183167]:
  _52 = MEM[(struct SmallVectorTemplateCommon *)&VS].D.54770.BeginX;
  I_54 = _52 + 4;

  <bb 11> [local count: 97524748]:
  # I_69 = PHI <_1(8), I_54(10)>
  ...

  <bb 13> [local count: 97524748]:
  _115 = (long unsigned int) _111;
  _116 = -_115;
  _117 = _66 + _116;
  _70 = MEM[(const struct SmallVectorBase *)&VS].Size;
  _71 = _70 + 1;
  MEM[(struct SmallVectorBase *)&VS].Size = _71;
  if (&D.55243 >= I_69)
    goto <bb 14>; [50.00%]
  else
    goto <bb 16>; [50.00%]

  <bb 14> [local count: 48762374]:
  _72 = MEM[(struct SmallVectorTemplateCommon *)&VS].D.54770.BeginX;
  _73 = (long unsigned int) _71;
  _74 = _73 * 4;
  _75 = _72 + _74;
  if (&D.55243 < _75)
    goto <bb 15>; [50.00%]
  else
    goto <bb 16>; [50.00%]

  <bb 15> [local count: 24381187]:
  _50 = MEM[(type &)&D.55243 + 4];   <<< -Warray-bounds

[Bug tree-optimization/100038] -Warray-bound triggers false positives

[foom at fuhm dot net]

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

James Y Knight <foom at fuhm dot net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |foom at fuhm dot net

--- Comment #8 from James Y Knight <foom at fuhm dot net> ---
Here's a shorter test-case, reproduces with g++-11 -O2 -Warray-bounds:
```
struct SparseBitVectorElement {
  long Bits[2];
  int find_first() const;
};

int SparseBitVectorElement::find_first() const {
  for (unsigned i = 0; i < 2; ++i)
    if (Bits[i])
      return i; // 
  __builtin_unreachable(); // Illegal empty element
}
```

The "__builtin_unreachable" at the end of the function seems to be the trigger
for the issue -- presumably because the compiler decides to omit the loop end
condition as being unnecessary.


Trying the above on godbolt, it appears that it no longer occurs on gcc trunk
for this test-case. But, I don't know if that was intentionally fixed or just
happens not to trigger here. (I haven't tried compiling LLVM with a gcc trunk
snapshot to see if all similar warnings have gone away.)