How does LuaJIT's trace compiler work?

Question

I've been reading up on JIT's and LuaJIT's trace compiler in particular, and I ended up with some questions.

From what I understand, LuaJIT's JIT doesn't compile hot methods like Java's HotSpot does, it compiles hot paths originating from loops. Does this mean that if something doesn't originate from a loop (say, I call Lua functions from the C-api) then the code will never be jitted? And what happens when you hit another loop? Will the path to the second loop be JIT'ed, and then a new path from that loop jitted as well, or will the second loop be a part of the same path?

How does the interpreter choose the most optimal hot path? Let's say I have a hash-table of ints -> strings. Now imagine that I've called table[x] with x being 3 and 5 enough times that they've become hot paths and jitted, how does the interpreter decide which jitted code to call for table[x] where x is 4?

Another thing that has been racking my brain. Since paths are compiled, not functions, won't a trace compiler require more memory? Since you can't really re-use compiled code of another path I mean, and since paths will probably be larger than single functions in the general case...

Bushranger

Answer 1

Mike Pall responded in quite detail on the LuaJIT mailing list. http://www.freelists.org/post/luajit/How-does-LuaJITs-trace-compiler-work,1

Bushranger

Answer 2

The first part you need to under stand is the LuaJIT IR and Bytecode, which you can check out on the wiki, this is what the LuaJIT interpreter runs and optimizes and hence does the traces on to determine what needs to be compiled and various as well as the additional of optimizations such as loop-unrolling for hot-loops in the trace path.

The second place to check is the LJ FAQ, which has this to say:

Q: Where can I learn more about the compiler technology used by LuaJIT?

I'm planning to write more documentation about the internals of LuaJIT. In the meantime, please use the following Google Scholar searches to find relevant papers:

Search for: Trace Compiler

Search for: JIT Compiler

Search for: Dynamic Language Optimizations

Search for: SSA Form

Search for: Linear Scan Register Allocation

Here is a list of the innovative features in LuaJIT. And, you know, reading the source is of course the only way to enlightenment. :-)

Abet very tongue-in-cheek (mainly 'cause Mike focuses on development rather than documentation), the most important part there is the last sentence, the source is very clean and the only actual way to find out how LJ does its magic. Additionally the innovative features link also gives one more clues on what to search for.

Wikipedia has a more descriptive page on tracing JIT, however, the papers at the bottom are what you'll find most useful to help understand the concepts used in the LJ source.

Some of the source files (in C) to get you started

• lj_record.c: core trace recorder, converts bytecode into IR
• lj_trace.c: more trace management
• lj_snap.c: handles/creates trace snapshots
• lj_ffrecord.c: records data for fast functions
• lj_crecord.c: records C data ops

Ambulate

I understand how bytecode and IR works, and the main part of the trace compiler, least I think I do :P I just had a few details I wasn't sure of. I've stayed away from the LuaJIT source code as I haven't learned assembly (and alot of the LuaJIT is written in assembly right?) – Bushranger

Anyway, I'll read the through what you have suggested, and see if that brings enlightenment. Great answer btw! +1 – Bushranger

@RobinHeggelundHansen: technically only the threaded interpreter is in assembly (well, a special abstraction used with dynasm), the actual tracer and code emitter are all in C (it is a bit weird because the field names are very compact, but when once you understand the conventions its a little easier) and Lua, I generally use VS to make spelunking of the source easier for me. I've added a few source files that contain many of the tracing aspects to my answer – Ambulate