1. Архитектура современных компиляторов и теория промежуточных представлений (IR)
Архитектура современных компиляторов и теория промежуточных представлений (IR)
Добро пожаловать в курс «Теория оптимизирующих компиляторов». Мы начинаем погружение в одну из самых сложных и увлекательных областей computer science не с написания кода, а с фундаментальной архитектуры. Чтобы понять, как компилятор превращает высокоуровневый код в эффективные машинные инструкции, необходимо разобраться, как он устроен внутри и на каком языке «думает» его оптимизатор.
Проблема и трёхфазная архитектура
Исторически первые компиляторы были монолитными программами. Они читали исходный код и сразу генерировали машинный код для конкретного процессора. Это создавало огромную проблему масштабируемости.
Представьте, что у нас есть языков программирования (C, C++, Fortran, Rust) и целевых архитектур (x86, ARM, RISC-V, MIPS). Если писать отдельный компилятор для каждой пары «язык-архитектура», нам потребуется реализовать компиляторов. Это колоссальный объем работы.
Решением стала трёхфазная архитектура (Three-Phase Design), которая разделяет компилятор на три независимые части:
!Трёхфазная архитектура, позволяющая переиспользовать оптимизатор для разных языков и архитектур
Благодаря введению общего промежуточного представления (Intermediate Representation — IR), сложность разработки снижается кардинально. Математически выигрыш можно выразить так:
где — общая трудоемкость разработки экосистемы, — количество поддерживаемых языков (требуется фронтендов), а — количество архитектур (требуется бэкендов). Вместо умножения мы получаем сложение.
Промежуточное представление (IR): Лингва франка компилятора
IR (Intermediate Representation) — это структура данных или код, который служит интерфейсом между фазами компиляции. Хорошее IR должно быть достаточно выразительным, чтобы сохранить семантику исходной программы, но достаточно низкоуровневым, чтобы оптимизатор мог видеть детали реализации.
Существует несколько уровней IR, которые часто используются совместно:
1. Графовые представления (AST и DAG)
На выходе из парсера мы обычно получаем Абстрактное синтаксическое дерево (AST). Оно идеально повторяет структуру исходного кода, но плохо подходит для оптимизаций, так как скрывает поток управления и поток данных.2. Линейные представления (Трёхадресный код)
Это наиболее популярный формат для оптимизаторов. Он напоминает ассемблер для абстрактной машины с бесконечным количеством регистров. Инструкция обычно имеет вид:где — целевой операнд (куда пишем), — операция, а и — исходные операнды. Именно поэтому код называется «трёхадресным».
3. Граф потока управления (CFG)
Для анализа программы линейный список инструкций разбивают на Базовые блоки (Basic Blocks). Базовый блок — это последовательность инструкций, в которую управление может попасть только через первую инструкцию и выйти только через последнюю. Внутри блока нет ветвлений.Блоки соединяются в Граф потока управления (Control Flow Graph — CFG), где узлы — это базовые блоки, а ребра — возможные переходы между ними.
!Граф потока управления, состоящий из базовых блоков и переходов между ними
SSA-форма: Главный инструмент оптимизатора
В современных компиляторах (таких как LLVM или GCC) используется специальная форма IR, называемая Static Single Assignment (SSA) или статическая форма единственного присваивания.
Ключевое правило SSA звучит просто: каждая переменная присваивается ровно один раз.
Рассмотрим пример обычного кода:
В этом коде переменная x меняет свое значение. Для человека это понятно, но для алгоритма анализа данных это создает сложность: когда мы видим использование x в строке y = x, нам нужно сканировать код назад, чтобы понять, какое именно присваивание актуально.
В SSA-форме мы версионируем переменные:
Теперь связь между определением (x_2) и использованием (y_1) очевидна и неизменна. Это свойство называется ссылочной прозрачностью.
Проблема слияния потоков и -функция
Однако, что делать, если у нас есть ветвление?
В SSA мы создаем версии x_1 и x_2 внутри веток if и else. Но какую версию использовать после выхода из if? Для решения этой проблемы вводится специальная фиктивная инструкция — -функция (Phi-function).
Математически это записывается так:
где:
* — новая версия переменной, объединяющая предыдущие;
* — функция выбора, которая возвращает , если управление пришло из ветки then, и , если из ветки else;
* — версии переменной из предшествующих базовых блоков.
Важно понимать: -функция не является реальной машинной инструкцией. Это теоретическая конструкция для анализатора. На этапе генерации машинного кода (в бэкенде) -функции заменяются на обычные инструкции пересылки данных (move) или просто исчезают благодаря грамотному распределению регистров.
LLVM IR: Промышленный стандарт
Чтобы закрепить теорию, взглянем на LLVM IR — де-факто стандарт в индустрии компиляторов. Это типичный пример линейного IR в SSA-форме.
Пример функции, вычисляющей сумму двух чисел:
Здесь:
* i32 — тип данных (32-битное целое). LLVM IR строго типизирован.
* %a, %b, %sum — виртуальные регистры. Их количество бесконечно.
* add — инструкция трёхадресного кода.
Если мы добавим условие, появятся метки базовых блоков и -узлы:
Обратите внимание на инструкцию phi. Она явно говорит: «Если мы пришли из блока %then, то результат равен %a. Если из %else, то %b».
Зачем нам всё это?
Использование SSA и графов потока управления позволяет сводить сложные задачи оптимизации к задачам на графах. Например:
В следующих статьях мы будем детально разбирать, как именно работают эти алгоритмы на базе представленной сегодня теории.