Last Comment Bug 695887 - IonMonkey: Introduce lazy bailouts
: IonMonkey: Introduce lazy bailouts
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: ---
Assigned To: Nicolas B. Pierron [:nbp]
:
Mentors:
Depends on: 706303
Blocks: 695075
  Show dependency treegraph
 
Reported: 2011-10-19 15:41 PDT by David Anderson [:dvander]
Modified: 2011-12-22 11:21 PST (History)
3 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
HeapFrames & postSnapshots. (32.84 KB, patch)
2011-11-04 19:22 PDT, Nicolas B. Pierron [:nbp]
no flags Details | Diff | Review
Use case sample. (6.04 KB, patch)
2011-11-04 19:23 PDT, Nicolas B. Pierron [:nbp]
nicolas.b.pierron: review-
Details | Diff | Review
FrameInfos & postSnapshots. (34.10 KB, patch)
2011-11-10 21:20 PST, Nicolas B. Pierron [:nbp]
dvander: review+
Details | Diff | Review
Add safepoint to LInstructions. (5.62 KB, patch)
2011-11-10 21:23 PST, Nicolas B. Pierron [:nbp]
dvander: review+
Details | Diff | Review
FrameInfos & postSnapshots & SnapshotIterator. (44.50 KB, patch)
2011-11-15 19:25 PST, Nicolas B. Pierron [:nbp]
cdleary: review+
Details | Diff | Review
Add safepoint to LInstructions. (10.94 KB, patch)
2011-11-15 19:27 PST, Nicolas B. Pierron [:nbp]
nicolas.b.pierron: review+
Details | Diff | Review
Use case sample. (5.28 KB, patch)
2011-11-15 19:29 PST, Nicolas B. Pierron [:nbp]
nicolas.b.pierron: review-
Details | Diff | Review

Description David Anderson [:dvander] 2011-10-19 15:41:36 PDT
When LIR is capable of leaving JIT code, we need some sort of record capturing the stack state, so the VM can lazily inspect or bailout Ion frames. Unlike eager bailouts, which occur when a guard fails, a lazy bailout has no "trigger" - it can only occur if the VM needs to deoptimize the frame from within C++.

When leaving a JIT frame, the stack always looks like this:

   ... locals ...
   <descriptor>
   <returnAddress>
   ... JS frame or code to enter C++ ...

We need a mapping from <returnAddress> to a block of data that describes the Ion state. Currently, this is simply a snapshotOffset. After bug 695075, we will also need to encode information about pointers - so likely <returnAddress> will have to map to a tuple (v8 makes each entry variable length and performs a linear search - this is an option too), so we should take that into account when designing the table.

The other tricky detail is the difference between idempotent and non-idempotent LIR. Idempotent LIR can call into C++, for example, to perform GC or run some small helper function. A non-idempotent LIR can call into anything.

(1) is simple: the instruction is resumeable so we can build a snapshot off the most recent resumePoint, which is what assignSnapshot() does.

(2) is not resumeable, so even if it has an assigned snapshot, this snapshot may correspond to a much earlier program point, and is not usable for a lazy bailout (which must recover the position in between the call and the next opcode).

We will need to introduce a new variant of assignSnapshot() that assigns a second snapshot appropriate for lazy bailouts. Instead of using lastResumePoint_, it will need to use ins->snapshot(). We could either introduce a new, explicit, assignLazySnapshot(), or make it implicit as part of updateResumeState().

We'll also have to teach the register allocator to fill in lazy snapshots. A trivial way to do this (which is done in v8) is to create an LLazyBailout no-op instruction that has the call's lazySnapshot as its normal, eager snapshot.

tl;dr summary:
-------------
(1) Need to introduce lazy snapshots for non-idempotent call instructions
(2) On outgoing calls, need a mapping from returnAddress -> [snapshotOffset],
    that can be expanded to map to multiple offsets.
Comment 1 Nicolas B. Pierron [:nbp] 2011-11-04 19:22:29 PDT
Created attachment 572154 [details] [diff] [review]
HeapFrames & postSnapshots.
Comment 2 Nicolas B. Pierron [:nbp] 2011-11-04 19:23:43 PDT
Created attachment 572155 [details] [diff] [review]
Use case sample.

