Request for Reviews (S): JDK-8003585 strength reduce or eliminate range checks for power-of-two sized arrays (Was: Re: A simple optimization proposal)
Krystal Mok
rednaxelafx at gmail.com
Thu Feb 13 19:57:28 PST 2014
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> 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> 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>> 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
>>>> <mailto: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 <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>
>>>>
>>>> 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>>> 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>>
>>>> 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>__>__>> 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>>
>>>>
>>>> -- 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>>>__> 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>>
>>>>
>>>> Regards,
>>>> Martin.
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140213/2e59a2dc/attachment-0001.html
More information about the hotspot-compiler-dev
mailing list