[Bug middle-end/31058] New: array overflow warning due to incorrect loop unrolling

[Bug middle-end/31058] New: array overflow warning due to incorrect loop unrolling

[mueller at gcc dot gnu dot org]

building this testcase with -O2 -march=athlon -Wall -fprefetch-loop-arrays
gives:

warning: array subscript is above array bounds
[...]

which, according to VRP, seems to be valid. 

testcase is:

=== Cut ===
struct real_value
{
  unsigned int cl:2;
  unsigned int decimal:1;
  unsigned long sig[5];
};
unsigned int uexp;

static void
clear_significand_below (struct real_value *r, unsigned int n)
{
  int i, w = n / 32;
  for (i = 0; i < w; ++i)
    r->sig[i] = 0;
}
void
do_fix_trunc (struct real_value *r)
{
  if (uexp < 160)
    clear_significand_below (r, 160 - uexp);
}
=== Cut ===


-- 
           Summary: array overflow warning due to incorrect loop unrolling
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: mueller at gcc dot gnu dot org


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

[Bug middle-end/31058] array overflow warning due to incorrect loop unrolling

[mueller at gcc dot gnu dot org]

------- Comment #1 from mueller at gcc dot gnu dot org  2007-03-06 15:22 -------
after prefetch-loop-arrays run, vrp2 looks like this: 

<L81>:;
  D.1885_87 = &r_4(D)->sig[i_13];
  D.1886_88 = D.1885_87 + 160B;
  __builtin_prefetch (D.1886_88, 1);
  r_4(D)->sig[i_13] = 0;
  i_8 = i_13 + 1;
  i_26 = i_8;
  r_4(D)->sig[i_26] = 0;
  i_28 = i_26 + 1;
  i_30 = i_28;
  r_4(D)->sig[i_30] = 0;
  i_32 = i_30 + 1;
  i_34 = i_32;
  r_4(D)->sig[i_34] = 0;
  i_36 = i_34 + 1;
  i_38 = i_36;
  r_4(D)->sig[i_38] = 0;
  i_40 = i_38 + 1;
  i_42 = i_40;
  r_4(D)->sig[i_42] = 0;
  i_44 = i_42 + 1;
  i_46 = i_44;
  r_4(D)->sig[i_46] = 0;
  i_48 = i_46 + 1;
  i_50 = i_48;
  r_4(D)->sig[i_50] = 0;
  i_52 = i_50 + 1;
  i_54 = i_52;
  r_4(D)->sig[i_54] = 0;
  i_56 = i_54 + 1;
  i_58 = i_56;
  r_4(D)->sig[i_58] = 0;
  i_60 = i_58 + 1;
  i_62 = i_60;
  r_4(D)->sig[i_62] = 0;
  i_64 = i_62 + 1;
  i_66 = i_64;
  r_4(D)->sig[i_66] = 0;
  i_68 = i_66 + 1;
  i_70 = i_68;
  r_4(D)->sig[i_70] = 0;
  i_72 = i_70 + 1;
  i_74 = i_72;
  r_4(D)->sig[i_74] = 0;
  i_76 = i_74 + 1;
  i_78 = i_76;
  r_4(D)->sig[i_78] = 0;
[...]

and so on. since it definitely writes more than 5 ints, I don't see how it
should *not* overflow the array. 


-- 


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

[Bug middle-end/31058] array overflow warning due to incorrect loop unrolling

[rakdver at gcc dot gnu dot org]

