$ cat tst.c int f(unsigned len, int buflen) { unsigned taillen; unsigned slen; unsigned i; int b[17]; /* needed <= 17 to trigger Warning */ int j = 0; /* needed to trigger Warning */ b[0] = 0; taillen= buflen & 7; /* taillen [0..7] */ if(taillen) { /* taillen [1..7] */ slen= 8 - taillen; /* slen [7..1] */ if (len<slen) /* needed to trigger Warning */ slen=len; /* slen' < slen */ for(i=0; i<slen; i++) { j = b[taillen]; /* taillen + slen = [1..7] + [7..1] = 8 */ taillen++; } } return j; } $ gcc -Warray-bounds -c -O3 tst.c tst.c: In function 'f': tst.c:17:9: warning: array subscript is above array bounds [-Warray-bounds] j = b[taillen]; /* taillen + slen = [1..7] + [7..1] = 8 */ ^ gcc version 4.8.0 20121026 (experimental) [trunk revision 192837] (GCC) - if i remove some code then warning disappeared - why '18' is safe array top-bound?
It's because of unrolling.
*** Bug 55085 has been marked as a duplicate of this bug. ***
*** Bug 55133 has been marked as a duplicate of this bug. ***
Author: hubicka Date: Fri Nov 2 16:34:52 2012 New Revision: 193098 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=193098 Log: PR middle-end/55079 * tree-ssa-loop-niter.c (number_of_iterations_exit): Update MAX field if NITER was folded to contant. (record_estimate): Sanity check. * tree-ssa-loop-ivcanon.c (remove_exits_and_undefined_stmts): New function. (remove_redundant_iv_test): New function. (loops_to_unloop, loops_to_unloop_nunroll): New static vars. (unloop_loops): Break out from ... (try_unroll_loop_completely): ... here; Pass in MAXITER; use remove_exits_and_undefined_stmts; do not unloop. (canonicalize_loop_induction_variables): Compute MAXITER; use remove_redundant_iv_test; remove loop_close_ssa_invalidated and irred_invalidated arguments. (canonicalize_induction_variables): Compute fresh bound estimates; unloop; walk from innermost. (tree_unroll_loops_completely): Likewise. * gcc.dg/tree-ssa/cunroll-10.c: New testcase. * gcc.dg/tree-ssa/cunroll-9.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/cunroll-10.c trunk/gcc/testsuite/gcc.dg/tree-ssa/cunroll-9.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-loop-ivcanon.c trunk/gcc/tree-ssa-loop-niter.c
The patch cures a lot of false positives seen at -O3 bootstrap. The testcase here is not cured, I am looking into it.
Hmm, it seems to be due to off-by-one bug in my patch Index: tree-ssa-loop-ivcanon.c =================================================================== --- tree-ssa-loop-ivcanon.c (revision 193098) +++ tree-ssa-loop-ivcanon.c (working copy) @@ -405,11 +405,11 @@ remove_exits_and_undefined_stmts (struct into unreachable (or trap when debugging experience is supposed to be good). */ if (!elt->is_exit - && elt->bound.ult (double_int::from_uhwi (npeeled))) + && elt->bound.ule (double_int::from_uhwi (npeeled))) { gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt); gimple stmt = gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0); gimple_set_location (stmt, gimple_location (elt->stmt)); gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); I however introduced it because w/o it we get bootstrap miscompare. Looks like I will need to debug it after all :(
Actually not, what happen here is that we unroll the loop 17 times based on the fact that the array access iterates from taillen to tailen+n_iterations and the array size is 17. Later in compilation we prove that tailen is actually non-zero by VRP and we work the hard way across the unrolled loop body to work out that the last access must be out of bounds. So this is not bug of unroller to not remove statement. Short of teaching SCEV about the value range of initial tailen, we really can't reduce number of iterations. We discussed it here http://gcc.gnu.org/ml/gcc-patches/2012-10/msg01103.html I do not think we really can solve these cases reliably short of silencing the warning on unrolled loop copies and other duplicated statements.
Hi, at -O3 bootstrap we have false positive on simplify-rtx.c ../../gcc/simplify-rtx.c: In function ‘rtx_def* simplify_plus_minus(rtx_code, machine_mode, rtx, rtx)’: ../../gcc/simplify-rtx.c:4285:63: warning: array subscript is below array bounds [-Warray-bounds] while (j-- && simplify_plus_minus_op_data_cmp (ops[j].op, save.op)); the siplified testcase is as follows: int a[8]; void test(unsigned int n) { unsigned int i; unsigned int j; if (n<8) for (j=0;j<n;j++) { i = j; do a[i+1]=a[i]; while (i--); } } here we unroll the inner do loop 7 times based on the array bounds derived from [i] access. Afterwards VRP proves that j is always at most 7 and thus the loop walks out of bounds. Here we may be able to determine that the loop accesses both i and i+1 and we could actually unroll only 6 times, but we handle each of array access independently.
This is reduced testcase from gcov.c int a[8]; int t (void) { int ix = 0; int k; int b = 0; int curr = 0; for (k = 0; k < 2; k++) { b = ix * 32; curr = a[ix++]; if (!(ix <= 8)) abort (); while (curr) { b = ix * 32; curr = a[ix++]; if (!(ix <= 8)) abort (); } } return curr + b; } jan@linux-e0ml:~/trunk/build/gcc> ./xgcc -B ./ -O2 -fprofile-use t.c -Warray-bounds -S -S -fdump-tree-cunroll-details -fdump-tree-all-details t.c: In function ‘t’: t.c:14:2: warning: incompatible implicit declaration of built-in function ‘abort’ [enabled by default] abort (); ^ t.c:25:1: note: file /home/jan/trunk/build/gcc/t.gcda not found, execution counts estimated } ^ t.c:19:15: warning: array subscript is above array bounds [-Warray-bounds] curr = a[ix++]; ^ t.c:19:15: warning: array subscript is above array bounds [-Warray-bounds] Obivously here unroller does not know that bv_ix is at least 1
I expect this to be a major nuisance on our users for 4.8. And I don't see a good way to solve this issue! For the testcase in comment#8 we warn during early VRP but not from late VRP. OTOH I'd rather disable the second VRPs array bound warnings ... What would be interesting to see is if there is a way for VRP to prove (after the unrolling happened) that the access is dead. For the testcase in comment#8 something magic happens for a[3] (no warning) vs. a[4] (warning). Maybe we should refrain from doing the speculative new complete unrolling during cunrolli? OTOH what happens in VRP for int a[4] case is that it estimates the number of iterations of the outer (not unrolled) loop to be 4, one too large: Analyzing # of iterations of loop 1 exit condition [0, + , 1] < n_8 bounds on difference of bases: 0 ... 4294967295 result: # of iterations n_8, bounded by 4294967295 Statement (exit)if (i_2 < n_8) is executed at most n_8 (bounded by 4294967295) + 1 times in loop 1. here # of iteration analysis does not take into account that n_8 is [0, 3] already. Of course there is no good way to feed it this information (we are currently iterating and not conservative!) without re-computing number of iterations and SCEV all the time (that was shot down to be very much too time consuming).
Created attachment 28911 [details] prototype patch The pattern we have is <bb 6>: _36 = i_33 + 1; _37 = a[i_33]; a[_36] = _37; i_39 = i_33 + 4294967295; if (i_33 != 0) goto <bb 7>; else goto <bb 11>; <bb 7>: _42 = i_39 + 1; _43 = a[i_39]; a[_42] = _43; and eventually adding an assert in bb7 that i_39 != 1 would help. But the only thing we try to add extra asserts for is stuff in the definition chain of comparison operands ... this OTOH is for stuff that uses comparison operands and live on the edge. Prototype patch attached, fixes comment#8 at least.
For the testcase in comment#1 we have Found new range for len_10: [1, 7] Visiting statement: len_17 = MIN_EXPR <len_10, len_11(D)>; Found new range for len_17: [0, +INF] which should have been [0, 7] I think. That fixes the testcase from comment#1.
(In reply to comment #9) > This is reduced testcase from gcov.c > int a[8]; > int > t (void) > { > int ix = 0; > int k; > int b = 0; > int curr = 0; > for (k = 0; k < 2; k++) > { > b = ix * 32; > curr = a[ix++]; > if (!(ix <= 8)) See below. > abort (); > > while (curr) > { > b = ix * 32; > curr = a[ix++]; > if (!(ix <= 8)) This is a test after the fact. For ix == 8 we will still enter the next loop iteration (GCC can't know anything about 'curr') and thus access a[8] which is out-of-bounds. Fixing the tests to test < 8 instead fixes the warnings. This testcase is invalid. > abort (); > } > } > return curr + b; > } > > jan@linux-e0ml:~/trunk/build/gcc> ./xgcc -B ./ -O2 -fprofile-use t.c > -Warray-bounds -S -S -fdump-tree-cunroll-details -fdump-tree-all-details > t.c: In function ‘t’: > t.c:14:2: warning: incompatible implicit declaration of built-in function > ‘abort’ [enabled by default] > abort (); > ^ > t.c:25:1: note: file /home/jan/trunk/build/gcc/t.gcda not found, execution > counts estimated > } > ^ > t.c:19:15: warning: array subscript is above array bounds [-Warray-bounds] > curr = a[ix++]; > ^ > t.c:19:15: warning: array subscript is above array bounds [-Warray-bounds] > > Obivously here unroller does not know that bv_ix is at least 1
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079 > > --- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-10 14:14:07 UTC --- > (In reply to comment #9) > > This is reduced testcase from gcov.c > > int a[8]; > > int > > t (void) > > { > > int ix = 0; > > int k; > > int b = 0; > > int curr = 0; > > for (k = 0; k < 2; k++) > > { > > b = ix * 32; > > curr = a[ix++]; > > if (!(ix <= 8)) > > See below. > > > abort (); > > > > while (curr) > > { > > b = ix * 32; > > curr = a[ix++]; > > if (!(ix <= 8)) > > This is a test after the fact. For ix == 8 we will still enter the > next loop iteration (GCC can't know anything about 'curr') and thus > access a[8] which is out-of-bounds. > > Fixing the tests to test < 8 instead fixes the warnings. > > This testcase is invalid. I fixed that in GCOV sources already, but it depends on the definition of invalidness. In general construct like ix <= some_constant may come from some unrelated stuff (macro expansion) and may be fully redundant in sane and valid program. In that case waring after unrolling some_constant times there will be out of bound access (without explicitely saying that unrolling is needed) is undesirable IMO. The loop has other exit that takes care of the proper bound. Honza
Author: rguenth Date: Tue Dec 11 10:06:15 2012 New Revision: 194388 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=194388 Log: 2012-12-11 Richard Biener <rguenther@suse.de> PR tree-optimization/55079 * tree-vrp.c (extract_range_from_binary_expr_1): Handle MAX/MIN_EXPR for more cases. (register_edge_assert_for_2): Register asserts for post-in/decrement tests. (check_array_ref): Dump what expression we emit array bound warnings for. (search_for_addr_array): Likewise. * gcc.dg/Warray-bounds-9.c: New testcase. * gcc.dg/Warray-bounds-10.c: Likewise. * gcc.dg/tree-ssa/ssa-pre-1.c: Adjust. Added: trunk/gcc/testsuite/gcc.dg/Warray-bounds-10.c trunk/gcc/testsuite/gcc.dg/Warray-bounds-9.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-vrp.c
All fixable testcases from this bug fixed.
Author: schwab Date: Wed Dec 12 09:32:40 2012 New Revision: 194437 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=194437 Log: PR tree-optimization/55079 * gcc.dg/tree-ssa/ssa-pre-1.c: Adjust. Modified: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-1.c