1. Промежуточные представления (IR) и форма статического единственного присваивания (SSA)
Промежуточные представления (IR) и форма статического единственного присваивания (SSA)
Компилятор — это не просто черный ящик, который превращает исходный код в исполняемый файл. Это сложная инженерная система, состоящая из множества этапов трансформации данных. Чтобы эффективно анализировать и оптимизировать код, компиляторы используют специальные структуры данных, называемые промежуточными представлениями (Intermediate Representation, IR).
В этой статье мы разберем, почему современным компиляторам недостаточно простого абстрактного синтаксического дерева (AST), зачем нужен трехадресный код и как форма статического единственного присваивания (SSA) совершила революцию в теории оптимизации.
Архитектура современного компилятора
Традиционно архитектуру компилятора делят на три большие части:
!Классическая трехфазная архитектура компилятора
Такое разделение решает фундаментальную проблему масштабируемости, известную как проблема . Если у нас есть языков программирования и целевых архитектур процессоров, то без общего IR нам пришлось бы писать компиляторов (для каждого языка под каждый процессор).
Использование общего IR меняет формулу сложности:
где — количество фронтендов (языков), а — количество бэкендов (архитектур). Достаточно написать один фронтенд для нового языка, чтобы он сразу заработал на всех архитектурах, поддерживаемых бэкендом.
Виды промежуточных представлений
IR бывает разным в зависимости от целей. Обычно выделяют три уровня:
* Высокоуровневое IR (HIR): Сохраняет структуру исходного языка (циклы for, while, структуры). Примером служит AST (Абстрактное синтаксическое дерево).
* Среднеуровневое IR (MIR): Теряет синтаксический сахар, превращая циклы в переходы (goto), но сохраняет типы данных и бесконечное количество виртуальных регистров. Именно здесь работает большинство оптимизаций.
* Низкоуровневое IR (LIR): Максимально близко к ассемблеру. Виртуальные регистры заменяются на физические, учитываются особенности конкретного процессора.
Трехадресный код (Three-Address Code)
Стандартом де-факто для оптимизаций является трехадресный код. Это формат, в котором каждая инструкция имеет не более трех операндов: один для результата и два для аргументов.
Пример выражения на языке высокого уровня:
В трехадресном коде это выражение разбивается на атомарные операции с использованием временных переменных:
Здесь t1 и t2 — это временные переменные (виртуальные регистры). Такая структура упрощает анализ, так как компилятору не нужно обходить сложные деревья выражений; он работает с плоским списком простых инструкций.
Проблема анализа потока данных
Представьте, что вы пишете оптимизатор, который должен заменить использование переменной на константу (Constant Propagation). Рассмотрим код:
Какое значение попадет в y? Очевидно, что 2. Но для компьютера это неочевидно. Чтобы понять это, компилятор должен просканировать весь код и найти последнее присваивание x перед его использованием. Если код содержит ветвления и циклы, задача становится крайне сложной. Переменная x меняет свое значение в разных местах, и отслеживать ее актуальное состояние — ресурсоемкая задача.
Здесь на сцену выходит SSA.
Static Single Assignment (SSA)
Форма статического единственного присваивания (SSA) — это свойство промежуточного представления, которое требует, чтобы каждой переменной значение присваивалось ровно один раз.
Как это возможно, если в программировании переменные постоянно меняются? Мы используем версионирование. Вместо того чтобы перезаписывать x, мы создаем новую версию переменной (x_1, x_2, x_3) при каждом присваивании.
Преобразуем предыдущий пример в SSA:
Теперь связь между определением и использованием (Def-Use chain) очевидна. В строке 3 используется x_2, и есть только одно место в программе, где x_2 определяется (строка 2). Нам не нужно сканировать код вверх или вниз — связь жестко зафиксирована именем переменной.
-функция (Фи-функция)
Самая большая сложность SSA возникает при ветвлении потока управления (Control Flow). Рассмотрим пример с условием:
Если мы применим версионирование:
В точке слияния потоков (после if/else) мы не знаем, по какому пути пошла программа. Чтобы решить эту проблему, в SSA вводится специальная инструкция: -функция.
Корректный SSA для примера выше:
!Использование Phi-функции в точке слияния потоков управления
Математически это записывается так:
где — новая версия переменной, объединяющая возможные варианты, — специальная функция выбора, а — версии переменной, приходящие из разных путей выполнения.
Важно понимать: -функция не существует в реальном процессоре. Это абстракция для анализатора. На этапе генерации машинного кода (в бэкенде) -функции заменяются на обычные инструкции пересылки данных (move) или просто исчезают благодаря грамотному распределению регистров.
Преимущества SSA для оптимизаций
Переход к SSA делает многие сложные алгоритмы оптимизации тривиальными.
1. Удаление мертвого кода (Dead Code Elimination)
В SSA, если переменная v_1 определена, но нигде не используется (нет инструкций, где она стоит справа), инструкцию v_1 = ... можно смело удалять. В обычном коде пришлось бы проверять, не переопределяется ли переменная позже.
2. Распространение констант (Constant Propagation)
Если мы видим инструкцию x_1 = 5, мы знаем, что x_1 всегда равно 5. Мы можем найти все места использования x_1 и заменить их на число 5.
Пример:
Компилятор видит a_1, заменяет на 5. Видит b_1, заменяет на 10. Получает c_1 = 5 + 10. Вычисляет c_1 = 15. Весь блок кода сворачивается в одну константу.
3. Нумерация значений (Value Numbering)
SSA позволяет легко находить и удалять дублирующиеся вычисления.
Так как a_1 и b_1 никогда не меняются (свойство SSA), то a_1 + b_1 всегда дает один и тот же результат. Компилятор видит, что правые части идентичны, и заменяет код на:
Пример из реального мира: LLVM IR
LLVM — это самый популярный современный фреймворк для создания компиляторов (используется в Clang, Rust, Swift). Его IR полностью построен на SSA.
Вот как выглядит простая функция на C:
А вот её (упрощенное) представление в LLVM IR:
Обратите внимание на инструкцию phi. Она явно говорит: "Если мы пришли из метки %if.then, то результат %a. Если из %if.else, то результат %b".
Итоги
if или в циклах), выбирая правильную версию переменной в зависимости от пути выполнения.