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
Fri Feb 14 11:10:00 PST 2014
Hi Kris,
Changes are good.
Next comment does not describe the following optimization correctly:
+ // Integer expressions which perform bitwise and can be proven to
+ // be less than or equal (unsigned) to either operand, as long as the
+ // compared operand is non-negative.
originally it was for "(x & m) <= m, if and only if (m >= 0)".
Thanks,
Vladimir
On 2/13/14 7:57 PM, Krystal Mok 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
> <mailto: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 <mailto: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>
> <mailto: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
> <https://bugs.openjdk.java.net/browse/JDK-8003585>
> Webrev:
> http://cr.openjdk.java.net/~__kmo/8003585/webrev.00/
> <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>
> <mailto: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
> <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>
> <mailto: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>
>
> <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>>
> <mailto:vladimir.kozlov@
> <mailto:vladimir.kozlov@>__orac__le.com <http://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>>
>
>
>
> <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>__>__>
> <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
> <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>>
>
>
> <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>>>
> <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
> <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>>
>
>
>
> <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