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

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

1. SSA форма

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

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

4. Циклы

5. CSE

6. Цикловые инварианты

7. Проверки диапазонов

8. Размотка циклов

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

Проверки диапазонов в массивах

Предположим, что у нас есть код:

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