Хабрахабр

[Перевод] Как LLVM оптимизирует функцию

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

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

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

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

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

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

0. Посмотрим, как Clang/LLVM 6. 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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

Атрибут параметра “nocapture” означает, что параметр нигде не сохраняется после выхода из функции, и “readonly” означает, что память не модифицируется функцией. “Norecurse” означает, что функция не включена ни в какие рекурсивные вызовы, “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”, который описан в его собственном исходнике так:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

И обратно:

И снова туда:

И обратно:

И туда:

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

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть