Компиляторы
Выбор инструкций
Одно деление на 3 в C. GCC с -O1 генерирует 5 инструкций умножения и сдвигов вместо медленного idiv. Это не хак - это математически точный эквивалент, найденный алгоритмом выбора инструкций. Выбор правильных машинных инструкций для каждой IR-операции может дать 10-20x разницу в скорости.
- **LLVM SelectionDAG** содержит тысячи паттернов для каждой архитектуры в `.td` файлах. Только для x86 - более 3000 паттернов в `X86InstrSSE.td`. TableGen генерирует C++ код матчера автоматически.
- **GCC** при компиляции с -O2 применяет magic number division для всех константных делителей. Это автоматическая суперoптимизация встроенная в компилятор через алгоритм из книги Hacker's Delight.
- **LLVM GlobalISel** - новый framework для instruction selection, работающий на глобальном SSA-IR. Используется в AArch64 backend по умолчанию и даёт на 10-15% быстрее компиляцию по сравнению с SelectionDAG при сравнимом качестве кода.
Tree Pattern Matching
Выбор инструкций - отображение IR-операций на машинные инструкции целевой архитектуры. Задача: покрыть дерево выражений (expression tree) паттернами машинных инструкций с минимальной стоимостью. Одна машинная инструкция может покрывать несколько IR-операций.
LLVM SelectionDAG реализует выбор инструкций через таблицы паттернов, генерируемые из `.td` файлов (TableGen). Для x86 это `X86InstrArith.td`, `X86InstrControl.td` и другие - тысячи паттернов. GCC использует RTL (Register Transfer Language) и DEFINE_INSN patterns в machine description файлах. Автоматически генерируемые matchers обрабатывают тысячи комбинаций быстрее ручного кода.
Почему одна машинная инструкция может покрывать несколько IR-операций?
DAG Covering
SelectionDAG (Directed Acyclic Graph) - обобщение дерева для instruction selection. В DAG узлы могут иметь несколько пользователей (shared values). Это важно: если выражение используется дважды, его нужно вычислить один раз и результат переиспользовать.
LLVM SelectionDAG - центральная структура данных backend'а LLVM. Каждый узел - SDNode с результатом, операцией и цепочкой (для ordering side effects). SelectionDAGISel.cpp - один из крупнейших файлов LLVM (~3000 строк). GlobalISel - новый подход LLVM: instruction selection на уровне глобального SSA-IR без промежуточного DAG. GlobalISel быстрее для JIT, SelectionDAG даёт лучший код.
Почему instruction selection работает с DAG, а не просто деревом?
Maximal Munch
Maximal munch - жадный алгоритм выбора инструкций: покрыть дерево снизу вверх, на каждом шаге выбирая самый большой подходящий паттерн. Не даёт оптимального результата, но прост и быстр. Оптимальный алгоритм - dynamic programming.
Алгоритм Aho-Johnson (1976) - оптимальное tree matching за O(N) через dynamic programming. На каждом узле вычисляется минимальная стоимость покрытия поддерева для каждого non-terminal. LLVM сначала пытался maximal munch, потом перешёл на DP через TableGen-generated matchers. Для большинства программ разница <5% но на некоторых горячих путях критична.
Когда maximal munch даёт неоптимальный результат?
Superoptimization
Superoptimization - поиск абсолютно оптимальной последовательности инструкций для заданного вычисления, часто перебором или с помощью SMT-решателей. Применяется офлайн для critical code paths и встроенных функций стандартных библиотек.
Alive2 - formal verification tool для LLVM оптимизаций на основе SMT (Z3 solver). Проверяет корректность peephole оптимизаций: не меняют ли они семантику. Нашёл несколько bugs в LLVM InstCombine, которые генерировали неправильный код. Superoptimizer Souper (Google) использует LLVM IR + Z3 для поиска улучшений и автоматически предлагает patches в LLVM.
Почему деление на константу 3 компилируется в умножение на magic number?
Итоги
- **Tree pattern matching** покрывает IR-дерево паттернами машинных инструкций. Одна инструкция может покрывать несколько IR-операций (LEA, составные адресации).
- **SelectionDAG** обрабатывает shared values (узлы с несколькими пользователями) - более реалистичное представление чем дерево.
- **Maximal munch** - жадный алгоритм O(N), не оптимален. **DP (Aho-Johnson)** - оптимален, используется в LLVM и GCC.
- **Суперoптимизация** - поиск абсолютно оптимальных последовательностей. Magic number division - встроенная суперoптимизация в GCC/Clang.
Связанные темы
Выбор инструкций связан со всеми аспектами backend компилятора:
- Распределение регистров — Instruction selection создаёт виртуальные регистры; register allocator маппирует их на физические
- Планирование инструкций — После выбора инструкций планировщик переставляет их для скрытия latency
- Целевые архитектуры — Паттерны instruction selection полностью определяются целевой ISA
Вопросы для размышления
- RISC архитектуры (RISC-V, ARM) имеют ортогональные инструкции - instruction selection проще. CISC (x86) имеет тысячи специализированных паттернов. Что из этого компилируется быстрее - и что генерирует более быстрый код?
- Souper (Google) находит улучшения LLVM InstCombine автоматически через Z3. Почему ручная верификация таких оптимизаций сложна - и что может пойти не так если оптимизация некорректна?
- WASM - stack-based VM. Instruction selection для WASM backend LLVM принципиально отличается от x86. Почему stack machine упрощает instruction selection - и какие новые проблемы создаёт?