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

1. SSA форма

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

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

4. Циклы

5. CSE

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

Сегодня мы поговорим о нескольких разных классах оптимизаций, которые позволяют компилятору увеличивать быстродействие наших программ. Для тех, кто здесь впервые, стоит сначала прочитать статьи об 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 -- это всего лишь частные случаи последнего, самого тяжеловесного преобразования. Тем не менее, на практике они тоже важны, так как их выполнение гораздо дешевле с точки зрения времени компиляции и не приводит к чрезмерному раздуванию объёма кода.

Заключение

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