Baseline-compile generators

RESOLVED FIXED in mozilla36

Status

()

Core
JavaScript Engine: JIT
RESOLVED FIXED
4 years ago
4 years ago

People

(Reporter: jandem, Assigned: jandem)

Tracking

(Blocks: 1 bug)

unspecified
mozilla36
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(15 attachments)

9.67 KB, patch
wingo
: review+
Details | Diff | Splinter Review
14.54 KB, patch
wingo
: review+
Details | Diff | Splinter Review
7.72 KB, patch
wingo
: review+
Details | Diff | Splinter Review
19.52 KB, patch
wingo
: review+
Details | Diff | Splinter Review
3.32 KB, patch
wingo
: review+
Details | Diff | Splinter Review
18.52 KB, patch
wingo
: review+
Details | Diff | Splinter Review
873 bytes, patch
wingo
: review+
Details | Diff | Splinter Review
6.20 KB, patch
nbp
: review+
Details | Diff | Splinter Review
8.46 KB, patch
wingo
: review+
Details | Diff | Splinter Review
20.60 KB, patch
wingo
: review+
shu
: review+
Details | Diff | Splinter Review
31.75 KB, patch
wingo
: review+
Details | Diff | Splinter Review
7.46 KB, patch
wingo
: review+
Details | Diff | Splinter Review
12.71 KB, patch
shu
: review+
wingo
: review+
Details | Diff | Splinter Review
7.72 KB, patch
wingo
: review+
Details | Diff | Splinter Review
13.29 KB, patch
wingo
: review+
Details | Diff | Splinter Review
Comment hidden (empty)
(Assignee)

Comment 1

4 years ago
Created attachment 8516632 [details] [diff] [review]
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.
Attachment #8516632 - Flags: review?(wingo)

Comment 2

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

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

LGTM, nice simplification
Attachment #8516632 - Flags: review?(wingo) → review+
(Assignee)

Comment 3

4 years ago
Created attachment 8516658 [details] [diff] [review]
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.
Attachment #8516658 - Flags: review?(wingo)
(Assignee)

Comment 4

4 years ago
Created attachment 8516670 [details] [diff] [review]
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.
Attachment #8516670 - Flags: review?(wingo)

Comment 5

4 years ago
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
Attachment #8516658 - Flags: review?(wingo) → review+

Comment 6

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

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

Super duper.
Attachment #8516670 - Flags: review?(wingo) → review+
(Assignee)

Comment 7

4 years ago
I have a WIP patch that passes jit-tests and jstests. Will start splitting it up and getting more patches up for review.
(Assignee)

Comment 9

4 years ago
Created attachment 8518061 [details] [diff] [review]
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.
Attachment #8518061 - Flags: review?(wingo)
(Assignee)

Comment 10

4 years ago
Created attachment 8518072 [details] [diff] [review]
Part 5 - Compile JSOP_GENERATOR
Attachment #8518072 - Flags: review?(wingo)
(Assignee)

Comment 11

4 years ago
Created attachment 8518122 [details] [diff] [review]
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.
Attachment #8518122 - Flags: review?(wingo)
(Assignee)

Comment 12

4 years ago
(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.
(Assignee)

Comment 13

4 years ago
Created attachment 8518126 [details] [diff] [review]
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.
Attachment #8518126 - Flags: review?(wingo)
(Assignee)

Comment 14

4 years ago
Created attachment 8518128 [details] [diff] [review]
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.
Attachment #8518128 - Flags: review?(nicolas.b.pierron)
(Assignee)

Comment 15

4 years ago
Created attachment 8518161 [details] [diff] [review]
Part 9 - Add InterpretGeneratorResume

Adds a self-hosted function the JIT can call when the generator has no baseline code.
Attachment #8518161 - Flags: review?(wingo)
Attachment #8518128 - Flags: review?(nicolas.b.pierron) → review+
(Assignee)

Comment 17

4 years ago
Created attachment 8519886 [details] [diff] [review]
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.
Attachment #8519886 - Flags: review?(wingo)
Attachment #8519886 - Flags: review?(shu)

Updated

4 years ago
Attachment #8518061 - Flags: review?(wingo) → review+

Updated

4 years ago
Attachment #8518072 - Flags: review?(wingo) → review+

Comment 18

4 years ago
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
Attachment #8518122 - Flags: review?(wingo) → review+

Updated

4 years ago
Attachment #8518126 - Flags: review?(wingo) → review+

Comment 19

4 years ago
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.
Attachment #8519886 - Flags: review?(wingo) → review+

Updated

4 years ago
Attachment #8518161 - Flags: review?(wingo) → review+
(Assignee)

Comment 20

4 years ago
(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

4 years ago
(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.
(Assignee)

Comment 22

4 years ago
(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 :)
(Assignee)

Comment 24

4 years ago
Created attachment 8520699 [details] [diff] [review]
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.
Attachment #8520699 - Flags: review?(wingo)

Comment 26

4 years ago
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.
Attachment #8520699 - Flags: review?(wingo) → review+

Comment 28

4 years ago
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.
Attachment #8519886 - Flags: review?(shu) → review+
(Assignee)

Comment 29

4 years ago
Created attachment 8521338 [details] [diff] [review]
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.
Attachment #8521338 - Flags: review?(wingo)
(Assignee)

Comment 31

4 years ago
(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.

Updated

4 years ago
Attachment #8521338 - Flags: review?(wingo) → review+
(Assignee)

Comment 32

4 years ago
Created attachment 8521391 [details] [diff] [review]
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.
Attachment #8521391 - Flags: review?(wingo)
Attachment #8521391 - Flags: review?(shu)

Comment 33

4 years ago
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.)
Attachment #8521391 - Flags: review?(wingo) → review+
(Assignee)

Comment 34

4 years ago
Created attachment 8521424 [details] [diff] [review]
Part 14 - Remove newborn state

I think you're right and the newborn state is no longer necessary.
Attachment #8521424 - Flags: review?(wingo)

Comment 36

4 years ago
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.
Attachment #8521391 - Flags: review?(shu) → review+

Comment 37

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

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

Excellent!
Attachment #8521424 - Flags: review?(wingo) → review+
(Assignee)

Comment 38

4 years ago
Created attachment 8522152 [details] [diff] [review]
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();
Attachment #8522152 - Flags: review?(wingo)

Comment 39

4 years ago
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?
Attachment #8522152 - Flags: review?(wingo) → review+
(Assignee)

Comment 40

4 years ago
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!
(Assignee)

Comment 41

4 years ago
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.
Keywords: leave-open
Depends on: 1098947
https://hg.mozilla.org/mozilla-central/rev/30276610fd29
Status: ASSIGNED → RESOLVED
Last Resolved: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla36
Blocks: 1099493
Depends on: 1109889
Depends on: 1100129
You need to log in before you can comment on or make changes to this bug.