Bug 59124 - [6 Regression] Wrong warnings "array subscript is above array bounds"
Summary: [6 Regression] Wrong warnings "array subscript is above array bounds"
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.8.3
: P2 normal
Target Milestone: 6.5
Assignee: Patrick Palka
URL:
Keywords: diagnostic
: 66992 (view as bug list)
Depends on:
Blocks: Warray-bounds
  Show dependency treegraph
 
Reported: 2013-11-14 00:44 UTC by Dmitry Gorbachev
Modified: 2017-11-16 16:35 UTC (History)
15 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.7.4
Known to fail: 4.8.0, 4.9.0, 8.0
Last reconfirmed: 2013-11-14 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Dmitry Gorbachev 2013-11-14 00:44:10 UTC
$ gcc -S -Wall -O3 1.c
1.c: In function 'foo':
1.c:12:23: warning: array subscript is above array bounds [-Warray-bounds]
       bar[j - 1] = baz[j - 1];
                       ^
1.c:12:23: warning: array subscript is above array bounds [-Warray-bounds]

=============== 8< ===============
unsigned baz[6];

void foo(unsigned *bar, unsigned n)
{
  unsigned i, j;

  if (n > 6)
    n = 6;

  for (i = 1; i < n; i++)
    for (j = i - 1; j > 0; j--)
      bar[j - 1] = baz[j - 1];
}
=============== >8 ===============

GCC 4.8.0 20120902 /rev. 190863/ - works,
GCC 4.8.0 20121111 /rev. 193417/ - fails.
Comment 1 Richard Biener 2013-11-14 09:51:08 UTC
Confirmed.  The inner loop is completely peeled but unreachable code remains.
Comment 2 Dmitry Gorbachev 2013-11-14 17:56:50 UTC
Another testcase:

============= 8< =============
extern char *bar[17];

int foo(int argc, char **argv)
{
  int i;
  int n = 0;

  for (i = 0; i < argc; i++)
    n++;

  for (i = 0; i < argc; i++)
    argv[i] = bar[i + n];

  return 0;
}
============= >8 =============

$ gcc -S -Wall -O3 2.c
2.c: In function 'foo':
2.c:12:18: warning: array subscript is above array bounds [-Warray-bounds]
     argv[i] = bar[i + n];
                  ^
2.c:12:18: warning: array subscript is above array bounds [-Warray-bounds]
2.c:12:18: warning: array subscript is above array bounds [-Warray-bounds]
2.c:12:18: warning: array subscript is above array bounds [-Warray-bounds]
2.c:12:18: warning: array subscript is above array bounds [-Warray-bounds]
2.c:12:18: warning: array subscript is above array bounds [-Warray-bounds]
2.c:12:18: warning: array subscript is above array bounds [-Warray-bounds]
2.c:12:18: warning: array subscript is above array bounds [-Warray-bounds]
2.c:12:18: warning: array subscript is above array bounds [-Warray-bounds]
Comment 3 Jakub Jelinek 2014-03-12 14:33:31 UTC
Both testcases regressed with r192538.
Comment 4 Richard Biener 2014-05-22 09:02:37 UTC
GCC 4.8.3 is being released, adjusting target milestone.
Comment 5 Jakub Jelinek 2014-12-19 13:25:19 UTC
GCC 4.8.4 has been released.
Comment 6 Richard Biener 2015-01-27 09:50:04 UTC
Author: rguenth
Date: Tue Jan 27 09:49:29 2015
New Revision: 220157

URL: https://gcc.gnu.org/viewcvs?rev=220157&root=gcc&view=rev
Log:
2015-01-27  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/56273
	PR tree-optimization/59124
	PR tree-optimization/64277
	* tree-vrp.c (vrp_finalize): Emit array-bound warnings only
	from the first VRP pass.

	* g++.dg/warn/Warray-bounds-6.C: New testcase.
	* gcc.dg/Warray-bounds-12.c: Likewise.
	* gcc.dg/Warray-bounds-13.c: Likewise.

Added:
    trunk/gcc/testsuite/g++.dg/warn/Warray-bounds-6.C
    trunk/gcc/testsuite/gcc.dg/Warray-bounds-12.c
    trunk/gcc/testsuite/gcc.dg/Warray-bounds-13.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c
Comment 7 Richard Biener 2015-01-27 10:59:25 UTC
The testcase in comment #2 is fixed for GCC 5 but the original testcase still warns.
Comment 8 Alexander Peslyak 2015-02-18 02:22:41 UTC
Here's another testcase:

$ gcc -S -Wall -O2 -funroll-loops testcase.c 
testcase.c: In function 'DES_std_set_key':
testcase.c:14:17: warning: array subscript is above array bounds [-Warray-bounds]
   while (DES_key[i++]) k += 2;
                 ^

