C++95

C++95

book1.jpg

#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.

Please open Telegram to view this post

VIEW IN TELEGRAM

❤31🔥28👍6

www.tgoop.com/cxx95/148

4.64K viewsJan 10 at 20:24

#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.