Re: [Lightning] Are tail calls possible in GNU lightning?

[Alex Gilding]

Haven't examined their source so couldn't say which strategy they're using, but is worth noting that Racket ( http://racket-lang.org/ ) uses GNU lightning for code generation, and as one of *the* big-name Scheme implementations, definitely has proper support for tail calls.

It's the 1.x series of lightning, but whatever they're doing should still be possible.

On 9 January 2015 at 21:55, Marc Nieper-Wißkirchen <address@hidden> wrote:

P.S.: I have written a small example program that demonstrates what I want to achieve:

#include <stdio.h>

#include <lightning.h>

static jit_state_t *_jit;

jit_node_t *compile() {

  jit_state_t *_jit;

  _jit = jit_new_state();

  jit_prolog();

  jit_node_t *label = jit_indirect();

  jit_reti(42);

  jit_emit();

  jit_clear_state();

  return jit_address(label);

}

int main(int argc, char* argv[]) {

  int (*code)();

  jit_node_t *jump, *label, *ref;

  init_jit(argv[0]);

  _jit = jit_new_state();

  

  jit_prolog();

  jit_prepare();

  jit_finishi(compile);

  jit_retval(JIT_R0);

  jit_jmpr(JIT_R0);

  

  code = jit_emit();

  jit_clear_state();

  

  printf("Result: %d\n", code());

  

  jit_destroy_state();

  finish_jit();

  return 0;

}

I can run this program successfully on my x86_64 GNU/Linux. But does it work portably?

Marc

2015-01-09 22:14 GMT+01:00 Marc Nieper-Wißkirchen <address@hidden>:

Dear Paulo,

thank you very much for your quick reply.

I am thinking of using GNU lightning to implement a small virtual machine that is able to JIT-compile a programming language like Scheme which needs guaranteed tail-calls (and where the existence call/cc forces continuation passing style).

In fact, the VM implementation will have a virtual stack and all internal calls will in fact be jumps as you suggested. Thus, so far I could implement everything in one large function, and everything would be fine.

However, the VM should also support a kind of eval, which should trigger JIT-compilation on the fly. In this case, GNU lightning shall be called from the already running compiled code. GNU lightning will produce a second function at a new address, which I want to tail-call from my already running function. Thus I need to know whether there is a portable way to dynamically jump into this second function.

(Don't hesitate to ask in case my explanation didn't help you.)

Best,

Marc

2015-01-09 21:19 GMT+01:00 Paulo César Pereira de Andrade <address@hidden>:

2015-01-09 16:33 GMT-02:00 Marc Nieper-Wißkirchen <address@hidden>:
> Hi,

  Hi,

> I haven't found any information whether tail calls are possible in GNU
> lightning while remaining portability. In case they are, would they also
> portably work across code that was generated by different calls to
> jit_emit()?

  It is not supported, but is on my non official TODO list. Note that
if one is implementing a high level language, most likely is also
using a "virtual stack" in the heap, and there anything can be done,
for example, all language specific function calls could be jumps.

  Implementation using the "real" stack would be somewhat like this:

1. Calculate stack depth of current function based on calls to jit_arg,
    jit_arg_f and jit_arg_d, just for the sake of asserting will not corrupt
    the stack, but must trust the programmer that the function
    was called that way
2. Instead of "jit_prepare", would have something like "jit_tail"
3. After the above, jit_pusharg* would replace arguments  in the
   current stack frame
4. Since it used the hypothetical "jit_tail" to prepare to call,
   when jit_finish*() would be called, it would be replaced by
   jit_jmp*(), or, could require an explicit jit_jmp* call

  This should not be too difficult to implement, and can be done
in a reasonably portable way.

  Should be easier to implement than other 2 TODOs I have, that
are support for varargs jit functions, not just calling varargs functions,
and jit_allocar, that is, allocating variable stack space at run time,
not just fixed size defined at jit generation.

  Do you have some more information about where, and why you
need it?

  I am holding lightning 2.0.6 release to fix any remaining issues
of using it to generate jit for GNU Smalltalk...

> Best,
>
> Marc

Thanks,
Paulo

_______________________________________________
Lightning mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/lightning