+7 (812) 670-9095
Обратная связьEnglish
Главная → Статьи → Системное ПО → Архитектура приложений с открытым исходным кодом: LLVM
Полезный совет
Почему премия попадает во 2 раздел отчета 6-НДФЛ отдельным блоком с датой фактического получения дохода, отличной от даты начисления дохода?Подробнее
Версия для печати

Архитектура приложений с открытым исходным кодом: LLVM

22 сентября 2017

АстроСофт занимается компиляторами с 1999 года. В нашем активе — собственны универсальный компилятор UCC, позволяющий быстро создавать компиляторы под целевые платформы заказчика. При этом мы разрабатываем и остальные компоненты SDK: ассемблер, линкер, отладчик и др.

В 2017 году в АстроСофт стартовало несколько проектов по разработке полномасштабных LLVM-компиляторов, и наши эксперты подготовили перевод статей, посвященных LLVM. Представляем первую статью из этого цикла.

Автор: Сhris Lattner.

Источник: The Architecture Of Open Source Applications, том 1, глава 11.




LLVM (Low level virtual machine) [1] — комплексный проект, ведущий разработку набора тесно связанных низкоуровневых инструментальных средств (в т. ч. компоновщиков, компиляторов, отладчиков и т. д.), совместимых с уже существующими средствами разработки, обычно для Unix-систем. «LLVM» раньше была аббревиатурой, но сейчас стала зонтичным брендом. При том, что LLVM предоставляет уникальные возможности и известна своими выдающимися инструментами (например, Clang [2] — C/C++/Objective-C компилятор, превосходящий GCC по ряду параметров), ее отличительной особенностью является внутренняя архитектура.

Начиная со своего появления в декабре 2000 года, LLVM разрабатывалась как набор повторно используемых библиотек с четко определенными интерфейсами. На тот момент языки написания ПО с открытым исходным кодом являлись узкоспециализированными инструментами с монолитными исполняемыми модулями. Например, было очень сложно повторно использовать парсер из статического компилятора (например, GCC) для статического анализа или рефакторинга. Многие скриптовые языки предоставляли способ внедрения собственной среды выполнения и интерпретатора в более крупные приложения, однако среда выполнения была монолитным куском кода, который либо полностью встраивался в приложение, либо нет. Было невозможно повторно использовать составляющие среды, а между реализациями языков было мало общего.

Компиляторы, как и сообщества разработчиков популярных реализаций языков, были строго полярными: обычно реализация предоставляла либо традиционный статический компилятор (GCC, Free Pascal, FreeBASIC), либо динамический в виде интерпретатора или компилятора «на лету» (англ. Just-In-Time, JIT). Реализация языка, поддерживающая оба вида компиляторов, была очень редкой и содержала мало повторно используемого кода.

За последние десять лет LLVM значительно изменила ситуацию. Сегодня она используется в качестве единой инфраструктуры для реализации широкого разнообразия языков, компилируемых как статически, так и динамически (например, семейство языков, поддерживаемых GCC, Java, .NET, Python, Ruby, Scheme, Haskell, D и другие менее известные языки). Она также заменила множество специализированных компиляторов, таких как механизм специализации среды выполнения в OpenGL от Apple и библиотеку обработки изображений в Adobe After Effects. LLVM использовалась для создания множества новых продуктов, самым известным из которых является среда выполнения и язык программирования GPU OpenCL.

Краткое введение в классическое проектирование компиляторов
Самый популярный подход к проектированию стандартного статического компилятора (большинство компиляторов C) состоит из трех этапов: проектирование фронтенда, оптимизатора и бэкенда. Фронтенд проводит синтаксический анализ исходного кода, проверяет его на наличие ошибок и формирует представление в виде абстрактного синтаксического дерева (АСД). Затем дерево может быть конвертировано в иное представление в целях оптимизации, а оптимизатор и бэкенд приступают к работе.

Рисунок 1. Состав трехэтапного компилятора.
Рисунок 1. Состав трехэтапного компилятора.

Оптимизатор осуществляет множество преобразований (например, устранение избыточных вычислений) для сокращения времени выполнения кода и обычно независим от исходного и целевого языков. После этого бэкенд (также известный как генератор кода) устанавливает соответствие кода с набором инструкций целевого языка. Он отвечает за формирование не только правильного, но и качественного кода, который использует преимущества особенностей поддерживаемой архитектуры. Бэкенд компилятора обычно состоит из выбора инструкций, распределения регистропланирования команд.

Эта модель успешно применяется как к интерпретаторам, так и к JIT-компиляторам. Виртуальная машина Java (англ. Java Virtual Machine, JVM) также является реализацией этой модели и использует байт-код Java в качестве интерфейса между фронтендом и оптимизатором.

