A simple optimization proposal (original) (raw)

Krystal Mok rednaxelafx at gmail.com
Fri Feb 14 00:04:52 PST 2014

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

More information about the hotspot-compiler-dev mailing list