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:10:00 PST 2014

Hi Kris,

Changes are good.

Next comment does not describe the following optimization correctly:

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 On Wed, Feb 12, 2014 at 4:50 PM, Krystal Mok <rednaxelafx at gmail.com_ _<mailto:rednaxelafx at gmail.com>> wrote: Thanks for your reviews, Azeem and Vladimir. Updated webrev here: http://cr.openjdk.java.net/~kmo/8003585/webrev.01/ I removed the two signed variants, leaving only the two unsigned variants. As for testing, I'm not up to speed with JMH yet... Do you think adapting the JMH benchmarks found on the StackOverflow post will do? http://stackoverflow.com/questions/21702939/why-the-bounds-check-doesnt-get-eliminated Thanks, Kris

On Wed, Feb 12, 2014 at 4:32 PM, Vladimir Kozlov <vladimir.kozlov at oracle.com <mailto:vladimir.kozlov at oracle.com>> wrote: We need to assign 8003585 to someone in our group to sponsor these changes and do our internal testing. Second equivalence also does not hold with x = -1: (x & (m-1)) < m, if and only if (m > 0) because -3 < -2._ _Which leaves equivalences only for unsigned compares._ _Thanks,_ _Vladimir_ _On 2/12/14 4:25 PM, Azeem Jiva wrote:_ _It looks good to me (not a Reviewer) but I’d ask for some_ _testing to_ _make sure nothing got broken. How about a JMH micro_ _benchmark to test_ _the gains?_ _--_ _Azeem Jiva_ _@javawithjiva_ _On Feb 12, 2014, at 4:17 PM, Krystal Mok_ _<rednaxelafx at gmail.com <mailto:rednaxelafx at gmail.com> <mailto:rednaxelafx at gmail.com_ _<mailto:rednaxelafx at gmail.com>>> wrote:_ Hi all, Could I get a couple of reviews for this change, please? Bug: https://bugs.openjdk.java.net/_browse/JDK-8003585 <https://bugs.openjdk.java.net/browse/JDK-8003585> Webrev: http://cr.openjdk.java.net/~_kmo/8003585/webrev.00/ <http://cr.openjdk.java.net/~kmo/8003585/webrev.00/> Note 1: Cases 2 and 4 are handled by the same code in this change. Note 2: Martin's concerns seems to hold, so the patch will need to be changed to handle that: On Wed, Feb 12, 2014 at 3:45 PM, Martin Grajcar <maaartinus at gmail.com <mailto:maaartinus at gmail.com> <mailto:maaartinus at gmail.com_ _<mailto:maaartinus at gmail.com>>> wrote: > I'm afraid, not all equivalences listed in > https://bugs.openjdk.java.net/_browse/JDK-8003585 <https://bugs.openjdk.java.net/browse/JDK-8003585> > are right, namely the first one > > (x & m) <= m, if and only if (m >= 0) > > Using x = -1 reduces the LHS to m <= m._ _Description: (copied from the bug report)_ _Integer expressions which perform bitwise and can be_ _proven to be less_ _than or equal to either operand, as long as the compared_ _operand is_ _non-negative. In other words:_ _Case 1:_ _(x & m) <= m, if and only if (m >= 0) This means the left-hand test can be replaced by the simpler right-hand test. There are also off-by-one versions, such as: Case 2: (x & (m-1)) < m, if and only if (m > 0) There are also unsigned versions: Case 3: (x & m) u<= m, always_ _Case 4:_ _(x & (m-1)) u< m, if and only if (m > 0) The optimizer should recognize these patterns. They are common in implicitly generated range checks for power-of-two sized arrays: int hash = ...; int bucket = hash & (array.length-1); Entry e = array[bucket]; The range check is: (hash & (array.length-1)) u< array.length_ _This check can be strength reduced to:_ _array.length != 0_ _If the array is constant, or if user code has a_ _dominating check for_ _an empty array, this check will go away completely._ _Tests:_ _Ran some tests manually and checked that Case 1, 2 and 4_ _does get_ _pattern matched. Need someone from Oracle to run JPRT_ _and other tests_ _appropriate._ _Thanks,_ _Kris (OpenJDK username: kmo)_ _On Wed, Feb 12, 2014 at 3:33 PM, 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: Kris, Can you submit formal review request as changes for 8003585 with webrev on cr.openjdk? Note, you can't return return phase->intcon(1) from Ideal() because we need new node. Return ConINode::make(phase->C, 1) instead. Thanks, Vladimir On 2/12/14 3:05 PM, Krystal Mok wrote: Hi Vladimir, Thanks for looking at it. I added the other cases and added a missing condition check. The patch is updated in place: https://gist.github.com/__rednaxelafx/8964030 <https://gist.github.com/_rednaxelafx/8964030> <https://gist.github.com/_rednaxelafx/8964030_ _<https://gist.github.com/rednaxelafx/8964030>> Ran a few small cases on case 1 and 3 manually and the resulting IR graphs were right. I wasn't able to check the case 2 ("Change ((x & m) u<= m) to always true") though, I don't know_ _what Java code_ _could be_ _compiled into that pattern._ _Thanks,_ _Kris_ _On Wed, Feb 12, 2014 at 2:00 PM, 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>> _<mailto:vladimir.kozlov@_ _mailto:vladimir.kozlov@orac_le.com <http://oracle.com> <mailto:vladimir.kozlov at _oracle.com_ _<mailto:vladimir.kozlov at oracle.com>>>> wrote: Looks reasonable. Kris, you need also look for other patterns listed in JDK-8003585. Thanks, Vladimir On 2/12/14 12:39 PM, Krystal Mok wrote: Hi Martin and John, I did a quick-and-dirty patch and it seems to work: https://gist.github.com/___rednaxelafx/8964030 <https://gist.github.com/__rednaxelafx/8964030> <https://gist.github.com/__rednaxelafx/8964030_ _<https://gist.github.com/_rednaxelafx/8964030>>