Реализации трехэтапной модели
Главное преимущество такой классической модели — адаптируемость. Оно становится очевидным, когда компилятору необходимо поддерживать множество исходных языков или целевых архитектур. Если оптимизатор компилятора использует общее представление кода, то фронтенд может быть написан под любой язык, способный сформировать это представление, а бэкенд может быть написан для любой целевой архитектуры, которая способна воспринять такое представление (см. рисунок 2).


Рисунок 2. Адаптируемость.
Рисунок 2. Адаптируемость.

При использовании такой модели портирование компилятора для поддержки нового исходного языка (например, Algol или BASIC) требует реализовать только новый фронтенд, а существующий оптимизатор и бэкенд могут быть использованы повторно. Если бы эти части были одним целым, реализация поддержки нового исходного языка потребовала бы написания компилятора с нуля, то есть поддержка N целевых архитектур и M исходных языков потребовала бы N*M компиляторов.

Другое преимущество трехэтапной модели заключается в том, что благодаря адаптируемости компилятор способен вовлечь большее количество программистов в свою разработку. Для проекта с открытым исходным кодом это означает большее количество энтузиастов, готовых внести свой вклад. Это приводит к росту количества и качества улучшений, вносимых в компилятор. Поэтому распространенные компиляторы с открытым исходным кодом (например, GCC) генерируют лучше оптимизированный машинный код, чем узкоспециализированные компиляторы (например, Free PASCAL). Это не касается проприетарных компиляторов, качество которых напрямую зависит от бюджета проекта. Например, компилятор Intel ICC широко известен высоким качеством генерируемого кода, несмотря на то, что он предназначен для узкой аудитории.

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


Существующие реализации языков

Несмотря на то, что преимущества трехэтапной модели подробно описаны в пособиях по компиляторам, на практике они редко воплощаются в полной мере. Рассмотрев несколько реализаций языков с открытым исходным кодом (созданных в то время, когда появилась LLVM), можно обнаружить, что различные реализации Perl, Python, Ruby и Java не имеют общего кода. А такие проекты, как Glasgow Haskell Compiler (GHC) и FreeBASIC, хотя и могут быть адаптированы для различных CPU, но очень специфичны и тесно связаны с одним исходным языком. Кроме того, существует множество узкоспециализированных технологий компиляции, созданных для применения в JIT-компиляторах для обработки изображений, регулярных выражений, драйверов видеокарт и других сфер с интенсивной вычислительной нагрузкой на CPU.

Существуют три наиболее успешные реализации трехэтапной модели, первой из которых являются виртуальные машины Java и .NET. Эти системы предоставляют JIT-компилятор, средство динамической поддержки и четко определенный формат байт-кода. Это означает, что любой язык, который может быть транслирован в байт-код (а таких существуют десятки [3]) может использовать преимущества оптимизатора и JIT-компилятора, а также среды выполнения. Недостатком является то, что обе реализации не обладают гибкостью при выборе среды выполнения. Они фактически навязывают JIT-компиляцию, сборку мусора и использование строго определенной объектной модели. Это приводит к неоптимальной производительности при компиляции языков, не соответствующих данной модели, например, С и проект LLJVM.

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

Последняя успешная реализация трехэтапной модели — GCC. Она поддерживает множество фронтендов и бэкендов и имеет большое активное сообщество. GCC долго являлась компилятором С, поддерживающим множество целевых архитектур и оставляющим желать лучшего при поддержке других исходных языков. Со временем сообщество GCC прогрессировало и создало более качественной продукт. В версии GCC 4.4 появилось новое представление оптимизатора (GIMPLE Tuples), которое становится все менее связанным с фронтендом. Кроме того, фронтенды GCC для Fortran и Ada используют чистое АСД.

Несмотря на то, что эти три подхода очень успешны, они имеют строгие ограничения, касающиеся их применения, так как они разрабатывались как монолитные продукты. Например, невозможно встроить GCC в другие приложения, чтобы использовать его в качестве динамического/JIT-компилятора, также невозможно извлечь и повторно использовать участки кода GCC отдельно от остальной части компилятора. Разработчики, намеренные использовать C++ фронтенд GCC в генерации документации, индексировании кода, рефакторинге и статических инструментах анализа, были вынуждены использовать GCC как монолитное приложение, производящее информацию в формате XML или писать плагины для внедрения стороннего кода в GCC.

Существуют несколько причин, по которым части GCC нельзя повторно использовать в качестве библиотек: широкое использование глобальных переменных, слабая защищенность инвариантов, неэффективные структуры данных, большой объем кодовой базы и использование макросов, препятствующих компиляции кодовой базы для одновременной поддержки нескольких пар фронтенд/целевая архитектура. Самыми сложными являются наследственные архитектурные проблемы, появившиеся на ранних этапах проектирования и создания компилятора. В частности, GCC имеет проблемы с иерархией и дырявыми абстракциями: бэкенд использует АСД фронтенда для генерации отладочной информации, фронтенды генерируют структуры данных бэкенда, а весь компилятор зависит от структур глобальных данных, задаваемых интерфейсом командной строки.


