Метатрейсинг

Метатрейсинг - это техника автоматического создания JIT-компиляторов на основе интерпретаторов. Вместо трассировки гостевой программы (Lua, Python) она трассирует сам хостовый интерпретатор (на C или RPython) в процессе выполнения гостевого кода.

Трейсинг и метатрейсинг

Обычный трейсинг-JIT наблюдает за гостевым кодом и записывает операции:

OP_LOOKUP("x")
guard true, pop() > 0
OP_ADD

Метатрейсинг-JIT наблюдает за интерпретатором и записывает хостовые операции:

push(lookup("x")); pc++;
guard true, pop() > 0; pc++;
push(pop() + pop()); pc++;

Метатрейс фиксирует всё, что интерпретатор на C (или RPython) делал на самом деле - обращения к памяти, арифметику, поток управления. Затем этот трейс оптимизируется и компилируется в машинный код.

Почему это работает

Ключевая идея: интерпретатор - это обычная программа. Трейс работы интерпретатора при выполнении гостевого кода содержит всё необходимое для эффективного исполнения этого кода без накладных расходов на интерпретацию.

Метатрейсинг естественным образом инлайнит код через границы функций. Когда в трейсе встречается push(val), он записывает не вызов push, а тело функции push: проверку границ, сохранение значения, инкремент указателя. Глубокий инлайнинг происходит автоматически.

Именно поэтому метатрейсинг может оптимизировать код далеко за пределами главного цикла интерпретатора. Вспомогательные функции, проверки типов, поиск методов - всё это инлайнится в единый оптимизированный трейс.

Линеаризация и guard'ы

Трейсы линеаризуют поток управления. Когда трассируемое исполнение идёт по ветке true в условном операторе if, трейс сохраняет только эту ветку. В точке ветвления трейс вставляет guard. Если впоследствии guard не срабатывает (условие оказалось ложным), исполнение деоптимизируется обратно в интерпретатор.

За простоту трейсов приходится расплачиваться именно guard'ами. Трейс, построенный по успешному сценарию ("happy path"), будет деоптимизироваться при каждом отклонении от него. Код с частыми ветвлениями порождает трейсы с большим количеством guard'ов, что снижает выигрыш.

RPython и Truffle

Две основные системы метатрейсинга:

RPython (часть PyPy) - интерпретатор пишется на ограниченном подмножестве Python. RPython компилирует его в C и добавляет метатрейсинг. Сам PyPy представляет собой интерпретатор Python, написанный на RPython. Даёт высокую производительность, но требует писать новый интерпретатор.

Truffle (GraalVM) - интерпретатор пишется на Java с аннотациями Truffle. GraalVM выполняет его частичное вычисление (partial evaluation) и компилирует в оптимизированный машинный код. Этот подход ближе к частичным вычислениям, чем к классическому метатрейсингу, но даёт схожие результаты.

Обе системы создают отличные JIT-компиляторы, но требуют начинать с нуля. Нельзя просто взять существующий CPython или PUC Lua и добавить в них метатрейсинг.

yk: метатрейсинг для C

yk применяет метатрейсинг напрямую к интерпретаторам на C. Проект использует модифицированный LLVM (ykllvm) для инструментирования интерпретатора записью трейсов. Добавляем около 400 строк кода в PUC Lua - и получаем JIT.

Преимущество: полная совместимость с эталонными реализациями. Недостаток: семантика C усложняет некоторые оптимизации по сравнению с RPython или Truffle.

Подробнее о реализации - в retrofitting-jit-c-interpreters.