#books #compiler Обзор книги "Оптимизирующие компиляторы. Структура и алгоритмы" (2024 г.) 📚 Я вас категорически приветствую! Третьего дня, по совету проверенных камрадов, приобрел новую мегакнигу "Оптимизирующие компиляторы". Сразу же, задыхаясь от интереса, схватил книгу цепкими лапами и принялся читать. Контент - мое почтение. Настоящей глыбой является Константин Владимиров. Даже моя, привыкшая к суровым алгоритмам башка, отказывалась принимать с первого захода. Совместными с ChatGPT усилиями дочитали книгу. Ощущения - атас! С "dragonbook" не идет ни в какое сравнение. Кроме того, задания в конце глав заставляют сильно думать. Проходил так всю неделю. Решительно готов к новым контрибам в Clang/LLVM. Многие дети тут увидят ненужные академические материалы. Тупым детям невдомек, что абстрактная математика и прикладные алгоритмы это разные вещи. Книга отличная. Всем рекомендую к приобретению. Все это, как водится, рецензия. ❌ ❌ ❌ Работа компилятора разделяется на несколько больших кусков - условно "фронтенд" и "бэкенд" (но и внутри них своя иерархия 🖥) 95% того, о чем я писал (по хештегу #compiler и т.д.) относится именно к фронтенду компилятора. На этом же уровне работают почти весь набор стандартных тулзов для C++ погромиста: clang-tidy (по AST), clangd (тоже по AST), clang-format (по аннотированным токенам) и т. д. Во фронтенды компиляторов порог входа сравнительно низкий - без предварительной подготовки любой студент может почитать/покоммитить или даже создать свой фронтенд 👦 Другое дело - бэкенд компиляторов, там требуется более серьезная подготовка - с графами, линейной алгеброй, теорией алгоритмов, и прочим. Книга как раз сфокусирована на бэкенде, в основном высокоуровневом (в отрыве от инструкций конкретной машины). Главы: 1️⃣ Тулчейны. Спидран по всем компонентам от грамматик до линкеров 🏃‍♂️ 2️⃣ Введение в оптимизации. Древние алгосы про "анализ потока данных" и решение многих задач через "решетки", нужны для ввода в контекст. 3️⃣ Построение SSA. Что такое SSA и как его построить через "дерево доминаторов". 4️⃣ Базовые оптимизации для SSA. Крутые алгоритмы для "глобальной нумерации значений" и "устранения избыточных вычислений". 5️⃣ Цикловые оптимизации. Много алгоритмов для оптимизации циклов (как for и while). 6️⃣ Межпроцедурные оптимизации. Инлайн и де-инлайн функций, хвостовая рекурсия, девиртуализация, и т. д. 7️⃣ Разрушение SSA. Саморазрушение - вот что действительно важно. Перевод SSA в ассемблер, и лютое количество NP-полных задач чтобы это нормально сделать 😔 Автор дает мега широкий обзор про кучу вопросов оптимизаций. Есть десятки ссылок на другие научные работы и статьи. В самой книге затронута самая база, то есть основа. Если всерьез работать компиляторщиком, можно по ссылкам почитать еще тысячи страниц и преисполниться 📖 К алгоритмам есть информация - какие применяются в LLVM и/или GCC, есть много примеров на LLVM IR. Активно используется "динамическое программирование", "жадные алгоритмы", "union-find множества" и прочие дорогие сердцу. Для каждого термина дается перевод на английский, тоже с мета-информацией. В частности есть доходчивое пояснение почему "graph cycle" переводится как "цикл" (и от него производные слова как "зациклиться" и т.д.), а "loop" тоже как "цикл" а не "луп" 🤔 Многие факты узнал впервые - например какие задачи компилятора решаемы (хотя бы за квадратичное время) а какие NP-полные, и компилятор их не делает решает приближенно 🚬 После прочтения книги в очередной раз понял, что не могу быть 100% уверенным, какой ассемблер сгенерирует компилятор 🤪 На эту тему есть крутой сборник фактов Common Misconceptions about Compilers.