Re: [JAVA PATCH] Enable more array bounds check elimination

[Roger Sayle <roger@nextmovesoftware.com>]

Hi Andrew,

On 02/22/2016, Andrew Haley wrote:
> I take it that this only really works with new arrays?

Alas yes, this patch only addresses the case that the array allocation is
visible (in the same method after inlining) as the array bounds check,
which fortunately is fairly frequent, especially for initializers.

I'd assumed that the middle-end optimizers were already doing a reasonable
job for the harder cases, but inspired by your question above, I've done some
more investigating and noticed other areas where improvements are possible.

For example

	int len = arr.length;
	for (int i=0; i<arr.length; i++)
	  arr[i] = arr[i]+1;

eliminates all bounds checks when arr is double[], but disappointingly
not when arr is int[].  I suspect that the middle-end optimizers assume
the worst, perhaps that arr.data[-1] potentially aliases arr.length, or
similar.  Obviously, java doesn't allow negative array indices, but I
suspect the gcj front-end's gimple doesn't manage to convey this.

I'm personally impressed that GCC recognizes that although

	for (int i=0; i<3; i++)
	  ... arr[i] ...

typically needs to perform index checking on every iteration,
that the reversed loop

	for (int i=2; i>=0; i--)
	  ... arr[i] ...

only needs to perform array bounds checking on the first iteration,
i.e. optimizes away the later checks [in unrolled loops].  This might
seem obvious, but there's a lot of analysis required to recover this
from java's bytecodes.


Please point me towards any relevant postings (of yours) on the subject of
gcj bounds check elimination, as I'd love to catch up on current thinking.

Cheers,

Roger
--