Bounds checks with unsafe array access

[Vladimir Ivanov]

Remi,

@Stable isn't a full match for final field case, since it doesn't treat 
default values as constants. But I agree, it's close.

Hotspot already constant folds loads from static final fields and 
there's an experimental flag TrustFinalNonStaticFields for final 
instance fields.

What we miss right now for preserving correctness w.r.t. Reflection API 
is a way to track dependencies between final fields and nmethods and 
invalidate all nmethods which (possibly) embed changed final values.

Best regards,
Vladimir Ivanov

On 9/10/14, 5:04 PM, Remi Forax 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
>> <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.
>>
>