445363 - Proper Tail Calls for the trace JIT

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, enhancement, P3)

Description

[Peter Michaux]

User-Agent:       Mozilla/5.0 (Macintosh; U; Intel Mac OS X; en-US; rv:1.8.1.15) Gecko/20080623 Firefox/2.0.0.15
Build Identifier: "Mozilla/5.0 (Macintosh; U; Intel Mac OS X; en-US; rv:1.8.1.15) Gecko/20080623 Firefox/2.0.0.15"

Proper tail calls (aka tail call elimination) was part of the ES4 proposal at various times. Currently proper tail calls are out of the proposal. Its apparent that multiple people are interested in proper tail calls being part of the language. Brendan Eich says that "tail calls are free with a tracing JIT."

Clearly proper tail calls open the doors to new programming techniques not currently possible with JavaScript. Hopefully those doors will be opened for JavaScript programmers. 



Reproducible: Always

Steps to Reproduce:
1. 
2. 
3.

Comment 1

[Brendan Eich [:brendan]]

Blake, were you interested in taking this on?

/be

Comment 2

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

arguments.callee.caller.arguments will currently get the arguments of the immediate caller, which I presume would be somewhat wrong in the case of proper tail calls.

I'm OK with that, as ECMA seems to be, but wanted to make sure that we were explicit about it.

Comment 3

[Blake Kaplan (:mrbkap) (inactive)]

We could avoid that by avoiding tail calls on heavyweight functions.

Comment 4

[Peter Michaux]

What is a "heavyweight function" and how would the programmer know one when he sees one?

I really think tail calls should be an all-the-way implementation. If a call is in tail position it automatically uses tail call elimination.

I understand backwards compatibility is important and the arguments.callee.caller problem exists with tail calls; however, the caller property has been considered deprecated for quite some time. Firefox, IE, and Safari do have the caller feature but Opera does not. Given it has been deprecated ages ago and not even available in all four main browser, the use of the caller property must be very rare.

Thinking of backwards compatibly...

Another likely similarly rare situation has been addressed in ES4 where an inner function's "this" is automatically set to the containing function's "this" rather than referencing the global object. (For some reason this is considered a bug fix when it really is exactly the expected behavior.) I can imagine there is some program out there where some one intentionally wanted the inner function's "this" to reference the global object. In the interest of improving JavaScript, it was decided that it was ok to break backwards compatibility of an obscure feature.  

I know some programmers who have been using some of the new, not-previously reserved keywords in ES4 and are dreading the switch. Again backwards compatibility sacrificed.

I mention these examples simply because the precedent for breaking backwards compatibility has been set and personally I don't see breaking the "caller" property to be as major. Some of the other existing features that were never deprecated and were available in all the major browsers are going to be broken soon.

Comment 5

[Brendan Eich [:brendan]]

Peter (sorry for delayed reply): there's no way we will break compatibility in implementing this. For ES as specified, it's an optimization only, not a storage guarantee. So transparent to user code.

The URL points to a nice spec, which looks right to me.

/be

Comment 6

[Brendan Eich [:brendan]]

Attachment: everything except the interpreter code to do the tail call

I think I'll do that and declare victory in this bug, and let dvander do the JIT work in the bug this bug blocks. Attaching now to get early eyes on the patch.

/be

Comment 7

[Brendan Eich [:brendan]]

Comment on attachment 403931 [details] [diff] [review]
everything except the interpreter code to do the tail call

Debugging, improving... new patch coming.

/be

Comment 8

[Brendan Eich [:brendan]]

Attachment: patch, everything but the JIT

Big fun. Want to get the JIT part before landing, but need dvander.

/be

Comment 9

[Brendan Eich [:brendan]]

  staticCalls = 58, 
  staticTailCalls = 6, 
  dynamicCalls = 20104, 
  dynamicTailCalls = 820, 
  ...

Possibly JSOP_TCALL misses too often, given dynamic spread vs. static. Will dig further tomorrow.

/be

Comment 10

[Brendan Eich [:brendan]]

Attachment: patch, more metering plus a display maintenance fix

t/3d-cube.js selected runtime counters:

  staticCalls = 58, 
  staticTailCalls = 6, 
  dynamicCalls = 20104, 
  dynamicTailCalls = 820, 
  tcallBadArgc = 0, 
  tcallBadNargs = 0, 
  tcallBadNslots = 412, 
  tcallBadVersion = 0, 
  tcallDebugging = 0, 

