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]

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/

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> 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/
>>
>> 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/05c6eb88/attachment.html