A simple optimization proposal

[Krystal Mok]

Hi Martin,

Thanks for your review!
Comments inline below:

On Thu, Feb 13, 2014 at 8:40 PM, Martin Grajcar <maaartinus at gmail.com>wrote:

> Hi Kris,
>
> some comments on
>
> http://cr.openjdk.java.net/~kmo/8003585/webrev.02/src/share/vm/opto/subnode.cpp.sdiff.html
>
> I could imagine adding cmp1->in(*1*) == cmp2 as an alternative at line
> 1217. While hardly anybody writes a.length & index, some previous
> transformation could rearrange the expression.
>
> Done. For commutative binary operations, C2 tends to put a constant
operand as the right operand, so that it's easier to pattern match and
constant fold. That's why most patterns in BoolNode::Ideal() don't need to
try commuting. But for the patterns in this bug, the operands to the "&"
aren't required to be constants, so you're right that I should add an
alternative here.

Same for the pattern that followed. I wouldn't want to try enumerate all
commuted patterns for that, but I'm going to at least cover (x & (m - 1)) <
m and ((m - 1) & x) < m.
(Note: (m - 1) won't need a commuted version because the constant operand
can be assumed to be on the right hand side.)


> The description at line 1221 mentions unsigned compare only while you're
> handling both. I'm unsure about the correctness in the signed case (but
> didn't check it). Some sort of proof would be nice, especially for extreme
> values.
>
> I've updated the comments but forgot to update the code to remove the
signed version. Vladimir already gave an example that when x == -1, the iff
relation doesn't hold.


> I like the idea at line 1237, though I don't exactly understand how it
> works. Is there a good description of all the nodes and all normalizations
> done?
>
> I don't know if there's any good description other than the code...
Anyway, the short answer is that C2 does array bounds check with a
well-known trick: instead of two comparisons:
 0 <= index && index < length
you can do a single unsigned comparison:
 index u< length
because length is known to be non-negative. If index were negative, viewing
it as an unsigned integer will make it greater than length.

You can find multiple sources that mention this trick, one of which is:
http://ssw.jku.at/Research/Papers/Wuerthinger07/Wuerthinger07.pdf
Page 126, in the paragraph right below Figure 1.

A part of IfNode::Ideal()'s logic pattern matches array range checks (in
IfNode::is_range_check()), and it optimizes consecutive range checks,
replacing them by the strongest check. It only expects the comparison to be
unsigned (CmpU). So, to make the most out of existing optimizations, I
opted to make this patch use (arraylength u> 0) instead of (arraylength !=
0).

I've replaced the webrev in place. Please take a look at the new version :-)

Thanks,
Kris


> Regards,
> Martin.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140214/41302c0d/attachment.html