Архитектура компилятора

LLVM содержит 2 миллиона строк кода - больше, чем ядро Linux 1.0. Компиляция Hello World через GCC запускает более 200 optimization passes. За каждым `-O2` флагом - десятилетия исследований в теории графов и NP-полных задач. Но самое интересное: вся эта сложность организована по одному принципу - один pass, одна задача, изолировано и тестируемо.

• **Уровни оптимизации:** `-O0` для быстрой отладки, `-O2` для production, `-Os` для embedded (минимальный размер) - каждый включает свой набор passes
• **LLVM passes для всех:** один и тот же набор оптимизаций работает для C (Clang), Rust, Swift, Julia - написал frontend, получил оптимизации бесплатно
• **Время компиляции как UX:** Go компилирует мгновенно (мало passes), Rust - минутами (borrow checker + 200 LLVM passes). Оба подхода имеют свои use cases

Рождение LLVM: когда PhD-проект изменил индустрию

2000 год, университет Иллинойса. Крис Латнер начинает PhD с идеей: что если IR компилятора будет достаточно низкоуровневым для оптимизаций, но достаточно высокоуровневым для анализа? Результат - LLVM (Low Level Virtual Machine). В 2005 году Apple нанимает Латнера, чтобы переписать на LLVM весь компилятор Mac OS X. Сегодня LLVM - основа Clang, Swift, Rust, CUDA, Halide, Julia и десятков других компиляторов. Один PhD проект, одна архитектурная идея - passes через IR - изменил весь компиляторный ландшафт.

Предварительные знания

• How a Computer Reads Code

Passes: один шаг - одна задача

2012 год. Команда Rust начинает рефакторинг компилятора. Проблема не в алгоритмах - в архитектуре: оптимизации перепутаны с кодогенерацией, тестировать отдельно невозможно. Решение - разбить всё на **passes**. Каждый pass получает IR, делает ровно одно преобразование, отдаёт дальше. Сейчас rustc содержит сотни изолированных passes - и каждый тестируется независимо.

Pass - изолированный модуль компилятора. Constant Folding не знает про Register Allocation. Inlining не знает про Loop Unrolling. Это не случайность - это архитектурное решение: один pass, одна задача, одна ответственность.

LLVM содержит более **200 различных passes**. Набор зависит от уровня оптимизации: `-O0` (без оптимизации, быстрая компиляция), `-O2` (стандартные оптимизации), `-O3` (агрессивные оптимизации, может увеличить размер кода).

Посмотреть, какие passes запускает LLVM: `clang -O2 -mllvm -debug-pass=Structure file.c`. Для Rust: `RUSTFLAGS="-C llvm-args=-debug-pass=Structure" cargo build`.

Pipeline и Intermediate Representation

Passes соединяются в **pipeline** - конвейер. Между ними данные передаются через **IR (Intermediate Representation)** - промежуточное представление, не привязанное ни к исходному языку, ни к целевой платформе. IR - это lingua franca внутри компилятора. LLVM IR понимают фронтенды C, Rust, Swift, Julia - один общий язык для всех.

Самая важная форма IR в современных компиляторах - **SSA (Static Single Assignment)**. Правило: каждой переменной значение присваивается **ровно один раз**. Если нужно изменить переменную - создаётся новая версия. Это не ограничение - это инструмент: каждый анализ мгновенно видит, откуда пришло значение.

**3-address code** - другая популярная форма IR: каждая инструкция содержит максимум 3 операнда. `a = b + c * d` превращается в `t1 = c * d; a = b + t1`. Промежуточные значения хранятся во временных переменных.

Не путайте IR и AST. AST - высокоуровневое представление, привязанное к синтаксису языка (ветки для `if`, `while`, `for`). IR - низкоуровневое, ближе к машинному коду (ветвления - `br`, `goto`; циклы - метки и переходы). Компилятор «опускает» (lowers) AST в IR.

