844805 - Don't call FoldConstants from Parser::memberExpr()

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jason Orendorff [:jorendorff]]

We know which calls are generator-expr calls; there's a different parse node kind.

Comment 1

[Jason Orendorff [:jorendorff]]

Also:

            /*
             * Do folding so we don't have roundtrip changes for cases like:
             * function (obj) { return obj["a" + "b"] }
             */
            if (foldConstants && !FoldConstants(context, &propExpr, this))
                return NULL;

Comment 2

[Jason Orendorff [:jorendorff]]

The call in unaryExpr() dates back to 2009, introduced in bug 382355.

It is not necessary anymore at least since PNK_GENEXP was introduced.

Comment 3

[Jason Orendorff [:jorendorff]]

Attachment: v1

Why is this patch so big?

Consider `obj["a" + "b"]`. We want to emit the same bytecode as for `obj.ab`.

This is a two-step optimization, first this:
  "a" + "b" ==> "ab"
then this:
  obj["ab"] ==> obj.ab

Both optimizations must happen, in that order.

Before this patch, the second optimization was implemented in the parse phase. But the first is implemented in FoldConstants. To get both, in the right order, the parser had to call FoldConstants immediately before attempting the second optimization.

Sounds slow, right? I even considered that this might be a counterexample to Brendan's claim that every O(n^2) hack has come back to bite -- this FoldConstants call has his fingerprints on it, and doesn't seem to have bitten us. But it turns out it's only O(n*d) where d is our recursion depth limit, in this case just under 2000 in a debug build on my MacBook.

The fix is to put both optimizations in FoldConstants where they belong.

The determination that an array or object literal is constant belongs in FoldConstants as well. Someday.

In the most extreme case I could contrive, below, this patch reduces the number of FoldConstants calls from 3,972,051 (363 msec in a DEBUG build) to 3,991
(6 msec).


var a = "x";
for (var i = 0; i < 1992; i++)
    a = "x[" + a + "]";

var t0 = Date.now();
var f = Function(a);
var t1 = Date.now();
print(t1 - t0);

Comment 4

[Jason Orendorff [:jorendorff]]

Comment on attachment 765114 [details] [diff] [review]
v1

Retracting; this patch is as busted as can be. If not more so.

Comment 5

[Jason Orendorff [:jorendorff]]

Attachment: Part 1 - Don't use pn_op of PNK_DOT/ELEM nodes

OK, this isn't the most straightforward fix, but it is more satisfying if you want to see ParseNode::pn_op go away.

The bug with my previous patch was that I wasn't setting pn_op=JSOP_SETPROP on a particular PNK_DOT node that I created in FoldConstants. Well, that bug should be unpossible.

The purpose of this "part 1" patch is to make the BytecodeEmitter stop
looking at the pn_op field of PNK_DOT and PNK_ELEM nodes (except to assert
that their values are exactly what we expect).

In the next patch I actually set pn_op to JSOP_NOP on those nodes (and
remove the assertions, of course).

- EmitPropLHS has an in-out parameter, op, which should be
  in-only. EmitPropLHS only writes to *op in one specific case
  which the caller can easily figure out beforehand.

  (In fact I changed it so that the *grandcaller*, EmitCallOrNew,
  figures it out, which turns out to be exactly what the adjacent
  PNK_ELEM case does.)

- Likewise the callContext argument becomes redundant, if the caller
  passes the correct op.

- Deleted a redundant BindNameToSlot call. Proof that it's redundant:
  in that path we have pn2->isKind(PNK_NAME), which means the whole
  pn2->isKind(PNK_DOT) block is skipped; we'll call EmitTree on pn2,
  which will call EmitNameOp, which will call BindNameToSlot.

- Changed each EmitAtomOp and EmitElemOp call site to hard-code the op,
  and add assertions that I'm not changing the behavior.

Comment 6

[Jason Orendorff [:jorendorff]]

Attachment: Part 2 - Don't even set the pn_op field of PNK_DOT/ELEM nodes

Comment 7

[Jason Orendorff [:jorendorff]]

Attachment: Part 3 - Previous patch unchanged except for line numbers

Comment 8

[Jeff Walden [:Waldo]]

