Как IndVarSimplification применяет математику в вашем коде / forpes.ru

Главная
Как IndVarSimplification применяет математику в вашем коде

Как IndVarSimplification применяет математику в вашем коде +30

29.05.2023 11:02

gir004 11 2500 Источник

Хочу поделиться своей историей расследования одной довольно необычной компиляторной оптимизации. Необычна она в том плане, что для нее производятся довольно нетривиальные математические вычисления. Приступим!

Чем я пользовался

Есть такой замечательный сайт: Compiler Explorer. Туда можно вставить код на одном из многих популярных языков программирования и посмотреть на ассемблер, в который этот код компилируется. Помимо ассемблера можно увидеть и другую полезную информацию, например промежуточные представления кода в процессе компиляции, а также список применяемых LLVM оптимизаций.

Рассмотрим вот такой простой код на языке Rust:

pub fn fancy_function(n: u64) -> u64 {
    let mut sum = 0;
    for i in 0..n {
        sum += i;
    }
    sum
}

Даже люди, не знакомые с Rust, смогут понять, что тут происходит: заводим переменную sum, проходим циклом по числам от до и суммируем их. Сумма возвращается из функции.

Казалось бы, как это можно упростить? Давайте заглянем в ассемблер:

Я нарисовал это в виде графа условных переходов. Зеленая ветка - если переход произошел, красная - если нет.

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

$1 + 2 + \dots + (n - 1) = \frac{n(n - 1)}{2}$

Да, действительно, по такой формуле все и считается. Это выглядит очень любопытно, давайте посчитаем более сложную сумму:

pub fn fancy_function(n: u64) -> u64 {
    let mut sum = 0;
    for i in 0..n {
        sum += i * i * i + 2 * i * i + 3 * i + 42;
    }
    sum
}

Здесь мы считаем сумму многочленов 3 степени. Кажется, я вспоминаю, как нам в универе рассказывали, что сумму любых многочленов можно выразить в виде формулы от n. Выведет ли эту формулу компилятор?

Да, это произошло! Формула конечно гораздо сложнее, чем в первом случае, но это все еще формула, которая считается за .

На этом моменте мне захотелось разобраться, кто, в какой момент и каким образом проводит эту замечательную оптимизацию, и я начал с описания процесса компиляции Rust. Если вкратце, то код на языке Rust оптимизируется в двух местах:

Mid-level Intermediate Representation (MIR) - представление кода, в котором убран весь синтаксический сахар и выведены типы всех объектов. На данном этапе применяются оптимизации, специфичные для языка Rust.
LLVM Intermediate Representation (LLVM-IR) - формат кода, который передается в LLVM для последующей компиляции в бинарный файл. Здесь применяются оптимизации LLVM.

Попробуем отключить оптимизации MIR. Для этого выберем nightly версию компилятора Rust и посмотрим. Для простоты я вернулся к первому примеру с суммой от до

А теперь наоборот, включим оптимизации MIR и выключим оптимизации LLVM:

Видите голубую стрелочку наверх? Это цикл! И даже в ассемблере больше нет инструкций умножения чисел, только сложения. Выходит это оптимизация на уровне LLVM? Давайте проверим.

В Compiler Explorer можно вывести список всех примененных оптимизаций, и среди них я нашел такую:

Оптимизация называется IndVarSimplifyPass. Тут было удалено тело цикла и вынесено в виде формулы . А то, что осталось от цикла, будет удалено позже другими оптимизациями.

Беглым взглядом пробежавшись по исходному коду IndVarSimplifyPass, я нашел комментарий о том, что вся "магия" происходит с помощью Scalar Evolution Evaluation.

Перед тем, как читать его исходный код, я посмотрел видео на YouTube от LLVM, где разбирается SCEV Evaluation, и вкратце объясняется, какая математика за этим стоит.

Если вкратце, то бывают простые рекуррентные последовательности, записывающиеся в нотации $\{b, +, c\}$ :

