Генерация кода

Один и тот же алгоритм, написанный одинаково, может работать в 10x быстрее или медленнее - в зависимости от того, насколько умён backend компилятора. Register allocation, instruction selection, scheduling - это то, что превращает абстрактный IR в быстрый нативный код.

• **Rust release builds**: LLVM -O3 с LTO даёт код, конкурентный с оптимизированным C. Без этого Rust debug builds в 10-50x медленнее release
• **Wasmtime**: Cranelift компилирует WebAssembly за ~100ms. Это делает serverless cold start приемлемым. LLVM потребовал бы 1-2s
• **Apple M1 SoC**: ARM backend LLVM оптимизирован Apple для M1. Результат: Clang на M1 компилирует LLVM быстрее, чем Intel Xeon в 2x дороже

Распределение регистров

Распределение регистров - NP-полная задача раскраски графа. Узлы - виртуальные регистры (переменные SSA), рёбра - конфликты (обе переменные живы одновременно). Цель: раскрасить граф в k цветов (физических регистров) с минимальным числом spill'ов в память.

Linear scan register allocation - более быстрый алгоритм O(n log n) vs Chaitin-Briggs O(n^2). JIT компиляторы (JVM, V8) используют linear scan - скорость компиляции важна. AOT (LLVM) может использовать более медленный но качественный Chaitin-Briggs.

Выбор инструкций

Instruction selection - сопоставление IR узлов с инструкциями целевой архитектуры. Одна IR инструкция может отображаться на разные машинные инструкции с разной стоимостью. Tree pattern matching через dynamic programming даёт оптимальное покрытие.

LLVM backend

LLVM (Low Level Virtual Machine) - модульный компилятор infrastructure. Frontend генерирует LLVM IR, LLVM оптимизирует и генерирует нативный код для 30+ архитектур. Rust, Swift, C++ (Clang), Julia, Kotlin Native - всё на LLVM.

LLVM IR типизирован и в SSA форме. nsw/nuw флаги на арифметике - undefined behavior разрешения, которые открывают дополнительные оптимизации. Rust использует это: signed integer overflow = UB (как в C), поэтому LLVM может оптимизировать агрессивнее.

Cranelift

Cranelift - новый code generator, написанный на Rust для Wasmtime и rustc backend. Разработан как альтернатива LLVM с фокусом на скорость компиляции (для JIT) и корректность (для WebAssembly runtime). Использует проверяемо корректный register allocator (regalloc2).

Сравнение LLVM vs Cranelift: LLVM - 60+ оптимизационных проходов, лучший output code, медленная компиляция. Cranelift - минимальные оптимизации, ~10x быстрее компиляция, хуже output code. Выбор: AOT -> LLVM, JIT/debug -> Cranelift.

Итоги

• **Register allocation**: NP-полная раскраска графа конфликтов. Spill в память если регистров не хватает. Linear scan для JIT, Chaitin-Briggs для AOT
• **Instruction selection**: одна IR операция -> оптимальные machine instructions. LEA вместо imul+add. Peephole оптимизации
• **LLVM**: модульная infrastructure. Frontend -> LLVM IR -> 30+ таргетов + 60 оптимизаций. Основа Rust, Swift, Clang, Julia
• **Cranelift**: 10x быстрее LLVM, меньше оптимизаций. Идеален для JIT (Wasmtime) и debug сборок

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

Codegen - финальный этап компилятора:

• IR и оптимизации — Оптимизированный IR поступает на вход codegen
• JIT компиляция — JIT - codegen в runtime, баланс скорости компиляции и качества кода

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

• Register allocation - NP-полная задача, но компиляторы решают её за секунды. Какие эвристики и упрощения делают это возможным на практике?
• LLVM IR содержит флаги nsw/nuw (no signed/unsigned wrap), которые разрешают undefined behavior оптимизации. Как баланс между оптимизируемостью и корректностью влияет на дизайн языка?
• Apple использует LLVM для всего Apple Silicon кода. Насколько глубоко компания может кастомизировать backend под свою микроархитектуру?

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

• fl-18-turing-machine