831585 - MOREITER and ITERNEXT should not save the next iteration value in JSContext

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jim Blandy :jimb]

+++ This bug was initially created as a clone of Bug #777596 +++

The MOREITER bytecode determines whether an iteration should continue, and ITERNEXT retrieves the iteration's next value. Depending on what's being iterated over, MOREITER may, as a side effect, actually produce the value for the next iteration.

As presently implemented, MOREITER saves the value it produces, if any, in JSContext::iterValue, and ITERNEXT tries to retrieve it from there. Bugs 772770 and bug 769754 demonstrate why this is a poor design: through various mechanisms (Debugger.Frame onStep handlers; proxies on the scope chain; and who knows what else), arbitrary JS code can run between those two bytecodes; and if that intervening code does any iteration itself, it will trash the interrupted code's iteration value that ITERNEXT was expecting.

Instead, MOREITER should produce *two* stack values: the next value, or MagicValue(JS_NO_ITER_VALUE) if none is available; and the boolean value indicating whether the iteration should continue, as it does now. ITERNEXT should then consult that stack slot when appropriate. By storing the pending value in the stack frame instead of JSContext, there will be no need for explicit code to save and restore it (like PreserveIterValue).

Bug 777596 has preparatory cleanup patches.

Comment 1

[Jim Blandy :jimb]

Attachment: Remove native iterator fast paths.

I haven't measured the impact of this patch, but it should make it simpler
to convert the code to a fused JSOP_IFMOREITER bytecode. This optimization
should be easy to re-introduce if it's valuable once the conversion is
done.

Comment 2

[Jim Blandy :jimb]

Attachment: Replace JSOP_MOREITER and JSOP_ITERNEXT with JSOP_IFMOREITER; remove JSContext::iterValue.

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Patch

It was hard to break this up so here's a patch that:

* Removes cx->iterValue (I posted a patch in bug 1066197 to temporarily move it to the runtime, that patch is not necessary after all).

* Remove JSOP_ITERNEXT.

* Instead of pushing a boolean, JSOP_MOREITER now pushes the Value directly, or MagicValue(JS_NO_ITER_VALUE) if we're done.

* JSOP_MOREITER is always followed by JSOP_IFMOREITER. It branches to the loop body if the value on the stack is not the magic value. Else, it pops the value and falls through to the code after the loop. Using a separate, non-effectful op to do the branching is a lot simpler to implement in the JITs.

* Fixes a small bug in jit/BytecodeAnalysis.cpp. We can't update |pc| in the |if (jump)| branch, as the old value is used afterwards.

 29 files changed, 289 insertions(+), 462 deletions(-)

For this function:

function f(arr) {
    for (var p in arr) {
	p.length;
    }
}

We used to emit this:

00000:  getarg 0
00003:  iter 1
00005:  goto 27 (+22)
00010:  loophead
00011:  iternext
00012:  setlocal 0
00016:  pop
00017:  getlocal 0
00021:  length "length"
00026:  pop
00027:  loopentry 129
00029:  moreiter
00030:  ifne 10 (-20)
00035:  enditer
00036:  retrval

Now we emit:

00000:  getarg 0
00003:  iter 1
00005:  goto 26 (+21)
00010:  loophead
00011:  setlocal 0
00015:  pop
00016:  getlocal 0
00020:  length "length"
00025:  pop
00026:  loopentry 129
00028:  moreiter
00029:  ifmoreiter 10 (-19)
00034:  enditer
00035:  retrval

I'm considering renaming JSOP_MOREITER to JSOP_ITERNEXT, but it would have to be a followup patch or it'd be very confusing.

Comment 5

[Jason Orendorff [:jorendorff]]

Jan, I tried to do this a few years back and hit assertions in the old decompiler.

The reason was that the decompiler used a single forward pass over the bytecode to reconstruct expressions for each slot in the operand stack. So this change:

    loophead
-   iternext
    setlocal 0
    pop

confused the decompiler regarding what was on the operand stack from then on.

I think the new decompiler works the same way. Can you tell if it's broken?

Comment 6

[Jason Orendorff [:jorendorff]]

(It was stupid of me to let the decompiler wreck that work; the right thing would have been to insert an unreachable JSOP_UNDEFINED or something to appease the decompiler. Or delete it.)

Comment 7

[Jan de Mooij [:jandem]]

