Bounds checks with unsafe array access
Vitaly Davidovich
vitalyd at gmail.com
Thu Sep 11 16:40:52 UTC 2014
Thanks Vladimir.
If a guard is used for arraylength, then that guard would have to be
checked each time anyway, right? In that case, given the guard would
perform a cmp against 0 (or a test), isn't the whole point defeated (i.e.
no range/length check)?
Right, currently dependencies are at the class level. But it sounded to me
like this will be extended to support dependencies on fields (i.e. to
support final fields)?
On Thu, Sep 11, 2014 at 12:13 PM, Vladimir Ivanov <
vladimir.x.ivanov at oracle.com> wrote:
> Thanks, Vitaly.
>
> I think it's much simpler to profile array length and then add a guard, if
> arrays of 0 length hasn't been seen.
>
> Considering how dependencies are implemented in HotSpot (on class
> granularity), it looks too coarse-grained for tracking instance-specific
> information.
>
> Best regards,
> Vladimir Ivanov
>
> On 9/10/14, 6:51 PM, Vitaly Davidovich wrote:
>
>> 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 <mailto: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@
>> oracle.com>
>> <mailto: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>__>
>> <mailto: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/20140911/134d2a41/attachment-0001.html>
More information about the hotspot-compiler-dev
mailing list