Этот пост посвящаю хорошему человеку и хорошему программисту – Ярославу, недавно реализовавшему свой первый 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. Но, конечно, свой велосипед ближе к телу.
