Bounds checks with unsafe array access

[John Rose]

On Sep 12, 2014, at 7:37 AM, Paul Sandoz <paul.sandoz at oracle.com> wrote:

> 
> On Sep 10, 2014, at 10:20 PM, John Rose <john.r.rose at oracle.com> wrote:
> 
>> On Sep 10, 2014, at 3:47 AM, Paul Sandoz <paul.sandoz at oracle.com> wrote:
>> 
>>> The patch for JDK-8003585 makes no difference.
>> 
>> My first thought, is, why not?  Isn't that just a bug?
>> 
> 
> I would presume so, it seems a general pattern, but I dunno enough about the C2 graph representation. Should i start by rendering graphs and eye-balling them?

Yes, that's about the best you can do for this kind of thing.
Folding cmp1 && cmp2 into cmp3 is no picnic.  It involves editing several control edges at once.
Happily, there is already code that attempts to do this, so you (or some other intrepid) could start there.
The location is IfNode::fold_compares.
It's (maybe, sort of) a bug that that logic doesn't already create CmpU nodes from (i >=0 && i<a.length).

> 
>> For virtualizing arrays, we need either an explicit range-check intrinsic, or robust canonicalization of the standard idioms into CmpU (which is what we use internally).
>> 
> 
> Ok.

That's turning cmp1 into cmp2, which is much more "local".  Should be doable in CmpINode::Ideal, by idiom recognition.

> 
>> Actually, we now have Integer.compareUnsigned!  
> 
> Ah! now it becomes obvious :-)
> 
>         if (Integer.compareUnsigned(index, a.length) >= 0)
>             throw new ArrayIndexOutOfBoundsException();
> 
> That it should in principle, vis some intrinsification, reduce to something like a cmp/jae or test/jbe depending on what comes before it.

Yes.  I don't even think it needs intrinsifying, since its expression is simple enough to recognize in CmpINode::Ideal.

> 
>> If we agree that is an intrinsic for range checks, the JIT will have a better optimization target to aim at.   Ultimately, we need an intrinsic (perhaps more intentional than Integer.compareUnsigned) that will encourage the JIT to treat it like a range check, doing iteration range splitting, predication, and all the rest.
>> 
>>> (Note: in general we cannot assume that "int index = i & (a.length - 1)" always occurs before the bounds checks, otherwise i would have explicitly written "if (a.length == 0) throw ...")
>> 
>> Right.  You want to factor the range check into a bit of code that doesn't know how it's going to be used, but then gets the same perks as normal array code, including the a.length==0 stuff, and the loop opts I mentioned.
>> 
>>> Ideally similar code as shown for an aaload should be generated. Any suggestions/ideas on how to make that happen?
>> 
>> First, agree on a range check intrinsic.  Then, treat optimization equity failures as JIT bugs.
> 
> Many thanks, seems like an excellent starting point is to intrinsify Integer.compareUnsigned and see what that yields.

I think that will get you a step forward.

The next step towards bringing unsafe ops to parity with array ops is finding out why the logic
for -XX:+RangeCheckElimination doesn't kick in (if that indeed is the case).
That would start with an examination of IdealLoopTree::policy_range_check.

— John

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140912/e04cc47c/attachment.html>