runloops test

vm.c

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <time.h>
#include <windows.h>

#define label(FUNC, NAME) \
	(void)&&FUNC ## __ ## NAME; \
	FUNC ## __ ## NAME: \
	__asm__ __volatile__ ( "\
	.global " #FUNC "__" #NAME "\n\
	.global _" #FUNC "__" #NAME "\n\
	" #FUNC "__" #NAME ":\n\
	_" #FUNC "__" #NAME ":\n")

enum { N = 1 << 29 };

enum op
{
	HALT,
	VALUE,
	COUNTER,
	ADD,
	SUB,
	CHOICE,
	SKIP,
	LOOP,
};

union scell
{
	enum op op;
	int arg;
};

union tcell
{
	const void *op;
	int arg;
};

struct cvm
{
	const union ccell *ip;
	int value;
	int counter;
};

struct jvm
{
	const void *ip;
	int value;
};

union ccell
{
	void (*op)(struct cvm *);
	int arg;
};

extern const char core_threaded__HALT[];
extern const char core_threaded__VALUE[];
extern const char core_threaded__COUNTER[];
extern const char core_threaded__ADD[];
extern const char core_threaded__SUB[];
extern const char core_threaded__CHOICE[];
extern const char core_threaded__SKIP[];
extern const char core_threaded__LOOP[];

extern void core_jit__HALT(void);
extern void core_jit__VALUE(void);
extern void core_jit__COUNTER(void);
extern void core_jit__ADD(void);
extern void core_jit__SUB(void);
extern void core_jit__CHOICE(void);
extern void core_jit__SKIP(void);
extern void core_jit__LOOP(void);

static inline void *alloc_pages(size_t size, int executable)
{
    return VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE,
        executable ? PAGE_EXECUTE_READWRITE : PAGE_READWRITE);
}

static inline int free_pages(void *pages, size_t size)
{
    (void)size;
    return VirtualFree(pages, 0, MEM_RELEASE);
}

int core_switch(const union scell *ip)
{
	register int value;
	register int counter;

	for(;; ++ip) switch(ip->op)
	{
		case HALT:
		return value;

		case VALUE:
		value = (++ip)->arg;
		continue;

		case COUNTER:
		counter = (++ip)->arg;
		continue;

		case ADD:
		value += (++ip)->arg;
		continue;

		case SUB:
		value -= (++ip)->arg;
		continue;

		case CHOICE:
		ip += counter % 2 ? ip[1].arg + 1 : 1;
		continue;

		case SKIP:
		ip += ip[1].arg + 1;
		continue;

		case LOOP:
		ip += --counter ? -(ip[1].arg + 1) : 1;
		continue;
	}
}

int core_goto(const union scell *ip)
{
	static const void *const LABELS[] = {
		[HALT] = &&LABEL_HALT,
		[VALUE] = &&LABEL_VALUE,
		[COUNTER] = &&LABEL_COUNTER,
		[ADD] = &&LABEL_ADD,
		[SUB] = &&LABEL_SUB,
		[CHOICE] = &&LABEL_CHOICE,
		[SKIP] = &&LABEL_SKIP,
		[LOOP] = &&LABEL_LOOP,
	};

	register int value;
	register int counter;

	goto *LABELS[ip->op];

	LABEL_HALT:
	return value;

	LABEL_VALUE:
	value = (++ip)->arg;
	goto *LABELS[(++ip)->op];

	LABEL_COUNTER:
	counter = (++ip)->arg;
	goto *LABELS[(++ip)->op];

	LABEL_ADD:
	value += (++ip)->arg;
	goto *LABELS[(++ip)->op];

	LABEL_SUB:
	value -= (++ip)->arg;
	goto *LABELS[(++ip)->op];

	LABEL_CHOICE:
	ip += counter % 2 ? ip[1].arg + 1 : 1;
	goto *LABELS[(++ip)->op];

	LABEL_SKIP:
	ip += ip[1].arg + 1;
	goto *LABELS[(++ip)->op];

	LABEL_LOOP:
	ip += --counter ? -(ip[1].arg + 1) : 1;
	goto *LABELS[(++ip)->op];
}

