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)

Azeem Jiva azeem.jiva at oracle.com
Wed Feb 12 16:25:25 PST 2014

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> wrote:

Hi all,

Could I get a couple of reviews for this change, please? Bug: https://bugs.openjdk.java.net/browse/JDK-8003585 Webrev: 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> wrote: > I'm afraid, not all equivalences listed in > 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> 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 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>> 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> 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>>> 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> — 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>>> 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> Regards, Martin.

-------------- next part -------------- An HTML attachment was scrubbed... URL: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140212/7edbd7f1/attachment.html

More information about the hotspot-compiler-dev mailing list