1093573 - Baseline-compile generators

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Part 1 - Some bytecode changes

Two changes:

(1) Eliminate JSOP_FINALYIELD and use JSOP_SETRVAL + JSOP_FINALYIELDRVAL instead.

(2) Always push a value when resuming a generator, even for newborn generators, so that we don't need to do the isNewborn() check in JIT code. JSOP_INITIALYIELD is followed by a JSOP_POP to discard this value.

Comment 2

[Andy Wingo [:wingo]]

Comment on attachment 8516632 [details] [diff] [review]
Part 1 - Some bytecode changes

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

LGTM, nice simplification

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Part 2 - Remove GENERATOR InterpreterFrame flag

It seems all places that use isGeneratorFrame() can use script->isGenerator() instead.

Also removes some dead (since bug 987560) code from Interpret.

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Part 3 - Use AbstractFramePtr

Use AbstractFramePtr in GeneratorObject create/suspend* methods, so that they work with both Baseline and Interpreter frames.

Also adds offsetOf* accessors to GeneratorObject.

Comment 5

[Andy Wingo [:wingo]]

Comment on attachment 8516658 [details] [diff] [review]
Part 2 - Remove GENERATOR InterpreterFrame flag

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

lgtm

::: js/src/jit/Ion.cpp
@@ +2164,5 @@
> +    if (script->isGenerator()) {
> +        JitSpew(JitSpew_IonAbort, "generator script");
> +        return false;
> +    }
> +

I guess this will be needed when generators get baseline support, cool

::: js/src/vm/Interpreter.cpp
@@ +1481,5 @@
>      /* State communicated between non-local jumps: */
>      bool interpReturnOK;
>  
> +    if (!activation.entryFrame()->prologue(cx))
> +        goto error;

yaaaay

Comment 6

[Andy Wingo [:wingo]]

Comment on attachment 8516670 [details] [diff] [review]
Part 3 - Use AbstractFramePtr

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

Super duper.

Comment 7

[Jan de Mooij [:jandem]]

I have a WIP patch that passes jit-tests and jstests. Will start splitting it up and getting more patches up for review.

Comment 8

[Jan de Mooij [:jandem]]

Parts 1-3:

https://hg.mozilla.org/integration/mozilla-inbound/rev/f8bcb09a02b3
https://hg.mozilla.org/integration/mozilla-inbound/rev/0af912c81294
https://hg.mozilla.org/integration/mozilla-inbound/rev/a81312500217

Andy, thanks for the (quick) reviews!

Comment 9

[Jan de Mooij [:jandem]]

Attachment: Part 4 - Add yield index

This patch adds a yield index operand to JSOP_INITIALYIELD and JSOP_YIELD, and stores this value in a slot on the generator when suspending.

JIT code can then use this value to quickly load the native code address from a table stored in the BaselineScript, when resuming the generator.

Comment 10

[Jan de Mooij [:jandem]]

Attachment: Part 5 - Compile JSOP_GENERATOR

Comment 11

[Jan de Mooij [:jandem]]

Attachment: Part 6 - Compile yield instructions

Compile yield bytecode ops. Also stores the native code address for each yield op in the BaselineScript, so that we can use that in a later patch.

Comment 12

[Jan de Mooij [:jandem]]

