Это цикл статей об оптимизирующих компиляторах вообще и LLVM в частности. Смотри все статьи данного цикла:
Циклы
Если вы не читали первые две части этого курса (про SSA-форму и доминирование), сначала прочитайте их. Иначе можете совсем ничего не понять.
Договоримся о терминах
Так получилось, что в теории компиляторов различают понятия cycle (цикл) и loop (петля). Если мы говорим о CFG, то cycle -- это любая последовательность блоков, такая, что начав с некоторого блока и двигаясь по рёбрам, вы можете вернуться в исходный блок. А loop -- это цикл, обладающий некоторыми дополнительными свойствами (о них мы поговорим ниже), и это именно та конструкция, которая появляется, когда мы пишем цикл на языке программирования высокого уровня (например, на С++). Любой loop -- это cycle, но не любой cycle -- это loop.
При этом компиляторы (в большинстве своём) умеют оптимизировать только loop'ы, а циклы, не являющиеся loop'ами, чаще всего игнорируют или ведут себя с ними крайне осторожно. Сказать по правде, они их зачастую даже и не видят. При этом такие конструкции языков программирования, как for
, while
, do-while
, foreach
и т.п. порождают именно loop.
Поэтому в этой статье и дальше в этой серии мы слегка надругаемся над английским языком. Словом "цикл" я буду называть именно loop (правильно было бы говорить "петля", а не "цикл", но это плохо согласуется с русскоязычной традицией), а когда речь пойдёт о чём-то другом, я буду явно называть их cycle или non-loop cycle. На практике, если вы пишете программу и специально не ищете себе приключений на одно место, вы в 99% случаев будете иметь дело именно с loop'ами.
Что такое цикл
Давайте вспомним, что такое граф потока управления (CFG) и попытаемся понять, как выглядят циклы в этом графе. Сначала пара общих определений:
Определение 1: Две вершины А
и В
сильно связаны, если в графе существует ориентированный путь как из А
в В
, так и из В
в А
.
Определение 2: Максимальный по включению связанный подграф называется компонентой сильной связности.
Проще всего понять, что это за монстр, если посмотреть внимательно вот на такой граф:
![Компоненты сильной связности выделены цветными прямоугольниками Компоненты сильной связности выделены цветными прямоугольниками](https://habrastorage.org/getpro/habr/upload_files/db9/1bc/133/db91bc1333101774782256b83ad7caaa.png)
Как видите, вершины 8
и 9
-- сильно связаны, потому что есть путь из 8
в 9
и наоборот. Вместе они образуют компоненту сильной связности. То же самое можно сказать о вершинах 4
, 5
, 6
и 7
, которые попарно достижимы друг из друга и также формируют компоненту. Вершина 3
имеет ребро сама в себя, поэтому она также выделяется в отдельную компоненту сильной связности.
Компонента сильной связности -- это обобщение понятие cycle. Например, внутри второй компоненты есть несколько cycle'ов, например, 4 → 6 → 7
и 5 → 6 → 7
, но компонента -- это именно максимальная по включению область, куда входят все они.
Определение 3: Циклом называется максимальный по включению сильно связный подграф, в котором одна из его вершин доминирует над всеми остальными. Эта вершина называется головным блоком (header) цикла, а все рёбра, идущие из данного цикла в головной блок, называются обратными рёбрами (backedge). Если обратное ребро одно, то оно ещё может называться latch (на русский переводится как "защёлка", но, если честно, звучит криво, я буду называть его "латч").
При этом цикл верхнего уровня -- это всегда компонента сильной связности, но внутри неё могут быть и другие вложенные циклы. Они не являются компонентами сильной связности (потому что не максимальны по включению), и они доминируются другой вершиной. Ниже будет пример, объясняющий это определение, если не поняли -- просто читайте дальше.
Определение 4: Ребро, идущее из цикла за его пределы, называется исходящим. Блок цикла, откуда оно выходит -- это выходящий блок (exiting block), а блок вне цикла, куда оно входит -- блок выхода (exit block).
На рисунке выше красная и зелёная компонента являются циклами. В красном цикле блок 3
одновременно является головным и латчем (он доминирует сам себя и сам в себя идёт). В зелёной компоненте головным является блок 8
, а латчем -- блок 9
. В синей же компоненте нет головного блока, потому что никакой из её блоков не доминирует все остальные. В этом легко убедиться: вы можете достичь вершин 6
и 7
как пройдя мимо вершины 4
, так и пройдя мимо вершины 5
. Ну или можете построить дерево доминирования и убедиться в этом ещё надёжнее.
Откуда в CFG берутся циклы и non-loop cycles
Слово Капитану Очевидность. Циклы в CFG берутся из циклов в исходном коде программы, для которой этот CFG строится. А точнее -- из конструкций типа do-while
, while
, for
и им подобных. На рисунках ниже схематично изображены циклы в CFG, получающиеся из соответствующих конструкций языка С++.
// 1
do {
// 2
if (...) {
// 3
} else {
// 4
}
// 5
} while (...);
// 6
![Цикл do-while. Голова - блок 2, латч - блок 5 Цикл do-while. Голова - блок 2, латч - блок 5](https://habrastorage.org/getpro/habr/upload_files/4ed/347/a8e/4ed347a8e56ddece3ae3b3917c1bcf4f.png)
2
, латч - блок 5
// 1
while ( /*2*/ ...) {
// 3
if (...) {
// 4
} else {
// 5
}
// 6
}
//7
![Цикл while. Голова - блок 2, латч - блок 6 Цикл while. Голова - блок 2, латч - блок 6](https://habrastorage.org/getpro/habr/upload_files/fb7/5c5/43c/fb75c543c95fb71129b279ed8ae80442.png)
2
, латч - блок 6
// 1
for (<init>; /*2*/ <check>; /*7*/ <increment>) {
// 3
if (...) {
// 4
} else {
// 5
}
// 6
}
// 8
![Цикл for. Цикл foreach будет выглядеть так же. Голова- блок 2, латч - блок 7 Цикл for. Цикл foreach будет выглядеть так же. Голова- блок 2, латч - блок 7](https://habrastorage.org/getpro/habr/upload_files/559/0fc/f2d/5590fcf2d7230b86a08afea9d4652926.png)
2
, латч - блок 7
Как видите, при прочих равных цикл do-while
выглядит несколько проще. По этой и ряду других причин компиляторы обычно предпочитают его в качестве канонической формы (но часто умеют обрабатывать и другие ситуации). Нетрудно понять, что цикл while
легко превратить в цикл do-while
следующим очевидным преобразованием:
while (cond) {
// do smth
}
--->
if (cond) {
do {
// do smth
} while (cond);
}
И аналогично можно поступить с циклом for/foreach
. Поэтому дальше большинство примеров будет относиться именно к циклам do-while
, имея в виду, что компилятор старается привести циклы именно к этой форме. В LLVM за это отвечает пасс Loop Rotate.
Как же получить non-loop cycle? Единственный известный мне способ этого добиться -- воспользоваться оператором goto
. Например, если вы напишете вот такой код
// 1
if (...)
// 2
goto label_in_loop;
// 3
do {
// 4
label_in_loop:
// 5
} while (...);
// 6
![Блоки 4 и 5 образуют non-loop cycle Блоки 4 и 5 образуют non-loop cycle](https://habrastorage.org/getpro/habr/upload_files/305/a55/5f6/305a555f61e688ac863d347e33f0d2c8.png)
Здесь блоки 4
и 5
образуют компоненту сильной связности, но непосредственным доминатором для них обоих является блок 1
. Он не входит в компоненту, поэтому эта парочка -- это non-loop cycles. На самом деле, не все non-loop cycles одинаково плохи: некоторые (и в частности этот) могут быть превращены в нормальный человеческий цикл, если выполнить первую итерацию данного non-loop cycle отдельно (мы прыгаем в середину только на первой итерации, а начиная со второй они выполняются как обычно), а есть такие, для которых и это невозможно. Мы пока что в сортах non-loop cycles разбираться не будем, а просто скажем, что наличие такой конструкции -- это проблема, и оптимизироваться она, скорее всего, не будет. Это, кстати, даёт некоторую рационализацию индоктринации первокурсников на тему "не пишите goto
, это плохой стиль". Действительно, не только стиль плохой, но ещё и вот такая вот гадость получиться может.
Вложенные циклы
Рассмотрим вот такую картину:
![Цикл {3, 4} вложен в цикл {2, 3, 4, 5, 7} Цикл {3, 4} вложен в цикл {2, 3, 4, 5, 7}](https://habrastorage.org/getpro/habr/upload_files/2dc/dda/670/2dcdda67006fc1d16e06a7f0bf46d1d3.png)
{3, 4}
вложен в цикл {2, 3, 4, 5, 7}
Здесь вершины {2, 3, 4, 5, 7}
образуют сильно связную компоненту, доминируемую вершиной 2
, то есть, цикл верхнего уровня. Однако вершины {3, 4}
также образуют сильно связный подграф, доминируемый вершиной 3
. Этот подграф не является компонентой сильной связности (а только её частью), но тем не менее {3, 4}
также является циклом с головным блоком 3
, который вложен в цикл {2, 3, 4, 5, 7}
с головным блоком 2
. Цикл {3, 4}
также называют дочерним, а {2, 3, 4, 5, 7}
-- родительским. Вложенность циклов может быть и больше, в этом случае можно говорить о циклах-внуках, правнуках и т.д. Такие конструкции получаются, когда, например, мы пишем
for (...) {
for (...) {
while (...) {
...
}
}
}
Несколько свойств, которые следует иметь в виду:
Все блоки, входящие в дочерний цикл, также входят в его родительский цикл. Таким образом, один блок может оказаться частью нескольких циклов (свой цикл, его родитель, дед, прадед и т.д.).
Все циклы верхнего уровня (то есть не имеющие родителя), являются компонентами сильной связности. Дочерние циклы таковыми не являются (они -- связные подграфы, являющиеся частями компонент своих родителей).
Выходящий блок внутреннего цикла может как быть выходящим блоком своего родителя, так и не быть. Так, на картинке выше блок
3
выходит из обоих циклов по ребру3 → 6,
а блок4
-- выходит из внутреннего цикла во внешний, но не выходит из внешнего, по ребру4 → 5
.Поскольку головной блок доминирует над всеми блоками цикла, путь по непосредственным доминаторам из любого циклового блока рано или поздно приведёт в головной блок.
Как искать циклы
Итак, теперь мы худо-бедно разобрались, что такое циклы. Обычно компиляторы строят для их хранения древовидные структуры, в которых циклы являются узлами, дочерние циклы -- детьми родительских, и содержат наборы соответствующих базовых блоков. Способов делать это -- несколько, ниже я опишу одну из возможных схем, которая используется в LLVM. Там за хранение циклов отвечает структура LoopInfo
и существует соответствующий анализ, который находит циклы всякий раз, когда они нужны.
Для алгоритма нам потребуется дерево доминирования, мы будем считать, что оно у нас есть и что мы умеем отвечать на вопрос о доминировании между двумя блоками. Как это делается, можно прочитать здесь. Схема алгоритма:
Будем идти по блокам в обратном порядке (post-order). Это обеспечит нам обработку заголовков вложенных циклов до того, как мы обработаем заголовок внешнего.
Проверяем, не является ли данный блок заголовком некоторого цикла:
Пусть
H
-- текущий блок,pred(H)
-- его предшественники (блоки, из которых есть рёбра вH
), аdom(H)
-- блоки, доминируемые блокомH
(т.е. блоки из его поддерева доминирования).Если
H
-- головной блок некоторого цикла, то у него есть обратные рёбра. По определению, множество обратных рёберB = pred(H) ∩ dom(H)
(то есть, блоки, доминируемыеH
и из которых есть ребро вH
). Если это пересечение не пустое, тоH
-- действительно заголовок некоторого цикла.В этом случае нужно найти остальные блоки этого цикла. Для этого запускаем любой графовый обход (DFS, BFS) из множества
B
, обход идёт по инвертированным рёбрам (то есть, после обработки блокаX
в очередь/стек будут положеныpred(X)
). Поднимаясь по предшественникам, мы обязаны по любому пути упереться в блокH
(по определению доминирования, в эти блоки нельзя было прийти иначе, как черезH
).Все блоки, которые мы пометили, относятся к циклу с заголовком
H
. Если среди них были головные блоки других циклов, эти циклы -- вложены в данный цикл.
Каноническая форма циклов
После того, как циклы найдены, компиляторы иногда стараются "причесать" их, или привести к некоторой канонической (стандартной, упрощённой и т.д.) форме. Это не обязательно, но это позволит проще имплементировать конкретные оптимизации, о которых будет рассказано позднее. Пока просто примем на веру, что так удобнее. Ниже -- несколько основных приёмов, которые могут быть использованы для каноникализации.
Избавление от множественных обратных рёбер. Такое может получиться, например, если вы пишете на С++ и используете ключевое слово continue. Каждый раз оно создаёт ребро в головной блок, и их может получиться несколько. Компилятор предпочитает иметь единственный латч вместо множества обратных рёбер, поэтому в этом случае он создаст новый блок, все старые обратные рёбра перенаправит в него, а уже этот блок -- в головной. Это потребует некоторых манипуляций с находящимися там финодами, каких именно -- оставляем как задачку для самостоятельного решения.
![Слева - два обратных ребра из блоков 3 и 4. Справа -- их перенаправили в блок 6, ставший единственным обратным ребром Слева - два обратных ребра из блоков 3 и 4. Справа -- их перенаправили в блок 6, ставший единственным обратным ребром](https://habrastorage.org/getpro/habr/upload_files/c84/82e/6b8/c8482e6b8cf8d107fa21b8c26c05ee30.png)
3
и 4
. Справа -- их перенаправили в блок 6
, ставший единственным обратным ребромВставка прехедера. Довольно часто оптимизации хотят вычислить некоторые выражения, которые нужны только если цикл будет исполняться, но не нужны в противном случае. Рассмотрим такой пример:
![Цикл без прехедера Цикл без прехедера](https://habrastorage.org/getpro/habr/upload_files/d10/7e2/450/d107e245025c8a7471ff5b8f8cd020ad.png)
Представьте, что мы хотим сгенерировать некоторое тяжеловесное выражение, которое не зависит от значений в цикле (и является инвариантом). Мы могли бы сделать это в блоке 1, но тогда это выражение бы вычислялось даже в том случае, если бы мы пошли по ребру 1 → 4
, что невыгодно, если цикл не будет исполняться. Чтобы иметь место, куда можно выносить такие выражения, CFG модифицируется так, чтобы нецикловой предшественник головного блока шёл только в головной блок. В данном случае нужно разбить ребро 1 → 2
и вставить туда новый блок, который будет называться прехедером (если кто-то знает адекватный русскоязычный аналог, дайте знать!)
![Вставка прехедера (блок 6) Вставка прехедера (блок 6)](https://habrastorage.org/getpro/habr/upload_files/7ae/818/f56/7ae818f5671e466eeb7f26648e7eff68.png)
6
)После двух вышеописанных манипуляций, у головного блока становится ровно два предшественника: прехедер и латч.
LCSSA-форма. Ещё одной каноникализацией, только не CFG, а инструкций, связанных с циклами, является построение замкнутой цикловой SSA-формы (Loop-Closed SSA form, LCSSA). Идея в следующем: как мы помним, в базовых блоках SSA-программы расположены инструкции. Создаваемые ими значения могут быть использованы другими инструкциями, и так далее.
Иногда оптимизатор хочет знать, какие из значений цикла нужны за его пределами. Он может этого хотеть по многим причинам, например -- если таких значений нет, то цикл можно вообще удалить, а если они инварианты -- вычислить их один раз за пределами цикла и потом удалить цикл. Причины могут быть и другие.
Проверить, используется ли значение за пределами цикла -- в принципе, несложно. Достаточно перебрать все инструкции, которые его используют, и для каждой такой инструкции проверить, содержится ли её блок в том же цикле. Проблема в том, что это дорого по времени (нужно перебирать всех пользователей), в то время как на практике число внутрицикловых значений, утекающих наружу, как правило, невелико.
Для удешевления этой задачи вводится следующее правило: пользователями внутрицикловых значений извне цикла могут быть только специальные финоды в блоках выхода (exit blocks). Все прочие инструкции используют эти финоды. Приведу простой пример:
define i32 @lcssa_example(i32 %n) {
entry:
br label %loop
loop: ; preds = %latch, %entry
%i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
%cond = icmp eq i32 %i, 1000
%i.2 = mul i32 %i, 2
br i1 %cond, label %exit1, label %latch
latch: ; preds = %loop
%i.next = add i32 %i, 1
%i.next.7 = mul i32 %i.next, 7
%loop.cond = icmp slt i32 %i.next, %n
br i1 %loop.cond, label %loop, label %exit2
exit1: ; preds = %loop
ret i32 %i.2
exit2: ; preds = %latch
ret i32 %i.next.7
}
Здесь внутрицикловые значения %i.2
и %i.next.7
используются вне цикла в блоках exit1
и exit2
, являющихся выходными. В канонической LCSSA-форме цикл будет переписан следующим образом:
define i32 @lcssa_example(i32 %n) {
entry:
br label %loop
loop: ; preds = %latch, %entry
%i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
%cond = icmp eq i32 %i, 1000
%i.2 = mul i32 %i, 2
br i1 %cond, label %exit1, label %latch
latch: ; preds = %loop
%i.next = add i32 %i, 1
%i.next.7 = mul i32 %i.next, 7
%loop.cond = icmp slt i32 %i.next, %n
br i1 %loop.cond, label %loop, label %exit2
exit1: ; preds = %loop
%i.2.lcssa = phi i32 [ %i.2, %loop ]
ret i32 %i.2.lcssa
exit2: ; preds = %latch
%i.next.7.lcssa = phi i32 [ %i.next.7, %latch ]
ret i32 %i.next.7.lcssa
}
Как видите, в блоках выхода были вставлены специальные финоды (в данном случае -- с одним входом), и все внешние пользователи внутрицикловых значений должны теперь использовать их.
Теперь для того, чтобы найти значения, которые вычисляются внутри цикла и используются вовне, достаточно пройти по блокам выхода, собрать их финоды и взять из них внутрицикловые значения, что, как правило, сильно быстрее (особенно если цикл -- огромный, а выходящих значений -- немного).
Вместо заключения
На сегодня всё. Мы пока ещё не добрались до конкретных оптимизаций, зато уже вооружились достаточным теоретическим багажом, чтобы нырять в них с головой. :) Надеюсь, что в следующих выпусках уже будет мясо. Оставайтесь с нами!