JITиё моё

Этот пост посвящаю хорошему человеку и хорошему программисту — Ярославу, недавно реализовавшему свой первый Brainfuck-интерпретатор.

Итак, все мы любим компиляторы и виртуальные машины. Некоторые из них считаются круче, потому что в них есть JIT. А что же такое этот JIT?

Обычно под этим словом подразумевают некую магическую силу, которая ускоряет виртуальную машину в несколько раз, ровно настолько, чтобы можно было хвастать тем фактом, что в ней есть JIT.

А как это работает внутри? Вот об этом и поговорим.

Brainэтосамое

Итак, напишем свой JIT компилятор для Самого Простого Языка. Сложнее языки я не потяну, да и лень, а еще проще… Ну проще просто не бывает.

Дано. Инструкции <, > = сдвинуть указатель влево-вправо; +, — = увеличить/уменшить на 1 значение по указателю, [ и ] — начало и конец цикла (в цикл входим если значение по указателю не равно нулю). Еще есть точка и запятая — для ввода и вывода символов.

Простой не-JIT интерпретатор пишется легко (хотя и погружает вас в мистический мир виртуальных машин и всего такого):

char m[9999],*n[99],*r=m,*p=m+5000,**s=n,d,c;main(){for(read(0,r,p)
;c=*r++;c-93?c-91?d?0:c-43&~2?c-44?c-46?p+=c&~2^60?0:c%4-1:write(1,
p,1):read(2,p,1):(*p-=c-44):d++||(*++s=r):d&&--d?0:*p?r=*s:--s);}

Ой. Я этот код украл в образовательных целях (http://esoteric.sange.fi/brainfuck/impl/interp/small.c). Ну, если совсем не понятно — вот код интерпретатора на самом брейнф-е:

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]

Это код из http://www.hevanet.com/cristofd/brainfuck/
Вроде бы это самый лаконичный.

Но, давайте делать JIT.

JIT

И вот оно разочарование. Нет никакой магии. Просто выделяем сегмент памяти (с правами rwx, чтобы код в нем можно было читать, писать и выполнять), пишем туда куски машинного кода, и делаем туда goto. Всё. Потом освобождаем память. Делать в настоящей жизни такое на каждый чих не нужно, наверное нужно оптимизировать только часто выполняемые участки кода, длинные циклы и все такое. Да, тут уже конечно без магии никуда. Но мы сейчас не об этом. Итак, простой JIT.

Сколько машинных инструкций вы помните наизусть? Вот и я ни одной. Поэтому предлагаю такой вот хак. Например для инструкции «+» (которая «(*p)++» в С) делать следующее:

bf_inc_start:
  (*p)++;
bf_inc_end:

Теперь, у нас есть адрес начала машинного кода и его конца. Можно делать memcpy(). Чтобы не писать все руками сделаем пару макросов:

#define JIT_BEGIN(name) bf_ ## name ## _begin
#define JIT_END(name) bf_ ## name ## _end
#define nop() asm ("nop");

#define JIT_CODE(name, code) \
	if (jit == 0) { \
		JIT_BEGIN(name): \
		code ; \
		JIT_END(name): \
		nop(); \
	} else { \
		memcpy(jitptr, &&JIT_BEGIN(name), \
				&&JIT_END(name) - &&JIT_BEGIN(name)); \
		jitptr += &&JIT_END(name) - &&JIT_BEGIN(name); \
	}

Эти макросы очень некрасивые, но работают. JIT_CODE либо интерпретирует код, либо копирует соответствующие машинные инструкции в область памяти для JIT. Кстати, без nop() вы рискуете узнать, что метки в конце блоков кода не ставят, напр.:

if (...) {
  ...
label: /* так нельзя */
}

Итак. Приступим к реализации нашего интерпрето-компилятора-с-JIT. Все будет в одной функции. Причин несколько. В основном — это любовь x86 к относительным адресам. Глобальные переменные окажутся недоступными если перенести наш машинный код в другое место, некоторые переходы тоже. Мы об этом еще сильно пожалеем когда доберемся до циклов. Вот весь код:

void bf(const char *s, int jit) {
	volatile char mem[8];
	volatile char volatile *p = mem;
	volatile void  *loops[128]; /* who needs more than 128 nested loops in BF?! */
	volatile void **sp = loops;
	volatile void *jitend;
	void *code;
	void *jitptr;
	int (*in)(void) = &getchar;
	int (*out)(int)  = &putchar;
	int i;

	int sz = 4096;

	memset(mem, 0, sizeof(mem));

	if (jit) {
		code = mmap (0, sz, PROT_READ | PROT_WRITE | PROT_EXEC,  
				MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
		jitptr = code;
	}
	for (;;) {
		switch (*s++) {
			case '<':
				JIT_CODE(left, p--);
				break;
			case '>':
				JIT_CODE(right, p++);
				break;
			case '+':
				JIT_CODE(inc, (*p)++);
				break;
			case '-':
				JIT_CODE(dec, (*p)--);
				break;
			case ',':
				JIT_CODE(in, (*p) = in());
				break;
			case '.':
				JIT_CODE(out, out((int) *p));
				break;
			case '[':
				if (jit) {
					*sp++ = jitptr;
					JIT_CODE(enter, { if (*p == 0) { void *endloop = 0x0123456789abcdef; goto *endloop; }});
				} else {

				}
				break;
			case ']':
				if (jit) {
					void *start = *(--sp);
					void *patchhi, *patchlo;
					uint32_t patternhi = 0x01234567;
					uint32_t patternlo = 0x89abcdef;
					patchhi = xmemmem(start, jitptr - start, &patternhi, sizeof(patternhi));
					patchlo = xmemmem(start, jitptr - start, &patternlo, sizeof(patternlo));
					JIT_CODE(exit, { asm volatile("jmp *%0" :: "r" (start)); })
					(* ((uint32_t *) patchhi)) = (uint32_t) ((uintptr_t) jitptr >> 32);
					(* ((uint32_t *) patchlo)) = (uint32_t) ((uintptr_t) jitptr & 0xffffffff);
				} else {

				}
				break;
			case '\0':
				if (!jit) {
					return;
				}
				JIT_CODE(ret, asm volatile("jmp *%0" :: "r" (&&end)));
				goto do_jit;
		}
	}
do_jit:
	if (jit) {
		unsigned char *p;
		memcpy(jitptr, &&JIT_BEGIN(ret), &&JIT_END(ret) - &&JIT_BEGIN(ret));
		jitptr += &&JIT_END(ret) - &&JIT_BEGIN(ret);

		for (p = code; p < jitptr; p++) {
			printf("%02x ", *p);
		}
		printf("\n");
		goto *code;
	}
end:
	if (jit) {
		munmap(code, sz);
	}
	printf("POINTER=%ld\n", p - mem);
	for (i = 0; i < sizeof(mem); i++) {
		printf("%02x ", (unsigned char) mem[i]);
	}
	printf("\n");
	return;
}

Переменная «jit» определяет режим — интерпретатор или компилятор JIT. Все переменные связанные с состоянием BF-машины делаем volatile, чтобы оптимизатору неповадно было.
С помощью mmap/munmap работаем с областью памяти для JIT.

Как в любом интерпретаторе BF в цикле читаем инструкции. Для каждой их них либо формируем машинные инструкции, либо интерпретируем (макрос JIT_CODE).

» заслуживает отдельной обработки, т.к. он возвращает нас назад в нашу функцию из JIT-области.

После всех операций и компиляции, если мы в JIT-режиме — дописываем «ret» и делаем goto в скомпилированную область. Если не рухнем — то все удачно.

В конце работы просто показываем чё наш язык наделал — состояние памяти и указателя.

А что же с циклами? На открывающую скобку запоминаем текущий адрес в JIT-области, нам сюда еще возвращаться. Код JIT такой — если под указателем сейчас 0 — прыгнуть в конец цикла. А где конец цикла? Пока не знаем. Заменяем этот адрес на метку — 0x0123456789abcdef (у меня 64-битная система). Когда встречаем закрывающую скобку — берем адрес открывающей из стека, делаем туда jmp. И патчим нашу метку фактическим адресом конца цикла.

Кстати, у меня сломался memmem из glibc — пришлось писать свой. Я так понимаю эта функция вообще тяжелой судьбы (см. маны)?

Вот и всё. Запускаем:

bf("+++", 0) - интерпретируем. Получаем [3, 0, ....] в памяти
bf("+++", 1) - то же, но с JIT. 
bf("+[,.]", 1) - программа "cat" с JIT.
bf("+++[,.]", 1) - считывает три буквы
На hello world - падает 🙂

Вообщем, так JIT писать нельзя. Работает только с gcc без оптимизаций, на 32-битной системе немного проще и стабильнее (как переделать под 32 бита — домашнее задание). Хотя идея конечно вначале казалась забавной — использовать машинный код одного компилятора для другого да еще и убить двух зайцев. Авантюра не удалась.

Выводы

Можно делать JIT по-человечески. Есть библиотечка GNU lightning (http://www.gnu.org/software/lightning/) для генерации JIT-кода, она дает более-менее универсальный набор инструкций, и не глючит. Еще можно смотреть в сторону LLVM. Но, конечно, свой велосипед ближе к телу.

Процессор J1 — куда уж проще

Осторожно — эта статья не содержит и теоретической, ни практической пользы, и была написана просто, как подведение черты под одним из увлечений.

Я давний фанат этого процессора. Я писал о нем на хабре, дважды, и хочется написать еще.

Для тех, кто не слышал никогда о J1 — это простенький процессор,
ориентированный на язык Форт. Для любителей подробностей — официальный сайт J1 CPU.

Так вот, я с гордостью могу сказать, что я маялся бездельем и тем временем написал эмулятор + компилятор почти-Форта для J1. Здесь я расскажу что это и зачем. Читать далее