Do not commit, this is just a test sample.
Comment 3 David Anderson [:dvander] 2011-11-08 15:04:33 PST
Comment on attachment 572154 [details] [diff] [review]
HeapFrames & postSnapshots.

Review of attachment 572154 [details] [diff] [review]:
-----------------------------------------------------------------

This patch looks good, mostly naming comments, but I would like to iterate on assignPostSnapshot once more. I missed something while originally laying out this bug, which is that both effectful and non-effectful calls need safepoints, which is important for opcodes like NewArray.

::: js/src/ion/IonFrames.h
@@ +62,5 @@
> +
> +// IonHeapFrame are stored on the heap and do not impact any cost on the Jitted
> +// code, either the size or the . This structure can be obtained by using the return address which is the
> +// only field which can not be extracted from the frames.
> +struct IonHeapFrame

This should be called something like "SafepointMapEntry" (in JaegerMonkey it was "NativeMapEntry"). "HeapFrame" is misleading - the fact that it's on the heap doesn't describe what it does, and it's not a frame. (Remember that eventually these entries will contain, or reference, a GC map as well).

I would also make it a sub-structure of IonScript or put it in IonCode.h, since that is basically where the entirety of the mapping lives.

::: js/src/ion/IonLIR.h
@@ +549,5 @@
>      LIR_OPCODE_LIST(LIROP)
>  #undef LIROP
>  
>  class LSnapshot;
> +class LCaptureAllocations;

Is this forward declare needed?

::: js/src/ion/LOpcodes.h
@@ +42,5 @@
>  #ifndef jsion_lir_opcodes_common_h__
>  #define jsion_lir_opcodes_common_h__
>  
>  #define LIR_COMMON_OPCODE_LIST(_)   \
> +    _(CaptureAllocations)           \

nit: Prefer "CaptureState" here. The ResumePoint/Snapshot terminology is all about varying ways of expressing interpreter state, "Allocations" is kind of operational.

::: js/src/ion/Lowering.cpp
@@ +163,5 @@
>      if (!defineReturn(ins, call))
>          return false;
>      if (!assignSnapshot(ins))
>          return false;
> +    if (!assignPostSnapshot(call, ins))

"assignPostSnapshot" is kind of operational, too. Ideally we want to express the fact that these instructions may leave JIT code to enter the VM: they must create a safepoint. The concept of pre/post snapshots is orthogonal to safepoints. For example, NewArray requires a safepoint, but it does not have a post-snapshot. Its safepoint uses the pre-snapshot. bug 695075 will introduce GC maps, and those will also become part of the safepoint.

Calls can be broken down into three categories:
 (1) Enters VM, effectful. Example: SetProperty. Requires a safepoint composed of a post-snapshot and a GC map.
 (2) Enters VM, not effectful. Example: NewArray. Requires a safepoint composed of either a pre- or post-snapshot, and a GC map.
 (3) Does not enter VM. Example: DoubleToECMAInt32. Does not require a safepoint.

For (1) and (2), we want one function, something like "assignSafepoint". This would assign either a pre- or post-snapshot based on whether the LIR is resumable, and with bug 695075, also attach a GC map.

::: js/src/ion/shared/CodeGenerator-x86-shared.cpp
@@ +137,5 @@
>  
>      // Call the wrapper function.  The wrapper is in charge to unwind the
>      // stack when returning from the call.
>      masm.call(wrapper);
> +    if (!assignHeapFrame(snapshot))

Ideally, both this function and callVM could take in an LInstruction *, and fill in the SafepointMapEntry based on which snapshot is available. This simplifies the CallGeneric code too, since you don't need to know what kind of snapshot to pass in.

