Inlining in Higgs

May 2013 might have been the most hectic month of my life: I presented at DConf, visited Mozilla in San Francisco, packed and moved into a new apartment, visited Toronto and finally went on a short trip to Florida. Things have finally settled down a bit; I’m finding time to resume work on Higgs, and the problem I’m tackling right now is that of function inlining. For the unfamiliar, inlining is a compiler optimization which substitutes the body of a function we’re calling (the callee) at a location we’re calling it at (a call site). Because Higgs is partially self-hosted and its runtime is mostly implemented in JavaScript, Higgs does very many function calls, and inlining is crucial to achieve any kind of competitive performance.

Inlining turns out to be more complicated to implement in a Just-In-Time (JIT) compiler than in an Ahead Of Time (AOT) compiler. For one, transforming code for inlining takes time and so taking the time to perform inlining might actually reduce overall performance if it isn’t done sparingly (there’s a cost-benefit tradeoff involved). Another issue is that the program in which we’re inlining function calls is currently running, and so we might be trying to modify the body of functions that are already on the stack. Reconfiguring stack frames as a program is running is called On-Stack Replacement (OSR). It’s often difficult to implement due to a variety of corner cases: stack frame layouts aren’t always straightforward.

I’m at the point where I just got inlining to work in Higgs. I chose to implement this at the level of the Intermediate Representation (IR) rather than directly in the backend because it seemed like this would make it easier to optimize code post-inlining. At the moment, the JIT compiler will try to do inlining only if the caller gets compiled as it’s about to be called. This is because I haven’t yet implemented OSR. Just getting this working required a fair bit of bugfixing as it ended up stressing parts of my backend that hadn’t been tested before. Because JavaScript does late binding, the inlining is conditional, that is, a test verifies that the callee is the function we expect before jumping to the inlined body.

You may be interested to know what the performance impact of this is. Some tests are slightly faster now, but at this point, most benchmarks run slightly slower with inlining enabled. This is because Higgs doesn’t yet do much specialization and optimization after inlining, but also because inlining doesn’t get used much. I’ll need to implement at least basic support for OSR (e.g.: support for replacing the topmost function on the stack) in order to make it so functions with long-running loops can benefit from inlining at all. I’ll also need to implement some support for constant propagation and type specialization in order to get more performance benefits from inlined calls. Simply eliminating some amount of call overhead turns out to be insufficient.

In other news, Tom (thejsjunky) is working on enhancing our Foreign Function Interface (FFI) library to maximize its user-friendliness. He’s also implementing a test harness to make it easier to add new tests to Higgs. It’s very important to me that Higgs be robust and well tested. I’d like to make it easy for people to submit failed test cases when they file a bug report on GitHub. I’d also like to encourage people to contribute new libraries and FFI bindings they wrote through pull requests. My goal is that Higgs will eventually be very much of a “batteries included” JS implementation which makes it easy for people to start hacking immediately. Tom and I even have modest hopes that we may be able to compete with CPython on some fronts by the time I present at Strange Loop in September.

Andrei Alexandrescu has been posting talks from DConf 2013 on Reddit at a rate of two or three per week. A video of my talk should become available next week and will be linked on this blog as well as on my twitter feed. Stay tuned :)