(In reply to Jason Orendorff [:jorendorff] from comment #5)
> I think the new decompiler works the same way. Can you tell if it's broken?

Andy Wingo added the BytecodeParser in jsopcode.cpp (based on the bytecode parser we used to have in jsanalyze.cpp), see bug 932180. It follows jumps to compute stack depths instead of doing a single forward pass + SRC_HIDDEN.

I had to make a small change to it for this patch (some tests failed without it), so I assume this mechanism is working fine.

Comment 8

[Brian Hackett [Laid off!]]

Comment on attachment 8489021 [details] [diff] [review]
Patch

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

Nice!

This looks really good, though at a high level I'm concerned about the JSOP_IFMOREITER opcode.  It seems like things would be simpler if the end of the loop changed from 'moreiter; ifmoreiter' to 'moreiter; isnoiter; ifeq' where isnoiter is an op that just pushes a boolean testing whether the top of the stack is the magic JS_NO_ITER_VALUE.  Building this op would also do the nonStringIteration_ optimization stuff in IonBuilder, and during lowering it could be fused with MTest like we do with MCompare.  This should eliminate MTestIteratorMore and most/all of the complexity added to IonBuilder control flow handling, plus it's nice for both analysis and conceptually if we minimize the number of control flow instructions, i.e. right now MTest looks like the only binary control flow instruction we have.  This would require a lot of changes to the patch though and it would also be great to just land as is.

::: js/src/jit/BytecodeAnalysis.cpp
@@ +201,5 @@
>          // Handle any fallthrough from this opcode.
>          if (BytecodeFallsThrough(op)) {
> +            jsbytecode *fallthrough = pc + GetBytecodeLength(pc);
> +            JS_ASSERT(fallthrough < end);
> +            unsigned nextOffset = script_->pcToOffset(fallthrough);

fallthroughOffset?

Comment 9

[Jan de Mooij [:jandem]]

(In reply to Brian Hackett (:bhackett) from comment #8)
> It seems like things would be simpler if the end of
> the loop changed from 'moreiter; ifmoreiter' to 'moreiter; isnoiter; ifeq'
> where isnoiter is an op that just pushes a boolean testing whether the top
> of the stack is the magic JS_NO_ITER_VALUE.

Nice idea! But in that case we'd also need a JSOP_POP after the IFEQ, to pop the MagicValue when we exit the loop, so it'd look like:

moreiter
isnoiter
ifeq
pop
<break_target>

The problem then is that breaks inside the loop will have to go to break_target, not to the pop. This requires some changes to IonBuilder, because it uses state.loop.exitpc both for break targets and as the start-pc-of-loop-successor.

My first approach was for IFMOREITER to always leave the value on the stack + have a POP after it, and I ran into this. It's fixable but it's just a bit annoying.

Comment 10

[Brian Hackett [Laid off!]]

Ah, good point.  Would the layout below avoid the break_target problem?

<head>
undefined
swap
<body>
pop
moreiter
isnoiter
ifeq <head>
pop

This might be going too far down the rabbit hole though.

Comment 11

[Jan de Mooij [:jandem]]

(In reply to Brian Hackett (:bhackett) from comment #10)
> Ah, good point.  Would the layout below avoid the break_target problem?

Yeah I was just thinking about that too... for-of loops do something similar I think.

(In reply to Brian Hackett (:bhackett) from comment #8)
> Building this op would also do
> the nonStringIteration_ optimization stuff in IonBuilder, and during
> lowering it could be fused with MTest like we do with MCompare.

How would this work? We need to add the MUnbox(String) to the loop's body block, which we create later when we get to the IFEQ no?

Comment 12

[Brian Hackett [Laid off!]]

(In reply to Jan de Mooij [:jandem] from comment #11)
> How would this work? We need to add the MUnbox(String) to the loop's body
> block, which we create later when we get to the IFEQ no?

Hmm, yeah, a fallible unbox in the loop test wouldn't work.  I think that ideally, when building MOREITER we produce a value whose type set is 'string | magic'.  Doing this would require the MOREITER stub to invalidate if it produces a non-string iteration value.  Then, when we get to the IFEQ, we can detect that the test only jumps on non-magic values, and at the head of the loop we do an infallible unbox to string.  We already have the ability to do this sort of detection in IonBuilder::improveTypesAtTest.

Making this change would be even more involved though.  As an interim solution I think you could add a special case for noStringIteration_ to processWhileCondEnd and do the fallible unboxing there, and then a later patch making the above improvements could remove the special case.

Comment 13

[Jan de Mooij [:jandem]]

Attachment: Patch v2

Slightly different approach. With this patch we emit the following (we keep the value on the stack):

00003:  iter 1
00005:  undefined
00006:  goto 26 (+20)
00011:  loophead
00012:  setlocal 0
<body>
00026:  loopentry 129
00028:  pop
00029:  moreiter
00030:  isnoiter
00031:  ifeq 11 (-20)
00036:  pop
00037:  enditer

Comment 14

[Brian Hackett [Laid off!]]

Comment on attachment 8490659 [details] [diff] [review]
Patch v2

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

Thanks!

Comment 15

[Jan de Mooij [:jandem]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/26d86ab7c4f3

Comment 16

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/26d86ab7c4f3