TurboFan: оптимизатор на море узлов

Почему граф, а не список операторов

Традиционный компилятор моделирует функцию как граф потока управления (CFG) из базовых блоков, каждый — фиксированная последовательность операторов. Порядок зашит с самого начала: оператор 3 идёт после оператора 2, потому что вы так написали. Чтобы перенести вычисление, такой компилятор должен доказать законность переноса относительно этого навязанного порядка.

TurboFan переворачивает это. Его IR — это граф «море узлов» (sea-of-nodes), где узел — это операция, а рёбра — не исходный порядок — кодируют каждое ограничение, которое реально важно. Понятия «порядок инструкций» нет до самого конца. Граф несёт три вида рёбер:

• Рёбра значений (зависимости по данным): у subtract есть рёбра значений к двум загрузкам, которые он потребляет. Это говорит «мне нужны эти входы», и ничего о том, когда.
• Рёбра эффектов (порядок наблюдаемых побочных эффектов): запись, вызов, который может изменить состояние, загрузка свойства, способная вызвать getter, — они сцеплены в цепочку эффектов, чтобы их относительный порядок сохранялся. Чистые операции (арифметика над известными числами) не несут ребра эффекта и свободно плавают.
• Рёбра управления (ветвления, слияния, циклы): скелет из if/loop/return, решающий, какие узлы вообще исполнятся.

Поскольку у чистого вычитания есть только рёбра значений и нет ограничений по эффекту или управлению, планировщик (поздняя фаза) может разместить его где угодно, где доступны его входы — включая вынос из цикла, если его входы инвариантны относительно цикла. Это и имеет в виду mrale.ph под «планировщик размещает вычисления поздно»: у узлов нет фиксированного дома до планирования, и оно назначает самый дешёвый законный.

Конвейер фаз

Зачем важен порядок проходов? Передние фазы могут свободно переписывать граф — как только вы фиксируете машинные инструкции, переписывание слишком дорого. TurboFan — это последовательность хорошо определённых проходов над этим графом. Форма, по порядку:

Построение графа превращает байт-код в начальный граф «море узлов», прикрепляя наблюдения из feedback vector, чтобы поздние фазы знали спекулируемые типы. Типизация и типизированное понижение распространяют типы по графу (+ двух узлов типа SignedSmall типизируется как число в известном диапазоне) и заменяют абстрактные операции на специализированные по типу — обобщённый JSAdd становится NumberAdd, затем потенциально Int32Add.

Затем проходы оптимизации переписывают граф:

• Инлайнинг — узел вызова, чья обратная связь называет небольшую известную цель, заменяется копией графа вызываемого, вплетая его рёбра значений и эффектов в вызывающего. Это то, что разблокирует межфункциональную оптимизацию; без него каждый вызов — непрозрачный эффект.
• Escape-анализ со скалярной заменой — объект, чья ссылка никогда не покидает функцию (подробно в уроке 04), теряет свою аллокацию, а его поля превращаются в обычные узлы графа (регистры), устраняя аллокацию в куче и давление на GC.
• Устранение загрузок/сохранений — загрузка, которая обязана прочитать только что сохранённое значение, заменяется самим сохранённым значением; сохранение, перезаписанное до любого чтения, удаляется.
• Устранение избыточности и свёртка констант — CheckMaps, который уже доказан доминирующим CheckMaps, удаляется; 2 * 3 становится 6; ветка по заведомо истинному условию схлопывается.
• Выбор представления — решает машинное представление каждого значения: тегированный указатель, 32-битное целое в регистре или 64-битный float в FP-регистре, вставляя преобразования только там, где граница представления реально пересекается.

Планирование — это фаза, которая наконец назначает узлы базовым блокам и порядок внутри них — размещая чистые узлы так поздно и так вне-циклово, как законно. Выбор инструкций сопоставляет паттерны графа машинным инструкциям целевой ISA. Аллокация регистров (TurboFan использует продвинутый аллокатор, а не линейное сканирование, как Maglev) назначает физические регистры и вставляет сбросы (spills). Генерация кода выпускает финальные байты. На выходе — блоб нативного машинного кода, установленный на функцию.

Где он работает и как его инспектировать

TurboFan компилирует на фоновом потоке (параллельная компиляция, урок 01): главный поток продолжает исполнять функцию на её текущем ярусе, а оптимизированный код подменяется, когда готов. Это источник самой частой ментальной ошибки о нём (см. ниже). Чтобы инспектировать граф, --trace-turbo дампит IR на каждой фазе в файлы, которые можно открыть в визуализаторе Turbolizer; --trace-opt логирует решения более высокого уровня. mrale.ph и посты v8.dev/blog — канонические глубокие референсы по графу и его фазам.