So nslots is not enough in the caller frame for the callee to take over. But this is easy to remedy with some rounding up or even extension if room in the arena. More tomorrow.

/be

Comment 11

[Boris Zbarsky [:bzbarsky]]

So looking at the interp code here, this really does clobber the calling fp, right?  Since it's a tail call, I guess it's not a problem for things like enablePrivilege.  But what about firebug (and for that matter DumpJSStack) stack traces?

Comment 12

[Brendan Eich [:brendan]]

(In reply to comment #11)
> So looking at the interp code here, this really does clobber the calling fp,
> right?  Since it's a tail call, I guess it's not a problem for things like
> enablePrivilege.  But what about firebug (and for that matter DumpJSStack)
> stack traces?

Read the patch carefully, notice

+                        !cx->debugHooks->callHook)

This is probably enough, but if not, it may be we don't care -- Waldo and I were talking about this last night. TCO does change a debugger's view of the stack. Optimization vs. debugging. But for now I hope to avoid acting on the JSOP_TCALL if the debugger is hooking into calls.

/be

Comment 13

[Brendan Eich [:brendan]]

Attachment: claim more slots for the new frame if they are available

Blake, hope you can review. Couple of sticky issues, see the FIXME: comments in jsops.cpp (want to fix both, must fix the latter before declaring victory here).

/be

Comment 14

[Jeff Walden [:Waldo]]

(In reply to comment #12)
> This is probably enough, but if not, it may be we don't care -- Waldo and I
> were talking about this last night.

To elaborate: Function.prototype.caller is extension-land, not part of any spec, nice-to-have, worth preserving wherever possible, but not important enough to sacrifice potential large perf wins.  Even here the plan is for it still to be present, just with intermediate frames elided, so a reasonably informative stack is still available.  Users can figure out the missing frames themselves, possibly by inspection, perhaps by more intrusive changes -- but if they're incapable of both, they probably shouldn't be using recursion.  :-)

Comment 15

[Brendan Eich [:brendan]]

Attachment: correct display non-maintenance, conditioned on rejecting optimized closure callee at greater static level

Comment 16

[Brendan Eich [:brendan]]

(In reply to comment #14)
> they're incapable of both, they probably shouldn't be using recursion.  :-)

Tail call optimization applies to non-recursive calls too, though. But your point about caller having gaps but still being useful still stands.

/be

Comment 17

[Peter Michaux]

It seems as though there is still interest in tail call elimination but if there is not going to be a guarantee then a programmer cannot make use of this change. Is there a plan to make this optimization guaranteed so programmers can count on it and program in a recursive style? Maybe I'm misunderstanding Brendan's comment #5 above about storage guarantees.

Comment 18

[Brendan Eich [:brendan]]

Peter: the guarantee would be a language change, so you need to go to es-discuss. The last time we beat this to death, some TC39 members (Waldemar in particular) opposed any mandatory proper tail call semantics in ECMAScript.

That leaves this as an optimization, which requires nothing for programmers to "make use of this change". That's the topic of this bug, and not a concern for any programmmer. It's like tracing, polymorphic inline caching, loop unrolling, etc. etc.

/be

Comment 19

[Brendan Eich [:brendan]]

Again I'm agreeing with Jeff about fun.caller. It already does not trace recursive cycles accurately (consider mutual recursion) since the property is a pigeon-hole on functions, not on activations. It is not a reliable complete back-trace mechanism, and it's non-standard.

/be

Comment 20

[Brendan Eich [:brendan]]

Oh, and ES5 strict mode poison-pills .caller on functions and arguments objects with throwing getters.

/be

Comment 21

[Boris Zbarsky [:bzbarsky]]

So.. I'm not very good at reading the jsparse code.  Do we emit a TCALL only when the function ends with |return foo()|?  Or also if there's a |return foo()| somewhere partway through the function?

Comment 22

[Brendan Eich [:brendan]]

