В моём углубленном курсе компиляторов прошлой осенью мы провели некоторое время, изучая дерево исходников LLVM. Миллион строк кода на C++ выглядят пугающе, но я нахожу это интересным упражнением, и, по крайней мере, некоторые студенты с этим согласны, и я подумал, что я попытаюсь написать что-то подобное. Мы будем использовать LLVM 3.9, но предыдущие (и, возможно, будущие) релизы не сильно отличаются.

Я не хочу тратить много времени на теоретические основы LLVM, но есть несколько вещей, которые вы должны знать.

Ядро LLVM не содержит фронтенды, только миддленд-оптимизаторы, несколько бэкендов, документацию, и много вспомогательного кода. Фронтенды, такие, как Clang, живут в отдельных проектах.

Промежуточное представление кода в ядре LLVM живёт в ОЗУ и с ним можно производить манипуляции с использованием большого C++ API. Это представление может быть сохранено в виде читаемого текста и распарсено обратно в память, но только для удобства отладки: при нормальной компиляции с использованием LLVM, текстовый IR никогда не генерируется. Обычно фронтенд строит IR с помощью вызовов LLVM API, затем запускает некоторые проходы оптимизации, и после вызывает бэкенд, который генерирует ассемблер или машинный код. Когда код LLVM записывается на диск (чего не происходит при нормальной компиляции проектов C и C++ с использованием Clang), он сохраняется как «биткод», компактное бинарное представление.

Основная документация на LLVM API генерируется в doxygen, и может быть найдена здесь. Эту информацию сложно использовать, если вы уже не знаете в точности, что вам нужно делать, и что искать. Руководства, ссылки на которые даны ниже, это стартовая точка для изучения LLVM API.

Обратимся к коду. Корневая директория содержит:

bindings — «связки», позволяют использовать LLVM API из языков, отличных от C++. Существуют также и другие связки, с языком С (о котором речь будет ниже), и Haskell (его нет в этом дереве).

cmake — LLVM использует CMake, а не autoconf. Просто скажите спасибо тем, кто сделал это за вас.

docs — документация в формате ReStructuredText. Смотрите пример руководства по языку, которое определяет смысл каждой инструкции LLVM (GitHub отображает .rst файлы как HTML по умолчанию, вы можете посмотреть «сырой» файл здесь). Материал в поддиректории с руководством особенно интересен, но не смотрите на него там, лучше зайдите сюда. Это лучший способ изучить LLVM!

examples: Это исходники, которые прилагаются к руководству. Как LLVM-хакерам, вам следует брать отсюда код, CMakeLists.txt, и т.п. отсюда каждый раз, когда это возможно.

include: Первая поддиректория, llvm-c, содержит связки для языка С, которые я не использовал, но которые выглядит довольно разумно. Важно то, что разработчики LLVM стараются сохранять эти связки стабильными, в то время, как С++ API изменяется с каждым релизом, хотя скорость изменений, кажется, замедляется последние несколько лет.

Вторая поддиректория, llvm, большая: она содержит 878 заголовочных файлов, определяющих LLVM API. В общем случае, проще использовать doxygen-версии этих файлов, чем читать их напрямую, но часто приходится грепать эти файлы в поисках какой-либо функции.

lib содержит действительно полезные вещи, мы рассмотрим их ниже отдельно.

projects не содержит ничего по умолчанию, однако сюда копируются компоненты LLVM, такие, как compiler-rt (рантайм-библиотеки для таких вещей, как санитайзеры), поддержка OpenMP и библиотеки LLVM C++, живущие в других репозиториях.

resources: что-то для Visual C++, что не нужно ни вам, ни мне, (подробнее здесь)

runtimes: ещё один плейсхолдер для внешних проектов, добавленный только прошлым летом (2016 года. прим. перев.), и я не знаю, на самом деле, для чего это.

test:: большая директория, содержит тысячи юнит-тестов LLVM, они запускаются, когда вы собираете цель check (make check-all, прим. перев.). Большая часть, это файлы .ll, содержащие LLVM IR в текстовой форме. Они тестируют разные вещи, например, что проход оптимизации приводит к ожидаемому результату. Я рассмотрю тесты LLVM в подробностях в будущем посте.

tools: сам по себе LLVM, это просто коллекция библиотек, и в нём нет выделенной функции main. Большинство поддиректорий в директории tools содержат исполняемые инструменты, которые линкуются с библиотеками LLVM. Например, llvm-dis, это дизассемблер, переводящий биткод в формат текстового ассемблера.

unittests: больше юнит-тестов, также запускаются при сборке цели check. Это файлы C++, которые используют фреймворк Google Test для вызова API напрямую, в отличие от тестов в директории «tests», которые запускают функции LLVM не напрямую, а через запуск ассемблера, дизассемблера или оптимизатора.

