Request for Reviews (S): JDK-8003585 strength reduce or eliminate range checks for power-of-two sized arrays (Was: Re: A simple optimization proposal)
Krystal Mok
rednaxelafx at gmail.com
Fri Feb 14 16:06:44 PST 2014
Hi Vladimir,
On Fri, Feb 14, 2014 at 3:27 PM, Vladimir Kozlov <vladimir.kozlov at oracle.com
> wrote:
> Changes are fine now.
>
> I am mostly concern about correctness of optimization and not that range
> check is folded. But any test is good so, please, add it.
>
Sure, I'll do that in the weekend.
> For foo*() method you can also compare returned value with value from
> array's element it should read.
>
Will do.
Thanks,
Kris
>
> Thanks,
> Vladimir
>
>
> On 2/14/14 2:47 PM, Krystal Mok wrote:
>
>> Hi Vladimir,
>>
>> Thanks for catching it. Another one of the left overs. But it's
>> interesting that it's only missing a chance to do the transformation
>> earlier; the expected optimizations were still performed by C2 in a
>> later phase even when I got that line wrong...so I didn't notice I
>> missed a place.
>>
>> Webrev updated in place again.
>>
>> The test that I used locally to verify the generated code patterns was:
>>
>> import java.util.*;
>>
>> public class TestArrayRangeCheck {
>> private static Object foo1(Object[] a, int x) throws Exception {
>> if (a.length == 0) throw new Exception();
>> return a[x & (a.length - 1)];
>> }
>>
>> private static Object foo2(Object[] a, int x) throws Exception {
>> a[1] = a[2];
>> return a[(a.length - 1) & x];
>> }
>>
>> private static Object foo3(Object[] a, int x) throws Exception {
>> if (a.length != 0) {
>> return a[x & (a.length - 1)];
>> }
>> return null;
>> }
>>
>> private static Object foo4(Object[] a, int x) throws Exception {
>> if (a.length > 0) {
>> return a[x & (a.length - 1)];
>> }
>> return null;
>> }
>> public static void main(String[] args) throws Exception {
>> foo1(a, 6);
>> foo1(a, 6);
>> foo2(a, 6);
>> foo2(a, 6);
>> foo3(a, 6);
>> foo3(a, 6);
>> foo4(a, 6);
>> foo4(a, 6);
>> HashMap<String, Integer> map = new HashMap<>();
>> String[] strs = new String[] {
>> "alpha", "beta", "charlie", "delta", "echo", "foxtrot", "golf",
>> "helios"
>> };
>> for (String s : strs) {
>> map.put(s, s.length());
>> }
>> for (int i = 0; i < 100; i++) {
>> int index = i % strs.length;
>> String key = strs[index];
>> int len = map.get(key);
>> if (len != key.length()) throw new Exception("unexpected
>> HashMap.getNode");
>> }
>>
>> System.in.read();
>> }
>> }
>>
>> The "foo" methods were for manual inspection of the generated code, and
>> the big loop in main() was to verify HashMap.getNode() still runs
>> correctly after compilation.
>>
>> The command to run the test was:
>>
>> java -XX:CompileCommand="compileonly java/util/HashMap get*"
>> -XX:CompileCommand="dontinline java/util/HashMap getNode"
>> -XX:CompileCommand="compileonly TestArrayRangeCheck foo*"
>> -XX:-TieredCompilation -XX:CICompilerCount=1 -XX:CompileThreshold=6
>> -XX:PrintIdealGraphLevel=4 -XX:PrintIdealGraphFile=ideal_hash.xml
>> -XX:+PrintCompilation -XX:+PrintAssembly TestArrayRangeCheck
>>
>> If that's the kind of test that you're looking for, then I can
>> rename/refactor the code a little bit and fit it into HotSpot's unit test.
>>
>> Thanks,
>> Kris
>>
>>
>>
>> On Fri, Feb 14, 2014 at 11:59 AM, Vladimir Kozlov
>> <vladimir.kozlov at oracle.com <mailto:vladimir.kozlov at oracle.com>> wrote:
>>
>> I found a problem:
>>
>> 1231 Node* ncmp = r->Opcode() == Op_LoadRange
>>
>> should be
>>
>> 1231 Node* ncmp = cmp2->Opcode() == Op_LoadRange
>>
>> because r->Opcode() == Op_AddI
>>
>> Kris, can you also add a test to verify correctness of these
>> transformations?
>>
>> Thanks,
>> Vlaidmir
>>
>>
>> On 2/14/14 11:48 AM, Vladimir Kozlov wrote:
>>
>> I assigned it to Nils, he will sponsor these changes.
>> We need to do more testing than just JPRT before the push.
>>
>> Thanks,
>> Vladimir
>>
>> On 2/14/14 11:16 AM, Krystal Mok wrote:
>>
>> Hi Vladimir,
>>
>> Thank you for your reviews, Vladimir.
>>
>> I've removed the bogus comment and updated the webrev in
>> place:
>> http://cr.openjdk.java.net/~__kmo/8003585/webrev.02/
>>
>> <http://cr.openjdk.java.net/~kmo/8003585/webrev.02/>
>>
>> Could someone on the compiler team run JPRT tests and push
>> for me?
>>
>> Thanks,
>> Kris
>>
>> On Fri, Feb 14, 2014 at 11:10 AM, Vladimir Kozlov
>> <vladimir.kozlov at oracle.com
>> <mailto:vladimir.kozlov at oracle.com>
>> <mailto:vladimir.kozlov at __oracle.com
>>
>> <mailto:vladimir.kozlov at oracle.com>>> wrote:
>>
>> Hi Kris,
>>
>> Changes are good.
>>
>> Next comment does not describe the following
>> optimization correctly:
>>
>> + // Integer expressions which perform bitwise and can
>> be proven to
>> + // be less than or equal (unsigned) to either
>> operand, as long
>> as the
>> + // compared operand is non-negative.
>>
>> originally it was for "(x & m) <= m, if and only if (m
>> >= 0)".
>>
>> Thanks,
>> Vladimir
>>
>>
>> On 2/13/14 7:57 PM, Krystal Mok wrote:
>>
>> Hi all,
>>
>> I've updated the patch again,
>> Webrev:
>> http://cr.openjdk.java.net/~____kmo/8003585/webrev.02/
>> <http://cr.openjdk.java.net/~__kmo/8003585/webrev.02/>
>>
>>
>> <http://cr.openjdk.java.net/~__kmo/8003585/webrev.02/
>> <http://cr.openjdk.java.net/~kmo/8003585/webrev.02/>>
>>
>> This version slightly differs from the original
>> equivalence
>> patterns as
>> stated in the bug report, in that it doesn't
>> transform the
>> following:
>> (x & array.length) < array.length
>> to:
>> array.length != 0
>> and instead transforms it to:
>> array.length u> 0
>> which are semantically the same.
>>
>> This is done to better align with the code pattern
>> that C2
>> generates for
>> array range checks, so that the logic in
>> IfNode::Ideal() can
>> better
>> remove redundant range checks.
>>
>> Also, I've added one more pattern matching to
>> transform:
>> array.length > 0
>> to:
>> array.length u> 0
>> (the actually code implements it inverted)
>> This is safe because array lengths are always >= 0,
>> while
>> changing the
>> form makes them more likely to get optimized by
>> IfNode::Ideal()
>> later.
>>
>> With this patch, C2 can now elide redundant range
>> checks in the
>> following two cases:
>>
>> Case 1:
>> array[1] = array[2]; // ensures array.length > 2
>> Object o = array[x & (array.length - 1)];
>>
>> Case 2:
>> if (array.length > 0) { // this is a signed
>> comparison
>> Object o = array[x & (array.length - 1)];
>> }
>>
>> I've tested the patch to compile
>> java.util.HashMap.getNode(), and
>> confirmed that redundant array bounds checks are
>> elided (matches
>> Case 2
>> above).
>>
>> Thanks,
>> Kris
>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140214/0280e201/attachment-0001.html
More information about the hotspot-compiler-dev
mailing list