Bounds checks with unsafe array access
Vitaly Davidovich
vitalyd at gmail.com
Wed Sep 10 14:51:03 UTC 2014
I'm sort of asking whether what I wrote earlier (inline below) is
feasible/practical:
Yeah, I don't know how one would do that practically. Compiler would have
> to somehow always know that whenever the array is set its len > 0. One
> crazy idea is to treat this like other speculation via deopt. When jit
> compiling a method with array access, check profiling info and see whether
> len has been seen > 0 always thus far. If so, compile that assumption in
> and register a deopt if this ever changes. This deopt would have to
> piggyback on write barrier or something, but this adds extra complexity and
> perf impact on writes. Maybe for cases where the array is predominantly
> read this could be a net win ...
If there was a way to track a dependency between writes to a final field
and nmethods using that final field (and being able to invalidate those
nmethods when a write is performed), then is there a way to extend this to
allow tracking a dependency between a write into an array field and
nmethods using that array? If so, one could presumably compile this nmethod
with the assumption that the array's length is > 0 (and thus helps Paul's
examples) assuming that's what profiling info tells us. But if this
assumption is broken (i.e. this array is replaced with a null or 0-length
array), the nmethod is invalidated.
Does that make sense?
On Wed, Sep 10, 2014 at 10:41 AM, Vladimir Ivanov <
vladimir.x.ivanov at oracle.com> wrote:
> Vitaly,
>
> Can you elaborate on what do you mean by "this mechanism could be extended
> to track non-final arrays"? I don't see strong relation between value
> profiling and tracking Reflection API usage.
>
> Best regards,
> Vladimir Ivanov
>
> On 9/10/14, 5:47 PM, Vitaly Davidovich wrote:
>
>> 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
>> <mailto: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>
>> <mailto: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/c51305da/attachment-0001.html>
More information about the hotspot-compiler-dev
mailing list