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

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

1. SSA форма

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

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

4. Циклы

5. CSE

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

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

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

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

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

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