Недавно друг написал мне:
А знаешь, что было бы интересно? Почитать про то, как меняется код после применения оптимизаций.
Я сразу подумал «Ну да, есть же тысячи статей и видео на эту тему». Но большая часть из них предполагает знание соответствующих терминов, внутренностей компилятора, IR и так далее. Проблема в том, что те, кто использует компиляторы (как мой друг) обычно не интересуются подобным. Их не интересует LLVM IR, что такое нода φ или какой цикл называется loop rotation и почему. Их интерес, по мере убывания, заключается в следующем: (1) что, (2) почему и (3) как.
Что. Прежде всего, пользователи хотят знать, что компилятор в состоянии сделать, а что нет — то есть что им нужно оптимизировать самим вручную, а что можно оставить компилятору.
Почему. Далее, им может быть интересно, почему компилятор оптимизировал именно так (к примеру, почему выбрал одну инструкцию вместо другой).
Как. Это затрагивает то, как именно компилятор достигает результата — то есть его устройство. Но это обычно интересует людей в последнюю очередь — скорее для удовлетворения собственного любопытства, нежели для работы.
В этой статья я объясню оптимизации на нескольких примерах. По большей части фокус будет на том, что происходит, затрагивая почему и как только когда это имеет смысл или особый интерес. Чтобы не делать эту статью слишком длинной, некоторые детали, в том числе как и почему, были вынесены в отдельное дополнение.
Стоит заметить, что в приведенных примерах будет использоваться C, а в некоторых случаях — когда C будет слишком высокоуровневым — x86–64 assembly. LLVM IR использоваться не будет, а касаться внутренностей компилятора и терминов буду только в разделах, посвященных тому, как это работает.
И наконец, я бы хотел использовать реальные примеры для каждого из случаев, но иногда это может сильно усложнить понимание концепций. Так что выбор примеров будет разниться от случая к случаю.
Арифметика
Начнем с простого, а именно с такой функции:
int times2(int n) {
return n*2;
}В целом, компиляторы довольно хорошо справляются с оптимизацией арифметических, логических и прочих скалярных операций. Даже в таком простом случае, когда, казалось бы, особо нечего делать, он сгенерировал следующий код при ‑O1 (godbolt) :
times2(int):
lea eax, [rdi+rdi]
retТо есть по сути компилятор превратил функцию в:
int times2(int n) {
return n+n;
}Почему так произошло вы можете прочитать в дополнении.
Давайте теперь взглянем на реалистичный пример, чтобы примерно понять ограничения компилятора при работе с арифметическими операциями на основе этого поста. Ниже чуть упрощенный код оригинала:
typedef struct Float2 {
float x, y;
} Float2;
Float2 ProjectSphere(float x, float z, float r,
float t, float ResultScale) {
float tz = t*z;
float rx = r*x;
float tx = t*x;
float rz = r*z;
float A = (tz + rx);
float B = (tz - rx);
float Min = (tx - rz) / A;
float Max = (tx + rz) / B;
Float2 Res = {Min*ResultScale, Max*ResultScale};
return Res;
}Поясню, какие изменения были внесены. В первую очередь для сокращения примера было удалено вычисление sqrt — оно не требуется для иллюстрации. Во‑вторых общие подвыражения (т. е. те, что встречаются по несколько раз) были перемещены в переменные, чтобы сделать код более читаемым. Мы вернемся к этому, когда дойдем до убирания общих подвыражений.
Итак, в самом посте показана оптимизация кода во избежание двух делений, поскольку деление в целом работает медленно на любом железе. Она использует следующую формулу:
Понятное дело, что z не должно быть равно 0. У нас есть два значения, одно из которых мы хотим разделить на A, другое — на B. Оптимизация в том, что мы разделим оба на A * B и затем умножим одно из них на A (получив B в знаменателе), а другое на B (получив A в знаменателе). Итак:
Float2 ProjectSphere(float x, float z, float r,
float t, float ResultScale) {
float tz = t*z;
float rx = r*x;
float tx = t*x;
float rz = r*z;
float A = (tz + rx);
float B = (tz - rx);
// Was: Nothing
ResultScale /= (A * B);
// Was: float Min = (tx - rz) / A;
float Min = (tx - rz) * B;
// Was: float Max = (tx + rz) / B;
float Max = (tx + rz) * A;
Float2 Res = {Min*ResultScale, Max*ResultScale};
return Res;
}Вопрос в следующем: Может ли компилятор сделать это сам? Выглядит реалистично, так как оптимизация необычная, но не слишком. Итак, попробуем -O3 с разными компиляторами. GCC дает два деления, что не особо хорошо. Clang чуть умнее и немного векторизует код. По сути, он создал следующий вектор: X = {(tx -rz), (tx + rz)}. Затем еще один: Y = {A, B}. И разделил X на Y. Так мы выполнили два деления, используя одну инструкцию деления.
Интересный случай получился с ICX. Он смог сгенерировать код совсем без делений… ну почти. По сути, получился следующий код:
Float2 ProjectSphere(float x, float z, float r, float t, float RS) {
float tz = t*z;
float rx = r*x;
float tx = t*x;
float rz = r*z;
float A = t*z + r*x;
float B = t*z - r*x;
float v = {A, B, A, B};
float rec_v = {1/A, 1/B, 1/A, 1/B};
float Min_s = tx - rz;
float Max_s = tx + rz;
float MinMax = {Min_s, Max_s, Min_s, Max_s};
float RS_v = {RS, RS, RS, RS};
// Focus on only the first two elements from here on.
// Anyway these are what we return.
float MinMaxRS = MinMax*RS_v; // = {Min_s*RS, Max_s*RS}
float Div = MinMaxRS*rec_v; // = {Min_s*RS/A, Max_s*RS/B}
float Clear = v*Div; // = {Min_s*RS, Max_s*RS}
float res = MinMaxRS - Clear; // = {0, 0}
res = res*rec_v; // = {0, 0}
res = res + Div; // = {Min_s*RS/A, Max_s*RS/B}
return res;
}В дополнении вы можете найти эту же версию кода C с аннотациями из assembly.
По сути ICX вычислил обратное число, что похоже на деление, и затем умножил на него. Это хорошее решение, поскольку rcpps в целом значительно быстрее divss и divps.
Но компилятор делает что‑то странное. На 21 строке у нас уже готов результат! Почему же мы не возвращаем его и продолжаем делать остальную несусветицу, чтобы получить тот же результат на строке 25? Вы же помните, что мы работаем с числами с плавающей запятой. Так что 0 на строке 24 не совсем нули. Если коротко, то ICX делает все эти операции, чтобы понизить отклонения в вычислениях.
Еще интересно то, что это ICX может это делать только потому, что в отличие от GCC и Clang, стандартная точность чисел с плавающей запятой не точная. Другим словом, сгенерированный код не обязательно даст тот же результат, что и оригинальный код. Что, кстати, справедливо и для ручной оптимизации — она не учитывает семантику чисел с плавающей запятой.
Что касается GCC и Clang, мы должны явно сказать им, что они могут использовать «быстрые вычисления», то есть оптимизации, которые могут дать неточный результат. Это делается с помощью флага -ffast-math. GCC это особо не помогло, а вот Clang смог сгенерировать почти такой же код, как и ICX!
Мораль сей басни в том, что компиляторы могут делать достаточно хитрые оптимизации, но им сперва нужно сказать, что важно, а что нет.
Устранение общих подвыражений
Вернемся к примеру ProjectSphere. Изначально код имел следующий вид:
Float2 ProjectSphere(float x, float z, float r, float t, float ResultScale) {
float Min = (t * x - r * z) / (t * z + r * x);
float Max = (t * x + r * z) / (t * z - r * x);
Float2 Res = {Min * ResultScale, Max * ResultScale};
return Res;
}Я преобразовал его в следующий:
Float2 ProjectSphere(float x, float z, float r, float t, float scale) {
float tz = t*z;
float rx = r*x;
float tx = t*x;
float rz = r*z;
float A = (tz + rx);
float B = (tz - rx);
float Min = (tx - rz) / A;
float Max = (tx + rz) / B;
Float2 Res = {Min*scale, Max*scale};
return Res;
}В моей версии используется оптимизация, которая называется «common subexpression elimination» (CSE) и из названия в целом понятно, что она делает. Мы по сути берем выражения, которые появляются несколько раз, как, к примеру, t*z в изначальном коде, и помещаем их в переменные. В теории это полезно, поскольку позволяет избежать повторных вычислений. На практике есть нюансы — CSE в целом повышает нагрузку на регистры, что детально объясняется в дополнении.
Общий консенсус сводится к тому, что нам не нужно выполнять эту оптимизацию вручную, поскольку компилятор сделает это за нас. Более того, должно быть не важно, применяем мы ее или нет! Компилятор должен видеть сквозь переменные. Другим словом, для компилятора такие переменные как tz должны быть как макросы, то есть tz и t*z должны быть равнозначны, так что не важно, как мы пишем код. Но правда ли это?
Используя ‑O1 в Clang обе версии дают нам по сути одинаковый код (одни и те же инструкции, просто в разном порядке), что также справедливо и для GCC с -O1. В случае -O2 и -O3 в GCC ситуация немного меняется. В обоих вариантах получается идентичный код, за исключением того, что в моей версии добавляется еще одна инструкция movdqa перед ret, что делает еще чуть медленнее. В Clang разница еще страннее при использовании ‑O2. Здесь моя версия чуть лучше, поскольку использует две subss, в то время как изначальный код дает две shufps.
Мораль в том, что выражение «то, как ты пишешь арифметику не имеет значения, компилятор разберется» попросту неправда. Что хуже, нет какого‑либо правила, которое помогло бы определить, какую версию когда использовать. В то же время, беспокоиться об этом стоит только когда необходимо выжать последнюю каплю производительности. Да, компилятор сделает то же самое в 90% случаев вне зависимости от того, как написан код.
Неоптимизированные сборки
Один из способов понять, что делает компилятор при включении оптимизаций — посмотреть, что не происходит, если их не включить. Опять обратимся к нашей упрощенной times2, немного измененной для использования одной локальной переменной:
int times2(int n) {
int x = n*2;
return x;
}Вот что Clang генерирует без оптимизаций (godbolt):
times2:
push rbp
mov rbp, rsp
mov dword ptr [rbp - 4], edi
mov eax, dword ptr [rbp - 4]
shl eax
mov dword ptr [rbp - 8], eax
mov eax, dword ptr [rbp - 8]
pop rbp
retНе особо разбираясь в коде, должно быть относительно понятно, что rbp бесполезна. Мы сохраняем ее значение, поместив на стек. Затем копируем значение rsp в rbp и, выполнив все операции с использованием rbp, убираем значение rbp со стека. Тем самым, чтобы упростить себе жизнь, я уберу rpb, используя -fomit-frame-pointer (godbolt). Если вы не знаете, что такое указатель фрейма — не волнуйтесь, это не важно в контексте статьи. Ну или можете почитать в интернете. Вот так выглядит код, используя только rsp:
times2:
; Save the argument `n`, whose value is in `edi`, to the stack.
; The next available position is `rsp - 4`.
mov dword ptr [rsp - 4], edi
; Load `n` into a register to do operations with it
mov eax, dword ptr [rsp - 4]
; n << 1
shl eax
; `x` is also assigned a stack position. The next available is
; `rsp - 8`. Save the result of the computation above there.
mov dword ptr [rsp - 8], eax
; Load `x` into `eax` because that's what we return.
mov eax, dword ptr [rsp - 8]
retДетали объясняются в assembly, но общая идея следующая: компилятор придерживается простой, наивной и повторяющейся методологии в неоптимизированных сборках. Это происходит примерно так. Сначала, каждой переменной присваивается позиция на стеке (то есть, каждая переменная имеет одну позицию на стеке и эта позиция соответствует только этой переменной). Это включает все локальные переменные, а также аргументы функции. Так что в начале функции мы просто копируем все аргументы на стек. Затем, когда мы хотим использовать значение переменной, мы помещаем его со стека в регистр, частично из‑за того, что мы не можем выполнять вычисления используя позиции на стеке напрямую — большая часть инструкций работает с регистрами. И, конечно же, каждое присвоение значения переменной помещает значение в соответствующей переменной позиции на стеке.
Это все может казаться глупым, поскольку у нас явно достаточно регистров, чтобы вообще не использовать стек в данном случае. И это правда. Но в случае неоптимизированных сборок стоит считать, что компилятору вообще не нужно думать. Описанный выше метод дает рабочий код без раздумий о количестве переменных, в то время как более хитрый метод с использованием только регистров потребовал бы как минимум задуматься о чем‑то вроде «Я буду использовать регистры, пока есть такая возможность, ну а если они закончатся, начну использовать стек». Но эти размышления сами по себе — оптимизация: выделение регистров (то есть то, как выделяются регистры для хранения значений). И если это необходимо, стоит включить оптимизации. Существуют разные уровни оптимизации выделения регистров в отношении помещения данных в регистры и в случае некоторых компиляторов более низкие уровни используют более простые методы.
Также, описанный выше метод упрощает работу дебагера. Так как каждая переменная соотносится с позицией на стеке и эта позиция не используется для чего‑либо еще, если на каком‑то этапе выполнения функции нужно будет просмотреть значение переменной, достаточно обратиться к ее позиции на стеке. В случае оптимизированных сборок значение переменной не привязано к конкретной позиции или регистру — оно перемещается. Так что компилятору необходимо сообщать об этих изменениях, а дебагеру в свою очередь — следить за ними. И, конечно же, для более простых функций как у нас, компилятор мог бы выделить по регистру для каждой из переменных, чтобы каждая переменная ассоциировалась только с одним регистром. Но используемые нами инструменты не оптимизированы для подобных случаев. Вместо этого, считается, что есть либо абсолютно прямолинейные дебаг/неоптимизированные сборки, либо оптимизированные — «будь что будет».
И наконец, стоит отметить что Clang использовал сдвиг влево для умножения даже в неоптимизированной сборке. Похожим образом, GCC использует похожую на нашу версию с заменой умножения на сложение (godbolt).
Инлайнинг
В данном случае я без зазрения совести оставлю ссылку на 6-минутный фрагмент моего выступления на митапе по компиляторам пару лет назад. Это одно из тех выступлений, которые, как мне кажется, вполне сносны, так что вот. За первые 6 минут я объясняю преимущества и недостатки инлайнинга, а также некоторые особенности (к примеру, когда инлайнинг возможен). Затем я погружаюсь в то, как это происходит внутри компилятора.
Что касается не видео‑контента, хотелось бы упомянуть реализацию инлайнинга в LLVM от Chris Lattner, созданную 20 лет назад.
Понижение силы операций
Предположим, у нас есть следующая функция:
void init_scaled(int *array, int n, int scale) {
for (int i = 0; i < n; i++) {
array[i] = i * scale;
}
}Один из способов избежать умножения в цикле — написать код следующим образом:
void init_scaled(int *array, int n, int scale) {
int tmp = 0;
for (int i = 0; i < n; i++) {
array[i] = tmp;
tmp += scale;
}
}Тут мы заменили умножение сложением, что в целом хорошо, поскольку сложение целых чисел быстрее умножения. Подобные оптимизации относятся к категории оптимизаций с понижением силы операций, в которых мы заменяем часть кода на равнозначный, но при этом менее “сильный”, то есть использующий более дешевые инструкции. Clang (и большая часть компиляторов) применит ее даже при -O1 (godbolt).
Более хитрая версия понижения силы это loop-invariant code motion. Вот пример, похожий на прошлый:
void scale_array(float *array, int n, float multiplier) {
const float pi = 3.14159;
for (int i = 0; i < n; i++) {
float scale = pi * multiplier;
array[i] = array[i] * scale;
}
}Вы можете заметить, что значение scale одинаково для всех итераций цикла. Так что мы можем вынести его из цикла, чтобы умножение происходило всего один раз:
void scale_array(float *array, int n, float multiplier) {
const float pi = 3.14159;
float scale = pi * multiplier;
for (int i = 0; i < n; i++) {
array[i] = array[i] * scale;
}
}Clang (и большинство компиляторов) выполнят ее (godbolt) даже при -O1. Assembly с аннотациями:
.LCPI0_0:
; This is pi
.long 0x40490fd0
scale_array:
...
; scale = multiplier * pi
mulss xmm0, dword ptr [rip + .LCPI0_0]
...
.LBB0_2:
; float tmp = array[i];
movss xmm1, dword ptr [rdi + 4*rcx]
; float tmp2 = tmp * scale
mulss xmm1, xmm0
; array[i] = tmp2;
movss dword ptr [rdi + 4*rcx], xmm1
...Оптимизации во время компиляции
Это может кого‑то удивить, но у большей части компиляторов есть несколько подсистем, которые выполняют код во время компиляции. Наиболее очевидный пример — все, что используется для вычисления constexpr.
Но есть некоторые неочевидные подсистемы. В качестве примера возьмем обычную сиракузскую последовательность (godbolt):
static int collatz(int n) {
int its = 0;
while (n != 1) {
its++;
if (n % 2 == 0) {
n /= 2;
} else {
n = 3 * n + 1;
}
}
return its;
}
int main(void) {
return collatz(6);
}Взглянем на assembly:
main:
mov eax, 8
retДля начала, я намеренно пометил функцию collatz как static, чтобы компилятор оставил только функцию main. Подробнее об этом поговорим в разделе об удалении мертвого кода.
Теперь компилятор по сути генерирует следующее:
int main(void) {
return 8;
}Другими словами, он выполнил функцию во время компиляции и заменил вызов функции возвращаемым значением collatz. Заметьте, что, как я упоминал в прошлой статье, компилятор может превращать циклы в вычисления констант, если цикл может быть сведен к этому. Но сиракузская последовательность известна тем, что к таковым не относится. Так что компилятору пришлось выполнить цикл на этапе компиляции.
Компилятор, в целом, не может знать, закончит ли цикл выполняться (особенно в случае сиракузской последовательности). Следует закономерный вопрос: может ли компилятор зависнуть в бесконечном цикле? В целом нет, поскольку у него есть лимит на количество итераций. К примеру, когда мы передадим 27 в качестве аргумента, что займет 111 итераций, компилятор сгенерирует следующее (godbolt):
main:
mov ecx, 27
xor eax, eax
.LBB0_1:
inc eax
mov edx, ecx
sar edx
test cl, 1
lea ecx, [rcx + 2*rcx + 1]
cmove ecx, edx
cmp ecx, 1
jne .LBB0_1
retИтак, цикл точно на месте (обратите внимание на jne к .LBB0_1). На момент написания статьи максимальное количество итераций для используемой тут подсистемы составляет 100. Мы можем увеличить его, передав команде аргумент -mllvm --scalar-evolution-max-iterations=111 (godbolt):
main:
mov eax, 111
retПочему аргумент называется именно так — отдельная история. Вам также может быть интересна моя статья, посвященная скалярной эволюции.
Заметьте, что компиляция теперь достаточно медленная (на самом деле, значительно медленная, особенно для всего лишь 111 итераций), что дает нам понять, что системы, работающие во время компиляции достаточно медленные. Но они и не создавались с расчетом на производительность. Несмотря на это, когда я в последний раз смотрел на язык Jai, он генерировал байткод для вычислений во время компиляции, что в теории должно работать быстрее.
И наконец, не все компиляторы будут пытаться вычислить циклы во время компиляции. К примеру, ни GCC, ни ICX не будут делать этого для примера с сиракузской последовательностью.
Удаление мертвого кода
«Мертвый код» — по сути бесполезный, неиспользуемый, повторяющийся и в целом ненужный код. Наверное, основная работа DCE — удаление неиспользуемого кода, добавленного при помощи #include. К примеру, добавив #include к примеру times2 (godbolt), можно заметить, что код не меняется, так как компилятор «выкинул» все. Ну, на самом деле причины две, основная — большая часть кода в файлах .h не исполняема. К примеру, struct не может быть выполнен. Он нужен для того, чтобы объяснить компилятору, как генерировать код, использующий структуры. Но в C++ файлы .h также могут содержать функции — к примеру, в классах. Они также будут убраны, если их не использовать.
Но есть и менее очевидный случай. Выше мы разбирали функцию collatz, которая была помечена как static. Что значит, что функция относится к этому модулю и не может быть использована в других модулях. В этом модуле она вызывается один раз, но этот вызов был заинлайнен. Так что функция теперь не нужна, из‑за чего компилятор убрал ее.
Большинство, когда слышит про удаление мертвого кода, задается вопросом: «Но ведь весь код, который я пишу, что‑то да делает, так как же компилятор находит мертвый код?» Выше мы наблюдали один из примеров. И в целом, большая часть мертвого кода генерируется из‑за оптимизаций компилятора.
Удаление мертвого кода может удивлять. Для примера вернемся к функции collatz. Но в этот раз вместо возвращения количества итераций мы вернем n (godbolt):
static int collatz(int n) {
int its = 0;
while (n != 1) {
its++;
if (n % 2 == 0) {
n /= 2;
} else {
n = 3 * n + 1;
}
}
////////////////////////////////////////
// THIS IS WHERE THE CHANGE HAPPENED ///
////////////////////////////////////////
return n;
}
int main(void) {
return collatz(27);
}Давайте взглянем на assembly:
main:
mov eax, 1
retКомпилятор по сути превратил код в следующий:
int main(void) {
return 1;
}Но как? Заметьте, что в данном случае мы не передавали аргумент, увеличивающий лимит на количество итераций. Так как же компилятор убрал цикл? Дело в условии цикла: while (n != 1). Благодаря ему компилятор знает, что когда цикл завершится, n должно иметь значение 1, иначе он никогда не завершится. Соответственно, компилятор возвращает 1.
Но откуда компилятор знает, что он завершится? Из стандарта C… Если кратко, бесконечные циклы без сторонних эффектов (к примеру, вывод или запись в volatile указатели) - undefined behavior. Компилятор всегда считает, что UB не случается и, соответственно, считает, что цикл завершится.
Это один из многих примеров, почему не стоит думать о C как о высокоуровневом ассемблере (т.е. способе легко писать assembly). Undefined behavior - на самом верху списка. Бывают случаи, когда компилятор сделает с кодом то, чего вы совсем не ожидали.