::: js/src/ion/x64/Lowering-x64.cpp
@@ +151,5 @@
>  bool
> +LIRGeneratorX64::assignPostSnapshot(MInstruction *mir, LInstruction *ins)
> +{
> +    JS_ASSERT(mir->resumePoint());
> +    if (postSnapshot_)

I would JS_ASSERT(!postSnapshot_), it would be a bug if we called this twice (we cannot fail in between two effects).
Comment 4 Nicolas B. Pierron [:nbp] 2011-11-08 18:32:53 PST
(In reply to David Anderson [:dvander] from comment #3)
> Comment on attachment 572154 [details] [diff] [review] [diff] [details] [review]
> HeapFrames & postSnapshots.
> 
> Review of attachment 572154 [details] [diff] [review] [diff] [details] [review]:
> -----------------------------------------------------------------
> 
> This patch looks good, mostly naming comments, but I would like to iterate
> on assignPostSnapshot once more. I missed something while originally laying
> out this bug, which is that both effectful and non-effectful calls need
> safepoints, which is important for opcodes like NewArray.
> 
> ::: js/src/ion/IonFrames.h
> @@ +62,5 @@
> > +
> > +// IonHeapFrame are stored on the heap and do not impact any cost on the Jitted
> > +// code, either the size or the . This structure can be obtained by using the return address which is the
> > +// only field which can not be extracted from the frames.
> > +struct IonHeapFrame
> 
> This should be called something like "SafepointMapEntry" (in JaegerMonkey it
> was "NativeMapEntry"). "HeapFrame" is misleading - the fact that it's on the
> heap doesn't describe what it does, and it's not a frame. (Remember that
> eventually these entries will contain, or reference, a GC map as well).
> 
> I would also make it a sub-structure of IonScript or put it in IonCode.h,
> since that is basically where the entirety of the mapping lives.

I don't think HeapFrame is missleading, on the contrary it fully describe what it does.  An HeapFrame is a part of a Frame which can be computed at compile time and which contain the rest of the Frame which is not included in the stack during the call.  I agree the name does not map the idea of "rest" and "computed at compilation time", but it is way more general than only the WhateverMapEntry.

> ::: js/src/ion/IonLIR.h
> @@ +549,5 @@
> >      LIR_OPCODE_LIST(LIROP)
> >  #undef LIROP
> >  
> >  class LSnapshot;
> > +class LCaptureAllocations;
> 
> Is this forward declare needed?
> 
> ::: js/src/ion/LOpcodes.h
> @@ +42,5 @@
> >  #ifndef jsion_lir_opcodes_common_h__
> >  #define jsion_lir_opcodes_common_h__
> >  
> >  #define LIR_COMMON_OPCODE_LIST(_)   \
> > +    _(CaptureAllocations)           \
> 
> nit: Prefer "CaptureState" here. The ResumePoint/Snapshot terminology is all
> about varying ways of expressing interpreter state, "Allocations" is kind of
> operational.

What is the "State", is that the set of allocations of the Snapshot which are updated ?  Unless we explicit the name "State", I don't think this is a good idea.  In addition, "State" is used in other context which make things confusing, such as "MachineState".

> ::: js/src/ion/Lowering.cpp
> @@ +163,5 @@
> >      if (!defineReturn(ins, call))
> >          return false;
> >      if (!assignSnapshot(ins))
> >          return false;
> > +    if (!assignPostSnapshot(call, ins))
> 
> "assignPostSnapshot" is kind of operational, too. Ideally we want to express
> the fact that these instructions may leave JIT code to enter the VM: they
> must create a safepoint. The concept of pre/post snapshots is orthogonal to
> safepoints. For example, NewArray requires a safepoint, but it does not have
> a post-snapshot. Its safepoint uses the pre-snapshot. bug 695075 will
> introduce GC maps, and those will also become part of the safepoint.
> 
> Calls can be broken down into three categories:
>  (1) Enters VM, effectful. Example: SetProperty. Requires a safepoint
> composed of a post-snapshot and a GC map.
>  (2) Enters VM, not effectful. Example: NewArray. Requires a safepoint
> composed of either a pre- or post-snapshot, and a GC map.
>  (3) Does not enter VM. Example: DoubleToECMAInt32. Does not require a
> safepoint.

 (4) Enters VM, effectful. Example: CallGeneric. Requires 2 safepoints
composed of a pre-snapshot, post-snapshot and 2? GC map.

> For (1) and (2), we want one function, something like "assignSafepoint".
> This would assign either a pre- or post-snapshot based on whether the LIR is
> resumable, and with bug 695075, also attach a GC map.

Sure, as an optimization, but not as a replacement of the post snapshot.

> ::: js/src/ion/shared/CodeGenerator-x86-shared.cpp
> @@ +137,5 @@
> >  
> >      // Call the wrapper function.  The wrapper is in charge to unwind the
> >      // stack when returning from the call.
> >      masm.call(wrapper);
> > +    if (!assignHeapFrame(snapshot))
> 
> Ideally, both this function and callVM could take in an LInstruction *, and
> fill in the SafepointMapEntry based on which snapshot is available. This
> simplifies the CallGeneric code too, since you don't need to know what kind
> of snapshot to pass in.

??? Call Generic need 2 snapshots, one before the compilation, one after the call.  So I don't see where this could help ?  Safepoint implies that you will have to lookup at the LIR to understand where the instruction would resume.

> ::: js/src/ion/x64/Lowering-x64.cpp
> @@ +151,5 @@
> >  bool
> > +LIRGeneratorX64::assignPostSnapshot(MInstruction *mir, LInstruction *ins)
> > +{
> > +    JS_ASSERT(mir->resumePoint());
> > +    if (postSnapshot_)
> 
> I would JS_ASSERT(!postSnapshot_), it would be a bug if we called this twice
> (we cannot fail in between two effects).

Oops, I forgot to set the postSnapshot of the instruction again.  This is useful in the case where one resumable MIR produces multiple LIR instructions which are both using the same postSnapshot.
Comment 5 Nicolas B. Pierron [:nbp] 2011-11-10 21:20:49 PST
Created attachment 573739 [details] [diff] [review]
FrameInfos & postSnapshots.

Renaming: HeapFrame -> FrameInfo.
Comment 6 Nicolas B. Pierron [:nbp] 2011-11-10 21:23:00 PST
Created attachment 573740 [details] [diff] [review]
Add safepoint to LInstructions.
Comment 7 David Anderson [:dvander] 2011-11-11 22:06:42 PST
Comment on attachment 573739 [details] [diff] [review]
FrameInfos & postSnapshots.

Review of attachment 573739 [details] [diff] [review]:
-----------------------------------------------------------------

looks good, r=me with nits picked:

::: js/src/ion/Ion.cpp
@@ +418,5 @@
> +IonScript::getFrameInfo(ptrdiff_t disp) const {
> +    JS_ASSERT(frameInfoEntries_ > 0);
> +
> +    if (frameInfoEntries_ == 1)
> +    {

nit: { goes on preceding line

@@ +442,5 @@
> +        // Check for infinite loops.
> +        JS_ASSERT(guess != old_guess);
> +
> +        if (guess_disp > disp)
> +        {

nit: { on preceding line

@@ +447,5 @@
> +            max_entry = guess;
> +            max = guess_disp;
> +        }
> +        else
> +        {

nit: } else {

::: js/src/ion/IonCode.h
@@ +168,5 @@
>      }
> +    const IonFrameInfo *frameInfos() const {
> +        return (const IonFrameInfo *)(reinterpret_cast<const uint8 *>(this) + frameInfoTable_);
> +    }
> +    IonFrameInfo *frameInfos() {

nit: s/frameInfos/frameInfoTable/

::: js/src/ion/shared/CodeGenerator-shared.cpp
@@ +201,5 @@
> +        return false;
> +
> +    // Is the heap frame table full?
> +    // if (bailouts_.length() >= BAILOUT_TABLE_SIZE)
> +    //    return false;

You can remove this.

::: js/src/ion/shared/CodeGenerator-x86-shared.cpp
@@ +819,5 @@
>          masm.bind(&thunk);
>          masm.mov(Imm32(call->nargs()), ArgumentsRectifierReg);
>          masm.movePtr(ImmWord(argumentsRectifier->raw()), ecx); // safe to take: return reg.
>          masm.call(ecx);
> +        if (!assignFrameInfo(call->postSnapshot()))

Together with your follow-up patch, these calls should become something like:

    if (!createSafepoint(call))
        return false;

(I like the "FrameInfo" structure name, but here we definitely want to express the fact that we're creating a GC point.)
Comment 8 David Anderson [:dvander] 2011-11-11 22:13:40 PST
Comment on attachment 573740 [details] [diff] [review]
Add safepoint to LInstructions.

Review of attachment 573740 [details] [diff] [review]:
-----------------------------------------------------------------

Great, this is exactly what I was hoping for! Follow-up patch to replace calls to assignPostSnapshot with assignSafepoint?

::: js/src/ion/x64/Lowering-x64.cpp
@@ +167,5 @@
>  
>  bool
> +LIRGeneratorX64::assignSafepoint(MInstruction *mir, LInstruction *ins)
> +{
> +    ins->setMir(mir);

It's a little confusing that both this and define() call ins->setMir(), but I don't have any good idea how to normalize that.
Comment 9 Nicolas B. Pierron [:nbp] 2011-11-15 19:25:16 PST
Created attachment 574774 [details] [diff] [review]
FrameInfos & postSnapshots & SnapshotIterator.

Previously this patch was based on a similar modification which enabled the frame
introspection.  As this is desirable for this feature, I added similar on top of the latest modifications.

This update the IonFrameIterator to make it usable (to fetch the next calleeToken) and to iterate over all frames nicely. (cf use case)  In addition, it introduces a way to convert it to a frameRecovery and to convert a FrameRecovery to a SnapshotIterator.
Comment 10 Nicolas B. Pierron [:nbp] 2011-11-15 19:27:01 PST
Created attachment 574775 [details] [diff] [review]
Add safepoint to LInstructions.

Update review status.
Comment 11 Nicolas B. Pierron [:nbp] 2011-11-15 19:29:51 PST
Created attachment 574776 [details] [diff] [review]
Use case sample.

Use case made on top of new array patch (see Bug 685838)
Comment 12 Chris Leary [:cdleary] (not checking bugmail) 2011-11-22 16:37:35 PST
Comment on attachment 574774 [details] [diff] [review]
FrameInfos & postSnapshots & SnapshotIterator.

Review of attachment 574774 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good!

::: js/src/ion/Ion.cpp
@@ +335,5 @@
>  {
>  }
>  
>  IonScript *
> +IonScript::New(JSContext *cx, size_t snapshotsSize, size_t bailoutEntries, size_t constants, size_t frameInfoTable)

Nit: we should call this frameInfos or frameInfoEntries for consistency with the constants and bailoutEntries.

@@ +414,5 @@
> +    memcpy(frameInfoTable(), fi, frameInfoEntries_ * sizeof(IonFrameInfo));
> +}
> +
> +const IonFrameInfo *
> +IonScript::getFrameInfo(ptrdiff_t disp) const {

Nit: bracket for function definitions (outside of a class) go on a newline.

@@ +422,5 @@
> +        JS_ASSERT(disp == frameInfoTable()[0].displacement);
> +        return &frameInfoTable()[0];
> +    }
> +
> +    size_t min_entry = 0;

Should use normal casing for all these local variables: minEntry, oldGuess, guessDisp.

@@ +431,5 @@
> +
> +    JS_ASSERT(min <= disp && disp <= max);
> +    while (true) {
> +        DebugOnly<size_t> old_guess = guess;
> +        guess = (disp - min) * (max_entry - min_entry) / (max - min);

Cool.

::: js/src/ion/IonFrames.cpp
@@ +149,3 @@
>      }
>      currentSize += current->prevFrameLocalSize();
> +    const_cast<uint8 *&>(prevCache_) = current_ + currentSize;

Casting a LHS ref is kind of gross -- can we mark prevCache as mutable instead?

::: js/src/ion/IonFrames.h
@@ +207,5 @@
>        : regs_(regs), fpregs_(fpregs)
>      { }
>  
>      double readFloatReg(FloatRegister reg) const {
> +        JS_ASSERT(fpregs_);

We don't assert that things are non-null if we're about to deref them anyway.

@@ +212,4 @@
>          return fpregs_[reg.code()];
>      }
>      uintptr_t readReg(Register reg) const {
> +        JS_ASSERT(regs_);

Same here.

::: js/src/ion/Lowering.cpp
@@ +632,5 @@
>  #ifdef DEBUG
>      ins->setInWorklistUnchecked();
>  #endif
> +
> +    // If no post snapshot is used, then exit with success.

s/is used/was present

::: js/src/ion/Snapshots.cpp
@@ +231,5 @@
>      JS_ASSERT(slotsRead_ == slotCount_);
>      JS_ASSERT(reader_.readSigned() == -1);
>  }
>  
> +SnapshotIterator::SnapshotIterator(const FrameRecovery& in)

For refs in SpiderMonkey style, the ampersand hugs the variable name.

@@ +244,5 @@
> +    unreadSlots_ = slots();
> +}
> +
> +uintptr_t
> +SnapshotIterator::fromLocation(const SnapshotReader::Location &loc) {

Nit: brace on newline.

@@ +247,5 @@
> +uintptr_t
> +SnapshotIterator::fromLocation(const SnapshotReader::Location &loc) {
> +    if (loc.isStackSlot())
> +        return in_.readSlot(loc.stackSlot());
> +    return in_.machine().readReg(loc.reg());

Nit: ternary?

@@ +256,5 @@
> +{
> +    switch (type) {
> +      case JSVAL_TYPE_INT32:
> +        return Int32Value(payload);
> +    case JSVAL_TYPE_BOOLEAN:

Indentation got messed up here.

::: js/src/ion/Snapshots.h
@@ +237,5 @@
> +    uint32 unreadSlots_;
> +
> +    uintptr_t fromLocation(const SnapshotReader::Location &loc);
> +    static Value FromTypedPayload(JSValueType type, uintptr_t payload);
> +  public:

Nit: newline before public, no newline afterwards.

@@ +241,5 @@
> +  public:
> +
> +    SnapshotIterator(const FrameRecovery &in);
> +
> +    Value read();

Nit: newline before inline definition.

::: js/src/ion/shared/CodeGenerator-shared.h
@@ +138,5 @@
>      // If the bailout table is full, this returns false, which is not a fatal
>      // error (the code generator may use a slower bailout mechanism).
>      bool assignBailoutId(LSnapshot *snapshot);
>  
> +    // Assign a FrameInfo to the current offset. This is desirable just after

Can we add, "and encodes the snapshot"?

::: js/src/ion/x86/Lowering-x86.cpp
@@ +213,5 @@
> +LIRGeneratorX86::assignPostSnapshot(MInstruction *mir, LInstruction *ins)
> +{
> +    JS_ASSERT(mir->resumePoint());
> +    // Do not expect a second LIR produced by the same MIR visit to use a
> +    // postSnapshot.

How about "Should only produce one postSnapshot per MIR"?

@@ +216,5 @@
> +    // Do not expect a second LIR produced by the same MIR visit to use a
> +    // postSnapshot.
> +    JS_ASSERT(!postSnapshot_);
> +
> +    LSnapshot *snapshot = buildSnapshot(ins, mir->resumePoint(), Bailout_Normal);

Do we need/want a different bailout kind for post snapshots?
Comment 13 David Anderson [:dvander] 2011-11-22 17:45:29 PST
> Do we need/want a different bailout kind for post snapshots?

Technically we don't need one but something like Bailout_Safepoint might be good for clarity.
Comment 14 Nicolas B. Pierron [:nbp] 2011-11-28 16:28:24 PST
https://hg.mozilla.org/projects/ionmonkey/rev/113e69231a02
Comment 15 Nicolas B. Pierron [:nbp] 2011-11-28 17:46:21 PST
Lack of ARM support makes Android builds red.
Comment 16 Nicolas B. Pierron [:nbp] 2011-12-22 11:21:19 PST
Bug 710130 is the last missing brick to bring this feature to ARM.
Marking this bug as fixed.

Note You need to log in before you can comment on or make changes to this bug.