Previous: , Up: GNU lightning examples

### 4.4 Fibonacci numbers

The code in this section calculates a variant of the Fibonacci sequence. While the traditional Fibonacci sequence is modeled by the recurrence relation:

```     f(0) = f(1) = 1
f(n) = f(n-1) + f(n-2)
```

the functions in this section calculates the following sequence, which is more interesting as a benchmark7:

```     fib(0) = fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) + 1
```

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 */

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

label = jit_label();
jit_prolog   ();
in =  jit_arg      ();
jit_getarg   (JIT_V0, in);              /* V0 = n */
ref = jit_blti     (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_V2);                     /* V2 = fib(n-2) */
jit_addr(JIT_R0, JIT_V1, JIT_V2);       /* R0 = V1 + V2 + 1 */
jit_retr(JIT_R0);

jit_patch(ref);                               /* patch jump */
jit_movi(JIT_R0, 1);                    /* R0 = 1 */
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 *loop;             /* start of the loop */

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

jit_prolog   ();
in =  jit_arg      ();
jit_getarg   (JIT_R2, in);              /* R2 = n */
jit_movi     (JIT_R1, 1);
ref = jit_blti     (JIT_R2, 2);
jit_subi     (JIT_R2, JIT_R2, 1);
jit_movi     (JIT_R0, 1);

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

jit_patch(ref);                               /* patch forward jump */
jit_movr     (JIT_R0, JIT_R1);          /* R0 = R1 */
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.

### (7)

That’s because, as is easily seen, the sequence represents the number of activations of the `nfibs` procedure that are needed to compute its value through recursion.

Previous: , Up: GNU lightning examples