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 benchmark5:

     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_addi(JIT_V1,  JIT_V1,  1);
        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 *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_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.


Footnotes

(5)

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