Update lightrec 20220910 (#686)

[pcsx_rearmed.git] / deps / lightning / doc / body.texi

@ifnottex
@dircategory Software development
@direntry
* lightning: (lightning).       Library for dynamic code generation.
@end direntry
@end ifnottex

@ifnottex
@node Top
@top @lightning{}

@iftex
@macro comma
@verbatim{|,|}
@end macro
@end iftex

@ifnottex
@macro comma
@verb{|,|}
@end macro
@end ifnottex

This document describes @value{TOPIC} the @lightning{} library for
dynamic code generation.

@menu
* Overview::                What GNU lightning is
* Installation::            Configuring and installing GNU lightning
* The instruction set::     The RISC instruction set used in GNU lightning
* GNU lightning examples::  GNU lightning's examples
* Reentrancy::              Re-entrant usage of GNU lightning
* Registers::               Accessing the whole register file
* Customizations::          Advanced code generation customizations
* Acknowledgements::        Acknowledgements for GNU lightning
@end menu
@end ifnottex

@node Overview
@chapter Introduction to @lightning{}

@iftex
This document describes @value{TOPIC} the @lightning{} library for
dynamic code generation.
@end iftex

Dynamic code generation is the generation of machine code
at runtime. It is typically used to strip a layer of interpretation
by allowing compilation to occur at runtime.  One of the most
well-known applications of dynamic code generation is perhaps that
of interpreters that compile source code to an intermediate bytecode
form, which is then recompiled to machine code at run-time: this
approach effectively combines the portability of bytecode
representations with the speed of machine code.  Another common
application of dynamic code generation is in the field of hardware
simulators and binary emulators, which can use the same techniques
to translate simulated instructions to the instructions of the
underlying machine.

Yet other applications come to mind: for example, windowing
@dfn{bitblt} operations, matrix manipulations, and network packet
filters.  Albeit very powerful and relatively well known within the
compiler community, dynamic code generation techniques are rarely
exploited to their full potential and, with the exception of the
two applications described above, have remained curiosities because
of their portability and functionality barriers: binary instructions
are generated, so programs using dynamic code generation must be
retargeted for each machine; in addition, coding a run-time code
generator is a tedious and error-prone task more than a difficult one.

@lightning{} provides a portable, fast and easily retargetable dynamic
code generation system.

To be portable, @lightning{} abstracts over current architectures'
quirks and unorthogonalities.  The interface that it exposes to is that
of a standardized RISC architecture loosely based on the SPARC and MIPS
chips.  There are a few general-purpose registers (six, not including
those used to receive and pass parameters between subroutines), and
arithmetic operations involve three operands---either three registers
or two registers and an arbitrarily sized immediate value.

On one hand, this architecture is general enough that it is possible to
generate pretty efficient code even on CISC architectures such as the
Intel x86 or the Motorola 68k families.  On the other hand, it matches
real architectures closely enough that, most of the time, the
compiler's constant folding pass ends up generating code which
assembles machine instructions without further tests.

@node Installation
@chapter Configuring and installing @lightning{}

Here we will assume that your system already has the dependencies
necessary to build @lightning{}. For more on dependencies, see
@lightning{}'s @file{README-hacking} file.

The first thing to do to build @lightning{} is to configure the
program, picking the set of macros to be used on the host
architecture; this configuration is automatically performed by
the @file{configure} shell script; to run it, merely type:
@example
     ./configure
@end example

@lightning{} supports the @code{--enable-disassembler} option, that
enables linking to GNU binutils and optionally print human readable
disassembly of the jit code. This option can be disabled by the
@code{--disable-disassembler} option.

Another option that @file{configure} accepts is
@code{--enable-assertions}, which enables several consistency checks in
the run-time assemblers.  These are not usually needed, so you can
decide to simply forget about it; also remember that these consistency
checks tend to slow down your code generator.

After you've configured @lightning{}, run @file{make} as usual.

@lightning{} has an extensive set of tests to validate it is working
correctly in the build host. To test it run:
@example
    make check
@end example

The next important step is:
@example
    make install
@end example

This ends the process of installing @lightning{}.

@node The instruction set
@chapter @lightning{}'s instruction set

@lightning{}'s instruction set was designed by deriving instructions
that closely match those of most existing RISC architectures, or
that can be easily syntesized if absent.  Each instruction is composed
of:
@itemize @bullet
@item
an operation, like @code{sub} or @code{mul}

@item
most times, a register/immediate flag (@code{r} or @code{i})

@item
an unsigned modifier (@code{u}), a type identifier or two, when applicable.
@end itemize

Examples of legal mnemonics are @code{addr} (integer add, with three
register operands) and @code{muli} (integer multiply, with two
register operands and an immediate operand).  Each instruction takes
two or three operands; in most cases, one of them can be an immediate
value instead of a register.

Most @lightning{} integer operations are signed wordsize operations,
with the exception of operations that convert types, or load or store
values to/from memory. When applicable, the types and C types are as
follow:

@example
     _c         @r{signed char}
     _uc        @r{unsigned char}
     _s         @r{short}
     _us        @r{unsigned short}
     _i         @r{int}
     _ui        @r{unsigned int}
     _l         @r{long}
     _f         @r{float}
     _d         @r{double}
@end example

Most integer operations do not need a type modifier, and when loading or
storing values to memory there is an alias to the proper operation
using wordsize operands, that is, if ommited, the type is @r{int} on
32-bit architectures and @r{long} on 64-bit architectures.  Note
that lightning also expects @code{sizeof(void*)} to match the wordsize.

When an unsigned operation result differs from the equivalent signed
operation, there is a the @code{_u} modifier.

There are at least seven integer registers, of which six are
general-purpose, while the last is used to contain the frame pointer
(@code{FP}).  The frame pointer can be used to allocate and access local
variables on the stack, using the @code{allocai} or @code{allocar}
instruction.

Of the general-purpose registers, at least three are guaranteed to be
preserved across function calls (@code{V0}, @code{V1} and
@code{V2}) and at least three are not (@code{R0}, @code{R1} and
@code{R2}).  Six registers are not very much, but this
restriction was forced by the need to target CISC architectures
which, like the x86, are poor of registers; anyway, backends can
specify the actual number of available registers with the calls
@code{JIT_R_NUM} (for caller-save registers) and @code{JIT_V_NUM}
(for callee-save registers).

There are at least six floating-point registers, named @code{F0} to
@code{F5}.  These are usually caller-save and are separate from the integer
registers on the supported architectures; on Intel architectures,
in 32 bit mode if SSE2 is not available or use of X87 is forced,
the register stack is mapped to a flat register file.  As for the
integer registers, the macro @code{JIT_F_NUM} yields the number of
floating-point registers.

The complete instruction set follows; as you can see, most non-memory
operations only take integers (either signed or unsigned) as operands;
this was done in order to reduce the instruction set, and because most
architectures only provide word and long word operations on registers.
There are instructions that allow operands to be extended to fit a larger
data type, both in a signed and in an unsigned way.

@table @b
@item Binary ALU operations
These accept three operands; the last one can be an immediate.
@code{addx} operations must directly follow @code{addc}, and
@code{subx} must follow @code{subc}; otherwise, results are undefined.
Most, if not all, architectures do not support @r{float} or @r{double}
immediate operands; lightning emulates those operations by moving the
immediate to a temporary register and emiting the call with only
register operands.
@example
addr         _f  _d  O1 = O2 + O3
addi         _f  _d  O1 = O2 + O3
addxr                O1 = O2 + (O3 + carry)
addxi                O1 = O2 + (O3 + carry)
addcr                O1 = O2 + O3, set carry
addci                O1 = O2 + O3, set carry
subr         _f  _d  O1 = O2 - O3
subi         _f  _d  O1 = O2 - O3
subxr                O1 = O2 - (O3 + carry)
subxi                O1 = O2 - (O3 + carry)
subcr                O1 = O2 - O3, set carry
subci                O1 = O2 - O3, set carry
rsbr         _f  _d  O1 = O3 - O1
rsbi         _f  _d  O1 = O3 - O1
mulr         _f  _d  O1 = O2 * O3
muli         _f  _d  O1 = O2 * O3
divr     _u  _f  _d  O1 = O2 / O3
divi     _u  _f  _d  O1 = O2 / O3
remr     _u          O1 = O2 % O3
remi     _u          O1 = O2 % O3
andr                 O1 = O2 & O3
andi                 O1 = O2 & O3
orr                  O1 = O2 | O3
ori                  O1 = O2 | O3
xorr                 O1 = O2 ^ O3
xori                 O1 = O2 ^ O3
lshr                 O1 = O2 << O3
lshi                 O1 = O2 << O3
rshr     _u          O1 = O2 >> O3@footnote{The sign bit is propagated unless using the @code{_u} modifier.}
rshi     _u          O1 = O2 >> O3@footnote{The sign bit is propagated unless using the @code{_u} modifier.}
movzr                O1 = O3 ? O1 : O2
movnr                O1 = O3 ? O2 : O1
@end example

@item Four operand binary ALU operations
These accept two result registers, and two operands; the last one can
be an immediate. The first two arguments cannot be the same register.

@code{qmul} stores the low word of the result in @code{O1} and the
high word in @code{O2}. For unsigned multiplication, @code{O2} zero
means there was no overflow. For signed multiplication, no overflow
check is based on sign, and can be detected if @code{O2} is zero or
minus one.

@code{qdiv} stores the quotient in @code{O1} and the remainder in
@code{O2}. It can be used as quick way to check if a division is
exact, in which case the remainder is zero.

@example
qmulr    _u       O1 O2 = O3 * O4
qmuli    _u       O1 O2 = O3 * O4
qdivr    _u       O1 O2 = O3 / O4
qdivi    _u       O1 O2 = O3 / O4
@end example

@item Unary ALU operations
These accept two operands, both of which must be registers.
@example
negr         _f  _d  O1 = -O2
comr                 O1 = ~O2
@end example

These unary ALU operations are only defined for float operands.
@example
absr         _f  _d  O1 = fabs(O2)
sqrtr                O1 = sqrt(O2)
@end example

Besides requiring the @code{r} modifier, there are no unary operations
with an immediate operand.

@item Compare instructions
These accept three operands; again, the last can be an immediate.
The last two operands are compared, and the first operand, that must be
an integer register, is set to either 0 or 1, according to whether the
given condition was met or not.

The conditions given below are for the standard behavior of C,
where the ``unordered'' comparison result is mapped to false.

@example
ltr       _u  _f  _d  O1 =  (O2 <  O3)
lti       _u  _f  _d  O1 =  (O2 <  O3)
ler       _u  _f  _d  O1 =  (O2 <= O3)
lei       _u  _f  _d  O1 =  (O2 <= O3)
gtr       _u  _f  _d  O1 =  (O2 >  O3)
gti       _u  _f  _d  O1 =  (O2 >  O3)
ger       _u  _f  _d  O1 =  (O2 >= O3)
gei       _u  _f  _d  O1 =  (O2 >= O3)
eqr           _f  _d  O1 =  (O2 == O3)
eqi           _f  _d  O1 =  (O2 == O3)
ner           _f  _d  O1 =  (O2 != O3)
nei           _f  _d  O1 =  (O2 != O3)
unltr         _f  _d  O1 = !(O2 >= O3)
unler         _f  _d  O1 = !(O2 >  O3)
ungtr         _f  _d  O1 = !(O2 <= O3)
unger         _f  _d  O1 = !(O2 <  O3)
uneqr         _f  _d  O1 = !(O2 <  O3) && !(O2 >  O3)
ltgtr         _f  _d  O1 = !(O2 >= O3) || !(O2 <= O3)
ordr          _f  _d  O1 =  (O2 == O2) &&  (O3 == O3)
unordr        _f  _d  O1 =  (O2 != O2) ||  (O3 != O3)
@end example

@item Transfer operations
These accept two operands; for @code{ext} both of them must be
registers, while @code{mov} accepts an immediate value as the second
operand.

Unlike @code{movr} and @code{movi}, the other instructions are used
to truncate a wordsize operand to a smaller integer data type or to
convert float data types. You can also use @code{extr} to convert an
integer to a floating point value: the usual options are @code{extr_f}
and @code{extr_d}.

@example
movr                                 _f  _d  O1 = O2
movi                                 _f  _d  O1 = O2
extr      _c  _uc  _s  _us  _i  _ui  _f  _d  O1 = O2
truncr                               _f  _d  O1 = trunc(O2)
@end example

In 64-bit architectures it may be required to use @code{truncr_f_i},
@code{truncr_f_l}, @code{truncr_d_i} and @code{truncr_d_l} to match
the equivalent C code.  Only the @code{_i} modifier is available in
32-bit architectures.

@example
truncr_f_i    = <int> O1 = <float> O2
truncr_f_l    = <long>O1 = <float> O2
truncr_d_i    = <int> O1 = <double>O2
truncr_d_l    = <long>O1 = <double>O2
@end example

The float conversion operations are @emph{destination first,
source second}, but the order of the types is reversed.  This happens
for historical reasons.

@example
extr_f_d    = <double>O1 = <float> O2
extr_d_f    = <float> O1 = <double>O2
@end example

@item Network extensions
These accept two operands, both of which must be registers; these
two instructions actually perform the same task, yet they are
assigned to two mnemonics for the sake of convenience and
completeness.  As usual, the first operand is the destination and
the second is the source.
The @code{_ul} variant is only available in 64-bit architectures.
@example
htonr    _us _ui _ul @r{Host-to-network (big endian) order}
ntohr    _us _ui _ul @r{Network-to-host order }
@end example

@code{bswapr} can be used to unconditionally byte-swap an operand.
On little-endian architectures, @code{htonr} and @code{ntohr} resolve
to this.
The @code{_ul} variant is only available in 64-bit architectures.
@example
bswapr    _us _ui _ul  01 = byte_swap(02)
@end example

@item Load operations
@code{ld} accepts two operands while @code{ldx} accepts three;
in both cases, the last can be either a register or an immediate
value. Values are extended (with or without sign, according to
the data type specification) to fit a whole register.
The @code{_ui} and @code{_l} types are only available in 64-bit
architectures.  For convenience, there is a version without a
type modifier for integer or pointer operands that uses the
appropriate wordsize call.
@example
ldr     _c  _uc  _s  _us  _i  _ui  _l  _f  _d  O1 = *O2
ldi     _c  _uc  _s  _us  _i  _ui  _l  _f  _d  O1 = *O2
ldxr    _c  _uc  _s  _us  _i  _ui  _l  _f  _d  O1 = *(O2+O3)
ldxi    _c  _uc  _s  _us  _i  _ui  _l  _f  _d  O1 = *(O2+O3)
@end example

@item Store operations
@code{st} accepts two operands while @code{stx} accepts three; in
both cases, the first can be either a register or an immediate
value. Values are sign-extended to fit a whole register.
@example
str     _c  _uc  _s  _us  _i  _ui  _l  _f  _d  *O1 = O2
sti     _c  _uc  _s  _us  _i  _ui  _l  _f  _d  *O1 = O2
stxr    _c  _uc  _s  _us  _i  _ui  _l  _f  _d  *(O1+O2) = O3
stxi    _c  _uc  _s  _us  _i  _ui  _l  _f  _d  *(O1+O2) = O3
@end example
As for the load operations, the @code{_ui} and @code{_l} types are
only available in 64-bit architectures, and for convenience, there
is a version without a type modifier for integer or pointer operands
that uses the appropriate wordsize call.

@item Argument management
These are:
@example
prepare     (not specified)
va_start    (not specified)
pushargr                                   _f  _d
pushargi                                   _f  _d
va_push     (not specified)
arg                                        _f  _d
getarg      _c  _uc  _s  _us  _i  _ui  _l  _f  _d
va_arg                                         _d
putargr                                    _f  _d
putargi                                    _f  _d
ret         (not specified)
retr                                       _f  _d
reti                                       _f  _d
va_end      (not specified)
retval      _c  _uc  _s  _us  _i  _ui  _l  _f  _d
epilog      (not specified)
@end example
As with other operations that use a type modifier, the @code{_ui} and
@code{_l} types are only available in 64-bit architectures, but there
are operations without a type modifier that alias to the appropriate
integer operation with wordsize operands.

@code{prepare}, @code{pusharg}, and @code{retval} are used by the caller,
while @code{arg}, @code{getarg} and @code{ret} are used by the callee.
A code snippet that wants to call another procedure and has to pass
arguments must, in order: use the @code{prepare} instruction and use
the @code{pushargr} or @code{pushargi} to push the arguments @strong{in
left to right order}; and use @code{finish} or @code{call} (explained below)
to perform the actual call.

@code{va_start} returns a @code{C} compatible @code{va_list}. To fetch
arguments, use @code{va_arg} for integers and @code{va_arg_d} for doubles.
@code{va_push} is required when passing a @code{va_list} to another function,
because not all architectures expect it as a single pointer. Known case
is DEC Alpha, that requires it as a structure passed by value.

@code{arg}, @code{getarg} and @code{putarg} are used by the callee.
@code{arg} is different from other instruction in that it does not
actually generate any code: instead, it is a function which returns
a value to be passed to @code{getarg} or @code{putarg}. @footnote{``Return
a value'' means that @lightning{} code that compile these
instructions return a value when expanded.} You should call
@code{arg} as soon as possible, before any function call or, more
easily, right after the @code{prolog} instructions
(which is treated later).

@code{getarg} accepts a register argument and a value returned by
@code{arg}, and will move that argument to the register, extending
it (with or without sign, according to the data type specification)
to fit a whole register.  These instructions are more intimately
related to the usage of the @lightning{} instruction set in code
that generates other code, so they will be treated more
specifically in @ref{GNU lightning examples, , Generating code at
run-time}.

@code{putarg} is a mix of @code{getarg} and @code{pusharg} in that
it accepts as first argument a register or immediate, and as
second argument a value returned by @code{arg}. It allows changing,
or restoring an argument to the current function, and is a
construct required to implement tail call optimization. Note that
arguments in registers are very cheap, but will be overwritten
at any moment, including on some operations, for example division,
that on several ports is implemented as a function call.

Finally, the @code{retval} instruction fetches the return value of a
called function in a register.  The @code{retval} instruction takes a
register argument and copies the return value of the previously called
function in that register.  A function with a return value should use
@code{retr} or @code{reti} to put the return value in the return register
before returning.  @xref{Fibonacci, the Fibonacci numbers}, for an example.

@code{epilog} is an optional call, that marks the end of a function
body. It is automatically generated by @lightning{} if starting a new
function (what should be done after a @code{ret} call) or finishing
generating jit.
It is very important to note that the fact that @code{epilog} being
optional may cause a common mistake. Consider this:
@example
fun1:
    prolog
    ...
    ret
fun2:
    prolog
@end example
Because @code{epilog} is added when finding a new @code{prolog},
this will cause the @code{fun2} label to actually be before the
return from @code{fun1}. Because @lightning{} will actually
understand it as:
@example
fun1:
    prolog
    ...
    ret
fun2:
    epilog
    prolog
@end example

You should observe a few rules when using these macros.  First of
all, if calling a varargs function, you should use the @code{ellipsis}
call to mark the position of the ellipsis in the C prototype.

You should not nest calls to @code{prepare} inside a
@code{prepare/finish} block.  Doing this will result in undefined
behavior. Note that for functions with zero arguments you can use
just @code{call}.

@item Branch instructions
Like @code{arg}, these also return a value which, in this case,
is to be used to compile forward branches as explained in
@ref{Fibonacci, , Fibonacci numbers}.  They accept two operands to be
compared; of these, the last can be either a register or an immediate.
They are:
@example
bltr      _u  _f  _d  @r{if }(O2 <  O3)@r{ goto }O1
blti      _u  _f  _d  @r{if }(O2 <  O3)@r{ goto }O1
bler      _u  _f  _d  @r{if }(O2 <= O3)@r{ goto }O1
blei      _u  _f  _d  @r{if }(O2 <= O3)@r{ goto }O1
bgtr      _u  _f  _d  @r{if }(O2 >  O3)@r{ goto }O1
bgti      _u  _f  _d  @r{if }(O2 >  O3)@r{ goto }O1
bger      _u  _f  _d  @r{if }(O2 >= O3)@r{ goto }O1
bgei      _u  _f  _d  @r{if }(O2 >= O3)@r{ goto }O1
beqr          _f  _d  @r{if }(O2 == O3)@r{ goto }O1
beqi          _f  _d  @r{if }(O2 == O3)@r{ goto }O1
bner          _f  _d  @r{if }(O2 != O3)@r{ goto }O1
bnei          _f  _d  @r{if }(O2 != O3)@r{ goto }O1

bunltr        _f  _d  @r{if }!(O2 >= O3)@r{ goto }O1
bunler        _f  _d  @r{if }!(O2 >  O3)@r{ goto }O1
bungtr        _f  _d  @r{if }!(O2 <= O3)@r{ goto }O1
bunger        _f  _d  @r{if }!(O2 <  O3)@r{ goto }O1
buneqr        _f  _d  @r{if }!(O2 <  O3) && !(O2 >  O3)@r{ goto }O1
bltgtr        _f  _d  @r{if }!(O2 >= O3) || !(O2 <= O3)@r{ goto }O1
bordr         _f  _d  @r{if } (O2 == O2) &&  (O3 == O3)@r{ goto }O1
bunordr       _f  _d  @r{if }!(O2 != O2) ||  (O3 != O3)@r{ goto }O1

bmsr                  @r{if }O2 &  O3@r{ goto }O1
bmsi                  @r{if }O2 &  O3@r{ goto }O1
bmcr                  @r{if }!(O2 & O3)@r{ goto }O1
bmci                  @r{if }!(O2 & O3)@r{ goto }O1@footnote{These mnemonics mean, respectively, @dfn{branch if mask set} and @dfn{branch if mask cleared}.}
boaddr    _u          O2 += O3@r{, goto }O1@r{ if overflow}
boaddi    _u          O2 += O3@r{, goto }O1@r{ if overflow}
bxaddr    _u          O2 += O3@r{, goto }O1@r{ if no overflow}
bxaddi    _u          O2 += O3@r{, goto }O1@r{ if no overflow}
bosubr    _u          O2 -= O3@r{, goto }O1@r{ if overflow}
bosubi    _u          O2 -= O3@r{, goto }O1@r{ if overflow}
bxsubr    _u          O2 -= O3@r{, goto }O1@r{ if no overflow}
bxsubi    _u          O2 -= O3@r{, goto }O1@r{ if no overflow}
@end example

@item Jump and return operations
These accept one argument except @code{ret} and @code{jmpi} which
have none; the difference between @code{finishi} and @code{calli}
is that the latter does not clean the stack from pushed parameters
(if any) and the former must @strong{always} follow a @code{prepare}
instruction.
@example
callr     (not specified)                @r{function call to register O1}
calli     (not specified)                @r{function call to immediate O1}
finishr   (not specified)                @r{function call to register O1}
finishi   (not specified)                @r{function call to immediate O1}
jmpr      (not specified)                @r{unconditional jump to register}
jmpi      (not specified)                @r{unconditional jump}
ret       (not specified)                @r{return from subroutine}
retr      _c _uc _s _us _i _ui _l _f _d
reti      _c _uc _s _us _i _ui _l _f _d
retval    _c _uc _s _us _i _ui _l _f _d  @r{move return value}
                                         @r{to register}
@end example

Like branch instruction, @code{jmpi} also returns a value which is to
be used to compile forward branches. @xref{Fibonacci, , Fibonacci
numbers}.

@item Labels
There are 3 @lightning{} instructions to create labels:
@example
label     (not specified)                @r{simple label}
forward   (not specified)                @r{forward label}
indirect  (not specified)                @r{special simple label}
@end example

The following instruction is used to specify a minimal alignment for
the next instruction, usually with a label:
@example
align     (not specified)                @r{align code}
@end example

@code{label} is normally used as @code{patch_at} argument for backward
jumps.

@example
        jit_node_t *jump, *label;
label = jit_label();
        ...
        jump = jit_beqr(JIT_R0, JIT_R1);
        jit_patch_at(jump, label);
@end example

@code{forward} is used to patch code generation before the actual
position of the label is known.

@example
        jit_node_t *jump, *label;
label = jit_forward();
        jump = jit_beqr(JIT_R0, JIT_R1);
        jit_patch_at(jump, label);
        ...
        jit_link(label);
@end example

@code{indirect} is useful when creating jump tables, and tells
@lightning{} to not optimize out a label that is not the target of
any jump, because an indirect jump may land where it is defined.

@example
        jit_node_t *jump, *label;
        ...
        jmpr(JIT_R0);                    @rem{/* may jump to label */}
        ...
label = jit_indirect();
@end example

@code{indirect} is an special case of @code{note} and @code{name}
because it is a valid argument to @code{address}.

Note that the usual idiom to write the previous example is
@example
        jit_node_t *addr, *jump;
addr  = jit_movi(JIT_R0, 0);             @rem{/* immediate is ignored */}
        ...
        jmpr(JIT_R0);
        ...
        jit_patch(addr);                 @rem{/* implicit label added */}
@end example

that automatically binds the implicit label added by @code{patch} with
the @code{movi}, but on some special conditions it is required to create
an "unbound" label.

@code{align} is useful for creating multiple entry points to a
(trampoline) function that are all accessible through a single
function pointer.  @code{align} receives an integer argument that
defines the minimal alignment of the address of a label directly
following the @code{align} instruction.  The integer argument must be
a power of two and the effective alignment will be a power of two no
less than the argument to @code{align}.  If the argument to
@code{align} is 16 or more, the effective alignment will match the
specified minimal alignment exactly.

@example
          jit_node_t *forward, *label1, *label2, *jump;
          unsigned char *addr1, *addr2;
forward = jit_forward();
          jit_align(16);
label1  = jit_indirect();                @rem{/* first entry point */}
jump    = jit_jmpi();                    @rem{/* jump to first handler */}
          jit_patch_at(jump, forward);
          jit_align(16);
label2  = jit_indirect();                @rem{/* second entry point */}
          ...                            @rem{/* second handler */}
          jit_jmpr(...);
          jit_link(forward);
          ...                            @rem{/* first handler /*}
          jit_jmpr(...);
          ...
          jit_emit();
          addr1 = jit_address(label1);
          addr2 = jit_address(label2);
          assert(addr2 - addr1 == 16);   @rem{/* only one of the addresses needs to be remembered */}
@end example

@item Function prolog

These macros are used to set up a function prolog.  The @code{allocai}
call accept a single integer argument and returns an offset value
for stack storage access.  The @code{allocar} accepts two registers
arguments, the first is set to the offset for stack access, and the
second is the size in bytes argument.

@example
prolog    (not specified)                @r{function prolog}
allocai   (not specified)                @r{reserve space on the stack}
allocar   (not specified)                @r{allocate space on the stack}
@end example

@code{allocai} receives the number of bytes to allocate and returns
the offset from the frame pointer register @code{FP} to the base of
the area.

@code{allocar} receives two register arguments.  The first is where
to store the offset from the frame pointer register @code{FP} to the
base of the area.  The second argument is the size in bytes.  Note
that @code{allocar} is dynamic allocation, and special attention
should be taken when using it.  If called in a loop, every iteration
will allocate stack space.  Stack space is aligned from 8 to 64 bytes
depending on backend requirements, even if allocating only one byte.
It is advisable to not use it with @code{frame} and @code{tramp}; it
should work with @code{frame} with special care to call only once,
but is not supported if used in @code{tramp}, even if called only
once.

As a small appetizer, here is a small function that adds 1 to the input
parameter (an @code{int}).  I'm using an assembly-like syntax here which
is a bit different from the one used when writing real subroutines with
@lightning{}; the real syntax will be introduced in @xref{GNU lightning
examples, , Generating code at run-time}.

@example
incr:
     prolog
in = arg                     @rem{! We have an integer argument}
     getarg    R0, in        @rem{! Move it to R0}
     addi      R0, R0, 1     @rem{! Add 1}
     retr      R0            @rem{! And return the result}
@end example

And here is another function which uses the @code{printf} function from
the standard C library to write a number in hexadecimal notation:

@example
printhex:
     prolog
in = arg                     @rem{! Same as above}
     getarg    R0, in
     prepare                 @rem{! Begin call sequence for printf}
     pushargi  "%x"          @rem{! Push format string}
     ellipsis                @rem{! Varargs start here}
     pushargr  R0            @rem{! Push second argument}
     finishi   printf        @rem{! Call printf}
     ret                     @rem{! Return to caller}
@end example

@item Register liveness

During code generation, @lightning{} occasionally needs scratch registers
or needs to use architecture-defined registers.  For that, @lightning{}
internally maintains register liveness information.

In the following example, @code{qdivr} will need special registers like
@code{R0} on some architectures.  As @lightning{} understands that
@code{R0} is used in the subsequent instruction, it will create
save/restore code for @code{R0} in case.

@example
...
qdivr V0, V1, V2, V3
movr  V3, R0
...
@end example

The same is not true in the example that follows.  Here, @code{R0} is
not alive after the division operation because @code{R0} is neither an
argument register nor a callee-save register.  Thus, no save/restore
code for @code{R0} will be created in case.

@example
...
qdivr V0, V1, V2, V3
jmpr  R1
...
@end example

The @code{live} instruction can be used to mark a register as live after
it as in the following example.  Here, @code{R0} will be preserved
across the division.

@example
...
qdivr V0, V1, V2, V3
live R0
jmpr R1
...
@end example

The @code{live} instruction is useful at code entry and exit points,
like after and before a @code{callr} instruction.

@item Trampolines, continuations and tail call optimization

Frequently it is required to generate jit code that must jump to
code generated later, possibly from another @code{jit_context_t}.
These require compatible stack frames.

@lightning{} provides two primitives from where trampolines,
continuations and tail call optimization can be implemented.

@example
frame   (not specified)                  @r{create stack frame}
tramp   (not specified)                  @r{assume stack frame}
@end example

@code{frame} receives an integer argument@footnote{It is not
automatically computed because it does not know about the
requirement of later generated code.} that defines the size in
bytes for the stack frame of the current, @code{C} callable,
jit function. To calculate this value, a good formula is maximum
number of arguments to any called native function times
eight@footnote{Times eight so that it works for double arguments.
And would not need conditionals for ports that pass arguments in
the stack.}, plus the sum of the arguments to any call to
@code{jit_allocai}. @lightning{} automatically adjusts this value
for any backend specific stack memory it may need, or any
alignment constraint.

@code{frame} also instructs @lightning{} to save all callee
save registers in the prolog and reload in the epilog.

@example
main:                        @rem{! jit entry point}
     prolog                  @rem{! function prolog}
     frame  256              @rem{! save all callee save registers and}
                             @rem{! reserve at least 256 bytes in stack}
main_loop:
     ...
     jmpi   handler          @rem{! jumps to external code}
     ...
     ret                     @rem{! return to the caller}
@end example

@code{tramp} differs from @code{frame} only that a prolog and epilog
will not be generated. Note that @code{prolog} must still be used.
The code under @code{tramp} must be ready to be entered with a jump
at the prolog position, and instead of a return, it must end with
a non conditional jump. @code{tramp} exists solely for the fact
that it allows optimizing out prolog and epilog code that would
never be executed.

@example
handler:                     @rem{! handler entry point}
     prolog                  @rem{! function prolog}
     tramp  256              @rem{! assumes all callee save registers}
                             @rem{! are saved and there is at least}
                             @rem{! 256 bytes in stack}
     ...
     jmpi   main_loop        @rem{! return to the main loop}
@end example

@lightning{} only supports Tail Call Optimization using the
@code{tramp} construct. Any other way is not guaranteed to
work on all ports.

An example of a simple (recursive) tail call optimization:

@example
factorial:                   @rem{! Entry point of the factorial function}
     prolog
in = arg                     @rem{! Receive an integer argument}
     getarg R0, in           @rem{! Move argument to RO}
     prepare
         pushargi 1          @rem{! This is the accumulator}
         pushargr R0         @rem{! This is the argument}
     finishi fact            @rem{! Call the tail call optimized function}
     retval R0               @rem{! Fetch the result}
     retr R0                 @rem{! Return it}
     epilog                  @rem{! Epilog *before* label before prolog}

fact:                        @rem{! Entry point of the helper function}
     prolog
     frame 16                @rem{! Reserve 16 bytes in the stack}
fact_entry:                  @rem{! This is the tail call entry point}
ac = arg                     @rem{! The accumulator is the first argument}
in = arg                     @rem{! The factorial argument}
     getarg R0, ac           @rem{! Move the accumulator to R0}
     getarg R1, in           @rem{! Move the argument to R1}
     blei fact_out, R1, 1    @rem{! Done if argument is one or less}
     mulr R0, R0, R1         @rem{! accumulator *= argument}
     putargr R0, ac          @rem{! Update the accumulator}
     subi R1, R1, 1          @rem{! argument -= 1}
     putargr R1, in          @rem{! Update the argument}
     jmpi fact_entry         @rem{! Tail Call Optimize it!}
fact_out:
     retr R0                 @rem{! Return the accumulator}
@end example

@item Predicates
@example
forward_p      (not specified)           @r{forward label predicate}
indirect_p     (not specified)           @r{indirect label predicate}
target_p       (not specified)           @r{used label predicate}
arg_register_p (not specified)           @r{argument kind predicate}
callee_save_p  (not specified)           @r{callee save predicate}
pointer_p      (not specified)           @r{pointer predicate}
@end example

@code{forward_p} expects a @code{jit_node_t*} argument, and
returns non zero if it is a forward label reference, that is,
a label returned by @code{forward}, that still needs a
@code{link} call.

@code{indirect_p} expects a @code{jit_node_t*} argument, and returns
non zero if it is an indirect label reference, that is, a label that
was returned by @code{indirect}.

@code{target_p} expects a @code{jit_node_t*} argument, that is any
kind of label, and will return non zero if there is at least one
jump or move referencing it.

@code{arg_register_p} expects a @code{jit_node_t*} argument, that must
have been returned by @code{arg}, @code{arg_f} or @code{arg_d}, and
will return non zero if the argument lives in a register. This call
is useful to know the live range of register arguments, as those
are very fast to read and write, but have volatile values.

@code{callee_save_p} exects a valid @code{JIT_Rn}, @code{JIT_Vn}, or
@code{JIT_Fn}, and will return non zero if the register is callee
save. This call is useful because on several ports, the @code{JIT_Rn}
and @code{JIT_Fn} registers are actually callee save; no need
to save and load the values when making function calls.

@code{pointer_p} expects a pointer argument, and will return non
zero if the pointer is inside the generated jit code. Must be
called after @code{jit_emit} and before @code{jit_destroy_state}.

@item Atomic operations
Only compare-and-swap is implemented. It accepts four operands;
the second can be an immediate.

The first argument is set with a boolean value telling if the operation
did succeed.

Arguments must be different, cannot use the result register to also pass
an argument.

The second argument is the address of a machine word.

The third argument is the old value.

The fourth argument is the new value.

@example
casr                                  01 = (*O2 == O3) ? (*O2 = O4, 1) : 0
casi                                  01 = (*O2 == O3) ? (*O2 = O4, 1) : 0
@end example

If value at the address in the second argument is equal to the third
argument, the address value is atomically modified to the value of the
fourth argument and the first argument is set to a non zero value.

If the value at the address in the second argument is not equal to the
third argument nothing is done and the first argument is set to zero.
@end table

@node GNU lightning examples
@chapter Generating code at run-time

To use @lightning{}, you should include the @file{lightning.h} file that
is put in your include directory by the @samp{make install} command.

Each of the instructions above translates to a macro or function call.
All you have to do is prepend @code{jit_} (lowercase) to opcode names
and @code{JIT_} (uppercase) to register names.  Of course, parameters
are to be put between parentheses.

This small tutorial presents three examples:

@iftex
@itemize @bullet
@item
The @code{incr} function found in @ref{The instruction set, ,
@lightning{}'s instruction set}:

@item
A simple function call to @code{printf}

@item
An RPN calculator.

@item
Fibonacci numbers
@end itemize
@end iftex
@ifnottex
@menu
* incr::             A function which increments a number by one
* printf::           A simple function call to printf
* RPN calculator::   A more complex example, an RPN calculator
* Fibonacci::        Calculating Fibonacci numbers
@end menu
@end ifnottex

@node incr
@section A function which increments a number by one

Let's see how to create and use the sample @code{incr} function created
in @ref{The instruction set, , @lightning{}'s instruction set}:

@example
#include <stdio.h>
#include <lightning.h>

static jit_state_t *_jit;

typedef int (*pifi)(int);    @rem{/* Pointer to Int Function of Int */}

int main(int argc, char *argv[])
@{
  jit_node_t  *in;
  pifi         incr;

  init_jit(argv[0]);
  _jit = jit_new_state();

  jit_prolog();                    @rem{/* @t{     prolog             } */}
  in = jit_arg();                  @rem{/* @t{     in = arg           } */}
  jit_getarg(JIT_R0, in);          @rem{/* @t{     getarg R0          } */}
  jit_addi(JIT_R0, JIT_R0, 1);     @rem{/* @t{     addi   R0@comma{} R0@comma{} 1   } */}
  jit_retr(JIT_R0);                @rem{/* @t{     retr   R0          } */}

  incr = jit_emit();
  jit_clear_state();

  @rem{/* call the generated code@comma{} passing 5 as an argument */}
  printf("%d + 1 = %d\n", 5, incr(5));

  jit_destroy_state();
  finish_jit();
  return 0;
@}
@end example

Let's examine the code line by line (well, almost@dots{}):

@table @t
@item #include <lightning.h>
You already know about this.  It defines all of @lightning{}'s macros.

@item static jit_state_t *_jit;
You might wonder about what is @code{jit_state_t}.  It is a structure
that stores jit code generation information.  The name @code{_jit} is
special, because since multiple jit generators can run at the same
time, you must either @r{#define _jit my_jit_state} or name it
@code{_jit}.

@item typedef int (*pifi)(int);
Just a handy typedef for a pointer to a function that takes an
@code{int} and returns another.

@item jit_node_t  *in;
Declares a variable to hold an identifier for a function argument. It
is an opaque pointer, that will hold the return of a call to @code{arg}
and be used as argument to @code{getarg}.

@item pifi         incr;
Declares a function pointer variable to a function that receives an
@code{int} and returns an @code{int}.

@item init_jit(argv[0]);
You must call this function before creating a @code{jit_state_t}
object. This function does global state initialization, and may need
to detect CPU or Operating System features.  It receives a string
argument that is later used to read symbols from a shared object using
GNU binutils if disassembly was enabled at configure time. If no
disassembly will be performed a NULL pointer can be used as argument.

@item _jit = jit_new_state();
This call initializes a @lightning{} jit state.

@item jit_prolog();
Ok, so we start generating code for our beloved function@dots{}

@item in = jit_arg();
@itemx jit_getarg(JIT_R0, in);
We retrieve the first (and only) argument, an integer, and store it
into the general-purpose register @code{R0}.

@item jit_addi(JIT_R0, JIT_R0, 1);
We add one to the content of the register.

@item jit_retr(JIT_R0);
This instruction generates a standard function epilog that returns
the contents of the @code{R0} register.

@item incr = jit_emit();
This instruction is very important.  It actually translates the
@lightning{} macros used before to machine code, flushes the generated
code area out of the processor's instruction cache and return a
pointer to the start of the code.

@item jit_clear_state();
This call cleanups any data not required for jit execution. Note
that it must be called after any call to @code{jit_print} or
@code{jit_address}, as this call destroy the @lightning{}
intermediate representation.

@item printf("%d + 1 = %d", 5, incr(5));
Calling our function is this simple---it is not distinguishable from
a normal C function call, the only difference being that @code{incr}
is a variable.

@item jit_destroy_state();
Releases all memory associated with the jit context. It should be
called after known the jit will no longer be called.

@item finish_jit();
This call cleanups any global state hold by @lightning{}, and is
advisable to call it once jit code will no longer be generated.
@end table

@lightning{} abstracts two phases of dynamic code generation: selecting
instructions that map the standard representation, and emitting binary
code for these instructions.  The client program has the responsibility
of describing the code to be generated using the standard @lightning{}
instruction set.

Let's examine the code generated for @code{incr} on the SPARC and x86_64
architecture (on the right is the code that an assembly-language
programmer would write):

@table @b
@item SPARC
@example
      save  %sp, -112, %sp
      mov  %i0, %g2                 retl
      inc  %g2                      inc %o0
      mov  %g2, %i0
      restore
      retl
      nop
@end example
In this case, @lightning{} introduces overhead to create a register
window (not knowing that the procedure is a leaf procedure) and to
move the argument to the general purpose register @code{R0} (which
maps to @code{%g2} on the SPARC).
@end table

@table @b
@item x86_64
@example
    sub   $0x30,%rsp
    mov   %rbp,(%rsp)
    mov   %rsp,%rbp
    sub   $0x18,%rsp
    mov   %rdi,%rax            mov %rdi, %rax
    add   $0x1,%rax            inc %rax
    mov   %rbp,%rsp
    mov   (%rsp),%rbp
    add   $0x30,%rsp
    retq                       retq
@end example
In this case, the main overhead is due to the function's prolog and
epilog, and stack alignment after reserving stack space for word
to/from float conversions or moving data from/to x87 to/from SSE.
Note that besides allocating space to save callee saved registers,
no registers are saved/restored because @lightning{} notices those
registers are not modified. There is currently no logic to detect
if it needs to allocate stack space for type conversions neither
proper leaf function detection, but these are subject to change
(FIXME).
@end table

@node printf
@section A simple function call to @code{printf}

Again, here is the code for the example:

@example
#include <stdio.h>
#include <lightning.h>

static jit_state_t *_jit;

typedef void (*pvfi)(int);      @rem{/* Pointer to Void Function of Int */}

int main(int argc, char *argv[])
@{
  pvfi          myFunction;             @rem{/* ptr to generated code */}
  jit_node_t    *start, *end;           @rem{/* a couple of labels */}
  jit_node_t    *in;                    @rem{/* to get the argument */}

  init_jit(argv[0]);
  _jit = jit_new_state();

  start = jit_note(__FILE__, __LINE__);
  jit_prolog();
  in = jit_arg();
  jit_getarg(JIT_R1, in);
  jit_prepare();
  jit_pushargi((jit_word_t)"generated %d bytes\n");
  jit_ellipsis();
  jit_pushargr(JIT_R1);
  jit_finishi(printf);
  jit_ret();
  jit_epilog();
  end = jit_note(__FILE__, __LINE__);

  myFunction = jit_emit();

  @rem{/* call the generated code@comma{} passing its size as argument */}
  myFunction((char*)jit_address(end) - (char*)jit_address(start));
  jit_clear_state();

  jit_disassemble();

  jit_destroy_state();
  finish_jit();
  return 0;
@}
@end example

The function shows how many bytes were generated.  Most of the code
is not very interesting, as it resembles very closely the program
presented in @ref{incr, , A function which increments a number by one}.

For this reason, we're going to concentrate on just a few statements.

@table @t
@item start = jit_note(__FILE__, __LINE__);
@itemx @r{@dots{}}
@itemx end = jit_note(__FILE__, __LINE__);
These two instruction call the @code{jit_note} macro, which creates
a note in the jit code; arguments to @code{jit_note} usually are a
filename string and line number integer, but using NULL for the
string argument is perfectly valid if only need to create a simple
marker in the code.

@item jit_ellipsis();
@code{ellipsis} usually is only required if calling varargs functions
with double arguments, but it is a good practice to properly describe
the @r{@dots{}} in the call sequence.

@item jit_pushargi((jit_word_t)"generated %d bytes\n");
Note the use of the @code{(jit_word_t)} cast, that is used only
to avoid a compiler warning, due to using a pointer where a
wordsize integer type was expected.

@item jit_prepare();
@itemx @r{@dots{}}
@itemx jit_finishi(printf);
Once the arguments to @code{printf} have been pushed, what means
moving them to stack or register arguments, the @code{printf}
function is called and the stack cleaned.  Note how @lightning{}
abstracts the differences between different architectures and
ABI's -- the client program does not know how parameter passing
works on the host architecture.

@item jit_epilog();
Usually it is not required to call @code{epilog}, but because it
is implicitly called when noticing the end of a function, if the
@code{end} variable was set with a @code{note} call after the
@code{ret}, it would not consider the function epilog.

@item myFunction((char*)jit_address(end) - (char*)jit_address(start));
This calls the generate jit function passing as argument the offset
difference from the @code{start} and @code{end} notes. The @code{address}
call must be done after the @code{emit} call or either a fatal error
will happen (if @lightning{} is built with assertions enable) or an
undefined value will be returned.

@item jit_clear_state();
Note that @code{jit_clear_state} was called after executing jit in
this example. It was done because it must be called after any call
to @code{jit_address} or @code{jit_print}.

@item jit_disassemble();
@code{disassemble} will dump the generated code to standard output,
unless @lightning{} was built with the disassembler disabled, in which
case no output will be shown.
@end table

@node RPN calculator
@section A more complex example, an RPN calculator

We create a small stack-based RPN calculator which applies a series
of operators to a given parameter and to other numeric operands.
Unlike previous examples, the code generator is fully parameterized
and is able to compile different formulas to different functions.
Here is the code for the expression compiler; a sample usage will
follow.

Since @lightning{} does not provide push/pop instruction, this
example uses a stack-allocated area to store the data.  Such an
area can be allocated using the macro @code{allocai}, which
receives the number of bytes to allocate and returns the offset
from the frame pointer register @code{FP} to the base of the
area.

Usually, you will use the @code{ldxi} and @code{stxi} instruction
to access stack-allocated variables.  However, it is possible to
use operations such as @code{add} to compute the address of the
variables, and pass the address around.

@example
#include <stdio.h>
#include <lightning.h>

typedef int (*pifi)(int);       @rem{/* Pointer to Int Function of Int */}

static jit_state_t *_jit;

void stack_push(int reg, int *sp)
@{
  jit_stxi_i (*sp, JIT_FP, reg);
  *sp += sizeof (int);
@}

void stack_pop(int reg, int *sp)
@{
  *sp -= sizeof (int);
  jit_ldxi_i (reg, JIT_FP, *sp);
@}

jit_node_t *compile_rpn(char *expr)
@{
  jit_node_t *in, *fn;
  int stack_base, stack_ptr;

  fn = jit_note(NULL, 0);
  jit_prolog();
  in = jit_arg();
  stack_ptr = stack_base = jit_allocai (32 * sizeof (int));

  jit_getarg_i(JIT_R2, in);

  while (*expr) @{
    char buf[32];
    int n;
    if (sscanf(expr, "%[0-9]%n", buf, &n)) @{
      expr += n - 1;
      stack_push(JIT_R0, &stack_ptr);
      jit_movi(JIT_R0, atoi(buf));
    @} else if (*expr == 'x') @{
      stack_push(JIT_R0, &stack_ptr);
      jit_movr(JIT_R0, JIT_R2);
    @} else if (*expr == '+') @{
      stack_pop(JIT_R1, &stack_ptr);
      jit_addr(JIT_R0, JIT_R1, JIT_R0);
    @} else if (*expr == '-') @{
      stack_pop(JIT_R1, &stack_ptr);
      jit_subr(JIT_R0, JIT_R1, JIT_R0);
    @} else if (*expr == '*') @{
      stack_pop(JIT_R1, &stack_ptr);
      jit_mulr(JIT_R0, JIT_R1, JIT_R0);
    @} else if (*expr == '/') @{
      stack_pop(JIT_R1, &stack_ptr);
      jit_divr(JIT_R0, JIT_R1, JIT_R0);
    @} else @{
      fprintf(stderr, "cannot compile: %s\n", expr);
      abort();
    @}
    ++expr;
  @}
  jit_retr(JIT_R0);
  jit_epilog();
  return fn;
@}
@end example

The principle on which the calculator is based is easy: the stack top
is held in R0, while the remaining items of the stack are held in the
memory area that we allocate with @code{allocai}.  Compiling a numeric
operand or the argument @code{x} pushes the old stack top onto the
stack and moves the operand into R0; compiling an operator pops the
second operand off the stack into R1, and compiles the operation so
that the result goes into R0, thus becoming the new stack top.

This example allocates a fixed area for 32 @code{int}s.  This is not
a problem when the function is a leaf like in this case; in a full-blown
compiler you will want to analyze the input and determine the number
of needed stack slots---a very simple example of register allocation.
The area is then managed like a stack using @code{stack_push} and
@code{stack_pop}.

Source code for the client (which lies in the same source file) follows:

@example
int main(int argc, char *argv[])
@{
  jit_node_t *nc, *nf;
  pifi c2f, f2c;
  int i;

  init_jit(argv[0]);
  _jit = jit_new_state();

  nc = compile_rpn("32x9*5/+");
  nf = compile_rpn("x32-5*9/");
  (void)jit_emit();
  c2f = (pifi)jit_address(nc);
  f2c = (pifi)jit_address(nf);
  jit_clear_state();

  printf("\nC:");
  for (i = 0; i <= 100; i += 10) printf("%3d ", i);
  printf("\nF:");
  for (i = 0; i <= 100; i += 10) printf("%3d ", c2f(i));
  printf("\n");

  printf("\nF:");
  for (i = 32; i <= 212; i += 18) printf("%3d ", i);
  printf("\nC:");
  for (i = 32; i <= 212; i += 18) printf("%3d ", f2c(i));
  printf("\n");

  jit_destroy_state();
  finish_jit();
  return 0;
@}
@end example

The client displays a conversion table between Celsius and Fahrenheit
degrees (both Celsius-to-Fahrenheit and Fahrenheit-to-Celsius). The
formulas are, @math{F(c) = c*9/5+32} and @math{C(f) = (f-32)*5/9},
respectively.

Providing the formula as an argument to @code{compile_rpn} effectively
parameterizes code generation, making it possible to use the same code
to compile different functions; this is what makes dynamic code
generation so powerful.

@node Fibonacci
@section Fibonacci numbers

The code in this section calculates the Fibonacci sequence. That is
modeled by the recurrence relation:
@display
     f(0) = 0
     f(1) = f(2) = 1
     f(n) = f(n-1) + f(n-2)
@end display

The purpose of this example is to introduce branches.  There are two
kind of branches: backward branches and forward branches.  We'll
present the calculation in a recursive and iterative form; the
former only uses forward branches, while the latter uses both.

@example
#include <stdio.h>
#include <lightning.h>

static jit_state_t *_jit;

typedef int (*pifi)(int);       @rem{/* Pointer to Int Function of Int */}

int main(int argc, char *argv[])
@{
  pifi       fib;
  jit_node_t *label;
  jit_node_t *call;
  jit_node_t *in;                 @rem{/* offset of the argument */}
  jit_node_t *ref;                @rem{/* to patch the forward reference */}
  jit_node_t *zero;               @rem{/* to patch the forward reference */}

  init_jit(argv[0]);
  _jit = jit_new_state();

  label = jit_label();
        jit_prolog   ();
  in =  jit_arg      ();
        jit_getarg   (JIT_V0, in);              @rem{/* R0 = n */}
 zero = jit_beqi     (JIT_R0, 0);
        jit_movr     (JIT_V0, JIT_R0);          /* V0 = R0 */
        jit_movi     (JIT_R0, 1);
  ref = jit_blei     (JIT_V0, 2);
        jit_subi     (JIT_V1, JIT_V0, 1);       @rem{/* V1 = n-1 */}
        jit_subi     (JIT_V2, JIT_V0, 2);       @rem{/* V2 = n-2 */}
        jit_prepare();
          jit_pushargr(JIT_V1);
        call = jit_finishi(NULL);
        jit_patch_at(call, label);
        jit_retval(JIT_V1);                     @rem{/* V1 = fib(n-1) */}
        jit_prepare();
          jit_pushargr(JIT_V2);
        call = jit_finishi(NULL);
        jit_patch_at(call, label);
        jit_retval(JIT_R0);                     @rem{/* R0 = fib(n-2) */}
        jit_addr(JIT_R0, JIT_R0, JIT_V1);       @rem{/* R0 = R0 + V1 */}

  jit_patch(ref);                               @rem{/* patch jump */}
  jit_patch(zero);                              @rem{/* patch jump */}
        jit_retr(JIT_R0);

  @rem{/* call the generated code@comma{} passing 32 as an argument */}
  fib = jit_emit();
  jit_clear_state();
  printf("fib(%d) = %d\n", 32, fib(32));
  jit_destroy_state();
  finish_jit();
  return 0;
@}
@end example

As said above, this is the first example of dynamically compiling
branches.  Branch instructions have two operands containing the
values to be compared, and return a @code{jit_note_t *} object
to be patched.

Because labels final address are only known after calling @code{emit},
it is required to call @code{patch} or @code{patch_at}, what does
tell @lightning{} that the target to patch is actually a pointer to
a @code{jit_node_t *} object, otherwise, it would assume that is
a pointer to a C function. Note that conditional branches do not
receive a label argument, so they must be patched.

You need to call @code{patch_at} on the return of value @code{calli},
@code{finishi}, and @code{calli} if it is actually referencing a label
in the jit code. All branch instructions do not receive a label
argument. Note that @code{movi} is an special case, and patching it
is usually done to get the final address of a label, usually to later
call @code{jmpr}.

Now, here is the iterative version:

@example
#include <stdio.h>
#include <lightning.h>

static jit_state_t *_jit;

typedef int (*pifi)(int);       @rem{/* Pointer to Int Function of Int */}

int main(int argc, char *argv[])
@{
  pifi       fib;
  jit_node_t *in;               @rem{/* offset of the argument */}
  jit_node_t *ref;              @rem{/* to patch the forward reference */}
  jit_node_t *zero;             @rem{/* to patch the forward reference */}
  jit_node_t *jump;             @rem{/* jump to start of loop */}
  jit_node_t *loop;             @rem{/* start of the loop */}

  init_jit(argv[0]);
  _jit = jit_new_state();

        jit_prolog   ();
  in =  jit_arg      ();
        jit_getarg   (JIT_R0, in);              @rem{/* R0 = n */}
 zero = jit_beqi     (JIT_R0, 0);
        jit_movr     (JIT_R1, JIT_R0);
        jit_movi     (JIT_R0, 1);
  ref = jit_blti     (JIT_R1, 2);
        jit_subi     (JIT_R2, JIT_R2, 2);
        jit_movr     (JIT_R1, JIT_R0);

  loop= jit_label();
        jit_subi     (JIT_R2, JIT_R2, 1);       @rem{/* decr. counter */}
        jit_movr     (JIT_V0, JIT_R0);          /* V0 = R0 */
        jit_addr     (JIT_R0, JIT_R0, JIT_R1);  /* R0 = R0 + R1 */
        jit_movr     (JIT_R1, JIT_V0);          /* R1 = V0 */
  jump= jit_bnei     (JIT_R2, 0);               /* if (R2) goto loop; */
  jit_patch_at(jump, loop);

  jit_patch(ref);                               @rem{/* patch forward jump */}
  jit_patch(zero);                              @rem{/* patch forward jump */}
        jit_retr     (JIT_R0);

  @rem{/* call the generated code@comma{} passing 36 as an argument */}
  fib = jit_emit();
  jit_clear_state();
  printf("fib(%d) = %d\n", 36, fib(36));
  jit_destroy_state();
  finish_jit();
  return 0;
@}
@end example

This code calculates the recurrence relation using iteration (a
@code{for} loop in high-level languages).  There are no function
calls anymore: instead, there is a backward jump (the @code{bnei} at
the end of the loop).

Note that the program must remember the address for backward jumps;
for forward jumps it is only required to remember the jump code,
and call @code{patch} for the implicit label.

@node Reentrancy
@chapter Re-entrant usage of @lightning{}

@lightning{} uses the special @code{_jit} identifier. To be able
to be able to use multiple jit generation states at the same
time, it is required to used code similar to:

@example
    struct jit_state lightning;
    #define lightning _jit
@end example

This will cause the symbol defined to @code{_jit} to be passed as
the first argument to the underlying @lightning{} implementation,
that is usually a function with an @code{_} (underscode) prefix
and with an argument named @code{_jit}, in the pattern:

@example
    static void _jit_mnemonic(jit_state_t *, jit_gpr_t, jit_gpr_t);
    #define jit_mnemonic(u, v) _jit_mnemonic(_jit, u, v);
@end example

The reason for this is to use the same syntax as the initial lightning
implementation and to avoid needing the user to keep adding an extra
argument to every call, as multiple jit states generating code in
paralell should be very uncommon.

@node Registers
@chapter Accessing the whole register file

As mentioned earlier in this chapter, all @lightning{} back-ends are
guaranteed to have at least six general-purpose integer registers and
six floating-point registers, but many back-ends will have more.

To access the entire register files, you can use the
@code{JIT_R}, @code{JIT_V} and @code{JIT_F} macros.  They
accept a parameter that identifies the register number, which
must be strictly less than @code{JIT_R_NUM}, @code{JIT_V_NUM}
and @code{JIT_F_NUM} respectively; the number need not be
constant.  Of course, expressions like @code{JIT_R0} and
@code{JIT_R(0)} denote the same register, and likewise for
integer callee-saved, or floating-point, registers.

@section Scratch registers

For operations, @lightning{} does not support directly, like storing
a literal in memory, @code{jit_get_reg} and @code{jit_unget_reg} can be used to
acquire and release a scratch register as in the following pattern:

@example
    jit_int32_t reg = jit_get_reg (jit_class_gpr);
    jit_movi (reg, immediate);
    jit_stxi (offsetof (some_struct, some_field), JIT_V0, reg);
    jit_unget_reg (reg);
@end example

As @code{jit_get_reg} and @code{jit_unget_reg} may generate spills and
reloads but don't follow branches, the code between both must be in
the same basic block and must not contain any branches as in the
following (bad) example.

@example
    jit_int32_t reg = jit_get_reg (jit_class_gpr);
    jit_ldxi (reg, JIT_V0, offset);
    jump = jit_bnei (reg, V0);
    jit_movr (JIT_V1, reg);
    jit_patch (jump);
    jit_unget_reg (reg);
@end example

@node Customizations
@chapter Customizations

Frequently it is desirable to have more control over how code is
generated or how memory is used during jit generation or execution.

@section Memory functions
To aid in complete control of memory allocation and deallocation
@lightning{} provides wrappers that default to standard @code{malloc},
@code{realloc} and @code{free}. These are loosely based on the
GNU GMP counterparts, with the difference that they use the same
prototype of the system allocation functions, that is, no @code{size}
for @code{free} or @code{old_size} for @code{realloc}.

@deftypefun void jit_set_memory_functions (@* void *(*@var{alloc_func_ptr}) (size_t), @* void *(*@var{realloc_func_ptr}) (void *, size_t), @* void (*@var{free_func_ptr}) (void *))
@lightning{} guarantees that memory is only allocated or released
using these wrapped functions, but you must note that if lightning
was linked to GNU binutils, malloc is probably will be called multiple
times from there when initializing the disassembler.

Because @code{init_jit} may call memory functions, if you need to call
@code{jit_set_memory_functions}, it must be called before @code{init_jit},
otherwise, when calling @code{finish_jit}, a pointer allocated with the
previous or default wrappers will be passed.
@end deftypefun

@deftypefun void jit_get_memory_functions (@* void *(**@var{alloc_func_ptr}) (size_t), @* void *(**@var{realloc_func_ptr}) (void *, size_t), @* void (**@var{free_func_ptr}) (void *))
Get the current memory allocation function. Also, unlike the GNU GMP
counterpart, it is an error to pass @code{NULL} pointers as arguments.
@end deftypefun

@section Alternate code buffer
To instruct @lightning{} to use an alternate code buffer it is required
to call @code{jit_realize} before @code{jit_emit}, and then query states
and customize as appropriate.

@deftypefun void jit_realize ()
Must be called once, before @code{jit_emit}, to instruct @lightning{}
that no other @code{jit_xyz} call will be made.
@end deftypefun

@deftypefun jit_pointer_t jit_get_code (jit_word_t *@var{code_size})
Returns NULL or the previous value set with @code{jit_set_code}, and
sets the @var{code_size} argument to an appropriate value.
If @code{jit_get_code} is called before @code{jit_emit}, the
@var{code_size} argument is set to the expected amount of bytes
required to generate code.
If @code{jit_get_code} is called after @code{jit_emit}, the
@var{code_size} argument is set to the exact amount of bytes used
by the code.
@end deftypefun

@deftypefun void jit_set_code (jit_ponter_t @var{code}, jit_word_t @var{size})
Instructs @lightning{} to output to the @var{code} argument and
use @var{size} as a guard to not write to invalid memory. If during
@code{jit_emit} @lightning{} finds out that the code would not fit
in @var{size} bytes, it halts code emit and returns @code{NULL}.
@end deftypefun

A simple example of a loop using an alternate buffer is:

@example
  jit_uint8_t   *code;
  int           *(func)(int);      @rem{/* function pointer */}
  jit_word_t     code_size;
  jit_word_t     real_code_size;
  @rem{...}
  jit_realize();                   @rem{/* ready to generate code */}
  jit_get_code(&code_size);        @rem{/* get expected code size */}
  code_size = (code_size + 4095) & -4096;
  do (;;) @{
    code = mmap(NULL, code_size, PROT_EXEC | PROT_READ | PROT_WRITE,
                MAP_PRIVATE | MAP_ANON, -1, 0);
    jit_set_code(code, code_size);
    if ((func = jit_emit()) == NULL) @{
      munmap(code, code_size);
      code_size += 4096;
    @}
  @} while (func == NULL);
  jit_get_code(&real_code_size);   @rem{/* query exact size of the code */}
@end example

The first call to @code{jit_get_code} should return @code{NULL} and set
the @code{code_size} argument to the expected amount of bytes required
to emit code.
The second call to @code{jit_get_code} is after a successful call to
@code{jit_emit}, and will return the value previously set with
@code{jit_set_code} and set the @code{real_code_size} argument to the
exact amount of bytes used to emit the code.

@section Alternate data buffer
Sometimes it may be desirable to customize how, or to prevent
@lightning{} from using an extra buffer for constants or debug
annotation. Usually when also using an alternate code buffer.

@deftypefun jit_pointer_t jit_get_data (jit_word_t *@var{data_size}, jit_word_t *@var{note_size})
Returns @code{NULL} or the previous value set with @code{jit_set_data},
and sets the @var{data_size} argument to how many bytes are required
for the constants data buffer, and @var{note_size} to how many bytes
are required to store the debug note information.
Note that it always preallocate one debug note entry even if
@code{jit_name} or @code{jit_note} are never called, but will return
zero in the @var{data_size} argument if no constant is required;
constants are only used for the @code{float} and @code{double} operations
that have an immediate argument, and not in all @lightning{} ports.
@end deftypefun

@deftypefun void jit_set_data (jit_pointer_t @var{data}, jit_word_t @var{size}, jit_word_t @var{flags})

@var{data} can be NULL if disabling constants and annotations, otherwise,
a valid pointer must be passed. An assertion is done that the data will
fit in @var{size} bytes (but that is a noop if @lightning{} was built
with @code{-DNDEBUG}).

@var{size} tells the space in bytes available in @var{data}.

@var{flags} can be zero to tell to just use the alternate data buffer,
or a composition of @code{JIT_DISABLE_DATA} and @code{JIT_DISABLE_NOTE}

@table @t
@item JIT_DISABLE_DATA
@cindex JIT_DISABLE_DATA
Instructs @lightning{} to not use a constant table, but to use an
alternate method to synthesize those, usually with a larger code
sequence using stack space to transfer the value from a GPR to a
FPR register.

@item JIT_DISABLE_NOTE
@cindex JIT_DISABLE_NOTE
Instructs @lightning{} to not store file or function name, and
line numbers in the constant buffer.
@end table
@end deftypefun

A simple example of a preventing usage of a data buffer is:

@example
  @rem{...}
  jit_realize();                        @rem{/* ready to generate code */}
  jit_get_data(NULL, NULL);
  jit_set_data(NULL, 0, JIT_DISABLE_DATA | JIT_DISABLE_NOTE);
  @rem{...}
@end example

Or to only use a data buffer, if required:

@example
  jit_uint8_t   *data;
  jit_word_t     data_size;
  @rem{...}
  jit_realize();                        @rem{/* ready to generate code */}
  jit_get_data(&data_size, NULL);
  if (data_size)
    data = malloc(data_size);
  else
    data = NULL;
  jit_set_data(data, data_size, JIT_DISABLE_NOTE);
  @rem{...}
  if (data)
    free(data);
  @rem{...}
@end example

@node Acknowledgements
@chapter Acknowledgements

As far as I know, the first general-purpose portable dynamic code
generator is @sc{dcg}, by Dawson R.@: Engler and T.@: A.@: Proebsting.
Further work by Dawson R. Engler resulted in the @sc{vcode} system;
unlike @sc{dcg}, @sc{vcode} used no intermediate representation and
directly inspired @lightning{}.

Thanks go to Ian Piumarta, who kindly accepted to release his own
program @sc{ccg} under the GNU General Public License, thereby allowing
@lightning{} to use the run-time assemblers he had wrote for @sc{ccg}.
@sc{ccg} provides a way of dynamically assemble programs written in the
underlying architecture's assembly language.  So it is not portable,
yet very interesting.

I also thank Steve Byrne for writing GNU Smalltalk, since @lightning{}
was first developed as a tool to be used in GNU Smalltalk's dynamic
translator from bytecodes to native code.