539144 - make fp->argv a (jit-time) constant offset from fp; rm argv/argc/fun/script/thisv

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Luke Wagner [:luke]]

Once JSStackFrames and values are stored in the same contiguous buffer (part of bug 536275), it is desirable to access a function's arguments as a negative constant offset from fp, instead of indirectly through fp->argv.  What is holding us back is that callers can pass any number of arguments to the callee which makes the offset to argv[0] variable.

One solution is to store the arguments in reverse order.  This requires either an in-place reverse for every call at JSOP_CALL, which probably isn't cheap, or storing the arguments in reverse order, which has problems with evaluation order.

Another solution is to place the first [0..fun->nargs) on the stack and the additional arguments directly into the Arguments object, since this is the only way these arguments can be accessed.  As a further optimization, the compile-time flag from bug 530650 can be used to ignore extra arguments altogether when there is no arguments object use in the callee.

Once this has been done, we can assume that, if !fp->argsobj, fp->argc == fp->fun->numargs or, if fp->argsobj, that fp->argc == arguments.length.  So, unless I'm missing a use of argc somewhere, we might be able to drop JSStackFrame::argc as well.

Comment 1

[Mike Shaver (:shaver emeritus)]

Somewhere in JSCore's source is a big comment talking about how their stack frame setup does basically this, but I can't find it right now via trac.

Comment 2

[Igor Bukanov]

