"It's Easy As 1, 2, 3" by Gharam Hutton.

Если вы учили теорию типов по мемам, эта статья для вас: поможет организовать знания.

Категориальной семантики нету.

Классно. Напомнило недавнее объяснение "на пальцах", как делать верифицированные бутстрапнутые компиляторы (от одного из авторов CakeML): https://popl21.sigplan.org/details/CPP-2021/6/A-Minimalistic-Verified-Bootstrapped-Compiler-Proof-Pearl-

Можно ли вызвать stackoverflow при компиляции gcc-шкой достаточно вложенной программы?

thanks for sharing

Краткий ответ да. А уж при каких уровнях вложенности будет возникать переполнение - это надо смотреть. Даже чисто теоретически в языках программирования есть вложенные структуры, которые надо временно размещать в стеке. И можно написать такое выражение, которое стек переполнит. Про немного другую тему, у меня знакомый как-то писал небольшой тест на C++, где создается шаблон с шаблонным параметром. И там задается константа, при увеличении константы в 10 раз время компиляции возрастало в кубе, то есть примерно в 1000 раз. И так можно было легко подвесить компилятор на часы и сутки.

На заметку компаниям, которые ищут компиляторщиков. Если вас интересуют профессионалы в этой области, то плохая идея — поручать общение исключительно HR'ам. Думаю, ничего унизительного для ваших специалистов нет в том, чтобы обратиться к желаемому кандидату напрямую.

Опять H) что ли)

Можно подумать со всеми остальными специалистами что-то существенно иначе.

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

Против тематических вакансий ничего не имею, если указана компания и вилка

Хотя бы компания. А так, бывают самые вкусные и без вилки

Распределение регистров и планирование инструкций - важные аспекты реализации бэкенда компилятора. Обе задачи 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

Ммм, старое-доброе CLP решает?

все новое - забытое старое 😊

Но тут, пожалуй, не только новое применение старой парадигмы, но и прогресс в ускорении поиска решений.

smt-солверы тоже недалеко от clp ушли так-то

не, ну smt-решатели это сильно ниже уровнем, чем CP. Решателем может служить в том числе и SMT.

CP радует тем, насколько удобно для него задачи формулируются и используют потом существующие внешние решатели

но тут @true_grue больше моего знает

хм, мне кажется CLP для конечных доменов не особо сильнее SMT

@impworks а вы пробовали потрясти Хуавей, Интел или что нибудь и попробывать сделать какой митап?