(In reply to Jan de Mooij [:jandem] from comment #11)
> Created attachment 8518122 [details] [diff] [review]
> Part 6 - Compile yield instructions

Forgot to mention, these are just the slow paths for now. We can inline YIELD without a VM call in a lot of cases, but we can do that later.

Comment 13

[Jan de Mooij [:jandem]]

Attachment: Part 7 - Allow OSR

With this patch we can enter generator scripts at loop heads.

We still can't resume them directly though; JSOP_RESUME support will be in another patch.

Comment 14

[Jan de Mooij [:jandem]]

Attachment: Part 8 - Add JitFrame_Unwound_BaselineJS

When we resume a generator, there will be a call directly from the BaselineJS frame, instead of from a BaselineStub frame (this is what we do for other calls).

So we now need JitFrame_Unwound_BaselineJS, just like JitFrame_Unwound_BaselineStub and JitFrame_Unwound_IonJS.

Comment 15

[Jan de Mooij [:jandem]]

Attachment: Part 9 - Add InterpretGeneratorResume

Adds a self-hosted function the JIT can call when the generator has no baseline code.

Comment 16

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/f8bcb09a02b3
https://hg.mozilla.org/mozilla-central/rev/0af912c81294
https://hg.mozilla.org/mozilla-central/rev/a81312500217

Comment 17

[Jan de Mooij [:jandem]]

Attachment: Part 10 - Compile JSOP_RESUME

And finally the most interesting part.

Shu, can you confirm that using a Kind_Op ICEntry here is fine for the DebugModeOSR? I couldn't come up with a testcase that asserts even with MOZ_SHOW_ALL_JS_FRAMES=1 (to expose self-hosted frames).

Some context: JSOP_RESUME is only emitted for the "resumeGenerator" calls in builtin/Generator.js. It pushes a new Baseline frame on the stack for the generator and resumes execution.

Comment 18

[Andy Wingo [:wingo]]

Comment on attachment 8518122 [details] [diff] [review]
Part 6 - Compile yield instructions

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

::: js/src/jit/BaselineJIT.h
@@ +179,5 @@
>      uint32_t bytecodeTypeMapOffset_;
>  
> +    // For generator scripts, we store the native code address for each yield
> +    // instruction.
> +    uint32_t yieldEntriesOffset_;

To me it would make sense to store a corresponding array of bytecode offsets in Script(), so that we could avoid the extra bytecode offset word in generator objects.

::: js/src/jit/VMFunctions.cpp
@@ +853,5 @@
> +{
> +    MOZ_ASSERT(*pc == JSOP_INITIALYIELD);
> +    return GeneratorObject::initialSuspend(cx, obj, frame, pc);
> +}
> +

it's kinda shocking how small this code is

Comment 19

[Andy Wingo [:wingo]]

Comment on attachment 8519886 [details] [diff] [review]
Part 10 - Compile JSOP_RESUME

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

LGTM.  Pretty gnarly but at least you managed to handle it in the compiler and not the macroassemblers.  Is the JIT frame that does the RESUME visible to a backtrace?

::: js/src/jit/BaselineCompiler.cpp
@@ +3421,5 @@
> +    masm.addPtr(scratch2, scratch1);
> +    masm.unboxInt32(Address(genObj, GeneratorObject::offsetOfYieldIndexSlot()), scratch2);
> +    masm.loadPtr(BaseIndex(scratch1, scratch2, ScaleFromElemWidth(sizeof(uintptr_t))), scratch1);
> +
> +    // Push |undefined| for all formals.

Note to self: this works because all formals are aliased and so lookup won't happen via the stack.

@@ +3443,5 @@
> +    masm.subPtr(BaselineStackReg, scratch2);
> +    masm.store32(scratch2, Address(BaselineFrameReg, BaselineFrame::reverseOffsetOfFrameSize()));
> +    masm.makeFrameDescriptor(scratch2, JitFrame_BaselineJS);
> +
> +    masm.Push(Imm32(0)); // actual argc

Apparently argc can be zero but there are slots reserved for formals still?  Cool.

@@ +3456,5 @@
> +
> +    // Push a fake return address on the stack. We will resume here when the
> +    // generator returns.
> +    Label genStart, returnTarget;
> +    masm.callAndPushReturnAddress(&genStart);

So, when the generator yields it will return here.  OK.

@@ +3488,5 @@
> +        masm.or32(Imm32(BaselineFrame::HAS_ARGS_OBJ), frame.addressOfFlags());
> +    }
> +    masm.bind(&noArgsObj);
> +
> +    // Push expression slots if needed.

Interesting, this is doing more inline that V8 does.  Of course on the other hand it's only doing it once and not six times for each architecture :)  Cool.

Comment 20

[Jan de Mooij [:jandem]]

