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

[Vladimir Kozlov]

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
>