Распределение регистров и планирование инструкций - важные аспекты реализации бэкенда компилятора. Обе задачи NP-полны и связаны между собой: распределение может внести в код новые инструкции, планирование же меняет инструкции местами. Несмотря на это в популярных компиляторах решаются они, как правило, раздельно и используют эвристические подходы.

Последние два десятилетия много исследований было посвящено точным комбинаторным методам решения тех же самых задач: предложены методы на основе целочисленного программирования, PBQP, программирования в ограничениях и др. Слабость таких подходов - большое время поиска оптимальных решений, что заставляет исследователей упрощать задачу, делая методы неприменимыми в универсальных компиляторах.

Роберто Лозано (Roberto Castaneda Lozano) задался целью разработать одновременно точный и легкий в реализации подход, причем решающий задачи планирования инструкций и распределения регистров совместно. За основу он взял программирование в ограничениях (constraint programming), позволяющее удобно выразить условия обеих задач и для которого существуют мощные решатели.

Проект Unison заменяет три фазы LLVM: предварительное планирование инструкций, распределение регистров и финальное планирование. Распределение проводится глобальное, планирование же локальное - последнее упрощение дает ощутимый эффект при умеренной сложности.

В отличие от предшественников Unison не упрощает задачу распределения. Все практические аспекты проблемы учитываются в решениях: спиллинг, алиасинг (aliasing), рематериализация (rematerialisation), разбиение областей жизни переменных (live range splitting), слияние (coalescing) и др. Программирование в ограничениях позволяет выразить любые проблемы распределения регистров лаконично и просто.

Оптимальность имеет свою цену: поиск решений занимает много времени. Размер компилируемых функций - до 1000 инструкций. Наибольший эффект от Unison был показан на спецпроцессоре Hexagon с длинным машинным словом (VLIW), где важно оптимальное расписание: на некоторых тестах реальное время исполнения снижается на 40%.

Лозано предлагает использовать Unison как инструмент для порождения кода к спецпроцессорам, оценки эффективности эвристических решений, поиска оптимальных решений в отдельных функциях.

Презентация на конференции LLVM (2017): https://www.youtube.com/watch?v=kx64V74Mba0

Обобщающая исследования Лозано диссертация (2018 год): http://kth.diva-portal.org/smash/get/diva2:1232941/FULLTEXT01.pdf

Оценка производительности Unison (2017): https://www.diva-portal.org/smash/get/diva2:1119107/FULLTEXT01.pdf

Сайт проекта: https://unison-code.github.io/

Программирование в ограничениях: https://ru.wikipedia.org/wiki/Программирование_в_ограничениях

Программная статья от именитых исследователей (Nuno P. Lopes и John Regehr) о роли точных методов в будущих компиляторах: https://arxiv.org/pdf/1809.02161.pdf

#registeralloc #instructionscheduling #constraintprogramming #unison #llvm