17/02/2021, Vladimir Kazanov¶
Распределение регистров и планирование инструкций - важные аспекты реализации бэкенда компилятора. Обе задачи 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
#constraintprogramming #unison #registeralloc #instructionscheduling #llvm
21/05/2020¶
Недавно (27-28 апреля, 2020) состоялся европейский симпозиум по Лиспу.
European Lisp Symposium https://www.european-lisp-symposium.org/2020/ Видеозаписи докладов: https://www.youtube.com/playlist?list=PLA66mD-6yK8yjlJCI0Ay2f2IvvmB9Ktga
Ниже краткая информация о 3 докладах по околокомпиляторной тематике:
Partial Evaluation Based CPS Transformation: An Implementation Case Study Описание компилятора для диалекта Лиспа pLisp. В компиляторе используются частичные вычисления и CPS. Слайды: https://www.european-lisp-symposium.org/static/2020/jayaprakash-slides.pdf Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf
LLVM Code Generation for Open Dylan Dylan — это диалект Лиспа с Алгол-подобным синтаксисом. В начале 90-х этот язык развивался компанией Apple. В докладе представлено описание генератора кода для Dylan на основе LLVM. Слайды: https://www.european-lisp-symposium.org/static/2020/housel-slides.pdf Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf
Later Binding: Just in Time Compilation of a Younger Dynamic Programming Language Краткий анализ компилятора LuaJIT Видео выступления: https://www.youtube.com/watch?v=FBk5XAEhu2s Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf