Поговорим об оптимизирующих компиляторах. Сказ шестой: цикловые инварианты

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

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

Заключение

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

ссылка на оригинал статьи https://habr.com/ru/articles/764636/