LLVM

Глава 11 из книги "Архитектура приложений с открытым исходным кодом", том 1.

Оригинал: LLVM
Автор: Chris Lattner
Перевод: А.Панин

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

После краткого экскурса в историю, давайте перейдем к подробному рассмотрению проекта LLVM: наиболее важным аспектом его архитектуры является использование промежуточного представления кода LLVM (LLVM Intermediate Representation - IR), являющегося формой для представления кода компилятором. Представление 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 и ret с очевидными аргументами. Другим кардинальным отличием от машинного кода является использование представлением LLVM IR бесконечного числа временных переменных с именами, начинающимися с символа %, вместо ограниченного набора именованных регистров.

Хотя представление LLVM IR и реализовано в форме языка, оно может быть представлено в виде трех изоморфных форм: в текстовом формате, описанном выше, в виде структур для хранения в памяти, исследуемых и изменяемых оптимизатором, и в виде эффективного и сжатого "биткода" для хранения на диске. Проект LLVM также предоставляет инструменты для преобразования хранящегося на диске представления из текстового в бинарный формат: llvm-as преобразует текстовый файл с расширением .ll в сжатый бинарный файл биткода с расширением .bc, а llvm-dis преобразует файл с расширением .bc в файл с расширением .ll.

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

11.3.1. Разработка алгоритмов оптимизаций для LLVM IR

Наиболее тривиальной оптимизацией является оптимизация арифметических тождеств с помощью шаблонов, например: для любого целочисленного значения X, X-X является 0, X-0 является X, (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;  // Совпадений не найдено, возвращается нулевое значение для указания на отсутствие преобразований.

В данном коде значения Op0 и Op1 привязаны к левому и правому операндам инструкции целочисленного вычитания (важно отметить, что эти обозначения не должны обязательно сохраняться для инструкций, работающих с числами с плавающей точкой IEEE!) LLVM реализован с использованием языка C++, который не является широко известным благодаря своим функциям для работы с шаблонами (в отличие от таких функциональных языков, как Objective Caml), но предоставляет чрезвычайно обобщенную систему шаблонов, которая позволяет нам реализовать подобные механизмы. Функция match и функции с префиксом m_ позволяют нам осуществлять операции декларативного сопоставления шаблонов в коде представления LLVM IR. Например, функция 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 для замены всех операций в коде на их упрощенную форму.

Сноски

Далее: 11.4. Реализация архитектуры трех фаз в LLVM