=============== 8< ===============
static int DES_KS_updates;
static char DES_key[16];

void DES_std_set_key(char *key)
{
        int i, j, k, l;

        j = key[0];
        for (k = i = 0; (l = DES_key[i]) && (j = key[i]); i++)
                ;

        if (!j) {
                j = i;
                while (DES_key[i++]) k += 2;
        }

        if (k < j && ++DES_KS_updates) {
        }

        DES_key[0] = key[0];
}
=============== >8 ===============

GCC 4.7.4 and below report no warning, 4.8.0 and 4.9.2 report the warning above.  Either -O2 -funroll-loops or -O3 result in the warning; simple -O2 does not.  While i++ could potentially run beyond the end of DES_key[], depending on what's in DES_key[] and key[], this isn't the case in the program this snippet is taken from (and simplified), whereas the warning definitively claims "is" rather than "might be".

For comparison, Dmitry's first testcase (from this bug's description) results in no warning with -O2 -funroll-loops (but does give the warning to me with -O3, as reported by Dmitry), whereas his second testcase (from comment 2) also reports the warning with -O2 -funroll-loops (but not with simple -O2).  I tested this with 4.9.2.

I hope this is similar enough to add to this bug (same affected versions, one of the two testcases also affected by -funroll-loops).
Comment 9 Alexander Peslyak 2015-02-18 04:37:23 UTC
(In reply to Alexander Peslyak from comment #8)
> $ gcc -S -Wall -O2 -funroll-loops testcase.c 
> testcase.c: In function 'DES_std_set_key':
> testcase.c:14:17: warning: array subscript is above array bounds

With GCC 5.0.0 20150215, this warning is gone.  I also confirm that Dmitry's comment #2 warning is gone.  The original one from this bug's description remains.
Comment 10 Richard Biener 2015-02-19 14:13:50 UTC
Author: rguenth
Date: Thu Feb 19 14:13:16 2015
New Revision: 220815

URL: https://gcc.gnu.org/viewcvs?rev=220815&root=gcc&view=rev
Log:
2015-02-19  Richard Biener  <rguenther@suse.de>

	Backport from mainline
	2014-12-09  Richard Biener  <rguenther@suse.de>

	PR middle-end/64199
	* fold-const.c (fold_binary_loc): Use TREE_OVERFLOW_P.

	* gcc.dg/torture/pr64199.c: New testcase.

	2015-01-14  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/64493
	PR tree-optimization/64495
	* tree-vect-loop.c (vect_finalize_reduction): For double-reductions
	assign the proper vectorized PHI to the inner loop exit PHIs.

	* gcc.dg/vect/pr64493.c: New testcase.
	* gcc.dg/vect/pr64495.c: Likewise.

	2015-01-27  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/56273
	PR tree-optimization/59124
	PR tree-optimization/64277
	* tree-vrp.c (vrp_finalize): Emit array-bound warnings only
	from the first VRP pass.

	* g++.dg/warn/Warray-bounds-6.C: New testcase.
	* gcc.dg/Warray-bounds-12.c: Likewise.
	* gcc.dg/Warray-bounds-13.c: Likewise.

	2015-02-19  Richard Biener  <rguenther@suse.de>

	Backport from mainline
	2015-01-15  Richard Biener  <rguenther@suse.de>

	PR middle-end/64365
	* tree-data-ref.c (dr_analyze_indices): Make sure that accesses
	for MEM_REF access functions with the same base can never partially
	overlap.

	* gcc.dg/torture/pr64365.c: New testcase.

Added:
    branches/gcc-4_9-branch/gcc/testsuite/g++.dg/warn/Warray-bounds-6.C
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/Warray-bounds-12.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/Warray-bounds-13.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr64199.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr64365.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/vect/pr64493.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/vect/pr64495.c
Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/fold-const.c
    branches/gcc-4_9-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_9-branch/gcc/tree-data-ref.c
    branches/gcc-4_9-branch/gcc/tree-vect-loop.c
    branches/gcc-4_9-branch/gcc/tree-vrp.c
Comment 11 Richard Biener 2015-02-24 12:49:43 UTC
Author: rguenth
Date: Tue Feb 24 12:49:11 2015
New Revision: 220939

URL: https://gcc.gnu.org/viewcvs?rev=220939&root=gcc&view=rev
Log:
2015-02-24  Richard Biener  <rguenther@suse.de>

        Backport from mainline
        2015-01-27  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/56273
	PR tree-optimization/59124
	PR tree-optimization/64277
	* tree-vrp.c (vrp_finalize): Emit array-bound warnings only
	from the first VRP pass.

	* g++.dg/warn/Warray-bounds-6.C: New testcase.
	* gcc.dg/Warray-bounds-12.c: Likewise.
	* gcc.dg/Warray-bounds-13.c: Likewise.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/g++.dg/warn/Warray-bounds-6.C
    branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/Warray-bounds-12.c
    branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/Warray-bounds-13.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-vrp.c
Comment 12 Georg Müller 2015-04-16 12:14:30 UTC
gcc --version
gcc (GCC) 5.0.1 20150413 (Red Hat 5.0.1-0.1)


When compiling the first example with -fopt-info, I see the following difference between -O2 -funroll-loops and -O3:

gcc -Wall -Wextra -fopt-info -O2 -c 1.c -funroll-loops
1.c:11:5: note: loop turned into non-loop; it never loops.
1.c:11:5: note: loop with 6 iterations completely unrolled
1.c:10:3: note: loop turned into non-loop; it never loops.
1.c:10:3: note: loop with 5 iterations completely unrolled


gcc -Wall -Wextra -fopt-info -O3 -c 1.c -funroll-loops
1.c:11:5: note: loop turned into non-loop; it never loops.
1.c:11:5: note: loop with 7 iterations completely unrolled
1.c: In function 'foo':
1.c:12:23: warning: array subscript is above array bounds [-Warray-bounds]
       bar[j - 1] = baz[j - 1];
                       ^
1.c:12:23: warning: array subscript is above array bounds [-Warray-bounds]
1.c:10:3: note: loop turned into non-loop; it never loops.
1.c:10:3: note: loop with 5 iterations completely unrolled

So, -O2 unrolls 6 and 5 iterations, while -O3 unrolls 7 and 5.
Comment 13 Georg Müller 2015-05-26 15:34:34 UTC
This bug is causing dpdk build failures on my fedora 22 machine:

git clone git://dpdk.org/dpdk
cd dpdk
make config T=x86_64-native-linuxapp-gcc
make

[...]
.../dpdk/lib/librte_eal/linuxapp/eal/eal_memory.c:1193:35: error: array subscript is above array bounds [-Werror=array-bounds]
      internal_config.hugepage_info[j].hugepage_sz) {
                                   ^
.../dpdk/lib/librte_eal/linuxapp/eal/eal_memory.c:1198:34: error: array subscript is above array bounds [-Werror=array-bounds]
     internal_config.hugepage_info[j].num_pages[socket]++;
                                  ^
.../dpdk/lib/librte_eal/linuxapp/eal/eal_memory.c:1198:34: error: array subscript is above array bounds [-Werror=array-bounds]
[...]

(fix is to disable -Werror, but it I had no problems with fedora 22 (gcc 4.9.2))
Comment 14 Georg Müller 2015-05-26 15:38:45 UTC
sorry, a small typo in the last line of the last message: there was no problem with fedora 21, not 22...
Comment 15 daniel 2015-06-01 23:49:40 UTC
FYI, I'm seeing a similar error on Arch Linux using 5.1.0.
== Build lib/librte_eal/linuxapp/eal
  CC eal.o
  CC eal_hugepage_info.o
  CC eal_memory.o
.../dpdk-2.0.0/lib/librte_eal/linuxapp/eal/eal_memory.c: In function ‘rte_eal_hugepage_init’:
.../dpdk-2.0.0/lib/librte_eal/linuxapp/eal/eal_memory.c:1193:35: error: array subscript is above array bounds [-Werror=array-bounds]
      internal_config.hugepage_info[j].hugepage_sz) {
                                   ^
.../dpdk-2.0.0/lib/librte_eal/linuxapp/eal/eal_memory.c:1198:34: error: array subscript is above array bounds [-Werror=array-bounds]
     internal_config.hugepage_info[j].num_pages[socket]++;
                                  ^
.../dpdk-2.0.0/lib/librte_eal/linuxapp/eal/eal_memory.c:1198:34: error: array subscript is above array bounds [-Werror=array-bounds]
cc1: all warnings being treated as errors
.../dpdk-2.0.0/mk/internal/rte.compile-pre.mk:126: recipe for target 'eal_memory.o' failed
[...]
Comment 16 Richard Biener 2015-06-23 08:14:37 UTC
The gcc-4_8-branch is being closed, re-targeting regressions to 4.9.3.
Comment 17 Jakub Jelinek 2015-06-26 19:52:07 UTC
GCC 4.9.3 has been released.
Comment 18 baoshan 2015-09-10 21:04:35 UTC
I see this issue on 5.2.0 too:

cat test.c
unsigned baz[6];
void test(unsigned *bar, unsigned n) {
     unsigned i, j;
     if (n > 6) {
          n = 6;
     }
     for (i = 1; i < n; i++) {
          for (j = i - 1; j > 0; j--) {
               bar[j - 1] = baz[j - 1];
          }
     }
}
bpg@ala-bpg-lx1$./cross/bin/arm-linux-gnueabi-gcc -c -Wall -O3 test.c
test.c: In function ‘test’:
test.c:9:32: warning: array subscript is above array bounds [-Warray-bounds]
                bar[j - 1] = baz[j - 1];
                                ^
test.c:9:32: warning: array subscript is above array bounds [-Warray-bounds]
bpg@ala-bpg-lx1$./cross/bin/arm-linux-gnueabi-gcc -v
Using built-in specs.
COLLECT_GCC=./cross/bin/arm-linux-gnueabi-gcc
COLLECT_LTO_WRAPPER=/net/ala-rsu-lx1/ala-rsu-lx11/bpg/SHARE/GCC520/X_520/cross/libexec/gcc/arm-linux-gnueabi/5.2.0/lto-wrapper
Target: arm-linux-gnueabi
Configured with: ../gcc-5.2.0/configure --prefix=/net/ala-rsu-lx1/ala-rsu-lx11/bpg/SHARE/GCC520/X_520/cross --target=arm-linux-gnueabi --enable-languages=c,c++ --d\
isable-multilib
Thread model: posix
gcc version 5.2.0 (GCC)
Comment 19 baoshan 2015-09-10 21:52:53 UTC
I did a little investigation to the code:

The warning occurs because tree_int_cst_lt (up_bound, up_sub) is true here:
  else if (TREE_CODE (up_sub) == INTEGER_CST
           && (ignore_off_by_one
               ? (tree_int_cst_lt (up_bound, up_sub)
                  && !tree_int_cst_equal (up_bound_p1, up_sub))
               : (tree_int_cst_lt (up_bound, up_sub)
                  || tree_int_cst_equal (up_bound_p1, up_sub))))
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
        {
          fprintf (dump_file, "Array bound warning for ");
          dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
          fprintf (dump_file, "\n");
        }
      warning_at (location, OPT_Warray_bounds,
=>                "array subscript is above array bounds");
      TREE_NO_WARNING (ref) = 1;
    }

