Этапы компиляции (кратко, по порядку)
- Лексический анализ (сканер): читает поток символов, группирует токены (идентификаторы, числа, операторы). Выдаёт последовательность токенов.
- Синтаксический анализ (парсер): строит синтаксическое дерево (AST) по грамматике языка; фиксирует синтаксические ошибки.
- Семантический анализ: проверка типов, разрешение имён, проверка присваиваний, инференс типов, построение таблиц символов; при необходимости — ранние трансформации AST.
- Построение промежуточного представления (IR): перевод AST в удобное для оптимизаций представление (например, трёадичные инструкции, трехадресный код, контрольный-граф (CFG) базовых блоков).
- Постобработки/аналитика на IR: построение CFG, анализ достижимости, анализ живости (liveness), определение деф‑юз цепочек (def-use), вычисление доминаторов и т.д.
- Преобразование в SSA (опционально, перед глобальными оптимизациями) — см. ниже.
- Оптимизации на IR: локальные (свертки констант, упрощение выражений), глобальные (мердж, удаление мёртвого кода, константное распространение/копийное распространение), специфичные SSA‑оптимизации.
- Аллокация регистров (обычно на основе интераференц‑графа, после выхода из SSA или с эмуляцией SSA).
- Генерация машинного кода: селекция инструкций, расписание, вставка прологов/эпилогов.
- Ассемблирование и линковка: получение исполняемого файла.
Что такое SSA (Static Single Assignment)
- SSA — это представление, в котором каждая логическая переменная присваивается ровно один раз. Повторные присваивания дают новые версиии переменной $v_0,v_1,v_2,\dots$.
- На месте слияния потоков управления (ветвления/циклы) вводятся $\varphi$-функции, которые выбирают версию переменной в зависимости от предка: например $v_3=\varphi (v_1,v_2)$.
Как строят SSA (алгоритм высокого уровня)
1. Построить CFG (граф базовых блоков).
2. Найти для каждого узла доминаторы и доминирующее дерево; вычислить dominance frontier (DF) для каждой вершины.
3. Для каждой переменной:
- Для каждого узла, где переменная определяется, вставлять $\varphi$-функции в узлы из DF по стандартному алгоритму (worklist на основе DF) до тех пор, пока все места слияния покрыты.
4. Переименование переменных (rename):
- Обойти доминирующее дерево сверху вниз.
- Для каждой определения переменной присвоить новую версию $v_i$ (увеличивая счётчик).
- Заменить все использования на текущую версию из стека/таблицы имён; при входе в блок сохранить/восстановить стеки.
- Это даёт корректные def-use цепочки: каждое использование ссылается на единственное присваивание.
Почему SSA облегчает оптимизации (коротко)
- Явная def-use связь: каждое использование знает, от какой версии пришло значение. Это упрощает анализ постоянства и зависимостей.
- Простота константного распространения и пропагации: если версия имеет константу, все её использования сразу видны.
- Упрощение DCE (удаление мёртвого кода): можно легко найти определения без использований.
- Упрощение общих подвыражений/сопоставления значений (value numbering): уникальность версий уменьшает неоднозначности.
- Лёгкая локализация и перемещение кода (code motion) и скалярная оптимизация.
- Многие оптимизации формулируются как локальные преобразования на графе определений‑использований.
Пример преобразования (простой if)
Исходный код (псевдо‑IR):
x = $0$ if (c) {
x = $1$ }
y = x + $2$
Построим SSA:
- первые определения: $x_0=0$.
- в теле ветки: $x_1=1$.
- в месте слияния вводим $\varphi$: $x_2=\varphi (x_0,x_1)$.
- использование: $y_0=x_2+2$.
Итог в SSA:
x${}_0$ = $0$
(if c) x${}_1$ = $1$
x${}_2$ = $\varphi (x_0,x_1)$
y${}_0$ = x${}_2$ + $2$
Как это помогает оптимизациям (на примере константной пропагации)
- Если компилятор знает, что в одном из входов $\varphi$ значение константа, он может распространить константу на использования, и если обе ветви дают одну и ту же константу — удалить $\varphi$ и заменить $x_2$ на константу, затем удалить лишние определения:
- Если обе ветви дают $0$, тогда $x_2=0$ и $y_0=2$ (после свёртки $0+2$).
- Также благодаря SSA легко заметить, что некоторый $x_i$ не используется и удалить соответствующее присваивание.
Коротко о некоторых технических деталях
- $\varphi$-функции не являются исполняемыми инструкциями; они семантически означают выбор значения в момент входа в блок.
- Возврат из SSA в нормальный код требует удаления $\varphi$-функций: их обычно реализуют через копирования/переименование в предшественниках или в точках входа (вставка move‑инструкций).
- Существуют варианты (partial SSA, pruned SSA) и оптимизации, которые минимизируют количество $\varphi$-функций.
Если нужно, могу показать более сложный пример (с циклом) и пошаговую вставку $\varphi$-функций и переименование.