Представление кода LLVM: LLVM IR

Теперь, зная предысторию, давайте окунемся в мир LLVM. Главной особенностью LLVM является промежуточное представление кода (англ. Intermediate Representation, IR), форма, которую использует LLVM для представления кода в компиляторе. LLVM IR был разработан для выполнения функций промежуточного анализа и преобразований внутри оптимизатора компилятора. Ее создание имело целью решение множества специализированных задач, включая поддержку легковесных оптимизаций среды выполнения, кроссфункциональные и межпроцедурные оптимизации, полный анализ программы и агрессивные реструктурирующие преобразования. Промежуточное представление кода определено как язык первого порядка с четкой семантикой. Для наглядности ниже представлен пример .ll файла.



define i32 @add1(i32 %a, i32 %b) {
entry:
  %tmp1 = add i32 %a, %b
  ret i32 %tmp1
}

define i32 @add2(i32 %a, i32 %b) {
entry:
  %tmp1 = icmp eq i32 %a, 0
  br i1 %tmp1, label %done, label %recurse

recurse:
  %tmp2 = sub i32 %a, 1
  %tmp3 = add i32 %b, 1
  %tmp4 = call i32 @add2(i32 %tmp2, i32 %tmp3)
  ret i32 %tmp4

done:
  ret i32 %b
}


Этот LLVM IR соответствует следующему коду на языке C, обеспечивающему возможность сложения целых чисел двумя разными способами:



unsigned add1(unsigned a, unsigned b) {
  return a+b;
}

// возможно не самый лучший способ сложения двух чисел
unsigned add2(unsigned a, unsigned b) {
  if (a == 0) return b;
  return add2(a-1, b+1);
}


Как видно из этого примера, LLVM IR — низкоуровневый RISC-подобный набор виртуальных инструкций. Как и настоящий набор инструкций RISC, он поддерживает линейные последовательности простых инструкций (сложение, вычитание, сравнение и ветвление). Эти инструкции имеют трехадресную форму. Это значит, что они берут некоторое количество входных данных и вычисляют результат в другом регистре. LLVM IR поддерживает метки и в целом выглядит как необычная форма языка ассемблера.

В отличие от большинства наборов инструкций RISC, LLVM тесно связана с системой простых типов (например, i32 — 32-битное целое число, i32** — указатель на указатель 32-битного целого числа), а некоторые детали, присущие машинному коду, опущены. Например, соглашение о вызове абстрагируется при помощи заданных в явном виде аргументов и инструкций call и set. Другое значительное отличие от машинного кода: LLVM IR использует бесконечный набор временных регистров (начинаются с символа %), а не фиксированный набор именованных регистров.

Помимо того, что LLVM IR реализован в форме языка, он имеет три изоморфические формы: текстовая форма, структура данных в памяти (проверяемая и модифицируемая самими оптимизациями) и двоичный «бит-код». LLVM также предоставляет инструменты для конвертирования текстового формата в двоичный: llvm-as собирает текстовый файл .ll в файл .bc, который содержит бит-код, а llvm-dis превращает файл .bc в файл .ll.

Промежуточное представление в компиляторе интересно тем, что оно может быть «идеальным миром» для оптимизатора компилятора: в отличие от фронтенда и бэкенда, оптимизатор не ограничен каким-либо исходным языком или определенной целевой аппаратной частью. Но обоим он должен превосходно служить: обеспечивать простоту генерации фронтенду и быть достаточно выразительным, чтобы предоставлять возможность оптимизации для целевых архитектур.

Оптимизация LLVM IR

Чтобы понять, как работает оптимизация, необходимо разобрать несколько примеров. Существует множество видов оптимизаций компиляторов, поэтому сложно предоставить универсальную инструкцию по решению любой задачи. Большинство оптимизаций имеют простую структуру:

  • поиск паттерна для преобразования;
  • проверка безопасности/корректности преобразования;
  • преобразование с внесением изменений в код.

Самая простая оптимизация состоит из поиска арифметических паттернов (например, для любого целого числа x, x-x=0,x-0=x, a(x*2)-x=x). В LLVM IR эти выражения будут выглядеть следующим образом:



?    ?    ?
%example1 = sub i32 %a, %a
?    ?    ?
%example2 = sub i32 %b, 0
?    ?    ?
%tmp = mul i32 %c, 2
%example3 = sub i32 %tmp, %c
?    ?    ?



Для таких «узких» преобразований LLVM предоставляет интерфейс упрощения инструкций, используемый во многих преобразованиях более высокого уровня. Ниже представлены преобразования функции SimplifySubInst:



// X - 0 -> X
if (match(Op1, m_Zero()))
  return Op0;

// X - X -> 0
if (Op0 == Op1)
  return Constant::getNullValue(Op0->getType());

// (X*2) - X -> X
if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())))
  return Op1;

…

Return 0; //Совпадений нет, возвращает null, чтобы показать что преобразований не было


Здесь, Op0 и Op1 — левый и правый операнд инструкции вычитания целых чисел (важно заметить, что они не всегда соответствуют стандарту IEEE, описывающему представление чисел с плавающей точкой). LLVM написана на С++, который не славится своими возможностями в сравнении паттернов (в отличие от функциональных языков, например, Objective Caml), но предлагает обобщенную систему шаблонов, позволяющую реализовывать нечто похожее. Функции match и m_ позволяют выполнять описательное сравнение паттернов при помощи кода промежуточного представления LLVM. Например, предикат m_Specific показывает совпадение, только если левая часть умножения идентична Op1.

Вместе эти три случая сравниваются с паттернами, а функция возвращает замену или нулевой указатель, если замена невозможна. Функцию SimplifyInstructionвызывает диспетчер, который переключает код операции и передает его на вспомогательные функции кодов операции. Эта функция вызывается во многих оптимизациях. Ниже представлен пример простого драйвера:



for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
  if (Value *V = SimplifyInstruction(I))
I-> replaceAllUsesWith(V);


Этот код просто запускает цикл поиска по каждой инструкции в блоке, проверяя их на возможность упрощения. Если SimplifyInstruction возвращает ненулевое значение, используется метод replaceAllUsesWith для замены конструкций кода на их упрощенные аналоги.


Реализация трехэтапной модели в LLVM

В основанном на LLVM компиляторе фронтенд отвечает за синтаксический анализ, валидацию и диагностику ошибок в исходном коде, затем он транслирует код в промежуточное представление LLVM IR (обычно, для этого строится АСД, а затем оно преобразуется в LLVM IR). Промежуточное представление пополняется за счет операций анализа и оптимизационных проходов, улучшающих код. Затем представление отправляется на генератор кода для составления нативного машинного кода (см. рисунок 3). Это простая реализация трехэтапной модели, но такое описание подчеркивает мощность и гибкость, которую обеспечивает LLVM при помощи промежуточного представления кода.


Рисунок 3. Реализация трехфазной модели LLVM
Рисунок 3. Реализация трехфазной модели LLVM.


Промежуточное представление кода LLVM IR — полное представление кода

Строго говоря, промежуточное представление LLVM является четко определенным и единственным интерфейсом оптимизатора. Это означает, что всё, что необходимо знать, чтобы писать фронтенды для LLVM, это: что такое LLVM IR, как он работает и какие инварианты ему необходимы. Так как LLVM IR имеет текстовую форму, то имеет смысл создавать фронтенд, который выводит LLVM IR в виде текста, а затем отправляет его на оптимизатор и необходимый генератор кода при помощи каналов Unix.

Это новое свойство LLVM, и именно оно является одной из причин успеха во множестве приложений. Даже успешный компилятор GCC с относительно эффективной архитектурой не обладает этим качеством: его промежуточное представление GEMPLE не является замкнутым. Например, когда генератор кода GCC выдает отладочную информацию DWARF, он возвращается назад и проходит по исходному древовидному представлению. GIMPLE использует кортежное представление для операций в коде, но (по крайней мере, в GCC 4.5) все еще представляет операнды в виде ссылок на исходное представление.

Следствие этого: для создания GCC-фронтенда его разработчики должны разбираться как в древовидных структурах данных GCC, так и в GIMPLE. Бэкенд GCC обладает похожими проблемами, а значит разработчикам необходимо знать, как устроен бэкенд RTL. Наконец, GCC не позволяет отображать «всё, что представляет мой код», а также читать и записывать GIMPLE (и относящиеся к нему структуры данных, формирующие представление кода) в текстовом формате. В результате, экспериментировать с GCC достаточно сложно, и из-за этого он имеет довольно мало фронтендов.


LLVM — набор библиотек

Помимо промежуточного представления кода, важной особенностью LLVM является то, что она представляет из себя набор библиотек, а не виртуальную машину (JVM или .NET VM) или монолитный компилятор, запускаемый из командной строки. LLVM — инфраструктура, набор технологий компиляции, которые можно использовать для решения определенных задач (например, для создания компилятора C, или оптимизатора). Это не только одно из главных достоинств LLVM, но и наиболее сложный для понимания аспект.

Рассмотрим оптимизатор в качестве примера: он берет данные из LLVM IR, обрабатывает их и выдает промежуточное представление кода, которое будет работать быстрее. В LLVM, как и во множестве других компиляторов, оптимизатор представляет собой конвейер различных оптимизационных проходов, каждый из которых применяется к исходному коду с целью его улучшения. Примерами проходов являются встраивание кода (вставляет тело функции в места вызова функции), реассоциация выражений, вынос инвариантного кода за тело цикла и т.д. В зависимости от уровня оптимизации используются различные проходы: например, на уровне –O0 (без оптимизации) компилятор Clang не проводит оптимизацию, на уровне –O3 он выполняет 67 проходов (в LLVM 2.8).

Каждый проход LLVM написан на C++ и представляет из себя класс, унаследованный от класса Pass. Большинство проходов состоят из одного файла .cpp, а их подкласс класса Pass определен в анонимном пространстве имен (благодаря чему, он доступен только для определяющего файла). Чтобы проход был полезен, он должен быть доступен для внешнего кода, для чего из файла экспортируется одна функция (для вызова прохода). Ниже представлен немного упрощенный вариант прохода [4]:


namespace {
  class Hello : public FunctionPass {
  public:
    // Print out the names of functions in the LLVM IR being optimized.
    virtual bool runOnFunction(Function &F) {
      cerr << "Hello: " << F.getName() << "\n";
      return false;
    }
  };
}
FunctionPass *createHelloPass() { return new Hello();}



Как было сказано выше, оптимизатор LLVM предоставляет десятки различных проходов, написанных в едином стиле. Эти проходы компилируются в один или несколько файлов , которые затем встраиваются в набор архивных библиотек (файлов на системах Unix). Эти библиотеки предоставляют различные механизмы анализа и преобразований, а проходы взаимосвязаны настолько слабо, насколько это возможно: они должны быть самостоятельными или декларировать зависимости от других проходов. При выполнении набора проходов LLVM PassManager использует декларации о зависимостях для их соблюдения и повышения эффективности проходов.

Библиотеки и абстрактные инструменты — это, конечно, хорошо, но они не решают задач. Самое интересное начинается, когда кто-то хочет создать новый инструмент, который будет использовать преимущества технологии компиляции, например, JIT-компилятор для языка обработки изображений. При разработке такого компилятора нужно иметь в виду, что язык обработки изображений очень чувствителен к задержке времени компиляции и имеет характерные свойства, требующие оптимизации для улучшения производительности.

Библиотечная структура оптимизатора LLVM позволяет выбирать как порядок выполнения проходов, так и сами проходы, необходимые именно для обработки изображений: если все описывается одной большой функцией, встраивание кода не имеет смысла. Также, при наличии маленького количества указателей, не стоит беспокоится об анализе псевдонимов и оптимизации памяти. Однако LLVM не решает все задачи оптимизации. Так как подсистема проходов разбита на модули, PassManager ничего не знает о внутреннем устройстве проходов, пользователь может написать собственный проход для конкретного языка, чтобы избавиться от недостатков оптимизатора LLVM или использовать специфичный для данного языка проход. Рисунок 4 показывает пример гипотетической системы обработки изображений:

Рисунок 4. Гипотетическая система обработки изображений, построенная при помощи LLVM.
Рисунок 4. Гипотетическая система обработки изображений, построенная при помощи LLVM.


Как только выбран набор оптимизаций (и соответствующие решения приняты для генератора кода), компилятор обработки изображений встраивается в исполняемую или динамическую библиотеку. Так как единственные ссылки на проходы LLVM — функции create, определенные в каждом файле .o, а оптимизатор находится в архивных библиотеках .a, в приложение попадают только действительно используемые проходы, а не весь оптимизатор LLVM. В случае, рассмотренном выше, так как существует ссылка на PassA и PassB, они будут включены в программу. PassD входит в программу, так как PassB использует PassD для анализа. Однако из-за того, что PassC (и десятки других проходов) не используются, их код не включается в приложение для обработки изображений.

Здесь проявляются преимущества библиотечной структуры LLVM. Такая простая структура позволяет LLVM обеспечивать широкие возможности, многие из которых могут быть полезны только узкому кругу людей, не причиняя неудобств пользователям библиотек, которым нужны только простые инструменты. С другой стороны, традиционные оптимизаторы компиляторов построены как тесно взаимосвязанные участки кода, в которых сложно разобраться. В LLVM отдельные оптимизаторы понятны и не требуют знания всей системы.

Библиотечная структура является причиной, по которой множество людей не понимают главной особенности LLVM: библиотеки LLVM предоставляют множество возможностей, но сами по себе они ничего не делают. Разработчик клиента (например, компилятора Clang) должен решить, как использовать эти библиотеки. LLVM может использоваться в различных приложениях и контекстах благодаря тщательному разграничению уровней, модульности и сосредоточенности на разбиение на независимые составляющие. То, что LLVM включает в себя JIT-компилятор, не значит, что каждый клиент его использует.