(In reply to Andy Wingo [:wingo] from comment #18)
> To me it would make sense to store a corresponding array of bytecode offsets
> in Script(), so that we could avoid the extra bytecode offset word in
> generator objects.

I was considering it but wasn't sure about growing JSScript. We could add a union somewhere maybe..

Comment 21

[Andy Wingo [:wingo]]

(In reply to Jan de Mooij [:jandem] from comment #20)
> (In reply to Andy Wingo [:wingo] from comment #18)
> > To me it would make sense to store a corresponding array of bytecode offsets
> > in Script(), so that we could avoid the extra bytecode offset word in
> > generator objects.
> 
> I was considering it but wasn't sure about growing JSScript. We could add a
> union somewhere maybe..

It need not take up space for non-generators; it could be like the TryNote array.

Comment 22

[Jan de Mooij [:jandem]]

(In reply to Andy Wingo [:wingo] from comment #21)
> It need not take up space for non-generators; it could be like the TryNote
> array.

Hm fair enough. I'll give it a try :)

Comment 23

[Jan de Mooij [:jandem]]

Parts 4-6:

https://hg.mozilla.org/integration/mozilla-inbound/rev/e8126f03c301
https://hg.mozilla.org/integration/mozilla-inbound/rev/e88c55b98d85
https://hg.mozilla.org/integration/mozilla-inbound/rev/91dfa90b8973

Comment 24

[Jan de Mooij [:jandem]]

Attachment: Part 11 - Remove bytecode slot

Removes the bytecode offset slot from GeneratorObject. We now store just the yield index and JSScript has a table to map the yield index to the bytecode offset.

I really like how this turned out.

Comment 25

[Jan de Mooij [:jandem]]

Parts 7-8:

https://hg.mozilla.org/integration/mozilla-inbound/rev/7ce270448bb3
https://hg.mozilla.org/integration/mozilla-inbound/rev/a36a3b892743

Comment 26

[Andy Wingo [:wingo]]

Comment on attachment 8520699 [details] [diff] [review]
Part 11 - Remove bytecode slot

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

Looks great, excellent simplification!  Just one nit that hasYieldOffsets is really the same as isGenerator, AFAICS.  Maybe just use isGenerator?  Dunno.

::: js/src/jsscript.h
@@ +900,5 @@
>          OBJECTS,
>          REGEXPS,
>          TRYNOTES,
>          BLOCK_SCOPES,
> +        YIELD_OFFSETS,

I guess it's clear to have this here, but really it's sufficient to look at the generatorKindBits (i.e. bool hasYieldOffsets() { return isGenerator() }.  Doesn't matter really as this bit is free right now.  If we leave it like it is, probably we should add an assertion.

Comment 27

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/e8126f03c301
https://hg.mozilla.org/mozilla-central/rev/e88c55b98d85
https://hg.mozilla.org/mozilla-central/rev/91dfa90b8973
https://hg.mozilla.org/mozilla-central/rev/7ce270448bb3
https://hg.mozilla.org/mozilla-central/rev/a36a3b892743

Comment 28

[Shu-yu Guo [:shu]]

Comment on attachment 8519886 [details] [diff] [review]
Part 10 - Compile JSOP_RESUME

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

::: js/src/jit/BaselineCompiler.cpp
@@ +3459,5 @@
> +    Label genStart, returnTarget;
> +    masm.callAndPushReturnAddress(&genStart);
> +
> +    // Add an IC entry so the return offset -> pc mapping works.
> +    ICEntry icEntry(script->pcToOffset(pc), ICEntry::Kind_Op);

If an ICEntry |entry| is of type Kind_Op, debug mode OSR expects the frame to be returnable directly to |returnAddressForIC(entry)| for the new entry **without any further register/stack fixups for, say, the BaselineFrameReg**, as the IC stub code is shareable across recompile. ISTM this code does that -- the generator's JIT code will always take care of popping the frame reg, and the stack is always fully synced at JSOP_RESUME.

Even though this doesn't have a corresponding stub frame, debug mode OSR doesn't care if there isn't a stub frame to patch.

Comment 29

[Jan de Mooij [:jandem]]

Attachment: Part 12 - Inline INITIALYIELD and YIELD

Inlines INITIALYIELD and YIELD-with-empty-stack. For now I decided to keep the exception for closing legacy generators, as it turned out to not be a huge problem (see the comment in the patch). Will file a follow-up bug to change this.

Comment 30

[Jan de Mooij [:jandem]]

Parts 9-11:

https://hg.mozilla.org/integration/mozilla-inbound/rev/4e2a28215270
https://hg.mozilla.org/integration/mozilla-inbound/rev/d8cd4f0de4f7
https://hg.mozilla.org/integration/mozilla-inbound/rev/b932c51b4ad9

Comment 31

[Jan de Mooij [:jandem]]

(In reply to Shu-yu Guo [:shu] from comment #28)
> Even though this doesn't have a corresponding stub frame, debug mode OSR
> doesn't care if there isn't a stub frame to patch.

Thanks for confirming this.

(In reply to Andy Wingo [:wingo] from comment #26)
> Looks great, excellent simplification!  Just one nit that hasYieldOffsets is
> really the same as isGenerator, AFAICS.  Maybe just use isGenerator?  Dunno.

Good point, I changed it.

Comment 32

[Jan de Mooij [:jandem]]

Attachment: Part 13 - Handle closing legacy generators correctly

Always resuming a close operation in the interpreter does not avoid the exception handling issues, because we can OSR into JIT code if there's a loop inside a finally block. Preventing OSR there is not that easy so this patch fixes Baseline's exception handling to deal with this.

r?shu for the IonFrames.cpp changes, wingo for the rest.

Comment 33

[Andy Wingo [:wingo]]

Comment on attachment 8521391 [details] [diff] [review]
Part 13 - Handle closing legacy generators correctly

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

Probably worth removing the newborn state, either before or after, and just letting the continuation set the state to closed from outside the generator on non-local return.

::: js/src/vm/GeneratorObject.cpp
@@ +112,5 @@
>      GeneratorObject *genObj = &obj->as<GeneratorObject>();
> +    if (resumeKind == GeneratorObject::THROW) {
> +        cx->setPendingException(arg);
> +        if (genObj->isNewborn())
> +            genObj->setClosed();

Won't the continuation of the resumeGenerator() set the generator object state to closed?  Seems odd to have the state be closed when you just pushed on the activation.  (Is there actually a newborn state any more?  With the try/catch around generatorResume() it seems to me that suspended at yield index 0 is just like any other yield index.)

Comment 34

[Jan de Mooij [:jandem]]

Attachment: Part 14 - Remove newborn state

I think you're right and the newborn state is no longer necessary.

Comment 35

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/4e2a28215270
https://hg.mozilla.org/mozilla-central/rev/d8cd4f0de4f7
https://hg.mozilla.org/mozilla-central/rev/b932c51b4ad9

Comment 36

[Shu-yu Guo [:shu]]

Comment on attachment 8521391 [details] [diff] [review]
Part 13 - Handle closing legacy generators correctly

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

It's unclear to me how this interacts with debug mode OSR. Debugger::onExceptionUnwind can trigger it, and since legacy generators are implemented as a throw, it'll end up calling onExceptionUnwind. I don't know if that frame can be patched properly. We should make the JS_GENERATOR_CLOSING magic exception not trigger onExceptionUnwind. As it stands now I think it'll try to reflect the JS_GENERATOR_CLOSING magic and assert.

r=me with onExceptionUnwind fixed.

::: js/src/jit/IonFrames.cpp
@@ +512,5 @@
> +HandleClosingGeneratorReturn(JSContext *cx, const JitFrameIterator &frame, jsbytecode *pc,
> +                             jsbytecode *unwoundScopeToPc, ResumeFromException *rfe,
> +                             bool *calledDebugEpilogue)
> +{
> +    // If we're closing a legacy generator, we need to return to the caller

The horror of legacy generators!!

@@ +521,5 @@
> +        return;
> +    RootedValue exception(cx);
> +    if (!cx->getPendingException(&exception))
> +        return;
> +    if (!exception.isMagic(JS_GENERATOR_CLOSING))

I guess this is the only magic value that can ever been thrown? Seems that way from the comments in JSWhyMagic.

Comment 37

[Andy Wingo [:wingo]]

Comment on attachment 8521424 [details] [diff] [review]
Part 14 - Remove newborn state

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

Excellent!

Comment 38

[Jan de Mooij [:jandem]]

Attachment: Part 15 - Add and optimize IsSuspendedStarGenerator

This patch adds a new intrinsic, IsSuspendedStarGenerator, as a fast path for the most common case. It's also inlined with a Baseline IC stub.

Also made a small change to stop monitoring types for GETALIASEDVAR ops if we know Ion can't compile the script: in generators all vars are aliased and monitoring is unnecessary if nothing will benefit from it.

With all these patches + bug 1097890 we have for the micro-benchmark below:

before: 983 ms
after:   43 ms
d8:      45 ms

function *g(n) { for (var i = 0; i < n; i++) { yield i; } }
function f() {
    var t = new Date();
    var it = g(1000000);
    for (var i=0; i<1000000; i++)
	it.next();
    print(new Date() - t);
}
f();

Comment 39

[Andy Wingo [:wingo]]

Comment on attachment 8522152 [details] [diff] [review]
Part 15 - Add and optimize IsSuspendedStarGenerator

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

LGTM with a small nit.  Jan the performance results are stellar; you are a wizard!

::: js/src/vm/GeneratorObject.h
@@ +141,2 @@
>          MOZ_ASSERT(!isClosed());
> +        return getFixedSlot(YIELD_INDEX_SLOT).toInt32() < YIELD_INDEX_CLOSING;

Can you add a static assertion that CLOSING is less than RUNNING?

Comment 40

[Jan de Mooij [:jandem]]

Parts 12-14:

https://hg.mozilla.org/integration/mozilla-inbound/rev/5e645894f6bf
https://hg.mozilla.org/integration/mozilla-inbound/rev/8792056f152c
https://hg.mozilla.org/integration/mozilla-inbound/rev/76fdd0f934c1

(In reply to Shu-yu Guo [:shu] from comment #36)
> r=me with onExceptionUnwind fixed.

Fixed it both in Baseline and the interpreter and added a testcase. Thanks!

Comment 41

[Jan de Mooij [:jandem]]

And finally part 15 :)

https://hg.mozilla.org/integration/mozilla-inbound/rev/30276610fd29

(In reply to Andy Wingo [:wingo] from comment #39)
> Can you add a static assertion that CLOSING is less than RUNNING?

Done.

Comment 42

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/5e645894f6bf
https://hg.mozilla.org/mozilla-central/rev/8792056f152c
https://hg.mozilla.org/mozilla-central/rev/76fdd0f934c1

Comment 43

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/30276610fd29