Я планировал написать статью о том, как LLVM оптимизирует функцию, но сначала необходимо написать, как Clang транслирует C или C++ в LLVM.




Рассмотрим высокоуровневые аспекты, не погружаясь в глубины Clang. Я хочу обратить внимание на то, как вывод Clang соотносится с входом, при этом мы не будем рассматривать нетривиальные возможности С++. Мы используем эту маленькую функцию, которую я позаимствовал из прекрасных лекций по цикловым оптимизациям:

bool is_sorted(int *a, int n) {
  for (int i = 0; i < n - 1; i++)
    if (a[i] > a[i + 1])
      return false;
  return true;
}

Так как Clang не делает никаких оптимизаций, и так как LLVM IR был изначально спроектирован для работы с C и C++, преобразование выполняется относительно легко. Я буду использовать Clang 6.0.1 (или близкую версию, поскольку эта ещё не выпущена) на x86-64.

Командная строка следующая:

clang++ is_sorted.cpp -O0 -S -emit-llvm

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

Начнём с верхней части файла:

; ModuleID = 'is_sorted.cpp'
source_filename = "is_sorted.cpp"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

Весь тескт между точкой с запятой и концом строки является комментарием, значит, первая строка не делает ничего, но, если вам интересно, в LLVM «модуль»- это единица компиляции, контенер для кода и данных. Вторая строка также не должна нас беспокоить. Третья строка описывает некие допущения, сделанные компилятором, они не играют роли в этой статье, но вы можете прочитать больше здесь. Целевая тройка указана в формате gcc-ism и далее нам не понадобится.

Функция LLVM имеет опциональные атрибуты:

; Function Attrs: noinline nounwind optnone uwtable

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

И вот наконец, наша функция:

define zeroext i1 @_Z9is_sortedPii(i32* %a, i32 %n) #0 {

“zeroext” означает, что возвращаемое значение функции (i1, однобитное целое), должно быть расширено нулями в бэкенде, до ширины, которую требует ABI. Затем идёт «дополненное» (mangled) имя функции, затем список параметров, в основном, такой же, как в коде С++, за исключением того, что i32 определяет 32-битную переменную. #0 соединяет функцию с группой атрибутов в конце файла.

Вот первый базовый блок:

entry:
  %retval = alloca i1, align 1
  %a.addr = alloca i32*, align 8
  %n.addr = alloca i32, align 4
  %i = alloca i32, align 4
  store i32* %a, i32** %a.addr, align 8
  store i32 %n, i32* %n.addr, align 4
  store i32 0, i32* %i, align 4
  br label %for.cond

Каждая инструкция LLVM должна находиться внутри базового блока: набора инструкций, имеющего один вход в начале и один выход в конце. Последняя инструкция базового блока должна быть терминирующей инструкцией: «проваливание» в следующий базовый блок недопустимо. Каждая функция должна иметь входной блок, не имеющий предшественников (predecessors), которые выполняют переход на данный блок. Это и другие свойства проверяются при парсинге IR, эти проверки также могут быть вызваны многократно в процессе компиляции «верификатором модулей» (“module verifier”). Верификатор полезен для отладки, когда проход генерирует неверный IR.

Первые четыре инструкции в этом базовом блоке — «alloca»: выделение стековой памяти. Первые три создают переменные, неявно созданные при компиляции, четвёртая — переменная цикла. Переменные, аллоцированные таким образом, могут быть доступны только через инструкции load и store. Следующие три инструкции инициализируют три стековых слота, a.addr и n.addr инициализируются с использованием значений, переданных в функцию в качестве парметров, и i инициализируется нулём. Возвращаемое значение не нужно инициализировать, об этом должен будет позаботиться любой код, не являющийся неопределённым в С и С++. Последняя инструкция — это безусловный переход на следующий базовый блок (мы пока не беспокоимся об этом, большинство ненужных переходов будут удалены бэкендом LLVM).

Вы можете спросить: почему Clang выделяет стековые слоты для a и n? Почему он просто не использует эти значения напрямую? В этой функции, так как a и n не изменяются, такая стратегия будет работать, но этот случай будет учтён оптимизатором, и находится вне компетенции Calng. В случае, если a и n могут модифицироваться, они должны находится в памяти, и не должны быть SSA-значениями, которые, по определению, могут принимать значение только в одной точке программы. Ячейки памяти находятся вне мира SSA и могут быть модифицированы когда угодно. Это может показаться странным, но такое решение позволяет организовать работу всех частей компилятора естественным и эффективным образом.

