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

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

1. SSA форма

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

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

4. Циклы

5. CSE

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

Когда вычисления бывают лишними

Когда мы пишем код, в нас иногда просыпается внутренний перфекционист, которому кажется, что он мог бы разогнать свою программу, заменив какие-то дублирующиеся вычисления на времянки. Например, вот в такой функции:

bool foo(int x, int y) {
  int sum1 = x * x + 2 * x * y + y * y;
  int sum2 = x * x - 2 * x * y + y * y;
  return sum1 ==  2 * sum2;
}

Нетрудно заметить, что выражения x * x, 2 * x * y и y * y вычисляются дважды. Мы могли бы вычислить их отдельно, а потом переиспользовать их для вычисления sum1 и sum2. Получится что-то вроде:

bool foo(int x, int y) {
  int tmp1 = x * x;
  int tmp2 = 2 * x * y;
  int tmp3 = y * y;
  int sum1 = tmp1 + tmp2 + tmp3;
  int sum2 = tmp2 - tmp2 + tmp3;
  return sum1 ==  2 * sum2;
}

Таким образом, мы сэкономили на умножениях, выполнив их вдвое меньше. Теперь видно, что в обе суммы входит подвыражение tmp1 + tmp3, и его также можно вынести во времянку и сэкономить одно сложение:

bool foo(int x, int y) {
  int tmp1 = x * x;
  int tmp2 = 2 * x * y;
  int tmp3 = y * y;
  int tmp4 = tmp1 + tmp3;
  int sum1 = tmp4 + tmp2;
  int sum2 = tmp4 - tmp2;
  return sum1 ==  2 * sum2;
}

Новый код содержит всего 8 операций сложения и умножения вместо 13, и это только за счёт того, что мы просто не стали считать одни и те же выражения дважды. Данный пример можно было бы оптимизировать и иначе, заметив, что обе суммы -- это знакомые нам со школы формулы квадрата суммы и квадрата разности, но об этом классе оптимизаций мы поговорим потом. Сегодня всё, что нас интересует -- это одни и те же подвыражения, которые мы считаем более одного раза. Для их удаления не нужно знать никаких математических формул или хитрых теорем, достаточно понять, что мы делаем одно и то же.

А теперь представьте, что кто-то добрый отрефакторил изначальный код, написав что-то вроде

// Compute (x + y) ^ 2
int square_sum(int x, int y) {
  return x * x + 2 * x * y + y * y;
}

// Compute (x - y) ^ 2
int square_sub(int x, int y) {
  return x * x - 2 * x * y + y * y;
}

bool foo(int x, int y) {
  int sum1 = square_sum(x, y);
  int sum2 = square_sub(x, y);
  return sum1 ==  2 * sum2;
}

Несмотря на то, что рефакторинг был максимально невинным, теперь общие подвыражения находятся в разных функциях. Стоит ли выдёргивать куски кода из них, копируя их в foo, только ради сокращения числа операций? С точки зрения управления кодом проекта, это крайне плохая идея.

В среде компиляторщиков бытует шутка, что мы никогда не останемся без работы, поскольку лучшие практики организации кода прямо противоположны лучшим практикам его оптимизации. Делая код более читаемым, мы часто убиваем возможности что-нибудь соптимизировать в нём руками. И задачей компилятора является как раз разрешение этого противоречия.

Хорошая новость состоит том, что большинство современных компиляторов отлично справляются с этим примером как до, так и после рефакторинга. При этом исходный код остаётся неизменным, а все преобразования, включая инлайнинг тел вызываемых функций и дальнейшее обнаружение общих подвыражений в них, делаются на внутреннем представлении во время оптимизации. В этой статье мы разберём основные способы, как это делается.

Удаление лишних подвыражений в блоке. Локальный CSE

Самая простая оптимизация, которая позволит нам повыкидывать лишние подвыражения, так и называется -- "Удаление общих подвыражений" (Common Subexpression Elimination, CSE). Эта оптимизация, как и многие другие, может выполняться локально (в рамках одного базового блока), или глобально (в рамках целой функции). Рассмотрим сначала самый простой вариант, когда у нас только один блок и нет никакой передачи потока управления. Запишем нашу исходную функцию в SSA-форме:

