2 @dircategory Software development
4 * lightning: (lightning). Library for dynamic code generation.
24 This document describes @value{TOPIC} the @lightning{} library for
25 dynamic code generation.
28 * Overview:: What GNU lightning is
29 * Installation:: Configuring and installing GNU lightning
30 * The instruction set:: The RISC instruction set used in GNU lightning
31 * GNU lightning examples:: GNU lightning's examples
32 * Reentrancy:: Re-entrant usage of GNU lightning
33 * Registers:: Accessing the whole register file
34 * Customizations:: Advanced code generation customizations
35 * Acknowledgements:: Acknowledgements for GNU lightning
40 @chapter Introduction to @lightning{}
43 This document describes @value{TOPIC} the @lightning{} library for
44 dynamic code generation.
47 Dynamic code generation is the generation of machine code
48 at runtime. It is typically used to strip a layer of interpretation
49 by allowing compilation to occur at runtime. One of the most
50 well-known applications of dynamic code generation is perhaps that
51 of interpreters that compile source code to an intermediate bytecode
52 form, which is then recompiled to machine code at run-time: this
53 approach effectively combines the portability of bytecode
54 representations with the speed of machine code. Another common
55 application of dynamic code generation is in the field of hardware
56 simulators and binary emulators, which can use the same techniques
57 to translate simulated instructions to the instructions of the
60 Yet other applications come to mind: for example, windowing
61 @dfn{bitblt} operations, matrix manipulations, and network packet
62 filters. Albeit very powerful and relatively well known within the
63 compiler community, dynamic code generation techniques are rarely
64 exploited to their full potential and, with the exception of the
65 two applications described above, have remained curiosities because
66 of their portability and functionality barriers: binary instructions
67 are generated, so programs using dynamic code generation must be
68 retargeted for each machine; in addition, coding a run-time code
69 generator is a tedious and error-prone task more than a difficult one.
71 @lightning{} provides a portable, fast and easily retargetable dynamic
72 code generation system.
74 To be portable, @lightning{} abstracts over current architectures'
75 quirks and unorthogonalities. The interface that it exposes to is that
76 of a standardized RISC architecture loosely based on the SPARC and MIPS
77 chips. There are a few general-purpose registers (six, not including
78 those used to receive and pass parameters between subroutines), and
79 arithmetic operations involve three operands---either three registers
80 or two registers and an arbitrarily sized immediate value.
82 On one hand, this architecture is general enough that it is possible to
83 generate pretty efficient code even on CISC architectures such as the
84 Intel x86 or the Motorola 68k families. On the other hand, it matches
85 real architectures closely enough that, most of the time, the
86 compiler's constant folding pass ends up generating code which
87 assembles machine instructions without further tests.
90 @chapter Configuring and installing @lightning{}
92 Here we will assume that your system already has the dependencies
93 necessary to build @lightning{}. For more on dependencies, see
94 @lightning{}'s @file{README-hacking} file.
96 The first thing to do to build @lightning{} is to configure the
97 program, picking the set of macros to be used on the host
98 architecture; this configuration is automatically performed by
99 the @file{configure} shell script; to run it, merely type:
104 @lightning{} supports the @code{--enable-disassembler} option, that
105 enables linking to GNU binutils and optionally print human readable
106 disassembly of the jit code. This option can be disabled by the
107 @code{--disable-disassembler} option.
109 Another option that @file{configure} accepts is
110 @code{--enable-assertions}, which enables several consistency checks in
111 the run-time assemblers. These are not usually needed, so you can
112 decide to simply forget about it; also remember that these consistency
113 checks tend to slow down your code generator.
115 After you've configured @lightning{}, run @file{make} as usual.
117 @lightning{} has an extensive set of tests to validate it is working
118 correctly in the build host. To test it run:
123 The next important step is:
128 This ends the process of installing @lightning{}.
130 @node The instruction set
131 @chapter @lightning{}'s instruction set
133 @lightning{}'s instruction set was designed by deriving instructions
134 that closely match those of most existing RISC architectures, or
135 that can be easily syntesized if absent. Each instruction is composed
139 an operation, like @code{sub} or @code{mul}
142 most times, a register/immediate flag (@code{r} or @code{i})
145 an unsigned modifier (@code{u}), a type identifier or two, when applicable.
148 Examples of legal mnemonics are @code{addr} (integer add, with three
149 register operands) and @code{muli} (integer multiply, with two
150 register operands and an immediate operand). Each instruction takes
151 two or three operands; in most cases, one of them can be an immediate
152 value instead of a register.
154 Most @lightning{} integer operations are signed wordsize operations,
155 with the exception of operations that convert types, or load or store
156 values to/from memory. When applicable, the types and C types are as
161 _uc @r{unsigned char}
163 _us @r{unsigned short}
171 Most integer operations do not need a type modifier, and when loading or
172 storing values to memory there is an alias to the proper operation
173 using wordsize operands, that is, if ommited, the type is @r{int} on
174 32-bit architectures and @r{long} on 64-bit architectures. Note
175 that lightning also expects @code{sizeof(void*)} to match the wordsize.
177 When an unsigned operation result differs from the equivalent signed
178 operation, there is a the @code{_u} modifier.
180 There are at least seven integer registers, of which six are
181 general-purpose, while the last is used to contain the frame pointer
182 (@code{FP}). The frame pointer can be used to allocate and access local
183 variables on the stack, using the @code{allocai} or @code{allocar}
186 Of the general-purpose registers, at least three are guaranteed to be
187 preserved across function calls (@code{V0}, @code{V1} and
188 @code{V2}) and at least three are not (@code{R0}, @code{R1} and
189 @code{R2}). Six registers are not very much, but this
190 restriction was forced by the need to target CISC architectures
191 which, like the x86, are poor of registers; anyway, backends can
192 specify the actual number of available registers with the calls
193 @code{JIT_R_NUM} (for caller-save registers) and @code{JIT_V_NUM}
194 (for callee-save registers).
196 There are at least six floating-point registers, named @code{F0} to
197 @code{F5}. These are usually caller-save and are separate from the integer
198 registers on the supported architectures; on Intel architectures,
199 in 32 bit mode if SSE2 is not available or use of X87 is forced,
200 the register stack is mapped to a flat register file. As for the
201 integer registers, the macro @code{JIT_F_NUM} yields the number of
202 floating-point registers.
204 The complete instruction set follows; as you can see, most non-memory
205 operations only take integers (either signed or unsigned) as operands;
206 this was done in order to reduce the instruction set, and because most
207 architectures only provide word and long word operations on registers.
208 There are instructions that allow operands to be extended to fit a larger
209 data type, both in a signed and in an unsigned way.
212 @item Binary ALU operations
213 These accept three operands; the last one can be an immediate.
214 @code{addx} operations must directly follow @code{addc}, and
215 @code{subx} must follow @code{subc}; otherwise, results are undefined.
216 Most, if not all, architectures do not support @r{float} or @r{double}
217 immediate operands; lightning emulates those operations by moving the
218 immediate to a temporary register and emiting the call with only
221 addr _f _d O1 = O2 + O3
222 addi _f _d O1 = O2 + O3
223 addxr O1 = O2 + (O3 + carry)
224 addxi O1 = O2 + (O3 + carry)
225 addcr O1 = O2 + O3, set carry
226 addci O1 = O2 + O3, set carry
227 subr _f _d O1 = O2 - O3
228 subi _f _d O1 = O2 - O3
229 subxr O1 = O2 - (O3 + carry)
230 subxi O1 = O2 - (O3 + carry)
231 subcr O1 = O2 - O3, set carry
232 subci O1 = O2 - O3, set carry
233 rsbr _f _d O1 = O3 - O1
234 rsbi _f _d O1 = O3 - O1
235 mulr _f _d O1 = O2 * O3
236 muli _f _d O1 = O2 * O3
237 divr _u _f _d O1 = O2 / O3
238 divi _u _f _d O1 = O2 / O3
249 rshr _u O1 = O2 >> O3@footnote{The sign bit is propagated unless using the @code{_u} modifier.}
250 rshi _u O1 = O2 >> O3@footnote{The sign bit is propagated unless using the @code{_u} modifier.}
251 movzr O1 = O3 ? O1 : O2
252 movnr O1 = O3 ? O2 : O1
255 @item Four operand binary ALU operations
256 These accept two result registers, and two operands; the last one can
257 be an immediate. The first two arguments cannot be the same register.
259 @code{qmul} stores the low word of the result in @code{O1} and the
260 high word in @code{O2}. For unsigned multiplication, @code{O2} zero
261 means there was no overflow. For signed multiplication, no overflow
262 check is based on sign, and can be detected if @code{O2} is zero or
265 @code{qdiv} stores the quotient in @code{O1} and the remainder in
266 @code{O2}. It can be used as quick way to check if a division is
267 exact, in which case the remainder is zero.
270 qmulr _u O1 O2 = O3 * O4
271 qmuli _u O1 O2 = O3 * O4
272 qdivr _u O1 O2 = O3 / O4
273 qdivi _u O1 O2 = O3 / O4
276 @item Unary ALU operations
277 These accept two operands, both of which must be registers.
283 These unary ALU operations are only defined for float operands.
285 absr _f _d O1 = fabs(O2)
289 Besides requiring the @code{r} modifier, there are no unary operations
290 with an immediate operand.
292 @item Compare instructions
293 These accept three operands; again, the last can be an immediate.
294 The last two operands are compared, and the first operand, that must be
295 an integer register, is set to either 0 or 1, according to whether the
296 given condition was met or not.
298 The conditions given below are for the standard behavior of C,
299 where the ``unordered'' comparison result is mapped to false.
302 ltr _u _f _d O1 = (O2 < O3)
303 lti _u _f _d O1 = (O2 < O3)
304 ler _u _f _d O1 = (O2 <= O3)
305 lei _u _f _d O1 = (O2 <= O3)
306 gtr _u _f _d O1 = (O2 > O3)
307 gti _u _f _d O1 = (O2 > O3)
308 ger _u _f _d O1 = (O2 >= O3)
309 gei _u _f _d O1 = (O2 >= O3)
310 eqr _f _d O1 = (O2 == O3)
311 eqi _f _d O1 = (O2 == O3)
312 ner _f _d O1 = (O2 != O3)
313 nei _f _d O1 = (O2 != O3)
314 unltr _f _d O1 = !(O2 >= O3)
315 unler _f _d O1 = !(O2 > O3)
316 ungtr _f _d O1 = !(O2 <= O3)
317 unger _f _d O1 = !(O2 < O3)
318 uneqr _f _d O1 = !(O2 < O3) && !(O2 > O3)
319 ltgtr _f _d O1 = !(O2 >= O3) || !(O2 <= O3)
320 ordr _f _d O1 = (O2 == O2) && (O3 == O3)
321 unordr _f _d O1 = (O2 != O2) || (O3 != O3)
324 @item Transfer operations
325 These accept two operands; for @code{ext} both of them must be
326 registers, while @code{mov} accepts an immediate value as the second
329 Unlike @code{movr} and @code{movi}, the other instructions are used
330 to truncate a wordsize operand to a smaller integer data type or to
331 convert float data types. You can also use @code{extr} to convert an
332 integer to a floating point value: the usual options are @code{extr_f}
338 extr _c _uc _s _us _i _ui _f _d O1 = O2
339 truncr _f _d O1 = trunc(O2)
342 In 64-bit architectures it may be required to use @code{truncr_f_i},
343 @code{truncr_f_l}, @code{truncr_d_i} and @code{truncr_d_l} to match
344 the equivalent C code. Only the @code{_i} modifier is available in
345 32-bit architectures.
348 truncr_f_i = <int> O1 = <float> O2
349 truncr_f_l = <long>O1 = <float> O2
350 truncr_d_i = <int> O1 = <double>O2
351 truncr_d_l = <long>O1 = <double>O2
354 The float conversion operations are @emph{destination first,
355 source second}, but the order of the types is reversed. This happens
356 for historical reasons.
359 extr_f_d = <double>O1 = <float> O2
360 extr_d_f = <float> O1 = <double>O2
363 @item Network extensions
364 These accept two operands, both of which must be registers; these
365 two instructions actually perform the same task, yet they are
366 assigned to two mnemonics for the sake of convenience and
367 completeness. As usual, the first operand is the destination and
368 the second is the source.
369 The @code{_ul} variant is only available in 64-bit architectures.
371 htonr _us _ui _ul @r{Host-to-network (big endian) order}
372 ntohr _us _ui _ul @r{Network-to-host order }
375 @code{bswapr} can be used to unconditionally byte-swap an operand.
376 On little-endian architectures, @code{htonr} and @code{ntohr} resolve
378 The @code{_ul} variant is only available in 64-bit architectures.
380 bswapr _us _ui _ul 01 = byte_swap(02)
383 @item Load operations
384 @code{ld} accepts two operands while @code{ldx} accepts three;
385 in both cases, the last can be either a register or an immediate
386 value. Values are extended (with or without sign, according to
387 the data type specification) to fit a whole register.
388 The @code{_ui} and @code{_l} types are only available in 64-bit
389 architectures. For convenience, there is a version without a
390 type modifier for integer or pointer operands that uses the
391 appropriate wordsize call.
393 ldr _c _uc _s _us _i _ui _l _f _d O1 = *O2
394 ldi _c _uc _s _us _i _ui _l _f _d O1 = *O2
395 ldxr _c _uc _s _us _i _ui _l _f _d O1 = *(O2+O3)
396 ldxi _c _uc _s _us _i _ui _l _f _d O1 = *(O2+O3)
399 @item Store operations
400 @code{st} accepts two operands while @code{stx} accepts three; in
401 both cases, the first can be either a register or an immediate
402 value. Values are sign-extended to fit a whole register.
404 str _c _uc _s _us _i _ui _l _f _d *O1 = O2
405 sti _c _uc _s _us _i _ui _l _f _d *O1 = O2
406 stxr _c _uc _s _us _i _ui _l _f _d *(O1+O2) = O3
407 stxi _c _uc _s _us _i _ui _l _f _d *(O1+O2) = O3
409 As for the load operations, the @code{_ui} and @code{_l} types are
410 only available in 64-bit architectures, and for convenience, there
411 is a version without a type modifier for integer or pointer operands
412 that uses the appropriate wordsize call.
414 @item Argument management
417 prepare (not specified)
418 va_start (not specified)
421 va_push (not specified)
423 getarg _c _uc _s _us _i _ui _l _f _d
430 va_end (not specified)
431 retval _c _uc _s _us _i _ui _l _f _d
432 epilog (not specified)
434 As with other operations that use a type modifier, the @code{_ui} and
435 @code{_l} types are only available in 64-bit architectures, but there
436 are operations without a type modifier that alias to the appropriate
437 integer operation with wordsize operands.
439 @code{prepare}, @code{pusharg}, and @code{retval} are used by the caller,
440 while @code{arg}, @code{getarg} and @code{ret} are used by the callee.
441 A code snippet that wants to call another procedure and has to pass
442 arguments must, in order: use the @code{prepare} instruction and use
443 the @code{pushargr} or @code{pushargi} to push the arguments @strong{in
444 left to right order}; and use @code{finish} or @code{call} (explained below)
445 to perform the actual call.
447 @code{va_start} returns a @code{C} compatible @code{va_list}. To fetch
448 arguments, use @code{va_arg} for integers and @code{va_arg_d} for doubles.
449 @code{va_push} is required when passing a @code{va_list} to another function,
450 because not all architectures expect it as a single pointer. Known case
451 is DEC Alpha, that requires it as a structure passed by value.
453 @code{arg}, @code{getarg} and @code{putarg} are used by the callee.
454 @code{arg} is different from other instruction in that it does not
455 actually generate any code: instead, it is a function which returns
456 a value to be passed to @code{getarg} or @code{putarg}. @footnote{``Return
457 a value'' means that @lightning{} code that compile these
458 instructions return a value when expanded.} You should call
459 @code{arg} as soon as possible, before any function call or, more
460 easily, right after the @code{prolog} instructions
461 (which is treated later).
463 @code{getarg} accepts a register argument and a value returned by
464 @code{arg}, and will move that argument to the register, extending
465 it (with or without sign, according to the data type specification)
466 to fit a whole register. These instructions are more intimately
467 related to the usage of the @lightning{} instruction set in code
468 that generates other code, so they will be treated more
469 specifically in @ref{GNU lightning examples, , Generating code at
472 @code{putarg} is a mix of @code{getarg} and @code{pusharg} in that
473 it accepts as first argument a register or immediate, and as
474 second argument a value returned by @code{arg}. It allows changing,
475 or restoring an argument to the current function, and is a
476 construct required to implement tail call optimization. Note that
477 arguments in registers are very cheap, but will be overwritten
478 at any moment, including on some operations, for example division,
479 that on several ports is implemented as a function call.
481 Finally, the @code{retval} instruction fetches the return value of a
482 called function in a register. The @code{retval} instruction takes a
483 register argument and copies the return value of the previously called
484 function in that register. A function with a return value should use
485 @code{retr} or @code{reti} to put the return value in the return register
486 before returning. @xref{Fibonacci, the Fibonacci numbers}, for an example.
488 @code{epilog} is an optional call, that marks the end of a function
489 body. It is automatically generated by @lightning{} if starting a new
490 function (what should be done after a @code{ret} call) or finishing
492 It is very important to note that the fact that @code{epilog} being
493 optional may cause a common mistake. Consider this:
502 Because @code{epilog} is added when finding a new @code{prolog},
503 this will cause the @code{fun2} label to actually be before the
504 return from @code{fun1}. Because @lightning{} will actually
516 You should observe a few rules when using these macros. First of
517 all, if calling a varargs function, you should use the @code{ellipsis}
518 call to mark the position of the ellipsis in the C prototype.
520 You should not nest calls to @code{prepare} inside a
521 @code{prepare/finish} block. Doing this will result in undefined
522 behavior. Note that for functions with zero arguments you can use
525 @item Branch instructions
526 Like @code{arg}, these also return a value which, in this case,
527 is to be used to compile forward branches as explained in
528 @ref{Fibonacci, , Fibonacci numbers}. They accept two operands to be
529 compared; of these, the last can be either a register or an immediate.
532 bltr _u _f _d @r{if }(O2 < O3)@r{ goto }O1
533 blti _u _f _d @r{if }(O2 < O3)@r{ goto }O1
534 bler _u _f _d @r{if }(O2 <= O3)@r{ goto }O1
535 blei _u _f _d @r{if }(O2 <= O3)@r{ goto }O1
536 bgtr _u _f _d @r{if }(O2 > O3)@r{ goto }O1
537 bgti _u _f _d @r{if }(O2 > O3)@r{ goto }O1
538 bger _u _f _d @r{if }(O2 >= O3)@r{ goto }O1
539 bgei _u _f _d @r{if }(O2 >= O3)@r{ goto }O1
540 beqr _f _d @r{if }(O2 == O3)@r{ goto }O1
541 beqi _f _d @r{if }(O2 == O3)@r{ goto }O1
542 bner _f _d @r{if }(O2 != O3)@r{ goto }O1
543 bnei _f _d @r{if }(O2 != O3)@r{ goto }O1
545 bunltr _f _d @r{if }!(O2 >= O3)@r{ goto }O1
546 bunler _f _d @r{if }!(O2 > O3)@r{ goto }O1
547 bungtr _f _d @r{if }!(O2 <= O3)@r{ goto }O1
548 bunger _f _d @r{if }!(O2 < O3)@r{ goto }O1
549 buneqr _f _d @r{if }!(O2 < O3) && !(O2 > O3)@r{ goto }O1
550 bltgtr _f _d @r{if }!(O2 >= O3) || !(O2 <= O3)@r{ goto }O1
551 bordr _f _d @r{if } (O2 == O2) && (O3 == O3)@r{ goto }O1
552 bunordr _f _d @r{if }!(O2 != O2) || (O3 != O3)@r{ goto }O1
554 bmsr @r{if }O2 & O3@r{ goto }O1
555 bmsi @r{if }O2 & O3@r{ goto }O1
556 bmcr @r{if }!(O2 & O3)@r{ goto }O1
557 bmci @r{if }!(O2 & O3)@r{ goto }O1@footnote{These mnemonics mean, respectively, @dfn{branch if mask set} and @dfn{branch if mask cleared}.}
558 boaddr _u O2 += O3@r{, goto }O1@r{ if overflow}
559 boaddi _u O2 += O3@r{, goto }O1@r{ if overflow}
560 bxaddr _u O2 += O3@r{, goto }O1@r{ if no overflow}
561 bxaddi _u O2 += O3@r{, goto }O1@r{ if no overflow}
562 bosubr _u O2 -= O3@r{, goto }O1@r{ if overflow}
563 bosubi _u O2 -= O3@r{, goto }O1@r{ if overflow}
564 bxsubr _u O2 -= O3@r{, goto }O1@r{ if no overflow}
565 bxsubi _u O2 -= O3@r{, goto }O1@r{ if no overflow}
568 @item Jump and return operations
569 These accept one argument except @code{ret} and @code{jmpi} which
570 have none; the difference between @code{finishi} and @code{calli}
571 is that the latter does not clean the stack from pushed parameters
572 (if any) and the former must @strong{always} follow a @code{prepare}
575 callr (not specified) @r{function call to register O1}
576 calli (not specified) @r{function call to immediate O1}
577 finishr (not specified) @r{function call to register O1}
578 finishi (not specified) @r{function call to immediate O1}
579 jmpr (not specified) @r{unconditional jump to register}
580 jmpi (not specified) @r{unconditional jump}
581 ret (not specified) @r{return from subroutine}
582 retr _c _uc _s _us _i _ui _l _f _d
583 reti _c _uc _s _us _i _ui _l _f _d
584 retval _c _uc _s _us _i _ui _l _f _d @r{move return value}
588 Like branch instruction, @code{jmpi} also returns a value which is to
589 be used to compile forward branches. @xref{Fibonacci, , Fibonacci
593 There are 3 @lightning{} instructions to create labels:
595 label (not specified) @r{simple label}
596 forward (not specified) @r{forward label}
597 indirect (not specified) @r{special simple label}
600 The following instruction is used to specify a minimal alignment for
601 the next instruction, usually with a label:
603 align (not specified) @r{align code}
606 @code{label} is normally used as @code{patch_at} argument for backward
610 jit_node_t *jump, *label;
613 jump = jit_beqr(JIT_R0, JIT_R1);
614 jit_patch_at(jump, label);
617 @code{forward} is used to patch code generation before the actual
618 position of the label is known.
621 jit_node_t *jump, *label;
622 label = jit_forward();
623 jump = jit_beqr(JIT_R0, JIT_R1);
624 jit_patch_at(jump, label);
629 @code{indirect} is useful when creating jump tables, and tells
630 @lightning{} to not optimize out a label that is not the target of
631 any jump, because an indirect jump may land where it is defined.
634 jit_node_t *jump, *label;
636 jmpr(JIT_R0); @rem{/* may jump to label */}
638 label = jit_indirect();
641 @code{indirect} is an special case of @code{note} and @code{name}
642 because it is a valid argument to @code{address}.
644 Note that the usual idiom to write the previous example is
646 jit_node_t *addr, *jump;
647 addr = jit_movi(JIT_R0, 0); @rem{/* immediate is ignored */}
651 jit_patch(addr); @rem{/* implicit label added */}
654 that automatically binds the implicit label added by @code{patch} with
655 the @code{movi}, but on some special conditions it is required to create
658 @code{align} is useful for creating multiple entry points to a
659 (trampoline) function that are all accessible through a single
660 function pointer. @code{align} receives an integer argument that
661 defines the minimal alignment of the address of a label directly
662 following the @code{align} instruction. The integer argument must be
663 a power of two and the effective alignment will be a power of two no
664 less than the argument to @code{align}. If the argument to
665 @code{align} is 16 or more, the effective alignment will match the
666 specified minimal alignment exactly.
669 jit_node_t *forward, *label1, *label2, *jump;
670 unsigned char *addr1, *addr2;
671 forward = jit_forward();
673 label1 = jit_indirect(); @rem{/* first entry point */}
674 jump = jit_jmpi(); @rem{/* jump to first handler */}
675 jit_patch_at(jump, forward);
677 label2 = jit_indirect(); @rem{/* second entry point */}
678 ... @rem{/* second handler */}
681 ... @rem{/* first handler /*}
685 addr1 = jit_address(label1);
686 addr2 = jit_address(label2);
687 assert(addr2 - addr1 == 16); @rem{/* only one of the addresses needs to be remembered */}
690 @item Function prolog
692 These macros are used to set up a function prolog. The @code{allocai}
693 call accept a single integer argument and returns an offset value
694 for stack storage access. The @code{allocar} accepts two registers
695 arguments, the first is set to the offset for stack access, and the
696 second is the size in bytes argument.
699 prolog (not specified) @r{function prolog}
700 allocai (not specified) @r{reserve space on the stack}
701 allocar (not specified) @r{allocate space on the stack}
704 @code{allocai} receives the number of bytes to allocate and returns
705 the offset from the frame pointer register @code{FP} to the base of
708 @code{allocar} receives two register arguments. The first is where
709 to store the offset from the frame pointer register @code{FP} to the
710 base of the area. The second argument is the size in bytes. Note
711 that @code{allocar} is dynamic allocation, and special attention
712 should be taken when using it. If called in a loop, every iteration
713 will allocate stack space. Stack space is aligned from 8 to 64 bytes
714 depending on backend requirements, even if allocating only one byte.
715 It is advisable to not use it with @code{frame} and @code{tramp}; it
716 should work with @code{frame} with special care to call only once,
717 but is not supported if used in @code{tramp}, even if called only
720 As a small appetizer, here is a small function that adds 1 to the input
721 parameter (an @code{int}). I'm using an assembly-like syntax here which
722 is a bit different from the one used when writing real subroutines with
723 @lightning{}; the real syntax will be introduced in @xref{GNU lightning
724 examples, , Generating code at run-time}.
729 in = arg @rem{! We have an integer argument}
730 getarg R0, in @rem{! Move it to R0}
731 addi R0, R0, 1 @rem{! Add 1}
732 retr R0 @rem{! And return the result}
735 And here is another function which uses the @code{printf} function from
736 the standard C library to write a number in hexadecimal notation:
741 in = arg @rem{! Same as above}
743 prepare @rem{! Begin call sequence for printf}
744 pushargi "%x" @rem{! Push format string}
745 ellipsis @rem{! Varargs start here}
746 pushargr R0 @rem{! Push second argument}
747 finishi printf @rem{! Call printf}
748 ret @rem{! Return to caller}
751 @item Register liveness
753 During code generation, @lightning{} occasionally needs scratch registers
754 or needs to use architecture-defined registers. For that, @lightning{}
755 internally maintains register liveness information.
757 In the following example, @code{qdivr} will need special registers like
758 @code{R0} on some architectures. As @lightning{} understands that
759 @code{R0} is used in the subsequent instruction, it will create
760 save/restore code for @code{R0} in case.
769 The same is not true in the example that follows. Here, @code{R0} is
770 not alive after the division operation because @code{R0} is neither an
771 argument register nor a callee-save register. Thus, no save/restore
772 code for @code{R0} will be created in case.
781 The @code{live} instruction can be used to mark a register as live after
782 it as in the following example. Here, @code{R0} will be preserved
793 The @code{live} instruction is useful at code entry and exit points,
794 like after and before a @code{callr} instruction.
796 @item Trampolines, continuations and tail call optimization
798 Frequently it is required to generate jit code that must jump to
799 code generated later, possibly from another @code{jit_context_t}.
800 These require compatible stack frames.
802 @lightning{} provides two primitives from where trampolines,
803 continuations and tail call optimization can be implemented.
806 frame (not specified) @r{create stack frame}
807 tramp (not specified) @r{assume stack frame}
810 @code{frame} receives an integer argument@footnote{It is not
811 automatically computed because it does not know about the
812 requirement of later generated code.} that defines the size in
813 bytes for the stack frame of the current, @code{C} callable,
814 jit function. To calculate this value, a good formula is maximum
815 number of arguments to any called native function times
816 eight@footnote{Times eight so that it works for double arguments.
817 And would not need conditionals for ports that pass arguments in
818 the stack.}, plus the sum of the arguments to any call to
819 @code{jit_allocai}. @lightning{} automatically adjusts this value
820 for any backend specific stack memory it may need, or any
821 alignment constraint.
823 @code{frame} also instructs @lightning{} to save all callee
824 save registers in the prolog and reload in the epilog.
827 main: @rem{! jit entry point}
828 prolog @rem{! function prolog}
829 frame 256 @rem{! save all callee save registers and}
830 @rem{! reserve at least 256 bytes in stack}
833 jmpi handler @rem{! jumps to external code}
835 ret @rem{! return to the caller}
838 @code{tramp} differs from @code{frame} only that a prolog and epilog
839 will not be generated. Note that @code{prolog} must still be used.
840 The code under @code{tramp} must be ready to be entered with a jump
841 at the prolog position, and instead of a return, it must end with
842 a non conditional jump. @code{tramp} exists solely for the fact
843 that it allows optimizing out prolog and epilog code that would
847 handler: @rem{! handler entry point}
848 prolog @rem{! function prolog}
849 tramp 256 @rem{! assumes all callee save registers}
850 @rem{! are saved and there is at least}
851 @rem{! 256 bytes in stack}
853 jmpi main_loop @rem{! return to the main loop}
856 @lightning{} only supports Tail Call Optimization using the
857 @code{tramp} construct. Any other way is not guaranteed to
860 An example of a simple (recursive) tail call optimization:
863 factorial: @rem{! Entry point of the factorial function}
865 in = arg @rem{! Receive an integer argument}
866 getarg R0, in @rem{! Move argument to RO}
868 pushargi 1 @rem{! This is the accumulator}
869 pushargr R0 @rem{! This is the argument}
870 finishi fact @rem{! Call the tail call optimized function}
871 retval R0 @rem{! Fetch the result}
872 retr R0 @rem{! Return it}
873 epilog @rem{! Epilog *before* label before prolog}
875 fact: @rem{! Entry point of the helper function}
877 frame 16 @rem{! Reserve 16 bytes in the stack}
878 fact_entry: @rem{! This is the tail call entry point}
879 ac = arg @rem{! The accumulator is the first argument}
880 in = arg @rem{! The factorial argument}
881 getarg R0, ac @rem{! Move the accumulator to R0}
882 getarg R1, in @rem{! Move the argument to R1}
883 blei fact_out, R1, 1 @rem{! Done if argument is one or less}
884 mulr R0, R0, R1 @rem{! accumulator *= argument}
885 putargr R0, ac @rem{! Update the accumulator}
886 subi R1, R1, 1 @rem{! argument -= 1}
887 putargr R1, in @rem{! Update the argument}
888 jmpi fact_entry @rem{! Tail Call Optimize it!}
890 retr R0 @rem{! Return the accumulator}
895 forward_p (not specified) @r{forward label predicate}
896 indirect_p (not specified) @r{indirect label predicate}
897 target_p (not specified) @r{used label predicate}
898 arg_register_p (not specified) @r{argument kind predicate}
899 callee_save_p (not specified) @r{callee save predicate}
900 pointer_p (not specified) @r{pointer predicate}
903 @code{forward_p} expects a @code{jit_node_t*} argument, and
904 returns non zero if it is a forward label reference, that is,
905 a label returned by @code{forward}, that still needs a
908 @code{indirect_p} expects a @code{jit_node_t*} argument, and returns
909 non zero if it is an indirect label reference, that is, a label that
910 was returned by @code{indirect}.
912 @code{target_p} expects a @code{jit_node_t*} argument, that is any
913 kind of label, and will return non zero if there is at least one
914 jump or move referencing it.
916 @code{arg_register_p} expects a @code{jit_node_t*} argument, that must
917 have been returned by @code{arg}, @code{arg_f} or @code{arg_d}, and
918 will return non zero if the argument lives in a register. This call
919 is useful to know the live range of register arguments, as those
920 are very fast to read and write, but have volatile values.
922 @code{callee_save_p} exects a valid @code{JIT_Rn}, @code{JIT_Vn}, or
923 @code{JIT_Fn}, and will return non zero if the register is callee
924 save. This call is useful because on several ports, the @code{JIT_Rn}
925 and @code{JIT_Fn} registers are actually callee save; no need
926 to save and load the values when making function calls.
928 @code{pointer_p} expects a pointer argument, and will return non
929 zero if the pointer is inside the generated jit code. Must be
930 called after @code{jit_emit} and before @code{jit_destroy_state}.
932 @item Atomic operations
933 Only compare-and-swap is implemented. It accepts four operands;
934 the second can be an immediate.
936 The first argument is set with a boolean value telling if the operation
939 Arguments must be different, cannot use the result register to also pass
942 The second argument is the address of a machine word.
944 The third argument is the old value.
946 The fourth argument is the new value.
949 casr 01 = (*O2 == O3) ? (*O2 = O4, 1) : 0
950 casi 01 = (*O2 == O3) ? (*O2 = O4, 1) : 0
953 If value at the address in the second argument is equal to the third
954 argument, the address value is atomically modified to the value of the
955 fourth argument and the first argument is set to a non zero value.
957 If the value at the address in the second argument is not equal to the
958 third argument nothing is done and the first argument is set to zero.
961 @node GNU lightning examples
962 @chapter Generating code at run-time
964 To use @lightning{}, you should include the @file{lightning.h} file that
965 is put in your include directory by the @samp{make install} command.
967 Each of the instructions above translates to a macro or function call.
968 All you have to do is prepend @code{jit_} (lowercase) to opcode names
969 and @code{JIT_} (uppercase) to register names. Of course, parameters
970 are to be put between parentheses.
972 This small tutorial presents three examples:
977 The @code{incr} function found in @ref{The instruction set, ,
978 @lightning{}'s instruction set}:
981 A simple function call to @code{printf}
992 * incr:: A function which increments a number by one
993 * printf:: A simple function call to printf
994 * RPN calculator:: A more complex example, an RPN calculator
995 * Fibonacci:: Calculating Fibonacci numbers
1000 @section A function which increments a number by one
1002 Let's see how to create and use the sample @code{incr} function created
1003 in @ref{The instruction set, , @lightning{}'s instruction set}:
1007 #include <lightning.h>
1009 static jit_state_t *_jit;
1011 typedef int (*pifi)(int); @rem{/* Pointer to Int Function of Int */}
1013 int main(int argc, char *argv[])
1019 _jit = jit_new_state();
1021 jit_prolog(); @rem{/* @t{ prolog } */}
1022 in = jit_arg(); @rem{/* @t{ in = arg } */}
1023 jit_getarg(JIT_R0, in); @rem{/* @t{ getarg R0 } */}
1024 jit_addi(JIT_R0, JIT_R0, 1); @rem{/* @t{ addi R0@comma{} R0@comma{} 1 } */}
1025 jit_retr(JIT_R0); @rem{/* @t{ retr R0 } */}
1030 @rem{/* call the generated code@comma{} passing 5 as an argument */}
1031 printf("%d + 1 = %d\n", 5, incr(5));
1033 jit_destroy_state();
1039 Let's examine the code line by line (well, almost@dots{}):
1042 @item #include <lightning.h>
1043 You already know about this. It defines all of @lightning{}'s macros.
1045 @item static jit_state_t *_jit;
1046 You might wonder about what is @code{jit_state_t}. It is a structure
1047 that stores jit code generation information. The name @code{_jit} is
1048 special, because since multiple jit generators can run at the same
1049 time, you must either @r{#define _jit my_jit_state} or name it
1052 @item typedef int (*pifi)(int);
1053 Just a handy typedef for a pointer to a function that takes an
1054 @code{int} and returns another.
1056 @item jit_node_t *in;
1057 Declares a variable to hold an identifier for a function argument. It
1058 is an opaque pointer, that will hold the return of a call to @code{arg}
1059 and be used as argument to @code{getarg}.
1062 Declares a function pointer variable to a function that receives an
1063 @code{int} and returns an @code{int}.
1065 @item init_jit(argv[0]);
1066 You must call this function before creating a @code{jit_state_t}
1067 object. This function does global state initialization, and may need
1068 to detect CPU or Operating System features. It receives a string
1069 argument that is later used to read symbols from a shared object using
1070 GNU binutils if disassembly was enabled at configure time. If no
1071 disassembly will be performed a NULL pointer can be used as argument.
1073 @item _jit = jit_new_state();
1074 This call initializes a @lightning{} jit state.
1077 Ok, so we start generating code for our beloved function@dots{}
1079 @item in = jit_arg();
1080 @itemx jit_getarg(JIT_R0, in);
1081 We retrieve the first (and only) argument, an integer, and store it
1082 into the general-purpose register @code{R0}.
1084 @item jit_addi(JIT_R0, JIT_R0, 1);
1085 We add one to the content of the register.
1087 @item jit_retr(JIT_R0);
1088 This instruction generates a standard function epilog that returns
1089 the contents of the @code{R0} register.
1091 @item incr = jit_emit();
1092 This instruction is very important. It actually translates the
1093 @lightning{} macros used before to machine code, flushes the generated
1094 code area out of the processor's instruction cache and return a
1095 pointer to the start of the code.
1097 @item jit_clear_state();
1098 This call cleanups any data not required for jit execution. Note
1099 that it must be called after any call to @code{jit_print} or
1100 @code{jit_address}, as this call destroy the @lightning{}
1101 intermediate representation.
1103 @item printf("%d + 1 = %d", 5, incr(5));
1104 Calling our function is this simple---it is not distinguishable from
1105 a normal C function call, the only difference being that @code{incr}
1108 @item jit_destroy_state();
1109 Releases all memory associated with the jit context. It should be
1110 called after known the jit will no longer be called.
1113 This call cleanups any global state hold by @lightning{}, and is
1114 advisable to call it once jit code will no longer be generated.
1117 @lightning{} abstracts two phases of dynamic code generation: selecting
1118 instructions that map the standard representation, and emitting binary
1119 code for these instructions. The client program has the responsibility
1120 of describing the code to be generated using the standard @lightning{}
1123 Let's examine the code generated for @code{incr} on the SPARC and x86_64
1124 architecture (on the right is the code that an assembly-language
1125 programmer would write):
1138 In this case, @lightning{} introduces overhead to create a register
1139 window (not knowing that the procedure is a leaf procedure) and to
1140 move the argument to the general purpose register @code{R0} (which
1141 maps to @code{%g2} on the SPARC).
1151 mov %rdi,%rax mov %rdi, %rax
1152 add $0x1,%rax inc %rax
1158 In this case, the main overhead is due to the function's prolog and
1159 epilog, and stack alignment after reserving stack space for word
1160 to/from float conversions or moving data from/to x87 to/from SSE.
1161 Note that besides allocating space to save callee saved registers,
1162 no registers are saved/restored because @lightning{} notices those
1163 registers are not modified. There is currently no logic to detect
1164 if it needs to allocate stack space for type conversions neither
1165 proper leaf function detection, but these are subject to change
1170 @section A simple function call to @code{printf}
1172 Again, here is the code for the example:
1176 #include <lightning.h>
1178 static jit_state_t *_jit;
1180 typedef void (*pvfi)(int); @rem{/* Pointer to Void Function of Int */}
1182 int main(int argc, char *argv[])
1184 pvfi myFunction; @rem{/* ptr to generated code */}
1185 jit_node_t *start, *end; @rem{/* a couple of labels */}
1186 jit_node_t *in; @rem{/* to get the argument */}
1189 _jit = jit_new_state();
1191 start = jit_note(__FILE__, __LINE__);
1194 jit_getarg(JIT_R1, in);
1196 jit_pushargi((jit_word_t)"generated %d bytes\n");
1198 jit_pushargr(JIT_R1);
1199 jit_finishi(printf);
1202 end = jit_note(__FILE__, __LINE__);
1204 myFunction = jit_emit();
1206 @rem{/* call the generated code@comma{} passing its size as argument */}
1207 myFunction((char*)jit_address(end) - (char*)jit_address(start));
1212 jit_destroy_state();
1218 The function shows how many bytes were generated. Most of the code
1219 is not very interesting, as it resembles very closely the program
1220 presented in @ref{incr, , A function which increments a number by one}.
1222 For this reason, we're going to concentrate on just a few statements.
1225 @item start = jit_note(__FILE__, __LINE__);
1227 @itemx end = jit_note(__FILE__, __LINE__);
1228 These two instruction call the @code{jit_note} macro, which creates
1229 a note in the jit code; arguments to @code{jit_note} usually are a
1230 filename string and line number integer, but using NULL for the
1231 string argument is perfectly valid if only need to create a simple
1234 @item jit_ellipsis();
1235 @code{ellipsis} usually is only required if calling varargs functions
1236 with double arguments, but it is a good practice to properly describe
1237 the @r{@dots{}} in the call sequence.
1239 @item jit_pushargi((jit_word_t)"generated %d bytes\n");
1240 Note the use of the @code{(jit_word_t)} cast, that is used only
1241 to avoid a compiler warning, due to using a pointer where a
1242 wordsize integer type was expected.
1244 @item jit_prepare();
1246 @itemx jit_finishi(printf);
1247 Once the arguments to @code{printf} have been pushed, what means
1248 moving them to stack or register arguments, the @code{printf}
1249 function is called and the stack cleaned. Note how @lightning{}
1250 abstracts the differences between different architectures and
1251 ABI's -- the client program does not know how parameter passing
1252 works on the host architecture.
1255 Usually it is not required to call @code{epilog}, but because it
1256 is implicitly called when noticing the end of a function, if the
1257 @code{end} variable was set with a @code{note} call after the
1258 @code{ret}, it would not consider the function epilog.
1260 @item myFunction((char*)jit_address(end) - (char*)jit_address(start));
1261 This calls the generate jit function passing as argument the offset
1262 difference from the @code{start} and @code{end} notes. The @code{address}
1263 call must be done after the @code{emit} call or either a fatal error
1264 will happen (if @lightning{} is built with assertions enable) or an
1265 undefined value will be returned.
1267 @item jit_clear_state();
1268 Note that @code{jit_clear_state} was called after executing jit in
1269 this example. It was done because it must be called after any call
1270 to @code{jit_address} or @code{jit_print}.
1272 @item jit_disassemble();
1273 @code{disassemble} will dump the generated code to standard output,
1274 unless @lightning{} was built with the disassembler disabled, in which
1275 case no output will be shown.
1278 @node RPN calculator
1279 @section A more complex example, an RPN calculator
1281 We create a small stack-based RPN calculator which applies a series
1282 of operators to a given parameter and to other numeric operands.
1283 Unlike previous examples, the code generator is fully parameterized
1284 and is able to compile different formulas to different functions.
1285 Here is the code for the expression compiler; a sample usage will
1288 Since @lightning{} does not provide push/pop instruction, this
1289 example uses a stack-allocated area to store the data. Such an
1290 area can be allocated using the macro @code{allocai}, which
1291 receives the number of bytes to allocate and returns the offset
1292 from the frame pointer register @code{FP} to the base of the
1295 Usually, you will use the @code{ldxi} and @code{stxi} instruction
1296 to access stack-allocated variables. However, it is possible to
1297 use operations such as @code{add} to compute the address of the
1298 variables, and pass the address around.
1302 #include <lightning.h>
1304 typedef int (*pifi)(int); @rem{/* Pointer to Int Function of Int */}
1306 static jit_state_t *_jit;
1308 void stack_push(int reg, int *sp)
1310 jit_stxi_i (*sp, JIT_FP, reg);
1311 *sp += sizeof (int);
1314 void stack_pop(int reg, int *sp)
1316 *sp -= sizeof (int);
1317 jit_ldxi_i (reg, JIT_FP, *sp);
1320 jit_node_t *compile_rpn(char *expr)
1322 jit_node_t *in, *fn;
1323 int stack_base, stack_ptr;
1325 fn = jit_note(NULL, 0);
1328 stack_ptr = stack_base = jit_allocai (32 * sizeof (int));
1330 jit_getarg_i(JIT_R2, in);
1335 if (sscanf(expr, "%[0-9]%n", buf, &n)) @{
1337 stack_push(JIT_R0, &stack_ptr);
1338 jit_movi(JIT_R0, atoi(buf));
1339 @} else if (*expr == 'x') @{
1340 stack_push(JIT_R0, &stack_ptr);
1341 jit_movr(JIT_R0, JIT_R2);
1342 @} else if (*expr == '+') @{
1343 stack_pop(JIT_R1, &stack_ptr);
1344 jit_addr(JIT_R0, JIT_R1, JIT_R0);
1345 @} else if (*expr == '-') @{
1346 stack_pop(JIT_R1, &stack_ptr);
1347 jit_subr(JIT_R0, JIT_R1, JIT_R0);
1348 @} else if (*expr == '*') @{
1349 stack_pop(JIT_R1, &stack_ptr);
1350 jit_mulr(JIT_R0, JIT_R1, JIT_R0);
1351 @} else if (*expr == '/') @{
1352 stack_pop(JIT_R1, &stack_ptr);
1353 jit_divr(JIT_R0, JIT_R1, JIT_R0);
1355 fprintf(stderr, "cannot compile: %s\n", expr);
1366 The principle on which the calculator is based is easy: the stack top
1367 is held in R0, while the remaining items of the stack are held in the
1368 memory area that we allocate with @code{allocai}. Compiling a numeric
1369 operand or the argument @code{x} pushes the old stack top onto the
1370 stack and moves the operand into R0; compiling an operator pops the
1371 second operand off the stack into R1, and compiles the operation so
1372 that the result goes into R0, thus becoming the new stack top.
1374 This example allocates a fixed area for 32 @code{int}s. This is not
1375 a problem when the function is a leaf like in this case; in a full-blown
1376 compiler you will want to analyze the input and determine the number
1377 of needed stack slots---a very simple example of register allocation.
1378 The area is then managed like a stack using @code{stack_push} and
1381 Source code for the client (which lies in the same source file) follows:
1384 int main(int argc, char *argv[])
1386 jit_node_t *nc, *nf;
1391 _jit = jit_new_state();
1393 nc = compile_rpn("32x9*5/+");
1394 nf = compile_rpn("x32-5*9/");
1396 c2f = (pifi)jit_address(nc);
1397 f2c = (pifi)jit_address(nf);
1401 for (i = 0; i <= 100; i += 10) printf("%3d ", i);
1403 for (i = 0; i <= 100; i += 10) printf("%3d ", c2f(i));
1407 for (i = 32; i <= 212; i += 18) printf("%3d ", i);
1409 for (i = 32; i <= 212; i += 18) printf("%3d ", f2c(i));
1412 jit_destroy_state();
1418 The client displays a conversion table between Celsius and Fahrenheit
1419 degrees (both Celsius-to-Fahrenheit and Fahrenheit-to-Celsius). The
1420 formulas are, @math{F(c) = c*9/5+32} and @math{C(f) = (f-32)*5/9},
1423 Providing the formula as an argument to @code{compile_rpn} effectively
1424 parameterizes code generation, making it possible to use the same code
1425 to compile different functions; this is what makes dynamic code
1426 generation so powerful.
1429 @section Fibonacci numbers
1431 The code in this section calculates the Fibonacci sequence. That is
1432 modeled by the recurrence relation:
1436 f(n) = f(n-1) + f(n-2)
1439 The purpose of this example is to introduce branches. There are two
1440 kind of branches: backward branches and forward branches. We'll
1441 present the calculation in a recursive and iterative form; the
1442 former only uses forward branches, while the latter uses both.
1446 #include <lightning.h>
1448 static jit_state_t *_jit;
1450 typedef int (*pifi)(int); @rem{/* Pointer to Int Function of Int */}
1452 int main(int argc, char *argv[])
1457 jit_node_t *in; @rem{/* offset of the argument */}
1458 jit_node_t *ref; @rem{/* to patch the forward reference */}
1459 jit_node_t *zero; @rem{/* to patch the forward reference */}
1462 _jit = jit_new_state();
1464 label = jit_label();
1467 jit_getarg (JIT_V0, in); @rem{/* R0 = n */}
1468 zero = jit_beqi (JIT_R0, 0);
1469 jit_movr (JIT_V0, JIT_R0); /* V0 = R0 */
1470 jit_movi (JIT_R0, 1);
1471 ref = jit_blei (JIT_V0, 2);
1472 jit_subi (JIT_V1, JIT_V0, 1); @rem{/* V1 = n-1 */}
1473 jit_subi (JIT_V2, JIT_V0, 2); @rem{/* V2 = n-2 */}
1475 jit_pushargr(JIT_V1);
1476 call = jit_finishi(NULL);
1477 jit_patch_at(call, label);
1478 jit_retval(JIT_V1); @rem{/* V1 = fib(n-1) */}
1480 jit_pushargr(JIT_V2);
1481 call = jit_finishi(NULL);
1482 jit_patch_at(call, label);
1483 jit_retval(JIT_R0); @rem{/* R0 = fib(n-2) */}
1484 jit_addr(JIT_R0, JIT_R0, JIT_V1); @rem{/* R0 = R0 + V1 */}
1486 jit_patch(ref); @rem{/* patch jump */}
1487 jit_patch(zero); @rem{/* patch jump */}
1490 @rem{/* call the generated code@comma{} passing 32 as an argument */}
1493 printf("fib(%d) = %d\n", 32, fib(32));
1494 jit_destroy_state();
1500 As said above, this is the first example of dynamically compiling
1501 branches. Branch instructions have two operands containing the
1502 values to be compared, and return a @code{jit_note_t *} object
1505 Because labels final address are only known after calling @code{emit},
1506 it is required to call @code{patch} or @code{patch_at}, what does
1507 tell @lightning{} that the target to patch is actually a pointer to
1508 a @code{jit_node_t *} object, otherwise, it would assume that is
1509 a pointer to a C function. Note that conditional branches do not
1510 receive a label argument, so they must be patched.
1512 You need to call @code{patch_at} on the return of value @code{calli},
1513 @code{finishi}, and @code{calli} if it is actually referencing a label
1514 in the jit code. All branch instructions do not receive a label
1515 argument. Note that @code{movi} is an special case, and patching it
1516 is usually done to get the final address of a label, usually to later
1519 Now, here is the iterative version:
1523 #include <lightning.h>
1525 static jit_state_t *_jit;
1527 typedef int (*pifi)(int); @rem{/* Pointer to Int Function of Int */}
1529 int main(int argc, char *argv[])
1532 jit_node_t *in; @rem{/* offset of the argument */}
1533 jit_node_t *ref; @rem{/* to patch the forward reference */}
1534 jit_node_t *zero; @rem{/* to patch the forward reference */}
1535 jit_node_t *jump; @rem{/* jump to start of loop */}
1536 jit_node_t *loop; @rem{/* start of the loop */}
1539 _jit = jit_new_state();
1543 jit_getarg (JIT_R0, in); @rem{/* R0 = n */}
1544 zero = jit_beqi (JIT_R0, 0);
1545 jit_movr (JIT_R1, JIT_R0);
1546 jit_movi (JIT_R0, 1);
1547 ref = jit_blti (JIT_R1, 2);
1548 jit_subi (JIT_R2, JIT_R2, 2);
1549 jit_movr (JIT_R1, JIT_R0);
1552 jit_subi (JIT_R2, JIT_R2, 1); @rem{/* decr. counter */}
1553 jit_movr (JIT_V0, JIT_R0); /* V0 = R0 */
1554 jit_addr (JIT_R0, JIT_R0, JIT_R1); /* R0 = R0 + R1 */
1555 jit_movr (JIT_R1, JIT_V0); /* R1 = V0 */
1556 jump= jit_bnei (JIT_R2, 0); /* if (R2) goto loop; */
1557 jit_patch_at(jump, loop);
1559 jit_patch(ref); @rem{/* patch forward jump */}
1560 jit_patch(zero); @rem{/* patch forward jump */}
1563 @rem{/* call the generated code@comma{} passing 36 as an argument */}
1566 printf("fib(%d) = %d\n", 36, fib(36));
1567 jit_destroy_state();
1573 This code calculates the recurrence relation using iteration (a
1574 @code{for} loop in high-level languages). There are no function
1575 calls anymore: instead, there is a backward jump (the @code{bnei} at
1576 the end of the loop).
1578 Note that the program must remember the address for backward jumps;
1579 for forward jumps it is only required to remember the jump code,
1580 and call @code{patch} for the implicit label.
1583 @chapter Re-entrant usage of @lightning{}
1585 @lightning{} uses the special @code{_jit} identifier. To be able
1586 to be able to use multiple jit generation states at the same
1587 time, it is required to used code similar to:
1590 struct jit_state lightning;
1591 #define lightning _jit
1594 This will cause the symbol defined to @code{_jit} to be passed as
1595 the first argument to the underlying @lightning{} implementation,
1596 that is usually a function with an @code{_} (underscode) prefix
1597 and with an argument named @code{_jit}, in the pattern:
1600 static void _jit_mnemonic(jit_state_t *, jit_gpr_t, jit_gpr_t);
1601 #define jit_mnemonic(u, v) _jit_mnemonic(_jit, u, v);
1604 The reason for this is to use the same syntax as the initial lightning
1605 implementation and to avoid needing the user to keep adding an extra
1606 argument to every call, as multiple jit states generating code in
1607 paralell should be very uncommon.
1610 @chapter Accessing the whole register file
1612 As mentioned earlier in this chapter, all @lightning{} back-ends are
1613 guaranteed to have at least six general-purpose integer registers and
1614 six floating-point registers, but many back-ends will have more.
1616 To access the entire register files, you can use the
1617 @code{JIT_R}, @code{JIT_V} and @code{JIT_F} macros. They
1618 accept a parameter that identifies the register number, which
1619 must be strictly less than @code{JIT_R_NUM}, @code{JIT_V_NUM}
1620 and @code{JIT_F_NUM} respectively; the number need not be
1621 constant. Of course, expressions like @code{JIT_R0} and
1622 @code{JIT_R(0)} denote the same register, and likewise for
1623 integer callee-saved, or floating-point, registers.
1625 @section Scratch registers
1627 For operations, @lightning{} does not support directly, like storing
1628 a literal in memory, @code{jit_get_reg} and @code{jit_unget_reg} can be used to
1629 acquire and release a scratch register as in the following pattern:
1632 jit_int32_t reg = jit_get_reg (jit_class_gpr);
1633 jit_movi (reg, immediate);
1634 jit_stxi (offsetof (some_struct, some_field), JIT_V0, reg);
1635 jit_unget_reg (reg);
1638 As @code{jit_get_reg} and @code{jit_unget_reg} may generate spills and
1639 reloads but don't follow branches, the code between both must be in
1640 the same basic block and must not contain any branches as in the
1641 following (bad) example.
1644 jit_int32_t reg = jit_get_reg (jit_class_gpr);
1645 jit_ldxi (reg, JIT_V0, offset);
1646 jump = jit_bnei (reg, V0);
1647 jit_movr (JIT_V1, reg);
1649 jit_unget_reg (reg);
1652 @node Customizations
1653 @chapter Customizations
1655 Frequently it is desirable to have more control over how code is
1656 generated or how memory is used during jit generation or execution.
1658 @section Memory functions
1659 To aid in complete control of memory allocation and deallocation
1660 @lightning{} provides wrappers that default to standard @code{malloc},
1661 @code{realloc} and @code{free}. These are loosely based on the
1662 GNU GMP counterparts, with the difference that they use the same
1663 prototype of the system allocation functions, that is, no @code{size}
1664 for @code{free} or @code{old_size} for @code{realloc}.
1666 @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 *))
1667 @lightning{} guarantees that memory is only allocated or released
1668 using these wrapped functions, but you must note that if lightning
1669 was linked to GNU binutils, malloc is probably will be called multiple
1670 times from there when initializing the disassembler.
1672 Because @code{init_jit} may call memory functions, if you need to call
1673 @code{jit_set_memory_functions}, it must be called before @code{init_jit},
1674 otherwise, when calling @code{finish_jit}, a pointer allocated with the
1675 previous or default wrappers will be passed.
1678 @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 *))
1679 Get the current memory allocation function. Also, unlike the GNU GMP
1680 counterpart, it is an error to pass @code{NULL} pointers as arguments.
1683 @section Alternate code buffer
1684 To instruct @lightning{} to use an alternate code buffer it is required
1685 to call @code{jit_realize} before @code{jit_emit}, and then query states
1686 and customize as appropriate.
1688 @deftypefun void jit_realize ()
1689 Must be called once, before @code{jit_emit}, to instruct @lightning{}
1690 that no other @code{jit_xyz} call will be made.
1693 @deftypefun jit_pointer_t jit_get_code (jit_word_t *@var{code_size})
1694 Returns NULL or the previous value set with @code{jit_set_code}, and
1695 sets the @var{code_size} argument to an appropriate value.
1696 If @code{jit_get_code} is called before @code{jit_emit}, the
1697 @var{code_size} argument is set to the expected amount of bytes
1698 required to generate code.
1699 If @code{jit_get_code} is called after @code{jit_emit}, the
1700 @var{code_size} argument is set to the exact amount of bytes used
1704 @deftypefun void jit_set_code (jit_ponter_t @var{code}, jit_word_t @var{size})
1705 Instructs @lightning{} to output to the @var{code} argument and
1706 use @var{size} as a guard to not write to invalid memory. If during
1707 @code{jit_emit} @lightning{} finds out that the code would not fit
1708 in @var{size} bytes, it halts code emit and returns @code{NULL}.
1711 A simple example of a loop using an alternate buffer is:
1715 int *(func)(int); @rem{/* function pointer */}
1716 jit_word_t code_size;
1717 jit_word_t real_code_size;
1719 jit_realize(); @rem{/* ready to generate code */}
1720 jit_get_code(&code_size); @rem{/* get expected code size */}
1721 code_size = (code_size + 4095) & -4096;
1723 code = mmap(NULL, code_size, PROT_EXEC | PROT_READ | PROT_WRITE,
1724 MAP_PRIVATE | MAP_ANON, -1, 0);
1725 jit_set_code(code, code_size);
1726 if ((func = jit_emit()) == NULL) @{
1727 munmap(code, code_size);
1730 @} while (func == NULL);
1731 jit_get_code(&real_code_size); @rem{/* query exact size of the code */}
1734 The first call to @code{jit_get_code} should return @code{NULL} and set
1735 the @code{code_size} argument to the expected amount of bytes required
1737 The second call to @code{jit_get_code} is after a successful call to
1738 @code{jit_emit}, and will return the value previously set with
1739 @code{jit_set_code} and set the @code{real_code_size} argument to the
1740 exact amount of bytes used to emit the code.
1742 @section Alternate data buffer
1743 Sometimes it may be desirable to customize how, or to prevent
1744 @lightning{} from using an extra buffer for constants or debug
1745 annotation. Usually when also using an alternate code buffer.
1747 @deftypefun jit_pointer_t jit_get_data (jit_word_t *@var{data_size}, jit_word_t *@var{note_size})
1748 Returns @code{NULL} or the previous value set with @code{jit_set_data},
1749 and sets the @var{data_size} argument to how many bytes are required
1750 for the constants data buffer, and @var{note_size} to how many bytes
1751 are required to store the debug note information.
1752 Note that it always preallocate one debug note entry even if
1753 @code{jit_name} or @code{jit_note} are never called, but will return
1754 zero in the @var{data_size} argument if no constant is required;
1755 constants are only used for the @code{float} and @code{double} operations
1756 that have an immediate argument, and not in all @lightning{} ports.
1759 @deftypefun void jit_set_data (jit_pointer_t @var{data}, jit_word_t @var{size}, jit_word_t @var{flags})
1761 @var{data} can be NULL if disabling constants and annotations, otherwise,
1762 a valid pointer must be passed. An assertion is done that the data will
1763 fit in @var{size} bytes (but that is a noop if @lightning{} was built
1764 with @code{-DNDEBUG}).
1766 @var{size} tells the space in bytes available in @var{data}.
1768 @var{flags} can be zero to tell to just use the alternate data buffer,
1769 or a composition of @code{JIT_DISABLE_DATA} and @code{JIT_DISABLE_NOTE}
1772 @item JIT_DISABLE_DATA
1773 @cindex JIT_DISABLE_DATA
1774 Instructs @lightning{} to not use a constant table, but to use an
1775 alternate method to synthesize those, usually with a larger code
1776 sequence using stack space to transfer the value from a GPR to a
1779 @item JIT_DISABLE_NOTE
1780 @cindex JIT_DISABLE_NOTE
1781 Instructs @lightning{} to not store file or function name, and
1782 line numbers in the constant buffer.
1786 A simple example of a preventing usage of a data buffer is:
1790 jit_realize(); @rem{/* ready to generate code */}
1791 jit_get_data(NULL, NULL);
1792 jit_set_data(NULL, 0, JIT_DISABLE_DATA | JIT_DISABLE_NOTE);
1796 Or to only use a data buffer, if required:
1800 jit_word_t data_size;
1802 jit_realize(); @rem{/* ready to generate code */}
1803 jit_get_data(&data_size, NULL);
1805 data = malloc(data_size);
1808 jit_set_data(data, data_size, JIT_DISABLE_NOTE);
1815 @node Acknowledgements
1816 @chapter Acknowledgements
1818 As far as I know, the first general-purpose portable dynamic code
1819 generator is @sc{dcg}, by Dawson R.@: Engler and T.@: A.@: Proebsting.
1820 Further work by Dawson R. Engler resulted in the @sc{vcode} system;
1821 unlike @sc{dcg}, @sc{vcode} used no intermediate representation and
1822 directly inspired @lightning{}.
1824 Thanks go to Ian Piumarta, who kindly accepted to release his own
1825 program @sc{ccg} under the GNU General Public License, thereby allowing
1826 @lightning{} to use the run-time assemblers he had wrote for @sc{ccg}.
1827 @sc{ccg} provides a way of dynamically assemble programs written in the
1828 underlying architecture's assembly language. So it is not portable,
1829 yet very interesting.
1831 I also thank Steve Byrne for writing GNU Smalltalk, since @lightning{}
1832 was first developed as a tool to be used in GNU Smalltalk's dynamic
1833 translator from bytecodes to native code.