Внутреннее устройство LLVM: формат битового кода

Программирование, философия, педалирование.


июл 36,

Теги: llvm , ржавчина

Серия:

llvm -внутренние

Предисловие

Я написал пару сообщений на самом LLVM , в основном на что вы можете делать с LLVM или как LLVM представляет определенные функции программы.

Я получил несколько хороших отзывов об этом, но я Я хочу сосредоточить часть сообщений на самой реализации LLVM : форматах файлов, стратегиях синтаксического анализа и алгоритмических вариантах, лежащих в основе общедоступных интерфейсов LLVM (API, интерфейсы командной строки и расходуемые выходные данные). файлы). Я буду писать эти сообщения, когда работаю над серией библиотек на чистом Rust для приема файлов LLVM промежуточное представление , с конечной целью иметь возможность выполнять анализ программ, скомпилированных в LLVM IR в чистом Rust, только для чтения.

Для тех, кто не знает, что такое LLVM это , это сообщение имеет более обширную информацию о компонентах LLVM и промежуточном представлении.

Quis repraesentābit ipsos repraesentātiōnēs?

1

Промежуточное представление LLVM – это не просто серия изменений в памяти программы по мере ее прохождения. фазы компиляции: это стабильная модель программы, которая может быть сохранена на диск и впоследствии восстановлена ​​для анализа ы, которые запускаются в совершенно новых вызовах clang или другие инструменты LLVM 2 .

Итак: как LLVM точно сохраняет свое промежуточное представление на диске?

Ответ двоякий: LLVM предоставляет как текстовую форму , который выглядит примерно как язык программирования семейства C, и двоичную форму ( битовый код , выражаясь языком LLVM), который более плотный и (якобы) быстрее анализируется. Эти две формы семантически идентичны, и их легко создать и преобразовать между ними:

1 2 3 4 5 6 7 8 9 19 19 36

  # создать foo.bc для foo.c   $  лязг  - emit-llvm   - c  foo.c  $  файл foo.bc foo.bc: LLVM IR bitcode  # конвертировать foo.bc в foo.ll (человекочитаемый IR)   $  llvm-dis foo.bc  $  файл foo .ll foo.ll: текст ASCII с очень длинными строками  # создать foo.ll прямо из foo.c   $  лязг  - S   - emit-llvm   - c  foo.c 

Текстовую форму IR LLVM интересно читать, но это «просто» текст: медленно и (возможно) раздражает анализировать с помощью машины, но легко для понимания людьми.

Напротив, форма битового кода в высшей степени непостижима даже по стандартам двоичного формата: кроме нескольких печатаемых строк, есть не являются очевидными структурами фиксированного размера или с префиксом длины. В обмен на эту непостижимость, он отлично справляется с хранением промежуточного представления LLVM с экономией места. Сравните представления SQLite

3. 2021. 0 объединенный выпуск :

sqlite3.c

sqlite3.ll

sqlite3.bc

19. 0 МБ

1,8 МБ

На порядок меньше - неплохо

3 4 . Давайте выясним, что нам нужно сделать, чтобы разобрать формат битового кода для себя.

Анализ битового кода LLVM

LLVM - это хорошо документированный проект, а формат битового кода - без исключения . Подводя итог:

  • Формат битового кода LLVM является специализацией более общего формата контейнера (например, MKV или MP4), битового потока .
  • Контейнер битового потока определяет последовательность блоков , каждый из которых содержит дополнительные (вложенные) блоки и / или записи данных . Записи данных - это листы структуры битового потока, записывающие информацию, зависящую от формата. Концепции блоков и записей примерно соответствуют концепциям программных функций на уровне IR (мыслительные функции, базовые блоки) и их компонентов (мыслительные инструкции, типы).

Все это звучит очень красиво структурировано, что вызывает вопрос: почему в файле битового кода нет видимой структуры (при просмотре в шестнадцатеричном редакторе)?

Ответ в немного из бит код и немного поток: блоки и записи не выровнены по байтам (или более крупным границам, например, словам); они кодируются как битовые поля переменной длины . Эти битовые поля могут разделять один байт или занимать несколько байтов, давая файлам битового кода исключительно высокую энтропию по сравнению с двоичными объектами (визуализировано с помощью

binvis.io ):

И блоки, и записи данных идентифицируются сокращенными идентификаторами , которые в документации LLVM обычно сокращаются до «сокращенных идентификаторов». В истинно самоопределении большинство идентификаторов сокращений, используемых файлом битового кода, не определяется форматом контейнера - они определяются в самом битовом потоке появлением DEFINE_ABBREV записи 5 . Действительно, формат контейнера определяет только 4 чрезвычайно простых идентификатора сокращений: два для управления областью блока ( ENTER_SUBBLOCK и END_BLOCK ), DEFINE_ABBREV и UNABBREV_RECORD как универсальная неэффективная кодировка «аварийного выхода» для записей 6 .