define i1 @foo(i32 %x, i32 %y) {
  %x2_1 = mul i32 %x, %x
  %x_times_2_1 = mul i32 2, %x
  %xy_times_2_1 = mul i32 %x_times_2_1, %y
  %x2_plus_2xy = add i32 %x2_1, %xy_times_2_1
  %y2_1 = mul i32 %y, %y
  %sum1 = add i32 %x2_plus_2xy, %y2_1
  %x2_2 = mul i32 %x, %x
  %x_times_2_2 = mul i32 2, %x
  %xy_times_2_2 = mul i32 %x_times_2_2, %y
  %x2_minus_2xy = sub i32 %x2_2, %xy_times_2_2
  %y2_2 = mul i32 %y, %y
  %sum2 = add i32 %x2_minus_2xy, %y2_2
  %sum2_times_2 = mul i32 2, %sum2
  %result = icmp eq i32 %sum1, %sum2_times_2
  ret i1 %result
}

Самый простой алгоритм удаления общих подвыражений выглядит следующим образом:

1. Бежим по инструкциям в блоке сверху вниз.

2. Для каждой инструкции, перебираем все предыдущие инструкции и пытаемся найти аналогичную (т.е. инструкцию с таким же опкодом и такими же аргументами).

3. Если нашли, то заменяем все использования текущей инструкции на найденную, текущую удаляем.

Нетрудно понять, что в худшем случае (когда мы вообще ни разу не найдём одинаковой инструкции), алгоритмическая сложность этой оптимизации -- O(N²). Её можно существенно ускорить, если вместо того, чтобы всякий раз искать заново аналогичную инструкцию, поддерживать множество увиденных ранее инструкций. Его можно организовать по-разному (и получить разные оценки ускорения), но в самом простом варианте мы можем просто хранить unordered_map<{opcode, op1, op2, ...}, Instruction*>. В этом случае алгоритм будет иметь линейную сложность и выглядеть следующим образом:

1. Бежим по инструкциям сверху вниз.

2. Для каждой инструкции формируем структуру-дексриптор (из опкода и операндов) и проверяем, есть ли в множестве инструкция с таким же дескриптором.

3. Если да, то заменяем текущую инструкцию на найденную и удаляем. Если нет, добавляем дескриптор текущей инструкции и её саму в множество.

Если мы последуем этому алгоритму, то в нашем примере удастся сделать следующие оптимизации:

• %x2_2 заменится на %x2_1

• %x_times_2_2 заменится на %x_times_2_1

• %xy_times_2_2 заменится на %xy_times_2_1

• %y2_2 заменится на %y2_1

В LLVM можно добиться этого результата при помощи пасса EarlyCSE.

Результат неплохой: оптимизация сделала ровно то, что мы делали руками до того, как заметили, что можно ещё посчитать (x * x + y * y) однажды. Спойлер: современный LLVM даже на уровне -O3 не может вытащить это подвыражение, однако способ есть. Я опишу его в статье, желающие потом смогут его запрограммировать в LLVM. :)

Сложная эквивалентность простых инструкций

В нашем мы полагаемся на то, что эквивалентные инструкции имеют одинаковый кортеж из опкода и операндов. На самом деле, эквивалентными могут быть инструкции с разными операндами и разными опкодами. Например, следующие пары инструкций эквивалентны:

• add i32 %x, %y и add i32 %y, %x

• add i32 %x, %x и mul i32 %x, 2

• mul i32 %x, 2 и shl i32 %x, 1

И так далее. Иными словами, существует много способов выразить одинаковые подвыражения. Хуже того, сумму (a + b + c + d) можно записать также как (d + a + c + b), получив при этом сразу несколько инструкций, таких, что равны друг другу будут только итоговые суммы, но не промежуточные результаты.

Давайте сначала разберём простой случай, то есть когда есть две эквивалентные инструкции, у которых разный опкод и/или набор операндов. При построении компиляторов существует два основных подхода к тому, как обеспечить работу оптимизаций в таких случаях. Их можно описать следующим образом:

1. Сильные проверки. Для этого пишутся различные утилиты функции вроде bool isEquivalent(const Instruction *, const Instruction *), которые содержат логику, доказывающую, что две произвольные инструкции на самом деле эквивалентны друг другу. Разные оптимизации пользуются этими утилитами. Это делает их более тяжеловесными (вместо банального сравнения кортежей приходится выполнять сложные проверки), но и более устойчивыми к тому, что пришло им на вход. В нашем случае использование этого подхода в алгоритме с хэшмапом было бы затруднительно, хотя квадратичный алгоритм с этой проверкой работал бы отлично (но медленно).

2. Каноникализация. Предполагается, что существует некоторая каноническая форма записи всех эквивалентных инструкций. То есть изо всех вариантов типа (x + x, x * 2, x << 1) какой-то один признаётся каноническим, а все остальные -- ересью и мракобесием. Существует отдельная трансформация, которая приводит все инструкции к их канонической форме, а все остальные оптимизации вправе ожидать, что они придут ей на вход именно в таком виде. Этот подход требует, чтобы все оптимизации, которые модифицируют код, поддерживали каноническую форму, либо что перед каждой оптимизацией, которая на это полагается, кто-то проведёт каноникализацию. Система становится более хрупкой к ошибкам, но всё в целом начинает работать быстрее.

На практике оба подхода сочетаются, хотя обычно предпочтение отдаётся каноникализации. Окупаются ли затраты на построение канонической формы -- вопрос скорее религиозный, чем научный.

Символьные вычисления решают проблему abcd

К сожалению, каноникализация неспособна решить проблему эквивалентности выражений a + b + c + d и d + a + c + b. Её в теории мог бы решить очень-очень умный метод isEquivalent, но он в таком случае был бы очень тяжёлым, так как ему пришлось бы бегать по деревьям выражений. Попробую в общих чертах описать схему решения данной проблемы "малой кровью". Подробное описание тянет на отдельную статью (и мы будем что-то подобное рассматривать в статье про SCEV), но я надеюсь, что общая схема будет понятна.

Теперь в наш map будут класться не просто кортежи из опкода и их непосредственных операндов, но некоторые виртуальные узлы, которые могут быть

1. Инструкцией

2. Константой

3. Простой арифметической операцией

Причём эти деревья также каноникализируются по собственным правилам, например:

1. Константы всегда сворачиваются

2. Когда операндов много, они сортируются единым образом (например, по алфавиту)

3. Все скобки раскрываются

И т.п. Приведу пример. Пусть есть код:

define i1 @example_abc(i32 %a, i32 %b, i32 %c) {
  %sum1 = add i32 %a, %b
  %sum2 = add i32 %sum1, %c

  %sum3 = add i32 %c, %a
  %sum4 = add i32 %b, %sum3

  %eq = icmp eq i32 %sum2, %sum4
  ret i1 %eq
}

При добавлении %sum1, кладётся кортеж {+, a, b}. При добавлении %sum2, нужно было бы добавить {+, {+, a, b}, c}, но мы сначала раскроем все скобки и добавим {+, a, b, c}. Далее, %sum3 после сортировки операндов превратится также в {+, a, c}, а потом {+, b, {+, a, c}} после раскрытия скобок и сортировки операндов также превращается в тот же {+, a, b, c}.

Со сложением разобрались. Теперь вернёмся к нашему изначальному примеру, в котором мы уже убрали все тривиально одинаковые выражения и получили вот это:

define i1 @foo(i32 %x, i32 %y) {
  %x2_1 = mul i32 %x, %x
  %x_times_2_1 = mul i32 2, %x
  %xy_times_2_1 = mul i32 %x_times_2_1, %y
  %x2_plus_2xy = add i32 %x2_1, %xy_times_2_1
  %y2_1 = mul i32 %y, %y
  %sum1 = add i32 %x2_plus_2xy, %y2_1
  %x2_minus_2xy = sub i32 %x2_1, %xy_times_2_1
  %sum2 = add i32 %x2_minus_2xy, %y2_1
  %sum2_times_2 = mul i32 2, %sum2
  %result = icmp eq i32 %sum1, %sum2_times_2
  ret i1 %result
}

Давайте просто выпишем все кортежи с раскрытием всех скобок, и посмотрим, что получается:

define i1 @foo(i32 %x, i32 %y) {
  %x2_1: {*, x, x}
  %x_times_2_1: {*, 2, x}
  %xy_times_2_1: {*, 2, x, y}
  %x2_plus_2xy: {+, {*, x, x}, {*, 2, x, y}}
  %y2_1: {*, y, y}
  %sum1: {+, {*, x, x}, {*, 2, x, y}, {*, y, y}}
  %x2_minus_2xy: {+, {*, x, x}, {*, -2, x, y}}
  %sum2: {+, {*, x, x}, {*, -2, x, y}, {*, y, y}}
  ...
}

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

CSE на сложном CFG

Итак, мы примерно поняли, что делать в рамках одного базового блока. Но очевидно, что в реальности функции обычно имеют циклы/условные переходы. На самом деле, переход от локального CSE к глобальному -- очень простой.

Помните, как мы заполняли наш unordered_map? В начале блока он пустой, а по ходу работу мы добавляли все новые увиденные инструкции, которые не удалось заменить на эквиваленты. Вспоминаем, что такое дерево доминирования и непосредственный доминатор (для тех, кто забыл, есть соответствующая статья). Непосредственный доминатор -- это ближайший блок, который точно выполнится до того, как мы будем выполнять данный блок, и все его инструкции (а также все инструкции из всех других доминаторов) видны в данном блоке. Короче говоря, единственным отличием станет то, что мы можем инициализировать наш unordered_map не пустым, а содержанием этого map'а в конце непосредственного доминатора. Простой пример:

define void @foo(i32 %a, i32 %b, i32 %c) {
  %sum1 = add i32 %a, %b
  %sum2 = add i32 %sum1, %c
  %cond = icmp sgt i32 %a, 100
  br i1 %cond, label %if.true, label %if.false

if.true:                                          ; preds = %entry
  %sum3 = add i32 %c, %a
  %sum4 = add i32 %sum3, %b
  call void @foo(i32 %sum4)
  br label %done

if.false:                                         ; preds = %entry
  %sum5 = add i32 %c, %b
  %sum6 = add i32 %sum5, %a
  call void @foo(i32 %sum6)
  br label %done

done:                                             ; preds = %if.false, %if.true
  ret void
}

declare void @foo(i32)

В конце блока entry в нашем мэпе будет лежать

sum1: {+, a, b}
sum2: {+, a, b, c}

Блоки if.true и if.false, для которых entry является непосредственным доминатором, и поэтому в них видны все значения из entry. В них можно изначально положить в мэп те же инструкции и потом заменить %sum4 и %sum6 на их эквивалент из первого блока.

CSE и нумерация значений

Параллельно с локальным и глобальным CSE существуют также оптимизации локальной и глобальной нумерации значений (Local/Global Value Numbering, LVN/GVN). Их цель примерно такая же, но вместо построения символьных кортежей выражений (которые на больших функциях имеют тенденцию сильно раздуваться) они решают аналогичную задачу тем, что вводят для каждого значения особый номер по таким правилам, чтобы разные номера соответствовали разным инструкциям, а у эквивалентных они совпадали (ситуация, когда инструкции эквивалентны, но номера разные, является допустимой, но говорит о том, что алгоритм недоработал). В целом, всё очень похоже на то, что мы делали при построении символьных деревьев с раскрытием скобок, только на каждом этапе вместо деревьев выступают некоторые хэши, посчитанные по особым правилам. Так, требуется, чтобы number(+, a, b) был равен number(+, b, a) и т.д.

Выбор между CSE и VN обычно определяется практическими соображениями (у них по-разному растёт стоимость на больших программах), мне чаще всего попадались ситуации, когда CSE применяется локально или на простом CFG (например, в LLVM пасс EarlyCSE не ходит сквозь точки слияния кода, что упрощает его алгоритм), а нумерация значений используется глобально (так получается дешевле). Тем не менее, описания и общие принципы работы этих оптимизаций весьма сходны, проблема построения функции нумерации эквивалентна проблеме каноникализации символьных деревьев, поэтому можно сказать, что это тот же самый (или очень похожий) алгоритм, описанный в других терминах. Поэтому подробно я его описывать не буду.