Re: [ANN] llvm-lua 1.0

["Robert G. Jakabosky" <bobby@...>]

On Thursday 04, Mike Pall wrote:
> 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.

Does LJ1 do this, or is this new in LJ2?  I have seen the de-optimize exits 
that are generated in LJ1 and though that they just ran a re-compile of the 
full function with some optimizations turned off.

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

Thanks for the link it looks interesting.  But I don't plan on making the slow 
path exits jump directly into the same logical spot in the slow path 
function.  I don't think LLVM would allow a branch from in-side one function 
to some place in-side another function.  The slow path function would need to 
be inlined at the end of the fast path function.

I was thinking of making the slow path function into a C-style continuation.  
The slow patch exits in the fast function would save the functions state and 
tail-call into the slow function.  The attached 'test_f.c' C-code shows how 
the Lua 'f' function from 'test.lua' could be compiled as a  fast path & slow 
path functions.  If fall-back to the slow function happens a lot during 
runtime, then the slow function could be made the default.

Both of those C functions could be optimized more, I just wanted to show how 
the fast function could fall back to the slow function.  The 
slow_path_func_f() is how llvm-lua 1.0 would compile the function (minus the 
switch statement at the top).

>
> > 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 agree that the default should support full Lua semantics, but for people who 
want as much performance from there scripts as possible they can choice to 
trade some Lua features for more speed.

Also when Lua is embedded, the host application can decide what level of 
compatibility with normal Lua semantics they want to provide there users.

> 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. :-)

That is a good idea, but would only work if the bytecode was compiled from Lua 
source code and not saved & loaded from a file.  Atleast not without changing 
the bytecode file format.

The practice of caching builtins in locals makes it harder for a static/AOT 
compiler like llvm-lua to detect if "match.sin" is being called.  The static 
compiler will need to evaluate the CLOSURE ops in the parent Lua function, to 
check the type/value of the up-value.  Right now llvm-lua doesn't do that 
type of analysis.

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

No, the static compiler could use compile-time IDs for all the standard 
library functions.  Those IDs would need to be added to the library 
registration process.

Does LJ2 only use the internal IDs to test if the inlined function was 
changed?

> [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.]

If the Lua core reserved a range of IDs for standard functions it could use 
those, in a new bytecode file format, as constant function references.

It would be really nice if there was no need for caching builtins functions in 
local variables for speed.  The caching wastes memory on stack space and/or 
up-values.

One way to still allow some monkey patching would be to put a proxy-object 
into the global tables for each of the functions.  All of these functions 
would then be stored at a fixed index in an array in the global_State.  Any 
writes to the proxy-object would change the value global function array.  
This would require a new opcode to load the global function, if support was 
to be added to the normal Lua interpreter, but a JIT/static compiler could 
inline the array access.

That would still by-pass any read filtering metatable added to _G or the 
standard library tables.

-- 
Robert G. Jakabosky

int fast_path_func_f(lua_State *L) {
entry:
  long for_idx;
  double x;

  /* check if 'x' parameter is a number */
  if(vm_test_is_number(L, 0) == 0) goto slow_path;
  /* load parameter 'x' */
  x = vm_get_number(L, 0);

  for_idx = 1;
  while(for_idx <= 2) {
    /* Lua: "x = f2(x)" */
    vm_OP_GETUPVAL(L, 5, 0); /* get up-value 'f2' the function to call */
    vm_set_number(L, 6, x); /* put 'x' value back on Lua-stack. */
    vm_OP_CALL(L, 5, 2, 2); /* call "f2(x)" */

    /* check if return value is a number */
    if(vm_test_is_number(L, 5) == 0) goto slow_path_from_loop;

    /* load return value */
    x = vm_get_number(L, 5);
    x = x * x; /* Lua: "x = x * x" */

    for_idx += 1;
  }

  vm_set_number(L, 0, x); /* put 'x' back on Lua-stack for return. */
  return vm_OP_RETURN(L, 0, 2); /* Lua: "return x" */

slow_path_from_loop:
  /* save function state back to Lua-stack */
  vm_set_number(L, 1, for_idx); /* save for loop index */
  /* mark resume point in slow function. */
  vm_set_resume_point(L, 1);

slow_path:
  return slow_path_func_f(L);
}

int slow_path_func_f(lua_State *L) {
entry:
  long for_idx;
  switch(vm_get_resume_point(L)) {
  case 1:
    for_idx = vm_get_number(L, 1); /* restore for loop index */
    goto resume_point_1;
  case 0:
  default:
    break;
  }

  for_idx = 1;
  while(for_idx <= 2) {
    vm_set_number(L, 4, for_idx); /* Update external for loop counter 'i' */

    vm_OP_GETUPVAL(L, 5, 0); /* get up-value 'f2' the function to call */
    vm_OP_MOVE(L, 6, 0); /* get parameter 'x' ready. */
    vm_OP_CALL(L, 5, 2, 2); /* Lua: "f2(x)" */
    vm_OP_MOVE(L, 0, 5); /* save return value back to 'x' */
resume_point_1:
    vm_OP_MUL(L, 0, 0, 0); /* Lua: "x = x * x" */
    for_idx += 1;
  }

  return vm_OP_RETURN(L, 0, 2); /* Lua: "return x" */
}

local function f2(x)
  if x < 0 then
    return "return some value that is not a number"
  end
  return x
end

local function f(x)
  for i=1,2 do
    x = f2(x)
    x = x * x
  end
  return x
end

print(f(3))
print(f(-1))