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 int
s. 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.