Вторая лекция это начало погружения в компиляторную теорию. Я сознательно сделал её короче, так как она довольно плотная, далее мы вернёмся к часовому формату.

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

https://youtu.be/0DQOmHfPErA

https://rutube.ru/video/8efdba83efac337400af15a8c81e7dbb/

Задания размещены списком в конце лекции, будет здорово если вы их сделаете и скинете скан вашего листочка с решениями сюда в комментарии.

#compilers

Не так давно мои МФТИ-шные контесты по C для первого курса (которые больше недоступны через ejudge) были добавлены на Яндекс контест, о чём я писал вот тут: https://t.me/cpp_lects_rus/187

Сейчас случилось ещё более радостное событие: задачи были добавлены на stepik.

https://stepik.org/209865

Громадное спасибо Артёму Ершову https://t.me/iam28th за эту замечательную работу!

#c_graduate

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

https://youtu.be/fLUnJGwEmYY

https://rutube.ru/video/6753137f2fe26ea94101956c5ac2f4e4/

Задания размещены списком в конце лекции, будет здорово если вы их сделаете и скинете скан вашего листочка с решениями сюда в комментарии.

#compilers

Всем привет. Очередная лекция по компиляторам завтра в 9 утра, а сегодня вечер пятницы и небольшой брейн-тизер по C++.

template<typename T = void>
int foo(int x) { return 1; }

int foo(...) { return 2; }

template<typename T = void>
int bar() { return 1; }

int bar(...) { return 2; }

int main() {
    std::cout << foo(2) << std::endl; // ?
    std::cout << bar() << std::endl;  // ???
}

https://godbolt.org/z/qfsEvxh4E

Громадное спасибо за него Владиславу Белову https://t.me/you_are_RTshnik наткнувшемуся на эту красоту во время выполнения одного из моих заданий.

Задача довольно обычная — объяснить в чём разница с детальными ссылками на C++23. Призов не будет, кроме зрительских симпатий.

P. S. книгу обещают перепечатать к 15 ноября.

UPD: Уважаемый подписчик Артём Колпаков @ddvamp развил и усилил пример до https://godbolt.org/z/ab31ah199

#questions #cpp_postgraduate

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

На этой лекции мы наконец-то построим 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

Позвали недолго поговорить во время трансляции четвертьфинала ICPC. Основная тематика разговора: чего будет ждать индустрия от тех ребят, которые сейчас увлекаются спортивным программированием, когда они вырастут и постучат в её (индустрии) двери.

https://www.youtube.com/watch?v=dfl9IYa9gPU&t=10367s

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

Но я постарался говорить мягко и выделить в основном позитивные моменты, которых там тоже много.

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

#conference #interview

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

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

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

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

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

#compilers

Продолжаю выводить в свет своих учеников. На этот раз предлагаю всеобщему вниманию наше совместное выступление с Марком Гончаровым @EverRester на RISC-V meetup в Нижнем Новгороде.

https://www.youtube.com/watch?v=9hG9pFS-O7w

В первой части я рассказываю про RISC-V и масштабируемую векторизацию, а также про цикловые оптимизации в нашем компиляторе. Это довольно обычный контент. Во второй части становится интереснее: Марк рассказывает про библиотеку SLEEF и про векторизацию циклов с математическими функциями внутри.

Мне кажется Марк проявил себя как отличный докладчик. Обязательно напишите ему что-нибудь в комментарии к видео.

#conference #riscv

Поздний пятничный вечер и пиво -- хороший фон для нашего с Полухиным и Гусаровым стендапа, записанного на C++ митапе Yadro.

https://youtu.be/LcnZKLmOUVo

Мне кажется, дискуссия была неплоха. Одна из лучших шуток это 43:55 -- моя подводка, а потом идеальная добивка от Антона. Мы не репетировали, честно.

Очередная лекция по компиляторам выйдет утром.

#conference

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

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

https://youtu.be/LzIvDMvZx6w

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

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

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

#compilers

Немного заслуженных поздравлений.

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

И я к таким заданиям обычно добавляю: поскольку очевидно кто-то не прав, вы получите высшую оценку за экзамен автоматом, т.е. безо всякого экзамена, если вы сделаете коммит в clang или gcc (смотря кто не прав) и его примут.

Много лет этой опцией никому не удавалось воспользовался. Люди пытались, но пройти ревью и влиться не могли. Но в этом году у нас есть первый победитель.

https://github.com/llvm/llvm-project/pull/118003

Мой студент Владислав Белов @sick_hoof со второго раза влил фикс в кланг. Первый раз его влили, но там в расширенных тестах упал assert и его откатили. Тот assert оказался ошибочным и в этом патче был торжественно удалён.

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

Вот тут он ожидает ошибку:

  template<typename T> struct A {
    typedef int M;
    struct B {
      typedef void M;
      struct C;
      struct D;
    };
  };

  template<typename T> struct A<T>::B::D : A<T*> {
    M m;
    // expected-error@-1 {{field has incomplete type 'M' (aka 'void'}}
  };

А вот тут он ошибки не ожидает, это должно работать:

  template<typename T> struct G {
    struct B {
      typedef int M;
      struct C {
        typedef void M;
        struct D;
      };
    };
  };

  template<typename T> struct G<T>::B::C::D : B {
    M m;
  };

Я полагаю, достойные студенты растут. Боевые. Самому иногда страшно становится.

#cpp_postgraduate

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

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

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

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

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

#compilers

В продолжение https://t.me/cpp_lects_rus/199

Новости книги.

Наконец-то чистовой тираж был отпечатан и разъехался по магазинам, ищите во всех книжных.

Читатели, купившие книгу первого (бракованного) тиража, могут:

1. Либо сделать бесплатную замену в любом магазине.
2. Либо оставить себе книгу из первого тиража и для выдачи бесплатной электронной версии прислать на адрес dostuplitres@gmail.com почту, к которой привязан аккаунт литрес, а также подтверждение покупки книги (чек/скрин + фото книги). В течение недели редакция соберёт письма, после запросит промокоды и, когда их сформируют, вышлет на указанные адреса

P. S. и завтра с утра последняя лекция курса будет на youtube.

#official

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

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

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

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

https://youtu.be/RK8HfK6giL8

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

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

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

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

#compilers