Using lightning from scheme

Using lightning from scheme

[Ian Grant]

[-- Attachment #1.1: Type: text/plain, Size: 2123 bytes --]

Here is the basis of a lightning interface for Guile. The example shows
that I seem to be able to JIT compile a foreign function binding and call
it, at least once!

The rest is data that I generated using the rather awful hack at


https://github.com/IanANGrant/red-october/blob/master/src/dynlibs/ffi/testrewrite.sml

which parses the output of GCC's cpp when applied to the text "#include
<lightning.h>" from whence it extracts the enum declaration of lightning's
opcodes, and the macros that connect the opcodes with the node-generating
functions jit_new_node_* Then it tries to infer the types of the
jit_new_node functions from their names, and I explicitly define the types
of the instruction opcode macros on a case-by-case basis, selecting them by
regexps on their names.

I hope a competent scheme programmer could get a full set of lightning
primitives going in a matter of a few hours using this. They won't if I
have made a lot of mistakes typing the opcode macros, but the same sort of
code I used in ML could be replicated in scheme, and then they could apply
the fixes in bulk. Once working, the interface could then be used to
generate itself, if one were that inclined. Or it could be used to
implement a lexical analyser generator, which Guile seems to need.

Anyone interested in this could look at
http://www.mpi-sws.org/~turon/re-deriv.pdf which is nicely written and
gives a current perspective which seems to have benefited PLT Racket. I
think it would be interesting to compile the DFAs into assembler which
reads mmapped fles, or guile port buffers, or bytevectors. One could also
compile the LALR tables into the same function, and I think the result
would perform quite well.  Have fun, but try to keep it abstract, so that
the interface can be generated from the same formal spec. for EMACS lisp,
say.

The same data could be used to generate a C function interface to
lightning, which did more argument sanity checking than lightning's CPP
macros currently do.

Ian

I've gzipped it just to stop the mailing list sed scripts from editing it.
They don't seem to know much about programming :-)

[-- Attachment #1.2: Type: text/html, Size: 2499 bytes --]

[-- Attachment #2: example.scm.gz --]
[-- Type: application/x-gzip, Size: 11557 bytes --]

[-- Attachment #3: Type: text/plain, Size: 159 bytes --]

_______________________________________________
Lightning mailing list
Lightning-mXXj517/zsQ@public.gmane.org
https://lists.gnu.org/mailman/listinfo/lightning

Re: Using lightning from scheme

[Ian Grant]

[-- Attachment #1.1: Type: text/plain, Size: 3733 bytes --]

I forgot to say that the dataflow list is what you probably guessed: an
attempt to specify which of the register arguments to the opcode macros are
inputs, and which are outputs. I want to use that for some extra checking
("Rn is unreferenced" or "Rn maybe used uninitialized") and to implement
register allocation by setting up a set of constraints, each represented by
user-defined variable, and solving the constraints like a sudoku puzzle,
maybe. Apparently it is quite quick of you search the most highly
constrained variables first. This is just a guess though. Another whacky
approach might be to specify the constraints as Prolog terms and throw
Harrison's Prolog interpreter at some likely-looking rules. But I am
talking out of my hat, really ...

Nevertheless ... it would be nice of we _could_ have the register
allocation algorithm described by a formal language, if not Prolog, then a
bit like Prolog, because then we would only need to specify the
interpreter, as two parts: a resolution solver and a search strategy, say.
Then we would have a spec of lightning register allocation that (a) could
be changed and easily experimented with, and (b) automatically implemented
in any language for which we have written the list functionals like map,
find, partition, etc.

And so on and so forth ... I am feeling like I have said rather a lot on
these two list lately and should shut up for a while ...

Ian



On Sat, Sep 6, 2014 at 7:40 PM, Ian Grant <ian.a.n.grant-gM/Ye1E23mwN+BqQ9rBEUg@public.gmane.org>
wrote:

> Here is the basis of a lightning interface for Guile. The example shows
> that I seem to be able to JIT compile a foreign function binding and call
> it, at least once!
>
> The rest is data that I generated using the rather awful hack at
>
>
> https://github.com/IanANGrant/red-october/blob/master/src/dynlibs/ffi/testrewrite.sml
>
> which parses the output of GCC's cpp when applied to the text "#include
> <lightning.h>" from whence it extracts the enum declaration of lightning's
> opcodes, and the macros that connect the opcodes with the node-generating
> functions jit_new_node_* Then it tries to infer the types of the
> jit_new_node functions from their names, and I explicitly define the types
> of the instruction opcode macros on a case-by-case basis, selecting them by
> regexps on their names.
>
> I hope a competent scheme programmer could get a full set of lightning
> primitives going in a matter of a few hours using this. They won't if I
> have made a lot of mistakes typing the opcode macros, but the same sort of
> code I used in ML could be replicated in scheme, and then they could apply
> the fixes in bulk. Once working, the interface could then be used to
> generate itself, if one were that inclined. Or it could be used to
> implement a lexical analyser generator, which Guile seems to need.
>
> Anyone interested in this could look at
> http://www.mpi-sws.org/~turon/re-deriv.pdf which is nicely written and
> gives a current perspective which seems to have benefited PLT Racket. I
> think it would be interesting to compile the DFAs into assembler which
> reads mmapped fles, or guile port buffers, or bytevectors. One could also
> compile the LALR tables into the same function, and I think the result
> would perform quite well.  Have fun, but try to keep it abstract, so that
> the interface can be generated from the same formal spec. for EMACS lisp,
> say.
>
> The same data could be used to generate a C function interface to
> lightning, which did more argument sanity checking than lightning's CPP
> macros currently do.
>
> Ian
>
> I've gzipped it just to stop the mailing list sed scripts from editing it.
> They don't seem to know much about programming :-)
>
>
>

[-- Attachment #1.2: Type: text/html, Size: 4493 bytes --]

[-- Attachment #2: Type: text/plain, Size: 159 bytes --]

_______________________________________________
Lightning mailing list
Lightning-mXXj517/zsQ@public.gmane.org
https://lists.gnu.org/mailman/listinfo/lightning

Re: Using lightning from scheme

[Paulo César Pereira de Andrade]

2014-09-06 21:18 GMT-03:00 Ian Grant <ian.a.n.grant-gM/Ye1E23mwN+BqQ9rBEUg@public.gmane.org>:

  I suggest looking at the lightning test driver
http://git.savannah.gnu.org/cgit/lightning.git/tree/check/lightning.c
if writing an interface to another language, it is one of the simplest possible
examples of an (almost) full interface to lightning. It shows, among other
things, that you need to know, and that is by design, if running on 32 or 64
bit arch, because some instructions are only available on 64 bit, or there
are extra instructions for 64 bit. There is no "long long" on 32 bit lightning.

> I forgot to say that the dataflow list is what you probably guessed: an
> attempt to specify which of the register arguments to the opcode macros are
> inputs, and which are outputs. I want to use that for some extra checking

  I believe you are talking about what lib/jit_classify() does. That interface
is not exported. The possible values, from include/lightning/jit_private.h
are:

#define jit_cc_a0_reg        0x00000001    /* arg0 is a register */
#define jit_cc_a0_chg        0x00000002    /* arg0 is modified */
#define jit_cc_a0_jmp        0x00000004    /* arg0 is a jump target */
#define jit_cc_a0_rlh        0x00000008    /* arg0 is a register pair */
#define jit_cc_a0_int        0x00000010    /* arg0 is immediate word */
#define jit_cc_a0_flt        0x00000020    /* arg0 is immediate float */
#define jit_cc_a0_dbl        0x00000040    /* arg0 is immediate double */
#define jit_cc_a1_reg        0x00000100    /* arg1 is a register */
#define jit_cc_a1_chg        0x00000200    /* arg1 is modified */
#define jit_cc_a1_int        0x00001000    /* arg1 is immediate word */
#define jit_cc_a1_flt        0x00002000    /* arg1 is immediate float */
#define jit_cc_a1_dbl        0x00004000    /* arg1 is immediate double */
#define jit_cc_a2_reg        0x00010000    /* arg2 is a register */
#define jit_cc_a2_chg        0x00020000    /* arg2 is modified */
#define jit_cc_a2_int        0x00100000    /* arg2 is immediate word */
#define jit_cc_a2_flt        0x00200000    /* arg2 is immediate float */
#define jit_cc_a2_dbl        0x00400000    /* arg2 is immediate double */

several of those are not used, but are there just in case in the future
they could be used. Register pairs are absolutely not planned as
"long long" and  are only used as output of qmul* (low/high result of
multiplication) and qdiv* (quotient/remainder of division), because
most backends support this, or it can be synthesized.

> ("Rn is unreferenced" or "Rn maybe used uninitialized") and to implement
> register allocation by setting up a set of constraints, each represented by

  One possible "example" here are return values. Lightning does not
know about types neither function prototypes. After a function call,
it considers the integer and float return registers as live; but note that
unlike lightning 1.x, there is no JIT_RET or JIT_FRET, you need to
call jit_retval, jit_retval_f or jit_retval_d to fetch the return value (the
main reason for this is to write sane code on backends that have special
access to such values, ABI may dictate always return on a gpr register,
or the register may not actually exist, like in the arm port, that works on
hardware without a math coprocessor and uses stack slots as "virtual"
fpr registers).

> user-defined variable, and solving the constraints like a sudoku puzzle,
> maybe. Apparently it is quite quick of you search the most highly
> constrained variables first. This is just a guess though. Another whacky
> approach might be to specify the constraints as Prolog terms and throw
> Harrison's Prolog interpreter at some likely-looking rules. But I am talking
> out of my hat, really ...
>
> Nevertheless ... it would be nice of we _could_ have the register allocation
> algorithm described by a formal language, if not Prolog, then a bit like
> Prolog, because then we would only need to specify the interpreter, as two
> parts: a resolution solver and a search strategy, say. Then we would have a
> spec of lightning register allocation that (a) could be changed and easily
> experimented with, and (b) automatically implemented in any language for
> which we have written the list functionals like map, find, partition, etc.

  Not an easy start point, but to have a general idea of a possible "register
allocation" implementation are the oemit*.c files at
https://github.com/pcpa/owl/blob/master/lib/
Basically the vm has 4 general purpose registers, and during code
generation it may keep values only on hard registers if working with
values that it knows do not overflow, that is, does not need to convert
an integer to mpz_t or floating value to a complex number, etc.

  To generate really efficient native code, I only suggest to avoid as much
as possible function calls (as in "C" function calls) and jit_jumpr calls
(calls to targets resolved at run time), after that are mostly micro
optimizations like spreading values in multiple registers to avoid contention,
reordering jumps to avoid as much as possible prediction misses, as well
as removing as much as possible jumps, etc.

> And so on and so forth ... I am feeling like I have said rather a lot on
> these two list lately and should shut up for a while ...
>
> Ian
>
>
>
> On Sat, Sep 6, 2014 at 7:40 PM, Ian Grant <ian.a.n.grant-gM/Ye1E23mwN+BqQ9rBEUg@public.gmane.org>
> wrote:
>>
>> Here is the basis of a lightning interface for Guile. The example shows
>> that I seem to be able to JIT compile a foreign function binding and call
>> it, at least once!
>>
>> The rest is data that I generated using the rather awful hack at
>>
>>
>> https://github.com/IanANGrant/red-october/blob/master/src/dynlibs/ffi/testrewrite.sml
>>
>> which parses the output of GCC's cpp when applied to the text "#include
>> <lightning.h>" from whence it extracts the enum declaration of lightning's
>> opcodes, and the macros that connect the opcodes with the node-generating
>> functions jit_new_node_* Then it tries to infer the types of the
>> jit_new_node functions from their names, and I explicitly define the types
>> of the instruction opcode macros on a case-by-case basis, selecting them by
>> regexps on their names.
>>
>> I hope a competent scheme programmer could get a full set of lightning
>> primitives going in a matter of a few hours using this. They won't if I have
>> made a lot of mistakes typing the opcode macros, but the same sort of code I
>> used in ML could be replicated in scheme, and then they could apply the
>> fixes in bulk. Once working, the interface could then be used to generate
>> itself, if one were that inclined. Or it could be used to implement a
>> lexical analyser generator, which Guile seems to need.
>>
>> Anyone interested in this could look at
>> http://www.mpi-sws.org/~turon/re-deriv.pdf which is nicely written and gives
>> a current perspective which seems to have benefited PLT Racket. I think it
>> would be interesting to compile the DFAs into assembler which reads mmapped
>> fles, or guile port buffers, or bytevectors. One could also compile the LALR
>> tables into the same function, and I think the result would perform quite
>> well.  Have fun, but try to keep it abstract, so that the interface can be
>> generated from the same formal spec. for EMACS lisp, say.
>>
>> The same data could be used to generate a C function interface to
>> lightning, which did more argument sanity checking than lightning's CPP
>> macros currently do.
>>
>> Ian
>>
>> I've gzipped it just to stop the mailing list sed scripts from editing it.
>> They don't seem to know much about programming :-)

Thanks,
Paulo