Я думаю о Clang, как о генераторе вырожденного SSA-кода, который удовлетворяет всем требованиям SSA, но только потому, что обмен информацией между базовыми блоками происходит через память. Генерация невырожденного кода требует некоторой внимательности и некоторого анализа, и разработчики Clang отказались делать это, для того, чтобы разделить обязанности генерации и оптимизации кода. Я не видел результатов измерений, но в моём понимании, генерируется множество операций с памятью, и затем, практически немедленно большинство из них удаляется оптимизатором, не приводя к большим накладным расходам времени компиляции,

Рассмотрим, как транслируется цикл for. В общем виде он выглядит так:

for (initializer; condition; modifier) {
  body
}

Это транслируется приблизительно так:

  initializer
  goto COND
COND:
  if (condition)
    goto BODY
  else
    goto EXIT
BODY:
  body
  modifier
  goto COND
EXIT:

Конечно, такая трансляция не специфична для Clang, любой компилятор С и С++ делает то же самое.

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

for.cond:                                         ; preds = %for.inc, %entry
  %0 = load i32, i32* %i, align 4
  %1 = load i32, i32* %n.addr, align 4
  %sub = sub nsw i32 %1, 1
  %cmp = icmp slt i32 %0, %sub
  br i1 %cmp, label %for.body, label %for.end

Clang также делает полезный комментарий, что этот базовый блок может быть достигнут либо из for.inc, либо из входного базового блока. Этот блок загружает i и n из памяти, уменьшает n (флаг nsw отражает то свойство языка C, что знаковое переполнение не определено; без этого флага LLVM использует семантику дополнительного кода), сравнивает уменьшенное значение с i, используя команду slt (signed less than, знаковое меньше, чем) и затем наконец выполняет ветвление на базовый блок for.body или for.end.

Вход в тело цикла возможен только из блока for.cond:

for.body:
  %2 = load i32*, i32** %a.addr, align 8
  %3 = load i32, i32* %i, align 4
  %idxprom = sext i32 %3 to i64
  %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom
  %4 = load i32, i32* %arrayidx, align 4
  %5 = load i32*, i32** %a.addr, align 8
  %6 = load i32, i32* %i, align 4
  %add = add nsw i32 %6, 1
  %idxprom1 = sext i32 %add to i64
  %arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1
  %7 = load i32, i32* %arrayidx2, align 4
  %cmp3 = icmp sgt i32 %4, %7
  br i1 %cmp3, label %if.then, label %if.end

Первые две строки загружают a и i в регистры SSA; i затем расширяется до 64 бит и может принимать участие в вычислении адреса. Команда getelementptr (или сокращённо gep) — известная своей вычурностью команда LLVM, она имеет даже свой собственный раздел справки. В отличие от машинного языка, LLVM не рассматривает указатели как целые. Это облегчает alias -анализ и другие оптимизации памяти. Этот код загружает a[i] и a[i + 1], сравнивает их и выполняет ветвление в зависимости от результата.

Блок if.then сохраняет 0 в стековый слот для возвращаемого значения функции и выполняет безусловный переход на выходной блок функции:

if.then:
  store i1 false, i1* %retval, align 1
  br label %return

Блок else тривиальный:

if.end:
  br label %for.inc

И блок для прибавления единицы к переменной цикла также очень прост:

for.inc:
  %8 = load i32, i32* %i, align 4
  %inc = add nsw i32 %8, 1
  store i32 %inc, i32* %i, align 4
  br label %for.cond

Этот код выполняет переход назад на проверку условия цикла.

Если цикл завершается нормально, мы возвращаем true:

for.end:
  store i1 true, i1* %retval, align 1
  br label %return

И наконец, то, что мы загрузили в стековый слот возвращаемого значения, загружается и возвращается:

return:
  %9 = load i1, i1* %retval, align 1
  ret i1 %9

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

(Благодарю Xi Wang и Alex Rosenberg за присланные исправления)