Progress on the Higgs JIT
I’ve been busy working on various aspects of the new Higgs JIT compiler in the last month or so. Among other things, I decided to expand it into a proper tracing JIT compiler complete with support for side-exit traces (or sub-traces as I like to call them). This brought some performance improvements. I’m also happy to report that the JIT compiler appears quite stable and is enabled by default. At this point, the Higgs JIT is still quite simple and primitive compared to commercial JavaScript VMs, but nevertheless provides marked speedups relative to the interpreter on every benchmark I tested it on.
JIT speedup relative to the interpreter
I’m interested in finding the source code for the latest version of the Mozilla TraceMonkey shell (as well as instructions on how to build it) so that I can compare the performance of Higgs to another JavaScript tracing JIT. TraceMonkey is no longer maintained by Mozilla and is no longer in their main source code repository.
One important optimization I added to Higgs was to implement a stack frame initialization analysis. Previously, Higgs initialized every stack slot as soon as a function was called to make sure that stack frames were always in a consistent state when the garbage collector (GC) was called. As you can imagine, this is is rather slow for large stack frames, and it’s often a complete waste of time if the variables are going to be initialized later on. Now, a simple analysis actually checks which variables have been written to (and so may contain references to heap objects) and the GC uses this information when performing a collection. This significantly reduces the amount of work that has to be done during function calls.
An important limitation of the current JIT compiler is that it directly translates the interpreter’s intermediate representation into a linear list of x86 machine instructions. This is an issue because the machine code produced is of fairly poor quality and would need to be further optimized, but contains little semantic information to facilitate optimization. One of the things I plan to do is to implement a liveness analysis to facilitate basic register allocation and eliminate redundant writes to the interpreter stack. I’m unfortunately not sure what is the best data structure to use (in terms of memory usage) to store liveness information and associate it with a function’s intermediate representation (if anyone has advice, please comment).
Tom, a friend of mine, recently started helping with the Higgs project. Among other things, he took the time to track down and help me fix bugs that were causing crashes in various benchmarks. This process involved fixing many inaccuracies in the Higgs implementation of the JS spec. We’re now at the point where all of the V8 and SunSpider benchmarks are working correctly, except for those using regular expressions. Tom has also started implementing a Foreign Function Interface (FFI) system for Higgs. Once completed, this should allow us to add support for APIs such as OpenGL, and POSIX sockets. This might give Higgs some real usefulness outside of academic experiments.
Pointers Gone Wild 
First of all, great work!
As for a data structure for liveness analysis, what about using a sort of 2 dimensional bitmap to indicate at which instruction a vaue is live. (Variables vs instruction, each bit represents an instruction) You would use about a byte per 8 instructions per basic block and would be able to sort the resulting bytes to find out which values are the most used. Then you could bitmask this set of bytes to find which ranges to split (like in the case of instructions requiring a precise register, like DIV). As for values escaping a basic block you can use another bitmap for the basic blocks in a function to setup for inter-block register allocation. Since you do this in IR, you would store SSA variables and could reduce the number of bits used in the resulting bitmap. (Not storing variables not used in said block) So instead of using whole integers to store liveness ranges (2 ints in a struct, let’s say) you use only a single byte per 8 instructions. Anyways, just a suggeston
TraceMonkey was removed in commit b2e8d10f25a1 (see bug 698201), so you if you do `hg up -r 646f4a4d58ea` to check out the last revision before its removal, you get the most up-to-date code there ever was for it.
Thank you sir.
http://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/2012/10/2012-10-21-11-57-46-mozilla-central/ I believe should have the tracing jit in the jsshell since it’s 1 day before the removal. Also I’m not sure if it needs to be enabled with a switch or not but just incase you haven’t gotten a jsshell by now.
Also… if this thing is fast maybe you should put it inside a little toy browser and have a way for people to test it in a browser setting??
Good luck and I hope such work continues smoothly, too bad you weren’t in Ontario as it would be nice to chat about such topics in person!
We’ve studied the idea of integrating into an existing browser and it seemed like that would be a massive piece of work. Might be fun project to implement a toy browser in JS and have it run inside of Higgs though. We’re working on improving our FFI lib. We hope to provide bindings for sockets and graphical APIs.
Fellow Canadian here (from Montreal). I was actually in Toronto just last weekend for Pride. I do go there every once in a while. Will be back in Ontario for a friend’s wedding in early September.
Hello :) Well My line of thinking all depends on HOW difficult this may be, You may have something!
I looked at the http://wiki.dlang.org/GUI_Libraries page and since I love Qt, I looked there to the Bitbucket Repository and found a port of the Qt Web Brwser example to D https://bitbucket.org/qtd/repo/src/d7b4cb20ce99d7a17772751e2615c180bb02e651/demos/browser?at=default Yes Qt guys are crazy but they had an extremely simplistic Browser Demo which is ported to the D Qt binding examples in that repo.
That demo I BELIEVE uses the QWebFrame::evaluateJavaScript function since the TODO.txt says it uses the QT 4.5.1 version which I believe is the port of http://doc.qt.digia.com/4.5-snapshot/webkit-fancybrowser.html toy browser implementation.
If that is the demo they ported to D then: https://github.com/ariya/phantomjs/blob/master/src/qt/src/3rdparty/webkit/Source/WebKit/qt/Api/qwebframe.cpp#L1549 shows exactly where you could put YOUR Higgs jit in there as an “#elif USE(HIGGS)” and just pass what you need to use Higgs as the JS execution engine instead of JSC or V8 as they do there.
So just a potential way to get it actually working without much hassle depending if the Browser demo is functional enough :)
If that Demo builds… you’re golden :)
Unfortunately it’s not as simple as you seem to think it is. This demo is just a barebones wrapper for the WebKit engine. Replacing JSC in there would be a lot of work. The interaction between the browser and JS isn’t just a one way call to some “evaluateJavaScript” function. There is a tree of DOM objects created by the browser that has to be accessible to JavaScript code. This is how the web browser exposes all its APIs and the webpage content to JS. JS code must be able to refer to DOM objects, read and write properties. Values have to be translated back and forth between the DOM world (C++) and the JS world. There are also garbage-collection intricacies involved since the JS code can now hold references to objects created by the browser, and the reverse may be true as well.
Well yes…http://qt-project.org/doc/qt-4.7/qwebframe.html refrences the http://qt-project.org/doc/qt-4.7/qwebframe.html#id-9552fabc-b6d8-4884-917b-1f1f0fb865ca (addToJavaScriptWindowObject) to interface and communicate natively between JS & C++? Which is done by doing creating/hooking up the webkit bridge here: http://qt-project.org/doc/qt-4.7/qtwebkit-bridge.html … right??
Since V8 is the grandchild project of this, KHTML->JSC->V8 I would have thought it’s abstractness as a framework would allow it to be pluggable like how they first implemented alternative JS engine backends. But yea, there seems to be alot of #includes specific for whichever one is used but I’d say if anyone can just ram Higgs in there its you(the creator) :) But of course all just tossing ideas, I’m not sure of it’s actual amount of effort.
I did link to the 4.7 framework links there but I think it does consider the interaction between the C++ and JS object/DOM hierarchy even when looking at the quick online docs and the hopeful looking JS engine conditional in the phantomjs source code.
It’s a shame if it’s really a humongous undertaking.
Either way, have a nice week!