Это цикл статей об оптимизирующих компиляторах вообще и 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 -- это вычурный частный случай этой оптимизации, выполненный на цикле.
