(original) (raw)

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@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@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@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@gmail.com
<mailto:rednaxelafx@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@gmail.com
<mailto:maaartinus@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@oracle.com <mailto:vladimir.kozlov@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@oracle.com
<mailto:vladimir.kozlov@oracle.com>
<mailto:vladimir.kozlov@\_\_oracle.com

<mailto:vladimir.kozlov@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@oracle.com
<mailto:john.r.rose@oracle.com> <mailto:john.r.rose@oracle.com
<mailto:john.r.rose@oracle.com>\_\_>
<mailto:john.r.rose@oracle.com
<mailto:john.r.rose@oracle.com>

<mailto:john.r.rose@oracle.com
<mailto:john.r.rose@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@gmail.com <mailto:maaartinus@gmail.com>
<mailto:maaartinus@gmail.com <mailto:maaartinus@gmail.com>>
<mailto:maaartinus@gmail.com
<mailto:maaartinus@gmail.com>

<mailto:maaartinus@gmail.com
<mailto:maaartinus@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.