Do some constant-folding / dead-code elimination in residual functions

[NTillmann]

When the global code has run, Prepack also does some analysis on the residual function, determining which captured variables are only ever read (are not "mutated").

Then the final values of those captured variables which are immutable and cannot be objects (because identities might matter) are inlined in the residual function bodies.

This in turn often leads to left-behind code of the form

if (false) { ... }

This is not wrong, and there are good existing minifiers that can eliminate that code. But there might be some value to Prepack doing such dead-code elimination, as that in turn might eliminate references to other captured variables, which in turn might simplify other parts of Prepack's code generation.

[bakkot]

What needs to be done for this to happen? Is this something someone from outside the project but with a good grasp of static analysis and JavaScript semantics could reasonably help progress?

[NTillmann]

Hi Kevin, thanks for asking!

There's one low-hanging fruit in the short term: Dead-code elimination in residual functions, leveraging knowledge about constants computed along the global code. This would effectively optimize the following code:

(function () {
  let f = false;
  global.residual = function () {
    if (f) { console.log("eliminate me"); }
    return 42;
  }
})();

I'll follow up with another comment on how that can be achieved.

Long term, and more comprehensive, would be to build out the true "partial-evaluators", an early prototype of which can be found in the src/partial-evaluators directory, and apply them on the residual function AST nodes, starting from a "havoced state" where nothing is known, except for those known constants I mentioned earlier. If done right, this will also achieve deadcode elimination, but also constant-folding, and possibly much more. @hermanventer will later write more about the required work.

I'd be happy to chat with you some more in person. Feel free to reach out to me: nikolait@fb.com.

[NTillmann]

How to do basic constant-folding in residual functions:

We already rewrite residual functions, replacing all captured local variables. This happens in the ClosureRefReplacer in src/serializer/visitors.js. For each captured local variable, we determine if it's ever modified. If not, we can often replace it with the (effectively constant) value computed along global code execution. For the example code I write in the previous comment, it replaces f with false.

On top of that, the existing visitor could be enhanced with simple rules, e.g. for an IfStatement, it could check if the condition (after the substitution I just mentioned) is the literal true or false, and then rewrite the AST node to the consequent or alternative.

This should make the following serializer test case pass:

// does not contain:eliminate
(function () {
  let f = false;
  global.inspect = function () {
    if (f) { console.log("eliminate me"); }
    return 42;
  }
})();

[bakkot]

Thanks for the response!

I'm happy to go add a little dead-code elimination logic. I've already been doing a similar thing in a personal project (actually, that's what made me want to look at Prepack, and this issue is what stopped me from using it). But in practice, in my experience, I think it's not going to do all that much without also doing at least a little constant folding and propagation - at least in my samples I ran into at least as many cases like if (1 === 2) as if (false).

Of course, it's easy enough to transform 1 === 2 too, but at that point it starts getting into the territory of the partial evaluator, which would be a much better solution anyway.

What would be the appropriate place to add dead code elimination? I could do it in ClosureRefReplacer, looks like, but that doesn't feel like the right place.

---

Re: the partial evaluator approach, in particular

starting from a "havoced state" where nothing is known, except for those known constants I mentioned earlier

I would love it if it were possible to assert some initial conditions - for example, no new properties on Object.prototype or Array.prototype. For many applications, consumers might be comfortable relying on invariants like those, and transformation could get a lot further.

[NTillmann]

What would be the appropriate place to add dead code elimination?

For the quick win, the ClosureRefReplacer is the right place. Doesn't look super clean, and it isn't the long-term solution, but it's where we can do something now.

I would love it if it were possible to assert some initial conditions

Right... Ideally, all built-ins would get frozen, at least at the end of the global code, but that's not typically the case. We are currently working on a different feature that does in fact make assumptions on what parts of the global code get mutated (#799). So I would be fine by making this assumption for the partial evaluator if some flag is given (the default should still be to be safe).

[NTillmann]

While basic dead-code elimination has been implemented by #1061, we are still leaving a lot of optimization potential on the table.

Consider the following code:

(function () {
  let c = false;
  function f() {
    let x = 0;
    function g() {
      return c ? x++ : 42;
    }
    return g;
  }
  global.x = f();
})();

Dead-code elimination removes the need for x, and yet the referentialization logic produces a huge chunk of code to deal with x...