utils: моды emacs и vim для соблюдения стиля кодинга LLVM, файл Valgrind для подавления ложноположительных срабатываний, инструменты lit и FileCheck для поддержки юнит-тестирования, и много других разных вещей. Возможно, большая часть из них вам не нужны.

OK, пока всё было довольно просто. Мы пропустили директорию lib, в которой содержится практически всё важное. Посмотрим на поддиректории:

Analysis директория содержит множество статических анализаторов, таких, как анализ алиасов и глобальных значений. Некоторые анализаторы имеют структуру проходов LLVM и должны запускаться менеджером проходов, другие представляют собой библиотеки, и могут быть вызваны напрямую. Странный член семейства анализаторов, это InstructionSimplify.cpp, это фактически преобразование, а не анализ. Я уверен, что многие не заметят комментарий, поясняющий, что этот проход делает здесь.

вот этот комментарий

Этот проход не изменяет сам по себе IR. Правило состоит в том, что llvm::SimplifyInstruction может возвращать только константы и существующие объекты Value, что удовлетворяет требованиям к анализатору. Проход, вызывающий SimplifyInstruction для каждой инструкции, это проход преобразования (lib/Transforms/Utils/SimplifyInstructions.cpp.).

AsmParser: парсит текстовый IR в память.

Bitcode: сериализация IR в компактный формат и чтение из компактного формата в RAM.

CodeGen: генератор аппаратно-независимого кода LLVM, фреймворк, на котором написаны бэкенды LLVM, и набор библиотек, которые эти бэкенды могут использовать. Там много кода (>100 KLOC), и, к сожалению, я мало о нём знаю.

DebugInfo, это библиотека для поддержки отображения между инструкциями LLVM и локациями исходного кода. Много хорошей информации на этих слайдах с выступления на 2014 LLVM Developers’ Meeting.

ExecutionEngine: Хотя LLVM обычно транслируется в машинный код или в ассемблер, он может быть выполнен интерпретатором. Не-JIT интерпретатор не работал как следует в последний раз, когда я его пытался использовать, но в любом случае, он работает медленнее, чем JIT. Последнее JIT API, Orc, находится здесь.

Fuzzer: это libFuzzer, аналогичный AFL (фаззинг). Он использует функциональность LLVM для фаззинга программ, компилируемых с помощью LLVM.

IR: различный код, относящийся к IR. Код для вывода IR-кода в текстовом формате, для апгрейда файлов биткода, созданных в ранних версиях LLVM, для сворачивания констант в процессе создания IR-узлов и т.п.

IRReader, LibDriver, LineEditor: почти никому неинтересно, что здесь находится, и вряд ли там есть какой-то полезный код вообще.

Linker: Модуль LLVM, как и единица компиляции С и С++, содержит функции и переменные. Линковщик объединяет множество модулей в один большой модуль.

LTO: Оптимизация времени компоновки, предмет множества постов и научных статей, позволяет оптимизатору видеть за пределами отдельных скомпилированных модулей. LLVM делает оптимизацию при компоновке «бесплатно», используя линковщик для создания большого модуля и затем оптимизируя его обычными проходами оптимизации. Это хороший подход, но он не масштабируется для очень больших проектов. Современный подход — ThinLTO, который позволяет получить большую часть преимуществ за маленькую часть цены.

MC: компилятор обычно генерирует ассемблерный код и позволяет ассемблеру создать машинный код. Подсистема MC в LLVM устраняет промежуточное звено и позволяет генерировать машинный код напрямую. Это ускоряет компиляцию и особенно полезно когда LLVM используется как JIT-компилятор.

Object: Реализация деталей форматов объектных файлов, таких, как ELF.

ObjectYAML — поддерживает кодирование объектных файлов в YAML. Я не знаю, зачем это нужно.

Option: — парсинг командной строки.

Passes: часть менеджера проходов, который управляет запуском проходов LLVM, принимая во внимание зависимости.

ProfileData: — читает и пишет данные профилирования для поддержки оптимизаций, основанных на профилировании.

Support: Поддержка различного кода, включая APInts (целые числа с произвольной точностью, широко используемые в LLVM) и т.п.

TableGen: своего рода швейцарский нож, инструмент, который получает на входе .td-файлы (которых в LLVM больше 200), содержащие структурированные данные, и генерирующий код С++, который компилируется в LLVM. TableGen используется, например, для реализации ассемблера и дизассемблера.

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

Transforms: это моя любимая директория, здесь живут миддленд-оптимизаторы. IPO содержит межпроцедурные оптимизации, работающие между границами функций, они обычно не очень агрессивны, но видят сразу много кода. InstCombine — это peephole-оптимизатор. Instrumentation — поддержка санитайзеров. ObjCARC поддерживает вот это. Scalar содержит оптимизации «из учебника» по компиляторам, я постараюсь написать более подробный пост о содержимом этой директории. Utils — вспомогательный код. Vectorize — автовекторизатор LLVM, предмет большой работы последних лет.

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

Путеводитель по исходникам LLVM