Когда виртуальная машина компилирует программу, она не преобразует её напрямую из байткода или AST в машинный код. Реализация современных JIT/AOT-компиляторов устроена иначе: они используют промежуточное представление программы - IR (Intermediate Representation). Промежуточное представление - это набор инструкций, графов, блоков, который достаточно далёк от конкретных особенностей аппаратной платформы, но уже достаточно формален для того, чтобы над ним выполнять оптимизации
Промежуточное представление надо превратить в реальный машинный код - набор инструкций процессора с конкретной архитектурой (arm, x86, RISC-V и других). Программа, которая переводит промежуточное представление к конкретному бинарному коду называется бекендом компилятора
Бекенд состоит из нескольких ключевых фаз, каждая из которых решает строго определённую задачу. Чтобы понимать, как компилятор действительно порождает код, нужно разбираться в логике этих фаз:
Высокоуровневое промежуточное представление - это представление программы, свободное от особенностей конкретной машины. Однако на практике даже промежуточное представление создаётся с оглядкой на целевую платформу, например, для упрощенного перевода инструкций под основную архитектуру
Высокоуровневое промежуточное представление:
И именно здесь возникает фундаментальная проблема: в промежуточном представлении значений может быть сотни, а аппаратных регистров - меньше тридцати, например, ARM64 предоставляет 31 регистр общего назначения
В промежуточном представлении легко создать 300 временных значений, но в реальном процессоре такое невозможно
Компилятору требуется понять:
Если некоторая инструкция создала значение A, то это значение имеет время жизни с момента определения до последнего использования. Но, так как программа состоит из блоков, между которыми есть переходы, циклы, ветвления, то нельзя просто определить, в какой момент значение A больше не нужно; нужно понять:
Это приводит к важному определению: значение A живо в точке P, если существует путь от P до какого-либо использования A
Не важно, реальный ли это путь или потенциальный, поэтому говорят, что статическая живость - это приближение реального поведения программы
Настоящий жизненный цикл значения на конкретном запуске может быть короче, но статический анализ обязан учитывать худший случай. Отсюда возникают понятий:
Чтобы анализ живости был возможен, нужно упорядочить базовые блоки графа потока управления в линейную последовательность.
Это не просто список блоков, а порядок, в котором:
Алгоритм расчёта живости работает с конца в начало, а регистровый аллокатор типа линейного сканирования ожидает, что программа развёрнута в линейную последовательность инструкций. Линейная нумерация - это своего рода временная шкала, вдоль которой мы будем измерять жизнь значений
Далее анализ живости выполняется в несколько фаз:
Обход графа потока управления идёт в обратном линейном порядке блоков
Для каждого блока вычисляется набор живых значений (live-set) - множество значений, которые должны быть живы в начале блока.
Набор живых значений блока складывается из:
Вход фи-функции выбирается в зависимости от того, из какого блока пришёл контроль, поэтому значение, необходимое фи-функции, должно быть живо в конце блока-предшественника его ветви
После определения набора живых значений блока каждая инструкция из набора получает живой диапазон, включающий весь блок: [block.begin, block.end)
Теперь внутри блока мы анализируем инструкции, начиная с конца:
Здесь впервые начинает образовываться структура живых интервалов: значения, которые используются позже, живут дольше; значения, которые не используются, постепенно покидают набор живых значений
После полного анализа всех инструкций блока необходимо удалить значения, которые участвуют в фи-инструкциях в этом же блоке, поскольку их жизнь фактически начинается в начале блока, а не продолжается в его конце
Если блок является заголовком цикла, то все значения, находящиеся в наборе живых значений в начале блока, обязаны перекрывать весь цикл. Это означает, что отрезок времени жизни расширяется до [loop_header.begin, loop_end).
Если значение живо во входе цикла и живо в одном из его тел, оно должно быть непрерывно живым для всей кольцевой структуры, чтобы не возникло разрывов, нарушающих моделирование циклического контроля
Этот шаг обеспечивает целостность данных в циклах для любого алгоритма распределения регистров
Теперь, когда мы знаем, где каждое значение живёт, можно распределять регистры.
У процессора мало регистров. Например:
Если бы регистров было 200–300, аллокация регистров не была бы нужна, но добавление регистров дорого само по себе:
Основная цель аллокатора регистров - минимизировать обращения к памяти, то есть вытеснений значений с регистров (spill) и внесений значений (fill)
Тут есть несколько подходов, но самым простым является линейное сканирование (Linear Scan). Линейное сканирование:
Простая версия линейного сканирования выглядит так:
Когда начинается новый интервал:
Самый простой способ выбрать, кого вытеснять - выбрать интервал с максимально дальним концом. Но это приводит к ужасному количеству вытеснений и внесений, потому что алгоритм не смотрит на ближайшее использование значения
Лучше выбирать интервал с самой далёкой следующей точкой использования. Это позволяет:
Ещё одна важная оптимизация: не нужно вытеснять весь интервал целиком, можно разбить его на части. Это радикально уменьшает количество вытеснение и внесение и часто спасает производительность
Выбор стратегии вытеснения должен быть правильным. Если алгоритм выбрал неудачное значение для вытеснения, начинается эффект домино:
Генерация кода - последняя стадия бекенда. Она использует ранее полученные артефакты:
Генерация кода работает так:
Инструкции промежуточного представления преобразуются в инструкции целевой архитектуры, учитывая:
Создаётся метаинформация для виртуальной машины и сборщика мусора:
Стековый фрейм (или фрейм вызова) содержит:
Особенно важно то, что адресация к слотам происходит через регистры sp или fp, поэтому генератор кода обязан аккуратно работать с этими регистрами
Однако, вместо бекенда можно использовать LLVM () - проект программной инфраструктуры для создания компиляторов, однако есть ключевые проблемы: