Это цикл статей об оптимизирующих компиляторах вообще и LLVM в частности. Смотри все статьи данного цикла:
Проверки диапазонов
В этой статье мы поговорим о том, чего нам стоят безопасные доступы к элементам массива, и как современные компиляторы пытаются сделать код снова быстрым.
Проверки диапазонов в массивах
Предположим, что у нас есть код:
int array[LEN];
...
int x = array[idx];
Если 0 <= idx < LEN
, то этот код прочитает соответствующий элемент массива. Однако что должно происходить, если idx < 0
или idx >= LEN
? Тут каждый язык даёт свой ответ. В языках типа С или С++ это -- неопределённое поведение. При исполнении такого кода нельзя ожидать, что случится что-то конкретное. В зависимости от того, что сделает компилятор, вы можете получить:
Краш
Зависание
Успешное прочтение какого-нибудь случайного значения
Всё вышеперечисленное в зависимости от каких-то малопонятных факторов
Любые другие неожиданные эффекты
Способов надёжно отловить эту ситуацию после того, как она случилась, не существует. Поэтому, чтобы убедиться, что такая ситуация будет корректно обработана (хотя бы в случае её возникновения было сообщение об ошибке), перед непосредственно чтением из памяти вставляется проверка диапазона (range check). Выглядит она примерно так:
int array[LEN];
...
if (idx < 0 || idx >= LEN) {
// Код обработки ошибки
}
int x = array[idx];
При обработке ошибки обычно делается что-то, что не позволяет исполниться некорректному чтению, например, бросается исключение. Некоторые языки программирования, такие как Java, вставляют такие проверки неявно при каждом доступе к массиву. Поэтому в Java аналогичный код без всяких рукописных проверок выбросит ArrayIndexOutOfBoundsException.
Теперь мы надёжно защищены от неопределённого поведения. Но чего нам это стоит? Давайте разберёмся.
Безопасно... И медленно
Давайте посмотрим, как выглядит ассемблерный код (на х86) доступа к массиву с и без проверки диапазона (на свежем clang).
#include <cstddef>
int read_without_check(int *array, int idx, unsigned LEN) {
__builtin_assume(LEN >= 0);
return array[idx];
}
int read_with_check(int *array, int idx, int LEN) {
__builtin_assume(LEN >= 0);
if (idx < 0 || idx >= LEN)
throw "out of bounds";
return array[idx];
}
read_without_check(int*, int, unsigned int): # @read_without_check(int*, int, unsigned int)
movslq %esi, %rax
movl (%rdi,%rax,4), %eax
retq
read_with_check(int*, int, int): # @read_with_check(int*, int, int)
cmpl %edx, %esi
jae .LBB1_2
movl %esi, %eax
movl (%rdi,%rax,4), %eax
retq
.LBB1_2:
pushq %rax
movl $8, %edi
callq __cxa_allocate_exception@PLT
leaq .L.str(%rip), %rcx
movq %rcx, (%rax)
movq typeinfo for char const*@GOTPCREL(%rip), %rsi
movq %rax, %rdi
xorl %edx, %edx
callq __cxa_throw@PLT
.L.str:
.asciz "out of bounds"
Фактически добавилось две инструкции: cmpl
и jae
. Стоит объяснить, почему jae
: если мы знаем, что LEN >= 0
, то две проверки
idx < 0 || idx >= LEN
можно заменить на
(unsigned) idx >= (unsigned) LEN
Если idx
был отрицательный, то при преобразовании в беззнаковый тип это будет огромное положительное число, заведомо больше LEN
. На практике компиляторы обычно знают, что размер массива -- неотрицательное число.
Итак, имеем три инструкции вместо одной. Честно говоря, само по себе это большой проблемой не является. Современные процессоры имеют предсказатель переходов, который прекрасно справляется с проверкой, которая на практике всегда true
. К тому же, обе новые инструкции достаточно дешёвые. Ну то есть да, дополнительная стоимость есть, но не такая уж и великая. Настоящие проблемы с производительностью начинаются, когда такой код оказывается в цикле.
#include <cstddef>
int read_loop_without_check(int *array, int idx, unsigned LEN) {
__builtin_assume(LEN >= 0);
int sum = 0;
for (int idx = 0; idx < 8; idx++) {
sum += array[idx];
}
return sum;
}
int read_loop_with_check(int *array, int idx, int LEN) {
__builtin_assume(LEN >= 0);
int sum = 0;
for (int idx = 0; idx < 8; idx++) {
if (idx < 0 || idx >= LEN)
throw "out of bounds";
sum += array[idx];
}
return sum;
}
Здесь мы читаем восемь элементов массива за раз. В первом случае можно сразу сделать это одной векторной инструкцией:
define dso_local noundef i32 @read_loop_without_check(int*, int, unsigned int)(ptr nocapture noundef readonly %0, i32 noundef %1, i32 noundef %2) local_unnamed_addr #0 {
%4 = load <8 x i32>, ptr %0, align 4
%5 = tail call i32 @llvm.vector.reduce.add.v8i32(<8 x i32> %4)
ret i32 %5
}
Если реальная длина массива окажется меньше 8, то и исходный код, и новый имели неопределённое поведение, а значит, такое преобразование валидно.
Однако во втором случае при длине массива меньше 8 изначально поведение было определённое: вылетало исключение. Поэтому зачитать 8 элементов одной векторной инструкции с риском вылезти за границы аллоцированной памяти в этом случае нельзя. Собственно, вариантов действий тут всего два:
Честно исполнить код как есть, выполнив проверку до 8 раз
Каким-то образом соптимизировать проверку
Понятно, что во всех случаях, когда это возможно, следует выбирать второй вариант. Давайте рассмотрим, как именно могут оптимизироваться проверки диапазонов.
Удаление на основе доминирующих проверок
В реальности, когда речь идёт не о демонстрационных примерах, проверки диапазонов не существуют отдельно, а являются частью большой и сложной программы. Часто бывает так, что какие-то из вышестоящих проверок позволяют избавиться от нашей. Давайте приведём простейший пример:
for (int idx = 0; idx < 10000; idx++) {
sum += read_with_check(array, idx + 1, LEN);
sum += read_with_check(array, idx, LEN);
}
Здесь мы имеем две проверки диапазона против idx + 1
и потом против idx
, причём первая исполняется раньше второй (строго говоря -- доминирует над второй).
Если мы уже дошли до исполнения второй проверки, то это значит, что первая благополучно прошла. Поэтому нам уже известно, что 0 <= idx + 1 < LEN
. Также, из условий цикла, мы знаем, что 0 <= idx < 10000
. И теперь нам нужно избавиться от проверки 0 <= idx < LEN
. Давайте немного преобразуем известные факты:
0 <= idx + 1 < LEN && 0 <= idx < 10000 // Отнимем 1 от первого неравенства
-1 <= idx < LEN - 1 && 0 <= idx < 10000 // объединим оба неравенства
max(-1, 0) <= idx < min(LEN - 1, 10000) // сократим
0 <= idx < min(LEN - 1, 10000)
Теперь нам осталось доказать импликацию искомого утверждения из известного. 0 <= idx
у нас уже есть, осталось доказать, что
idx < min(LEN - 1, 10000) <= LEN - 1 && LEN >= 0 // LEN - 1 вычисляется без переполнения
idx < min(LEN - 1, 10000) <= LEN - 1 < LEN
Таким образом, имея некоторые известные факты на момент исполнения проверки, мы доказали, что условие этой проверки с учётом этих фактов всегда истинно. Таким образом, исходный пример
for (int idx = 0; idx < 10000; idx++) {
sum += read_with_check(array, idx + 1, LEN);
sum += read_with_check(array, idx, LEN);
}
можно упростить до
for (int idx = 0; idx < 10000; idx++) {
sum += read_with_check(array, idx + 1, LEN);
sum += read_without_check(array, idx, LEN);
}
Теперь на два чтения из массива приходится уже не две, а одна проверка. Позднее мы рассмотрим, как избавиться и от неё, а пока опишем общую схему, позволяющую удалять проверки только на основании доминирующих условий:
Берём очередную проверку, которую требуется удалить
Находим все проверки, которые над ней доминируют
Пытаемся доказать, что из истинности доминирующего утверждения следует истинность и того утверждения, которое хотим доказать, и если это так -- удаляем проверку
В LLVM этим занимаются такие оптимизационные пассы, как Constraint Elimination (для любых проверок) и Ind Var Simplify (для проверок против индукционных переменных).
Замена на инвариантную проверку
Иногда проверка, от которой мы хотим избавиться, теоретически может упасть, и нет никаких вышестоящих фактов, которые бы об этого защитили. Но упасть она может не когда попало, а, например, только на первой итерации цикла либо никогда. Приведём простейший пример:
for (int idx = start; idx >= 0; idx--) {
<много кода>
sum += read_with_check(array, idx, LEN);
<много кода>
}
Здесь мы можем упасть прямо на первой итерации, если start >= LEN
. Но интересно то, что если на первой итерации оказалось, что 0 <= idx = start < LEN
, то и на любой другой итерации 0 <= idx < start < LEN
. Чтобы понять логику оптимизации, давайте мысленно произведём полную размотку цикла:
sum += read_with_check(array, start, LEN);
sum += read_with_check(array, start - 1, LEN);
sum += read_with_check(array, start - 2, LEN);
...
sum += read_with_check(array, 1, LEN);
sum += read_with_check(array, 0, LEN);
Теперь видно, что ситуация похожа на ту, что мы рассматривали в предыдущем примере: для каждой проверки (кроме первой) мы проверяем диапазон сначала для idx + 1
, а потом для idx
. Значит, последнюю проверку диапазона можно удалить на основании предпоследней, предпоследнюю -- на основании той, что перед ней, и так далее. В сухом остатке удалить можно все проверки, кроме самой первой, которая действительно может упасть.
Люди, знакомые с понятием математической индукции, наверняка заметили аналогию: у нас есть индукционный переход, а база индукции нуждается в проверке. Поскольку база не зависит от номера итерации, эта проверка -- инвариантная.
Существуют разные способы реализовать эту оптимизацию технически. Первый называется пилинг (loop peeling), и она заключается в том, чтобы выполнить первую итерацию цикла отдельно от остальных:
for (int idx = start; idx >= start - 1; idx--) {
<много кода>
sum += read_with_check(array, start, LEN);
<много кода>
}
for (int idx = start - 1; idx >= 0; idx--) {
<много кода>
sum += read_without_check(array, idx, LEN);
<много кода>
}
В общем случае это может потребовать модификации CFG (если цикл большой, сложный и содержит много ветвлений), и не все оптимизационные пассы могут себе это позволить. Часто проверку диапазона против счётчика заменяют на проверку против инварианта. Чтобы продемонстрировать, нужно заинлайнить проверку:
for (int idx = start; idx >= 0; idx--) {
<много кода>
if (idx < 0 || idx >= LEN)
throw "out of bounds";
sum += array[idx];
<много кода>
}
превращается в
for (int idx = start; idx >= 0; idx--) {
<много кода>
if (start < 0 || start >= LEN)
throw "out of bounds";
sum += array[idx];
<много кода>
}
В LLVM заменой таких проверок на инвариантные занимается Ind Var Simplify, пилинг выполняет Loop Unroll.
Как избавиться от инвариантной проверки в цикле, мы рассматривали в предыдущей статье.
Разбиение диапазона индукционной переменной
В примерах выше мы уже рассматривали проверки, совершаемые против индукционной переменной. Индукционная переменная -- это переменная, изменяющаяся в цикле по формуле
iv(N) = start + step * N
здесь start
и step
-- цикловые инварианты, а N
-- номер итерации цикла. Типичный пример индукционной переменной -- цикловой счётчик, индукционными переменными также являются их производные (например, в цикле по i
переменная 2 * i + 3
также является индукционной, потому что представима в виде 3 + 2 * N
.
Давайте рассмотрим ситуацию, когда проверка диапазона выполняется против индукционной переменной. Например:
for (int idx = start; idx < end; idx += step) {
<много кода>
sum += read_with_check(array, idx, LEN);
<много кода>
}
Давайте для простоты считать step > 0
, а также считать доказанным, что idx
не переполняется в ходе этих вычислений (в противном случае логика усложнится, но принципиально не изменится). Идея оптимизации состоит в следующем: давайте проанализируем проверку диапазона и поймём, при каких idx
она не упадёт. В нашем случае проверка не упадёт, если 0 <= idx < LEN
. Мы ничего не знаем о связи start
и end
с этими величинами, но тем не менее можем посчитать пересечение безопасного диапазона и пространства итерации индукционной переменной:
[0, LEN) ∩ [start, end) = [max(0, start), min(LEN, end))
Таким образом, итерации цикла, при котором idx
лежит в этом безопасном диапазоне, можно делать без проверок. В общем случае проверки, возможно, придётся делать до и после этого диапазона. Смысл оптимизации в том, чтобы разбить пространства итерации на 3 непересекающихся множества (некоторые из них вполне могут оказаться пустыми):
[start, max(0, start))
[max(0, start), min(LEN, end)) // здесь проверку можно не делать
[min(LEN, end), end)
С точки зрения модификации кода, мы получим
int idx = start;
for (; idx < max(0, start); idx += step) {
<много кода>
sum += read_with_check(array, idx, LEN);
<много кода>
}
for (; idx < min(LEN, end); idx += step) {
<много кода>
sum += read_without_check(array, idx, LEN);
<много кода>
}
for (; idx < end; idx += step) {
<много кода>
sum += read_with_check(array, idx, LEN);
<много кода>
}
В худшем случае такое преобразование приводит к раздуванию цикла в 3 раза, что, в целом, нежелательно, особенно если мы экономим размер кода и время компиляции. На практике, компиляторы часто что-нибудь знают про start
и end
(часто start = 0
, а end
связан с LEN
), что позволяет им сразу же удалить какие-то из этих циклов. В идеале должен остаться только второй.
В LLVM этим занимается пасс Inductive Range Check Elimination.
Удаление с помощью спекулятивной проверки
Данный класс оптимизаций применим тогда, когда нам известна семантика кода, который выполняется в случае ошибки. Например, если мы имеем дело с Java (так, например, поступает основанный на LLVM компилятор Falcon в Azul Prime VM), обработка ошибки заключается в том, что мы уходим из скомпилированного кода в интерпретатор, или совершаем так называемую деоптимизацию.
for (int idx = start; idx < end; idx += step) {
<много кода>
if (idx < 0 || idx >= LEN)
call deopt(); // мы уйдём в интерпретатор и будем там заново исполнять эту операцию
sum += array[idx];
<много кода>
}
Что интересно, уход в интерпретатор -- это корректное действие в любой точке программы. Можно ведь вообще не исполнять JIT-компилированный код, а вместо этого всё считать в интерпретаторе. Это медленно, но корректно.
Отсюда проистекает интересная идея для оптимизации: давайте заранее проверим достаточные инвариантные условия, при которых проверка точно не упадёт. Если они нарушаются, то мы сразу уйдём в интерпретатор и будем выполнять цикл в нём. Заметьте: достаточные условия не обязательно также являются и необходимыми, а поэтому может так получиться, что на самом деле исключений кидать не придётся. В этом заключается спекулятивность данной оптимизации: мы предполагаем (спекулируем), что наши достаточные условия сами по себе окажутся хороши и очень похожи на необходимые, а если нет, то мы готовы заплатить за эту ошибку исполнением цикла в интерпретаторе.
В нашем примере несложно выписать достаточные условия, при которых проверка не упадёт:
0 <= start < LEN && 0 <= end <= LEN
По сути, смысл здесь очень простой: если проверка против индукционной переменной не падает ни на первой, ни на последней итерации, и переменная в ходе итерации не переполняется, то ни на какой другой итерации эта проверка также не может упасть.
Важно понять, что это условие избыточное. Например, если end = 103, LEN = 101
, а step = 4
, то условие не будет выполнено, хотя в реальности выхода за границу массива не произойдёт, потому что idx
всегда будет делиться на 4, и последним индексом, по которому произойдёт реальное чтение, будет 100, а не 101.
И тем не менее, мы считаем, что на практике оно достаточно хорошо, чтобы попробовать (к тому же, можно сделать вычисление самих условий чуть умнее в случае шага не равного 1). Поэтому оптимизация будет выглядеть примерно так:
for (int idx = start; idx < end; idx += step) {
<много кода>
if (start < 0 || start >= LEN || end < 0 || end > LEN)
call deopt(); // мы уйдём в интерпретатор и будем там заново исполнять эту операцию
sum += array[idx];
<много кода>
}
Мы снова получили инвариантную проверку, не зависящую от индукционной переменной. Как с ними работать -- описано в предыдущей статье.
В LLVM такими вещами занимается пасс Loop Predication.
Заключение
Уже по тому, сколько существует разных способов борьбы с проверками диапазонов (наверняка есть и такие, которые я в этой статье не описал), ясно, что проблема достаточно серьёзная. Неудалённые проверки в цикле -- помеха не только для векторизации, но и для множества других оптимизаций (например, в статье про UB я объяснял, почему нельзя переносить некоторые инструкции сквозь проверки). Интересующимся, помимо прочего, рекомендую прочитать про оптимизацию Guard Widening в LLVM. Она не то чтобы целится именно на проверки диапазонов, но даёт интересный взгляд на спекулятивные оптимизации. В некотором смысле, Loop Predication -- это вычурный частный случай этой оптимизации, выполненный на цикле.