Bounds checks with unsafe array access
Vladimir Ivanov
vladimir.x.ivanov at oracle.com
Thu Sep 11 16:13:02 UTC 2014
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 at 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.
>
>
>
More information about the hotspot-compiler-dev
mailing list