Структура адаптируемого генератора кода LLVM

Генератор кода LLVM отвечает за преобразование кода LLVM IR в целевой машинный язык, т.е. его задача — формировать наилучший машинный код для каждого целевого языка. В идеале каждый генератор кода должен быть создан специально для каждого целевого языка, но с другой стороны, генераторы кода каждого целевого языка решают похожие задачи. Например, каждый целевой язык должен задавать значения регистрам и, несмотря на то, что все языки имеют разные файлы регистра, используемые для присвоения им значений, алгоритмы следует как можно чаще использовать повторно.

Как и оптимизатор, генератор кода LLVM делит задачу генерации кода на различные проходы: выбор инструкций, распределение регистров, планирование, оптимизация структуры кода и генерация кода ассемблера. Кроме того, генератор кода содержит множество встроенных проходов, используемых по умолчанию. Разработчик целевого языка имеет возможность выбора проходов, изменения значений по умолчанию и реализации абсолютно новых пользовательских проходов. Например, бэкенд x86 использует планировщик, уменьшающий дефицит регистров, так как он имеет очень мало регистров, а бэкенд PowerPC использует планировщик, оптимизирующий задержку, так как у него регистров много. Бэкенд x86 использует пользовательский проход для обработки стека с плавающей точкой x87, а бэкенд ARM использует пользовательский проход для расположения набора констант внутри функций, где это необходимо. Такая гибкость позволяет разработчикам целевых языков писать качественный код без написания всего генератора кода с нуля.


Файлы описания целевых языков LLVM

Сочетание и комбинирование позволяют разработчикам целевых языков выбирать инструменты архитектуры и способствуют масштабному повторному использованию кода среди различных целевых языков. Это приводит к другой проблеме: каждый общий компонент должен обладать информацией об особенностях целевого языка. Например, общий распределитель регистров должен знать файл регистра каждого целевого языка и существующие между инструкциями и их операндами ограничения. В LLVM эта проблема решена за счет предоставления описания целевого языка на предметно-ориентированном декларативном языке (набор файлов .td), обработанного при помощи инструмента tblgen. Упрощенный процесс формирования целевой программы для архитектуры x86 показан на рисунке 5.


Рисунок 5. Упрощенный процесс формирования целевой программы.
Рисунок 5. Упрощенный процесс формирования целевой программы.


Различные подсистемы, поддерживаемые файлами .td, позволяют разработчикам формировать различные части их целевой программы. Например, бэкенд x86 определяет класс регистра, содержащий все 32-битные регистры под названием «GR32» (в файлах .td уникальные определения целей записаны заглавными буквами), например:



def GR32 : RegisterClass<[i32], 32,
  [EAX, ECX, EDX, ESI, EDI, EBX, EBP, ESP,
   R8D, R9D, R10D, R11D, R14D, R15D, R12D, R13D]> { … }



Это определение говорит о том, что регистры в этом классе могут содержать 32-битные целые числа («i32»), предпочтительно с гранулярностью, равной 32 бита; имеют вышеперечисленные 16 регистров, которые определены в других .td-файлах; и имеют больше информации о предпочтительном порядке распределений и др. Инструкции могут ссылаться на это определение, используя его в качестве операнда. Например, инструкция«complement a 32-bit register» выглядит следующим образом:



let Constraints = "$src = $dst" in
def NOT32r : I<0xF7, MRM2r,
               (outs GR32:$dst), (ins GR32:$src),
               "not{l}\t$dst",




Это определение говорит о том, что регистры в этом классе могут содержать 32-битные целые числа («i32»), предпочтительно с гранулярностью, равной 32 бита; имеют вышеперечисленные 16 регистров, которые определены в других .td-файлах; и имеют больше информации о предпочтительном порядке распределений и др. Инструкции могут ссылаться на это определение, используя его в качестве операнда. Например, инструкция «complement a 32-bit register» выглядит следующим образом:



let Constraints = "$src = $dst" in
def NOT32r : I<0xF7, MRM2r,
               (outs GR32:$dst), (ins GR32:$src),
               "not{l}\t$dst",
               [(set GR32:dst, (not GR32:$src))]>;


Согласно этому определению, NOT32r — инструкция (она использует класс I из tblgen), содержащая информацию о кодировке (0xF7, MRM2r), определения 32-битного регистра выхода $dst и 32-битного регистра входа $src (класс регистра GR32 определяет, какие регистры могут быть использованы в качестве операнда), определяющая синтаксис сборки для инструкции (используя синтаксис {} для обработки синтаксиса AT&T и Intel), а также содержащая описание результата, который предоставляет инструкция, и паттерна, которому она должна соответствовать в последней строчке. Ограничение let в первой строчке сообщает распределителю регистров, что регистры входа и выхода должны соответствовать одному физическому регистру.

