Компиляторы
Локальные оптимизации
Программист пишет `2 * 3 + 4`. Компилятор даже не генерирует код для этого - просто подставляет `10`. Или пишет `x * 8` - получает сдвиг. Локальные оптимизации невидимы для пользователя, но работают на каждой строчке кода. Именно они превращают читаемый высокоуровневый код в быстрый машинный.
- **LLVM InstCombine** - pass, выполняющий тысячи мелких algebraic simplifications: `x + 0 -> x`, `x * 1 -> x`, `(x + 1) - 1 -> x`. Файл `InstructionCombining.cpp` в LLVM содержит более 6000 строк только паттернов упрощений.
- **GCC** при компиляции SQLite с -O2 применяет constant folding к hash-функциям, CSE к повторяющимся вычислениям индексов, и strength reduction к умножениям в B-tree traversal. Результат: 15-20% ускорение по сравнению с -O0.
- **Rust** применяет локальные оптимизации на уровне MIR до LLVM, что позволяет оптимизировать generic код до монорфизации - экономит время компиляции для кода с множеством инстанций.
Constant Folding
Constant folding - вычисление константных выражений во время компиляции. Если все операнды операции известны статически, результат вычисляется компилятором и встраивается как литерал. Это устраняет runtime-вычисления без изменения семантики.
GCC применяет constant folding даже на -O0 через `fold_build2()` в `fold-const.cc`. LLVM делает это в `ConstantFoldInstruction()` и `InstSimplify` pass. Rust применяет constant folding через MIRI ещё до LLVM - в фазе MIR optimization. Результат: `[0u8; 64 * 1024]` не генерирует цикл инициализации, а встраивается как константный блок памяти.
Constant folding вычисляет `2 * 3` при компиляции. Может ли оно вычислить `x * 3` где `x` - параметр функции?
Dead Code Elimination
Dead Code Elimination (DCE) - удаление кода, результат которого никогда не используется. В SSA-форме это элементарно: если у инструкции нет uses (пользователей её результата) - инструкция мёртвая. ADCE (Aggressive DCE) также удаляет недостижимые basic blocks.
ADCE (Aggressive DCE) в LLVM удаляет блоки, постдоминирование которых не нужно. Это важно после других оптимизаций: constant folding может сделать условие всегда true/false, ADCE удалит недостижимую ветку, что откроет новые возможности для constant folding. Такая цепочка оптимизаций - норма: LLVM запускает `instcombine -> simplifycfg -> instcombine -> ...` в цикле до фиксированной точки.
Почему DCE в SSA-форме проще, чем в обычном IR?
Common Subexpression Elimination
Common Subexpression Elimination (CSE) - замена повторных вычислений одного и того же выражения ссылкой на уже вычисленный результат. Если `a + b` вычисляется дважды в одном блоке и `a`, `b` не меняются между вычислениями - второе вычисление заменяется копией результата первого.
PRE (Partial Redundancy Elimination) - обобщение CSE, которое устраняет вычисления, дублирующиеся только на некоторых путях. Если `a + b` вычисляется в одной ветке if-else но не в другой - PRE добавляет вычисление в недостающую ветку и выносит результат в phi. Это может казаться контринтуитивным: добавить код чтобы его убрать. GCC использует PRE по умолчанию при -O2.
Чем GVN отличается от локального CSE?
Strength Reduction
Strength reduction - замена дорогих операций более дешёвыми эквивалентами. Классика: умножение на степень двойки заменяется сдвигом, деление константой заменяется умножением на обратное, возведение в степень разворачивается.
Современные x86 процессоры имеют быстрые умножители (3-4 такта), поэтому strength reduction актуально не для всех архитектур. Компилятор знает latency целевой архитектуры через machine description. LLVM использует `TargetTransformInfo::getArithmeticInstrCost()` чтобы решить, выгодна ли замена. Для embedded систем (ARM Cortex-M0 без аппаратного умножения) strength reduction даёт 10-20x ускорение.
Почему `x / 8` заменяется на `x >> 3` только для беззнакового `x`?
Ключевые идеи
- **Constant folding** вычисляет константные выражения при компиляции. Constant propagation распространяет значения через SSA use-def chains.
- **DCE** удаляет инструкции без uses. В SSA проверка тривиальна - O(1) на инструкцию. ADCE дополнительно удаляет недостижимые блоки.
- **CSE** устраняет повторные вычисления одного выражения. GVN расширяет CSE на весь CFG через value numbering.
- **Strength reduction** заменяет дорогие операции дешёвыми: умножение -> сдвиг, деление -> умножение на обратное. Актуальность зависит от архитектуры.
Связанные темы
Локальные оптимизации взаимодействуют и открывают возможности для глобальных:
- SSA-форма — SSA делает constant propagation и DCE тривиальными через явные use-def chains
- Глобальные оптимизации — Локальные оптимизации часто открывают возможности для глобальных - цепочки оптимизаций запускаются итеративно
- Оптимизации циклов — Loop strength reduction - частный случай, важный для вычислительно интенсивного кода
Вопросы для размышления
- LLVM запускает instcombine -> simplifycfg в цикле до фиксированной точки. Почему одного прохода недостаточно - что открывает каждая итерация?
- Strength reduction заменяет `x * 7` на `(x << 3) - x`. На современном x86 с задержкой `imul` в 3 такта и `shl+sub` в 2 такта - всегда ли это оптимально? Что ещё нужно учесть?
- CSE предполагает, что выражение без side effects. Как компилятор определяет, есть ли у функции side effects - и что происходит, если функция читает глобальную переменную?