Это цикл статей об оптимизирующих компиляторах вообще и LLVM в частности. Смотри все статьи данного цикла:
SSA форма
Доминирование
Неопределённое поведение
Циклы
CSE
Цикловые инварианты
Сегодня мы поговорим о нескольких разных классах оптимизаций, которые позволяют компилятору увеличивать быстродействие наших программ. Для тех, кто здесь впервые, стоит сначала прочитать статьи об 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 -- это всего лишь частные случаи последнего, самого тяжеловесного преобразования. Тем не менее, на практике они тоже важны, так как их выполнение гораздо дешевле с точки зрения времени компиляции и не приводит к чрезмерному раздуванию объёма кода.
Заключение
В этой статье мы рассмотрели, как можно сокращать избыточность вычислений, вынося инвариантные выражения и ветвления из циклов. За рамками рассмотрения остались некоторые тонкости реализации, в частности, связанные с неопределённым поведением (они ранее освещались в соответствующей статье), а также сложности взаимодействия таких оптимизаций с последующей кодогенерацией. Темп выхода статей слегка замедлился, но я всё-таки надеюсь со временем обозреть все интересные высокоуровневые оптимизации, с которыми доводилось иметь дело в бытность компиляторным инженером.
