542002 - Optimize to flat closures even if some upvars can't be copied

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Brendan Eich [:brendan]]

See bug 508716 comment 25.

/be

Comment 1

[Brendan Eich [:brendan]]

Attachment: patch to test

Jason, you might want to start looking.

Boris, this may be helpful -- it eliminates all "inner tree trying to grow" aborts in one of dmandelin's closures test.

I need to cover a hazardous case still, and add some trace-tests.

/be

Comment 2

[Boris Zbarsky [:bzbarsky]]

Yeah, this gives about a 20% speedup on the fluid-sim with no green tossed in (from 30FPS to 36FPS, with the share of time spent in JS going down from 64% to 58%), with all the branch exits listed in bug 508716 comment 20 disappearing.  Oh, and time in js_Interpret goes from 6.8% to 0.3%.

Comment 3

[Brendan Eich [:brendan]]

Attachment: fix EmitNameOp bugs

Comment 4

[Brendan Eich [:brendan]]

Comment on attachment 423553 [details] [diff] [review]
fix EmitNameOp bugs

interdiff chokes on jstracer.cpp diffs but gets the only real changes (jsemit.cpp ones) right.

/be

Comment 5

[Brendan Eich [:brendan]]

Attachment: patch with tests, second of which shows remaining hazard

This also fixes EmitNameOp to avoid deoptimizing (setting MIGHT_CALLOUT) for a deoptimized lexical name use (which can't be a getter or setter implicit call).

/be

Comment 6

[Jason Orendorff [:jorendorff]]

This changes parenting in TM::record_JSOP_LAMBDA_FC but I don't see the corresponding change in the interpreter path (js_NewFlatClosure).

This bug's summary should probably be changed. Eliminating the guard on parent whenever possible is the bulk of the work here and the major win.

Can we make the flat closure optimization per-name and available to all nested functions, instead of having a separate JSFUN_FLAT_CLOSURE function-kind?

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #6)
> This changes parenting in TM::record_JSOP_LAMBDA_FC but I don't see the
> corresponding change in the interpreter path (js_NewFlatClosure).

js_NewFlatClosure uses cx->fp->scopeChain already -- same as the JIT with this patch. Or is TR::scopeChain() not the same?

> This bug's summary should probably be changed. Eliminating the guard on parent
> whenever possible is the bulk of the work here and the major win.

The two are subtly related, since if you don't do the flat optimization you end up with extra heavyweights (the ones for Field in the fluid simulator), which then require the parent guard, even with the optimizations to TR::guardCallee in this bug's patch.

> Can we make the flat closure optimization per-name and available to all nested
> functions, instead of having a separate JSFUN_FLAT_CLOSURE function-kind?

That would lose, because null closures even with upvars do not need to be cloned at all, whereas flat closures mean cloned function objects with dslots for the copied (flattened) upvars. The hierarchy of optimizations (jsfun.h has a comment about this) is:

1. NULL_CLOSURE: non-escaping and/or no-upvar functions, which need only a global scope linked via parent, so need not be cloned when evaluated (see the method barrier code).

2. FLAT_CLOSURE: constant upvars copied into the cloned function object's slots. This patch allows some upvars to be accessed by JSOP_NAME et al.

3. INTERPRETED: the rest, using JSOP_NAME for upvars that are not constant, e.g. HEAVYWEIGHT or not.

Not cloning is huge. I wish we could avoid it in other cases, but I'm hard pressed to think of how.

We do want faster GC-thing, object, and function object allocation, for sure.

/be

Comment 8

[Brendan Eich [:brendan]]

(In reply to comment #7)
nested
> > functions, instead of having a separate JSFUN_FLAT_CLOSURE function-kind?
> 
> That would lose, because null closures even with upvars do not need to be
> cloned at all,

Er, in some cases (jorendorff reminded me on IRC): the "method" cases.

/be

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #8)
> (In reply to comment #7)
> nested
> > > functions, instead of having a separate JSFUN_FLAT_CLOSURE function-kind?
> > 
> > That would lose, because null closures even with upvars do not need to be
> > cloned at all,
> 
> Er, in some cases (jorendorff reminded me on IRC): the "method" cases.

To say a bit more: deferring cloning until a function object reference escapes (this does not happen if the function is called, provided it does not use its own name or arguments object) requires a read barrier. But so do getters for object properties. So I folded the method barrier into this case, to avoid regressing performanace.

For non-object-properties such as return values, arguments passed down, and other uses of a function reference where we would like to clone the function only on such a reference and not on a call, then without heavy static analysis it seems we would need runtime escape analysis. This looks too costly to me -- no getter barrier pre-exists to piggy-back on.

/be

Comment 10

[Jason Orendorff [:jorendorff]]

Here's a better sneak attack test.

function loop(f, expected) {
    // This is the loop that breaks us.
    // At record time, f's parent is a Call object with no fp.
    // At second execute time, it is a Call object with fp,
    // and all the Call object's dslots are still JSVAL_VOID.
    for (var i = 0; i < 9; i++)
        assertEq(f(), expected);
}

function C(bad) {
    var x = bad;
    function f() {
        return x;  // We trick TR::callProp() into emitting code that gets
                   // JSVAL_VOID (from the Call object's dslots)
                   // rather than the actual value (true or false).
    }
    this.m = f;
    return f;
}

var obj = {
    set m(f) {
        if (f())  // Call once to resolve x on the Call object,
                  // for shape consistency. Otherwise loop gets
                  // recorded twice.
            loop(f, true);
    }
};

loop(C.call(obj, false), false);
C.call(obj, true);

Comment 11

[Jason Orendorff [:jorendorff]]

Just a reminder: with the patch, this asserts in the decompiler

    "" + function (x) { this.f = function(){return x;}; }

because the patch changes the decompiler's treatment of UNBRAND but doesn't change the emitter to emit UNBRANDTHIS instead (yet).

Comment 12

[Brendan Eich [:brendan]]

Attachment: patch with JSOP_UNBRANDTHIS generation and jorendorff's righteous sneak-attack test

Comment 13

[Brendan Eich [:brendan]]

Attachment: defeat the sneak attack

Comment 14

[Brendan Eich [:brendan]]

Attachment: patch without sneak-attack defense

Runtime defense is unsound due to order of unexpected escape vs. trace recording being undetermined.

/be

Comment 15

[Brendan Eich [:brendan]]

Simplifying bug. The static analysis is not feasible, and a hybrid scheme has problems unless the runtime part is drastic.

/be

Comment 16

[Brendan Eich [:brendan]]

Static analysis is always feasible if conservative enough, so I'm fixing it to close holes. It will not avoid the parent guard for methods of Field, but for those methods that are not fully flat closures, the parent will be the FluidField Call object, a singleton. So we'll pay a succeeding-guard cost, without exiting and causing inner tree trying to grow pathologies.

Patch as soon as I've finished making the analysis sufficiently restrictive.

/be

Comment 17

[Brendan Eich [:brendan]]

Attachment: patch for review

Check EmitImplicitlyConvertibleOperand against runtime js_ValueTo* calls from the interpreter and helpers (jsiter.cpp, e.g.).

/be

Comment 18

[Brendan Eich [:brendan]]

Attachment: avoid redundancy via cg->mightCallKid()

Comment 19

[Brendan Eich [:brendan]]

(In reply to comment #17)
> Created an attachment (id=425251) [details]
> patch for review
> 
> Check EmitImplicitlyConvertibleOperand against runtime js_ValueTo* calls from
> the interpreter and helpers (jsiter.cpp, e.g.).

Also against ECMA-262 spec, but of course we have extensions such as __iterator__.

/be

Comment 20

[Jason Orendorff [:jorendorff]]

Still thinking it over. I have to break for dinner. I'll finish tonight.

Comment 21

[Jason Orendorff [:jorendorff]]

An indirect consequence of a snowstorm in Nashville is that this didn't get done. Instead I'm trying to get a toddler to sleep. Tomorrow for sure.

Comment 22

[Jason Orendorff [:jorendorff]]

Comment on attachment 425263 [details] [diff] [review]
avoid redundancy via cg->mightCallKid()

In js_EmitTree, case TOK_INC/TOK_DEC:
>             op = PN_OP(pn2);
>             if (op == JSOP_CALLEE) {
>                 if (js_Emit1(cx, cg, op) < 0)
>                     return JS_FALSE;
>-            } else if (pn2->pn_cookie != FREE_UPVAR_COOKIE) {
>-                atomIndex = (jsatomid) pn2->pn_cookie;
>-                EMIT_UINT16_IMM_OP(op, atomIndex);
>             } else {
>-                JS_ASSERT(JOF_OPTYPE(op) == JOF_ATOM);
>-                if (!EmitAtomOp(cx, pn2, op, cg))
>-                    return JS_FALSE;
>-                break;
>+                /*
>+                 * An expression such as ++f could call, via a toString or
>+                 * valueOf function defined in Function.prototype which then
>+                 * invokes |this|, a child function f otherwise not seen as
>+                 * called. See EmitImplicitlyConvertibleOperand.
>+                 */
>+                cg->mightCallKid();
>+
>+                if (pn2->pn_cookie != FREE_UPVAR_COOKIE) {
>+                    atomIndex = (jsatomid) pn2->pn_cookie;
>+                    EMIT_UINT16_IMM_OP(op, atomIndex);
>+                } else {
>+                    JS_ASSERT(JOF_OPTYPE(op) == JOF_ATOM);
>+                    if (!EmitAtomOp(cx, pn2, op, cg))
>+                        return JS_FALSE;
>+                    break;
>+                }
>             }

I think all three cases need cg->mightCallKid(), not just the last two.

You marked the operands of && and || as "implicitly convertible", but
conversion to boolean is harmless (for now).

There are also XML ops that can do implicit conversion, including at least
XMLTAGEXPR, XMLELTEXPR and {GET,CALL}XMLNAME.

I'm surely missing another hole somewhere. Do you think these holes are
exploitable, or just corner-case correctness bugs?

As we discussed on IRC last week, this blacklisting approach seems fragile to
me. And because almost everything inhibits it, this optimization doesn't seem
widely applicable. There are better ways to spend these lines of code and
future maintenance cost. I don't feel strongly enough to minus a patch that you
and bz both want, but please think it over.

Comment 23

[Brendan Eich [:brendan]]

(In reply to comment #22)
> (From update of attachment 425263 [details] [diff] [review])
> In js_EmitTree, case TOK_INC/TOK_DEC:
> >             op = PN_OP(pn2);
> >             if (op == JSOP_CALLEE) {
[...]
> I think all three cases need cg->mightCallKid(), not just the last two.

Definitely -- duh! Thanks.

> You marked the operands of && and || as "implicitly convertible", but
> conversion to boolean is harmless (for now).

That was not because of conversion to boolean, which for objects yields true, rather as noted in some comment in the patch it was to avoid complexifying the emitter to pass down a flag from the caller that we care about mightCallKid.

> There are also XML ops that can do implicit conversion, including at least
> XMLTAGEXPR, XMLELTEXPR and {GET,CALL}XMLNAME.

None function-valued, though.

> I'm surely missing another hole somewhere. Do you think these holes are
> exploitable, or just corner-case correctness bugs?

I think I'm gonna bail on the static analysis again. dmandelin has a grand plan for closures that should take away the pain of the parent guard. The main win for now is partial flat closures, which allow Fluid to be lightweight.

Thanks for the wise advice. I'll put up a simpler patch tomorrow.

/be

Comment 24

[Brendan Eich [:brendan]]

Attachment: partial flat closures only, no aggro static analysis

To be safe and aggressive, static analysis would need to model the heap, or at least track local function reference flow better (SSA). Maybe later, but for now this is enough.

I had to revert the trace-test/tests/closures/lambda.js patch, so that will wait for dmandelin to rescue it from the "Inner tree is trying to grow" hell.

/be

Comment 25

[Jason Orendorff [:jorendorff]]

Comment on attachment 426274 [details] [diff] [review]
partial flat closures only, no aggro static analysis

Great. This looks good -- though I found (preexisting) bug 545446 while tinkering with it. r=me.

Comment 26

[Brendan Eich [:brendan]]

http://hg.mozilla.org/tracemonkey/rev/a353e155804e

/be

Comment 27

[Brendan Eich [:brendan]]

Followup to fix latent bug hidden by fact that until the main patch landed, we had to be able to flatten all upvars in order to make a flat closure:

http://hg.mozilla.org/tracemonkey/rev/a8d65f5da19a

/be

Comment 28

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/a353e155804e