This is a little essay that tries to answer the question: 'So, how does LuaJIT really work?'.
I tried to avoid going into all the gory details, but at the same time provide a deep enough explanation, to let you find your way around LuaJIT's inner workings.
The learning curve is maybe a little bit steep for newbies and compiler gurus will certainly fall asleep after two paragraphs. It's difficult to strike a balance here.
Acronym Soup
As the name says LuaJIT is a Just-In-Time (JIT) compiler. This means that functions are compiled on demand, i.e. when they are run first. This ensures both a quick application startup and helps to avoid useless work, too. E.g. unused functions are not compiled at all.
The other alternative is known as Ahead-Of-Time (AOT) compilation. Here everything is compiled before running any function. This is the classic way for many languages, such as C or C++.
In fact plain Lua allows you to pre-compile Lua source code into Lua bytecode and store it in a binary file that can be run later on. This is used only in specific settings (e.g. memory limited embedded systems), because the Lua bytecode compiler is really fast. The ability to run source files right away is part of what makes a dynamic language (aka scripting language) so powerful.
JIT compilation has a few other advantages for dynamic languages that AOT compilation can only provide with a massive amount of code analysis. More can be found in the literature. One particular advantage is explained later.
Quick, JIT — Run!
JIT compilation happens mostly invisible. You'll probably never notice that a compilation is going on. Part of the secret is that everything happens in little pieces intermixed with running the application itself inbetween. The other part of the secret is that JIT compilation can be made pretty fast.
Most applications quickly converge to a stable state where everything that really needs to be compiled is compiled right away. Only occasional isolated compiles happen later on.
Even though the name doesn't suggest it, LuaJIT can operate in AOT mode, too. But this is completely under user control (see jit.compile()) and doesn't happen automatically.
Unless you have good reason to suspect that AOT compilation might help for a specific application, I wouldn't bother though. Compilation speed is usually a non-argument, because LuaJIT is extremely fast. Compilation times are typically in the microsecond range for individual Lua functions.
Starting Up
The next few paragraphs may not be exactly breaking news to you, if you are familiar with JIT compilers. Still, please read on, because some terms are introduced that are used later on.
When you start LuaJIT everything proceeds like in standard Lua: the Lua core is initialized, the standard libraries are loaded and the command line is analyzed. Then usually the first Lua source code file is loaded and is translated to Lua bytecode. And finally the function for the initial main chunk is run ...
Kicking the Compiler
This is where LuaJIT kicks in:
All Lua functions carry an additional status code for LuaJIT. Initially this is set to 'NONE', i.e. the function has not been looked at (yet). If a function is run with this setting, the LuaJIT compiler pipeline is started up.
If you haven't loaded any special LuaJIT modules and optimization is not turned on, the compiler pipeline only consists of the compiler backend.
The compiler backend is the low-level encoding engine that translates bytecode instructions to machine code instructions. Without any further hints from other modules, the backend more or less does a 1:1 translation. I.e. a single variant of a bytecode instruction corresponds to a single piece of machine code.
If all goes well, these little code pieces are put together, a function prologue is slapped on and voila: your Lua function has been translated to machine code. Of course things are not that simple when you look closer, but hey — this is the theory.
Anyway, the status code for the function is set to 'OK' and the machine code is run. If this function runs another Lua function which has not been compiled, that one is compiled, too. And so on.
Call Gates
Ok, so what happens when a function is called repeatedly? After all this is the most common case.
Simple: The status code is checked again. This time it's set to 'OK', so the machine code can be run directly. Well — that's not the whole truth: for calls that originate in a JIT compiled function a better mechanism, tentatively named call gates is used.
Every function has a call gate field (a function pointer). By default it's set to a function that does the above checks and runs the compiler. But as soon as a function is compiled, the call gate is modified to point to the just compiled machine code.
Calling a function is then as easy as calling the code that the call gate points to. But due to special (faster) calling conventions this function pointer cannot be used directly from C. So calls from a non-compiled function or from a C function use an extra entry call gate which in turn calls the real call gate. But this is really a non-issue since most calls in typical applications are intra-JIT calls.
The Compiler Pipeline
The compiler pipeline has already been mentioned. This sounds more complicated than it is. Basically this is a coroutine that runs a frontend function which in turn calls all functions from the pipeline table.
The pipeline table is sorted by priorities. The standard backend has priority 0. Positive priorities are run before the backend and negative priorities are run after the backend. Modules can dynamically attach or detach themselves to the pipeline with the library function jit.attach().
So a typical optimizer pass better have a positive priority, because it needs to be run before the backend is run. E.g. the LuaJIT optimizer module registers itself with priority 50.
On the other hand a typical helper module for debugging — a machine code disassembler — needs to be run after the backend and is attached with a negative priority.
One special case occurs when compilation fails. This can be due to an internal error (ouch) or on purpose. E.g. the optimizer module checks some characteristics of the function to be compiled and may decide that it's just not worth it. In this case a status other than OK is passed back to the pipeline frontend.
The easiest thing would be to abort pipeline processing and just give up. But this would remove the ability to trace the progress of the compiler (which better include failed compilations, too). So there is a special rule that odd priorities are still run, but even priorities are not. That's why e.g. -j trace registers itself with priority -99.
The Optimizer
Maybe it hasn't become clear from the above description, but a module can attach any Lua or C function to the compiler pipeline. In fact all of the loadable modules are Lua modules. Only the backend itself is written in C.
So, yes — the LuaJIT optimizer is written in pure Lua!
And no, don't worry, it's quite fast. One reason for this is that a very simple abstract interpretation algorithm is used. It mostly ignores control flow and/or basic block boundaries.
Thus the results of the analysis are really only hints. The backend must check the preconditions (the contracts) for these hints (e.g. the object type). Still, the generated hints are pretty accurate and quite useful to speed up the compiled code (see below).
Explaining how abstract interpretation works is not within the scope for this short essay. You may want to have a look at the optimizer source code and/or read some articles or books on this topic. The canonical reference is » Principles of Program Analysis. Ok, so this one is a bit more on the theoretical side (a gross understatement). Try a search engine with the keywords "abstract interpretation", too.
Suffice to say the optimizer generates hints and passes these on to the backend. The backend then decides to encode different forms for the same bytecode instruction, to combine several instructions or to inline code for C functions. If the hints from the optimizer are good, the resulting code will perform better because shorter code paths are used for the typical cases.
The JIT Advantage
One important feature of the optimizer is that it takes 'live' function arguments into account. Since the JIT compiler is called just before the function is run, the arguments for this first invocation are already present. This can be used to great advantage in a dynamically typed language, such as Lua.
Here's a trivial example:
function foo(t, k) return t[k] end
Without knowing the most likely arguments for the function there's not much to optimize.
Ok, so 't' is most likely a table. But it could be userdata, too. In fact it could be any type since the introduction of generic metatables for types.
And more importantly 'k' can be a number, a string or any other type. Oh and let's not forget about metamethods ...
If you know a bit about Lua internals, it should be clear by now that the code for this function could potentially branch to half of the Lua core. And it's of course impossible to inline all these cases.
On the other hand if it's known (or there's a good hint) that 't' is a table and that 'k' is a positive integer, then there is a high likeliness that the key 'k' is in the array part of the table. This lookup can be done with just a few machine code instructions.
Of course the preconditions for this fast path have to be checked (unless there are definitive hints). But if the hints are right, the code runs a lot faster (about a factor of 3 in this case for the pure table lookup).
Optimizing the Optimizer
A question that surely popped up in your mind while reading the above section: does the optimizer optimize itself? I.e. is the optimizer module compiled?
The current answer is no. Mainly because the compiler pipeline is single-threaded only. It's locked during compilation and any parallel attempt to JIT compile a function results in a 'DELAYED' status code. In fact all modules that attach to the compiler pipeline disable compilation for the entire module (because LuaJIT would do that anyway). The main chunk of modules loaded with require() is never compiled, so there is no chicken-and-egg problem here.
Of course you could do an AOT compilation in the main chunk of the optimizer module. But then only with the plain backend. Recompiling it later on with the optimizer attached doesn't work, because a function cannot be compiled twice (I plan to lift this restriction).
The other question is whether it pays off to compile the optimizer at all? Honestly, I haven't tried, because the current optimizer is really simple. It runs very quickly, even under the bytecode interpreter.
That's All Folks
Ok, that's all for now. I'll extend this text later on with new topics that come up in questions. Keep on asking these on the mailing list if you are interested.
Thank you for your attention!