1030098 - Implement lambda-lifting

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine: JIT, defect, P5)

Description

[Till Schneidereit [:till]]

Would, among probably quite a few other things, help Earley-Boyer.

Comment 1

[Luke Wagner [:luke]]

Marc Feeley did some measurements on this a while back (iirc, they were promising).

Comment 2

[Hannes Verschore [:h4writer]]

(In reply to Luke Wagner [:luke] from comment #1)
> Marc Feeley did some measurements on this a while back (iirc, they were
> promising).

I heard that too. Was it only research he did or is there something we can (re)use for finally doing this?

Comment 3

[Lars T Hansen [:lth]]

I'm all for this, but full lambda lifting is fairly involved.

What, if anything, are we presently doing to optimize named local functions that are only used as call targets?  Are we requiring a heap-allocated activation record for the outer function, for example?

Comment 4

[Luke Wagner [:luke]]

Marc can fill in more, but I think he used a source-to-source translation that hooked in before the parser even got a hold of the source.  To avoid parsing twice, we'd probably want to operate on the SM AST.  Our AST is not the most malleable thing, esp with regards to naming, but doing this anywhere else seems tricky; the JITs primarily work within a single function (or at least a set of inlined functions).  Maybe we'll finally have the motivation to convert the parser to do name resolution in a second pass :)

One question is whether any of the usual suspects in JS would get in the way.  In particular, .caller both allows unexpected callers and exposes function object identity.  To address the former, we could .bind the new arguments introduced by the lifting inside .caller.  For the latter, .caller isn't even spec'd so maybe we just ignore it.  Other than that, I can't think of any other bad cases off the top of my head...

Comment 5

[Luke Wagner [:luke]]

(In reply to Lars T Hansen [:lth] from comment #3)
> What, if anything, are we presently doing to optimize named local functions
> that are only used as call targets?  Are we requiring a heap-allocated
> activation record for the outer function, for example?

Yes, unless the function is marked as a singleton; in which case we try hard not to clone it.  .caller is again the challenge here, but perhaps we can also break identity.

Comment 6

[Nicolas B. Pierron [:nbp] {away}]

I think this is interesting to investigate, but independently of the .caller issue I think there is another set of issues such as DOM callbacks.  If I have a simple example such as:

  function f(a) {
    for (var i = 0; i < a.length; i++)
      a[i] = function () { … };
  }

We might think that it is safe to do so, but we might also change the semantic as before lifting "a[0] !== a[1]", and after lifting "a[0] === a[1]".  Even if this might not matter in a lot of cases it does matter for some cases such as event listeners, as listeners are suppress if there is a strictly matching equality.

Sadly, trying to prevent against the previous one might be hard without deep knowledge of which functions are using the inner function, for example one case where we might want to make use of such lambda-lifting would be:

  function f(a) {
    for (var i = 0; i < a.length; i++)
      a[i] = a.map(function () { … });
  }

but to do so we need to provide some guarantee on the inner function and on the usage of the callback.  Sadly, I think part of this knowledge is only available within Baseline / Ion.

Comment 7

[Marc Feeley]

I'm sorry for getting to reply so late...

The lambda lifting I implemented was a preprocessor (JS to JS).  This was only meant as a quick and dirty experiment to evaluate how much could be gained by lambda lifting (for Earley-Boyer the speedup was 2.5x if I remember correctly).  But for a production quality implementation the lambda lifting should be done on the AST.

.caller is a problem because it exposes too much of the implementation.  Sadly the requirement to maintain the .caller info makes many source-to-source (AST-to-AST) transformations impossible.

Comment 8

[Marc Feeley]

Sorry but I don't see the problem.  In your example, what would the code be after lifting?

Comment 9

[Nicolas B. Pierron [:nbp] {away}]

(In reply to Marc Feeley from comment #8)
> Sorry but I don't see the problem.  In your example, what would the code be
> after lifting?

The problem is that if map is not known at the AST time, and that doing lambda lifting is an observable behavior, and more over the DOM identify use this to identify functions.  Which means that if you register a function twice, and remove it later, you might not have what you expected.

var arr = [0,1,2,3]

function f(a) {
  for (var i = 0; i < a.length; i++)
    a[i] = function () { return i; }
};
f(arr)
arr[0] === arr[1] // false

dom.listen(arr[0]);
dom.listen(arr[1]);
dom.stop(arr[0]);
dom.stop(arr[0]); // arr[1] stills listen for events


function f(a) {
  var g = function () { return i; };
  for (var i = 0; i < a.length; i++) a[i] = g;
}
f(arr)
arr[0] === arr[1] // true

dom.listen(arr[0]);
dom.listen(arr[1]);
dom.stop(arr[0]); // ???
dom.stop(arr[0]); // no more listeners.


The second example highlight the fact that we do not have enough static information to know that what ".map" do, and it could well be doing some dom function calls, until we know that ".map" is the Array.map native implementation.

Comment 10

[Marc Feeley]

I understand that function identity (=== test) must be preserved.  What I don't understand is what you expect the lambda-lifting to do!  Normally, lambda-lifting is limited to the named functions, and only the named functions that are called by the code (i.e. are non-escaping).  So the function in a[i] = function () { ... } would never be lambda-lifted, but the code in the ... might be transformed by the lambda-lifting.  In earley-boyer lambda-lifting the named functions is already a big improvement.

Comment 11

[Marc Feeley]

I think you are confusing "lambda floating" and "lambda lifting".  In lambda floating, function creation is moved to a different place, for example moving a function creation out of the for loop as in your example:

function f(a) {
  var g = function () { return i; };
  for (var i = 0; i < a.length; i++) a[i] = g;
}

As you say, this has an impact on function identity, so the program must not be testing these functions for ===.

In lambda lifting, extra parameters are added to the parameter list of functions to eliminate the free variables (and thus allowing these functions to be statically created, no closure allocation).  That is, transforming

function f(x) {
  function g(y) { return x+y; }
  return g(10);
}

into

function f(x) {
  function g(x,y) { return x+y; }
  return g(x,10);
}

Usually, lambda lifting is only done on functions for which all the call sites are locally visible and where the function is only called locally (never passed to another function, or returned, or stored in an object).  This can be determined with a simple analysis.  It happens very often in Earley-Boyer.

Comment 12

[Till Schneidereit [:till]]

While that won't help Earley-Boyer, wouldn't it be quite a bit simpler to implement lambda-lifting for strict functions? No need to worry about caller for them, so a local escape analysis, which we already have, should be sufficient to determine eligibility.

Comment 13

[Mayank Bansal]

Still relevant?

Comment 14

[Iain Ireland [:iain]]

An optimization that requires static analysis at parse time is a hard sell these days. We would generally prefer to limit that to Ion. Inlining + scalar replacement gets us the same effect of eliding the lambda allocation if we inline the lambda body. If we wanted to optimize this area, I think aggressive inlining of lambda bodies is probably a better fit.