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
Wed Feb 12 16:50:53 PST 2014
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/20140212/f15b05e0/attachment.html
More information about the hotspot-compiler-dev
mailing list