Как LLVM оптимизирует функцию

Оптимизирующий AOT-компилятор обычно структурирован так:

1. фронтенд, преобразующий исходный код в промежуточное представление
2. конвейер машинно-независимой оптимизации (IR): последовательность проходов, которые переписывают IR для устранения неэффективных участков и структур, которые не могут быть непосредственно преобразованы в машинный код. Иногда эту часть называют middle-end.
3. Машинно-зависимый бэкенд для генерации ассемблерного кода или машинного кода.

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

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

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

В этом посте мы посмотрим, как работают некоторые проходы оптимизации LLVM. Я подразумеваю, что вы читали эту часть, про то, как Clang компилирует функцию или что вы более или менее понимаете как работает LLVM IR. Особенно полезно понимать SSA (static single assignment)-форму: Википедия даст вам начальное представление, и эта книга даст вам больше информации, чем вы хотели бы знать. Также читайте LLVM Language Reference и список проходов оптимизации.

Посмотрим, как Clang/LLVM 6.0.1 оптимизирует этот C++ код:

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;
}

При этом мы помним, что конвейер оптимизации — очень оживлённое место, и мы пропустим много весёлых моментов, таких, как:

Инлайнинг — простая, но очень важная оптимизация, которая не происходит в данном примере, т.к. мы рассматриваем только одну функцию.
Практически все оптимизации, специфичные для С++, но не для С
Автовекторизацию, которой мешает ранний выход из цикла

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

Вот файл IR, созданный Clang (я вручную удалил атрибут «optnone», который вставил Clang) и командная строка, используемая, чтобы увидеть эффект каждого прохода оптимизации:

opt -O2 -print-before-all -print-after-all is_sorted2.ll

Первый проход, это "упрощение CFG" (control flow graph). Так как Clang не выполняет оптимизации, IR, который он порождает, содержит простые возможности для оптимизации:

Здесь базовый блок 26 просто выполняет переход к блоку 27. Такие блоки можно удалить, перенаправив ссылки на них блок назначения. LLVM автоматически перенумерует блоки. Полный список преобразований, производимых SimplifyCFG, перечислен наверху прохода.

Этот файл реализует удаление невыполняемого кода и слияние базовых блоков, вместе с рядом других оптимизаций потока управления. Например:

• удаление базовых блоков, не имеющих предшественников
• слияние базового блока с его предшественником, если предшественник только один и предшественник имеет только один последующий блок.
• удаление phi-узлов для базовых блоков, имеющих единственного предшественника.
• удаление базовых блоков, состоящих только их безусловного перехода.
• изменение инструкций invoke для nounwind-функций на call
• изменение "if (x) if (y)" на "if (x&y)"

Большая часть возможностей для оптимизации CFG появляется как результат работы других проходов LLVM. Например, удаление недостижимого кода (dead code elimination) и перемещение инвариантов цикла с лёгкостью может привести к возникновению пустых базовых блоков.

Следующий проход, SROA (scalar replacement of aggregates), один из наиболее интенсивно используемых. Его название приводит к некоторой путанице, потому что SROA — только одна из его функций. Проход проверяет каждую инструкцию alloca (выделение памяти в стеке функции), и пытается преобразовать её в SSA-регистры. Одна инструкция alloca (то есть, фактически, переменная на стеке прим. перев..) превращается в множество регистров, если она статически присваивается несколько раз, а также, если alloca является классом или структурой, она разделяется на компоненты (это и называется «скалярной заменой», о которой говорится в названии прохода). Простая версия SROA сдалась бы на стековых переменных, для которых применяется операция взятия адреса, но версия LLVM взаимодействует с алгоритмом анализа алиасов, и поступает интеллектуальным образом (хотя это и не требуется в следующем примере).

После SROA, инструкции alloca (и соответствующие им инструкции load и store) исчезают, и код становится более чистым и пригодным для последующих оптимизаций (конечно, SROA не может удалить все alloca в общем случае, это происходит только в том случае, если анализ указателей может полностью избавиться от алиасов). В процессе своей работы SROA вставляет в код инструкции phi. Инструкции phi составляют ядро SSA-представления, и отсутствие phi в коде, который генерирует Clang говорит нам о том, что Clang генерирует тривиальный вариант SSA, в котором базовые блоки связаны через память, а не через SSA-регистры.

