Bounds checks with unsafe array access

[Vitaly Davidovich]

I think there's a fundamental problem in trying to "convey" things to the
compiler.  Clearly, it can't be some metadata approach since compiler can't
just trust user blindly.  The only way I know to convey things is through
code shape.

One thing that bothers me is that even fields marked final aren't really
treated as such by compiler because it's paranoid of things like
reflection.  If there was some way to reassure it that final fields aren't
modified behind its back, then more type info can be captured at init time
(e.g. array is not null and length is captured as a constant).

Sent from my phone
On Sep 10, 2014 6:48 AM, "Paul Sandoz" <paul.sandoz at oracle.com> wrote:

> 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 --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140910/682e56b0/attachment-0001.html>