Bounds checks with unsafe array access

[Paul Sandoz]

Hi,

This method:

    static int aaload(int[] a, int i) {
        int index = i & (a.length - 1);

        return a[index];
    }

compiles to:

  0x000000010466a56c: mov    0xc(%rsi),%r11d    ;*arraylength
                                                ; implicit exception: dispatches to 0x000000010466a5a5
  0x000000010466a570: mov    %r11d,%r10d
  0x000000010466a573: dec    %r10d
  0x000000010466a576: and    %r10d,%edx         ;*iand

  0x000000010466a579: cmp    %r11d,%edx
  0x000000010466a57c: jae    0x000000010466a58e
  0x000000010466a57e: mov    0x10(%rsi,%rdx,4),%eax


For the bounds check there is only one unsigned comparison check since the array length is non-negative (this will also catch the case if "i" is -ve and the array length is 0).

If the patch for JDK-8003585 is applied the check gets strength reduced to:

  0x000000010d9e06ec: mov    0xc(%rsi),%r11d    ;*arraylength
                                                ; implicit exception: dispatches to 0x000000010d9e0725
  0x000000010d9e06f0: mov    %r11d,%r10d
  0x000000010d9e06f3: dec    %r10d
  0x000000010d9e06f6: and    %r10d,%edx         ;*iand

  0x000000010d9e06f9: test   %r11d,%r11d
  0x000000010d9e06fc: jbe    0x000000010d9e070e
  0x000000010d9e06fe: mov    0x10(%rsi,%rdx,4),%eax

and if the array is constant or there is a dominating check (hoisted out of a loop) then the bounds check will go away. More on that later.


This method:

    int unsafe_aaload(int[] a, int i) {
        int index = i & (a.length - 1);

        // Emulate return a[index]
        if (index < 0 || index >= a.length)
            throw new ArrayIndexOutOfBoundsException();

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

compiles to:

  0x000000010495be8c: mov    0xc(%rdx),%r10d    ;*arraylength
                                                ; implicit exception: dispatches to 0x000000010495bee9
  0x000000010495be90: mov    %r10d,%r8d
  0x000000010495be93: dec    %r8d
  0x000000010495be96: and    %r8d,%ecx          ;*iand

  0x000000010495be99: test   %ecx,%ecx
  0x000000010495be9b: jl     0x000000010495beb6  ;*iflt

  0x000000010495be9d: cmp    %r10d,%ecx
  0x000000010495bea0: jge    0x000000010495becd  ;*if_icmplt

  0x000000010495bea2: movslq %ecx,%r10
  0x000000010495bea5: mov    0x10(%rdx,%r10,4),%eax  ;*invokevirtual getInt


The patch for JDK-8003585 makes no difference.

(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 ...")

Ideally similar code as shown for an aaload should be generated. Any suggestions/ideas on how to make that happen?


--

Regarding removing the bounds checks, as previously referred to. If it is known the array length is always > 0 the bounds check can be removed. The general context here is code in the ForkJoinPool.WorkQueue, such as:

        final ForkJoinTask<?> poll() {
            ForkJoinTask<?>[] a; int b; ForkJoinTask<?> t;
            while ((b = base) - top < 0 && (a = array) != null) {
                int j = (((a.length - 1) & b) << ASHIFT) + ABASE;
                t = (ForkJoinTask<?>)U.getObjectVolatile(a, j);
                if (base == b) {
                    if (t != null) {
                        if (U.compareAndSwapObject(a, j, t, null)) {
                            base = b + 1;
                            return t;
                        }
                    }
                    else if (b + 1 == top) // now empty
                        break;
                }
            }
            return null;
        }

If "array" is not null it's length is always > 0 (a zero length array is never allocated by the code). Is there a way to safely convey that knowledge to the runtime/compiler? thereby enabling removal of bounds checks for any replacement of Unsafe in such code.

Paul.
-------------- 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/20140910/49339a14/signature.asc>