В традиционных алгоритмах распределения регистров на основе задач упаковки в контейнеры или раскраски графов трудно учесть дополнительные ограничения на доступ к регистрам.

Речь идет об архитектурах с нерегулярным доступом к регистрам (register aliasing, ограничения на использование конкретных регистров в командах). И это относится к x86, но в еще большей мере — к DSP-процессорам и другим специализированным архитектурам.

За последние 3 десятилетия исследователи предложили несколько подходов к проблеме, в том числе метод на базе задачи о квадратичном присваивании (quadratic assignment problem, или QAP), верней частном ее случае: partitioned boolean quadratic optimization problem, или PBQP.

Бернард Шольц (Bernhard Scholz) в работе 2002 года сформулировал распределение регистров как задачу PBQP и показал, что метод позволяет моделировать особенности сложных архитектур. PBQP - NP-полная задача, поэтому впоследствии для метода были разработаны эффективные эвристики, делающие время поиска решений приемлемым.

Интересным метод является не только из-за применимости к отдельным архитектурам:

- возможно регулировать время работы решателя, то есть алгоритм становится прогрессивным;
- решатель может, применяя или не применяя эвристику, находить субоптимальные или оптимальные решения;
- алгоритм пытается избегать применения эвристики и в большинстве случаев находит оптимальные решения.

Наилучшие относительно других подходов результаты PBQP показывает именно в нерегулярных архитектурах, ради которых решатель PBQP был реализован сначала в libfirm, после - и в LLVM.

Впоследствии исследования применимости PBQP в распределении регистров и порождении кода вдохновили эксперименты в применении метода, например, к тестированию памяти или методам машинного обучения.

Понятия регулярности и ортогональности архитектур процессоров в классической работе (1981): https://www.cs.auckland.ac.nz/compsci703s1c/resources/Wulf.pdf

Оригинальная публикация, представляющая PBQP (2002): http://www.complang.tuwien.ac.at/scholz/publications/lctes02.ps.gz

Развитие идей, обновленный алгоритм и новая эвристика (2006): https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.4551&rep=rep1&type=pdf

Разработчики libfirm о применении к SSA (2011): https://link.springer.com/content/pdf/10.1007/978-3-642-19861-8_4.pdf

Неформальный пост от разработчиков libfirm (2011): https://beza1e1.tuxen.de/articles/pbqp.html

Сама задача: https://en.wikipedia.org/wiki/Quadratic_assignment_problem

Тестирование памяти (2020): https://dl.acm.org/doi/fullHtml/10.1145/3427378

Машинное обучение (2018): https://arxiv.org/pdf/1710.01079.pdf

#pbqp #registeralloc #libfirm #llvm