kripken/emscripten — pull request #1981 by rfk (2014-01-06 11:31:35+00:00)
Title: work-in-progress: registerize based on full liveness analysis

I've noticed that many of my functions seem to use more local variables than necessary - for example the main dispatch loop for pypy.js uses 101 local variables. So I've been experimenting with ways to reduce this.

This PR is a work-in-progress to add a full live-variable analysis to the "registerize" function. It builds a flow graph, finds the set of variables live at each point, and assigns them to registers based on which variables are live concurrently. It also has a few tricks for eliminating redundant assignments.

Compared to the existing "registerize" function, I see the following changes when compiling pypy.js with this branch:

* the number of local variables decreases, from 101 to 59 for the main dispatch loop
* uncompressed code size decreases, from 64M to 62M total
* compile time goes up, from ~22 minutes to ~23 minutes
* I didn't measure peak memory usage during the compile, but I imagine it will also increase

So it seems like a nice win so far, and I think there's a little more improvement that could be wrung out of it.

The code's pretty complex, and it feels kinda silly to decompose the generated javascript back into a low-level flow-graph representation. I also worry that it may be too computationally expensive to include by default. But perhaps it would make a nice additional optimizer pass that can be enabled e.g. as part of -O3.

What do you think about an approach like this, is it worth pursuing in more detail?