$\{b, +, c\} = b, b + c, b + 2c, b + 3c, \dots$

То есть это обычная арифметическая прогрессия. Можно подняться на уровень выше и получить более сложную:

$\{a, +, b, +, c\} =\{a, +, \{b, +, c\}\} = a, a + b, a + 2b + c, a + 3b + 3c, a + 4b + 6c, \dots$

То есть начинаем с элемента , а затем на каждом шаге прибавляем элементы арифметической прогрессии $\{b, +, c\}$ . Можно аналогично определять последовательности больших порядков.

В данной нотации можно выразить сумму i-го элемента:

$\{x_1, +, x_2, +, \dots, +, x_n\}_i = x_1 \binom{i}{0} + x_2 \binom{i}{1} + \ldots + x_n \binom{i}{n - 1}$

А сумму можно выразить так:

$\sum_{i = 1}^n \{x_1, +, \dots, +, x_n\} = \{0, +, x_1, +, \dots, +, x_n\}_n$

А еще есть правила, по которым такие последовательности можно поэлементно складывать и умножать.

И вот, проглядев код SCEV Evaluation, я нашел места, где происходят математические вычисления:

Тут вычисляются биномиальные коэффициенты
Тут считается i-й элемент последовательности
Тут считается сумма двух последовательностей
А тут вычисляется произведение последовательностей.

Чтобы окончательно разобраться в этом, я написал простой парсер выражений, в который вводится формула i-го элемента (в виде полинома от i), и выводится формула суммы этих элементов при i от 0 до Пример:

Посмотреть код и попробовать можно в моем репозитории.

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

Комментарии (11)

OBIEESupport
29.05.2023 11:17
#25594404
+2
То, насколько изящно вы это сделали, замечательно говорит, что теория компиляторов (элементы которой вы тут показали) не зря называется "математикой, застывшей в ассемблере".

Izaron
29.05.2023 11:17
#25595692
+4
Для полноты рассказа (для тех, кто на "вы" с компиляторами) можно сказать, что язык Rust имеет к теме статьи очень посредственное отношение (это может быть важно знать).

В тулчейне LLVM есть название "фронтенд" для программы, которая переводит исходный код в LLVM IR, и "бэкенд" для программы, которая оптимизирует LLVM IR и переводит его в ассемблер.

Для нового языка программирования достаточно написать только "фронтенд", то есть переводчик исходника в LLVM IR. Сначала "фронтенд" был только один - Clang (для языков C/C++/Objective-C), затем появились другие для новых языков, в том числе для Rust.

Другими словами, примерные программы в статье могли бы быть написаны вместо Rust на C, C++ или куче других языков, а смысл остался бы тем же.
1. gir004 Автор
  29.05.2023 11:17
  #25595946
  +1
  Да, большое спасибо за уточнение! Я забыл об этом написать, но я пробовал компилировать подобный код на C и C++, и везде оптимизация срабатывала.
  
  Однако у rust есть другая особенность: если написать цикл от 0 до n включительно (через for i in 0..=n), то оптимизация не срабатывает, хотя если написать код "по-простому" (без range based for), то оптимизация работает.

kovserg
29.05.2023 11:17
#25595746
+3
В заключение, хочу выразить мысль, что такая оптимизация в очередной раз подчёркивает, что код, который вы написали, не обязательно будет совпадать в точности с тем, что будет исполнять процессор.

