Bounds checks with unsafe array access

[Remi Forax]

On 09/10/2014 02:41 PM, Vitaly Davidovich wrote:
>
> 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.
>

It's not paranoid, most of the dependency injection libraries, Hibernate 
or serialization code allow you to set the value of final field at runtime.

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

@java.lang.invoke.Stable

Rémi

> Sent from my phone
>
> On Sep 10, 2014 6:48 AM, "Paul Sandoz" <paul.sandoz at oracle.com 
> <mailto: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/22187ef4/attachment-0001.html>