From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <java-patches-return-20935-listarch-java-patches=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 32282 invoked by alias); 22 Feb 2016 23:02:36 -0000
Mailing-List: contact java-patches-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <java-patches.gcc.gnu.org>
List-Subscribe: <mailto:java-patches-subscribe@gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/java-patches/>
List-Post: <mailto:java-patches@gcc.gnu.org>
List-Help: <mailto:java-patches-help@gcc.gnu.org>, <http://gcc.gnu.org/ml/#faqs>
Sender: java-patches-owner@gcc.gnu.org
Received: (qmail 32268 invoked by uid 89); 22 Feb 2016 23:02:36 -0000
Authentication-Results: sourceware.org; auth=none
X-Virus-Found: No
X-Spam-SWARE-Status: No, score=2.3 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=recover, inspired, gcj, convey
X-HELO: server.nextmovesoftware.com
Received: from server.nextmovesoftware.com (HELO server.nextmovesoftware.com) (162.254.253.69) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Mon, 22 Feb 2016 23:02:35 +0000
Received: from host109-147-72-25.range109-147.btcentralplus.com ([109.147.72.25]:61756 helo=macbookpro.home)	by server.nextmovesoftware.com with esmtpsa (TLSv1:AES128-SHA:128)	(Exim 4.85)	(envelope-from <roger@nextmovesoftware.com>)	id 1aXzUt-0002Zv-4Z; Mon, 22 Feb 2016 18:02:31 -0500
From: Roger Sayle <roger@nextmovesoftware.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Subject: Re: [JAVA PATCH] Enable more array bounds check elimination
Date: Mon, 22 Feb 2016 23:02:00 -0000
Message-Id: <74FFBDDA-D906-470D-A7BA-559AAD71E76A@nextmovesoftware.com>
Cc: java-patches@gcc.gnu.org
To: Andrew Haley <aph@redhat.com>
Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\))
X-Get-Message-Sender-Via: server.nextmovesoftware.com: authenticated_id: roger@nextmovesoftware.com
X-SW-Source: 2016-q1/txt/msg00019.txt.bz2


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
--