Компиляторы
LLVM Passes: написание оптимизаций
Компилятор Rust умеет складывать несколько struct fields прямо в CPU регистры не выделяя память на стеке. Google Chrome компилируется с 150+ оптимизационных passes. Каждый pass - это отдельная программа трансформации IR, которую можно написать, отладить и включить в pipeline независимо. LLVM pass infrastructure превращает написание оптимизаций из чёрной магии в инженерную задачу.
- **Rust SROA + InstCombine**: функции принимающие struct по значению часто компилируются без стековых аллокаций - поля struct напрямую передаются в регистрах ABI (System V AMD64 ABI до 6 integer регистров)
- **Google SafeStack**: custom LLVM pass для защиты от stack-based exploits - разделяет безопасные и небезопасные стековые переменные; используется в Chrome renderer process
- **LLVM PGO (Profile-Guided Optimization)**: InstrProfiling pass инструментирует код -> сбор профиля -> OptimizationRemarkEmitter применяет profile к inline/unroll решениям; используется во всех production компиляторах
Function Pass
FunctionPass - наиболее распространённый тип LLVM pass: работает с одной функцией за раз, не видит другие функции модуля. Этот дизайн позволяет параллельно применять pass к разным функциям. Для написания: унаследовать от PassInfoMixin, реализовать метод run(Function&, FunctionAnalysisManager&).
Clang-Tidy checks реализованы как FunctionPass-based анализаторы. Google использует custom LLVM passes в Chromium для profile-guided оптимизаций специфичных для их workload. LLVM Developer Policy: каждый upstream pass должен иметь unit tests через FileCheck (literate testing в .ll файлах).
Что означает возврат `PreservedAnalyses::all()` из LLVM pass?
Module Pass и межпроцедурный анализ
ModulePass видит весь модуль: все функции, глобальные переменные, метаданные. Используется для межпроцедурных оптимизаций: inline (решение об инлайнинге требует видеть callee), dead argument elimination, constant propagation через границы функций. Дороже FunctionPass: не параллелизуется, требует больше памяти.
LLVM inliner - это ModulePass: он строит Call Graph всего модуля и принимает решение об инлайнинге на основе cost model. Heuristics: размер callee, количество call sites, hotness из PGO профиля. Rust использует этот механизм для инлайнинга через crate boundaries при LTO.
Почему LLVM inliner реализован как ModulePass, а не FunctionPass?
Analysis Passes
Analysis pass вычисляет информацию об IR без его изменения. Результаты кешируются PassManager. Ключевые анализы: DominatorTree (доминирование блоков), LoopInfo (структура циклов), ScalarEvolution (инварианты SCEV для индексов), AliasAnalysis (могут ли два указателя указывать на одно место), CallGraph.
AliasAnalysis - самый дорогой и важный анализ: LLVM имеет BasicAA (O(1), на основе типов), TypeBasedAA (TBAA metadata), SCEVAA (для индексов массивов). Ошибочный alias analysis = неверная программа после оптимизации. Поэтому `restrict` в C99 так важен: он даёт компилятору гарантию no-alias, которую AliasAnalysis иначе не может доказать.
Что такое AliasAnalysis и почему он критичен для оптимизаций?
Transformation Passes
Transformation pass изменяет IR используя результаты анализов. Паттерн: запросить анализ -> найти pattern -> применить трансформацию -> обновить анализы. InstCombine - canonical simplifier: x+0->x, (x*2+1)*2->(x+1)*2. SROA (Scalar Replacement of Aggregates) разбивает struct/array на независимые scalars, открывая путь для register allocation.
LLVM Instruction Combiner (InstCombine) применяет ~400 паттернов упрощения алгебраических выражений. Каждый паттерн задаётся через TableGen DSL или C++ код. SROA на практике устраняет 30-50% аллокаций на стеке превращая struct fields в SSA virtual registers. Это критично для Rust: многие struct передаются по значению через stack аллокации.
Чем больше passes в pipeline, тем лучше оптимизирован код
Passes имеют interaction effects: порядок важен, некоторые passes открывают возможности для других. Избыточные passes увеличивают compile time без улучшения кода
LLVM -O2 pipeline тщательно подобран десятилетиями экспериментов. Например, mem2reg должен идти до большинства оптимизаций чтобы создать SSA форму. InstCombine лучше работать после SROA. Произвольный порядок passes = плохие результаты
Почему SROA (Scalar Replacement of Aggregates) важен для производительности?
Итоги
- FunctionPass работает с одной функцией (параллелизуемо); ModulePass видит весь модуль (нужен для inlining, dead function elimination)
- Analysis passes кешируются PassManager; трансформации должны сообщать какие анализы они инвалидировали через PreservedAnalyses
- Transformation паттерн: запросить анализ -> найти IR pattern -> применить replaceAllUsesWith/eraseFromParent -> вернуть PreservedAnalyses
Связанные темы
LLVM Passes - конкретная реализация компиляторных оптимизаций:
- LLVM инфраструктура — LLVM IR и общая архитектура, поверх которой работают passes
- MLIR — MLIR использует аналогичную pass infrastructure но с dialects вместо единого IR
- Тестирование компиляторов — Каждый LLVM pass тестируется через FileCheck и lit - differential testing IR трансформаций
Вопросы для размышления
- LLVM InstCombine применяет ~400 алгебраических упрощений. Как тестируется что каждое упрощение корректно для всех возможных входных значений?
- AliasAnalysis - самый сложный анализ. Что происходит если AliasAnalysis даёт false negative (говорит 'no alias' когда на самом деле alias)? Как это обнаружить?
- Pass ordering имеет значение: mem2reg должен идти до большинства оптимизаций. Как LLVM гарантирует правильный порядок в pipeline без явного перечисления всех зависимостей?