Multi-pass компиляция

GCC при `-O2` выполняет около 200 проходов. LLVM - около 150. Это не «сложно ради сложности» - это архитектура, которая держит индустрию 40 лет. Каждый pass делает маленькое, хорошо определённое преобразование. Один pass не может сломать другой - они изолированы.

**Преимущества multi-pass:**

Порядок passes имеет значение. **Inlining** перед **Constant Folding** - эффективнее, потому что после вставки тела функции появляются новые константные выражения. LLVM автоматически подбирает оптимальный порядок для каждого уровня `-O`.

Single-pass: быстро, но с ограничениями

1960-70-е. Память - катастрофический дефицит: 64 КБ роскошь. Хранить полное AST или IR программы невозможно. Решение - **single-pass** компилятор: читает исходный код один раз, слева направо, сразу генерирует машинный код. Без промежуточных представлений. Ограничения языка - прямое следствие ограничений железа.

**Pascal** (1970) и **ранний C** (1972) спроектированы специально для single-pass компиляции. В Pascal нельзя вызвать функцию, объявленную ниже. В C - нужны **forward declarations** и header files.

Go спроектирован с учётом скорости компиляции: пакеты компилируются параллельно, нет circular dependencies, нет header files. Результат: Go компилирует проект из миллионов строк за секунды, пока Rust и C++ тратят минуты. Сознательный trade-off между глубиной оптимизации и скоростью разработки.

Не путайте количество passes с качеством кода! Rust компилируется медленно (сотни passes + borrow checker), но генерирует код, сопоставимый с C. Go компилируется мгновенно (меньше passes), но производительность runtime на 10-30% ниже. Выбор - trade-off между compile time и runtime performance.

Ключевые идеи

• **Pass** - один модуль компилятора, выполняющий одно преобразование. Constant folding, dead code elimination, register allocation - каждый pass изолирован и тестируем
• **Pipeline** - цепочка passes, связанных через **IR** (промежуточное представление). **SSA-форма** (каждая переменная присваивается один раз) упрощает анализ и оптимизации
• **Multi-pass** (GCC, LLVM, Rust) - модульность, глубокие оптимизации, но медленная компиляция. **Single-pass** (Pascal, ранний C) - мгновенная компиляция, но ограниченная оптимизация и forward declarations
• Больше passes не значит лучше: `-O3` может быть медленнее `-O2` из-за увеличения размера кода и давления на CPU cache

Связанные темы

Архитектура компилятора - основа для понимания каждой его части. Дальше разбираются отдельные фазы:

• Лексический анализ (Lexer) — Первый pass в pipeline: символы - токены. Реализация через DFA и regex
• Intermediate Representation — LLVM IR, SSA, CFG и формы IR подробно
• LLVM: введение — Практика: как работать с LLVM passes, писать свои оптимизации

Вопросы для размышления

• Go компилируется в 100x быстрее Rust, но генерирует на 10-30% более медленный код. Какой trade-off оптимален для web-сервера? Для embedded системы? Для CLI утилиты?
• Если один pass создаёт возможности для другого (inlining -> constant folding), то теоретически можно запускать passes бесконечно. Как компилятор решает, когда остановиться?
• SSA-форма требует phi-функций для ветвлений. Как это влияет на размер IR по сравнению с обычным представлением? Стоит ли overhead?

Связанные уроки

• comp-21-ir — Архитектура passes ведёт к глубокому изучению LLVM IR и SSA
• comp-22-ssa — SSA-форма - центральный инструмент pipeline, разобранного здесь
• comp-06-lexer-basics — Лексер - первый pass в pipeline, фундамент архитектуры
• comp-41-llvm-intro — LLVM - промышленная реализация multi-pass архитектуры
• comp-23-local-optimization — Constant folding и DCE - частные случаи pass-архитектуры
• alg-01 — Анализ сложности passes требует базовых алгоритмических знаний
• fl-01-intro