Такое определение — очень емкое описание инструкции, и общий код LLVM при помощи инструмента tblgen может извлечь из него много полезной информации. Одного такого определения достаточно, чтобы на этапе выбора инструкций при помощи сравнения исходного промежуточного представления кода с паттерном формировалась инструкция для компилятора. Оно также содержит достаточно информации об обработке инструкции, чтобы распределитель регистров мог зашифровать и расшифровать инструкцию в машинный код, и чтобы парсить и выводить инструкцию в текстовой форме. Эти особенности позволяют целевой архитектуре x86 поддерживать независимый ассемблер x86 (который является упрощенной заменой GNU ассемблера gas) и дизассемблеры, исходя из ее описания, а также выполнять шифрование инструкции для JIT.

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

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


Интересные возможности модульной структуры

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


Выбор времени и места старта каждой фазы компиляции

Как было сказано ранее, LLVM IR может быть эффективно сериализован и десериализован в/из двоичного формата (LLVM бит-код). Так как LLVM IR самодостаточен, а сериализация — процесс без потерь, можно выполнить часть компиляции, сохранить прогресс на диск и продолжить работу позже. Эта особенность предоставляет некоторые интересные возможности, включая поддержку оптимизации во время компоновки и установки, что увеличивает время генерации кода по сравнению с временем компиляции.

Оптимизация во время компоновки (англ. Link-Time Optimization, LTO) решает проблему, при которой компилятор видит только одну единицу трансляции (например, файл .c и все его заголовочные файлы) одновременно и не может выполнять оптимизации (например, встраивание кода) за пределами этого файла. LLVM-компиляторы, например, Clang, делает это при помощи команд –flto или –O4. Эти команды инструктируют компилятор записывать бит-код в файл .o вместо создания собственного объектного файла, а также задерживают генерацию кода до времени компоновки (см. рисунок 6).

Рисунок 6. Оптимизация во время компоновки.

Рисунок 6. Оптимизация во время компоновки.


В зависимости от операционной системы меняются детали, но основная часть остается неизменной: компоновщик распознает, что он имеет дело с файлами .o, содержащими бит-код, а не с собственными объектными файлами. Он считывает файлы с бит-кодом в память, компонует их, а затем запускает оптимизатор LLVM. Благодаря тому, что теперь оптимизатор может видеть гораздо большую часть кода, он может выполнять встраивание кода, подстановку констант, более агрессивное удаление мертвого кода. Многие современные компиляторы поддерживают LTO, однако большинство из них (например, GCC, Open64, Intel compiler и т.д.) делают это при помощи ресурсоемкого и медленного процесса сериализации. В LLVM LTO естественным образом происходит из структуры системы и работает с различными исходными языками (в отличие от множества других компиляторов), благодаря тому, что промежуточное представление кода не зависит от исходного языка.

Идея оптимизации во время установки заключается в откладывании генерации кода еще дальше — до времени установки, как показано на рисунке 7. Время установки — очень интересное время (в случае, когда программное обеспечение поставляется в коробке, скачивается, загружается на мобильное устройства и т.д.), так как именно в этот момент становится доступна информация о характеристиках целевого устройства. В семействе x86, например, существует множество чипов и характеристик. За счет задержки при выборе инструкции, планирования и других аспектов генерации кода, можно подобрать наилучший вариант для аппаратного обеспечения, на котором будет работать приложение.


Рисунок 7. Оптимизация во время установки.

Рисунок 7. Оптимизация во время установки.


Модульное тестирование оптимизатора

Компиляторы очень сложно устроены, их качество важно, а, следовательно, критически важно и тестирование. Например, после исправления ошибки, вызывавшей сбой приложения, необходимо провести регрессионное тестирование, чтобы убедиться, что это не повторится. Классический подход к такому тестированию — создать файл .c (например), пропустить его через компилятор и проверить, чтобы компилятор не дал сбой при помощи тестовой программы. Такой подход используется в пакете программ для тестирования GCC.

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

За счет использования текстовой формы LLVM IR и модульного оптимизатора, пакет программ для тестирования LLVM содержит сфокусированные регрессионные тесты, способные загрузить LLVM IR с диска, запустить один цикл оптимизации и проверить ожидаемое поведение. Помимо обнаружения сбоя, более продвинутые тесты режимов функционирования выявляют, проводилась ли оптимизация. Ниже приведен простой тест, который проверяет работу подстановки констант с инструкциями сложения:



; RUN: opt < %s -constprop -S | FileCheck %s
define i32 @test() {
  %A = add i32 4, 5
  ret i32 %A
  ; CHECK: @test()
  ; CHECK: ret i32 9
}


