Теория языков программирования
Промежуточное представление и оптимизации
Ваш код на Rust или C++ может быть в 10-50 раз быстрее написанного в лоб - благодаря SSA и оптимизациям в LLVM. Компилятор видит всю программу целиком и применяет трансформации, которые человек никогда не написал бы вручную.
- **LLVM**: 60+ оптимизационных проходов на SSA IR. Clang с -O2 выдаёт код в 5-10x быстрее -O0 для числодробилок
- **V8 TurboFan**: JIT компилятор JavaScript использует Sea of Nodes IR (вариант SSA). Горячие функции оптимизируются в 100x быстрее интерпретатора
- **GHC**: Haskell компилятор делает 10+ оптимизационных проходов на Core IR (typed lambda calculus в SSA стиле). Fusion elimination устраняет промежуточные структуры данных
SSA форма
SSA (Static Single Assignment) - промежуточное представление, где каждая переменная определяется ровно один раз. При слиянии путей исполнения используется phi-функция. SSA упрощает большинство оптимизаций - нетрудно заметить def-use цепочки.
LLVM IR - SSA форма с типами. GCC GIMPLE - другая SSA-based IR. Все современные оптимизирующие компиляторы используют SSA. Cranelift (Rust's WebAssembly backend) тоже SSA-based.
Зачем в SSA нужна phi-функция?
Control Flow Graph
CFG (Control Flow Graph) - граф, где узлы - базовые блоки (straight-line code без ветвлений), рёбра - переходы управления (jump, branch, call). CFG + SSA = основа большинства оптимизаций в LLVM.
Dominance - BB A доминирует BB B, если все пути от entry к B проходят через A. Dominance tree - ключевая структура для SSA построения и оптимизаций. Loop detection через back edges в CFG.
Что такое базовый блок в CFG?
Dead Code Elimination
Dead code elimination (DCE) - удаление кода, результат которого никогда не используется. В SSA это легко: если у переменной нет uses (пустая use-chain) - определяющая инструкция мертва. Итерируем до фиксированной точки.
Tree shaking в webpack/rollup - DCE для JavaScript. Инструмент анализирует import/export граф и удаляет неиспользуемые модули. Lodash tree shaking экономит 70% размера бандла.
Почему DCE проще выполнять на SSA форме, чем на обычном коде?
Constant Folding и Propagation
Constant folding - вычисление выражений с константами во время компиляции. Constant propagation - замена переменных с известным константным значением на это значение. Вместе они часто открывают возможности для DCE.
Как constant folding и DCE работают вместе?
Inlining функций
Inlining - замена вызова функции её телом в месте вызова. Устраняет overhead вызова (push args, call, ret), открывает cross-function оптимизации (constant folding через границы функций). Главная оптимизация для производительности.
Больше оптимизаций = всегда быстрее. -O3 всегда лучше -O2
-O3 включает агрессивный inlining и vectorization - иногда хуже из-за code bloat и I-cache pressure
SQLite намеренно компилируется с -O2: при -O3 хуже cache locality для OLTP паттернов. Профилирование всегда важнее эвристик
Почему нельзя inline'ить все функции?
Итоги
- **SSA**: каждая переменная определяется один раз. phi-функция на точках слияния. Упрощает def-use анализ
- **CFG**: граф базовых блоков и переходов. Dominance tree - основа SSA построения и loop detection
- **DCE**: пустая use-chain -> инструкция мертва. Удаление unreachable blocks
- **Constant folding + propagation** -> открывает DCE. **Inlining** -> cross-function оптимизации, но осторожно с code bloat
Связанные темы
IR и оптимизации - центр backend пайплайна:
- AST — Из AST генерируется IR для оптимизаций
- Генерация кода — После оптимизаций IR превращается в машинный код
Вопросы для размышления
- Rust гарантирует zero-cost abstractions. Как SSA + inlining делают это возможным для итераторов - почему chain().filter().map() не медленнее ручного цикла?
- JIT компиляторы (V8, JVM HotSpot) применяют speculative inlining: инлайнят предполагаемый тип, добавляют deoptimization guard. Когда это лучше статического инлайнинга?
- Profile-Guided Optimization даёт +10-20% к реальному коду. Почему компилятор без профиля принимает субоптимальные решения?