[Bug tree-optimization/65258] Wrong array bounds warning

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65258

--- Comment #5 from Richard Biener  ---
Author: rguenth
Date: Thu Dec 14 15:08:09 2017
New Revision: 255641

URL: https://gcc.gnu.org/viewcvs?rev=255641=gcc=rev
Log:
2017-12-14  Richard Biener  

PR tree-optimization/65258
* gcc.dg/Warray-bounds-23.c: New testcase.

Added:
trunk/gcc/testsuite/gcc.dg/Warray-bounds-23.c
Modified:
trunk/gcc/testsuite/ChangeLog

[Bug tree-optimization/65258] Wrong array bounds warning

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65258

Richard Biener  changed:

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
  Known to work||7.1.0
 Resolution|--- |FIXED

--- Comment #4 from Richard Biener  ---
Fixed in GCC 7+.

[Bug tree-optimization/65258] Wrong array bounds warning

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65258

--- Comment #3 from Richard Biener rguenth at gcc dot gnu.org ---
Created attachment 34921
  -- https://gcc.gnu.org/bugzilla/attachment.cgi?id=34921action=edit
untested patch

Patch to add additional asserts and to better handle UNDEFINED in propagation.

[Bug tree-optimization/65258] Wrong array bounds warning

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65258

--- Comment #2 from Richard Biener rguenth at gcc dot gnu.org ---
There are of course two issues here - one VRP not optimizing away the dead code
and unrolling creating the dead code in the first place (thus number of
iteration
analysis being not very precise).

Number of iteration analysis has a hard time exercising SCEV here as that
cannot
handle division (generally such IVs are not affine, in this case the evolution
of j/8 is not affine in the j loop).

Now for the VRP issue it is forwprop that replaces the sequence of i-- with
i = j/8 - 1, i = j/8 - 2, ... thereby making VRPs life hard with

  bb 3:
  i_9 = j_3 / 8;
  i_26 = i_9 + 4294967295;
  if (i_9 != 0)
goto bb 4;
  else
goto bb 14;

  bb 4:
  a[i_26] = 0;
  i_30 = i_9 + 4294967294;
  if (i_26 != 0)
goto bb 5;
  else
goto bb 14;

  bb 5:
  a[i_30] = 0;
  i_34 = i_9 + 4294967293;
  if (i_30 != 0)
goto bb 6;
  else
goto bb 14;

where the assertion on i_26 != 0 doesn't help it improving the range
for i_34 (which is based on i_9 again).

Disabling forwprop2 fixes the warning and makes VRP1 do its job.  It is
match.pd:491 that does the transform.

Of course I can write the problematic code in plain C as well so VRP should
better deal with it somehow.

We can easily do

  i_38 = i_53 + 4294967292;
  if (i_34 != 0)
goto bb 7;
  else
goto bb 14;

  bb 7:
  i_56 = ASSERT_EXPR i_53, i_53 != 3;
  a[i_38] = 0;
  i_42 = i_56 + 4294967291;
  if (i_38 != 0)
goto bb 8;
  else 
goto bb 14;

  bb 8: 
  i_57 = ASSERT_EXPR i_56, i_56 != 4;
  a[i_42] = 0;

but then we'd still need an assert for i_42 as well which is quite backward.

In fact the way VRP works makes this quite hard to do.  For a real
sophisticated VRP we'd walk the full dominator tree dominating each
predicate to compute value-ranges for SSA names dominated by those predicates
(but that's quadratic).

That said - with the above we are down to a single warning (but the code is
not removed).  We are not able to simplify the last branch to false and
the branch after gets UNDEFINED into the comparison so we can fold either
way (we could put builtin_unreachable before that branch...).

So - not sure if improving to

t.c: In function 'main':
t.c:8:3: warning: array subscript is above array bounds [-Warray-bounds]
  a[i] = 0;
   ^

is worth it.

[Bug tree-optimization/65258] Wrong array bounds warning

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65258

Richard Biener rguenth at gcc dot gnu.org changed:

   What|Removed |Added

   Keywords||diagnostic,
   ||missed-optimization
 Status|UNCONFIRMED |ASSIGNED
   Last reconfirmed||2015-03-02
  Component|c   |tree-optimization
   Assignee|unassigned at gcc dot gnu.org  |rguenth at gcc dot 
gnu.org
 Ever confirmed|0   |1
  Known to fail||4.8.3, 4.9.2, 5.0

--- Comment #1 from Richard Biener rguenth at gcc dot gnu.org ---
Early unrolling peels the a[i] = 0 loop 10 times.  VRP where we perform the
array bound warning still isn't able to prove that the last iterations are
not executed.  So we end up with

  bb 3:
  # j_12 = PHI j_3(7), j_13(9)
  i_9 = j_12  3;
  i_25 = i_9 + 4294967295;
  a[i_25] = 0;
  i_29 = i_9 + 4294967294;
  a[i_29] = 0;
  i_33 = i_9 + 4294967293;
  if (i_29 != 0)
goto bb 4;
  else
goto bb 6;

  bb 4:
  a[i_33] = 0;
  i_37 = i_9 + 4294967292;
  if (i_33 != 0)
goto bb 5;
  else
goto bb 6;

  bb 5:
  a[i_37] = 0;
  i_41 = i_9 + 4294967291;
  a[i_41] = 0;
  i_45 = i_9 + 4294967290;
  a[i_45] = 0;
...

I believe that's also partly because we have propagated the increments
to be based on the initial value and thus we don't get any additional
asserts registered after the preceeding checks for != 0.

Let me see if I can do anything about this.