Далее следует “early common subexpression elimination”, CSE (ранее удаление общих подвыражений). CSE пытается устранить случаи избыточных подвыражений, которые могут встречаться как в коде, написанном человеком, так и в частично оптимизированном коде. “Early CSE” — быстрый и простой вариант CSE, который выявляет тривиальные избыточные вычисления.

Здесь %10 и %17 делают одно и тоже, то есть код может быть переписан так, что будет использовано одно значение, а второе удалено. Это даёт некоторое представление о преимуществе SSA: когда каждый регистр присваивается лишь однажды, нет такой вещи, как множество версий одного регистра. Таким образом, избыточные вычисления могут быть выявлены с использованием синтаксической эквивалентности, без использования глубокого анализа программы (это не так для локаций памяти, которые существуют вне мира SSA).

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

Этот проход преобразует простые глобальные переменные, для которых нигде не берётся адрес. В очевидных случаях, операции чтения записи глобальных переменных помечаются как константные, удаляются переменные, для которых происходит только запись, и т.п.

Этот проход делает такие изменения:

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

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

Следующий проход объединяет инструкции и называется “instruction combiner“, InstCombine. Это большая и разнообразная коллекция оптимизаций (peephole optimizations), которые (обычно) переписывают некоторые инструкции, объединённые общими данными, в более эффективную форму. InstCombine не меняет порядок выполнения (control flow) функции. В приведённом примере он изменил не так много:

Здесь вместо вычитания 1 из %1, для того, чтобы вычислить %4, мы прибавляем -1. Это не оптимизация, а приведение к каноническому виду. Когда существует много способов сделать вычисление, LLVM пытается привести его к канонической (часто произвольно выбранной) форме, которую последующие проходы и бэкенды ожидают увидеть. Второе изменение, сделанное InstCombine, это приведение к канонической форме двух операций знакового расширения (инструкция sext), которые вычисляют %7 и %11, преобразованных к расширению нулями (zext). Это преобразование является безопасным, когда компилятор может доказать, что операнд sext неотрицательный. В данном случае это так, потому что переменная цикла изменяется от 0 до n (если n отрицательное, цикл не выполняется вообще). Последним изменением стало добавление флага «nuw» (no unsigned wrap) к инструкции, которая вычисляет %10. Мы можем видеть, что это безопасно, из того, что (1) переменная цикла всегда увеличивается и (2) если переменная начинается с нуля и увеличивается, она бы стала неопределённой при смене знака при пересечении INT_MAX, перед тем, как достигнет беззнакового переполнения, следующего за UINT_MAX. Этот флаг может быть использован для последующих оптимизаций.

Далее, второй раз запускается SimplifyCFG, и удаляет два пустых базовых блока:

Затем проход "вывод атрибутов функций" (“Deduce function attributes”) аннотирует функцию:

“Norecurse” означает, что функция не включена ни в какие рекурсивные вызовы, “readonly” означает, что функция не изменяет глобальное состояние. Атрибут параметра “nocapture” означает, что параметр нигде не сохраняется после выхода из функции, и “readonly” означает, что память не модифицируется функцией. Вы можете посмотреть список атрибутов функций и атрибутов параметров.

Затем проход “rotate loops” перемещает код в попытках улучшить условия для последующих оптимизаций:

Хотя разница выглядит пугающе, изменения на самом деле небольшие. Мы можем увидеть, что произошло, в более читаемом виде, если мы попросим LLVM нарисовать граф передачи управления до и после прохода ротации циклов. Вот их вид до (слева) и после (справа):

Оригинальный код по-прежнему соответствует структуре цикла, которую сгенерировал Clang:

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

После работы прохода цикл выглядит так:

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

(Исправления, предложенные Йоханнесом Дурфертом, приведены ниже — спасибо!)

Цель прохода «loop rotation» состоит в удалении одной ветви, что обеспечивает возможность дальнейших оптимизаций. Я не нашёл лучшего описания этого преобразования в интернете.

Проход «CFG simplification» (упрощение графа потока управления) сворачивает два базовых блока, которые содержат только вырожденные (одновходовые) phi-инструкции:

Проход «instruction combiner» (объединение инструкций) превращает “%4 = 0 s< (%1 — 1)" в "%4 = %1 s> 1″ (где s< и s> — операции сравнения знаковых операндов), это полезное преобразование, оно сокращает длину цепочек зависимостей и также может создавать «мёртвые» (недостижимые) инструкции (см. патч, который это выполняет). Этот проход также удаляет тривиальные phi-инструкции, которые были добавлены проходом «loop rotation».

