Proper Tail Calls for the trace JIT

RESOLVED WONTFIX

Status

()

Core
JavaScript Engine
P3
enhancement
RESOLVED WONTFIX
9 years ago
6 years ago

People

(Reporter: Peter Michaux, Assigned: brendan)

Tracking

(Depends on: 1 bug)

unspecified
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite ?

Firefox Tracking Flags

(Not tracked)

Details

(URL)

Attachments

(3 attachments, 18 obsolete attachments)

3.31 KB, patch
Details | Diff | Splinter Review
61.61 KB, patch
mrbkap
: review+
Details | Diff | Splinter Review
24.14 KB, patch
Details | Diff | Splinter Review
(Reporter)

Description

9 years ago
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.
(Assignee)

Comment 1

9 years ago
Blake, were you interested in taking this on?

/be
Status: UNCONFIRMED → NEW
Ever confirmed: true
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.
We could avoid that by avoiding tail calls on heavyweight functions.
(Reporter)

Comment 4

9 years ago
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.
(Assignee)

Comment 5

8 years ago
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
Assignee: general → brendan
(Assignee)

Updated

8 years ago
Blocks: 519853
Status: NEW → ASSIGNED
Priority: -- → P1
Target Milestone: --- → mozilla1.9.2
(Assignee)

Comment 6

8 years ago
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
(Assignee)

Comment 7

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

Debugging, improving... new patch coming.

/be
Attachment #403931 - Attachment is obsolete: true
(Assignee)

Comment 8

8 years ago
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
Attachment #403976 - Flags: review?(mrbkap)
(Assignee)

Comment 9

8 years ago
  staticCalls = 58, 
  staticTailCalls = 6, 
  dynamicCalls = 20104, 
  dynamicTailCalls = 820, 
  ...

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

/be
(Assignee)

Comment 10

8 years ago
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
Attachment #403976 - Attachment is obsolete: true
Attachment #403981 - Flags: review?(mrbkap)
Attachment #403976 - Flags: review?(mrbkap)
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?
(Assignee)

Comment 12