int core_threaded(const union tcell *ip)
{
	register int value;
	register int counter;

	goto *ip->op;

	label(core_threaded, HALT);
	return value;

	label(core_threaded, VALUE);
	value = (++ip)->arg;
	goto *(++ip)->op;

	label(core_threaded, COUNTER);
	counter = (++ip)->arg;
	goto *(++ip)->op;

	label(core_threaded, ADD);
	value += (++ip)->arg;
	goto *(++ip)->op;

	label(core_threaded, SUB);
	value -= (++ip)->arg;
	goto *(++ip)->op;

	label(core_threaded, CHOICE);
	ip += counter % 2 ? (ip[1].arg + 1) : 1;
	goto *(++ip)->op;

	label(core_threaded, SKIP);
	ip += ip[1].arg + 1;
	goto *(++ip)->op;

	label(core_threaded, LOOP);
	ip += --counter ? -(ip[1].arg + 1) : 1;
	goto *(++ip)->op;
}

static void core_call__HALT(struct cvm *vm) {}

static void core_call__VALUE(struct cvm *vm)
{
	vm->value = (++vm->ip)->arg;
	(++vm->ip)->op(vm);
}

static void core_call__COUNTER(struct cvm *vm)
{
	vm->counter = (++vm->ip)->arg;
	(++vm->ip)->op(vm);
}

static void core_call__ADD(struct cvm *vm)
{
	vm->value += (++vm->ip)->arg;
	(++vm->ip)->op(vm);
}

static void core_call__SUB(struct cvm *vm)
{
	vm->value -= (++vm->ip)->arg;
	(++vm->ip)->op(vm);
}

static void core_call__CHOICE(struct cvm *vm)
{
	vm->ip += vm->counter % 2 ? (vm->ip[1].arg + 1) : 1;
	(++vm->ip)->op(vm);
}

static void core_call__SKIP(struct cvm *vm)
{
	vm->ip += vm->ip[1].arg + 1;
	(++vm->ip)->op(vm);
}

static void core_call__LOOP(struct cvm *vm)
{
	vm->ip += --vm->counter ? -(vm->ip[1].arg + 1) : 1;
	(++vm->ip)->op(vm);
}

int core_call(const union ccell *ip)
{
	struct cvm vm = { .ip = ip };
	ip->op(&vm);
	return vm.value;
}

__asm__("\
core_jit__HALT:\n\
	addq $0x8, %rsp\n\
	retq\n\
");

__asm__("\
core_jit__VALUE:\n\
	movl %edx, %eax\n\
	retq\n\
");

__asm__("\
core_jit__COUNTER:\n\
	movl %edx, %ecx\n\
	retq\n\
");

__asm__("\
core_jit__ADD:\n\
	addl %edx, %eax\n\
	retq\n\
");

__asm__("\
core_jit__SUB:\n\
	subl %edx, %eax\n\
	retq\n\
");

// dangerous: using %ebx messes with winapi!!!
__asm__("\
core_jit__CHOICE:\n\
	movl %ecx, %ebx\n\
	andl $1, %ebx\n\
	jz core_jit__CHOICE_even\n\
	movq (%rsp), %r8\n\
	movslq %edx, %rdx\n\
	leaq (%r8,%rdx), %r8\n\
	movq %r8, (%rsp)\n\
core_jit__CHOICE_even:\n\
	retq\n\
");

__asm__("\
core_jit__SKIP:\n\
	movq (%rsp), %r8\n\
	movslq %edx, %rdx\n\
	leaq (%r8,%rdx), %r8\n\
	movq %r8, (%rsp)\n\
	retq\n\
");

__asm__("\
core_jit__LOOP:\n\
	decl %ecx\n\
	jz core_jit__LOOP_break\n\
	popq %r8\n\
	movsx %edx, %rdx\n\
	subq %rdx, %r8\n\
	pushq %r8\n\
core_jit__LOOP_break:\n\
	retq\n\
");

extern void core_jit__HALT(void);
extern void core_jit__VALUE(void);
extern void core_jit__COUNTER(void);
extern void core_jit__ADD(void);
extern void core_jit__SUB(void);
extern void core_jit__CHOICE(void);
extern void core_jit__SKIP(void);
extern void core_jit__LOOP(void);

enum
{
	JIT_ARG_SIZE = 5,
	JIT_CALL_SIZE = 5,
};

static void jit_arg(void **cp, int value)
{
	unsigned char *bp = *cp;
	*bp++ = 0xBA;

	memcpy(bp, &value, sizeof value);
	bp += sizeof value;

	*cp = bp;
}

