Last Comment Bug 445363 - Proper Tail Calls for the trace JIT
: Proper Tail Calls for the trace JIT
Status: RESOLVED WONTFIX
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: P3 enhancement with 1 vote (vote)
: ---
Assigned To: Brendan Eich [:brendan]
:
Mentors:
http://wiki.ecmascript.org/doku.php?i...
Depends on: 565374 523497
Blocks: 519853
  Show dependency treegraph
 
Reported: 2008-07-15 11:50 PDT by Peter Michaux
Modified: 2011-11-28 23:06 PST (History)
19 users (show)
brendan: in‑testsuite?
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
everything except the interpreter code to do the tail call (29.99 KB, patch)
2009-09-30 18:22 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
patch, everything but the JIT (40.97 KB, patch)
2009-10-01 00:02 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
patch, more metering plus a display maintenance fix (41.94 KB, patch)
2009-10-01 00:18 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
claim more slots for the new frame if they are available (44.59 KB, patch)
2009-10-01 12:26 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
correct display non-maintenance, conditioned on rejecting optimized closure callee at greater static level (46.18 KB, patch)
2009-10-03 22:23 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
better optimized closure screening (55.02 KB, patch)
2009-10-04 10:37 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
refreshed patch (55.81 KB, patch)
2009-10-05 17:42 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
refreshed again to track back-out (55.08 KB, patch)
2009-10-05 20:23 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
jit part, v1 (7.77 KB, patch)
2009-10-07 21:04 PDT, David Anderson [:dvander]
no flags Details | Diff | Splinter Review
rebased to tm tip (58.55 KB, patch)
2009-10-14 17:30 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
rebased again plus CloneParseTree fix (59.36 KB, patch)
2009-10-16 12:36 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
fix to consolidate initialization in NewOrRecycledNode (59.98 KB, patch)
2009-10-16 15:11 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
fix another fuzzer-found bug, easy (60.86 KB, patch)
2009-10-16 15:38 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
don't forget "with"! (61.60 KB, patch)
2009-10-18 06:38 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
plain diff of last two patches (3.31 KB, patch)
2009-10-18 06:43 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
rebased to tm tip (61.48 KB, patch)
2009-10-18 18:41 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
fix the problem Jesse found (61.61 KB, patch)
2009-10-19 13:32 PDT, Brendan Eich [:brendan]
mrbkap: review+
Details | Diff | Splinter Review
jit v2, crashes (23.63 KB, patch)
2009-10-19 17:35 PDT, David Anderson [:dvander]
no flags Details | Diff | Splinter Review
working jit patch (22.45 KB, patch)
2009-10-19 20:16 PDT, David Anderson [:dvander]
no flags Details | Diff | Splinter Review
jit patch with assorted fixes (24.18 KB, patch)
2009-10-20 18:57 PDT, David Anderson [:dvander]
no flags Details | Diff | Splinter Review
fixes comment #58 (24.14 KB, patch)
2009-10-20 19:14 PDT, David Anderson [:dvander]
no flags Details | Diff | Splinter Review

Description Peter Michaux 2008-07-15 11:50:45 PDT
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] 2008-07-15 14:12:47 PDT
Blake, were you interested in taking this on?

/be
Comment 2 Mike Shaver (:shaver -- probably not reading bugmail closely) 2008-07-22 13:50:42 PDT
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) 2008-07-22 15:04:28 PDT
We could avoid that by avoiding tail calls on heavyweight functions.
Comment 4 Peter Michaux 2008-07-22 16:26:09 PDT
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] 2009-09-30 16:45:54 PDT
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] 2009-09-30 18:22:33 PDT
Created attachment 403931 [details] [diff] [review]
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] 2009-09-30 19:15:42 PDT
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] 2009-10-01 00:02:22 PDT
Created attachment 403976 [details] [diff] [review]
patch, everything but the JIT

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

/be
Comment 9 Brendan Eich [:brendan] 2009-10-01 00:07:23 PDT
  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] 2009-10-01 00:18:22 PDT
Created attachment 403981 [details] [diff] [review]
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 [:bz] 2009-10-01 05:34:04 PDT
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] 2009-10-01 11:06:40 PDT
(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] 2009-10-01 12:26:41 PDT
Created attachment 404097 [details] [diff] [review]
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] (remove +bmo to email) 2009-10-02 15:06:19 PDT
(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] 2009-10-03 22:23:07 PDT
Created attachment 404473 [details] [diff] [review]
correct display non-maintenance, conditioned on rejecting optimized closure callee at greater static level
Comment 16 Brendan Eich [:brendan] 2009-10-03 22:35:21 PDT
(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 2009-10-03 22:45:36 PDT
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] 2009-10-03 23:33:10 PDT
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] 2009-10-03 23:39:22 PDT
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] 2009-10-03 23:41:19 PDT
Oh, and ES5 strict mode poison-pills .caller on functions and arguments objects with throwing getters.

/be
Comment 21 Boris Zbarsky [:bz] 2009-10-04 08:27:54 PDT
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] 2009-10-04 08:53:21 PDT
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 2009-10-04 09:15:07 PDT
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 [:bz] 2009-10-04 09:47:57 PDT
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] 2009-10-04 10:03:10 PDT
(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] 2009-10-04 10:19:10 PDT
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] 2009-10-04 10:21:21 PDT
I should credit Dave Herman along with Lars Hansen for the spec at the URL.

