Это цикл статей об оптимизирующих компиляторах вообще и LLVM в частности. Смотри все статьи данного цикла:
Цикловые инварианты
Сегодня мы поговорим о нескольких разных классах оптимизаций, которые позволяют компилятору увеличивать быстродействие наших программ. Для тех, кто здесь впервые, стоит сначала прочитать статьи об SSA-форме, доминировании, циклах и (опционально) неопределённом поведении, чтобы понимать, о чём идёт речь.
Что такое цикловой инвариант
В предыдущей статье была рассмотрена ситуация, когда мы несколько раз вычисляли одно и то же подвыражение, и могли сэкономить, переиспользовав первый результат. Тогда две разные операции в исходной программе вычисляли один и тот же результат. Но бывают ситуации, когда в коде программы операция одна, но её результаты -- избыточны, поскольку вычисляются снова и снова. Как вы догадались, речь идёт об операциях в циклах. Рассмотрим следующий пример:
int foo(int n) { int sum = 0; for (int i = 0; i < n; i++) { sum += i + n * 2; } return sum; }
Как несложно заметить, на каждой итерации мы вычисляем n * 2, чтобы потом добавить это выражение к сумме. Поскольку значение n на протяжении функции не меняется, выражение n * 2 также не будет меняться и зависеть от номера итерации цикла. Вполне очевидно, что его можно бы было посчитать однажды, произведя простейшую оптимизацию:
int foo(int n) { int sum = 0; int tmp = n * 2; for (int i = 0; i < n; i++) { sum += i + tmp; } return sum; }
Тогда при исполнении программы мы сэкономим n - 1 умножение, что выгодно при n > 1. Итак, начнём с определений.
Цикловым инвариантом называется выражение, значение которого не зависит от номера итерации цикла.
Очевидно, что значения всех выражений, вычисленных до входа в цикл, являются инвариантами, а некоторые выражения внутри цикла -- могут быть инвариантами, если все их операнды -- инварианты. В нашем примере значение n вычислено до входа в цикл, и поэтому является инвариантом, а n * 2 -- зависит только от инвариантов и является инвариантом даже несмотря на то, что изначально вычислялось внутри цикла.
Теперь рассмотрим другой пример:
int foo(int n) { int sum = 0; for (int i = 0; i < n; i++) { if ((n / 8) > 100) { sum += i + n * 2; } else { sum -= i; } } return sum; }
Как мы видим, выражение (n / 8) > 100 является инвариантом, поэтому ветвление по нему называется инвариантным ветвлением. Его особенность в том, что, войдя в цикл и однажды пройдя по одной из веток, мы на каждой итерации будем идти в ту же ветку.
В дальнейших разделах я расскажу, как современные компиляторы умеют оптимизировать такой код.
Вынос инвариантных выражений из цикла
Давайте рассмотрим наш первый пример и сразу перепишем его в SSA-форме:
define i32 @foo(i32 %n) { entry: br label %header header: ; preds = %backedge, %entry %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ] %i = phi i32 [ 0, %entry ], [ %i.next, %backedge ] %loop.cond = icmp slt i32 %i, %n br i1 %loop.cond, label %backedge, label %done backedge: ; preds = %header %n2 = mul nsw i32 %n, 2 %i.plus.n2 = add nsw i32 %i, %n2 %sum.next = add nsw i32 %sum, %i.plus.n2 %i.next = add nsw i32 %i, 1 br label %header done: ; preds = %header ret i32 %sum }
Выражение в SSA-форме является цикловым инвариантом, если выполнено одно из двух условий:
Оно строго доминирует над заголовком цикла (т.е. вычислено до входа в цикл);
Все операнды данного выражения являются цикловыми инвариантами.
В примере выше видно, что выражения %n и 2 доминируют над заголовком цикла (т.е. вычислены ранее), а выражение %n2 = mul nsw i32 %n, 2 соответствует второму случаю (все операнды -- инварианты)
Понятно, что если цикл делает хотя бы две итерации, то вычислять инвариантные выражения за его пределами -- скорее всего выгодно. Естественным образом встаёт вопрос -- если не в цикле, то где?
В зависимости от обстоятельств, может быть выгодно вычислять инвариантные выражения как до входа в цикл (например, в предзаголовочном блоке), так и после выхода из цикла (например, в выходном блоке). В зависимости от того, что мы выбираем, слегка меняется и алгоритм оптимизации, которая занимается выносом. Обычно разделяют подъём (hoisting) и спуск (sinking) инвариантных выражений по дереву доминирования. В LLVM обеими преобразованиями целенаправленно занимается оптимизационный пасс LICM (Loop Invariant Code Motion, Движение инвариантного циклового кода), о��нако в разных формах подобные преобразования делают и другие оптимизации. Рассмотрим, как это делается.
В обоих случаях алгоритм можно описать следующей схемой:
Обходим блоки цикла в определённом порядке
Обходим инструкции внутри блока в определённом порядке
Всякий раз, когда мы видим инструкцию, которая является цикловым инвариантом, перемещаем её в целевой блок и продолжаем
Порядок, в котором обходятся блоки и инструкции, определяются соображениями оптимальности. Желательно, чтобы алгоритм сошёлся за один проход, после чего в цикле не должно остаться инвариантных выражений. В случае подъёма инструкций (т.е. выноса из тела цикла в предзаголовок) мы хотим обеспечить, чтобы на момент обработки очередной инструкции все её инвариантные операнды уже были вынесены из цикла, чтобы проверка данной инструкции была дешёвой, а её вынос -- законным (напомним, что все операнды инструкции обязаны над ней доминировать). С другой стороны, в случае спуска мы хотим, чтобы все инвариантные пользователи данной инструкции к моменту её обработки уже были перемещены вниз, поскольку мы обязаны поддерживать свойство SSA-формы, согласно которому операнд доминирует своих пользователей. Рассмотрим это на примере:
define i32 @example_hoist_sink(i32 %a, i32 %b, i32 %c) { entry: br label %header header: ; preds = %backedge, %entry %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ] %cond = icmp slt i32 %iv, 12 %x = mul i32 %a, %b br i1 %cond, label %if.true, label %backedge if.true: ; preds = %header %y = mul i32 %x, %c %z = mul i32 %y, %c %sum.incremented = add i32 %sum, %x %if.true.cond = icmp eq i32 %x, 1000 br i1 %if.true.cond, label %backedge, label %side.exit backedge: ; preds = %if.true, %header %sum.next = phi i32 [ %sum, %header ], [ %sum.incremented, %if.true ] %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %backedge ret i32 %sum side.exit: ; preds = %if.true ret i32 %z }
Здесь значения %a, %b и %с доминируют над заголовком цикла (и потому являются инвариантами), а значения %x, %y, %z и %if.true.cond вычислены внутри цикла, но зависят только от инвариантных аргументов. Давайте сначала рассмотрим, как выглядит подъём инвариантов в этом случае. Алгоритм подъёма обходит блоки в порядке RPOT (то есть в топологическом порядке) и инструкции в блоке сверху вниз. Такой обход обеспечивает требуемое свойство, чтобы инвариантные аргументы были обработаны до своих пользователей. В данном случае, алгоритм сработает так:
RPOT для блоков данного цикла -
header,if.true,backedge. Они будут обрабатываться в этом порядке, инструкции в блоках обрабатываются сверху вниз.При обработке блока
headerвыяснится, что все аргументы инструкции%x-- инварианты, поэтому она будет перемещена в блок%entry.При обработке блока
if.trueсначала будет обработана инструкция %y и перемещена вверх, поскольку к этому моменту её операнды%xи%суже оба инварианты, а потом -- инструкция%z. Потом будет вынесено также условие%if.true.cond.
В результате мы получим следующий код:
define i32 @example_hoist_sink(i32 %a, i32 %b, i32 %c) { entry: %x = mul i32 %a, %b %y = mul i32 %x, %c %z = mul i32 %y, %c %if.true.cond = icmp eq i32 %x, 1000 br label %header header: ; preds = %backedge, %entry %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ] %cond = icmp slt i32 %iv, 12 br i1 %cond, label %if.true, label %backedge if.true: ; preds = %header %sum.incremented = add i32 %sum, %x br i1 %if.true.cond, label %backedge, label %side.exit backedge: ; preds = %if.true, %header %sum.next = phi i32 [ %sum, %header ], [ %sum.incremented, %if.true ] %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %backedge ret i32 %sum side.exit: ; preds = %if.true ret i32 %z }
Довольны ли мы такой оптимизацией? С одной стороны, мы существенно снизили объём вычислений во время исполнения ци��ла. С другой -- могло статься, что мы никогда не ходили в блок if.true, и таким образом, все вынесенные значения нам на самом деле не пригождались никогда. В этом случае выгоднее было бы просто переместить %x в блок %if.true, убрав его из заголовка, и мы бы получили больший выигрыш. Как же быть?
На самом деле, вынос %x в предзаголовок -- это всё равно выгоднее, чем считать его на каждой итерации в заголовке, даже если это и не оптимальное решение. Что касается %y и %z, то они нужны только в выходном блоке %side.exit, поэтому к ним разумнее было бы применить не подъём, а спуск. Оставлю вопрос о том, какой обход блоков и инструкций нужно использовать при спуске, для самостоятельного решения читателем. В оптимальном решении %y и %z будут спущены в выходной блок. Что касается инструкций %x и %if.true.cond, то их выгодно либо поднять в предзаголовок, либо опустить в блок %if.true, в зависимости от того, какой из блоков горячее. Узнать это можно, если есть профилировочная информация или какие-то дополнительные знания относительно условия цикла. В данном случае можно статически доказать, что блок if.true выполнится целых 12 раз, и поэтому выгодно поднять их в заголовок. Итак, оптимальное решение для данной задачи выглядит следующим образом:
define i32 @example_hoist_sink(i32 %a, i32 %b, i32 %c) { entry: %x = mul i32 %a, %b %if.true.cond = icmp eq i32 %x, 1000 br label %header header: ; preds = %backedge, %entry %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ] %cond = icmp slt i32 %iv, 12 br i1 %cond, label %if.true, label %backedge if.true: ; preds = %header %sum.incremented = add i32 %sum, %x br i1 %if.true.cond, label %backedge, label %side.exit backedge: ; preds = %if.true, %header %sum.next = phi i32 [ %sum, %header ], [ %sum.incremented, %if.true ] %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %backedge ret i32 %sum side.exit: ; preds = %if.true %y = mul i32 %x, %c %z = mul i32 %y, %c ret i32 %z }
Инвариантные загрузки из памяти
Стоит сделать отдельную оговорку про случай, когда мы имеем дело с памятью. Работа с ней не в полной мере отражается SSA-формой, и в LLVM IR моделируется с помощью свойств чтения и записи памяти. В настоящее время есть попытка исправить ситуацию при помощи Memory SSA, но это всё равно надстройка над IR, а не его часть.
Рассмотрим простой пример:
define void @example_hoist_load(ptr dereferenceable(32) %p1, ptr dereferenceable(32) %p2) { entry: br label %header header: ; preds = %backedge, %entry %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] %cond = call i1 @cond() br i1 %cond, label %if.true, label %if.false if.true: ; preds = %header store i32 %iv, ptr %p1, align 4 br label %backedge if.false: ; preds = %header %loaded.value = load i32, ptr %p2, align 4 br label %backedge backedge: ; preds = %if.false, %if.true %phi = phi i32 [ %iv, %if.true ], [ %loaded.value, %if.false ] %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %backedge ret void } declare i1 @cond() #0 attributes #0 = { memory(read) }
Здесь в зависимости от условия %cond мы либо пишем память по указателю %p1, либо читаем по указателю %p2. Можем ли мы вынести загрузку из %p2 в предзаголовок?
На самом деле, ответ на этот вопрос -- сложный, и зависит от множества факторов. Такой вынос возможен, если всякий раз, когда мы читаем значение из этой памяти, оно одно и то же. Как минимум это возможно, если мы докажем один из фактов:
Все записи в цикле не делаются в эту память (т.е. области памяти, куда указывают
%p1и%p2, не пересекаются)Функция
cond()обладает свойством монотонности: она может вернуть сначалаfalse, потомtrue, но не наоборот. Если это так, то все чтения%p2будут сделаны до записей в%p1, поэтому вынести чтение можно.
Также нельзя забывать, что для того, чтобы вынести чтение из-под условия, необходимо доказать, что данный указатель будет доступен для чтения в том месте, куда вы его выносите. Чтение из неинициализированного указателя может приводить к неопределённому поведению, и о его последствиях у меня есть отдельная статья.
Всё это -- довольно продвинутые области оптимизации и выходит далеко за рамками нашего сегодняшнего рассказа. Пока просто запомним, что с памятью всё не так просто, и для того, чтобы вынести чтение или запись в память, инвариантности указателя недостаточно. Нужно ещё знать что-то об инвариантности данных по этому указателю.
Ветвления по инвариантным условиям
Итак, с выносом инструкций всё более или менее ясно. Но можно ли выносить из цикла сложный код с передачей потока управления, если все переходы в нём -- инвариантные? На самом деле, есть несколько способов это сделать, и я попробую их перечислить, хотя и не обещаю, что покрою здесь все нюансы. В LLVM этим явно занимаются тот же LICM и Loop Unswitching, и подозреваю, что какие-то элементы подобного толка иногда могут выполнять и другие трансформации.
Давайте рассмотрим самый простой пример:
define i32 @example_hoist_cfg_simple(i32 %n, i32 %m) { entry: %cond = icmp eq i32 %n, %m br label %header header: ; preds = %backedge, %entry %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] br i1 %cond, label %backedge, label %side.exit backedge: ; preds = %header %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %backedge ret i32 -1 side.exit: ; preds = %header ret i32 %iv }
Здесь в цикле присутствует ветвление по инвариантному условию, причём никакой важный код до этого ветвления не исполняется. На самом деле, мы либо на первой итерации цикла сразу выйдем в %side.exit, если %cond == false, либо же не попадём в этот блок никогда. В данном случае можно поднять ветвление так же, как мы ранее поднимали выражения, в предзаголовок. Давайте механически проделаем эту операцию:
define i32 @example_hoist_cfg_simple(i32 %n, i32 %m) { entry: %cond = icmp eq i32 %n, %m br i1 %cond, label %preheader, label %side.exit preheader: br label %header header: ; preds = %backedge, %entry %iv = phi i32 [ 0, %preheader ], [ %iv.next, %backedge ] br label %backedge backedge: ; preds = %if.true, %header %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %backedge ret i32 -1 side.exit: ret i32 %iv ; ТАК НЕЛЬЗЯ! }
Итак, мы превратили условный переход в цикле в безусловный и подняли ветвление вверх. В этом коде есть проблема: если раньше мы могли использовать значение %iv в блоке %side.exit, потому что между ними существовало отношение доминирования, то теперь так делать нельзя. При переходе entry -> side.exit мы никогда не вычисляли значение %iv! Поэтому перед тем, как выполнять такое преобразование, нужно убедиться, что все значения, используемые в блоке %side.exit, будут там доступны после оптимизации. Например, здесь можно использовать знание о том, что мы могли попасть в блок %side.exit только на нулевой итерации, и заменить ret i32 %iv на ret i32 0. Также, чтобы два раза не вставать, мы можем избавиться и от безусловного перехода, склеив блоки header и backedge в один. Итоговый оптимизированный код выглядит так:
define i32 @example_hoist_cfg_simple(i32 %n, i32 %m) { %cond = icmp eq i32 %n, %m br i1 %cond, label %preheader, label %side.exit preheader: ; preds = %entry br label %header header: ; preds = %header, %preheader %iv = phi i32 [ 0, %preheader ], [ %iv.next, %header ] %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %header ret i32 -1 side.exit: ; preds = %entry ret i32 0 }
Давайте слегка усложним пример. Теперь перед ветвлением, которое мы хотим вынести, существует инструкция со сторонним эффектом:
define i32 @example_hoist_cfg_side_effects(i32 %n, i32 %m) { entry: %cond = icmp eq i32 %n, %m br label %header header: ; preds = %backedge, %entry %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] call void @side_effect_1() call void @side_effect_2() call void @side_effect_3() br i1 %cond, label %backedge, label %side.exit backedge: ; preds = %header %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %backedge ret i32 -1 side.exit: ; preds = %header ret i32 %iv } declare void @side_effect_1() declare void @side_effect_2() declare void @side_effect_3()
Теперь надо учитывать, что код выше ветвления мог записать какую-нибудь внешнюю память, и в случае, если функция вернёт 0, внешний код вправе ожидать, что это будет сделано. Поэтому нельзя допустить, чтобы после оптимизации ветвление оказалось выше данного стороннего эффекта. Поэтому оптимизированный код в этом случае обязан будет продублировать инструкции, лежащие выше ветвления:
define i32 @example_hoist_cfg_side_effects(i32 %n, i32 %m) { entry: %cond = icmp eq i32 %n, %m br i1 %cond, label %preheader, label %header.copy preheader: ; preds = %entry br label %header header: ; preds = %backedge, %preheader %iv = phi i32 [ 0, %preheader ], [ %iv.next, %backedge ] call void @side_effect_1() call void @side_effect_2() call void @side_effect_3() br label %backedge backedge: ; preds = %header %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %backedge ret i32 -1 side.exit: ; preds = %header.copy ret i32 %iv.copy header.copy: ; preds = %entry %iv.copy = phi i32 [ 0, %entry ] call void @side_effect_1() call void @side_effect_2() call void @side_effect_3() br label %side.exit } declare void @side_effect_1() declare void @side_effect_2() declare void @side_effect_3()
Или, после упрощений и склеиваний безусловных переходов:
define i32 @example_hoist_cfg_side_effects(i32 %n, i32 %m) { entry: %cond = icmp eq i32 %n, %m br i1 %cond, label %header, label %header.copy header: ; preds = %header, %entry %iv = phi i32 [ %iv.next, %header ], [ 0, %entry ] call void @side_effect_1() call void @side_effect_2() call void @side_effect_3() %iv.next = add i32 %iv, 1 %loop.cond = icmp slt i32 %iv.next, 1000 br i1 %loop.cond, label %header, label %done done: ; preds = %header ret i32 -1 header.copy: ; preds = %entry call void @side_effect_1() call void @side_effect_2() call void @side_effect_3() ret i32 0 } declare void @side_effect_1() declare void @side_effect_2() declare void @side_effect_3()
Но иногда бывает так, что ветвление по инвариантному условию не выходит из цикла, или объём кода, который придётся раскопировать для его удаления, очень велик. В этом случае делается полная версия данной трансформации, которую проще всего описать схематично. Изначальный код:
cond = ... for (...) { // A if (cond) { // B } else { // C } // D }
превращается в
cond = ... if (cond) { for (...) { // A if (true) { // B } else { // C } // D } } else { for (...) { // A if (false) { // B } else { // C } // D } }
В этом случае объём и сложность фрагментов кода A, B, C, D не имеют особого значения. Трансформация выполняется чисто механически, дальнейшие трансформации избавятся от ветвлений по константным условиям и соответствующим образом преобразуют все финоды. Единственным недостатоком здесь является удвоение размера кода, что негативно сказывается на времени компиляции и объёме сгенерированного кода. Поэтому прибегать к этой технике (она называется non-trivial unswitching) стоит только в крайнем случае и ради больших выигрышей в производительности.
На самом деле, как вы могли заметить, все простые случаи вынесения инвариантного CFG -- это всего лишь частные случаи последнего, самого тяжеловесного преобразования. Тем не менее, на практике они тоже важны, так как их выполнение гораздо дешевле с точки зрения времени компиляции и не приводит к чрезмерному раздуванию объёма кода.
Заключение
В этой статье мы рассмотрели, как можно сокращать избыточность вычислений, вынося инвариантные выражения и ветвления из циклов. За рамками рассмотрения остались некоторые тонкости реализации, в частности, связанные с неопределённым поведением (они ранее освещались в соответствующей статье), а также сложности взаимодействия таких оптимизаций с последующей кодогенерацией. Темп выхода статей слегка замедлился, но я всё-таки надеюсь со временем обозреть все интересные высокоуровневые оптимизации, с которыми доводилось иметь дело в бытность компиляторным инженером.