Хочу выразить другую мысль: мы видим движение куда-то не туда. Мы написали императивный код который описывает что надо сделать, а оптимизатор делает это по своему. Может пора уже переходить на декларативный уровень? Где вы описываете что надо и какие преобразования, предположения и инварианты есть что бы компилятор генерировал код на основе явных инструкций. Не применительно к данной оптимизации в C++ есть довольно большой зоопарк предположений (не всегда верных, даже в большинстве случаев не верных) на которых он строит свои оптимизации. В результате иногда бывает очень весело.
1. Izaron
  29.05.2023 11:17
  #25596052
  +3
  Мы написали императивный код который описывает что надо сделать, а оптимизатор делает это по своему
  
  Оптимизатор сделал ровно то, что требуется. Проанализировал граф зависимостей между переменными и выяснил, как его можно переупорядочить и упростить, не нарушая инварианты по side effects, которые были в исходном коде. Код от этого не перестал быть императивным.
  
  Может пора уже переходить на декларативный уровень?
  
  Тогда C++ это уже супер декларативный уровень, потому что в ассемблере нет никаких классов, лямбд, исключений. Инварианты для компилятора тоже можно наставить [[assume]].
  
  в C++ есть довольно большой зоопарк предположений (не всегда верных, даже в большинстве случаев не верных) на которых он строит свои оптимизации
  
  C++ это достаточно зрелый язык, что у него есть модель памяти (у модного Rust ее нет...) Большинство предположений соответствуют ей и строги математически.
  
  Например, если читать из одного и того же адреса в цикле, то C++ соптимизирует это в одно чтение, предполагая, что незачем читать больше одного раза одно и то же - нет side effect. Чтобы указать, что это не так (например, на железке в этот адрес какой-то другой процесс может записывать числа) и каждое чтение это наличие side effect, нужен модификатор volatile.
  1. kovserg
    29.05.2023 11:17
    #25596122
    +1
    C++ это достаточно зрелый язык, что у него есть модель памяти
    
    Не то слово, даже перезрелый. Вот какие грибы надо было есть что бы такое стандартизировать? https://youtu.be/ZgZ4_2YwtDQ?t=533
    
    yeputons
    29.05.2023 11:17
    #25596464
    А какие альтернативы? Это уже по факту было и компиляторами использовалось. Strict aliasing rule и оптимизации вроде "указатели из разных массивов не могут указывать на один и тот же элемент" берутся отсюда же. А дальше либо мы как-то убеждаем компиляторы не делать какие-то оптимизации, либо легализуем такое поведение в стандарте и попутно пытаемся придать ему смысл. Второе кажется вероятнее.

Refridgerator
29.05.2023 11:17
#25596644
Если int помененять на double, останется ли эта оптимизация? Справится ли оптимизатор с чуть более сложными вычислениями, например:?
```
double avg = 0;
for(int k=1;i<=n;i++)
{
	avg+=pow(2*cos(2*k*pi/n),2);
}
```
1. gir004 Автор
  29.05.2023 11:17
  #25597464
  К сожалению (или к счастью), нет, такое не сработает. Дело в том, что IndVarSimplification оптимизирует только весьма ограниченный ряд последовательностей. Это арифметические прогрессии, ряды, где разницы между соседними элементами образуют арифметическую прогрессию и т.д. А функции cos и pow кажется могут вообще не заинлайниться, и оптимизации точно не произойдет
  1. kovserg
    29.05.2023 11:17
    #25597730
    +1
    Для этого есть maple где вы сначала делаете аналитические преобразования, можно потом выполнить разложение и потом попросить сгенерировать код на C. Дальше уже оценить приближение и области применимости.

Readme
29.05.2023 11:17
#25597524
+5
Хороший разбор и примеры. Интересно, что материал неявно затрагивает ещё одну важную тему: SCEV Evaluation является прекрасным примером оптимизации, честно полагающейся на отсутствие UB (undefined behavior) в исходном коде. Мы применяем матаппарат на множестве целых чисел, чтобы вывести некоторые результирующие формулы, но они с большой вероятностью перестают работать, если допустить целочисленное переполнение на итерациях суммирования (однако, не исключено, что формулы справедливы в арифметике по модулю 2⁶⁴, например).

Как IndVarSimplification применяет математику в вашем коде +30

Комментарии (11)

gir004 Автор

gir004 Автор