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

Vladimir Kozlov vladimir.kozlov at oracle.com
Fri Feb 14 11:48:35 PST 2014

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

More information about the hotspot-compiler-dev mailing list