From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 59120 invoked by alias); 13 Jul 2016 20:07:17 -0000 Mailing-List: contact java-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: java-patches-owner@gcc.gnu.org Received: (qmail 59088 invoked by uid 89); 13 Jul 2016 20:07:16 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.7 required=5.0 tests=BAYES_40,RP_MATCHES_RCVD,SPF_HELO_PASS,UNSUBSCRIBE_BODY autolearn=no version=3.3.2 spammy=HTo:U*roger, spending, belief, unlikely X-Spam-User: qpsmtpd, 2 recipients X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 13 Jul 2016 20:07:06 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id E3A634754AA; Wed, 13 Jul 2016 20:07:04 +0000 (UTC) Received: from localhost.localdomain (ovpn-116-70.phx2.redhat.com [10.3.116.70]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u6DK73Wt011275; Wed, 13 Jul 2016 16:07:04 -0400 Subject: Re: [JAVA PATCH] Enable more array bounds check elimination To: "roger@nextmovesoftware.com" , java-patches@gcc.gnu.org, gcc-patches@gcc.gnu.org References: <4F362C11-3DAA-4A9A-AEAB-089C20B3590C@nextmovesoftware.com> From: Jeff Law Message-ID: Date: Wed, 13 Jul 2016 20:07:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.1.1 MIME-Version: 1.0 In-Reply-To: <4F362C11-3DAA-4A9A-AEAB-089C20B3590C@nextmovesoftware.com> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-SW-Source: 2016-q3/txt/msg00004.txt.bz2 On 02/22/2016 11:10 AM, roger@nextmovesoftware.com wrote: > > It has been a while since my last contribution. The following patch allows GCC's optimizers > to more aggressively eliminate and optimize java array bounds checks. The results are > quite impressive, for example producing a 26% performance improvement on the sieve.java > benchmark given at http://keithlea.com/javabench/ on x86_64-pc-linux-gnu, reducing the > runtime for 1 million iterations from 31.5 seconds on trunk, to 25.0s with this patch, in fact > eliminating all array bounds checks. This is close to the 22.3s of an equivalent C/C++ > implementation, and significantly closes the gap to Java HotSpot(TM) JIT at 23.0 seconds. > > The approach is to provide sufficient information in the gimple generated by the gcj front-end > to allow the optimizers to do their thing. For array allocations of constant length, I propose > generating an additional (cheap) write to the array length field returned from _Jv_NewPrimArray, > which is then sufficient to allow this value to propagate throughout the optimizers. > > This is probably best explained by a simple example. Consider the array initializer below: Thanks. The example helped a lot. At a very high level, you should be aware of a general belief that GCJ's life is limited. There's been various calls to deprecate it. So spending a lot of time optimizing GCJ's output may not be the best use of your skills :-) > > With the patch below, we now generate the much more informative .004t.gimple for this: > > D.926 = _Jv_NewPrimArray (&_Jv_intClass, 3); > D.926->length = 3; Essentially you're just storing back into the result the length that we'd passed to the allocator. Cute. Good to see that all the work we've done to propagate the RHS of that kind of statement into uses has paid off. Presumably there's no reasonable way this could fail (like you're getting objects from a readonly part of memory), or the result gets used in some other thread which changes its size prior to the re-storing of the initial size? > > > Achieving this result required two minor tweaks. The first is to allow the array length constant > to reach the newarray call, by allowing constants to remain on the quickstack. This allows the > call to _Jv_NewPrimArray to have a constant integer argument instead of the opaque #slot#0#0. > Then in the code that constructs the call to _Jv_NewPrimArray we wrap it in a COMPOUND_EXPR > allowing us to insert the superfluous, but helpful, write to the length field. > > Whilst working on this improvement I also noticed that the array bounds checks we were > initially generating could also be improved. Currently, an array bound check in 004t.gimple > looks like: > > D.925 = MEM[(struct int[] *)_ref_1_4.6].length; > D.926 = (unsigned int) D.925; > if (_slot_2_5.9 >= D.926) goto ; else goto ; > : > _Jv_ThrowBadArrayIndex (_slot_2_5.8); > if (0 != 0) goto ; else goto ; > : > iftmp.7 = 1; > goto ; > : > iftmp.7 = 0; > : > > Notice the unnecessary "0 != 0" and the dead assignments to iftmp.7 (which is unused). FWIW, we're generally moving away from optimization in the language front-ends -- in particular folding, which you introduce in this patch on the array index. Given the trajectory of GCJ I'm not going to worry about it though. > > With the patch below, we now not only avoid this conditional but also use __builtin_expect > to inform the compiler that throwing an BadArrayIndex exception is typically unlikely. i.e. Sounds like a good thing as well. > > D.930 = MEM[(struct int[] *)_ref_1_4.4].length; > D.931 = D.930 <= 1; > D.932 = __builtin_expect (D.931, 0); > if (D.932 != 0) goto ; else goto ; > : > _Jv_ThrowBadArrayIndex (0); > : > > > The following patch has been tested on x86_64-pc-linux-gnu with a full make bootstrap > and make check, with no new failures/regressions. > > Please let me know what you think (for stage 1 once it reopens)? > > Roger > -- > Roger Sayle, Ph.D. > CEO and founder > NextMove Software Limited > Registered in England No. 07588305 > Registered Office: Innovation Centre (Unit 23), Cambridge Science Park, Cambridge CB4 0EY > > 2016-02-21 Roger Sayle > > * expr.c (push_value): Only call flush_quick_stack for non-constant > arguments. > (build_java_throw_out_of_bounds_exception): No longer wrap calls > to _Jv_ThowBadArrayIndex in a COMPOUND_EXPR as no longer needed. > (java_check_reference): Annotate COND_EXPR with __builtin_expect > to indicate that calling _Jv_ThrowNullPointerException is unlikely. > (build_java_arrayaccess): Construct an unlikely COND_EXPR instead > of a TRUTH_ANDIF_EXPR in a COMPOUND_EXPR. Only generate array > index MULT_EXPR when size_exp is not unity. > (build_array_length_annotation): When optimizing, generate a write > to the allocated array's length field to expose constant lengths > to GCC's optimizers. > (build_newarray): Call new build_array_length_annotation. > (build_anewarray): Likewise. Looks generally OK. There's a whitespace nit in the call to build3 in build_java_arrayaccess (missing space between the function name and open paren). I think this is OK for trunk after fixing the whitespace nit. jeff