<https://gist.github.com/__rednaxelafx/8964030_ _<https://gist.github.com/_rednaxelafx/8964030> <https://gist.github.com/_rednaxelafx/8964030_ _<https://gist.github.com/rednaxelafx/8964030>>> If it looks right then I'll refactor that code a little bit and send it in for official review. - Kris On Wed, Feb 12, 2014 at 11:17 AM, John Rose <john.r.rose at oracle.com_ _<mailto:john.r.rose at oracle.com> <mailto:john.r.rose at oracle.com_ _<mailto:john.r.rose at oracle.com>>_ <mailto:john.r.rose at oracle.com_ _<mailto:john.r.rose at oracle.com> <mailto:john.r.rose at oracle.com_ _<mailto:john.r.rose at oracle.com>>> <mailto:john.r.rose at oracle.com_ _<mailto:john.r.rose at oracle.com> <mailto:john.r.rose at oracle.com_ _<mailto:john.r.rose at oracle.com>>_ <mailto:john.r.rose at oracle.com_ _<mailto:john.r.rose at oracle.com> <mailto:john.r.rose at oracle.com_ _<mailto:john.r.rose at oracle.com>>>>> wrote:_ It's totally reasonable, and is already filed as an RFE (please comment on it!): https://bugs.openjdk.java.net/___browse/JDK-8003585 <https://bugs.openjdk.java.net/__browse/JDK-8003585> <https://bugs.openjdk.java._net/_browse/JDK-8003585_ _<https://bugs.openjdk.java.net/_browse/JDK-8003585>> <https://bugs.openjdk.java.__net/browse/JDK-8003585_ _<https://bugs.openjdk.java._net/browse/JDK-8003585_ _<https://bugs.openjdk.java.net/browse/JDK-8003585>>> — John On Feb 12, 2014, at 9:40 AM, Martin Grajcar <maaartinus at gmail.com_ _<mailto:maaartinus at gmail.com> <mailto:maaartinus at gmail.com <mailto:maaartinus at gmail.com>> <mailto:maaartinus at gmail.com_ _<mailto:maaartinus at gmail.com> <mailto:maaartinus at gmail.com <mailto:maaartinus at gmail.com>>> <mailto:maaartinus at gmail.com_ _<mailto:maaartinus at gmail.com> <mailto:maaartinus at gmail.com_ _<mailto:maaartinus at gmail.com>> <mailto:maaartinus at gmail.com_ _<mailto:maaartinus at gmail.com> <mailto:maaartinus at gmail.com_ _<mailto:maaartinus at gmail.com>>>>> wrote: Most hash tables are power-of-two sized so that they can use masking for the access. It looks like the bounds check doesn't get eliminated, although it could be. Based on the equivalence |a[x & (a.length - 1)]| throws if and only if |a.length == 0|, I'm proposing this simple algorithm: * For each array access, check if the index has been computed via a bitwise and. * If so, check if either of the operands was computed as length minus one. * If so, replace the bounds check by a zero-length check. This zero-length check can then be easily moved out of the loop by the existing optimizations. I hope I'm not talking non-sense. For more details see http://stackoverflow.com/___questions/21702939/why-the-___bounds-check-doesnt-get-___eliminated <http://stackoverflow.com/__questions/21702939/why-the-__bounds-check-doesnt-get-__eliminated> <http://stackoverflow.com/__questions/21702939/why-the-__bounds-check-doesnt-get-__eliminated_ _<http://stackoverflow.com/_questions/21702939/why-the-_bounds-check-doesnt-get-_eliminated>> <http://stackoverflow.com/__questions/21702939/why-the-__bounds-check-doesnt-get-__eliminated_ _<http://stackoverflow.com/_questions/21702939/why-the-_bounds-check-doesnt-get-_eliminated> <http://stackoverflow.com/_questions/21702939/why-the-_bounds-check-doesnt-get-_eliminated_ _<http://stackoverflow.com/questions/21702939/why-the-bounds-check-doesnt-get-eliminated>>> Regards, Martin.

More information about the hotspot-compiler-dev mailing list