-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! -
--