8 years ago
(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
(Assignee)

Comment 13

8 years ago
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
Attachment #403981 - Attachment is obsolete: true
Attachment #404097 - Flags: review?(mrbkap)
Attachment #403981 - Flags: review?(mrbkap)
(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.  :-)
(Assignee)

Comment 15

8 years ago
Created attachment 404473 [details] [diff] [review]
correct display non-maintenance, conditioned on rejecting optimized closure callee at greater static level
Attachment #404097 - Attachment is obsolete: true
Attachment #404473 - Flags: review?(mrbkap)
Attachment #404097 - Flags: review?(mrbkap)
(Assignee)

Comment 16

8 years ago
(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
(Reporter)

Comment 17

8 years ago
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.
(Assignee)

Comment 18

8 years ago
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
(Assignee)

Comment 19

8 years ago
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
(Assignee)

Comment 20

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

/be
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?
(Assignee)

Comment 22

8 years ago
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
(Reporter)

Comment 23

8 years ago
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.
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.
(Assignee)

Comment 25

8 years ago
(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
(Assignee)

Comment 26

8 years ago
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
(Assignee)

Comment 27

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

/be
(Assignee)

Comment 28

8 years ago
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
(Assignee)

Comment 29

8 years ago
Created attachment 404518 [details] [diff] [review]
better optimized closure screening
Attachment #404473 - Attachment is obsolete: true
Attachment #404518 - Flags: review?(mrbkap)
Attachment #404473 - Flags: review?(mrbkap)
(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.)
(Assignee)

Comment 31

8 years ago
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
(Assignee)

Comment 32

8 years ago
Created attachment 404736 [details] [diff] [review]
refreshed patch
Attachment #404518 - Attachment is obsolete: true
Attachment #404736 - Flags: review?(mrbkap)
Attachment #404518 - Flags: review?(mrbkap)
(Assignee)

Comment 33

8 years ago
Created attachment 404761 [details] [diff] [review]
refreshed again to track back-out
Attachment #404736 - Attachment is obsolete: true
Attachment #404761 - Flags: review?(mrbkap)
Attachment #404736 - Flags: review?(mrbkap)
(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.
(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.
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.
(Assignee)

Comment 37

8 years ago
Created attachment 406361 [details] [diff] [review]
rebased to tm tip
Attachment #404761 - Attachment is obsolete: true
Attachment #404761 - Flags: review?(mrbkap)
(Assignee)

Comment 38

8 years ago
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
Attachment #406361 - Flags: review?(mrbkap)
(Assignee)

Comment 39

8 years ago
Created attachment 406743 [details] [diff] [review]
rebased again plus CloneParseTree fix
Attachment #406361 - Attachment is obsolete: true
Attachment #406743 - Flags: review?(mrbkap)
Attachment #406361 - Flags: review?(mrbkap)
(Assignee)

Comment 40

8 years ago
Created attachment 406792 [details] [diff] [review]
fix to consolidate initialization in NewOrRecycledNode
Attachment #406743 - Attachment is obsolete: true
Attachment #406792 - Flags: review?(mrbkap)
Attachment #406743 - Flags: review?(mrbkap)
(Assignee)

Comment 41

8 years ago
Created attachment 406797 [details] [diff] [review]
fix another fuzzer-found bug, easy

Bugzilla interdiff should work this time.

/be
Attachment #406792 - Attachment is obsolete: true
Attachment #406797 - Flags: review?(mrbkap)
Attachment #406792 - Flags: review?(mrbkap)
(Assignee)

Comment 42

8 years ago
Fuzzer-generated test for last fix:

http://pastebin.mozilla.org/676962

/be
Flags: in-testsuite?
(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.
(Assignee)

Comment 44

8 years ago
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
Attachment #406797 - Attachment is obsolete: true
Attachment #406907 - Flags: review?(mrbkap)
Attachment #406797 - Flags: review?(mrbkap)
(Assignee)

Comment 45

8 years ago
Gary, thanks for fuzzing!

/be
(Assignee)

Comment 46

8 years ago
Created attachment 406908 [details] [diff] [review]
plain diff of last two patches

Since interdiff fails.

/be
(Assignee)

Comment 47

8 years ago
Created attachment 406962 [details] [diff] [review]
rebased to tm tip
Attachment #406907 - Attachment is obsolete: true
Attachment #406962 - Flags: review?(mrbkap)
Attachment #406907 - Flags: review?(mrbkap)

Comment 48

8 years ago
(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.
(Assignee)

Comment 49

8 years ago
Created attachment 407099 [details] [diff] [review]
fix the problem Jesse found

More hate for JSFRAME_COMPUTED_THIS.

/be
Attachment #406962 - Attachment is obsolete: true
Attachment #407099 - Flags: review?(mrbkap)
Attachment #406962 - Flags: review?(mrbkap)
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);
}
Attachment #405212 - Attachment is obsolete: true
without the JIT patch, comparing interpreter only, this seems to regress sunspider:

http://pastebin.mozilla.org/677575
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
Attachment #407170 - Attachment is obsolete: true

Comment 53

8 years ago
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

8 years ago
(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

8 years ago
I suspect there are other assertions in jstracer.cpp that, like the one in comment 53, need to be updated to include JSOP_TCALL.
(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

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

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

Comment 58

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

Assertion failure: index < arr->length, at ../jsscript.h:168
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.
Depends on: 523497
Bug from comment 59 is bug 523497.
Created attachment 407448 [details] [diff] [review]
jit patch with assorted fixes
Attachment #407202 - Attachment is obsolete: true
Created attachment 407450 [details] [diff] [review]
fixes comment #58

previous patch fixed comment #53 and comment #54
Attachment #407448 - Attachment is obsolete: true
(Assignee)

Comment 63

8 years ago
(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
(Assignee)

Comment 64

8 years ago
(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 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.
When mangling the pc, is it worth asserting that imacpc is null?

Updated

8 years ago
Attachment #407099 - Flags: review?(mrbkap) → review+
(Assignee)

Comment 67

8 years ago
(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
(Assignee)

Updated

8 years ago
Target Milestone: mozilla1.9.2 → mozilla1.9.3a1
(Assignee)

Updated

7 years ago
Priority: P1 → P3
Target Milestone: mozilla1.9.3a1 → mozilla1.9.3
(Assignee)

Updated

7 years ago
Depends on: 565374
(Assignee)

Comment 68

7 years ago
Split out front end analysis to bug 565374.

/be
Target Milestone: mozilla1.9.3 → mozilla2.0
(Assignee)

Updated

7 years ago
Target Milestone: mozilla2.0 → ---
This is still applicable for IonMonkey, correct?
(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.
Status: ASSIGNED → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → WONTFIX

Updated

6 years ago
Summary: Proper Tail Calls → Proper Tail Calls for the trace JIT
You need to log in before you can comment on or make changes to this bug.