[Bug java/21855] New: array bounds checking elimination

[Bug java/21855] New: array bounds checking elimination

[tromey at gcc dot gnu dot org]

public class q
{
  public static void main(String[] args)
  {
    for (int i = 0; i < args.length; ++i)
      System.out.println(args[i]);
  }
}

Right now you will get an unnecessary array bounds check at 'args[i]'.
BTW we implement this check with an unsigned comparison to also weed
out negative indices.

Also, an array's size is fixed at its creation.  We ought to be
able to constant propagate in code like this:

   int[] array = new int[256];
   for (int i = 0; i < array.length; ++i) { ... }

... but afaik there is no way for the front end of the value of
'array.length'

-- 
           Summary: array bounds checking elimination
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: java
        AssignedTo: dnovillo at redhat dot com
        ReportedBy: tromey at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org,java-prs at gcc dot gnu
                    dot org


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

[Bug tree-optimization/21855] array bounds checking elimination

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-06-01 20:31 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
          Component|java                        |tree-optimization
     Ever Confirmed|                            |1
           Keywords|                            |alias, missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2005-06-01 20:31:28
               date|                            |


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

[Bug tree-optimization/21855] array bounds checking elimination

[dnovillo at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|dnovillo at redhat dot com  |dnovillo at gcc dot gnu dot
                   |                            |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/21855] array bounds checking elimination

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-06-03 14:34 -------

Aliasing is getting in the way of range propagation here.  We don't realize that
args.length does not change during the loop, which means that we don't eliminate
the redundant load and fail to see the equivalence between the ranges.

Analysis from an IRC discussion:

<dnovillo> tromey: so, this is how we get ourselves tied up in a knot.  This is
the IL inside the loop body (21855):
<dnovillo> <L0>:;
<dnovillo>   D.671_6 = args_5->length;
<dnovillo>   if (i_2 >= D.671_6) goto <L10>; else goto <L1>;
<dnovillo>   [ ... ]
<dnovillo>   i.4_13 = (unsigned int) i_12;
<dnovillo>   D.680_14 = args_5->length;
<dnovillo>   D.681_15 = (unsigned int) D.680_14;
<dnovillo>   if (i.4_13 < D.681_15) goto <L6>; else goto <L4>;
<dnovillo> <L4>:;
<dnovillo>   D.682_27 = _Jv_ThrowBadArrayIndex (i_12);
<dnovillo> the first if() controls the iteration of the loop.
<dnovillo> the second if () is the redundancy we want to remove.
<dnovillo> when we get to this point, i_12 has the range we want, namely [-INF,
D.671_6 - 1].
<dnovillo> Two things go wrong:
<dnovillo> 1- The cast to unsigned int is an euphemism for ABS_EXPR here.  VRP
doesn't see that and sets i.4_13's range to VARYING.  That's trivial to fix.
<dnovillo> 2- We load from 'args_5->length' inside the loop even though the
memory has not changed.  This is the aliasing problem.  If we realized that
args_5->length doesn't change, FRE would've removed the redundant load and the
inner if
<dnovillo> would look like: 'if (i.4_13 < D.671_6)'
<dnovillo> which we would immediately toss away
<DannyB> dnovillo: my proposal to solve #2 is to have multiple name tags per
pointer (one for each offset that is accessed off that pointer), so that we can
say that args_5->length only is modified by args_5->length
<DannyB> (or whatever else happens to alias that field)
<dnovillo> DannyB: not making args point-to call-clobbered vars would suffice here.
<dnovillo> DannyB: there are System. calls in the loop.
<DannyB> Isn't args an incoming pointer?
<dnovillo> nope.
<dnovillo> DannyB: bah. yes.

-- 


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

[Bug tree-optimization/21855] array bounds checking elimination

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-06-04 17:00 -------
*** Bug 18178 has been marked as a duplicate of this bug. ***

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


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