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

[Paul Sandoz]

Hi Roland,

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

int a_loop() {
    int[] a = array;
    int sum = 0;
    for (int i = 0; i < a.length; i++) {
        sum += a(a, i);
    }
    return sum;
}

int a(int[] a, int i) {
    if (i < 0 || i >= a.length)
        throw new ArrayIndexOutOfBoundsException();

    return a[i];
}

int u_loop() {
    int[] a = array;
    int sum = 0;
    for (int i = 0; i < a.length; i++) {
        sum += u(a, i);
    }
    return sum;
}

int u(int[] a, int i) {
    if (i < 0 || i >= a.length)
        throw new ArrayIndexOutOfBoundsException();

    long address = (((long) i) << 2) + UNSAFE.ARRAY_INT_BASE_OFFSET;
    return UNSAFE.getInt(a, address);
}


For example, here is the main loop for u_loop on jdk9/dev (using -XX:LoopUnrollLimit=0):

0x000000010ba77938: test   %ecx,%ecx
0x000000010ba7793a: jl     0x000000010ba779d2  ;*iflt
                                              ; - arrays.ArrayTest::u at 1 (line 71)
                                              ; - arrays.ArrayTest::u_loop at 19 (line 65)

0x000000010ba77940: cmp    %ebp,%ecx
0x000000010ba77942: jge    0x000000010ba779f9  ;*if_icmplt
                                              ; - arrays.ArrayTest::u at 7 (line 71)
                                              ; - arrays.ArrayTest::u_loop at 19 (line 65)

0x000000010ba77948: movslq %ecx,%r10
0x000000010ba7794b: add    0x10(%rbx,%r10,4),%eax  ;*iadd
                                              ; - arrays.ArrayTest::u_loop at 22 (line 65)

0x000000010ba77950: inc    %ecx               ;*iinc
                                              ; - arrays.ArrayTest::u_loop at 24 (line 64)

0x000000010ba77952: cmp    %r8d,%ecx
0x000000010ba77955: jl     0x000000010ba77938  ;*if_icmpge
                                              ; - arrays.ArrayTest::u_loop at 12 (line 64)


And here is the same on jdk9/hs-rt with your patch applied:

0x0000000110355f40: movslq %r10d,%r9
0x0000000110355f43: add    0x10(%r8,%r9,4),%eax  ;*iadd
                                              ; - arrays.ArrayTest::u_loop at 22 (line 65)

0x0000000110355f48: inc    %r10d              ;*iinc
                                              ; - arrays.ArrayTest::u_loop at 24 (line 64)

0x0000000110355f4b: cmp    %r11d,%r10d
0x0000000110355f4e: jl     0x0000000110355f40  ;*if_icmpge
                                              ; - arrays.ArrayTest::u_loop at 12 (line 64)

I wish we could get rid of those pesky "movslq" instructions :-) but IIUC that is tricky.


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.

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 841 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20150224/1d48545d/signature.asc>