Поговорим об оптимизирующих компиляторах. Сказ четвёртый: Циклы

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

1. SSA форма

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

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

4. Циклы

5. CSE

6. Цикловые инварианты

7. Проверки диапазонов

8. Размотка циклов

Если вы не читали первые две части этого курса (про 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

Цикл do-while. Голова - блок 2, латч - блок 5

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

Цикл while. Голова - блок 2, латч - блок 6

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

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

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

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

Цикл {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, ставший единственным обратным ребром

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

Цикл без прехедера

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

Вставка прехедера (блок 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
}

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

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

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

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