[Bug tree-optimization/66974] New: -Warray-bounds false positive with -O3

[Bug tree-optimization/66974] New: -Warray-bounds false positive with -O3

[gajjanagadde at gmail dot com]

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

            Bug ID: 66974
           Summary: -Warray-bounds false positive with -O3
           Product: gcc
           Version: 5.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gajjanagadde at gmail dot com
                CC: gajjanagadde at gmail dot com
  Target Milestone: ---

Created attachment 36039
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36039&action=edit
gcc_warraybounds_false.i

Compiling the following code on GCC 5.2.0 produces a bogus out of bounds
warning at -O3 level:

-------
int foo(unsigned order) {
    int c[3] = {1, 2, 3};
    unsigned i, j;
    for (i = 1; i < order; i++) {
        for (j = 0; j < i / 2; j++) {
            c[j] += c[i] * c[i-j-1];
            c[i-j-1] += c[i] * c[j];
        }
    }
    return c[0];
}

----------------------
%gcc -Warray-bounds -O3 -c gcc_warraybounds_false.c

gcc_warraybounds_false.c: In function ‘foo’:
gcc_warraybounds_false.c:6:22: warning: array subscript is above array bounds
[-Warray-bounds]
             c[j] += c[i] * c[i-j-1];
                      ^
gcc_warraybounds_false.c:7:26: warning: array subscript is above array bounds
[-Warray-bounds]
             c[i-j-1] += c[i] * c[j];
                          ^
gcc_warraybounds_false.c:6:22: warning: array subscript is above array bounds
[-Warray-bounds]
             c[j] += c[i] * c[i-j-1];
                      ^
gcc_warraybounds_false.c:6:29: warning: array subscript is above array bounds
[-Warray-bounds]
             c[j] += c[i] * c[i-j-1];
                             ^
gcc_warraybounds_false.c:7:22: warning: array subscript is above array bounds
[-Warray-bounds]
             c[i-j-1] += c[i] * c[j];
                      ^
gcc_warraybounds_false.c:7:26: warning: array subscript is above array bounds
[-Warray-bounds]
             c[i-j-1] += c[i] * c[j];
                          ^
gcc_warraybounds_false.c:7:22: warning: array subscript is above array bounds
[-Warray-bounds]
             c[i-j-1] += c[i] * c[j];


-----------------------

config:
Using built-in specs.
COLLECT_GCC=/usr/bin/gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-unknown-linux-gnu/5.2.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: /build/gcc/src/gcc-5.2.0/configure --prefix=/usr
--libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man
--infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/
--enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-shared
--enable-threads=posix --enable-libmpx --with-system-zlib --with-isl
--enable-__cxa_atexit --disable-libunwind-exceptions --enable-clocale=gnu
--disable-libstdcxx-pch --disable-libssp --enable-gnu-unique-object
--enable-linker-build-id --enable-lto --enable-plugin
--enable-install-libiberty --with-linker-hash-style=gnu
--enable-gnu-indirect-function --disable-multilib --disable-werror
--enable-checking=release --with-default-libstdcxx-abi=gcc4-compatible
Thread model: posix
gcc version 5.2.0 (GCC)
>From gcc-bugs-return-493061-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Jul 23 03:06:15 2015
Return-Path: <gcc-bugs-return-493061-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 44638 invoked by alias); 23 Jul 2015 03:06:15 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 44592 invoked by uid 48); 23 Jul 2015 03:06:10 -0000
From: "dj at redhat dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/66974] -Warray-bounds false positive with -O3
Date: Thu, 23 Jul 2015 03:06:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 5.2.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: dj at redhat dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: cc
Message-ID: <bug-66974-4-hhZZIWCsDk@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-66974-4@http.gcc.gnu.org/bugzilla/>
References: <bug-66974-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-07/txt/msg01951.txt.bz2
Content-length: 630

https://gcc.gnu.org/bugzilla/show_bug.cgi?idf974

DJ Delorie <dj at redhat dot com> changed:

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

--- Comment #1 from DJ Delorie <dj at redhat dot com> ---
If elsewhere calls foo(500) you will get an actual out of bounds access.  I
think the warning is appropriate.  Have you tried checking the value of 'order'
in that function, before the loop, to validate its value?  Such a check might
fix your bug and silence the warning.

[Bug tree-optimization/66974] -Warray-bounds false positive with -O3

[gajjanagadde at gmail dot com]

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

--- Comment #2 from Ganesh Ajjanagadde <gajjanagadde at gmail dot com> ---
Of course. However, the caller might ensure that order is always in the valid
range (e.g <= 3 in this case), and the callee should not have to verify this
if that is the case. The reason we do not actually do the check is because it
is in performance critical code (note test case is simplified and does not
convey how critical it is, which can only be seen from interactions with larger
codebase).

As per manual,
-----------------------
-Warray-bounds
-Warray-bounds=n
This option is only active when -ftree-vrp is active (default for -O2 and
above).  It warns about subscripts to arrays that are always out of bounds. 
This warning is enabled by -Wall.

-Warray-bounds=1
This  is  the  warning  level  of -Warray-bounds and  is  enabled  by -Wall;
higher levels are not, and must be explicitly requested.

-Warray-bounds=2
This warning level also warns about out of bounds access for arrays
at  the  end  of  a  struct  and  for  arrays  accessed  through  pointers.
This warning level may give a larger number of false positives and
is deactivated by default.
--------------------------

Thus, -Warray-bounds should not flag unless the compiler is certain about the
out of bounds nature. Here the compiler can't do that, and should not give a
false positive.

For the sake of argument, suppose it should flag this. Then -Warray-bounds is
not terribly useful, since much simpler code (below) does not trigger the
warning under same flags:

------------------

int foo(unsigned order) {
    int c[3] = {1, 2, 3};
    unsigned i;
    for (i=1; i < order; i++)
        c[i] += c[i/2];
    return c[0];
}

------------------

[Bug tree-optimization/66974] -Warray-bounds false positive with -O3

[manu at gcc dot gnu.org]

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

Manuel López-Ibáñez <manu at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |diagnostic
                 CC|                            |manu at gcc dot gnu.org

--- Comment #3 from Manuel López-Ibáñez <manu at gcc dot gnu.org> ---
The reason seems to be that GCC unrolls the inner loop completely to something
like:

if (i / 2 != 0) {
  // i > 1
      c[0] += c[i] * c[i-1];
      c[i-1] += c[i] * c[0];
      if (i / 2 > 1) {
        // i > 3
        c[1] += c[i] * c[i-2];
        c[i-2] += c[i] * c[1];
        if (i / 2 > 2) {
        // i > 5
          c[2] += c[i] * c[i-3];
          c[i-3] += c[i] * c[2];
        }
      }
 }

by reasoning that j < 3. However, it is not able to remove the two inner
conditions by reasoning that i < 3  Since i's upper-bound depends on order and
order is a parameter, it should be able to assume it (or at least say "may be
above").

Interestingly, if one changes the function to:

int foo(unsigned order) {
  int c[3] = {1, 2, 3};
  if (order >= 5) return 0;
  unsigned i, j;
  for (i = 1; i < order; i++) {
    for (j = 0; j < i / 2; j++) {
      c[j] += c[i] * c[i-j-1];
      c[i-j-1] += c[i] * c[j];
    }
  }
  return c[0];
}

There is an out-of-bounds access that is not detected by -Warray-bounds, but it
is detected by -Wuninitialized:

test.c:7:16: warning: ‘c[3u]’ may be used uninitialized in this function
[-Wmaybe-uninitialized]
       c[j] += c[i] * c[i-j-1];
                ^
>From gcc-bugs-return-493074-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Jul 23 09:43:31 2015
Return-Path: <gcc-bugs-return-493074-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 112927 invoked by alias); 23 Jul 2015 09:43:30 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 112867 invoked by uid 48); 23 Jul 2015 09:43:27 -0000
From: "dwmw2 at infradead dot org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug target/50818] va_list is filled incorrectly in functions with ms_abi attribute on amd64
Date: Thu, 23 Jul 2015 09:43:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: target
X-Bugzilla-Version: 4.4.5
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: dwmw2 at infradead dot org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: cc
Message-ID: <bug-50818-4-B8XYOgnXzk@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-50818-4@http.gcc.gnu.org/bugzilla/>
References: <bug-50818-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-07/txt/msg01964.txt.bz2
Content-length: 1016

https://gcc.gnu.org/bugzilla/show_bug.cgi?idP818

David Woodhouse <dwmw2 at infradead dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dwmw2 at infradead dot org

--- Comment #2 from David Woodhouse <dwmw2 at infradead dot org> ---
Still broken in 5.1.1.

Note that if you contrive to build it with -mabi=ms on the command line (by
splitting the two functions into separate files and building them separately),
it works fine.

It also works fine if you explicitly use __builtin_ms_va_{list,start,end}.

The problem seems to be that GCC is using the *global* ABI setting to decide
what to do when it sees a plain __builtin_va_list, rather the ABI for the
*current* function.

This is hurting us for UEFI builds too, where only public functions are marked
with __attribute__((ms_abi)) but we need *some* way to make va_list do the
right thing in the general case.