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

[Paulo César Pereira de Andrade]

2015-01-09 19:55 GMT-02:00 Marc Nieper-Wißkirchen <address@hidden>:
> 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);
> }

  This will leak a jit_state_t, but I presume it is only for example,
otherwise, need to jit_destroy_state it once no longer used.

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

  This works because neither function receives (stack) arguments,
but if whatever "compile" returns needs more arguments than the
code calling it, it will corrupt the stack. Lightning could fix some
of the cases (same jit_context_t calling jit compiled functions),
but  without full control of all code generation cannot fix or know
about cases were it could, or would corrupt the stack, and even
when possible to fix in lightning, it would be better to rely on the
programmer understanding the code generation, and being
responsible for not corrupting data (proper/clear documentation
should exist, to make the information easy to understand).

>   jit_retval(JIT_R0);
>   jit_jmpr(JIT_R0);

  This will not work on some backends, like ia64 or big endian
powerpc (function descriptors), or, mips or little endian powerpc
where the function pointer must be in a specific register, to
compute GOT, PIC, etc. hppa also needs some special
handling. Also, for the sake of simplicity/safety, lightning would
still need to spill/reload modified callee save registers.

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

  No, as commented above (ia64, mips, BE or LE powerpc). Your
example is a simple case, but to be complete, it would need to
support stack arguments, and for the sake of self documenting,
and avoiding having lightning to do different code generation based
on context, that may not be too easy to infer when reading the code,
it would be better to have two calls, one for preparing to push
arguments for a tail call (could be omitted if not passing any
arguments), and one to tail call the pointer. Somewhat like
jit_tailcall{i,r} (for no arguments), and "jit_tailprepare" and
"jit_tailfinish{i,r}". Well, need to choose some naming
scheme, sometimes the first idea does not sound do cool :)

> 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