Как Clang компилирует функцию

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

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

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 объёмный, и не может быстро выводиться или парситься, бинарный формат биткода всегда является более предпочтительным, если человеку не нужно смотреть на этот код. Здесь ^[2]находится полный 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 «модуль»- это единица компиляции, контенер для кода и данных. Вторая строка также не должна нас беспокоить. Третья строка описывает некие допущения, сделанные компилятором, они не играют роли в этой статье, но вы можете прочитать больше здесь ^[3]. Целевая тройка ^[4] указана в формате gcc-ism и далее нам не понадобится.

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

; Function Attrs: noinline nounwind optnone uwtable

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

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

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

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

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

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 должна находиться внутри базового блока: набора инструкций, имеющего один вход в начале и один выход в конце. Последняя инструкция базового блока должна быть терминирующей инструкцией ^[7]: «проваливание» в следующий базовый блок недопустимо. Каждая функция должна иметь входной блок, не имеющий предшественников (predecessors), которые выполняют переход на данный блок. Это и другие свойства ^[8] проверяются при парсинге 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 ^[9](или сокращённо gep) — известная своей вычурностью команда LLVM, она имеет даже свой собственный раздел справки ^[10]. В отличие от машинного языка, 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 за присланные исправления)

Автор: Владимир

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