Далее следует проход “canonicalize natural loops”, который описан в его собственном исходнике так:

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

Вставка блока перед циклом (Loop pre-header) гарантирует, что будет единственная, некритическое ребро входа в заголовок цикла. Это упрощает количество анализов и преобразований,таких, как LICM.

Вставка блока на выходе из цикла гарантирует, что все блоки, являющиеся выходными для цикла (то есть имеющие предшественников в теле цикла) будут иметь предшественников только в теле цикла (и заголовок цикла будет для них доминирующим). Это упрощает преобразования, такие, как "store-sinking", встроенные в LICM.

Этот проход гарантирует, что цикл имеет в точности одно ребро передачи управления из конца цикла в начало (backedge).

Инструкция Indirectbr вносит некоторые усложнения. Если цикл содержит эту инструкцию или в него выполняется вход этой инструкцией, невозможно выполнить преобразования цикла гарантированным образом. Код клиента должен проверять, что эти условия истинны, прежде чем полагаться на них.

Отметим, что проход simplifycfg очистит блоки, которые были разделены, но в дальнейшем это не потребовалось, то есть использование этого прохода не пессимизирует сгенерированный код.

Этот проход, очевидно, изменяет CFG, обновляет информацию о циклах и о доминаторах.


Здесь мы видим, что произошла вставка выходного блока:

Затем следует "упрощение переменной цикла":

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

Если количество проходов цикла вычислимо, этот проход выполняет соответствующие изменения:

Выходное условие цикла приводится к каноническому виду, при котором переменная цикла сравнивается с конечной величиной. Например, цикл ‘for (i = 7; i*i < 1000; ++i)' преобразуется в 'for (i = 0; i != 25; ++i)'.

Любое использование вне цикла выражения с использованием переменной цикла indvar заменяется на вычисление выходного соответствующего выражения вне цикла, устраняя зависимость этого значения от переменной цикла. Если единственной целью цикла является вычисление выходного значения соответствующего производного выражения, это преобразование делает цикл "мёртвым".

Эффектом этого прохода будет изменение 32-битной переменной цикла на 64-битную:

Я не знаю, почему zext — ранее приведённое к каноническому виду из sext, вернулось опять к sext.

Сейчас проход “global value numbering” выполняет очень умную оптимизацию. Одной из причин написания этого поста является желание её показать. Можете ли вы увидеть её здесь?

Увидели? Да, две инструкции load в цикле слева, соответствующие a[i] и a[i + 1]. Здесь GVN обнаружил, что в загрузке a[i] нет необходимости, потому что a[i + 1] из одной итерации цикла может быть перенесена в следующую, как a[i]. Этот простой трюк наполовину сокращает количество чтений из памяти, выполняемых функцией. И LLVM, и GCC научились выполнять это преобразование лишь недавно.

Возможно, вы спросите себя, будет ли работать этот трюк, если мы сравниваем a[i] с a[i + 2]. Получается так, что нет, но GCC может выделить до четырёх регистров для таких случаев.

Потом запускается проход “bit-tracking dead code elimination”:

Этот файл реализует проход "Bit-Tracking Dead Code Elimination". Некоторые инструкции (сдвиги, некоторые инструкции "и" и "или" и т.п.) "убивают" некоторые входные биты. Мы отслеживаем эти входные биты и удаляем инструкции, которые вычисляют только "мёртвые" биты.

Но здесь получается, что такие хитрости не нужны, потому что единственный мёртвый код, это инструкция GEP (get element pointer), и она тривиально мертва (проход GVN удалил инструкцию load, которая использовала адрес, вычисляемый этой инструкцией):

Сейчас алгоритм объединения инструкций поместил add в другой базовый блок. Логика, по которой это преобразование было помещено в InstCombine, не ясна мне, возможно, не нашлось какого-то очевидного места, куда можно было его поместить:

Сейчас происходит нечто более странное: проход “jump threading” удалил то, что проход “canonicalize natural loops” сделал ранее:

Затем мы снова выполняем приведение к каноническому виду:

И упрощение CFG преобразует это по-другому:

И обратно:

И снова туда:

И обратно:

И туда:

И наконец, мы закончили с миддлендом! Код справа — это тот код, который мы передадим (в нашем случае) бэкенду x86-64.

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

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

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

Источник