4.3 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 GNU 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 allocai, which receives the number of bytes to allocate and returns the offset from the frame pointer register FP to the base of the area.

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

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

typedef int (*pifi)(int);       /* 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(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;
}

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 allocai. Compiling a numeric operand or the argument 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 ints. 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 stack_push and stack_pop.

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

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;
}

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

Providing the formula as an argument to 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.