Re: [ANN] llvm-lua 1.0

[Mike Pall <mikelu-0906@...>]

Robert G. Jakabosky wrote:
> A JIT compiler will still need hooks to catch the slow paths just in case the 
> function is called with a different type for one of it's parameters or 
> something else in the environment changes.  The JIT will be able to just 
> re-compile the code to allow the new path.

Recompiling everyhing for every taken exit is too expensive. But
there's a gradual approach:
- The first few times a particular exit is taken, just reconstruct
  the state and return back to the interpreter.
- If the exit is taken often enough, start recording at the exit
  point, compile this trace in isolation and link it to the
  original trace.
- Recompile everything as a whole only if the side trace is run
  more often than the main trace. Alternatively drop everything and
  let the recording heuristics find a new trace.

> With a static compiler it will not be able to do a on-the-fly re-compile, but 
> I think it will be possible to provide a slower fall-back copy of the 
> function.  This will require a duplicate of every function, but I think in a 
> lot of cases the extra slow version will not need to be used.

This requires creation of split/join compensation code. Turns out,
this is a hard problem:

The Multiflow Trace Scheduling Compiler
P. Geoffrey Lowney et al, 1992
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.4703

> Yes I really hate it when somebody messes with the math.* functions ;-) 
> 
> I have though about providing a Lua restricted mode that dis-allows some 
> changes to _G and the standard libraries.  The restricted mode would allow 
> static compilers to inline more code without needing some of the slow paths.  
> As long as the script doesn't need to use some weird tricks like that it 
> should be able to run under the restricted mode (might also be usefull to the 
> sand-boxing people).

Well, I've thought about something like an '-Obuiltin' option. This
would pin down all built-in library functions at compile time. Ok,
so monkey patching would no longer give the expected results (you
can still do math.sin = math.random, but it's ignored). IMHO this
is an uncommon practice, except for debugging (so don't turn this
option on then).

Of course this violates Lua semantics, that's why it should probably
be off by default. But I guess most users wouldn't mind in this case.
If you have a large codebase, you can't afford to mess around with
the namespace of the standard libraries anyway. Same issue, if you
need to integrate 3rd-party modules which depend on these functions.

I guess it would be easiest to do this in the parser. Whenever a
chain of table lookups starting with a global is made, do this
lookup in parallel on the global environment which is active during
parsing. If the endpoint of the lookup is one of the builtin
functions, put it into the constant table and emit a simple load
from the constant table (instead of the chain of table lookups).

In terms of Lua 5.1 bytecode this would replace GETGLOBAL+GETTABLE*
with a single LOADK. This ought to be *really* fast, both in the
interpreter and when compiled. It would also put an end to the
cumbersome practice of caching builtins in locals or upvalues
(local sin = math.sin; local cos = math.cos; ...). In fact, using
the long name inline would be faster -- the function identity check
for the call dispatch can be constant-folded by the compiler. :-)

A static compiler probably needs to match the builtins by name.
OTOH in LJ2 all builtin functions are already marked with an
internal ID. Doing the lookup at runtime during parsing is trivial.
This would also allow a limited form of monkey patching -- if you
do it *before* parsing/loading the main part of your Lua code.

[This idea would pay off even for the plain Lua interpreter. Simply
set a flag in luaL_openlibs before registering the standard library
functions and turn it off at the end. Copy this flag into every
newly created CClosure in lua_pushcclosure(). Check this flag while
parsing and do the above transformation. That's all.]

--Mike