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

x86-64 имеет 16 регистров общего назначения. Типичная функция может иметь 100+ виртуальных регистров. Задача распределения - упаковать 100 в 16 без потери корректности. Это задача раскраски графа - NP-полная в общем случае. Но компиляторы решают её за доли секунды. Как?

• **GCC** с 1993 года использует Chaitin-Briggs graph coloring. Для x86-64 с 16 регистрами граф редко требует spilling в хорошо написанном C коде - но C++ with many local objects может легко перегрузить аллокатор.
• **LLVM Greedy Register Allocator** (используется по умолчанию) объединяет linear scan с локальными эвристиками spill/split. По сравнению с pure graph coloring на SPEC CPU2017: -2% производительность, но в 3x быстрее компилируется.
• **V8 TurboFan** использует linear scan для JIT горячих функций JavaScript. Решение принимается за <1ms на функцию - иначе JIT overhead превысит выигрыш от оптимизации.

Graph Coloring

Распределение регистров через раскраску графа - классический подход Chaitin (1982). Строится interference graph: узлы - виртуальные регистры, рёбра - пары, живые одновременно (interferering). Задача: раскрасить граф K цветами (K = количество физических регистров) так, чтобы смежные узлы имели разные цвета.

Раскраска графа - NP-полная задача в общем случае. Но на практике interference graphs имеют специальную структуру (chordal graphs для некоторых программ) - что делает раскраску полиномиальной. GCC и LLVM используют эвристики: simplification ordering, spill cost based on loop depth. Современный LLVM allocator (PBQP, Greedy) дополнительно использует machine model для оценки стоимости spill.

Liveness Analysis

Liveness analysis - backward dataflow анализ, определяющий в каждой точке программы, какие переменные 'живы' (их значение может быть использовано в будущем). Переменная жива после своего определения и до последнего использования.

LLVM вычисляет liveness через `LiveVariables` и `LiveIntervals` passes. `LiveIntervals` строит интервалы [def, last-use] для каждого виртуального регистра - это более компактная форма чем bitset. GCC использует `df_analyze()`. Liveness информация используется не только для register allocation, но и для dead store elimination и copy propagation.

Linear Scan

Linear Scan Register Allocation - линейный алгоритм распределения регистров за O(N log N). Порядок: сортировать live intervals по началу, жадно назначать регистры, при нехватке - spill наименее приоритетный interval. Используется там где скорость компиляции важнее качества: JIT компиляторы.

HotSpot JVM использовал linear scan для JIT компиляции Java - скорость компиляции критична. LLVM содержит `LinearScanRegisterAllocator` как альтернативу Greedy allocator. V8 TurboFan использует linear scan. Современный вариант - SSA-based linear scan (Wimmer & Franz, 2010) работает непосредственно на SSA-форме и даёт качество ближе к graph coloring при сохранении линейной скорости.

Spilling

Spilling - выгрузка значения из регистра в стек (stack frame) когда не хватает физических регистров. Spill = store + нужные load'ы при каждом использовании. Это снижает производительность - доступ к памяти дороже регистра в 10-100 раз.

Компиляторная оптимизация rematerialization - альтернатива spill: вместо сохранения значения в память, повторно вычислить его когда нужно. Подходит для дешёвых вычислений: `x = 0` (xor self) или `x = small_constant`. LLVM определяет `isReMaterializable()` для каждого класса инструкций. На RISC-V с его 32 регистрами spilling встречается реже, чем на x86-32 с его 8 регистрами.

Итоги

• **Graph coloring**: виртуальные регистры = узлы, interference = рёбра, K цветов = K физических регистров. NP-полная задача, но практически решается за полиномиальное время.
• **Liveness analysis**: backward dataflow определяет, где каждая переменная жива. Основа для построения interference graph.
• **Linear scan**: O(N log N) жадный алгоритм. Быстрый, чуть хуже по качеству. Выбор JIT компиляторов (V8, HotSpot).
• **Spilling**: выгрузка в стек при нехватке регистров. Особенно дорого в циклах. Rematerialization - альтернатива для дешёвых выражений.

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

Распределение регистров - ключевая фаза backend компилятора:

• Глобальные оптимизации — Live variables analysis (dataflow) является входом для register allocator
• Выбор инструкций — Instruction selection происходит перед register allocation - виртуальные регистры создаются здесь
• Планирование инструкций — После register allocation планировщик переставляет инструкции скрывая latency load/store

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

• x86-64 имеет 16 GPR, но некоторые зарезервированы (rsp, rbp). ARM64 имеет 31 GPR. Как наличие большего числа регистров влияет на частоту spilling - и почему это помогает функциональному коду больше чем императивному?
• Register coalescing - объединение двух регистров `a = b` в один физический. Это конфликтует с graph coloring (добавляет ограничение). Как решить этот trade-off?
• JVM managed code требует GC roots map - компилятор должен знать, где именно в регистрах находятся object references. Как это усложняет register allocation по сравнению с нативными языками?

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

• plt-17-memory-models