[Bug tree-optimization/55079] New: [4.8 regeression] false positive -Warray-bounds

[Bug tree-optimization/55079] New: [4.8 regeression] false positive -Warray-bounds

[dimhen at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

             Bug #: 55079
           Summary: [4.8 regeression] false positive -Warray-bounds
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: dimhen@gmail.com


$ 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?

[Bug tree-optimization/55079] [4.8 regeression] false positive -Warray-bounds

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-10-26
                 CC|                            |hubicka at gcc dot gnu.org
   Target Milestone|---                         |4.8.0
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> 2012-10-26 10:08:44 UTC ---
It's because of unrolling.

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |nately@t-online.de

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> 2012-10-30 09:33:03 UTC ---
*** Bug 55133 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> 2012-10-30 09:32:45 UTC ---
*** Bug 55085 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds

[hubicka at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #4 from Jan Hubicka <hubicka at gcc dot gnu.org> 2012-11-02 16:35:01 UTC ---
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

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds

[hubicka at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #5 from Jan Hubicka <hubicka at gcc dot gnu.org> 2012-11-02 16:46:54 UTC ---
The patch cures a lot of false positives seen at -O3 bootstrap. The testcase
here is not cured, I am looking into it.

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds

[hubicka at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #6 from Jan Hubicka <hubicka at gcc dot gnu.org> 2012-11-02 18:44:37 UTC ---
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 :(

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds

[hubicka at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #7 from Jan Hubicka <hubicka at gcc dot gnu.org> 2012-11-02 20:51:31 UTC ---
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.

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[hubicka at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

Jan Hubicka <hubicka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.8 regression] false      |[4.8 regression] false
                   |positive -Warray-bounds     |positive -Warray-bounds
                   |                            |(also seen at -O3
                   |                            |bootstrap)

--- Comment #8 from Jan Hubicka <hubicka at gcc dot gnu.org> 2012-11-14 19:31:16 UTC ---
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.

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[hubicka at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #9 from Jan Hubicka <hubicka at gcc dot gnu.org> 2012-11-15 01:01:30 UTC ---
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

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-07 12:54:35 UTC ---
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).

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-10 13:23:17 UTC ---
Created attachment 28911
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28911
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.

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-10 13:50:15 UTC ---
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.

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[rguenth at gcc dot gnu.org]

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.

>             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

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[hubicka at ucw dot cz]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #14 from Jan Hubicka <hubicka at ucw dot cz> 2012-12-10 16:26:40 UTC ---
> 
> 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

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-11 10:06:20 UTC ---
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

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-11 10:07:58 UTC ---
All fixable testcases from this bug fixed.

[Bug tree-optimization/55079] [4.8 regression] false positive -Warray-bounds (also seen at -O3 bootstrap)

[schwab at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55079

--- Comment #17 from Andreas Schwab <schwab at gcc dot gnu.org> 2012-12-12 09:32:47 UTC ---
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