bz: see the URL, the spec is good (a few minor bugs, I'll edit fixes in tomorrow) and it works as you expect:

js> function f(x){if(x) return g(); return h();}
js> dis(f)
flags: NULL_CLOSURE
main:
00000:  trace
00001:  getarg 0
00004:  ifeq 14 (10)
00007:  callname "g"
00010:  tcall 0
00013:  return
00014:  callname "h"
00017:  tcall 0
00020:  return
00021:  stop

Source notes:
  0:     4 [   4] if      
  1:    10 [   6] pcbase   offset 3
  3:    17 [   7] pcbase   offset 3

The parser builds the AST, the emitter walks it, and we pre-order push down pn_wrapped (if in a try or let block/expr) and compute pn_tailpos appropriately (either inherited, or determined completely by the statement form). Thus the emitter code for a TOK_LP (left-paren is the tree type for a call expression) can specialize from JSOP_CALL to JSOP_TCALL, and the emitter code for TOK_RETURN can worry about pn_wrapped (by setting pn2->pn_tailpos = !pn->pn_wrapped).

/be

Comment 23

[Peter Michaux]

Brendan,

Maybe there is a bit of a misunderstanding about the intention of why I started this ticket. I hope you don't read this comment as argumentative or overly pedantic. I'm differentiating between ECMAScript and JavaScript to be specific.

I'm not sure why you bring up ECMAScript the way you do. For the time being the ECMAScript committee isn't interested in guarrenting tail call elimination in the ECMAScript language. From what I remember, you suggested that implementers leading the way by implementing tail call elimination might change the committees opinion in the future. I read that as meaning implementers would lead the way by guaranteeing tail call elimination in their own languages (i.e. JavaScript, JScript, etc). That is why I started this ticket. To try to get a first implementation to make the guarantee.

If JavaScript implements tail call elimination but doesn't guarantee it then what has been gained? A programmer cannot program in a recursive style without the guarantee but call stack information is lost for calls in tail position. For a competent programmer it is getting the worst of both sides. It is true the optimization may have some minor benefits. Maybe avoid stack overflow in some cases but that is not an issue people encounter currently when programming in a non-recursive style. Maybe an incompetent programmer would program in a recursive style and the optimization would save them but if they don't know what they are doing then they are just getting by on luck anyway.

If the JavaScript language guarantees tail call elimination then if I am programming specifically for JavaScript then I can program in a recursive style. If I'm programming for the web at large I still could not until all the browsers make the guarantee. That is what leading the way is all about. Others will hopefully follow in the future.

What I'm trying to say is this ticket was to get JavaScript to have a language change (i.e. making the guarantee) that is within the bounds of the current ECMAScript standard. The ECMAScript standard is not part of this ticket and the process to change that language is separate.

Comment 24

[Boris Zbarsky [:bzbarsky]]

Brendan, sounds (and looks from that dis output) like the answer to the second question in comment 21 is yes.

My concern is basically that I end up doing DumpJSStack() a fair amount when debugging various things; usually I only care about the top frame but about 10% of the time I need to figure out who called it and why.  With this setup, it looks like code like this:

  function f(x) {
    if (x) return g(x); return g(x+1);
  }

wouldn't let me reconstruct from the DumpJSStack output whether f was called with 0 or 1 as the argument.  This might not be an issue, but maybe we should consider a (debug-build-only?) way of disabling tail-call optimization without setting up a debugger hook somehow from inside gdb.

Comment 25

[Brendan Eich [:brendan]]

(In reply to comment #23)
> Brendan,
> 
> Maybe there is a bit of a misunderstanding about the intention of why I started
> this ticket. I hope you don't read this comment as argumentative or overly
> pedantic. I'm differentiating between ECMAScript and JavaScript to be specific.

This bug's product and component are "Core / JavaScript Engine", not "JS language definition". More below.

Of course I cited (via the URL) the ES4-era spec (which is about ES3, it does not include let blocks/exprs) from wiki.ecmascript.org, so there is a specified design here, not just random hacking.

Sorry if I seemed to hijack this bug, but it has to be about code change to be valid in bugzilla.mozilla.org, and I'm going to make best use of it.

> I'm not sure why you bring up ECMAScript the way you do. For the time being the
> ECMAScript committee isn't interested in guarrenting tail call elimination in
> the ECMAScript language. From what I remember, you suggested that implementers
> leading the way by implementing tail call elimination might change the
> committees opinion in the future.

I agree that fixing this bug is a shot worth taking for several reasons, but we should be clear about how the game works. It's a competitive gambit. It has to pay off in the market to be anything more than an optimization which we would probably keep, even guarantee, but which wouldn't have teeth in any standard if the gambit fails.

The gambit could also backfire on its own as an optimization, if too many users object to ellipses in stack dumps.

But in the best case, if programmers prefer engines that do "TCO" then we may push for "PTC" as a guaranteed language semantic. We can't get PTC through Ecma TC39 right now, IMHO. We have other good reasons to want TCO. So that's what this bug is about.

> I read that as meaning implementers would
> lead the way by guaranteeing tail call elimination in their own languages (i.e.
> JavaScript, JScript, etc). That is why I started this ticket. To try to get a
> first implementation to make the guarantee.

Let's have the implementation first. Your comment 17 is out of order just in terms of work flow. I can't guarantee something not yet implemented.

> What I'm trying to say is this ticket was to get JavaScript to have a language
> change (i.e. making the guarantee) that is within the bounds of the current
> ECMAScript standard. The ECMAScript standard is not part of this ticket and the
> process to change that language is separate.

There is no process to change the JavaScript language definition other than to do what we've done in the past: propose through ecmascript.org (e.g. Lars's tail call spec linked from this bug's URL), implement in SpiderMonkey (and also in Rhino, note that it does JS1.8 now too).

So again, I still think our best course is to focus on implementation and not put cart before horse or spend too many words on "guarantees".

/be

Comment 26

[Brendan Eich [:brendan]]

There may be a case for explicit tail call syntax. See

http://bugs.ecmascript.org/ticket/323

and the es-discuss post cited in the next to last comment:

https://mail.mozilla.org/pipermail/es-discuss/2008-January/001837.html

But explicit syntax was going down when last seen in the ticket and mailing list, and this bug is not about adding it. I mention it because it would allow "opt-in" by programmers who didn't care about their own stack traces' readability. But a stack backtrace is usually read by someone other than the original programmer!

bz's comment 24 deserves more thought and even experience, so again I ask that we get this patch in and work on stack backtracing after, and only if necessary.

/be

Comment 27

[Brendan Eich [:brendan]]

I should credit Dave Herman along with Lars Hansen for the spec at the URL.

/be

Comment 28

[Brendan Eich [:brendan]]

I wrote "ellipses in stack dumps" in comment 25 on purpose. We can tell when a tail call has happened while walking the stack, so the Error object's "stack" property, and other such things, can insert some kind of "...". Comments?

/be

Comment 29

[Brendan Eich [:brendan]]

Attachment: better optimized closure screening

Comment 30

[Jeff Walden [:Waldo]]

(In reply to comment #28)
> I wrote "ellipses in stack dumps" in comment 25 on purpose. We can tell when a
> tail call has happened while walking the stack, so the Error object's "stack"
> property, and other such things, can insert some kind of "...". Comments?

Seems reasonable, with syntax considerations regarding what web code might expect the stack property to contain.

In the realm of "things we could consider if everybody and their mother complains that vociferously", we could implement a "use moz-disable-tailcalls" directive to not emit tail calls during bytecode generation.  (I don't think any effort should be spent on such a thing unless we actually heard an excess of complaining.)

Comment 31

[Brendan Eich [:brendan]]

Latest path, no ellipsis, /tmp/ojs is an unpatched shell:

$ cat tc.js
function f1() f2();
function f2() f3();
function f3() { throw new Error("hi"); }
try { f1(); } catch (e) { print(e.stack); }

$ /tmp/ojs !$
/tmp/ojs tc.js
Error("hi")@:0
f3()@tc.js:3
f2()@tc.js:2
f1()@tc.js:1
@tc.js:4

$ ./Darwin_DBG.OBJ/js !$
./Darwin_DBG.OBJ/js tc.js
Error("hi")@:0
f3()@tc.js:3
@tc.js:4

The formatting of e.stack is designed so you can say e.stack.split('\n') to get an array of strings, each string describing a frame; and the frame strings can be split on @ to separate a call expression from filename:lineNumber pair, etc.

Literal ellipsis would give

Error("hi")@:0
f3()@tc.js:3
...
@tc.js:4

and be readable and clear by standard rules of ellipses. No @ or : separators to mislead. This seems usable for those who know what to look for, and a breaking change to provoke changes in code that consumes stack property string values.

The dilemma is whether breaking such code provokes change or just bugs biting users who are third parties to our first party and webdevs' second party.

The alternative that keeps code "working" would look like

Error("hi")@:0
f3()@tc.js:3
...@?:?
@tc.js:4

perhaps, or something even more "compatible" such as ...@?:0 -- but given stack's status as a Mozilla extension, I would rather take door #1 (just ...). Anyone have a better idea?

/be

Comment 32

[Brendan Eich [:brendan]]

Attachment: refreshed patch

Comment 33

[Brendan Eich [:brendan]]

Attachment: refreshed again to track back-out

Comment 34

[Nicholas Nethercote [inactive]]

(In reply to comment #26)
> There may be a case for explicit tail call syntax.

In my last job I programmed in a functional language (Mercury) and more than once wished there was a way to say, via explicit syntax or a pragma or whatever:  "I really need this call to be a tail call, please tell me if you can't make it so and why".

The same feature would be useful for various optimisations that have big effects, eg. loop vectorisation, deforestation.

Just my two cents.

Comment 35

[Nicholas Nethercote [inactive]]

(In reply to comment #34)
> 
> The same feature would be useful for various optimisations that have big
> effects, eg. loop vectorisation, deforestation.

Not that vectorisation and deforestation are necessarily relevant for ECMAScript.  I'm just saying this kind of feature would be potentially useful in a wide range of settings, eg. lots of different language implementations.

Comment 36

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

Attachment: jit part, v1

Patch on top of Brendan's. This actually compiles stuff in controlflow-recursive which is neat. There's still some work to do I think -- Will go over the logic with a fine-toothed comb and benchmark tomorrow.

Comment 37

[Brendan Eich [:brendan]]

Attachment: rebased to tm tip

Comment 38

[Brendan Eich [:brendan]]

Comment on attachment 406361 [details] [diff] [review]
rebased to tm tip

Blake, if you need a break from wrappers, this is a good read.

/be

Comment 39

[Brendan Eich [:brendan]]

Attachment: rebased again plus CloneParseTree fix

Comment 40

[Brendan Eich [:brendan]]

Attachment: fix to consolidate initialization in NewOrRecycledNode

Comment 41

[Brendan Eich [:brendan]]

Attachment: fix another fuzzer-found bug, easy

Bugzilla interdiff should work this time.

/be

Comment 42

[Brendan Eich [:brendan]]

Fuzzer-generated test for last fix:

http://pastebin.mozilla.org/676962

/be

Comment 43

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(In reply to comment #41)
> Created an attachment (id=406797) [details]
> fix another fuzzer-found bug, easy
> 
> Bugzilla interdiff should work this time.
> 
> /be

(function(){with({}){return(l for each(b in[]))}})()

This asserts without -j at Assertion failure: !js_IsActiveWithOrBlock(cx, fp->scopeChain, 0), at ../jsops.cpp:238

I'm quite sure it doesn't occur without the patch. TM tip.

Comment 44

[Brendan Eich [:brendan]]

Attachment: don't forget "with"!

I updated the spec at the bug URL.

Lars Hansen wrote at the bottom of that spec:

"Just noting that the Scheme report requires tail call behavior for apply  as well, so we should probably consider doing the same for Function.prototype.call  and Function.prototype.apply."

I'll look into doing this.

/be

Comment 45

[Brendan Eich [:brendan]]

Gary, thanks for fuzzing!

/be

Comment 46

[Brendan Eich [:brendan]]

Attachment: plain diff of last two patches

Since interdiff fails.

/be

Comment 47

[Brendan Eich [:brendan]]

Attachment: rebased to tm tip

Comment 48

[Jesse Ruderman]

(function f(n) { this.q; if (n > 0) f(n - 1); })(1); print("PASS");

Does not print "PASS" when using this patch.  I am testing without -j.

Comment 49

[Brendan Eich [:brendan]]

Attachment: fix the problem Jesse found

More hate for JSFRAME_COMPUTED_THIS.

/be

Comment 50

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

Attachment: jit v2, crashes

This is crashing in xparb, which I'm currently debugging. reduced:

Date.prototype.dateFormat = function() {
    return this['theFunction']();
}

Date.prototype.theFunction = function() {
    return String.leftPad(this.getSeconds(), 2, '0');
}

String.leftPad = function (val, size, ch) {
    var result = new String(val);
    while (result.length < size)
        result += ch;
    return result;
}

var date = new Date("1/1/2007 1:11:11");

for (i = 0; i < 3; ++i) {
    var longFormat = date.dateFormat("s");
    date.setTime(date.getTime() + 84266956);
}

Comment 51

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

without the JIT patch, comparing interpreter only, this seems to regress sunspider:

http://pastebin.mozilla.org/677575

Comment 52

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

Attachment: working jit patch

With a non-crashing JIT patch, things aren't much better yet

http://pastebin.mozilla.org/677584

Comment 53

[Jesse Ruderman]

for (let b=0;b<5;++b) (function(){gc()})();

Fails the following assertion, with op == JSOP_TCALL:

http://hg.mozilla.org/tracemonkey/file/b8460dfab18c/js/src/jstracer.cpp#l6552

Comment 54

[Jesse Ruderman]

(function f(n){ ({}|0); return n ? f(n-1) : 42; })(6)

Assertion failure: (jsbytecode*)fragment->ip >= fp->script->code && (jsbytecode*)fragment->ip < fp->script->code + fp->script->length, at ../jsrecursion.cpp:505

Comment 55

[Jesse Ruderman]

I suspect there are other assertions in jstracer.cpp that, like the one in comment 53, need to be updated to include JSOP_TCALL.

Comment 56

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

(In reply to comment #54)
> (function f(n){ ({}|0); return n ? f(n-1) : 42; })(6)
> 
> Assertion failure: (jsbytecode*)fragment->ip >= fp->script->code &&
> (jsbytecode*)fragment->ip < fp->script->code + fp->script->length, at
> ../jsrecursion.cpp:505

This should be |fragment->root| so the assertion is just wrong - oops. Will post a new patch once I've figured out what's going on with 3d-cube.

Comment 57

[Jesse Ruderman]

for(let i in (function f() { yield; with({}){} (function(){yield})() })()){}

Assertion failure: env->getPrivate() == fp, at ../jsfun.cpp:894

Comment 58

[Jesse Ruderman]

for (var j=0;j<3;++j){(function(){})();let(x){}}

Assertion failure: index < arr->length, at ../jsscript.h:168

Comment 59

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

The problem with 3d-cube is that it was never compiling Loop() before, even with trace-recursion landed. Now we are and we're seeing new behavior since this is easy tail-recursion. We inline DrawLine() over and over, duplicating lots of branches, which creates tail explosion. Unfortunately tracing Loop() is an extremely long trace and we end up adding ~40ms in recording+compilation time, with only a 2ms gain in executed code.

Filing a separate bug.

Comment 60

[Boris Zbarsky [:bzbarsky]]

Bug from comment 59 is bug 523497.

Comment 61

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

Attachment: jit patch with assorted fixes

Comment 62

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

Attachment: fixes comment #58

previous patch fixed comment #53 and comment #54

Comment 63

[Brendan Eich [:brendan]]

(In reply to comment #57)
> for(let i in (function f() { yield; with({}){} (function(){yield})() })()){}
> 
> Assertion failure: env->getPrivate() == fp, at ../jsfun.cpp:894

diff -u b/js/src/jsemit.cpp b/js/src/jsemit.cpp
--- b/js/src/jsemit.cpp
+++ b/js/src/jsemit.cpp
@@ -6457,11 +6457,12 @@
             return JS_FALSE;
 
         /* Try for a proper tail call if in tail position. */
-        if (PN_OP(pn) == JSOP_CALL) {
+        if ((PN_OP(pn) == JSOP_CALL || PN_OP(pn) == JSOP_APPLY) &&
+            !(cg->flags & TCF_FUN_IS_GENERATOR)) {
             JS_RUNTIME_METER(cx->runtime, staticCalls);
             if (pn->pn_tailpos) {
                 JS_RUNTIME_METER(cx->runtime, staticTailCalls);
-                pn->pn_op = JSOP_TCALL;
+                pn->pn_op = (PN_OP(pn) == JSOP_CALL) ? JSOP_TCALL : JSOP_TAPPLY;
             }
         }
 
---- snip ----

fixes this one. Working on a new patch including this and more.

/be

Comment 64

[Brendan Eich [:brendan]]

(In reply to comment #58)
> for (var j=0;j<3;++j){(function(){})();let(x){}}
> 
> Assertion failure: index < arr->length, at ../jsscript.h:168

This WFM now -- fixed by a patch for another bug (I suspected bug 523284 at first but don't think so now). But which one?

/be

Comment 65

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 407099 [details] [diff] [review]
fix the problem Jesse found

Why can't we replace pn_wrapped by checking the stmtStack in TOK_RETURN (which, as far as I can tell, is the only *use* of pn_wrapped)?

There's some weird wrapping in jsinterp.cpp... I thought we broke after the operator, so:

if (foo <
     bar)

and not

if (foo
    < bar)

or something.

How do we know in JSOP_TCALL that fp is a JSInlineFrame, can we not get there as the result of JS_CallFunctionValue?

It would be nice to see a comment describing (somewhere) how tcall is calculated (namely that it's pushed down with the "body" being a tail call, some  statements explicitly disabling tail call position on their kids, some statements implicitly disabling tail call position (like TOK_UNARYOP) and some simply propagating (like TOK_HOOK)). Also, is it worth putting a link to Lars's spec somewhere in the source?

I haven't gone over the fp-overwriting code in detail yet (but wasn't there going to be a JSFRAME_TCALL?).

There are a couple of followup bugs mentioned in the patch: dealing with upvars seems like the most obvious, but also one detecting tail call in a non-fall-through switch case statement.

What's with the crazy #ifdef DEBUG` (with the backtick). If you're going to disable the block, please use DEBUG_off or something so it looks you meant to disable it!

I'll stamp + after I finish going through the fp-mangling code.

Comment 66

[Blake Kaplan (:mrbkap) (inactive)]

When mangling the pc, is it worth asserting that imacpc is null?

Comment 67

[Brendan Eich [:brendan]]

(In reply to comment #65)
> (From update of attachment 407099 [details] [diff] [review])
> Why can't we replace pn_wrapped by checking the stmtStack in TOK_RETURN (which,
> as far as I can tell, is the only *use* of pn_wrapped)?

We could, but (a) I wanted to follow the spec, and (b) decoupling from the stateful stack by setting flags in the AST is cleaner.

> There's some weird wrapping in jsinterp.cpp... I thought we broke after the
> operator, so:
> 
> if (foo <
>      bar)
> 
> and not
> 
> if (foo
>     < bar)
> 
> or something.

We break after && and ||. Other ops, we're not so consistent but generally break before the op. This is codified in the Mozilla guide.

> How do we know in JSOP_TCALL that fp is a JSInlineFrame, can we not get there
> as the result of JS_CallFunctionValue?

Good catch.

> It would be nice to see a comment describing (somewhere) how tcall is
> calculated (namely that it's pushed down with the "body" being a tail call,
> some  statements explicitly disabling tail call position on their kids, some
> statements implicitly disabling tail call position (like TOK_UNARYOP) and some
> simply propagating (like TOK_HOOK)). Also, is it worth putting a link to Lars's
> spec somewhere in the source?

I will comment a bit and link to Lars' and Dave's spec.

> I haven't gone over the fp-overwriting code in detail yet (but wasn't there
> going to be a JSFRAME_TCALL?).

David's patch adds that. I will talk to him about pulling it into the interp patch and do the ellipsis thing.

> There are a couple of followup bugs mentioned in the patch: dealing with upvars
> seems like the most obvious, but also one detecting tail call in a
> non-fall-through switch case statement.

I was gonna not file those eagerly. I don't think the switch one is important enough to merit more than the comment.

> What's with the crazy #ifdef DEBUG` (with the backtick). If you're going to
> disable the block, please use DEBUG_off or something so it looks you meant to
> disable it!

Typo! Thanks.

/be

Comment 68

[Brendan Eich [:brendan]]

Split out front end analysis to bug 565374.

/be

Comment 69

[Ryan VanderMeulen [:RyanVM]]

This is still applicable for IonMonkey, correct?

Comment 70

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

(In reply to Ryan VanderMeulen from comment #69)
> This is still applicable for IonMonkey, correct?

I think we can have a new bug if and when we want to try tail-call optimizations in IonMonkey. This bug was mostly about the tracer.