[18.12.2025] Faster Chaitin-like Register Allocation via Grammatical Decompositions of Control-Flow Graphs

[Ruslan Savchenko]

В ближайший четверг (завтра) в 16:30 состоится доклад Кулигиной Маргариты на тему «Faster Chaitin-like Register Allocation via Grammatical Decompositions of Control-Flow Graphs».

Аннотация:

Распределение регистров - ключевая задача бэкенда компилятора: при ограниченном числе регистров нужно так сопоставить переменные регистрам, чтобы одновременно живые переменные не попадали в один регистр, а при необходимости - минимизировать перенос (spill) в память. Классические подходы либо строят интерференционный граф и выполняют его раскраску (Chaitin и производные), либо используют линейный алгоритм распределения регистров (linear scan). При этом точные алгоритмы, основанные на общих tree-decomposition-подходах, часто оказываются непрактичными из-за высоких степеней полинома и больших констант.

Авторы предлагают другой путь: представить структурный CFG (control-flow graph) как выход графовой грамматики (series/parallel/loop, SPL) и выполнять динамическое программирование по грамматическому разложению. Это даёт значительно лучшие асимптотики - в частности, улучшенные оценки для минимизации суммарного spill при фиксированном числе регистров и для проверки возможности раскраски без spill - и делает практическими точные алгоритмы там, где предыдущие treewidth-подходы оказывались неприменимы. В докладе поговорим о фундаменте распределения регистров в компиляторах, разберём идею грамматических декомпозиций и как они связаны с CFG, объясним, почему это значительно ускоряет Chaitin-подобные методы, и пройдёмся по ключевым результатам и экспериментам из статьи.