Bounds checks with unsafe array access

[Vitaly Davidovich]

It's paranoid to me because I know whether I'm using any of that stuff or
not :)

@Stable isn't meant for use outside JDK right? So doesn't seem like a
general solution.  And even if it were, does compiler take this at full
faith?

Sent from my phone
On Sep 10, 2014 9:05 AM, "Remi Forax" <forax at univ-mlv.fr> wrote:

>
> 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> 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/264a5e3a/attachment.html>