RPN JIT Compiler
/* http://redd.it/2zna5q | |
* Fibonacci example: | |
* (1) (2) + | |
* 0:0 | |
* 1:1 | |
* 20 | |
*/ | |
#define _BSD_SOURCE // MAP_ANONYMOUS | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <stdint.h> | |
#include <string.h> | |
#include <unistd.h> | |
struct asmbuf { | |
size_t nconstants; | |
double constants[32]; | |
size_t size, fill; | |
uint8_t code[]; | |
}; | |
#ifdef __WIN32__ | |
#include <windows.h> | |
struct asmbuf * | |
asmbuf_create(void) | |
{ | |
SYSTEM_INFO system_info; | |
GetSystemInfo(&system_info); | |
long page_size = system_info.dwPageSize; | |
struct asmbuf *buf = | |
VirtualAlloc(NULL, page_size, MEM_COMMIT, PAGE_READWRITE); | |
buf->size = page_size; | |
return buf; | |
} | |
void | |
asmbuf_free(struct asmbuf *buf) | |
{ | |
VirtualFree(buf, buf->size, MEM_RELEASE); | |
} | |
void | |
asmbuf_finalize(struct asmbuf *buf) | |
{ | |
DWORD old_protect; | |
VirtualProtect(buf, buf->size, PAGE_EXECUTE_READ, &old_protect); | |
} | |
#else /* POSIX */ | |
#include <sys/mman.h> | |
struct asmbuf * | |
asmbuf_create(void) | |
{ | |
long page_size = sysconf(_SC_PAGESIZE); | |
int prot = PROT_READ | PROT_WRITE; | |
int flags = MAP_ANONYMOUS | MAP_PRIVATE; | |
struct asmbuf *buf = mmap(NULL, page_size, prot, flags, -1, 0); | |
buf->size = page_size; | |
return buf; | |
} | |
void | |
asmbuf_free(struct asmbuf *buf) | |
{ | |
munmap(buf, buf->size); | |
} | |
void | |
asmbuf_finalize(struct asmbuf *buf) | |
{ | |
mprotect(buf, buf->size, PROT_READ | PROT_EXEC); | |
} | |
#endif | |
void | |
asmbuf_ins(struct asmbuf *buf, int size, uint64_t ins) | |
{ | |
for (int i = size - 1; i >= 0; i--) | |
buf->code[buf->fill++] = (ins >> (i * 8)) & 0xff; | |
} | |
void | |
asmbuf_immediate(struct asmbuf *buf, int size, const void *value) | |
{ | |
memcpy(buf->code + buf->fill, value, size); | |
buf->fill += size; | |
} | |
static void | |
operator2(struct asmbuf *buf, int size, uint64_t op) | |
{ | |
asmbuf_ins(buf, 6, 0x660f1244cff0); // movlpd -16(%rdi, %rcx, 8), %xmm0 | |
asmbuf_ins(buf, 6, 0x660f124ccff8); // movlpd -8(%rdi, %rcx, 8), %xmm1 | |
asmbuf_ins(buf, size, op); | |
asmbuf_ins(buf, 3, 0x48ffc9); // dec %rcx | |
asmbuf_ins(buf, 6, 0x660f1344cff8); // movlpd %xmm0, -8(%rdi, %rcx, 8) | |
} | |
int | |
main(void) | |
{ | |
/* %rdi : pointer to the base of the stack | |
* %rsi : index of the top of the stack when called | |
* %rcx : index of the current top of the stack | |
* %xmm* : intermediate results | |
*/ | |
struct asmbuf *buf = asmbuf_create(); | |
long max_backreference = 0; | |
long max_stack = 0; | |
long current_stack = 0; | |
asmbuf_ins(buf, 3, 0x4889f1); // mov %rsi, %rcx | |
int c; | |
while ((c = fgetc(stdin)) != '\n' && c != EOF) { | |
if (c == ' ') | |
continue; | |
switch (c) { | |
case '0': | |
case '1': | |
case '2': | |
case '3': | |
case '4': | |
case '5': | |
case '6': | |
case '7': | |
case '8': | |
case '9': { | |
ungetc(c, stdin); | |
double *data = &buf->constants[buf->nconstants++]; | |
scanf("%lf", data); | |
asmbuf_ins(buf, 2, 0x48a1); // mov (data), %rax | |
asmbuf_immediate(buf, 8, &data); | |
asmbuf_ins(buf, 4, 0x488904cf); // mov %rax, (%rdi, %rcx, 8) | |
asmbuf_ins(buf, 3, 0x48ffc1); // inc %rcx | |
if (++current_stack > max_stack) | |
max_stack = current_stack; | |
} break; | |
case '(': { | |
int n; | |
scanf("%d)", &n); | |
if (n > max_backreference) | |
max_backreference = n; | |
int8_t offset = -8 * n; | |
asmbuf_ins(buf, 4, 0x488b44f7); // mov -offset(%rdi,%rsi,8),%rax | |
asmbuf_immediate(buf, 1, &offset); | |
asmbuf_ins(buf, 4, 0x488904cf); // mov %rax, (%rdi, %rcx, 8) | |
asmbuf_ins(buf, 3, 0x48ffc1); // inc %rcx | |
if (++current_stack > max_stack) | |
max_stack = current_stack; | |
} break; | |
case '+': | |
operator2(buf, 4, 0xf20f58c1); // addsd %xmm1,%xmm0 | |
current_stack--; | |
break; | |
case '-': | |
operator2(buf, 4, 0xf20f5cc1); // subsd %xmm1,%xmm0 | |
current_stack--; | |
break; | |
case '*': | |
operator2(buf, 4, 0xf20f59c1); // mulsd %xmm1,%xmm0 | |
current_stack--; | |
break; | |
case '/': | |
operator2(buf, 4, 0xf20f5ec1); // divsd %xmm1,%xmm0 | |
current_stack--; | |
break; | |
case 'Q': | |
asmbuf_ins(buf, 6, 0x660f124ccff8); // movlpd -8(%rdi,%rcx,8),%xmm1 | |
asmbuf_ins(buf, 4, 0xf20f51c9); // sqrtsd %xmm1,%xmm1 | |
asmbuf_ins(buf, 6, 0x660f134ccff8); // movlpd %xmm1,-8(%rdi,%rcx,8) | |
break; | |
case '@': | |
asmbuf_ins(buf, 6, 0x660f124ccff8); // movlpd -8(%rdi,%rcx,8),%xmm1 | |
asmbuf_ins(buf, 6, 0x660f134ccff8); // movlpd %xmm1,-8(%rdi,%rcx,8) | |
if (++current_stack > max_stack) | |
max_stack = current_stack; | |
break; | |
} | |
} | |
asmbuf_ins(buf, 3, 0x4889c8); // mov %rcx, %rax | |
asmbuf_ins(buf, 1, 0xc3); // retq | |
asmbuf_finalize(buf); | |
__attribute__ ((sysv_abi)) | |
long (*recurrence)(double *, long) = (void *)buf->code; | |
double stack[max_backreference + max_stack]; | |
/* Accept up to `max_backreference` initial values. */ | |
long nterms; | |
for (;;) { | |
char line[256]; | |
fgets(line, sizeof(line), stdin); | |
long n; | |
double value; | |
if (sscanf(line, "%ld:%lf", &n, &value) != 2) { | |
nterms = strtol(line, NULL, 10); | |
break; | |
} else { | |
stack[n] = value; | |
} | |
} | |
/* Compute terms. */ | |
for (long n = 0; n < max_backreference; n++) | |
printf("%ld: %.15f\n", n, stack[n]); | |
for (long n = max_backreference; n <= nterms;) { | |
long nelements = recurrence(stack, max_backreference); | |
long nvalues = nelements - max_backreference; | |
for (long i = 0; i < nvalues; i++) | |
printf("%ld: %.15f\n", n + i, stack[max_backreference + i]); | |
memmove(stack, stack + nvalues, max_backreference * sizeof(stack[0])); | |
n += nvalues; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment