Request for Reviews (S): JDK-8003585 strength reduce or eliminate range checks for power-of-two sized arrays (Was: Re: A simple optimization proposal)
Martin Grajcar
maaartinus at gmail.com
Thu Feb 13 20:44:21 PST 2014
Hi Kris,
I like it. What about transforming also array.length != 0 into the unsigned
test?
Regards,
Martin.
On Fri, Feb 14, 2014 at 4:57 AM, Krystal Mok <rednaxelafx at gmail.com> 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>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/20140214/ccc93c48/attachment-0001.html
More information about the hotspot-compiler-dev
mailing list