Выложил четвёртую лекцию курса по компиляторам.

На этой лекции мы наконец-то построим SSA представление, на котором в современном мире выполняется большинство компиляторных оптимизаций. По дороге мы познакомимся с такими полезными концепциями как доминаторы, фронт доминирования и дерево доминаторов.

https://youtu.be/diSnBssZ1dQ

https://rutube.ru/video/00ea76b6e9c1406fdc7814ab16ce1c8d/

Задания размещены списком в конце лекции. На этот раз большинство этих заданий предполагает основательное программирование из области алгоритмов над графами. Вам будет предложено по произвольному входному графу построить его дерево доминаторов, DJ-граф и DF-граф. Скидывайте сюда в комментарии ссылки на ваши репозитории с решениями.

#compilers

Выложил пятую лекцию курса по компиляторам.

Настало время познакомиться с базовыми оптимизациями и ввести фреймворк для работы с SSA-представлением. Эта лекция посвящена двум основным идеям: продвижению информации вниз по графу потока управления (constant propagation, copy propagation, value range propagation) и удалению избыточности (global value numbering, partial redundancy elimination).

https://youtu.be/6yo4ofdLRfU

https://rutube.ru/video/62a76dc317939e381df018f6a61be6e0/

Я понимаю, что сложно. Держитесь, впереди самое интересное.

#compilers

Выложил шестую лекцию курса по компиляторам.

Вы же всегда хотели узнать в чём разница между обратными и обращёнными дугами и чем цикл в компьютерной программе отличается от цикла в графе? А чем сводимый граф отличается от не сводимого? А как насчёт поиска базовых индуктивностей и скалярной эволюции? Конечно же вы всегда хотели. В этом видео вы получите всё перечисленное и немного больше. И даже немного про алгебру цепочек рекуррентностей.

https://youtu.be/V6hWKXvUQvo

https://rutube.ru/video/74991603431c25f8d08631b6a5c8e2bf/

Мне кажется лекции снова вынырнули на тот уровень, где они становятся интересны широкой аудитории. Вряд ли вы когда-либо думали о циклах в вашей программе именно таким образом.

#compilers

Выложил лекцию по цикловым оптимизациям

Здесь мы остановимся на основных оптимизациях циклов и попробуем их уложить в некую систему. Основными осями этой системы будут обработка индуктивностей и обработка инвариантов. Мы разберём LSR, раскрутку циклов, их пилинг и многое другое.

https://www.youtube.com/watch?v=OsiqdpCXBtY

https://rutube.ru/video/339ee2a715b0bceabf22cecd3db6f9fb/

В лекции есть небольшая деталь для гурманов.

#compilers

Выложил лекцию по межпроцедурным оптимизациям.

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

https://youtu.be/LzIvDMvZx6w

https://rutube.ru/video/26054b88c9ae1760cfd3244a369ae7ae

Летом на школе мы не успели это пройти и я пообещал что дойдём осенью. И вот буквально в этот четверг мы его записали, срочно обработали звук и я его выкладываю, всё ради непрерывности курса.

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

#compilers

Выложил девятую (предпоследнюю лекцию) в курсе.

На этой лекции мы познакомимся с проблемой выбора инструкций -- перехода от высокоуровневого к низкоуровневому промежуточному представлению. Мы узнаем не менее четырёх NP-сложных задач (и некоторые более сложные) а также два вида низкоуровневого представления и несколько смелых алгоритмов. Самое красивое что нас ждёт это конструкция Пробстинга и внезапная связь выбора инструкций с проблемой вычислимости булевых формул.

https://www.youtube.com/watch?v=Kbv21aYCoyM

https://rutube.ru/video/000c34fb9c7107f443b0caaa7a29275b

Смотреть стоит хотя бы ради упомянутой конструкции Пробстинга. Очень красивая штука. Ну и тем, кого постоянно волновало что это за новый Global ISel в LLVM и откуда он растёт, тоже ИМХО будет полезно.

#compilers

Выложил десятую и последнюю в этом курсе лекцию по оптимизирующим компиляторам.

Пришла пора разрушить то, что мы так тщательно строили и чем так долго пользовались. Это будет не так просто и процесс будет иметь некоторые нюансы. И, конечно же, после разрушения SSA представления, нам всё ещё будет чем заняться. Например распределением регистров, рематериализацией значений, планированием инструкций и разрывание антизависимостей. Мы увидим как отлично зарекомендовавший себя в выборе инструкций подход через квадратичное булево программирование поможет нам с иррегулярными архитектурами. В конце нас ждут последние задания и последняя литература.

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

И я надеюсь вам понравилось.

https://youtu.be/RK8HfK6giL8

https://rutube.ru/video/7396f97feffd6f971570fe1bc38de413/

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

P. S. У меня также предусмотрены пара интересных конкурсов с призами в виде книги (издательство обещало оплатить доставку по РФ). Скоро начнём.

P. P. S. Далее на канале нас ждёт прикладная лекция по цикловым и межпроцедурным оптимизациям в RISC-V, прочитанная мной в Сириусе (Сочи) и, бонусная рождественская лекция с ещё одним интересным содокладчиком. Не отключайтесь.

#compilers

Официальный пост для развёрнутых отзывов к книге "Оптимизирующие компиляторы, структура и алгоритмы".

https://www.chitai-gorod.ru/product/optimiziruyushchie-kompilyatory-struktura-i-algoritmy-3059667

https://www.litres.ru/book/konstantin-vladimirov/optimiziruuschie-kompilyatory-struktura-i-algoritmy-71185981/

И на курс к ней: https://www.youtube.com/playlist?list=PL3BR09unfgcjBG1H9xRUesaQX6nCsobs1

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

Не постите сюда конкретные баги, пост с errata будет следующим. Этот пост -- чисто поделиться впечатлениями.

#official #compilers

Официальный пост для errata к книге "Оптимизирующие компиляторы, структура и алгоритмы".

https://www.chitai-gorod.ru/product/optimiziruyushchie-kompilyatory-struktura-i-algoritmy-3059667

https://www.litres.ru/book/konstantin-vladimirov/optimiziruuschie-kompilyatory-struktura-i-algoritmy-71185981/

И на курс к ней: https://www.youtube.com/playlist?list=PL3BR09unfgcjBG1H9xRUesaQX6nCsobs1

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

#official #compilers

Выложили моё выступление в ИТМО. Попробовал поговорить о настоящей сложности распределения регистров и вообще — про обманчиво простые задачи.

https://www.youtube.com/watch?v=XUttZ838Tw0

00:00 Начало. Кто использует стек?
04:50 Задача распределения регистров и подход через раскраску графов.
10:20 Покраска через клеточные автоматы
12:43 Учёт иррегулярности архитектур и PBQP
15:12 Эвристики для спиллов и рематериализация.
23:05 Слияние и разбиение интервалов активности.
29:28 Немного о настоящей сложности задачи
33:18 Литература и ответы на вопросы

#compilers #conference