Bounds checks with unsafe array access
Vitaly Davidovich
vitalyd at gmail.com
Wed Sep 10 13:47:32 UTC 2014
Vladimir,
Nice to hear you guys are looking to do something about this. Supposing
there was a way to track nmethod dependencies on final fields (with
invalidation upon change), presumably this mechanism could be extended to
track non-final arrays as well and thus support the examples Paul brought
up?
Sent from my phone
On Sep 10, 2014 9:36 AM, "Vladimir Ivanov" <vladimir.x.ivanov at oracle.com>
wrote:
> 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.
>>>
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140910/54f42418/attachment-0001.html>
More information about the hotspot-compiler-dev
mailing list