RUN указывает, какую команду необходимо выполнить, в данном случае: инструменты opt и FileCheck. Программа opt — простая функция-обертка менеджера проходов LLVM, которая компонует все стандартные проходы (и может динамически загружать плагины, содержащие другие проходы) и делает их доступными через командную строку. Инструмент FileCheck проверяет, чтобы его стандартные входные значения соответствовали набору директив CHECK. В этом случае простой тест проверяет, чтобы проход constprop сворачивал функцию (add i32 4, 5) в 9.

Это может показаться очень тривиальным примером, но его сложно проверить при помощи написания файлов .c: фронтенды часто сворачивают константы при парсинге, так что написать код, который доберется до прохода оптимизации сворачивания констант, очень сложно. Так как мы можем загружать LLVM IR в виде текста, пропускать его через интересующий нас проход и выгружать результат в другой текстовый файл, то проводить нужное нам тестирование очень просто. Это касается как регрессионных тестов, так и тестирования новых функций.


Автоматическое уменьшение количества тестов при помощи BugPoint

Когда в компиляторе или другом клиенте библиотек LLVM найдена ошибка, первый шаг к ее исправлению — составление теста, который бы точно воспроизводил проблему. Когда такой тест получен, стоит свести его к наименьшему примеру, воспроизводящему ошибку, и выделить ту часть LLVM, в которой появляется ошибка (например, в проходе оптимизации). Со временем вы научитесь делать это, но это утомительный и трудоёмкий ручной процесс, особенно, когда компилятор генерирует неправильный код, но при этом не вылетает.

Инструмент LLVM BugPoint [5] использует сериализацию промежуточного представления кода и модульную структуру LLVM для автоматизации этого процесса. Например, получая на вход .ll или .bc файл вместе со списком оптимизационных проходов, которые вызывают вылет оптимизатора, BugPoint сводит входные данные к небольшому тесту и определяет, какой именно оптимизатор вызывает ошибку. Затем он выводит тест и использует команду opt, чтобы воспроизвести ошибку. При этом, для уменьшения объема входных данных и списка оптимизационных проходов используется метод, похожий на дельта-отладку. Так как BugPoint знает структуру промежуточного представления кода, ему не требуется тратить время на генерацию ошибочных промежуточных представлений для оптимизатора, в отличие от стандартного инструмента delta.

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

BugPoint — очень простой инструмент, который помог сэкономить бесчисленное множество часов тестирования за время существования LLVM. Ни один другой компилятор с открытым исходным кодом не обладает таким мощным инструментом, так как он зависит от четко определенного промежуточного представления. Однако BugPoint не идеален, и ему не помешает переработка. BugPoint вышел в 2002 году и обновляется лишь тогда, когда кто-то натыкается на необычную ошибку, с которой инструмент не справляется должным образом. Он развивается и со временем обрастает новыми функциями (например, отладка JIT), не имея постоянной структуры или владельца.


Прошлое и будущее LLVM

Изначально модульная структура LLVM не разрабатывалась для достижения описанных выше целей. Она была механизмом самозащиты: было очевидно, что мы не сможем сделать все правильно с первого раза. Так, модульный конвейер проходов был создан для упрощения процесса изоляции проходов, чтобы их можно было легко отбросить при появлении лучших вариантов.

Другим важным аспектом гибкости LLVM является желание пересматривать наши решения и вносить обширные изменения в API, не волнуясь об обратной совместимости. Крупные изменения в промежуточном представлении кода LLVM требуют обновления всех оптимизационных проходов и значительного пересмотра API C++. Мы делали это несколько раз и, несмотря на то, что это причиняет неудобства пользователям, это верный путь к поддержанию быстрого развития. Чтобы сделать жизнь внешних клиентов проще (и для поддержки других языков), мы предоставляем функции-обертки на С для многих распространенных API (максимально стабильных), а новые версии LLVM будут способны читать старые файлы .ll и .bc.

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

Проект LLVM продолжает расти и развиваться в различных направлениях. Мы рады видеть разнообразие применений LLVM в других проектах и то, как он продолжает появляться в тех местах, о которых его разработчики даже и не думали. Новый отладчик LLDB — хороший пример: он использует C/C++/Objective-C парсеры из Clang, чтобы парсить выражения, использует LLVM JIT для их перевода в целевой код, использует LLVM дизассемблеры и целевые программы LLVM для обработки соглашений о вызове. Возможность повторного использования уже существующего кода позволяет разработчикам отладчиков фокусироваться на написании логики отладчика, вместо реализации очередного парсера C++ с нуля.

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


Список литературы
  1. http://llvm.org
  2. http://clang.llvm.org
  3. http://en.wikipedia.org/wiki/List_of_JVM_languages
  4. http://llvm.org/docs/WritingAnLLVMPass.html
  5. http://llvm.org/docs/Bugpoint.html

Теги: компилятор, LLVM