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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автор: 32bit_me

Источник ^[56]