Skip to content

Instantly share code, notes, and snippets.

Created March 20, 2015 14:30
Show Gist options
  • Save anonymous/f7e4a5086a2b0acc83aa to your computer and use it in GitHub Desktop.
Save anonymous/f7e4a5086a2b0acc83aa to your computer and use it in GitHub Desktop.
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