------- Comment #2 from rakdver at gcc dot gnu dot org  2007-03-06 15:31 -------
(In reply to comment #1)
> and so on. since it definitely writes more than 5 ints, I don't see how it
> should *not* overflow the array. 

since the body of the loop is never entered.


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unreachable code

[rakdver at gcc dot gnu dot org]

------- Comment #3 from rakdver at gcc dot gnu dot org  2007-03-07 09:15 -------
The same problem appears in the following testcase.

int a[100];

void test (int real_length_of_a)
{
  int x = 110;

  if (x < real_length_of_a)
    a[x]++;
}


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|array overflow warning due  |bogus array overflow
                   |to incorrect loop unrolling |warnings in unreachable code


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

[Bug middle-end/31058] bogus array overflow warnings in unreachable code

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2007-03-07 09:33 -------
But real length of a cannot be greater than 100.  I guess VRP could be improved
to derive a value range for x in this case ...


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unreachable code

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #5 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2007-03-07 09:38 -------
Subject: Re:  bogus array overflow warnings in unreachable code

> But real length of a cannot be greater than 100.  I guess VRP could be improved
> to derive a value range for x in this case ...

I think that in VRP, x is already eliminated, i.e., the code looks like

if (real_length > 110)
  a[110]++;


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unreachable code

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2007-03-07 09:39 -------
Uh, yes.  So let's teach CCP to convert a[110]++; to builtin_trap then ;)


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unrolled loops

[mueller at gcc dot gnu dot org]

------- Comment #7 from mueller at gcc dot gnu dot org  2007-03-07 10:59 -------
I don't think this is the same testcase. you will get any warning in this case,
because the compiler cannot determine that it is supposed to be dead code. 


-- 

mueller at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|bogus array overflow        |bogus array overflow
                   |warnings in unreachable code|warnings in unrolled loops


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

[Bug middle-end/31058] bogus array overflow warnings in unrolled loops

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #8 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2007-03-07 11:02 -------
Subject: Re:  bogus array overflow warnings in unrolled loops

> I don't think this is the same testcase. you will get any warning in this case,
> because the compiler cannot determine that it is supposed to be dead code. 

it is exactly the same in the unrolled loop case -- compiler
cannot determine that the unrolled loop body is a dead code.


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unrolled loops

[mueller at gcc dot gnu dot org]

------- Comment #9 from mueller at gcc dot gnu dot org  2007-03-07 11:34 -------
well, the unrolled body is generated code, it could set TREE_NO_WARNING (for
example). or it could avoid unrolling if its not a flex array. 


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unrolled loops

[pinskia at gcc dot gnu dot org]

------- Comment #10 from pinskia at gcc dot gnu dot org  2007-03-07 20:37 -------
> well, the unrolled body is generated code, it could set TREE_NO_WARNING (for
> example). or it could avoid unrolling if its not a flex array. 

Except it cannot tell sorry, this is exactly the same issue as the bogus
warning for the function given in comment #3.  To really tell array overflows,
you really need to emitt bounds checking.

I think this warning should never have ended in VRP, as shown you can get many
many bogus warnings.  So really I think it might be best to remove the warning
and have the C/C++ front-end emits bounds checking when ARRAY_REF and the size
is known (for -fbounds-checking).


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unrolled loops

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2007-03-07 20:54 -------
Sorry, but I don't agree a bit with you.  It doesn't have as much false
positives
as other warnings in -Wall.  And I think a warning for the testcase in comment
#3
is ok -- the code looks very suspicious.  Also the testcase in comment #3 has
"unreachable" code produced by the programmer, while for the testcase in
comment
#1 the compiler inserts the unreachable code (and it can either avoid it in
this
particular case or set TREE_NO_WARNING on the array accesses it produces).


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unrolled loops

[pinskia at gcc dot gnu dot org]

------- Comment #12 from pinskia at gcc dot gnu dot org  2007-03-07 21:21 -------
(In reply to comment #11)
> Sorry, but I don't agree a bit with you.  It doesn't have as much false
> positives
> as other warnings in -Wall.

Actually if you read the documention for -Wall, it says enable warnings that
are easy to avoid.
"This enables all the warnings about constructions that some users consider
questionable, and that are easy to avoid (or modify to prevent the warning),
even in conjunction with macros. "

So really this warning is not easy to avoid in the case of
-fprefetch-loop-arrays (or -funroll-loops if it comes and does (non complete)
unroll at the tree level).


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unrolled loops

[pinskia at gcc dot gnu dot org]

------- Comment #13 from pinskia at gcc dot gnu dot org  2007-03-07 21:22 -------
Actually comment #3 shows this warning is not easy to avoid at all and should
not be turned on with -Wall at all.

I still had allways said it should not be included in -Wall.


-- 


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

[Bug middle-end/31058] bogus array overflow warnings in unrolled loops

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2007-03-07 21:22 -------
This is why we have this bug -- because loop unrolling creates possibly
unreachable code with out-of-bounds array access.


-- 


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[pinskia at gcc dot gnu dot org]

------- Comment #15 from pinskia at gcc dot gnu dot org  2007-03-07 21:24 -------
(In reply to comment #14)
> This is why we have this bug -- because loop unrolling creates possibly
> unreachable code with out-of-bounds array access.
But the warning code is the real cause, sorry but there is no work around from
loop unrolling.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|bogus array overflow        |overflow warnings should not
                   |warnings in unrolled loops  |be enabled with -Wall


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[rguenth at gcc dot gnu dot org]

------- Comment #16 from rguenth at gcc dot gnu dot org  2007-03-07 21:25 -------
We might now be able to disable the warning in the second vrp pass -- Dirk, did
you try that after all the early optimizations we now got?


-- 


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[gdr at cs dot tamu dot edu]

------- Comment #17 from gdr at cs dot tamu dot edu  2007-03-07 21:35 -------
Subject: Re:  bogus array overflow warnings in unrolled loops

"rguenth at gcc dot gnu dot org" <gcc-bugzilla@gcc.gnu.org> writes:

| This is why we have this bug -- because loop unrolling creates possibly
| unreachable code with out-of-bounds array access.

While I don't think removing the warning from -Wall solves the
problem, I tend to agree with Andrew Pinski that it should not be
included there.

-- Gaby


-- 


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[mueller at gcc dot gnu dot org]

-- 

mueller at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-03-07 21:55:36
               date|                            |


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[mueller at gcc dot gnu dot org]

------- Comment #18 from mueller at gcc dot gnu dot org  2007-03-07 22:03 -------
IIRC there are some cases that are only caught in the 2nd vrp run. It is still
a possibility if this bug cannot be fixed otherwise. 

However, I don't see the issue with this testcase. 

a) its not a flex array
b) the unrolled loop produces out of bounds accesses
c) hence, the unrolled version cannot ever be used
d) it shouldn't be produced in the first place. 

we can turn this bug about a false positive warning into a code bloat
regression by removing the warning (or disabling it from -Wall). That doesn't
fix it though. 


-- 


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #19 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2007-03-07 22:17 -------
Subject: Re:  overflow warnings should not be enabled with -Wall

> IIRC there are some cases that are only caught in the 2nd vrp run. It is still
> a possibility if this bug cannot be fixed otherwise. 
> 
> However, I don't see the issue with this testcase. 
> 
> a) its not a flex array

well, it may be a flex array -- it is at the end of the structure.

> b) the unrolled loop produces out of bounds accesses
> c) hence, the unrolled version cannot ever be used

no, this cannot be derived.

> d) it shouldn't be produced in the first place. 

Well, yes, this is true.  It is quite unlikely that a programmer would
use length of 5 for a tail array, hence we should take this as a hint
and avoid prefetching the array.


-- 


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[manu at gcc dot gnu dot org]

------- Comment #20 from manu at gcc dot gnu dot org  2007-03-08 15:28 -------
I think the description doesn't match the real bug, as explained in comment #14
and #18. 

And comment #6 may have a wink but I think it summarises why the testcase in
comment #3 deserves a warning.

I have my own opinion about whether "out-of-bounds array access warnings should
not be enabled by -Wall" but I don't think this bug report is about that, so
those advocating the former should open a new bug report with testcases to
support their position and the description of this bug should be something
similar to "fprefetch-loop-arrays generates code known unreachable at compile
time".


-- 

manu at gcc dot gnu dot org changed:

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


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #21 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2007-03-08 15:43 -------
Subject: Re:  overflow warnings should not be enabled with -Wall