Эти идентификаторы сокращений (и форматы сокращений, на которые они ссылаются, подробнее об этом скоро) привязаны к блоку, который их вводит 7 , за одним исключением: блоки битового потока, которые Модуль description LLVM может сам содержать BLOCKINFO , который, в свою очередь, может определять несколько сокращений для любых последующих блоков, которые соответствуют идентификаторам блоков, указанным BLOCKINFO .

Если все эти косвенные указания и сокращения не были достаточно сложными, формат контейнера битового потока использует три различных метода для определения длины записей и их составляющие битовые поля:

Сокращения и БЛОКИНФО

Как уже упоминалось выше: каждое сокращение имеет соответствующее определение сокращения , расположение которого в потоке определяет его соответствующее аббревиатура ID .

Другими словами: идентификаторы сокращений никогда не определяются явно где-либо. Они неявно определены как часть порядка появления DEFINE_ABBREV записи, которые применяются к текущей области блока.

Итак, как определить, какие сокращения применяются? к текущему объему блока? Мы применяем три правила:

  • Независимо от нашей текущей области применения, сокращения 0 через 3 определяются самим контейнером битового потока: они END_BLOCK , ENTER_SUBBLOCK , DEFINE_ABBREV и UNABBREV_RECORD , как уже упоминалось выше.
  • Затем, начиная с начального состояния счетчика 4 , проверяем специальные БЛОКИНФО блокировать. BLOCKINFO (по сути) содержит сопоставление идентификаторов блоков с записями сокращений - мы назначаем каждой записи, которая соответствует идентификатору блока нашей текущей области видимости порядковый идентификатор аббревиатуры.
  • Наконец, мы подсчитываем все DEFINE_ABBREV записи, присутствующие в нашей текущей области. Они также получают идентификаторы последовательных сокращений.
  • Эти правила могут быть трудными для абстрактного понимания, поэтому рассмотрите следующее символическое представление модуля LLVM IR в потоке битов. формат контейнера (я дал DEFINE_ABBREV s символические имена для понимания):

      
     

    БЛОК MODULE_BLOCK (ИДЕНТИФИКАТОР БЛОКА № 8 ) BLOCK BLOCKINFO (BLOCK ID # 0) RECORD SETBID # 8 (MODULE_BLOCK) RECORD DEFINE_ABBREV // ЗАПИСЬ "A" DEFINE_ABBREV // УСТАНОВКА ЗАПИСИ "B" № 36 (FUNCTION_BLOCK) ЗАПИСАТЬ DEFINE_ABBREV // "C" ЗАПИСЬ DEFINE_ABBREV // "D" ЗАПИСЬ DEFINE_ABBREV // БЛОК "E" FUNCTION_BLOCK (ID БЛОКА # 36) ЗАПИСЬ DEFINE_ABBREV // "F"

    8,0 МБ
     1 2 3 4 5 6 7 8 9 11 14 

    Здесь у нас есть три потенциальных области действия блока (верхний уровень MODULE_BLOCK с вложенным БЛОКИНФО а также БЛОК_ФУНКЦИИ ). Идентификаторы сокращения по умолчанию для каждого из них:

    • МОДУЛЬ_БЛОК : A ( # 4), B (# 5), D (# 6), E (# 7)
    • БЛОКИНФО : Нет (только встроенные сокращенные идентификаторы!)
    • FUNCTION_BLOCK : C (# 4), F (# 5)

    Обратите внимание, что здесь есть некоторая тонкость : the МОДУЛЬ_БЛОК указан как блок верхнего уровня, а БЛОКИНФО вложен в него, но BLOCKINFO может (и содержит в данном случае) определения сокращений, которые мы должен интерпретировать, чтобы правильно проанализировать МОДУЛЬ_БЛОК . Таким образом, нам потенциально необходимо перейти вперед в битовом потоке, чтобы интерпретировать BLOCKINFO , прежде чем мы сможем правильно интерпретировать нашу фактическую отправную точку

      12 .

      Я всего-лишь хочу

      гриль интерпретировать ИК!

      Весь этот текст, и мы явно не приблизились к фактическому получению семантики IR из файла битового кода, сгенерированного LLVM. Упс.

      Все здесь важная основа для интерпретации контейнера битового потока, но получение фактической семантики IR - это совершенно другое, отдельное зверюга. Я собираюсь посвятить следующий пост (дайте ему около месяца) именно этому: взяв здесь примитивы и взлом

      используя их для создания библиотеки Rust которые могут интерпретировать модули битового кода

      12 . Этот ящик, в свою очередь, станет субстратом для высокоуровневого ящика, который предоставляет приятные API для фактического анализа LLVM IR. И все это без необходимости сборки или ссылки на сборку вашей системы LLVM!

      Первый шаг этого (долгого) процесса уже сделан: я открываю исходный код начальной версии llvm-bitcursor , который предоставит битовый курсор над контейнером битового потока. Он уже поддерживает VBR n декодирование тоже.



      Обсуждение Reddit


    Leave a comment

    Your email address will not be published. Required fields are marked *

    14 − thirteen =