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

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

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |RESOLVED
         Resolution|                            |INVALID

--- Comment #13 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-01-10 15:42:47 UTC ---
We can't optimize this because System.out.println can change args[].  Thus
the testcase is too simple to be useful (and no, we are not treating
program arguments special - I doubt that would be useful, nor would it be
easily possible).

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

[aph at gcc dot gnu.org]

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

Andrew Haley <aph at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |WAITING
         Resolution|INVALID                     |

--- Comment #14 from Andrew Haley <aph at gcc dot gnu.org> 2012-01-10 15:52:07 UTC ---
(In reply to comment #13)
> We can't optimize this because System.out.println can change args[].

That's the whole point: System.out.println cannot change args[], which is a
java array, and the length of a Java array is constant.  It is not an invalid
test case.

[Bug java/21855] array bounds checking elimination

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW
          Component|tree-optimization           |java

--- Comment #15 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-01-10 16:20:13 UTC ---
(In reply to comment #14)
> (In reply to comment #13)
> > We can't optimize this because System.out.println can change args[].
> 
> That's the whole point: System.out.println cannot change args[], which is a
> java array, and the length of a Java array is constant.  It is not an invalid
> test case.

I suppose

  public static void main(String[] args)

is passing args by value (but the implementation detail uses reference
passing for efficiency?).  In this case the Java frontend should do
like the C++ frontend and tell this to the middle-end by properly
marking args as 1) DECL_BY_REFERENCE, 2) use a TYPE_RESTRICT qualified
pointer for the reference.  Then we would optimize this case.

Java frontend issue.

[Bug java/21855] array bounds checking elimination

[aph at gcc dot gnu.org]

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

--- Comment #16 from Andrew Haley <aph at gcc dot gnu.org> 2012-01-10 16:26:51 UTC ---
(In reply to comment #15)
> (In reply to comment #14)
> > (In reply to comment #13)
> > > We can't optimize this because System.out.println can change args[].
> > 
> > That's the whole point: System.out.println cannot change args[], which is a
> > java array, and the length of a Java array is constant.  It is not an invalid
> > test case.
> 
> I suppose
> 
>   public static void main(String[] args)
> 
> is passing args by value (but the implementation detail uses reference
> passing for efficiency?).

args is indeed a reference to a Java array.  The length field of a Java
array is immutable.  The elements of an array are not immutable.

> In this case the Java frontend should do
> like the C++ frontend and tell this to the middle-end by properly
> marking args as 1) DECL_BY_REFERENCE, 2) use a TYPE_RESTRICT qualified
> pointer for the reference.  Then we would optimize this case.

If we could mark the length field as immutable that would fix it.  Is there any
way to do that?

[Bug java/21855] array bounds checking elimination

[rguenth at gcc dot gnu.org]

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

--- Comment #17 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-01-10 16:30:30 UTC ---
(In reply to comment #16)
> (In reply to comment #15)
> > (In reply to comment #14)
> > > (In reply to comment #13)
> > > > We can't optimize this because System.out.println can change args[].
> > > 
> > > That's the whole point: System.out.println cannot change args[], which is a
> > > java array, and the length of a Java array is constant.  It is not an invalid
> > > test case.
> > 
> > I suppose
> > 
> >   public static void main(String[] args)
> > 
> > is passing args by value (but the implementation detail uses reference
> > passing for efficiency?).
> 
> args is indeed a reference to a Java array.  The length field of a Java
> array is immutable.  The elements of an array are not immutable.

You mean that System.out.println could change the elements of the array
(well, it doesn't, but theoretically it could)?

> > In this case the Java frontend should do
> > like the C++ frontend and tell this to the middle-end by properly
> > marking args as 1) DECL_BY_REFERENCE, 2) use a TYPE_RESTRICT qualified
> > pointer for the reference.  Then we would optimize this case.
> 
> If we could mark the length field as immutable that would fix it.  Is there any
> way to do that?

No.  What you can do is, via the method I outlined, tell GCC that
args is to be treated similar to a local automatic variable - thus
it cannot be refered to from other functions (unless you pass them
its address of course).

[Bug java/21855] array bounds checking elimination

[rguenth at gcc dot gnu.org]

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

--- Comment #18 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-01-10 16:35:46 UTC ---
(In reply to comment #17)
> (In reply to comment #16)
> > (In reply to comment #15)
> > > (In reply to comment #14)
> > > > (In reply to comment #13)
> > > > > We can't optimize this because System.out.println can change args[].
> > > > 
> > > > That's the whole point: System.out.println cannot change args[], which is a
> > > > java array, and the length of a Java array is constant.  It is not an invalid
> > > > test case.
> > > 
> > > I suppose
> > > 
> > >   public static void main(String[] args)
> > > 
> > > is passing args by value (but the implementation detail uses reference
> > > passing for efficiency?).
> > 
> > args is indeed a reference to a Java array.  The length field of a Java
> > array is immutable.  The elements of an array are not immutable.
> 
> You mean that System.out.println could change the elements of the array
> (well, it doesn't, but theoretically it could)?
> 
> > > In this case the Java frontend should do
> > > like the C++ frontend and tell this to the middle-end by properly
> > > marking args as 1) DECL_BY_REFERENCE, 2) use a TYPE_RESTRICT qualified
> > > pointer for the reference.  Then we would optimize this case.
> > 
> > If we could mark the length field as immutable that would fix it.  Is there any
> > way to do that?
> 
> No.  What you can do is, via the method I outlined, tell GCC that
> args is to be treated similar to a local automatic variable - thus
> it cannot be refered to from other functions (unless you pass them
> its address of course).

Thus, similar to the C++ case with

struct Array { int length; void data[]; }

void foo (Array args)
{
 ...
}

foo cannot change the callers args.length (only its own copy) but it
can change the callers args.data[] contents.  If the C++ frontend
decides to pass args by reference then it sets DECL_BY_REFERENCE
and uses a TYPE_RESTRICT qualified pointer.  This way the optimization
will be the same as if it was passed "really" by value.

Not sure if the Java situation is similar enough.

[Bug java/21855] array bounds checking elimination

[aph at gcc dot gnu.org]

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

--- Comment #19 from Andrew Haley <aph at gcc dot gnu.org> 2012-01-10 16:44:16 UTC ---
(In reply to comment #17)
> (In reply to comment #16)
> > (In reply to comment #15)
> > > (In reply to comment #14)
> > > > (In reply to comment #13)
> > > > > We can't optimize this because System.out.println can change args[].
> > > > 
> > > > That's the whole point: System.out.println cannot change args[], which is a
> > > > java array, and the length of a Java array is constant.  It is not an invalid
> > > > test case.
> > > 
> > > I suppose
> > > 
> > >   public static void main(String[] args)
> > > 
> > > is passing args by value (but the implementation detail uses reference
> > > passing for efficiency?).
> > 
> > args is indeed a reference to a Java array.  The length field of a Java
> > array is immutable.  The elements of an array are not immutable.
> 
> You mean that System.out.println could change the elements of the array
> (well, it doesn't, but theoretically it could)?

In theory yes, it could.

> > > In this case the Java frontend should do
> > > like the C++ frontend and tell this to the middle-end by properly
> > > marking args as 1) DECL_BY_REFERENCE, 2) use a TYPE_RESTRICT qualified
> > > pointer for the reference.  Then we would optimize this case.
> > 
> > If we could mark the length field as immutable that would fix it.  Is there any
> > way to do that?
> 
> No.  What you can do is, via the method I outlined, tell GCC that
> args is to be treated similar to a local automatic variable - thus
> it cannot be refered to from other functions (unless you pass them
> its address of course).

But that doesn't help.  args *can* potentially be referred to by other
functions.  The special property we need to make use of its that fact that once
an array is created, its length can never change.

[Bug java/21855] array bounds checking elimination

[rguenth at gcc dot gnu.org]

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

--- Comment #21 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-01-10 16:57:36 UTC ---
The Java frontend could handle this by performing loads of the length field
via a SAVE_EXPR and sharing this across a function.  That way CSE would
happen automagically.

[Bug java/21855] array bounds checking elimination

[rguenth at gcc dot gnu.org]

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

--- Comment #20 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-01-10 16:55:52 UTC ---
(In reply to comment #19)
>
> > No.  What you can do is, via the method I outlined, tell GCC that
> > args is to be treated similar to a local automatic variable - thus
> > it cannot be refered to from other functions (unless you pass them
> > its address of course).
> 
> But that doesn't help.  args *can* potentially be referred to by other
> functions.  The special property we need to make use of its that fact that once
> an array is created, its length can never change.

That is something we cannot express at the moment, and I think it would
be hard to implement reliably (thinking of the RTX_UNCHANGING saga - we
do have to exclude the stmts that initialize the length field).

[Bug java/21855] array bounds checking elimination

[aph at gcc dot gnu.org]

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

--- Comment #22 from Andrew Haley <aph at gcc dot gnu.org> 2012-01-10 17:08:30 UTC ---
(In reply to comment #21)
> The Java frontend could handle this by performing loads of the length field
> via a SAVE_EXPR and sharing this across a function.  That way CSE would
> happen automagically.

Now that's a nice idea.  

In this specific case it should be easy, because array.length is used in the
control expression for the loop.  So. we can create the SAVE_EXPR when the loop
is initialized.

The problem with doing this in general is that we don't have a CFG, so we don't
always know when to create that SAVE_EXPR.  If we can find an initial use of an
array that dominates all other uses we can create the SAVE_EXPR at that point.

[Bug java/21855] array bounds checking elimination

[tromey at gcc dot gnu.org]

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

--- Comment #23 from Tom Tromey <tromey at gcc dot gnu.org> 2012-01-10 17:17:50 UTC ---
I thought I wrote a pass to do this optimization, but I can't find it now.
Anyway I think that would be the simplest approach by far.

[Bug java/21855] array bounds checking elimination

[tromey at gcc dot gnu.org]

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

--- Comment #24 from Tom Tromey <tromey at gcc dot gnu.org> 2012-01-10 17:21:02 UTC ---
I found my code and it turns out I never finished it.
(I did write a java-specific devirtualization pass.)
Here is an introductory comment that explains my plans:

/* This pass implements a few simple gcj-specific optimizations
   related to handling of invariants.  In Java, certain fields of
   some objects are known to be invariant after the object has been
   created.  For instance, the vtable pointer of an object cannot
   change; neither can the length of an array.

   Also, this pass knows that 'new Type[n]' sets the length of an
   array to 'n'.

   Ideally GCC would recognize these cases and optimize for us.
   However, currently there is no way to express these properties to
   the optimizers.
 */

[Bug java/21855] array bounds checking elimination

[aph at gcc dot gnu.org]

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

Andrew Haley <aph at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |WONTFIX

--- Comment #25 from Andrew Haley <aph at gcc dot gnu.org> ---
We'll never do this.

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

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2009-04-03 12:07 -------
Huh.  C testcase please?  I think this may be fixed now.


-- 


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]

------- Comment #5 from pinskia at gcc dot gnu dot org  2009-04-03 19:18 -------
There are multiple of issues here, first we have an issue that the java
front-end is not telling the middle-end that args.length cannot be changed
after a new has happened (an aliasing issue).  And then we had some branch
issues but those might have been fixed already.


-- 


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

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

[tromey at gcc dot gnu dot org]

------- Comment #6 from tromey at gcc dot gnu dot org  2009-04-08 16:37 -------
How would the FE indicate that the length field is immutable?


-- 


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

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

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2009-04-08 20:33 -------
You can't.


-- 


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

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

[aph at gcc dot gnu dot org]

------- Comment #8 from aph at gcc dot gnu dot org  2009-04-23 16:15 -------
2 reasons:

1.  Habit.
2.  The original test case is written in Java: no unsigned types!


-- 

aph at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|39870                       |


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

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

[paolo dot carlini at oracle dot com]

------- Comment #9 from paolo dot carlini at oracle dot com  2009-04-23 16:17 -------
Ah! Now however, I **must** know why Java doesn't have unsigned types!


-- 


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

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

[aph at gcc dot gnu dot org]

------- Comment #10 from aph at gcc dot gnu dot org  2009-04-23 16:23 -------
Officially, java doesn't have unsigned types for economy: believe it or not,
Java was once intended to be a small language.  However, there are not many
unused bytecodes left, and a full set of signed instructions would use them
all. 


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #11 from paolo dot carlini at oracle dot com  2009-04-23 16:26 -------
Interesting, thanks Andrew.


-- 


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

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

[steven at gcc dot gnu dot org]

------- Comment #12 from steven at gcc dot gnu dot org  2010-07-15 22:43 -------
I would be surprised if this is not fixed now. Can someone with Java-fu check?


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |WAITING


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

[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