A simple optimization proposal
rednaxelafx at gmail.com
Fri Feb 14 00:04:52 PST 2014
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
> 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
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
> 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
> 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:
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 !=
I've replaced the webrev in place. Please take a look at the new version :-)
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the hotspot-compiler-dev