Bounds checks with unsafe array access
Vitaly Davidovich
vitalyd at gmail.com
Wed Sep 10 13:15:22 UTC 2014
Also, private static (javac) compile time constants get const propagated by
javac and nobody seems to mind that they can't change the value at runtime
(or rather, there won't be any effect). In my opinion, same should be done
for final fields as the common case is that people aren't fudging it via
reflection. If one wants to prevent this optimization, explicitly disable
it via -XX.
Sent from my phone
On Sep 10, 2014 9:10 AM, "Vitaly Davidovich" <vitalyd at gmail.com> wrote:
> 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/0724a1a2/attachment-0001.html>
More information about the hotspot-compiler-dev
mailing list