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

[Roland Westrelin]

Thanks for taking a look, Vladimir.

> Can you explain why you decided to not do next optimization?:
> 
> http://cr.openjdk.java.net/~kvn/8042997/webrev/src/share/vm/opto/parse2.cpp.udiff.html

John commented on the initial bug with a suggestion to reuse uncommon traps instead.
https://bugs.openjdk.java.net/browse/JDK-8042997?focusedCommentId=13597525&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-13597525

> If C2 generates 'throw' code instead of uncommon traps it will be handled by the case "merge region". Right? Did you verified it?

I think it would be but I didn’t verify it. I followed John’s suggestion. At first I went with the uncommon traps also because I thought I could make this transformation more general but then realized it was too tricky.

One problem with the change to parse2.cpp I think, would be if there’s a null check in between. That wouldn’t be handled correctly, AFAICT. Also range check smearing only recognizes a range check if it traps with Reason_range_check. We wouldn’t have a trap in this case, right?

> Did you consider to use dominated If for folded cmp? That way you don't need adjst middle test if it exists (reroute_side_effect_free_unc). Also I think it is correct thing to do since middle test may depend on first (dominating) test.

I thought about it but I didn’t do it because if we have an integer comparison, followed by a null  check followed by an integer comparison on a LoadRange that depends on the null check, turning it into an unsigned comparison on the the LoadRange followed by a null check wouldn’t work (the LoadRange would depend on the null check which would be after the comparison).

> cmpi_if() should also exclude overflow, no_overflow cases.

Right.

> side_effect_free() does not check that middle test is actual NULL check. You only check that there is CastPP. It could be not enough.

I don’t think it has to be a null check. A check that is simple enough doesn’t have to block the transformation. Do you have an example where another type of checks would be a problem?

> Name cmpi_if() should be is_cmpi_folds().
> Name proj_cmpi_with - is_ctrl_folds().
> Name shared_region() - has_shared_region().
> Name side_effect_free() - is_side_effect_free_test()
> Name uncommon_traps() - has_only_uncommon_traps()
> 
> In ProjNode::other_if_proj() add assert that _con is 0 or 1 only.

I’ll do that.

Roland.

> 
> Thanks,
> Vladimir
> 
> On 2/19/15 7:36 AM, Roland Westrelin 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.
>>