The code in this section calculates the Fibonacci sequence. That is modeled by the recurrence relation:
f(0) = 0
f(1) = f(2) = 1
f(n) = f(n-1) + f(n-2)
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.
#include <stdio.h> #include <lightning.h> static jit_state_t *_jit; typedef int (*pifi)(int); /* 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; /* offset of the argument */ jit_node_t *ref; /* to patch the forward reference */ jit_node_t *zero; /* 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); /* 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); /* V1 = n-1 */ jit_subi (JIT_V2, JIT_V0, 2); /* V2 = n-2 */ jit_prepare(); jit_pushargr(JIT_V1); call = jit_finishi(NULL); jit_patch_at(call, label); jit_retval(JIT_V1); /* V1 = fib(n-1) */ jit_prepare(); jit_pushargr(JIT_V2); call = jit_finishi(NULL); jit_patch_at(call, label); jit_retval(JIT_R0); /* R0 = fib(n-2) */ jit_addr(JIT_R0, JIT_R0, JIT_V1); /* R0 = R0 + V1 */ jit_patch(ref); /* patch jump */ jit_patch(zero); /* patch jump */ jit_retr(JIT_R0); /* call the generated code, 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; }
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 jit_note_t * object
to be patched.
Because labels final address are only known after calling emit,
it is required to call patch or patch_at, what does
tell GNU lightning that the target to patch is actually a pointer to
a 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 patch_at on the return of value calli,
finishi, and calli if it is actually referencing a label
in the jit code. All branch instructions do not receive a label
argument. Note that movi is an special case, and patching it
is usually done to get the final address of a label, usually to later
call jmpr.
Now, here is the iterative version:
#include <stdio.h> #include <lightning.h> static jit_state_t *_jit; typedef int (*pifi)(int); /* Pointer to Int Function of Int */ int main(int argc, char *argv[]) { pifi fib; jit_node_t *in; /* offset of the argument */ jit_node_t *ref; /* to patch the forward reference */ jit_node_t *zero; /* to patch the forward reference */ jit_node_t *jump; /* jump to start of loop */ jit_node_t *loop; /* start of the loop */ init_jit(argv[0]); _jit = jit_new_state(); jit_prolog (); in = jit_arg (); jit_getarg (JIT_R0, in); /* 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); /* 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); /* patch forward jump */ jit_patch(zero); /* patch forward jump */ jit_retr (JIT_R0); /* call the generated code, 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; }
This code calculates the recurrence relation using iteration (a
for loop in high-level languages). There are no function
calls anymore: instead, there is a backward jump (the 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 patch for the implicit label.