I dumped the tree up_bound and up_sub:
(gdb) p debug_tree(up_bound)
 <integer_cst 0x7ffff6acd3a8 type <integer_type 0x7ffff6c3d0a8 sizetype> constant 5>
 p debug_tree(up_sub)
 <integer_cst 0x7ffff6ae92d0 type <integer_type 0x7ffff6c3d738 unsigned int> constant 4294967291>

We can see the value of up_sub is represented as unsigned int value 4294967291 which is really weird to me, it suppose to be a int value -5 here.
Comment 20 Manuel López-Ibáñez 2015-09-11 00:29:50 UTC
(In reply to baoshan from comment #19)
> We can see the value of up_sub is represented as unsigned int value
> 4294967291 which is really weird to me, it suppose to be a int value -5 here.

All counters are unsigned. You can see what code looks like to GCC at exactly that moment by using -fdump-tree-all-all-lineno and looking for that line in test.c.079t.vrp1. 

;;   basic block 10, loop depth 1, count 0, freq 1430, maybe hot
;;   Invalid sum of incoming frequencies 1226, should be 1430
;;    prev block 9, next block 11, flags: (NEW, REACHABLE)
;;    pred:       9 [85.7%]  (TRUE_VALUE,EXECUTABLE)
;;   starting at line 9
  [test.c:9:13] # RANGE [4294967291, 4294967295]
  _51 = i_2 + 4294967290;
  [test.c:9:10] # RANGE [4294967291, 4294967295] NONZERO 4294967295
  _52 = (long unsigned intD.10) _51;
  [test.c:9:10] # RANGE [17179869164, 17179869180] NONZERO 17179869180
  _53 = _52 * 4;
  [test.c:9:10] # PT = nonlocal
  _54 = bar_12(D) + _53;
  [test.c:9:23] # VUSE <.MEM_48>
  _55 = [test.c:9:23] bazD.1755[_51];
  [test.c:9:18] # .MEM_56 = VDEF <.MEM_48>
  [test.c:9:10] *_54 = _55;
  [test.c:9:13] # RANGE [4294967290, 4294967294]
  _59 = i_2 + 4294967289;
  [test.c:9:10] # RANGE [4294967290, 4294967294] NONZERO 4294967295
  _60 = (long unsigned intD.10) _59;
  [test.c:9:10] # RANGE [17179869160, 17179869176] NONZERO 17179869180
  _61 = _60 * 4;
  [test.c:9:10] # PT = nonlocal
  _62 = bar_12(D) + _61;
  [test.c:9:23] # VUSE <.MEM_56>
  _63 = [test.c:9:23] bazD.1755[_59];
  [test.c:9:18] # .MEM_64 = VDEF <.MEM_56>
  [test.c:9:10] *_62 = _63;
;;    succ:       11 [100.0%]  (FALLTHRU,EXECUTABLE)

It seems GCC at some moment unrolls the loop and creates such block with those ranges. Probably, the block is unreachable, but it would be better to not create it in the first place. Finding out where and why it is created would help to figure out a fix.
Comment 21 baoshan 2015-09-11 16:13:48 UTC
(In reply to Manuel López-Ibáñez from comment #20)
> (In reply to baoshan from comment #19)
> > We can see the value of up_sub is represented as unsigned int value
> > 4294967291 which is really weird to me, it suppose to be a int value -5 here.
> 
> All counters are unsigned. You can see what code looks like to GCC at
> exactly that moment by using -fdump-tree-all-all-lineno and looking for that
> line in test.c.079t.vrp1. 
> 
> ;;   basic block 10, loop depth 1, count 0, freq 1430, maybe hot
> ;;   Invalid sum of incoming frequencies 1226, should be 1430
> ;;    prev block 9, next block 11, flags: (NEW, REACHABLE)
> ;;    pred:       9 [85.7%]  (TRUE_VALUE,EXECUTABLE)
> ;;   starting at line 9
>   [test.c:9:13] # RANGE [4294967291, 4294967295]
>   _51 = i_2 + 4294967290;
>   [test.c:9:10] # RANGE [4294967291, 4294967295] NONZERO 4294967295
>   _52 = (long unsigned intD.10) _51;
>   [test.c:9:10] # RANGE [17179869164, 17179869180] NONZERO 17179869180
>   _53 = _52 * 4;
>   [test.c:9:10] # PT = nonlocal
>   _54 = bar_12(D) + _53;
>   [test.c:9:23] # VUSE <.MEM_48>
>   _55 = [test.c:9:23] bazD.1755[_51];
>   [test.c:9:18] # .MEM_56 = VDEF <.MEM_48>
>   [test.c:9:10] *_54 = _55;
>   [test.c:9:13] # RANGE [4294967290, 4294967294]
>   _59 = i_2 + 4294967289;
>   [test.c:9:10] # RANGE [4294967290, 4294967294] NONZERO 4294967295
>   _60 = (long unsigned intD.10) _59;
>   [test.c:9:10] # RANGE [17179869160, 17179869176] NONZERO 17179869180
>   _61 = _60 * 4;
>   [test.c:9:10] # PT = nonlocal
>   _62 = bar_12(D) + _61;
>   [test.c:9:23] # VUSE <.MEM_56>
>   _63 = [test.c:9:23] bazD.1755[_59];
>   [test.c:9:18] # .MEM_64 = VDEF <.MEM_56>
>   [test.c:9:10] *_62 = _63;
> ;;    succ:       11 [100.0%]  (FALLTHRU,EXECUTABLE)
> 
> It seems GCC at some moment unrolls the loop and creates such block with
> those ranges. Probably, the block is unreachable, but it would be better to
> not create it in the first place. Finding out where and why it is created
> would help to figure out a fix.

Don't you think the range value is strange? how it is possible the range value is so big according the code?
Comment 22 Manuel López-Ibáñez 2015-09-11 16:51:08 UTC
(In reply to baoshan from comment #21)
> Don't you think the range value is strange? how it is possible the range
> value is so big according the code?

j = i - 1 is actually j = i + 4294967295 because of unsigned.

Thus the problematic ranges:

   [test.c:9:13] # RANGE [4294967291, 4294967295]
   _51 = i_2 + 4294967290;

 are actually:

   [test.c:9:13] # RANGE [-5, -1]
   _51 = i_2 - 6;

but this code should have not been generated. Those ranges do seem suspicious. Finding out how that block ends up with those ranges would be helpful. You probably need to debug vrp or (using -fopt-info) the point where gcc gives:

test.c:7:3: note: loop turned into non-loop; it never loops.
test.c:7:3: note: loop with 5 iterations completely unrolled
Comment 23 baoshan 2015-09-17 18:18:30 UTC
(In reply to Manuel López-Ibáñez from comment #22)
> (In reply to baoshan from comment #21)
> > Don't you think the range value is strange? how it is possible the range
> > value is so big according the code?
> 
> j = i - 1 is actually j = i + 4294967295 because of unsigned.
> 
> Thus the problematic ranges:
> 
>    [test.c:9:13] # RANGE [4294967291, 4294967295]
>    _51 = i_2 + 4294967290;
> 
>  are actually:
> 
>    [test.c:9:13] # RANGE [-5, -1]
>    _51 = i_2 - 6;
> 
> but this code should have not been generated. Those ranges do seem
> suspicious. Finding out how that block ends up with those ranges would be
> helpful. You probably need to debug vrp or (using -fopt-info) the point
> where gcc gives:
> 
> test.c:7:3: note: loop turned into non-loop; it never loops.
> test.c:7:3: note: loop with 5 iterations completely unrolled

I have seen two places that would convert "A-1" to "A+(-1)", and due the type is unsigned int, it would be converted to "A+4294967295". This looks not right to me.

The two places are:
1. fold-const.c:10626
      /* A - B -> A + (-B) if B is easily negatable.  */
      if (negate_expr_p (arg1)
          && !TYPE_OVERFLOW_SANITIZED (type)
          && ((FLOAT_TYPE_P (type)
               /* Avoid this transformation if B is a positive REAL_CST.  */
               && (TREE_CODE (arg1) != REAL_CST
                   ||  REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg1))))
              || INTEGRAL_TYPE_P (type)))
=>      return fold_build2_loc (loc, PLUS_EXPR, type,
                            fold_convert_loc (loc, type, arg0),
                            fold_convert_loc (loc, type,
                                              negate_expr (arg1)));

2. c-common.c:4574
  if (resultcode == MINUS_EXPR)
    intop = fold_build1_loc (loc, NEGATE_EXPR, sizetype, intop);
Comment 24 Andrew Pinski 2015-09-17 18:42:50 UTC
(In reply to baoshan from comment #23)
> I have seen two places that would convert "A-1" to "A+(-1)", and due the
> type is unsigned int, it would be converted to "A+4294967295". This looks
> not right to me.

Why wrapping is well defined for unsigned types so adding 4294967295 is the same as subtracting by 1.
Comment 25 baoshan 2015-09-17 19:02:18 UTC
(In reply to Andrew Pinski from comment #24)
> (In reply to baoshan from comment #23)
> > I have seen two places that would convert "A-1" to "A+(-1)", and due the
> > type is unsigned int, it would be converted to "A+4294967295". This looks
> > not right to me.
> 
> Why wrapping is well defined for unsigned types so adding 4294967295 is the
> same as subtracting by 1.

What is wrapping? and where it is defined? I don't know this part and I like to learn it.
Thanks.
Comment 26 Jakub Jelinek 2015-09-17 19:08:12 UTC
(In reply to baoshan from comment #25)
> > Why wrapping is well defined for unsigned types so adding 4294967295 is the
> > same as subtracting by 1.
> 
> What is wrapping? and where it is defined? I don't know this part and I like
> to learn it.
> Thanks.

Just read the C or C++ standards?
E.g. C99, 6.2.5/9:
... "A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type." ...
Comment 27 baoshan 2015-09-18 17:59:33 UTC
> It seems GCC at some moment unrolls the loop and creates such block with
> those ranges. Probably, the block is unreachable, but it would be better to
> not create it in the first place. Finding out where and why it is created
> would help to figure out a fix.


At pass "cunrolli", it would unroll the loops according the estimated iterate times. The problem is at this time it use array ref(infer_loop_bounds_from_ref) to infer the iterate times which is not accurate. The inaccurate iterate times result the extra blocks.

I am not sure which way to go at this point. Should we add value range propagation in/before "cunrolli" so we can get the accurate iterate times? or We just disable the warning being reported at "vrp" pass?
Comment 28 Manuel López-Ibáñez 2015-09-18 18:32:10 UTC
(In reply to baoshan from comment #27)
> > It seems GCC at some moment unrolls the loop and creates such block with
> > those ranges. Probably, the block is unreachable, but it would be better to
> > not create it in the first place. Finding out where and why it is created
> > would help to figure out a fix.
> 
> 
> At pass "cunrolli", it would unroll the loops according the estimated
> iterate times. The problem is at this time it use array
> ref(infer_loop_bounds_from_ref) to infer the iterate times which is not
> accurate. The inaccurate iterate times result the extra blocks.

The question is why is it inaccurate? Note that cunrolli says:


Statement _14 = baz[_9];
 is executed at most 5 (bounded by 5) + 1 times in loop 2.
Loop 2 iterates at most 6 times.
Analyzing # of iterations of loop 2
  exit condition [i_2 + 4294967295, + , 4294967295] != 0
  bounds on difference of bases: -4294967295 ... 0
Applying pattern match.pd:71, generic-match.c:9500
  result:
    # of iterations i_2 + 4294967295, bounded by 4294967295
Estimating sizes for loop 2
 BB: 7, after_exit: 0
  size:   2 if (j_3 != 0)
   Exit condition will be eliminated in last copy.
 BB: 6, after_exit: 1
  size:   1 _9 = j_3 + 4294967295;
  size:   0 _10 = (long unsigned int) _9;
Applying pattern match.pd:71, generic-match.c:9500
Applying pattern match.pd:136, generic-match.c:6019
  size:   1 _11 = _10 * 4;
Applying pattern match.pd:71, generic-match.c:9500
Applying pattern match.pd:136, generic-match.c:6019
  size:   1 _13 = bar_12(D) + _11;
  size:   1 _14 = baz[_9];
  size:   1 *_13 = _14;
size: 7-0, last_iteration: 2-2
  Loop size: 7
  Estimated size after unrolling: 28
pr59124.c:8:5: note: loop turned into non-loop; it never loops.
pr59124.c:8:5: note: loop with 7 iterations completely unrolled
Last iteration exit edge was proved true.
Forced statement unreachable: _14 = baz[_9];


However, it is clear that _14 = baz[_9] is executed only 5 times (not 5 times + 1). Why is this estimate wrong?
Comment 29 baoshan 2015-09-18 18:53:18 UTC
> However, it is clear that _14 = baz[_9] is executed only 5 times (not 5
> times + 1). Why is this estimate wrong?

The max value of n is 6, so the max value of i is 5 as "i < n", then the max value of j is 4 as "j = i - 1" which means the max iterate times is 4.
Comment 30 Manuel López-Ibáñez 2015-09-18 19:17:20 UTC
(In reply to baoshan from comment #29)
> > However, it is clear that _14 = baz[_9] is executed only 5 times (not 5
> > times + 1). Why is this estimate wrong?
> 
> The max value of n is 6, so the max value of i is 5 as "i < n", then the max
> value of j is 4 as "j = i - 1" which means the max iterate times is 4.

True! Well, that reinforces my point that something is very wrong in the estimation. What is it?
Comment 31 baoshan 2015-09-18 21:11:44 UTC
(In reply to Manuel López-Ibáñez from comment #30)
> (In reply to baoshan from comment #29)
> > > However, it is clear that _14 = baz[_9] is executed only 5 times (not 5
> > > times + 1). Why is this estimate wrong?
> > 
> > The max value of n is 6, so the max value of i is 5 as "i < n", then the max
> > value of j is 4 as "j = i - 1" which means the max iterate times is 4.
> 
> True! Well, that reinforces my point that something is very wrong in the
> estimation. What is it?

At the pass "cunrolli", it infers the iterative times by checking the array's boundary, as we have "unsigned baz[6];", it would think the max value of iterative times is 6.
Comment 32 baoshan 2015-09-22 20:06:44 UTC
(In reply to Manuel López-Ibáñez from comment #30)
> (In reply to baoshan from comment #29)
> > > However, it is clear that _14 = baz[_9] is executed only 5 times (not 5
> > > times + 1). Why is this estimate wrong?
> > 
> > The max value of n is 6, so the max value of i is 5 as "i < n", then the max
> > value of j is 4 as "j = i - 1" which means the max iterate times is 4.
> 
> True! Well, that reinforces my point that something is very wrong in the
> estimation. What is it?

And I think it is not wrong, it's just inaccurate, and it is not making any wrong result in running time.

Can you point me how to proceed?
Comment 33 Manuel López-Ibáñez 2015-09-22 20:44:15 UTC
(In reply to baoshan from comment #32)
> And I think it is not wrong, it's just inaccurate, and it is not making any
> wrong result in running time.
> 
> Can you point me how to proceed?

To be honest, I don't know, since neither loop-unrolling nor VRP are my speciality. If you can figure out how the estimate can be improved in cunrolli, that would be great. There are some functions called after that point that seem to attempt to provide a more accurate estimate. One would need to go through them carefully in GDB and find out why they fail. 

If itl cannot be fixed here, the info about valid ranges is still inaccurate, that is, the loop may be unrolled into 6 iterations, but only 4 are ever executed. There must be a way to teach VRP that this is the case and mark the blocks as unreachable.

I hope other more knowledgeable devs will chime in, I'm out of ideas.
Comment 34 Jeffrey A. Law 2016-02-10 17:59:15 UTC
*** Bug 66992 has been marked as a duplicate of this bug. ***
Comment 35 Patrick Palka 2016-03-27 17:48:16 UTC
I have a rather simple patch that teaches VRP to insert the relevant ASSERT_EXPRs so that it knows to remove the unreachable code inserted by the loop unrolling.
Comment 36 Patrick Palka 2016-03-28 02:22:15 UTC
Patch posted at https://gcc.gnu.org/ml/gcc-patches/2016-03/msg01439.html
Comment 37 Domani Hannes 2016-03-29 19:02:14 UTC
With the new patch there is still a warning with this example:
=============== 8< ===============
int f(void);

int test(void)
{
  int baz[4];
  int q = 0;
  int d, i, j, sum;

  for (i = 0; i < 2; i++)
  {
    d = f();

    if (d == 3)
    {
      baz[q] = d;
      q++;
      if (q == 4) break;
    }
  }

  sum = 0;
  for (i = 0; i < q; i++)
  {
    for (j = i + 1; j < q; j++)
    {
      sum += baz[j];
    }
  }

  return (sum);
}
=============== >8 ===============
$ gcc -O3 -Wall -S q.c
q.c: In function 'test':
q.c:27:17: warning: array subscript is above array bounds [-Warray-bounds]
       sum += baz[j];
                 ^
Comment 38 Patrick Palka 2016-03-30 00:55:32 UTC
Author: ppalka
Date: Wed Mar 30 00:55:00 2016
New Revision: 234544

URL: https://gcc.gnu.org/viewcvs?rev=234544&root=gcc&view=rev
Log:
PR tree-optimization/59124 (bogus -Warray-bounds warning)

gcc/ChangeLog:

	PR tree-optimization/59124
	* tree-vrp.c (register_edge_assert_for_2): For NAME != CST1
	where NAME = A +- CST2 add the assertion A != (CST1 -+ CST2).

gcc/testsuite/ChangeLog:

	PR tree-optimization/59124
	* gcc.dg/Warray-bounds-19.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/Warray-bounds-19.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c
Comment 39 Patrick Palka 2016-03-30 01:04:24 UTC
(In reply to Domani Hannes from comment #37)
> With the new patch there is still a warning with this example:
> =============== 8< ===============
> int f(void);
> 
> int test(void)
> {
>   int baz[4];
>   int q = 0;
>   int d, i, j, sum;
> 
>   for (i = 0; i < 2; i++)
>   {
>     d = f();
> 
>     if (d == 3)
>     {
>       baz[q] = d;
>       q++;
>       if (q == 4) break;
>     }
>   }
> 
>   sum = 0;
>   for (i = 0; i < q; i++)
>   {
>     for (j = i + 1; j < q; j++)
>     {
>       sum += baz[j];
>     }
>   }
> 
>   return (sum);
> }
> =============== >8 ===============
> $ gcc -O3 -Wall -S q.c
> q.c: In function 'test':
> q.c:27:17: warning: array subscript is above array bounds [-Warray-bounds]
>        sum += baz[j];
>                  ^

Thanks, I'll check it out.  Seems to be a regression from 4.7 as well.
Comment 40 Richard Biener 2016-08-03 11:32:19 UTC
GCC 4.9 branch is being closed
Comment 41 Szőts Ákos 2016-08-30 12:25:47 UTC
A newer example:

int main() {
  bool exists = true;
  int i = 0;
  int sum = 0;

  volatile int array_size = 7;
  volatile int array[7];

  while (exists)
  {
    for (i = 0; i < array_size - 1; i++)
    {
      if (array[i] == 0) sum += array[i + 1];
      exists = false;
    }
  }

  return 0;
}

Can be reproduced both by v5.3.0 and v6.1.1 with "g++ -O3 -Wall main.cpp".
Comment 42 Patrick Palka 2016-08-30 13:18:19 UTC
(In reply to Szőts Ákos from comment #41)
> A newer example:
> 
> int main() {
>   bool exists = true;
>   int i = 0;
>   int sum = 0;
> 
>   volatile int array_size = 7;
>   volatile int array[7];
> 
>   while (exists)
>   {
>     for (i = 0; i < array_size - 1; i++)
>     {
>       if (array[i] == 0) sum += array[i + 1];
>       exists = false;
>     }
>   }
> 
>   return 0;
> }
> 
> Can be reproduced both by v5.3.0 and v6.1.1 with "g++ -O3 -Wall main.cpp".

Isn't this warning valid?  By marking array_size as volatile you are telling the compiler that its value could change at any time.  So the loop won't necessarily terminate once i == 6.
Comment 43 Szőts Ákos 2016-08-30 14:15:12 UTC
Yes, I can agree with this reasoning. However, when you remove either the "while" or the "if" statements, the warning disappears. I don't think they should have any influence on the array_size.
Comment 44 Patrick Palka 2016-08-31 18:30:28 UTC
(In reply to Szőts Ákos from comment #43)
> Yes, I can agree with this reasoning. However, when you remove either the
> "while" or the "if" statements, the warning disappears. I don't think they
> should have any influence on the array_size.

Hmm yeah it's rather flaky.  The warning depends on whether or not the compiler unrolls the for loop.
Comment 45 Jeffrey A. Law 2017-01-04 08:42:43 UTC
AFAICT all the valid tests within this BZ have been fixed on the trunk (and likely in gcc-6 as well).  I'm removing the gcc-7 regression marker.

Any additional issues with unrolling triggering false positive Wuninitialized warnings be reported as new bugs rather than piled onto this BZ.
Comment 46 Jakub Jelinek 2017-10-10 13:25:19 UTC
GCC 5 branch is being closed
Comment 47 Martin Sebor 2017-11-16 16:35:32 UTC
None of the test cases here except for the one in comment #41 triggers -Warray-bounds with GCC 8.0.  According to comments #42 and #43 the warning for the test case in comment #41 is a true positive.  I'll go ahead and resolve this as fixed.

I suggest to open a separate bug for any new/outstanding issues in this area to make it easier to track each separately.