> I think the description doesn't match the real bug, as explained in comment #14
> and #18. 
> 
> And comment #6 may have a wink but I think it summarises why the testcase in
> comment #3 deserves a warning.
> 
> I have my own opinion about whether "out-of-bounds array access warnings should
> not be enabled by -Wall" but I don't think this bug report is about that, so
> those advocating the former should open a new bug report with testcases to
> support their position and the description of this bug should be something
> similar to "fprefetch-loop-arrays generates code known unreachable at compile
> time".

"suspected to be unreachable at compile time".  It would be valid for
the array to extend beyond the structure, hence the compiler cannot
prove that the unrolled loop body is really unreachable.


-- 


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[rguenth at gcc dot gnu dot org]

------- Comment #22 from rguenth at gcc dot gnu dot org  2007-03-08 16:38 -------
Note that one reason we do not optimize the dead code is the stupidity of VRP
dealing with the IL in the second pass.  While in the first pass VRP figures
out a range of [0,5] for w_6 in

<bb 2>:
  uexp.1_1 = uexp;
  if (uexp.1_1 <= 159) goto <L0>; else goto <L1>;

<L0>:;
  D.1770_3 = 160 - uexp.1_1;
  D.1778_5 = D.1770_3 >> 5;
  w_6 = (int) D.1778_5;

in the second VRP pass we get w_6 as varying...  Appearantly the difference
starts with the

   D.1778_5 = D.1770_3 >> 5;

statement where the first pass gets [0, 5] and the second [0, +INF].  It
looks like this is because the first pass sees

   D.1778_5 = D.1770_3 / 32;

instead.  It seems to be the VRP pass itself calling fold_stmt on the
division and producing the (unhandled) division.  Fixing that makes the
warning (and the dead code) go away.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c      (revision 122691)
--- gcc/tree-vrp.c      (working copy)
*************** extract_range_from_binary_expr (value_ra
*** 1568,1573 ****
--- 1568,1574 ----
        && code != CEIL_DIV_EXPR
        && code != EXACT_DIV_EXPR
        && code != ROUND_DIV_EXPR
+       && code != RSHIFT_EXPR
        && code != MIN_EXPR
        && code != MAX_EXPR
        && code != BIT_AND_EXPR
*************** extract_range_from_binary_expr (value_ra
*** 1735,1741 ****
           || code == FLOOR_DIV_EXPR
           || code == CEIL_DIV_EXPR
           || code == EXACT_DIV_EXPR
!          || code == ROUND_DIV_EXPR)
      {
        tree val[4];
        size_t i;
--- 1736,1743 ----
           || code == FLOOR_DIV_EXPR
           || code == CEIL_DIV_EXPR
           || code == EXACT_DIV_EXPR
!          || code == ROUND_DIV_EXPR
!          || code == RSHIFT_EXPR)
      {
        tree val[4];
        size_t i;


-- 


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[mueller at gcc dot gnu dot org]

------- Comment #23 from mueller at gcc dot gnu dot org  2007-03-08 21:32 -------
Great, this patch makes a -fprefetch-loop-arrays bootstrap succeed. I think
LSHIFT_EXPR should be handled similar. 


-- 


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[rguenth at gcc dot gnu dot org]

------- Comment #24 from rguenth at gcc dot gnu dot org  2007-03-09 12:29 -------
Subject: Bug 31058

Author: rguenth
Date: Fri Mar  9 12:29:09 2007
New Revision: 122748

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=122748
Log:
2007-03-09  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/30904
        PR middle-end/31058
        * tree-vrp.c (extract_range_from_binary_expr): Handle RSHIFT_EXPR
        the same way as *_DIV_EXPR.

        * gcc.dg/pr30904.c: Remove xfail.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/pr30904.c
    trunk/gcc/tree-vrp.c


-- 


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

[Bug middle-end/31058] overflow warnings should not be enabled with -Wall

[rguenth at gcc dot gnu dot org]

------- Comment #25 from rguenth at gcc dot gnu dot org  2007-03-09 12:30 -------
The original issue is fixed.  The rest belongs in a different bug.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |30904
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.3.0
Bug 31058 depends on bug 30904, which changed state.

Bug 30904 Summary: VRP does not track values of shifts and/or bitfields?
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30904

           What    |Old Value                   |New Value
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED

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