1395900 - for-in loops can trigger lots of IonBuilder loop restarts

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement)

Description

[Jan de Mooij [:jandem]]

The function below triggers 25 (!) loop restarts in IonBuilder. This is because we don't know the IteratorMore type and also because we don't know "x" has type MIRType::String in the loop.

I noticed this first on Speedometer. A patch for this reduces the number of restarts from ~1850 to ~650 so it seems pretty effective.

var o = {y: 1};
function f() {
    for (var i = 0; i < 10000; i++) {
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
        for (var x in o) {}
    }
}
f();

Comment 1

[Jan de Mooij [:jandem]]

(In reply to Jan de Mooij [:jandem] from comment #0)
> The function below triggers 25 (!) loop restarts in IonBuilder.

FWIW my patches get rid of all of these loop restarts for the function in comment 0.

Comment 2

[Jan de Mooij [:jandem]]

Attachment: Part 1 - Fix issue in analyzeNewLoopTypes

This does not affect Speedometer much, but I noticed it on my micro-benchmarks.

In analyzeNewLoopTypes, we first look for a pre-existing loop header so we can reuse its phi types. If we can't use the existing loop header because oldEntry->isDead(), we happily return from analyzeNewLoopTypes.

Instead, I think we should just fall through to the code after the loop, in this case.

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Part 2 - Add MIteratorMore type to analyzeNewLoopTypes

This teaches analyzeNewLoopTypes about MIteratorMore's MIRType::Value type, so we don't trigger a loop abort for each for-in loop.

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Part 3 - Remove unused IonBuilder::nonStringIteration_

nonStringIteration_ is dead.

We used it to unbox |x| to string in |for (x in y)|, but I think I broke that a long time ago when I removed JSOP_ITERNEXT (it was merged with JSOP_ITERMORE).

Comment 5

[Jan de Mooij [:jandem]]

Attachment: Part 4 - Add JSOP_ITERNEXT

This adds JSOP_ITERNEXT back. It's a NOP in the interpreter and Baseline, but IonBuilder can use it to unbox the value as string.

Unfortunately legacy generators can return non-strings, in that case we bail and forbid Ion compilation of the script. Legacy generators will likely be removed soon and shouldn't be used on the web.

Comment 6

[Ted Campbell [:tcampbell]]

Comment on attachment 8903545 [details] [diff] [review]
Part 2 - Add MIteratorMore type to analyzeNewLoopTypes

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

::: js/src/jit/IonBuilder.cpp
@@ +563,5 @@
>      }
>      if (!loopHeaders_.append(LoopHeader(cfgBlock->startPc(), entry)))
>          return abort(AbortReason::Alloc);
>  
> +    if (loopEntry->isForIn()) {

Good find :)

Comment 7

[Ted Campbell [:tcampbell]]

Comment on attachment 8903549 [details] [diff] [review]
Part 4 - Add JSOP_ITERNEXT

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

Please update jsopcodes.cpp so dis() doesn't show |<unknown>|
https://searchfox.org/mozilla-central/rev/51b3d67a5ec1758bd2fe7d7b6e75ad6b6b5da223/js/src/jsopcode.cpp#678-701

::: js/src/frontend/BytecodeEmitter.cpp
@@ +7508,5 @@
>          auto loopDepth = this->stackDepth;
>  #endif
>          MOZ_ASSERT(loopDepth >= 2);
>  
> +        if (iflags == JSITER_ENUMERATE) {

Add stack comment

Comment 8

[Ted Campbell [:tcampbell]]

Comment on attachment 8903543 [details] [diff] [review]
Part 1 - Fix issue in analyzeNewLoopTypes

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

If I'm reading this right, your patch will allow us to retry seeding types through |GETLOCAL; SETLOCAL| sequences (the type of other ops wont be different than first time we saw this loop header). If your micro-benchmarks show this gaining us new type info, patch seems good to me.

One side-effect is that loopHeaders_ adds new entries. An alternative would be |break| instead of |continue| and updating the matching entry instead of allocating a new one. I'm fine with leaving as is, but might be clearer to reuse the entry.

Comment 9

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/f719e2cf81ea
part 1 - Try to get new loop types in analyzeNewLoopTypes even if the previous header is dead. r=tcampbell
https://hg.mozilla.org/integration/mozilla-inbound/rev/fdc73e6b6a21
part 2 - Teach analyzeNewLoopTypes about for-in iterator value slot. r=tcampbell
https://hg.mozilla.org/integration/mozilla-inbound/rev/456b4480fdbf
part 3 - Remove unused IonBuilder::nonStringIteration_. r=tcampbell
https://hg.mozilla.org/integration/mozilla-inbound/rev/57a63c3f76fb
part 4 - Add JSOP_ITERNEXT to improve iterator key type information in Ion. r=tcampbell

Comment 10

[Jan de Mooij [:jandem]]

(In reply to Ted Campbell [:tcampbell] from comment #8)
> One side-effect is that loopHeaders_ adds new entries. An alternative would
> be |break| instead of |continue| and updating the matching entry instead of
> allocating a new one. I'm fine with leaving as is, but might be clearer to
> reuse the entry.

Yeah, fair enough. I changed it to a break, updated the existing entry, and added a foundEntry bool so we don't add a new entry after the loop in this case.

Comment 11

[Jan de Mooij [:jandem]]

This seems to have improved sunspider tagcloud by 3-4%.

Sunspider now takes 185-187 ms on the Mac x64 slave. Back in March, this was ~216 ms. So we "accidentally" improved sunspider by more than 10% - simply by optimizing performance all over the place :)

Comment 12

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/f719e2cf81ea
https://hg.mozilla.org/mozilla-central/rev/fdc73e6b6a21
https://hg.mozilla.org/mozilla-central/rev/456b4480fdbf
https://hg.mozilla.org/mozilla-central/rev/57a63c3f76fb