Цель работы: Познакомиться с инструментами Clang и LLVM, научиться собирать AST и IR-промежуточное представление кода на C/C++, а также извлекать базовую информацию о программе (например, список функций). Задачи:
- Установить Clang и LLVM;
- Скомпилировать простой C-файл с использованием clang и получить его: абстрактное синтаксическое дерево (AST), промежуточное представление LLVM IR;
- Использовать opt для применения базовой комплексной оптимизации (например, О2);
- Построить граф потока управления (CFG) для оптимизированной программы;
- Проанализировать результат, сделать выводы и ответить на контрольные вопросы.
Clang — это компилятор для языков C, C++, Objective-C и других, работающий как фронтенд для LLVM. Он:
- Выполняет лексический, синтаксический и семантический анализ исходного кода;
- Создаёт абстрактное синтаксическое дерево (AST);
- Генерирует промежуточное представление (LLVM IR).
Таким образом, Clang отвечает за первую стадию компиляции: от исходного текста до промежуточного представления.
LLVM — это модульная инфраструктура для компиляторов. Она включает:
- Промежуточное представление (LLVM IR);
- Инструменты для оптимизации кода;
- Бэкенд для генерации машинного кода под различные архитектуры (x86, ARM и др.).
Современные компиляторы используют LLVM как основу для:
- Преобразования IR в оптимизированный код;
- Генерации платформозависимого исполняемого файла.
| Характеристика | AST | LLVM IR |
|---|---|---|
| Уровень абстракции | Высокий (близко к исходному коду) | Низкий (близко к машинному коду) |
| Назначение | Анализ структуры и семантики программы | Оптимизация и генерация машинного кода |
| Представление | Структура данных на основе синтаксиса | Линейная последовательность инструкций |
AST используется для понимания структуры программы.
LLVM IR — для анализа и трансформаций кода.
LLVM IR нужен для:
- Универсальности: один IR поддерживает разные языки и архитектуры;
- Оптимизации: IR позволяет применять мощные трансформации кода;
- Гибкости: IR служит связующим звеном между фронтендом и бэкендом компилятора;
- Портируемости: код можно легко адаптировать под разные платформы.
Инструкция alloca (от allocate) выделяет память в стеке текущей функции. Она используется для создания локальных переменных.
Пример:
%ptr = alloca i32Эта команда резервирует место для одного целого числа на стеке. Она важна для управления памятью на уровне IR — особенно в функциях, где нужно хранить временные данные или параметры.
Оптимизация кода — это процесс преобразования программы для улучшения её характеристик без изменения поведения. Основные цели:
- Увеличение производительности (уменьшение времени выполнения);
- Снижение потребления памяти;
- Уменьшение размера исполняемого файла;
- Улучшение энергоэффективности (важно для мобильных устройств).
Компилятор с оптимизациями может автоматически заменять неэффективные конструкции более быстрыми и компактными.
SSA (Static Single Assignment) — это форма представления кода, в которой каждая переменная присваивается только один раз. Все повторные присваивания создают новые версии переменной.
Преимущества SSA:
- Упрощает анализ зависимостей;
- Облегчает оптимизации, такие как удаление мёртвого кода и устранение общего подвыражения;
- Позволяет точнее отслеживать значения переменных.
LLVM IR использует SSA по умолчанию.
CFG (Control Flow Graph) — это граф, где:
- Вершины — базовые блоки (последовательности инструкций без ветвлений);
- Рёбра — возможные переходы между блоками (например, через
brилиswitch).
CFG помогает:
- Понять структуру выполнения программы;
- Определять достижимость кода;
- Выполнять оптимизации, такие как свёртывание циклов и предсказание ветвлений;
- Анализировать потоки данных и зависимости.
LLVM IR использует отдельные инструкции для каждой арифметической операции. Примеры:
%sum = add i32 %a, %b ; сложение
%prod = mul i32 %a, %b ; умножение
%diff = sub i32 %a, %b ; вычитание
%quot = sdiv i32 %a, %b ; целочисленное делениеКаждая операция:
-
Явно указывает тип операндов (i32, float и т.д.);
-
Является выражением в SSA-форме (результат сохраняется в %имя).
Функции — это самодостаточные блоки кода с чёткими границами. Это позволяет:
-
Проводить локальные оптимизации (например, устранение мёртвого кода);
-
Анализировать зависимости и эффекты внутри функции;
-
Выполнять инлайнинг, если функция маленькая;
-
Упрощать повторное использование и линковку модулей.
-
Разделение по функциям делает анализ более масштабируемым и параллелизуемым.
LLVM может применить инлайнинг — заменить вызов функции её телом. Преимущества:
-
Уменьшение накладных расходов на вызов функции;
-
Дополнительные возможности для локальных оптимизаций;
-
Улучшение производительности.
-
Короткие функции, вызываемые один раз, почти всегда инлайнится во время оптимизации.
12. Какие преимущества даёт использование IR и CFG для автоматических оптимизаций по сравнению с анализом исходного текста на C?
Преимущества использования IR и CFG:
-
Унифицированность: один IR подходит для разных языков;
-
Формализованная структура: упрощает статический анализ;
-
Типовая строгость и SSA: позволяют безопасно выполнять глубокие трансформации;
-
Явные зависимости и переходы: CFG помогает выявлять критические пути и упрощает анализ потоков выполнения;
-
Избавление от синтаксической сложности C: не нужно учитывать макросы, препроцессор и особенности синтаксиса.
-
IR и CFG создают среду, более удобную для автоматических и агрессивных оптимизаций, чем исходный текст программы.
Работа выполнялась в среде Ubuntu 22.04. Установлены следующие инструменты:
clang— компилятор языка C/C++.llvm— инструменты анализа и оптимизации кода.opt— инструмент для работы с LLVM IR и применения оптимизаций.Graphviz— инструмент для визуализации кода.
Команда установки:
sudo apt install clang llvm graphviz
Пример программы main.c:
#include <stdio.h>
int add(int a, int b) {
return a + b;
}
int main() {
return add(3, 4);
}Команда для генерации AST:
clang -Xclang -ast-dump -fsyntax-only main.c
Команда для генерации LLVM IR:
clang -S -emit-llvm main.c -o main.ll
Команда для генерации неоптимизированного IR:
clang -O0 -S -emit-llvm main.c -o main_O0.llОсобенности IR до оптимизации:
- Все переменные (
a,b) размещены в памяти черезalloca. - Множество операций
loadиstore. - Функция
addвызывается как отдельная функция.
Команда для генерации оптимизированного IR с уровнем -O2:
clang -O2 -S -emit-llvm main.c -o main_O2.llОптимизация -O2 включает более 30 различных оптимизаций, таких как:
-inline: встраивание небольших функций (встраиваетaddвmain).-constprop: подстановка констант: если аргументы функции известны (например, add(3, 4)), результат (7) вычисляется на этапе компиляции;-mem2reg: перевод переменных из памяти в регистры (SSA).-instcombine: объединение и упрощение инструкций.-simplifycfg: оптимизация структуры блоков.-reassociate,-gvn,-sroa,-dceи другие.
Особенности IR после оптимизации:
- Функция
squareисчезла (встроена через-inlineи вычислена через-constprop). - Переменные,
alloca,store,loadудалены (-mem2reg,-dce)..
Команда для сравнения IR до и после оптимизации:
diff main_O0.ll main_O2.ll
Изменения после оптимизации:
- Переменные типа
allocaудалены. - Код переведён в SSA-форму.
- Улучшена читаемость и упрощён поток управления.
Команда для генерации оптимизированного LLVM IR:
clang -O2 -S -emit-llvm main.c -o main.llКоманда для генерации .dot-файлов CFG:
opt -passes=dot-cfg -disable-output main.ll
Вывод:
find . -name "*.dot"
./.main.dot
./.square.dotСоздаются DOT-файлы:
.main.dot— для функцииmain..square.dot— для функцииsquare(если не была удалена оптимизацией).
Команды для преобразования .dot в .png:
dot -Tpng .main.dot -o cfg_main.png
dot -Tpng .add.dot -o cfg_add.pngКоманды для просмотра CFG:
xdg-open cfg_main.png
xdg-open cfg_add.png
- С помощью Clang можно получить полную структуру AST, IR и CFG.
- LLVM предоставляет гибкие инструменты анализа и оптимизации.
- Промежуточное представление (IR) удобно для написания компиляторных трансформаций.