/be
Comment 28 Brendan Eich [:brendan] 2009-10-04 10:24:49 PDT
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] 2009-10-04 10:37:02 PDT
Created attachment 404518 [details] [diff] [review]
better optimized closure screening
Comment 30 Jeff Walden [:Waldo] (remove +bmo to email) 2009-10-04 13:30:43 PDT
(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] 2009-10-04 14:39:30 PDT
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] 2009-10-05 17:42:51 PDT
Created attachment 404736 [details] [diff] [review]
refreshed patch
Comment 33 Brendan Eich [:brendan] 2009-10-05 20:23:57 PDT
Created attachment 404761 [details] [diff] [review]
refreshed again to track back-out
Comment 34 Nicholas Nethercote [:njn] 2009-10-06 15:13:54 PDT
(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 [:njn] 2009-10-06 15:17:50 PDT
(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] 2009-10-07 21:04:28 PDT
Created attachment 405212 [details] [diff] [review]
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] 2009-10-14 17:30:11 PDT
Created attachment 406361 [details] [diff] [review]
rebased to tm tip
Comment 38 Brendan Eich [:brendan] 2009-10-14 17:30:50 PDT
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] 2009-10-16 12:36:57 PDT
Created attachment 406743 [details] [diff] [review]
rebased again plus CloneParseTree fix
Comment 40 Brendan Eich [:brendan] 2009-10-16 15:11:21 PDT
Created attachment 406792 [details] [diff] [review]
fix to consolidate initialization in NewOrRecycledNode
Comment 41 Brendan Eich [:brendan] 2009-10-16 15:38:59 PDT
Created attachment 406797 [details] [diff] [review]
fix another fuzzer-found bug, easy

Bugzilla interdiff should work this time.

/be
Comment 42 Brendan Eich [:brendan] 2009-10-16 15:40:52 PDT
Fuzzer-generated test for last fix:

http://pastebin.mozilla.org/676962

/be
Comment 43 Gary Kwong [:gkw] [:nth10sd] 2009-10-18 00:07:41 PDT
(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] 2009-10-18 06:38:56 PDT
Created attachment 406907 [details] [diff] [review]
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] 2009-10-18 06:39:35 PDT
Gary, thanks for fuzzing!

/be
Comment 46 Brendan Eich [:brendan] 2009-10-18 06:43:28 PDT
Created attachment 406908 [details] [diff] [review]
plain diff of last two patches

Since interdiff fails.

/be
Comment 47 Brendan Eich [:brendan] 2009-10-18 18:41:19 PDT
Created attachment 406962 [details] [diff] [review]
rebased to tm tip
Comment 48 Jesse Ruderman 2009-10-18 19:36:38 PDT
(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] 2009-10-19 13:32:19 PDT
Created attachment 407099 [details] [diff] [review]
fix the problem Jesse found

More hate for JSFRAME_COMPUTED_THIS.

/be
Comment 50 David Anderson [:dvander] 2009-10-19 17:35:02 PDT
Created attachment 407170 [details] [diff] [review]
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] 2009-10-19 20:13:48 PDT
without the JIT patch, comparing interpreter only, this seems to regress sunspider:

http://pastebin.mozilla.org/677575
Comment 52 David Anderson [:dvander] 2009-10-19 20:16:11 PDT
Created attachment 407202 [details] [diff] [review]
working jit patch

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

http://pastebin.mozilla.org/677584
Comment 53 Jesse Ruderman 2009-10-19 23:19:57 PDT
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 2009-10-20 00:50:36 PDT
(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 2009-10-20 00:52:02 PDT
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] 2009-10-20 01:25:10 PDT
(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 2009-10-20 11:50:02 PDT
for(let i in (function f() { yield; with({}){} (function(){yield})() })()){}

Assertion failure: env->getPrivate() == fp, at ../jsfun.cpp:894
Comment 58 Jesse Ruderman 2009-10-20 11:58:21 PDT
for (var j=0;j<3;++j){(function(){})();let(x){}}

Assertion failure: index < arr->length, at ../jsscript.h:168
Comment 59 David Anderson [:dvander] 2009-10-20 17:03:34 PDT
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 [:bz] 2009-10-20 18:13:16 PDT
Bug from comment 59 is bug 523497.
Comment 61 David Anderson [:dvander] 2009-10-20 18:57:16 PDT
Created attachment 407448 [details] [diff] [review]
jit patch with assorted fixes
Comment 62 David Anderson [:dvander] 2009-10-20 19:14:33 PDT
Created attachment 407450 [details] [diff] [review]
fixes comment #58

previous patch fixed comment #53 and comment #54
Comment 63 Brendan Eich [:brendan] 2009-10-21 12:09:21 PDT
(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] 2009-10-21 12:21:26 PDT
(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) 2009-10-26 04:51:54 PDT
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) 2009-10-26 08:29:59 PDT
When mangling the pc, is it worth asserting that imacpc is null?
Comment 67 Brendan Eich [:brendan] 2009-10-26 10:07:29 PDT
(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] 2010-05-12 19:46:51 PDT
Split out front end analysis to bug 565374.

/be
Comment 69 Ryan VanderMeulen [:RyanVM] 2011-11-24 07:59:55 PST
This is still applicable for IonMonkey, correct?
Comment 70 David Anderson [:dvander] 2011-11-24 09:59:23 PST
(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.

Note You need to log in before you can comment on or make changes to this bug.