Оптимизирующие компиляторы, Структура и алгоритмы, Владимиров К., 2024

Оптимизирующие компиляторы, Структура и алгоритмы, Владимиров К., 2024.
        
   «Оптимизирующие компиляторы» — настольная книга специалиста, который решил не просто укрепить свои знания, но и вывести навыки на новый уровень.
Вместе с Константином Владимировым вы разберете теорию оптимизирующей компиляции — все те сложные преобразования, которые происходят с текстом программы на его пути к исполняемому файлу, узнаете, что такое тулчейны и каким этапам трансформации подвергается программа до того, как будет впервые запущена, а также закрепите полученные знания, выполняя задания.




Тулчейны.
Так исторически сложилось, что компиляторы не работают в изоляции. На практике пользователь вообще редко запускает компилятор. И gcc и clang и даже cl это просто программы-оболочки (также говорят «драйверы»), которые запускают из-под себя не только компилятор, но и много что ещё. Конечно, пользователя интересует результат: превращение текста программы в исполняемый файл. Но именно для достижения такого результата одного только компилятора мало. Когда в обыденном языке мы говорим «компилятор gcc», мы обычно имеем в виду как раз ту самую программу-оболочку, под которой скрывается GNU Toolchain — громадный и разветвлённый набор компонентов и библиотек.

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

ОГЛАВЛЕНИЕ.
Введение. 
Глава 1. Тулчейны. 
1.1 Общий обзор.
1.2 Компиляторы.
1.2.1 Лексический анализ. 
1.2.2 Синтаксический анализ.
1.2.3 Промежуточное представление. 
1.2.4 Машинно-независимые оптимизации. 
1.2.5 Кодогенерация. 
1.3 Ассемблеры. 
1.3.1 Ассемблирование функций и понятие ABI.
1.3.2 Дизассемблирование и релокации. 
1.4 Линкеры.
1.4.1 Оптимизации времени линковки. 
1.4.2 Релаксации.
1.5 Задачи на самостоятельную проработку. 
Глава 2. Введение в оптимизации.
2.1 Поток управления. 
2.2 Решётки и распространение констант.
2.2.1 Бинарные отношения. 
2.2.2 Решётки.
2.2.3 Продвижение констант.
2.3 Поток данных.
2.3.1 Достигающие определения.
2.3.2 Доступные выражения.
2.3.3 Активные переменные и обратный анализ. 
2.3.4 Трансформации и анализ в HIR. 
2.4 Нумерация значений.
2.5 Задачи на самостоятельную проработку. 
Глава 3.Построение SSA. 
3.1 SSA представление.
3.1.1 Наивный способ построения SSA.
3.2 Отношения и структуры доминирования. 
3.2.1 Дерево доминаторов. 
3.2.2 Фронт доминирования.
3.2.3 Графы схождения.
3.3 Построение SSA. 
3.3.1 Свойства и виды SSA.
3.3.2 Основной алгоритм.
3.3.3 Построение SSA в LLVM.
3.4 Задачи на самостоятельную проработку. 
Глава 4. Базовые оптимизации для SSA. 
4.1 Начинаем использовать SSA.
4.1.1 Работа с SSA представлением.
4.1.2 Граф зависимостей SSA.
4.2 Продвижение констант и не только.
4.2.1 Простое продвижение констант. 
4.2.2 Добавляем информацию из CFG.
4.2.3 Другие продвижения информации. 
4.3 Глобальная нумерация значений. 
4.3.1 Построение классов конгруэнтности.
4.3.2 Улучшение эффективности разбиения.
4.4 Устранение частичной избыточности.
4.4.1 Разбиение критического ребра. 
4.4.2 Граф избыточных выражений.
4.4.3 Алгоритм SSAPRE. 
4.5 Задачи на самостоятельную проработку. 
Глава 5. Цикловые оптимизации.
5.1 Естественные циклы. 
5.1.1 Обходы в графах и обращение дуг. 
5.1.2 Сводимость. 
5.1.3 Канонический вид цикла. 
5.1.4 Замкнутое цикловое SSA.
5.2 Поиск и оптимизации индуктивностей. 
5.2.1 Индуктивные переменные. 
5.2.2 Поиск базовых индуктивностей.
5.2.3 Скалярная эволюция.
5.2.4 Упрощение вычислений в циклах. 
5.2.5 Раскрутка циклов.
5.3 Инварианты и квази-инварианты.
5.3.1 Вынос инвариантного кода из цикла.
5.3.2 Пилинг циклов.
5.4 Структурные оптимизации.
5.4.1 Распределение и соединение циклов.
5.4.2 Оптимизации для локальности данных. 
5.4.3 Разглаживание циклов. 
5.4.4 Вынос инвариантного управления. 
5.4.5 Управление цикловыми оптимизациями.
5.5 Задачи на самостоятельную проработку. 
Глава 6. Межпроцедурные оптимизации.
6.1 Клонирование и трансформации функций. 
6.1.1 Продвижение констант и прочей информации.
6.1.2 Эвристики и управление эвристиками.
6.1.3 Частичная девиртуализация. 
6.1.4 Хвостовая рекурсия.
6.2 Подстановка и факторизация функций.
6.2.1 Подстановка функций.
6.2.2 Вынос функций.
6.3 Задачи на самостоятельную проработку. 
Глава 7. Разрушение SSA.
7.1 Выбор инструкций. 
7.1.1 Перевод в представление SDHIR.
7.1.2 Легализация и выбор инструкций.
7.1.3 Альтернативный подход: модификация LIR. 
7.1.4 Конструкция Пробстинга. 
7.1.5 Подход на основе PBQP.
7.2 Распределение регистров.
7.2.1 Разрушение SSA. 
7.2.2 Подходы, основанные на раскраске графа. 
7.2.3 Линейный подход к распределению регистров. 
7.2.4 Подходы, основанные на PBQP и ILP. 
7.3 Планирование инструкций.
7.3.1 Планирование на виртуальных регистрах. 
7.3.2 Планирование на физических регистрах.
7.4 Задачи на самостоятельную проработку.
Заключение. 
Предметный указатель. 
Литература.

Купить .





Теги: учебник по программированию :: программирование :: Владимиров :: компилятор :: тулчейны :: программа