static void jit_call(void **cp, void fn(void))
{
	unsigned char *bp = *cp;

	ptrdiff_t diff = (unsigned char *)fn - (bp + 5);
	assert(INT_MIN <= diff && diff <= INT_MAX);
	int offset = (int)diff;

	*bp++ = 0xE8;
	
	memcpy(bp, &offset, sizeof offset);
	bp += sizeof offset;

	*cp = bp;
}

int main(void)
{
	static const union scell SCODE[] = {
		{ .op = VALUE },
		{ .arg = 0 },
		{ .op = COUNTER },
		{ .arg = N },
		{ .op = CHOICE },
		{ .arg = 4 },
		{ .op = ADD },
		{ .arg = 2 },
		{ .op = SKIP },
		{ .arg = 2 },
		{ .op = SUB },
		{ .arg = 1 },
		{ .op = LOOP },
		{ .arg = 8 },
		{ .op = HALT },
	};

	{
		clock_t start = clock();
		int value = core_switch(SCODE);
		clock_t end = clock();
		printf("switch core: got %i in %ums\n", value,
			(unsigned)(((end - start) * 1000) / CLOCKS_PER_SEC));
	}

	{
		clock_t start = clock();
		int value = core_goto(SCODE);
		clock_t end = clock();
		printf("goto core: got %i in %ums\n", value,
			(unsigned)(((end - start) * 1000) / CLOCKS_PER_SEC));
	}

	{
		static const union tcell TCODE[] = {
			{ .op = core_threaded__VALUE },
			{ .arg = 0 },
			{ .op = core_threaded__COUNTER },
			{ .arg = N },
			{ .op = core_threaded__CHOICE },
			{ .arg = 4 },
			{ .op = core_threaded__ADD },
			{ .arg = 2 },
			{ .op = core_threaded__SKIP },
			{ .arg = 2 },
			{ .op = core_threaded__SUB },
			{ .arg = 1 },
			{ .op = core_threaded__LOOP },
			{ .arg = 8 },
			{ .op = core_threaded__HALT },
		};

		clock_t start = clock();
		int value = core_threaded(TCODE);
		clock_t end = clock();
		printf("threaded core: got %i in %ums\n", value,
			(unsigned)(((end - start) * 1000) / CLOCKS_PER_SEC));
	}

	{
		static const union ccell CCODE[] = {
			{ .op = core_call__VALUE },
			{ .arg = 0 },
			{ .op = core_call__COUNTER },
			{ .arg = N },
			{ .op = core_call__CHOICE },
			{ .arg = 4 },
			{ .op = core_call__ADD },
			{ .arg = 2 },
			{ .op = core_call__SKIP },
			{ .arg = 2 },
			{ .op = core_call__SUB },
			{ .arg = 1 },
			{ .op = core_call__LOOP },
			{ .arg = 8 },
			{ .op = core_call__HALT },
		};

		clock_t start = clock();
		int value = core_call(CCODE);
		clock_t end = clock();
		printf("call core: got %i in %ums\n", value,
			(unsigned)(((end - start) * 1000) / CLOCKS_PER_SEC));
	}

	{
		void *code = alloc_pages(1024, 1);

		void *cp[1] = { code };
		jit_arg(cp, 0);
		jit_call(cp, core_jit__VALUE);
		jit_arg(cp, N);
		jit_call(cp, core_jit__COUNTER);
		jit_arg(cp, 2 * (JIT_ARG_SIZE + JIT_CALL_SIZE));
		jit_call(cp, core_jit__CHOICE);
		jit_arg(cp, 2);
		jit_call(cp, core_jit__ADD);
		jit_arg(cp, JIT_ARG_SIZE + JIT_CALL_SIZE);
		jit_call(cp, core_jit__SKIP);
		jit_arg(cp, 1);
		jit_call(cp, core_jit__SUB);
		jit_arg(cp, 5 * (JIT_ARG_SIZE + JIT_CALL_SIZE));
		jit_call(cp, core_jit__LOOP);
		jit_call(cp, core_jit__HALT);

		clock_t start = clock();
		int value = ((int (*)(void))code)();
		clock_t end = clock();
		printf("jit core: got %i in %ums\n", value,
			(unsigned)(((end - start) * 1000) / CLOCKS_PER_SEC));

		free_pages(code, 1024);
	}
}