Это цикл статей об оптимизирующих компиляторах вообще и LLVM в частности. Смотри все статьи данного цикла:

1. SSA форма

2. Доминирование

3. Неопределённое поведение

4. Циклы

Если вы не читали первые две части этого курса (про 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: Максимальный по включению связанный подграф называется компонентой сильной связности.

Проще всего понять, что это за монстр, если посмотреть внимательно вот на такой граф:

Как видите, вершины 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

// 1
while ( /*2*/ ...) {
  // 3
  if (...) {
    // 4
  } else {
    // 5
  }
  // 6
}
//7

// 1
for (<init>; /*2*/ <check>; /*7*/ <increment>) {
  // 3
  if (...) {
    // 4
  } else {
    // 5
  }
  // 6
}
// 8

Как видите, при прочих равных цикл 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 образуют компоненту сильной связности, но непосредственным доминатором для них обоих является блок 1. Он не входит в компоненту, поэтому эта парочка -- это non-loop cycles. На самом деле, не все non-loop cycles одинаково плохи: некоторые (и в частности этот) могут быть превращены в нормальный человеческий цикл, если выполнить первую итерацию данного non-loop cycle отдельно (мы прыгаем в середину только на первой итерации, а начиная со второй они выполняются как обычно), а есть такие, для которых и это невозможно. Мы пока что в сортах non-loop cycles разбираться не будем, а просто скажем, что наличие такой конструкции -- это проблема, и оптимизироваться она, скорее всего, не будет. Это, кстати, даёт некоторую рационализацию индоктринации первокурсников на тему "не пишите goto, это плохой стиль". Действительно, не только стиль плохой, но ещё и вот такая вот гадость получиться может.

Вложенные циклы

Рассмотрим вот такую картину:

Здесь вершины {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. Каждый раз оно создаёт ребро в головной блок, и их может получиться несколько. Компилятор предпочитает иметь единственный латч вместо множества обратных рёбер, поэтому в этом случае он создаст новый блок, все старые обратные рёбра перенаправит в него, а уже этот блок -- в головной. Это потребует некоторых манипуляций с находящимися там финодами, каких именно -- оставляем как задачку для самостоятельного решения.

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

Представьте, что мы хотим сгенерировать некоторое тяжеловесное выражение, которое не зависит от значений в цикле (и является инвариантом). Мы могли бы сделать это в блоке 1, но тогда это выражение бы вычислялось даже в том случае, если бы мы пошли по ребру 1 → 4, что невыгодно, если цикл не будет исполняться. Чтобы иметь место, куда можно выносить такие выражения, CFG модифицируется так, чтобы нецикловой предшественник головного блока шёл только в головной блок. В данном случае нужно разбить ребро 1 → 2 и вставить туда новый блок, который будет называться прехедером (если кто-то знает адекватный русскоязычный аналог, дайте знать!)

После двух вышеописанных манипуляций, у головного блока становится ровно два предшественника: прехедер и латч.

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
}

Как видите, в блоках выхода были вставлены специальные финоды (в данном случае -- с одним входом), и все внешние пользователи внутрицикловых значений должны теперь использовать их.

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

Вместо заключения

На сегодня всё. Мы пока ещё не добрались до конкретных оптимизаций, зато уже вооружились достаточным теоретическим багажом, чтобы нырять в них с головой. :) Надеюсь, что в следующих выпусках уже будет мясо. Оставайтесь с нами!