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

[Azeem Jiva]

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