Request for Reviews (S): JDK-8003585 strength reduce or eliminate range checks for power-of-two sized arrays (Was: Re: A simple optimization proposal)
Vladimir Kozlov
vladimir.kozlov at oracle.com
Wed Feb 12 16:32:29 PST 2014
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.
>>
>>
>>
>>
>>
>
More information about the hotspot-compiler-dev
mailing list