RFR(M): 8073480: C2 should optimize explicit range checks

[Roland Westrelin]

Hi Paul.

> I tried out the patch and verified it works nicely with cases such as:

Thanks for trying it and confirming that it works ok.

> Do you know if your patch will play nicely with that for:
> 
>  https://bugs.openjdk.java.net/browse/JDK-8003585
> 
> ?
> 
> Thus when doing:
> 
>  int m = a.length - 1;
>  int index = i & m;
> 
> the unsigned bounds check (explicit for Unsafe or implicit for array access) will get strength reduced to a check if the array length is zero.

I think it should work ok with JDK-8003585. It’s independent from JDK-8003585 AFAICT and can only help.

Roland.

> 
> Paul.
> 
> On Feb 19, 2015, at 4:36 PM, Roland Westrelin <roland.westrelin at oracle.com> wrote:
> 
>> http://cr.openjdk.java.net/~roland/8073480/webrev.00/
>> 
>> Transform explicit range checks in java code of the form:
>> 
>> if (index < 0 || index >= array.length) {
>> throw new ArrayIndexOutOfBoundsException(); 
>> }
>> 
>> as a single CmpU (rather than 2 CmpIs) that is recognized by c2 as a range check.
>> 
>> To do that, IfNode::fold_compares():
>> 
>> - now works with non constant bounds
>> - in addition to 2 consecutive integer comparisons that both branch to a single region, it handles 2 consecutive integer comparisons that both branch to 2 uncommon traps
>> - it allows one test between the 2 integer comparisons to be folded: in the expression above array.length may require a null check
>> 
>> If 2 integer comparisons are folded, the second one is the one that is kept but the uncommon trap is changed so execution restarts at the first if. The trap’s reason is changed to a new reason:
>> 
>> - if this pattern does indeed look like a range check, the reason becomes Reason_range_check so the compiler recognizes this test as a range check. If we trap too much at this test, we don’t perform the folding again
>> - if this pattern doesn’t look like a range check, the reason becomes new reason Reason_unstable_fused_if (in this implementation, it’s the same value as Reason_range_check due to restrictions on number of trap reasons). If we trap too much with this reason, folding is not performed anymore. It’s a new trap reason because we don’t know what if causes the trap. Deoptimization causes the re-execution of the sequence of ifs so profiling should be updated to reflect what branch is taken for next compilation.
>> 
>> A test in between the 2 integer comparisons is modified so it causes re-executions at the first integer comparison otherwise, an exception due to a null check for instance could be thrown when it shouldn’t have been.
>> 
>> If the compiler doesn’t compile:
>> throw new ArrayIndexOutOfBoundsException();
>> as an uncommon trap, the 2 comparisons could still be folded but the compiler wouldn’t always recognize the test as a range check because it wouldn’t find an uncommon trap with reason Reason_range_check.
>> 
>> This is related to:
>> https://bugs.openjdk.java.net/browse/JDK-8042997
>> We’ll introduce an intrinsic to ensure developers can add explicit range checks and have a 100% predictable behavior from the compiler.
>> 
>> Roland.
>