The following C++ code cause current gcc master to emit an incorrect array bounds warning: $ cat test.cpp struct type { bool a, b; bool get_b() { return b; } }; type stuff[9u]; void bar(); void foo() { for(unsigned i = 0u; i < 9u; i++) { if(!stuff[i].a) { continue; } bar(); for(unsigned j = i + 1u; j < 9u; j++) { if(stuff[j].a && stuff[j].get_b()) { return; } } } } $ g++-4.8.0-pre9999 -Warray-bounds -O3 -c test.cpp test.cpp: In function ‘void foo()’: test.cpp:22:17: warning: array subscript is above array bounds [-Warray-bounds] if(stuff[j].a && stuff[j].get_b()) { ^ I appreciate static analyzers as much as everyone, but having false positives in the normal warnings (especially ones enabled at -Wall) can be annoying. GCC was build from git master just now: $ g++-4.8.0-pre9999 -v Using built-in specs. COLLECT_GCC=g++-4.8.0-pre9999 COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-pc-linux-gnu/4.8.0-pre9999/lto-wrapper Target: x86_64-pc-linux-gnu Configured with: /var/tmp/portage/sys-devel/gcc-4.8.0_pre9999/work/gcc-4.8.0-9999/configure --prefix=/usr --bindir=/usr/x86_64-pc-linux-gnu/gcc-bin/4.8.0-pre9999 --includedir=/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.0-pre9999/include --datadir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.8.0-pre9999 --mandir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.8.0-pre9999/man --infodir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.8.0-pre9999/info --with-gxx-include-dir=/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.0-pre9999/include/g++-v4 --host=x86_64-pc-linux-gnu --build=x86_64-pc-linux-gnu --disable-altivec --disable-fixed-point --with-ppl --with-cloog --disable-ppl-version-check --with-cloog-include=/usr/include/cloog-ppl --enable-lto --enable-nls --without-included-gettext --with-system-zlib --enable-obsolete --disable-werror --enable-secureplt --enable-multilib --with-multilib-list=m32,m64 --enable-libmudflap --disable-libssp --enable-libgomp --with-python-dir=/share/gcc-data/x86_64-pc-linux-gnu/4.8.0-pre9999/python --enable-checking=release --disable-libgcj --enable-libstdcxx-time --enable-languages=c,c++,fortran --enable-shared --enable-threads=posix --enable-__cxa_atexit --enable-clocale=gnu --enable-targets=all --with-bugurl=http://bugs.gentoo.org/ --with-pkgversion='Gentoo 4.8.0_pre9999' Thread model: posix gcc version 4.8.0-pre9999 20130210 (experimental) commit bc85f3af1b43674782c9b5bb2240117f293b5530 (Gentoo 4.8.0_pre9999)
The same code and command-line arguments do not produce a warning in gcc 4.7.2, 4.6.3, 4.5.4 and clang 3.2 as well as clang's static analyzer.
The problem is a missing VRP. Basically ivopts changes: if (j_10 != 9) Which works into: j_10 = ivtmp.12_56; if (ivtmp.12_56 != 9) goto <bb 7>; else goto <bb 6>; Which does not work as VRP cannot figure out j_10 will never be 9. I have some patches to VRP which improves this but I don't remember if it fixes this case where there is an assignment which is used later on.
I will have a look.
(In reply to comment #2) > The problem is a missing VRP. Basically ivopts changes: > if (j_10 != 9) > > Which works into: > > j_10 = ivtmp.12_56; > if (ivtmp.12_56 != 9) > goto <bb 7>; > else > goto <bb 6>; > > > Which does not work as VRP cannot figure out j_10 will never be 9. > I have some patches to VRP which improves this but I don't remember if it fixes > this case where there is an assignment which is used later on. A similar case was PR55079 which was j_10 = ivtmp.12_56 + 1; if (ivtmp.12_56 == 5) ... I handled already. Extending this to copies should be easy. If I do that it still doesn't work. That's because we warn for stuff[j_15] and j_15 is [9, 16] (we completely peel the loop). The access is guarded with <bb 30>: j_55 = ivtmp.12_56 + 8; j_72 = ivtmp.12_56 + 8; if (j_72 != 9) goto <bb 31>; else goto <bb 3>; <bb 31>: # j_15 = PHI <j_55(30)> _12 = stuff[j_15].a; if (_12 != 0) but j_72 is [9, 16] as well and ivtmp.12_56: [1, 9]. Improving VRP to see that j_55 is != 9 in bb31 will only lead to [10, 16] which is also out-of-bounds. It might very well be that folding the < test to != in VRP1 causes most of the issues. Indeed -fdisable-tree-vrp1 "fixes" the testcase. We should probably delay that optimization to VRP2 only, thus don't do Folding statement: if (i_1 <= 8) Simplified relational if (i_1 <= 8) into if (i_1 != 9) (simplify_cond_using_ranges).
One of the reasons this all happens is of course that after complete unrolling we miss a pass that does full redundancy removal and const/copy propagation. For the latter we abuse VRP (but cripple it), for the former we have DOM, but that is scheduled after VRP. I wonder if we should simply move VRP after DOM. Like with Index: gcc/passes.c =================================================================== --- gcc/passes.c (revision 195938) +++ gcc/passes.c (working copy) @@ -1488,7 +1488,6 @@ init_optimization_passes (void) NEXT_PASS (pass_lower_vector_ssa); NEXT_PASS (pass_cse_reciprocals); NEXT_PASS (pass_reassoc); - NEXT_PASS (pass_vrp); NEXT_PASS (pass_strength_reduction); NEXT_PASS (pass_dominator); /* The only const/copy propagation opportunities left after @@ -1497,6 +1496,7 @@ init_optimization_passes (void) only examines PHIs to discover const/copy propagation opportunities. */ NEXT_PASS (pass_phi_only_cprop); + NEXT_PASS (pass_vrp); NEXT_PASS (pass_cd_dce); NEXT_PASS (pass_tracer); as DOM also performs constant/copy propagation. That doesn't fix the warning but makes the IL that we feed into VRP2 much more suitable to its working. A patch to disable the < -> != transform fixes this bug and I am going to test that.
Author: rguenth Date: Mon Feb 11 13:33:19 2013 New Revision: 195940 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=195940 Log: 2013-02-11 Richard Biener <rguenther@suse.de> PR tree-optimization/56273 * tree-vrp.c (simplify_cond_using_ranges): Disable for the first VRP run. (check_array_ref): Fix missing newline in dumps. (search_for_addr_array): Likewise. * g++.dg/warn/Warray-bounds-6.C: New testcase. * gcc.dg/tree-ssa/pr21559.c: Adjust. * gcc.dg/tree-ssa/vrp17.c: Likewise. * gcc.dg/tree-ssa/vrp18.c: Likewise. * gcc.dg/tree-ssa/vrp23.c: Likewise. * gcc.dg/tree-ssa/vrp24.c: Likewise. Added: trunk/gcc/testsuite/g++.dg/warn/Warray-bounds-6.C Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/testsuite/gcc.dg/tree-ssa/pr21559.c trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp17.c trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp18.c trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp23.c trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c trunk/gcc/tree-vrp.c
Fixed.
Author: rguenth Date: Mon Feb 11 15:08:51 2013 New Revision: 195942 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=195942 Log: 2013-02-11 Richard Biener <rguenther@suse.de> PR tree-optimization/56273 * gcc.dg/tree-ssa/vrp17.c: Disable tail-merging. Modified: trunk/gcc/testsuite/ChangeLog trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp17.c
I am just rebuilding (Updated to revision 195983.) and noticed /home/data/newsoft/gcc-build/./gcc/xgcc -B/home/data/newsoft/gcc-build/./gcc/ -B/afs/cern.ch/user/i/innocent/w2/x86_64-unknown-linux-gnu/bin/ -B/afs/cern.ch/user/i/innocent/w2/x86_64-unknown-linux-gnu/lib/ -isystem /afs/cern.ch/user/i/innocent/w2/x86_64-unknown-linux-gnu/include -isystem /afs/cern.ch/user/i/innocent/w2/x86_64-unknown-linux-gnu/sys-include -g -O2 -ftree-vectorize -fPIC -O2 -g -O2 -ftree-vectorize -fPIC -DIN_GCC -W -Wall -Wno-narrowing -Wwrite-strings -Wcast-qual -Wstrict-prototypes -Wmissing-prototypes -Wold-style-definition -isystem ./include -I. -I. -I../.././gcc -I../../../gcc-trunk/libgcc -I../../../gcc-trunk/libgcc/. -I../../../gcc-trunk/libgcc/../gcc -I../../../gcc-trunk/libgcc/../include -I../../../gcc-trunk/libgcc/config/libbid -DENABLE_DECIMAL_BID_FORMAT -g0 -finhibit-size-directive -fno-inline -fno-exceptions -fno-zero-initialized-in-bss -fno-toplevel-reorder -fno-tree-vectorize -fno-stack-protector -I. -I. -I../.././gcc -I../../../gcc-trunk/libgcc -I../../../gcc-trunk/libgcc/. -I../../../gcc-trunk/libgcc/../gcc -I../../../gcc-trunk/libgcc/../include -I../../../gcc-trunk/libgcc/config/libbid -DENABLE_DECIMAL_BID_FORMAT -o crtend.o -MT crtend.o -MD -MP -MF crtend.dep -fno-omit-frame-pointer -fno-asynchronous-unwind-tables -c ../../../gcc-trunk/libgcc/crtstuff.c -DCRT_END ../../../gcc-trunk/libgcc/crtstuff.c: In function 'frame_dummy': ../../../gcc-trunk/libgcc/crtstuff.c:463:19: warning: array subscript is above array bounds [-Warray-bounds] if (__JCR_LIST__[0]) is this real or bogus?
(In reply to comment #9) > ../../../gcc-trunk/libgcc/crtstuff.c: In function 'frame_dummy': > ../../../gcc-trunk/libgcc/crtstuff.c:463:19: warning: array subscript is above > array bounds [-Warray-bounds] > if (__JCR_LIST__[0]) > > is this real or bogus? Real and bogus at the same time. STATIC void *__JCR_LIST__[] __attribute__ ((used, section(JCR_SECTION_NAME), aligned(sizeof(void*)))) = { }; So it has a size of 0 so reading 0 is above the array bounds but this is not normal code.
Author: rguenth Date: Thu Feb 21 10:52:39 2013 New Revision: 196200 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=196200 Log: 2013-02-21 Richard Biener <rguenther@suse.de> PR tree-optimization/56415 Revert 2013-02-11 Richard Biener <rguenther@suse.de> PR tree-optimization/56273 * tree-vrp.c (simplify_cond_using_ranges): Disable for the first VRP run. * g++.dg/warn/Warray-bounds-6.C: New testcase. * gcc.dg/tree-ssa/pr21559.c: Adjust. * gcc.dg/tree-ssa/vrp17.c: Likewise. * gcc.dg/tree-ssa/vrp18.c: Likewise. * gcc.dg/tree-ssa/vrp23.c: Likewise. * gcc.dg/tree-ssa/vrp24.c: Likewise. Removed: trunk/gcc/testsuite/g++.dg/warn/Warray-bounds-6.C Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/testsuite/gcc.dg/tree-ssa/pr21559.c trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp17.c trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp18.c trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp23.c trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c trunk/gcc/tree-vrp.c
Re-open, patch has been reverted.
I give up. We have to live with this false positive.
GCC 4.8.0 is being released, adjusting target milestone.
GCC 4.8.1 has been released.
GCC 4.8.2 has been released.
So what would be the problem with running DOM after full loop unrolling. We've known since the early 90s that CSE/cprop after loop unrolling was profitable at the RTL level. It wouldn't be a surprise at all that it'd be profitable at the tree level. And presumably if we're doing full loop unrolling, then we're typically an -O3 compile and the extra DOM or VRP pass would be justified from a compile-time standpoint.
GCC 4.8.3 is being released, adjusting target milestone.
GCC 4.8.4 has been released.
Fixed in GCC 5.
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
Mine for backporting.
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
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