Глобальные оптимизации

GCC с флагом -O3 применяет 50+ оптимизационных passes к коду. Локальные оптимизации работают внутри одного блока - но глобальные видят весь граф функции и межпроцедурный граф. Это позволяет LLVM ускорить NumPy на 2-5x просто изменив флаги компиляции - без изменения кода.

• **LLVM с Profile-Guided Optimization (PGO)** использует профиль реального выполнения для LICM и inlining: горячие функции инлайнятся агрессивно, холодные - нет. Chrome компилируется с PGO и получает 5-10% ускорение по сравнению с -O2.
• **Rust** использует alias analysis неявно через borrow checker: компилятор знает, что mutable reference уникальна, и применяет оптимизации, недоступные для C с указателями. LLVM получает `noalias` аннотации для всех `&mut` параметров.
• **MLGO (Machine Learning Guided Optimization)** в LLVM - нейросеть для принятия решений об inlining. Google опубликовал результаты: +1.5% throughput Chrome, -0.5% размер бинарника. Модель обучена на корпусе production кода.

Dataflow Analysis

Dataflow analysis - семейство алгоритмов для сбора информации о значениях переменных вдоль путей в CFG. Информация распространяется от блока к блоку через уравнения передачи (transfer functions) до достижения фиксированной точки.

Сходимость dataflow анализа гарантирована если решётка конечна и transfer functions монотонны. LLVM реализует инфраструктуру dataflow в `DataFlowSanitizer` и в отдельных passes. GCC имеет `df_analyze()` - единый фреймворк для reaching definitions, live variables и других анализов. Время сходимости: O(N * D) итераций где D - глубина вложенности циклов.

Loop Invariant Code Motion

Loop Invariant Code Motion (LICM) - вынос из цикла вычислений, результат которых не меняется от итерации к итерации. Если выражение внутри цикла не зависит от переменных, изменяемых в цикле, его можно вычислить один раз до цикла.

LICM в LLVM (pass `LICM`) использует alias analysis чтобы определить, не изменяет ли тело цикла значение, читаемое в потенциальном инварианте. Если `sin(angle)` может быть alias с изменяемой памятью - LICM не вынесет. На практике это редкость. JVM HotSpot JIT делает LICM особенно агрессивно - даже `arr.length` выносится из цикла как инвариант после доказательства неизменности ссылки.

Function Inlining

Function inlining - подстановка тела функции на место вызова. Устраняет overhead вызова (push args, call, pop), но главное - открывает возможности для других оптимизаций: constant propagation через границу функции, LICM, CSE.

LLVM с 2020 года поддерживает MLGO (Machine Learning Guided Optimization) для inlining: нейросеть принимает решение о каждом вызове на основе 47 признаков (размер функции, количество пользователей, профильные данные). Google сообщил об ускорении Chrome на 1.5% и уменьшении размера бинарника на 0.5% по сравнению с эвристическим inlining. Rust использует `#[inline]`, `#[inline(always)]`, `#[inline(never)]` для явного управления.

Alias Analysis

Alias analysis определяет, могут ли два указателя обращаться к одной и той же области памяти. Это критично для оптимизаций: нельзя переставлять нагрузку и сохранение если они могут касаться одной памяти. Консервативный анализ предполагает aliasing везде и блокирует оптимизации.

Strict aliasing rule в C/C++: указатели разных типов не могут алиасить (за исключением char*). GCC с `-O2` использует это для TBAA оптимизаций. Знаменитый баг: `*(int*)float_ptr` - undefined behaviour по strict aliasing, компилятор вправе оптимизировать предполагая aliasing нет. Корректный способ: `memcpy` или `__attribute__((may_alias))`. В Rust нет C aliasing - borrow checker гарантирует отсутствие mutable aliasing статически.

Ключевые идеи

• **Dataflow analysis** распространяет информацию о значениях вдоль CFG до фиксированной точки. Forward (reaching defs) и backward (live vars) - основные направления.
• **LICM** выносит loop-invariant вычисления из тела цикла. Требует доказательства инвариантности всех операндов. `volatile` - абсолютный запрет.
• **Inlining** подставляет тело функции и открывает возможности для cross-function оптимизаций. Агрессивный inlining может вызвать code bloat и падение производительности.
• **Alias analysis** определяет, могут ли указатели обращаться к одной памяти. Консервативный анализ блокирует оптимизации. `restrict`, TBAA, Rust borrow checker - способы дать компилятору больше информации.

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

Глобальные оптимизации работают на IR и открывают возможности для последующих фаз:

• Локальные оптимизации — Глобальные оптимизации часто открывают возможности для повторного прохода локальных
• Оптимизации циклов — LICM - часть семейства loop оптимизаций; dataflow анализ используется для loop analysis
• Распределение регистров — Live variable analysis (dataflow) является входом для register allocator

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

• Dataflow analysis сходится к фиксированной точке. Может ли существовать программа, для которой сходимость не достигается? Что гарантирует завершение?
• Rust borrow checker статически гарантирует отсутствие mutable aliasing. Это позволяет LLVM применять `noalias` для всех `&mut`. Насколько это ускоряет код по сравнению с эквивалентным C кодом без `restrict`?
• PGO (Profile-Guided Optimization) требует сначала запустить программу, собрать профиль, потом перекомпилировать. Какие ситуации делают PGO неприменимым или ненадёжным?

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

• alg-21-dp