Оптимизирующие компиляторы (МФТИ, 2024). Лекция 9. Выбор инструкций.

Лекции по компиляторам для свежих интернов базовой кафедры в МФТИ. На этой лекции мы познакомимся с проблемой выбора инструкций -- перехода от высокоуровневого к низкоуровнему промежуточному представлению. Мы узнаем не менее четырёх NP-сложных задач (и некоторые более сложные) а также два вида низкоуровневого представления и несколько смелых алгоритмов. Самое красивое что нас ждёт это конструкция Пробстинга и внезапная связь выбора инструкций с проблемой вычислимости булевых формул. Лектор: Константин Владимиров Видео и звук: Юлий Тарасов Timeline 00:00 Low-level IR 06:25 Selection DAG 13:05 SDHIR и легализация 20:15 Instruction Selection в LLVM 33:30 Выбор инструкций 36:45 SAT и конструкция Пробстинга 44:10 PBQP для выбора инструкций 50:40 GLIR и Global ISel 55:00 Задания и литература Errata * пока пусто