Встраивание JIT-компиляторов в C-интерпретаторы

Laurence Tratt рассказывает о yk - системе, которая автоматически превращает C-интерпретаторы в JIT-компилирующие виртуальные машины с помощью meta-tracing. Замысел прост: добавляем ~400 строк кода в PUC Lua или MicroPython и получаем среднее геометрическое ускорение около 2x при сохранении полной совместимости с эталонной реализацией.

Почему это важно

Создание JIT-компиляторов обходится очень дорого. На HotSpot ушло более 1000 человеко-лет. Над V8 годами работает большая команда. К тому же JIT-компиляторы обычно отстают от спецификаций языка: изменения в языке ломают допущения, глубоко зашитые в JIT. LuaJIT застрял на тринадцатилетней давности Lua 5.1.

Альтернативные подходы (RPython, Truffle) позволяют создавать отличные JIT, но требуют написания нового интерпретатора. Пользователи же не терпят реализаций формата "почти совместимо".

yk заполняет этот пробел: выводит JIT прямо из эталонного C-интерпретатора. Полная совместимость получается автоматически, потому что JIT-компиляции подвергается сам эталонный код.

Как работает meta-tracing

Трассирующий JIT наблюдает за гостевой программой (Lua, Python) и записывает её исполнение. Мета-трассирующий JIT наблюдает за хостовым интерпретатором (C), который выполняет гостевую программу.

Когда работает интерпретатор Lua:

switch (GET_OPCODE(i)) {
  case OP_ADD: push(pop() + pop()); pc++; break;
  ...
}

Мета-трассировщик записывает не факт "произошёл OP_ADD", а реальные операции языка C: чтения из памяти, сложение, записи. Затем он оптимизирует полученную трассу и компилирует её в машинный код.

Ключевое преимущество: meta-tracing естественным образом выполняет инлайнинг через границы функций. Вместо записи вызова push(...) он сохраняет само содержимое push. Именно этим yk отличается от подходов copy-and-patch, которые компилируют только основной цикл интерпретатора.

Реализация через ykllvm

yk использует форк LLVM, который инструментирует интерпретатор на этапе компиляции. Он вставляет вызовы __yk_trace_basicblock(id) в каждую точку управления потоком, присваивая каждому базовому блоку уникальный ID. Когда обнаруживается горячий цикл, система фиксирует, какие именно блоки выполняются.

Трасса оптимизируется и компилируется в машинный код. Когда интерпретатор в следующий раз доходит до этого цикла, он передаёт управление скомпилированному коду.

Три ключевые оптимизации

Promotion (продвижение) - функция yk_promote(val) сообщает трассировщику: "зашей это значение времени выполнения прямо в трассу как константу". После этого в трассу добавляется guard-проверка, которая выполняет деоптимизацию, если значение изменится. При диспетчеризации инструкций продвижение опкода позволяет полностью вырезать оператор switch.

Idempotent functions (идемпотентные функции) - пометка функции через yk_idempotent даёт оптимизатору знать, что при одинаковых входных данных функция всегда чистая. Это открывает путь к агрессивной константной свёртке. В статье утверждается, что одна лишь пометка загрузки опкода как идемпотентной дала 4-кратный прирост, устранив накладные расходы на декодирование инструкций.

Backward code generation (генерация кода в обратном порядке) - идея заимствована из LuaJIT. Генерация машинного кода с конца к началу обеспечивает более качественное распределение регистров и неявно удаляет мёртвый код.

Деоптимизация

Если guard-проверка не проходит, выполнение должно вернуться в интерпретатор. Для этого требуется восстановить стек фреймов и состояние регистров интерпретатора в точке проверки - то есть прыгнуть из JIT-скомпилированного кода обратно в середину AOT-скомпилированной функции.

Для реализации этого механизма yk расширяет функциональность stackmap в LLVM. Он использует shadow stack для хранения информации, необходимой для восстановления состояния интерпретатора на любом guard'е.

Компромисс

yklua демонстрирует среднее геометрическое ускорение порядка 2x на бенчмарках, а на некоторых доходит до 4-6x. Это меньше пиковых показателей оптимизированного вручную LuaJIT. Зато обновление yklua с Lua 5.4.6 до 5.5.0 заняло меньше двух часов. В случае с LuaJIT на это ушли бы месяцы.

Ниша yk: вы жертвуете абсолютным максимумом производительности ради тривиальной поддержки свежих версий и абсолютной совместимости.

Текущее состояние

Проект находится на стадии alpha, финансируется Shopify и Royal Academy of Engineering. Поддерживается только x64. Хватает нереализованных оптимизаций. Можно наткнуться на TODO, которые прерывают исполнение. Но система уже работает достаточно стабильно, чтобы показывать заметное ускорение на реальных программах.

Проекты: yk (ядро), yklua (Lua), ykmicropython (MicroPython), ykllvm (форк LLVM).

bytecode-to-source-mapping описывает учёт на противоположной стороне того же интерпретатора - восстановление исходной строки по смещению в байткоде, а также компромиссы между объёмом памяти и скоростью поиска, выбранные в JVM и Lua.