JIT-компилятор как учебный проект в Академическом Университете

Около шестнадцати лет назад вышла первая версия Hotspot – реализация JVM, впоследствии ставшая стандартной виртуальной машиной, поставляемой в комплекте JRE от Sun.

Основным отличием этой реализации стал JIT-компилятор, благодаря которому заявления про медленную Джаву во-многих случаях стали совсем несостоятельными.
Сейчас почти все интерпретируемые платформы, такие как CLR, Python, Ruby, Perl, и даже замечательный язык программирования R, обзавелись своими реализациями JIT-трансляторов.

В рамках этой статьи я не планирую проливать свет на малоизвестные детали реализации промышленных JIT-компиляторов, скорее это будет совсем поверхностное ознакомление с азами и рассказ про учебный проект по соответствующей тематике.

Таким образом вам может быть интересно под катом, если:

• Вы принципиально не понимаете, что такое JIT-компилятор, или у вас есть легкое непонимание, чем такой подход существенно лучше интерпретации.
• Вы хотели бы написать простой JIT для своего интерпретируемого языка.
• Вы преподаете курс «Языки программирования и компиляторы», и не против сделать практическое задание для студентов еще интересней.
• Вам интересно, как нарисована эта картинка.

Преимущества JIT-компиляции

Чтобы говорить о преимуществах сначала разберемся, с тем, что это такое. Начнем издалека, а именно с определения компилируемого языка.

Компилируемый язык программирования — язык программирования, исходный код которого преобразуется компилятором в машинный код конкретной архитектуры, например x86/ARM. Этот машинный код представляет собой последовательность команд, которая совсем понятна вашему процессору, и может быть исполнена им без посредника.

Интерпретируемые языки программирования отличаются тем, что исходники не преобразовываются в машинный код для непосредственного выполнения на ЦПУ, а исполняются с помощью специальной программы-интерпретатора.
Как промежуточный вариант, многие языки (Java, C#, Python) транслируются в машинно-независимый байт-код ^[1],
который все еще не может быть исполнен напрямую на ЦПУ, и чтобы его исполнить все еще необходим интерпретатор.

Почему интерпретация медленней? Ответ на этот вопрос, как ни странно не всем кажется очевидным, хотя он действительно очень простой: интерпретируя каждую команду по отдельности, мы затрачиваем дополнительные ресурсы на перевод семантики этой команды на язык процессора. Кроме того современные процессоры оптимизированы для выполнения последовательных команд (см. Конвейер ^[2]), а интерпретатор чаще всего представляет собой огромный switch с кучей опций, загоняющий в тупик предсказатель переходов ^[3].

Вполне естественным решением всех этих проблем было бы лишь однажды перевести байт-код на язык процессора и передать его ЦПУ для исполнения. Так чаще всего и поступают, называя этот процесс Just-in-time-компиляцией (JIT). Кроме того, именно в течение этой фазы чаще всего проводятся различные оптимизации генерируемого кода.

Теперь перейдем к практике.

Постановка задачи

Курс “Виртуализация и виртуальные машины” в нашем университете читает Николай Иготти, принимавший участие в разработке самых разных классов ВМ: Hotspot, VirtualBox, NativeClient, и не понаслышке знающий детали их реализации. Благодаря чудесам современных технологий, чтобы узнать про это все подробней необязательно даже быть студентом Академического Университета, так как курс опубликован на лекториуме ^[4]. Хотя нужно отметить, что это конечно немного не то, в силу интерактивности курса и работе с аудиторией на лекциях.

В рамках курса для получения допуска к экзамену студентам было предложено написать свою реализацию простой стековой виртуальной машины-интерпретатора и транслятор в байт-код из C-подобного языка. На самом деле задание несколько проще, чем может показаться на первый взгляд – вместе с заданием выдается много готового кода на C++:

• Парсер в AST того самого языка программирования, который нужно транслировать. За это огромное спасибо! Обычно к шестому курсу студенты АУ успевают написать по шестнадцать различных парсеров, и писать еще один рекурсивный спуск совсем неинтересно.
• Список типов инструкций байт-кода в виде enum’а с подробными комментариями.
• Утилитные классы для работы с байт-кодом: его конструирование и работа с бинарным представлением.

Кодовое название у всего этого задания – mathvm, видимо в силу того, что основная цель языка программирования, как это часто бывает, что-нибудь посчитать.

Типичная программа на языке mathvm:

function int fib(int x) {
    if (x <= 1) {
        return x;
    }
    int r = fib(x - 1);
    return r + fib(x - 2);
}
print(fib(35), 'n');

Основные возможности языка:

• Работа с типами данных: int, double, string, арифметика над ними.
• Стандартные управляющие конструкции: if, while, for, print.
• Возможность объявления функций внутри функций, как следствие наличие замыканий. Эта фича, хоть и вызвала множество вопросов при проектировании интерпретатора, однако, с учетом наличия инструкций для работы с замыканиями не стала камнем преткновения.
• Возможность декларации native-функций. То есть можно объявить функцию без тела с пометкой native и именем символа, который может быть загружен виртуальной машиной через dlsym ^[5] с параметром RTLD_DEFAULT.
  Например так:

  function void printfIDS(string format, int x1, double x2, string x3) native ‘printf’;
  printfIDS(‘%d %f %sn’, 1, 2, ‘abc’);
  

Мне кажется именно последний пункт делает задание намного веселей:

• Во-первых не сразу понятно, как можно передать в функцию заранее неизвестное множество аргументов, если в рантайме у вас есть указатель на функцию, сигнатура и вычисленные аргументы сохранены в определенное место в памяти. Более-менее ясно, что совсем кроссплатформенно это сделать не удастся, и как минимум нужно зафиксировать Calling conventions. Мы сошлись на соглашении о вызовах из System V ABI ^[6], использующегося в популярных unix-системах.
  Но даже после этого не кажется очевидным, как наиболее безболезненно достичь цели.
  Единственное, что приходило в голову – огромная, страшная ассемблерная вставка с кодом, который раскладывает аргументы по соответствующим регистрам и ячейкам стека. В результате я выбрал немного другое решение, которое опишу ниже.
• Native-функции значительно расширяют возможности получаемого языка. Когда после нескольких дней угара интерпретатор и транслятор готовы, и вместо унылого численного интегрирования трапециями, на вашем детище запускается что-нибудь такое ^[7] и рисует на экране крутую психоделическую анимацию (см. скриншот в начале статьи), это является приятным бонусом.

Внимательный читатель мог заметить, что в программе из последнего пункта зачем-то вычисляется количество отрисовываемых кадров в секунду (FPS). Этот показатель позволяет оценить производительность интерпретатора и позволяет таким образом привнести соревновательный дух в казавшийся кому-то скучным учебный процесс.
Студент, интерпретатор которого будет самым быстрым на этом и еще паре подобных бенчмарков, автоматически сдает экзамен, а кроме того получает любовь и уважение коллег. Надо отметить, что мы не первый поток, с которым играли в эту игру, и обычно для победы нужно было реализовать JIT-компилятор.

Сложности

Казалось бы, что существенно сложного в том, чтобы просто перевести семантику несложных байт-код инструкций в соответствующие элементы набора инструкций x86?

1. Если бы у нас был компилируемый язык, то мы бы могли буквально сгенерировать текст на языке ассемблера, затем соответственно ассемблировать, получив в результате исполняемый файл.
   Но в рамках JIT-трансляции разделять процесс на две эти фазы – непозволительная роскошь, и нужно как-то сразу научиться генерировать в памяти процесса ВМ машинный код.
2. Да и не любая область памяти подойдет для записи машинного кода. Точнее записать-то можно куда угодно, но вот передать исполнение можно только на область памяти, страницы которой отмечены как исполняемые. Кажется тут не обойтись простым malloc’ом.
3. В идеале, конечно, чтобы получаемый машинный код работал как можно быстрее.

Asmjit

Для решения первых двух проблем вполне подходит Asmjit ^[8] – библиотека с открытым исходным кодом, развиваемая по большей части одним человеком в течение последних нескольких лет, и используемая в других проектах автора, а также в JIT для скриптов на сервере GTA San Andreas MP ^[9].
Как несложно понять из названия, её основная миссия – создание удобного API для генерации машинного кода Just-in-time. Eё публичный интерфейс можно разделить на две части:

• X86Assembler – низкоуровневый интерфейс, который по сути позволяет делать три вещи:
  1. Инициировать выделение куска памяти с привилегиями на исполнение.
  2. Располагать в нем инструкции/данные последовательно и заводить метки для мест, куда существуют переходы из других участков кода.
     Для работы с кодом в библиотеке есть набор классов-операндов: GpReg, XmmReg, Imm, Mem, а для каждой инструкции в классе есть одноименный метод, причем ровно с тем набором перегрузок, которые допустимы для данной инструкции. Например метод с сигнатурой mov(X86Mem &, X86Mem &) отсутствует, как и должно быть.
  3. Получение указателя на начало заполненного куска памяти, который можно использовать, как указатель на функцию-точку входа.

• X86Compiler – высокоуровневая обертка над X86Assembler, инкапсулирующая
  • Создание функций и работу с аргументами в соответствии с заданными calling conventions, как на стороне определения функции, так и в месте вызова (кстати наиболее простой способ реализовать native-функции).
  • Регистровую аллокацию: можно определить переменные (GpVar или XmmVar), место для хранения которых компилятор выберет сам. Сразу оговорюсь, что не искал, и не в курсе насчет того, какой алгоритм аллокации используется. Единственное, что могу сказать – на простых экспериментах имеющиеся регистры использовались вполне разумно.

В своей реализации я использовал именно Assembler, подкупивший меня своей прозрачностью и более тонкой управляемостью.

Самый простой работающий пример использования Asmjit:

#include "asmjit/asmjit.h"
#include <iostream>

int main(int argc, char** argv) {
    using namespace std;
    using namespace asmjit;
    using namespace asmjit::x86;

    JitRuntime runtime; // RAII object

    X86Assembler assembler(&runtime);
    assembler.add(rdi, rsi); // add second argument to first
    assembler.mov(rax, rdi); // mov result to return register
    assembler.ret();

    void * address = assembler.make();
    cout << reinterpret_cast<int64_t (*) (int64_t, int64_t)>(address)(2, 2) << endl; // 4

    return 0;
}

Я думаю у людей, знакомых с ассемблером, он не должен вызвать много вопросов. Единственное, о чем следует упомянуть – объект runtime, отвечающий за время жизни выделенной памяти. Она будет освобождена после вызова его деструктора (RAII ^[10]).
Еще примеры использования можно подсмотреть в каталоге с тестами библиотеки или у меня в репозитории.

Отладка

Как ни странно отладка сгенерированного кода не отличается особыми извращениями.
Во-первых, если что-то пошло не так, можно вдумчиво посмотреть логи Asmjit. В логах можно увидеть полученный ассемблерный код и немножко комментариев, откуда он здесь появился.
В случае, если даже это вам не помогло, то в большинстве современных дебаггеров (gdb/VS) есть возможность работы в режиме отладки с дизассемблированием. То есть вы можете поставить брейкпойнт на место вызова сгенерированной функции, и Step Into переведет вас на экран с ассемблерным кодом, где можно почти как обычно пошагово отлаживать.
Важно

• В трех случаях из десяти через полчаса вы найдете ошибку не в компиляторе, а в самой интерпретируемой программе.
• К сожалению, так как Asmjit пока не слишком интенсивно используется, потенциально может содержать разной степени противности баги. Поэтому внимательно смотрите, что в логах именно то, что вы хотели. Хотя мне ничего не попадалось, моему одногруппнику не повезло: тот факт, что был сгенерирован невалидный код не было видно даже в логах, а только в дебаггере.

Оптимизация

После трех дней активного программирования и отладки появился первый совершенно бесхитростный вариант JIT-транслятора, в котором все значения стека и переменных каждый раз бездумно сохранялись в память.
Даже такое решение дало прирост производительности примерно в шесть раз, с 6 FPS, которые получались с интерпретатором до 36 FPS.

Вообще в начале семестра, когда выяснились правила игры, у меня были наполеоновские планы: сделать все совсем по-взрослому – с переводом байткода в SSA ^[11] и умным алгоритмом регистровой аллокации.
Но в связи с острой нехваткой времени и банальным малодушием все закончилось несколько прозаичней.

Распределение регистров

На всякий случай напомню, что один из наиболее критичных пунктов в плане производительности программы – эффективность использования имеющихся регистров ЦПУ.
Это связано с тем, что основная вычислительная деятельность может производиться только на них, а кроме того чтение/запись даже в память, находящуюся в L1-кэше, работает до двух раз дольше, чем аналогичные операции над регистрами.
Я воспользовался не самым сложным, но зато довольно действенным эвристическим решением: будем хранить в регистрах первые элементы стека виртуальной машины, 7 элементов для слотов общего назначения (строки/целые числа) и 14 для слотов для чисел с плавающей точкой.
Это решение кажется наиболее оправданным, так как наиболее горячими переменными в рамках работы функции действительно является именно низ стека, участвующий во всех вычислениях.
Кроме того, если использовать те же самые регистры, по которым раскладываются аргументы при вызове функций, то это в некоторых случаях позволяет сэкономить время в местах вызова.
В результате реализации этих идей, я получил ускорение на 9 FPS, таким образом достигнув 45 FPS, что не могло меня не радовать.

Peephole-оптимизации

Одним из простых классических подходов при генерации являются так называемые Peephole-оптимизации ^[12], идея которых заключается в поиске и замене определенных последовательностей инструкций на другие, более производительные.

Например из-за недостатка выразительности байт-кода mathvm, операторы сравнения вроде (x0 <= x1) приходится описывать как-то так:

LOADIVAR_0
LOADIVAR_1
IF_CMPLE L1
ILOAD_0 // загрузка константы 0 на вершину стека
JA L2 // безусловный переход
L1:
ILOAD_1
L2: 
...

Знатоки Instructions set’а x86, скажут, что такой код можно записать гораздо короче и без единого условного прыжка:

mov rdi, %(var0)
mov rsi, %(var1)
cmp rdi, rsi
setle al
movzx rax, al

Подобные конструкции встречаются и в других случаях: оператор отрицания, цикл for. Детектирование и исправление этих паттернов привело к ускорению на 4 FPS до 49 пунктов.

Оптимизация замыканий

Для обеспечания работы с замыканиями в прологе и эпилоге каждой функции я сохранял в специально выделенную область памяти вне стека адрес, где расположены переменные последнего вызова.
Кроме того нужно сохранять и восстанавливать предыдущий base pointer. На всю эту радость уходило до семи лишних инструкций на каждый вызов, в том числе активно работающих с памятью.
На деле же большинство функций не содержит внутри себя замыканий, и этих потерь можно избежать.
Поэтому я провел дополнительный анализ всего полученного байт-кода на предмет наличия замыканий и соответствующие избыточные инструкции были удалены, в результате чего мультик стал рисоваться еще на 3 FPS быстрее.

Inlining

Заключительный пункт истории про микрооптимизации – inlining или по-русски ”встраивание”. Метод, с помощью которого промышленные компиляторы борются с расходами на вызов маленьких функций: код вызываемой функции просто дублируется в месте вызова, без пролога/эпилога и прочих “лишних” инструкций. Правда надо отметить, что в настоящей жизни к решению о встраивании компиляторы подходят очень осторожно – размер получаемого машинного кода все-таки тоже является мерилом качества их работы.

Однако в моем случае, так как оценивается именно время работы, я решил попробовать встраивать все, что встраивается (нерекурсивные вызовы).
И вот здесь как ни странно оказалось легче работать на уровне трансляции AST в байт-код.

Полученный прирост на 2 FPS был уже не таким значительным, как в предыдущих случаях, но суммарные 53-54 FPS (почти девятикратное ускорение) не могут не радовать. Ускорение таких же порядков наблюдалось и на других доступных бенчмарках.

Что интересно, даже в моем простом JIT-трансляторе для получения пиковой производительности требовалось несколько итераций разогрева, хотя я совсем не запускал интерпретатор и сразу компилировал весь код.
Это иллюстрирует высказывания авторитетных людей про то, что warmup в бенчмарках нужен не только для того, чтобы все, что нужно, скомпилировалось, а еще и для устаканивания профиля программы.

Итоги

В результате моя реализация стала самой быстрой, однако связано это не столько с тем, что я самый хитрый, сколько с тем, что никто из соперников не сделал даже самую простую реализацию JIT’а.
Таким образом отсутствие хоть какой-то спортивной интриги немного омрачило победу.

Исходники моей реализации можно посмотреть в репозитории ^[13], в каталоге impl.
Заранее извиняюсь за качество кода, но это все-таки игрушечный проект, и поддерживать его дальше я не планирую.

Спасибо за внимание!

Автор: bintree

Источник ^[14]