Request for Reviews (S): JDK-8003585 strength reduce or eliminate range checks for power-of-two sized arrays (Was: Re: A simple optimization proposal)

[Nils Eliasson]

Current change passes JPRT. Running bigapps and nightly code policy as well.

Will wait for tests and reviewer go-ahead before pushing.

//N

On 2014-02-14 20:48, 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/
>>
>> 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>> 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/>
>>
>>         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
>>