Comment on attachment 766165 [details] [diff] [review]
Part 1 - Don't use pn_op of PNK_DOT/ELEM nodes

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

This looks reasonably right, although I'm not 100% confident in its exact correctness.  My puny mind cannot fully comprehend all the twistings of this at once, sadly, but that's why we have tests and fuzzers.  :-)  Let's lean on them more!

::: js/src/frontend/BytecodeEmitter.cpp
@@ -1861,5 @@
>      return true;
>  }
>  
>  static bool
> -EmitPropLHS(JSContext *cx, ParseNode *pn, JSOp *op, BytecodeEmitter *bce, bool callContext)

Yayayayayayayay callContext goes away!  \o/

Comment 9

[Jeff Walden [:Waldo]]

Comment on attachment 766166 [details] [diff] [review]
Part 2 - Don't even set the pn_op field of PNK_DOT/ELEM nodes

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

\o/ \o/ \o/

Comment 10

[Jeff Walden [:Waldo]]

Comment on attachment 766168 [details] [diff] [review]
Part 3 - Previous patch unchanged except for line numbers

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

\o/ \o/ \o/

Comment 11

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/3f152e51be2b
https://hg.mozilla.org/mozilla-central/rev/5428fa083db3
https://hg.mozilla.org/mozilla-central/rev/c39ede0eea8f

Comment 12

[Jason Orendorff [:jorendorff]]

This caused a perf regression (bug 887266) so I backed it out.

But I know what it is. Patch coming.

Comment 13

[Jason Orendorff [:jorendorff]]

Attachment: Part 2 - Don't even set the pn_op field of PNK_DOT/ELEM nodes, v2

The interdiff from v1 is:

>diff --git a/js/src/frontend/ParseNode.h b/js/src/frontend/ParseNode.h
>--- a/js/src/frontend/ParseNode.h
>+++ b/js/src/frontend/ParseNode.h
>@@ -789,0 +789,5 @@ class ParseNode
>+    template <class NodeType>
>+    inline bool is() const {
>+        return NodeType::test(*this);
>+    }
>+
>
>diff --git a/js/src/frontend/FullParseHandler.h b/js/src/frontend/FullParseHandler.h
>--- a/js/src/frontend/FullParseHandler.h
>+++ b/js/src/frontend/FullParseHandler.h
>     PropertyName *isGetProp(ParseNode *pn) {
>-        return pn->isOp(JSOP_GETPROP) ? pn->pn_atom->asPropertyName() : NULL;
>+        return pn->is<PropertyAccess>() ? &pn->as<PropertyAccess>().name() : NULL;
>     }

Comment 14

[Luke Wagner [:luke]]

Ahh, the f.apply optimization...

Various people have remarked recently that it would be nice if we had an API in shell so that we could test whether various optimizations were applied and this is another case where it would have been nice to get a simple jit_test failure.  The old thing we exposed for trace tests was extremely fickle, but I bet we could do better than that.

Comment 15

[Jeff Walden [:Waldo]]

Comment on attachment 768162 [details] [diff] [review]
Part 2 - Don't even set the pn_op field of PNK_DOT/ELEM nodes, v2

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

Boooooo, isOp.

Comment 16

[Jason Orendorff [:jorendorff]]

In bug 887266 Hannes says that the *backout* also caused perf regressions! I can't find evidence of this on awfy but I'm sure I'm just not looking in the right place. In the meantime I'll investigate bug 888002 and see if we can get this re-landed...

Comment 17

[Jason Orendorff [:jorendorff]]

Our frontend is a bit brittle, it seems. :(

Removing the FoldConstants call in Parser::unaryExpr() changed the behavior of a bug that I didn't know we had. The new behavior triggered an assertion instead of just user-visible non-spec-compliant behavior.

I've filed a patch to fix that newly discovered bug *and* re-remove the FoldConstants call in bug 888002.

Comment 18

[Jason Orendorff [:jorendorff]]

Resummarizing. This bug will only remove one FoldConstants call; the other one bites the dust in 888002.

Comment 19

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/bcd0568981d6
https://hg.mozilla.org/mozilla-central/rev/41740f0ba78d
https://hg.mozilla.org/mozilla-central/rev/32c80f595de5