(In reply to comment #0)
> Another solution is to place the first [0..fun->nargs) on the stack and the
> additional arguments directly into the Arguments object, since this is the only
> way these arguments can be accessed.

This is not true. The arguments can be accessed via either a debugger hook (that can be installed after the function is called) or via a slow native. So the arguments still has to be stored. But the place for them can come after JSStackFrame.

Comment 3

[Brendan Eich [:brendan]]

Can we optimize harder if there's no debugHook set?

/be

Comment 4

[Brendan Eich [:brendan]]

I.e., debugger turns off baseline JIT.

/be

Comment 5

[Mike Shaver (:shaver emeritus)]

I don't think that it's very important to let debuggers inspect excess arguments here.  The use cases are minimal (since the function that's being debugged doesn't consume them, they can't have much effect) and they're available by going up to the calling frame and inspecting values there.

Slow natives are a harder case, though we could make them indicate that they want excess args.  Seems like "optimize away storage of excess arguments" is a different bug, though, and a lower priority one than the primary issue here?

Comment 6

[Luke Wagner [:luke]]

(In reply to comment #1)
Indeed this was inspired by stepping through JSC.

Since the goal is to optimize FUN_INTERPRETED callees, it seems like we could keep passing excess arguments to (all) natives without losing the desired fp[-k] access for JSOP_{GET,SET}ARG.  Natives already primarily access their arguments through the argv/argc function parameters.

Comment 7

[Brendan Eich [:brendan]]

Igor has suggested using a separate space for extra args in previous bugs, which would be a win compared to the "no room in arena, have to relocate argv" status quo. But I agree with shaver: debuggers can look in the caller frame for extra args. We don't even need to reason about debuggers turning off the baseline JIT, at least not for this case.

/be

Comment 8

[Luke Wagner [:luke]]

(In reply to comment #7)
> Igor has suggested using a separate space for extra args in previous bugs,
> which would be a win compared to the "no room in arena, have to relocate argv"
> status quo.

Is there any reason to make this "separate space" not the Arguments object (assuming we can avoid making the Arguments object via the flag in bug 530650)?  We will already avoid "relocate argv" case by moving to a single contiguous buffer.

> But I agree with shaver: debuggers can look in the caller frame for
> extra args.

Well, if the interpreted callee makes no use of arguments (as determined by bug 530650), then I'm proposing these excess arguments be simply popped, never to be seen again.

Comment 9

[Igor Bukanov]

(In reply to comment #8)
> Is there any reason to make this "separate space" not the Arguments object
> (assuming we can avoid making the Arguments object via the flag in bug 530650)?

Yes - the cases like arguments.length and arguments[i] are optimized to separated bytecode JSOP_ARGCNT and JSOP_ARGSUB. They avoids creation the arguments object. Thus to continue to optimize this case the space outside the arguments object should be found.


> Well, if the interpreted callee makes no use of arguments (as determined by bug
> 530650), then I'm proposing these excess arguments be simply popped, never to
> be seen again.

How would interpreter check that the callee does not need extra arguments? Obviously js_Interpret still needs to see if argc > callee.length (unless we introduce a special bytecode for call sites where the compiler can statically proov that argc <= callee.length). 

After this an extra optimization to query whether the caller uses the extra arguments means an extra "if" check. Typically the arguments beyond callee.length are there for a reason (the caller expects that the callee uses the arguments), thus this extra "if" would just slow down this use case.

Comment 10

[Brendan Eich [:brendan]]

JSOP_ARGCNT and JSOP_ARGSUB (the latter is not for arguments[i] where i is a non-constant expression, btw -- only for i a compile-time constant) do help functions such as

function onetwothreeargs(a) {
  var b = (arguments.length >= 2) ? arguments[1] : default_b;
  var c = (arguments.length >= 3) ? arguments[2] : default_c;
  . . .
}

This was why I added 'em long ago. It would be good to measure their utility now on real browser sessions, but let's say they matter. Then we might want to use a separate area as Igor proposes, or perhaps just round up to some minimum argument count.

The baseline JIT should be able to speculate using PICs so that it knows the arity of the callee, or takes a slow path for unknown-arity callees (which is the way we call now in the bytecode interpreter).

Between these ideas there is probably a way to avoid penalizing onetwothreeargs kinds of functions, while not slowing down the baseline JIT.

/be

Comment 11

[Brendan Eich [:brendan]]

Another point: for direct calls, argc is encoded as an immediate of JSOP_CALL and kin. If a callee needed only argc, it could perhaps dig it up there.

/be

Comment 12

[Luke Wagner [:luke]]

Fixing this would also be good for the dual-stack layout, obviating the need for a new JSStackFrame::argvTypes.

I talked today with dvander and brendan about keeping a side stack which is only used for overflow arguments and replacing fp->argv with a maybe-null pointer to the overflow.

On a side note, we discovered today that even functions that don't create aliases to arguments, allocate an arguments object.  Perhaps this could be fixed using the static analysis in bug 530650.

Comment 13

[Luke Wagner [:luke]]

An even simpler/better idea is what JSC does, which is to dup [0, fun->nargs) onto the top of the stack.  This gives args a constant offset from fp while keeping the overflow around.  To get rid of argv/argc, we could push JSVAL_TO_INT(argc) onto the stack between the original and dup'ed arguments and use a frame flag to indicate the overflow.

Comment 14

[Luke Wagner [:luke]]

Attachment: patch

WIP.  Its hard to separate argv/argc/fun/script/thisv removal, so this patch removes them all.  The patch is interp-only, and passes trace/ref tests.  Removing these members means slightly slower access times to rematerialize when requested (from the VM and interpreter, including the interpreter call/return path).  Thankfully, running SS/V8 in interp-only (the worst-case for this patch) shows no slowdown on SS as a whole and a 2% speedup in V8.  So that bodes well for JM.

Comment 16

[Luke Wagner [:luke]]

Attachment: jsinterp.h changes

The above patch, since it is already so-thoroughly mucking with the JSStackFrame interface, takes the opportunity to apply some of the conventions discussed in bug 586533.  (With a few comments to fill in TOODs) JSStackFrame should now actually be somewhat readable.

Brendan, feedback?

Comment 17

[Luke Wagner [:luke]]

Attachment: WIP

This patch contains passes trace/ref tests with the tracer.  This bug now depends on JM landing since, for simplicity, the patch completely ignores (#if 0's off) recursion.  Although the main beneficiary of the patch is JM, TM shows a 3% (19ms) speedup on SS (with recursion off, of course).  Next up, try server and a patch for JM.

One note: to avoid messing with really delicate native stack offset computations associated with upvars, I turned off some of the rare (never hit on SS/V8) upvar paths.  With PICs, JM should be able to do well and, in some cases, better than the tracer for these upvar paths.

Comment 18

[Luke Wagner [:luke]]

Attachment: WIP 2

Got try server green for trace-jit only.  method-jit compilers and runs simple code using arguments, but need to focus on inline call path or just wait until script ICs land and fix it for that.

Comment 19

[Luke Wagner [:luke]]

Attachment: WIP 3

Rebased over JM and passing trace/ref tests with j and jm.  Have to fix some constants for non-x86 non-gnu platforms.  Also testing on try.

I am getting wild perf variations that show slight improvement.  I didn't even try to optimize the JM call path since dvander is about to rewrite/inline it in bug 587698, which should make all this more important.

Comment 20

[Luke Wagner [:luke]]

Even without the optimizations dvander's going to add in bug 592976, for this micro-benchmark:

function f(x,y,z) {
    for (var i = 0; i < 10000000; ++i) {
        x = y + z;
        y = x + z;
    }
}

var bef = new Date();
f(1,2,3);
var aft = new Date();
print(aft - bef);

I'm measuring a drop from 91ms to 68ms.

Comment 21

[Luke Wagner [:luke]]

Attachment: WIP

Fixed bug from test (putting result of thisObject hook into non-canonical this in argument overflow case).  Going to try-server again and get reviews.

Comment 22

[Luke Wagner [:luke]]

Attachment: WIP 5

Fixed JM-rebase bug on x64 and compile error on ARM.

Comment 23

[Luke Wagner [:luke]]

Attachment: WIP 6

Rebasing over scripted ICs

Comment 24

[Luke Wagner [:luke]]

Attachment: SS / V8 results for method-jit only

WIP 6 passes trace and ref tests.  Perf results for *method-jit only* on x86 linux are attached: SS shows a 1.9% speedup V8 shows a 7.5% speedup.  So that's good.

With JM+TM, I see a 1.4% speedup on SS, but a 1% slowdown on V8, mostly from one benchmark (raytrace) with a 8.6% slowdown and another (splay) that is 3% slower.  I'm pretty sure this is a bug that is affecting what traces or how we connect traces or something... investigating.

Comment 25

[Luke Wagner [:luke]]

Attachment: WIP 7

So the v8-raytrace regression was caused a bug fix rolled into this patch.  Filed bug 594621 on this.  This bug fix also makes SS faster, so taking it out lowered the -jm SS score.  With -m, I'm now getting SS is 2% faster and V8 is 9.2% faster.  With -jm, I get SS a wash and V8 .8% faster.

Comment 26

[Luke Wagner [:luke]]

Attachment: WIP 8

Adding an "underflow" tag (to the existing "overflow" tag) means we can even skip writing nactual when nactual == nformal.  Doing that and adding the 3 lines of code to make JSStackFrame::annotation lazy bring the speedup to 3.7% on SS and 9.9% on V8 (with -m).

Comment 27

[Luke Wagner [:luke]]

Attachment: updated SS / V8 results for method-jit only

Comment 28

[Brendan Eich [:brendan]]

Yeehaw! Go Texas!

/be

Comment 29

[Luke Wagner [:luke]]

Attachment: patch

Try server is looking green so time for review.  The patch is smaller than the size implies: a large portion is simple renamings, so I'm just going to have Brendan review jsinterp.h as a whole and then cut out all the actual renaming fluff.

Comment 30

[Luke Wagner [:luke]]

Attachment: jsinterp.h / jsinterpinlines.h changes

Comment 31

[Brendan Eich [:brendan]]

Comment on attachment 473743 [details] [diff] [review]
jsinterp.h / jsinterpinlines.h changes

>+    JSFRAME_FUNCTION           = 0x10000, /* frame pushed for a function invocation */

Does "function invocation" imply non-native clearly now? I know it does in the code, just wondering if the comment should say so. I'm not looking for a flag name change.

>+    JSStackFrame        *down_;         /* previous cx->regs->fp */

Since you are touching down uses, would you be willing to rename? "upvars" has stuck but it conflicts with "down" for the dynamic link. "dynamicLink" or "dlink" or "link" or "back" (backtrace)?

>+    /* TODO: remove */
>+    void                *ncode_;
>+    JSVersion           callerVersion_; /* bug 535912 */
>+    JSObject            *blockChain_;   /* bug 540675 */
>+
>+#if JS_BITS_PER_WORD == 32
>+    void                *padding;
>+#endif

These will all go, eh?


>+    /*
>+     * Down-frame
>+     *
>+     * A frame's 'down' frame is either null or the previous frame pointed to
>+     * by cx->regs->fp when this frame was pushed. Often, given two down-linked
>+     * frames, the up-frame is a function or eval that was called by the
>+     * down-frame, but not always: the down-frame may have called a native that
>+     * reentered the VM through JS_CallFunctionValue on the same context
>+     * (without calling JS_SaveFrameChain) which pushed the up-frame. Thus,
>+     * 'down' has little semantic meaning and basically just tells the VM the
>+     * what to set cx->regs->fp to when this frame is popped.

"savedfp" or "savefp" (name mongering still).

>+     */
>+

Nit: no need here or below in similar situations to add a blank line.

>+    JSScript *script() const {
>+        JS_ASSERT(isScriptFrame());
>+        return isFunctionFrame() ? isEvalFrame() ? args.script
>+                                                 : fun()->script()
>+                                 : exec.script;

Right-heavy ?: style is not typical. Try underhanging the outer ? and : below the 'i' in 'isFunctionFrame()' and put the inner ?: all on the same line?

>+    /*
>+     * Arguments
>+     *
>+     * Only non-eval function frames have arguments. A frame follows its
>+     * arguments contiguously in memory. The arguments pushed by the caller are
>+     * the 'actual' arguments. The declared arguments of the callee are the
>+     * 'formal' arguments. These two sets of arguments may be disjoint when the
>+     * caller pushes too many (actual) arguments and, to maintain the invariant
>+     * that formal argument #1 is -fun->nargs values behind &fp, the engine
>+     * copies the (formal) [0, fun->nargs) subset to the top of the stack.

This copy happens only if there are too many actuals, but you didn't say that explicitly. Worth doing to avoid confusion -- it reads as though we always copy.

>+     * Since the subset of arguments is potentially on the stack twice, it is
>+     * important for all reads/writes to refer to the same canonical memory
>+     * location which we define to be the formal argument.

s/which/that/ here and elsewhere for defining clauses.

>-    JSObject* getArgsObj() const {
>+    JSObject& argsObj() const {
>         JS_ASSERT(hasArgsObj());
>         JS_ASSERT(!isEvalFrame());
>-        return argsobj;
>+        return *args.obj;
>     }
> 
>     JSObject* maybeArgsObj() const {
>-        return argsobj;
>+        return hasArgsObj() ? &argsObj() : NULL;
>     }

Declarator mode style deviations here.

>+    /*
>+     * This
>+     *

Sentence cut off. Oops, I forgot to cite it but earlier, you have a "the what" wrong word glitch, split across a line IIRC (look for ' * what').

>+     * Every frame has a this value although, until 'this' is computed, the
>+     * value may not be the semantically-correct 'this' value.
>+     *
>+     * The 'this' value is stored before the formal arguments for function
>+     * frames and directly before the frame for global frames. The *Args
>+     * members assert !isEvalFrame(), so reimplement.

Who reimplements, or should? Oh, you mean "we implement specialized inline methods" -- say that?

>+    /*
>+     * Scope chain
>+     *
>+     * Every frame has a scopeChain, the root of which represents the current

Root implies linkage direction, which is up the tree, linked via the parent slot -- worth commenting on these facts.

>+     * global object. A 'call object' is a node on a scope chain representing
>+     * a function's activation record. A call object is used for dynamically-
>+     * scoped name lookups and holds the values of locals and arguments when a
>+     * function returns (and its stack frame is popped).

Call objects are not only for dynamic scope (eval, with) -- they are also for staticly-scoped upvars in closures that we couldn't optimize.

> For performance
>+     * reasons, call objects are created lazily on demand, so a given function
>+     * frame may or may not have a call object.

Important also to note that lightweight functions should not get Call objects.

>                                                 When a function does have a call
>+     * object, it is found by walking up the scope chain until the first call
>+     * object. Thus, it is important, when setting the scope chain, to indicate
>+     * whether the new scope chain contains a new call object and thus changes
>+     * the state of the 'hasCallObj' state.

"state of the ... state" -- second "state" could be "result", or lose "state of the".

>+    JSObject& callObj() const {
>+        JS_ASSERT(hasCallObj());
>+        JSObject *pobj = &scopeChain();
>+        while (JS_UNLIKELY(pobj->getClass() != &js_CallClass))
>+            pobj = pobj->getParent();

Assert before updating pobj that js_IsCacheableNonGlobalScope(pobj) || pobj->isWith() ?

(Test me here!)

>+    /* Annotation */
>+
>+    void* annotation() const {
>+        return (flags & JSFRAME_HAS_ANNOTATION) ? annotation_ : NULL;
>+    }
>+
>+    void setAnnotation(void *annot) {
>+        flags |= JSFRAME_HAS_ANNOTATION;
>+        annotation_ = annot;
>+    }
>+

FIXME citing bug to get rid of this carbuncle from the Java / Netscape 4 daze?

>+    /*
>+     * Generator-specific members
>+     *
>+     * A non-eval function frame may optionally be the activation of a
>+     * generator. For the most part, generator frames act like ordinary frames.
>+     * For exceptions, see js_FloatingFrameIfGenerator.

There's a bug asking for js_ elimination by namespace js, if not a better OOP-method home. In this case, if you end up touching js_FloatingFrameIfGenerator (or just for a later bug), how about making it a method of JSContext?

[jsinterpinlines.h inline methods deleted -- great to see the formerly-open-coded frame setup abstracted and tidied up!]

>+inline js::Value &
>+JSStackFrame::canonicalActualArg(uintN i) const {

Nit: { on new line in col. 1.

Looks great, r=me with nitpicks.

/be

Comment 32

[Luke Wagner [:luke]]

Attachment: patch minus syntactic changes implied by jsinterp.h changes

Comment 33

[Luke Wagner [:luke]]

(In reply to comment #31)

Thanks!

> >+    /* TODO: remove */
> >+    void                *ncode_;
> >+    JSVersion           callerVersion_; /* bug 535912 */
> >+    JSObject            *blockChain_;   /* bug 540675 */
> >+
> >+#if JS_BITS_PER_WORD == 32
> >+    void                *padding;
> >+#endif
> 
> These will all go, eh?

Yes.  callerVersion is already gone!

> >+     * 'formal' arguments. These two sets of arguments may be disjoint when the
> >+     * caller pushes too many (actual) arguments and, to maintain the invariant
> >+     * that formal argument #1 is -fun->nargs values behind &fp, the engine
> >+     * copies the (formal) [0, fun->nargs) subset to the top of the stack.
> 
> This copy happens only if there are too many actuals, but you didn't say that
> explicitly. Worth doing to avoid confusion -- it reads as though we always
> copy.

Good point.  I tried to say that with "these two sets may be disjoint if ...", but that is rather indirect.

Comment 34

[Luke Wagner [:luke]]

Hah!  I was measuring v8 with the SS harness using --args=-jm, which just does -j.  (I thought the reason early-boyer was so slow was the JM-TM integration bug that was recently fixed.)  So with --args='-j -m', I get a 4.5% speedup on V8:

** TOTAL **:      1.046x as fast    2224.1ms +/- 0.3%   2126.3ms +/- 0.4%

=============================================================================

  v8:             1.046x as fast    2224.1ms +/- 0.3%   2126.3ms +/- 0.4%
    crypto:       1.111x as fast     299.2ms +/- 3.6%    269.4ms +/- 1.6%
    deltablue:    1.069x as fast     401.8ms +/- 0.7%    375.7ms +/- 1.2%
    earley-boyer: 1.094x as fast     348.2ms +/- 0.3%    318.3ms +/- 0.2%
    raytrace:     1.018x as fast     371.2ms +/- 1.4%    364.5ms +/- 1.4%
    regexp:       -                  245.9ms +/- 0.2%    245.8ms +/- 0.2% 
    richards:     -                  214.8ms +/- 1.1%    214.3ms +/- 0.7% 
    splay:        1.014x as fast     343.0ms +/- 0.8%    338.3ms +/- 1.0%

Comment 35

[Brendan Eich [:brendan]]

(In reply to comment #33)
> Good point.  I tried to say that with "these two sets may be disjoint if ...",
> but that is rather indirect.

(Nerd! :-P)

Seriously, the set-disjointness understates the situation, which involves order and concrete memory adjacency vs. non-adjacency. Best to keep it real, Plato.

/be

Comment 36

[Luke Wagner [:luke]]

(In reply to comment #35)
Thanks, Hilbert.

Comment 37

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 473780 [details] [diff] [review]
patch minus syntactic changes implied by jsinterp.h changes

This patch is beautiful, and not just because of the monster ASCII comment. I'm up to the tracer & interp changes, so dumping methodjit comments here for posterity (most discussed IRL already).

> class InlineFrameAssembler {
...
>     uint32     argc;            // number of args being passed to the function

Nit: argc looks unused now.

>+stubs::CompileFunction(VMFrame &f, uint32 nactual)
...
>-    f.regs.fp = fp;

This is technically safe because FixupArity() sets regs.fp, and the JIT'd call to CompileFunction() sets regs.fp as well. But we should probably explicitly document this.

> void * JS_FASTCALL
> stubs::UncachedNew(VMFrame &f, uint32 argc)
> {
...
>-            void *ret;
>-            if (!UncachedInlineCall(f, JSFRAME_CONSTRUCTING, &ret, argc))
>-                THROWV(NULL);

This will cause scripted |new| to Invoke() every time in debug mode, so we should keep the inline calls here.

>+template <class Op>
>+inline void
>+JSStackFrame::forEachCanonicalActualArg(Op op)

I really like this pattern.

Comment 38

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 473780 [details] [diff] [review]
patch minus syntactic changes implied by jsinterp.h changes

r=me on tracer part, though a comment explaining visitFrameObjPtr would be nice. It took me a minute to track down what was going on there.

>                 guard(true,
>-                      addName(lir->ins2(LIR_lti, idx_ins, INS_CONST(afp->numActualArgs())),
>+                      addName(lir->ins2(LIR_andi,
>+                                        lir->ins2(LIR_gei, idx_ins, INS_CONST(0)),
>+                                        lir->ins2(LIR_lti, idx_ins, INS_CONST(afp->numActualArgs()))),
>                               "guard(upvar index in range)"),
>-                      exit);
>+                      MISMATCH_EXIT);

Nit that looks pre-existing: s/upvar/argument/
Another nit: This could be an unsigned comparison.

>-                guard(true, lir->ins2(LIR_ltui, idx_ins, INS_CONST(afp->numActualArgs())),
>-                      snapshot(BRANCH_EXIT));

This is safe because of the above guard, right? So maybe just replace that one with this shorter one.

>-        *p = *(JSObject **)mStack;
>+            JSObject *frameobj = *(JSObject **)mStack;
>+        JS_ASSERT((frameobj == NULL) == (*mTypeMap == JSVAL_TYPE_NULL));
>+        if (p == fp->addressOfArgs()) {

Nit: weird indentation.

Comment 39

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 473780 [details] [diff] [review]
patch minus syntactic changes implied by jsinterp.h changes

>+     * TODO: comment
>+    inline Value *getStackLimit(JSContext *cx);

Nit: TODO

Comment 40

[Luke Wagner [:luke]]

Many thanks for the careful review!

http://hg.mozilla.org/tracemonkey/rev/8721b595e7ab

Comment 41

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/8721b595e7ab