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

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

1. SSA форма

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

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

Вообще-то, третья статья данного цикла должна была рассказывать о конкретных оптимизациях. Но пока я прикидывал её план, стало ясно, что без освещения некоторых аспектов неопределённого поведения многое из дальнейших описаний будет непонятно. Поэтому сделаем ещё один осторожный шаг, прежде, чем окунаться в омут с головой.

Наверное, многие слышали, что неопределённое поведение (undefined behavior, UB) — постоянный источник разнообразных багов, иногда очень забавных, иногда довольно жутких. Тема также неоднократно освещалась и на Хабре, навскидку раз, два, три (и даже целый тег есть). Однако чаще всего статьи по данной теме посвящены тому, как можно отстрелить себе ногу, голову или случайно сжечь свой жёсткий диск, исполнив какой-нибудь опасный код. Я же намерен сделать акцент на том, зачем авторы языков программирования надобавляли всей этой красоты, и как оптимизатор может её эксплуатировать, чтобы делать из неё перфоманс. Всё будет проиллюстрировано наглядными примерами из LLVM и присыпано байками из собственного опыта, так что наливайте себе чай, располагайтесь поудобнее, и погнали.

Коротко о предмете

Если вы совсем не знакомы с тем, что такое undefined behavior, то есть много источников, которые можно прочитать для ознакомления. Начать можно со статьи в Википедии, а дальше гуглить по ключевым словам и наслаждаться десятками историй на тему "я не понимаю, какого чёрта моя программа работает не так, как мне хочется" или "1001 способ отстрелить себе ногу для чайников". Некоторые довольно забавны, рекомендую.

Для нас имеет значение то, что в языках программирования (и особо этим славен С++ и ему подобные) в стандарте встречаются фразы типа

When signed integer arithmetic operation overflows (the result does not fit in the result type), the behavior is undefined

В этом случае может произойти абсолютно всё что угодно: может быть, вам повезёт, и при переполнении получится результат по модулю 2ⁿ, может быть повезёт чуть меньше, и получится какой-нибудь 0 или SINT_MAX, а может быть, ваша программа удалит корневой каталог, а жёсткий диск сгорит синим пламенем просто потому, что вы сложили два числа.

Вот краткий список ситуаций, когда мы можем столкнуться с неопределённым поведением:

• Переполнения знаковой арифметики

• Деление (или взятие остатка) на 0

• Разыменование (т.е. чтение или запись) nullptr или указателя на невыделенную память (например, за границы массива)

• Использование неинициализированных переменных

• Бесконечный цикл без сайд-эффектов

• Гонка при записи неволатильного поля разными потоками

• и т.п.

Благими намерениями

В нашей среде существует локальный мем "demon optimizer" — это такой гипотетический оптимизирующий компилятор, который будет специально находить любой формальный повод, по которому может случиться UB, и в этой ситуации всегда стараться наносить наибольший возможный урон (например, вставлять "rm -rf /" везде, когда переполняется хоть какая-то знаковая арифметика). Понятно, что в реальности компилятор не ставит себе задачу при малейшей возможности нагадить программисту. В реальности всё хуже: он может нагадить ему, искренне стараясь делать добро.

Не так давно в интернетах дивились примерно следующей ситуации: компилятор clang умудрился вызвать функцию never_called

#include <iostream>

int main() {
    int cnt = 0;
    while (cnt++ != -1) {}
    return 0;
}

void never_called() {
    std::cout << "You are screwed" << std::endl;
}

Вместо принта можно вставить какой-нибудь "rm -rf /", и этот код также исполнится. Почему так происходит, нетрудно понять, если заглянуть в godbolt:

main:                                   # @main
never_called():                      # @never_called()
        push    rbx
        mov     rbx, qword ptr [rip + std::cout@GOTPCREL]
        lea     rsi, [rip + .L.str]
        mov     edx, 15
        mov     rdi, rbx
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)@PLT
        mov     rax, qword ptr [rbx]
        mov     rax, qword ptr [rax - 24]
        mov     rbx, qword ptr [rbx + rax + 240]
        test    rbx, rbx
        je      .LBB1_5
        cmp     byte ptr [rbx + 56], 0
        je      .LBB1_3
        movzx   eax, byte ptr [rbx + 67]
        jmp     .LBB1_4
.LBB1_3:
        mov     rdi, rbx
        call    std::ctype<char>::_M_widen_init() const@PLT
        mov     rax, qword ptr [rbx]
        mov     rdi, rbx
        mov     esi, 10
        call    qword ptr [rax + 48]
.LBB1_4:
        movsx   esi, al
        mov     rdi, qword ptr [rip + std::cout@GOTPCREL]
        call    std::basic_ostream<char, std::char_traits<char> >::put(char)@PLT
        mov     rdi, rax
        pop     rbx
        jmp     std::basic_ostream<char, std::char_traits<char> >::flush()@PLT               # TAILCALL
.LBB1_5:
        call    std::__throw_bad_cast()@PLT
.L.str:
        .asciz  "You are screwed"

Как видим, прямо за меткой main идёт метка начала функции never_called, и если передать ей управление, то процессор пойдёт исполнять его дальше сплошняком. Давайте примерно разберём схему того, как это случилось.

1. Согласно стандарту С++, знаковое переполнение — это UB. Поэтому можно считать, что cnt, которая изначально было равно нулю и шло вверх, всегда будет неотрицательным. Отрицательным оно может стать только при переполнении, но поскольку это UB, компилятору на это наплевать.

2. Сравнение "cnt != -1" можно превратить в "true", поскольку cnt — неотрицательное, а -1 — отрицательное, и можно считать, что они никогда не равны.

3. Цикл while (true) {} — это бесконечный цикл без сайд-эффектов, то есть UB. Компилятор считает, что если мы сюда пришли, то делать можно всё что угодно. Например... Ничего. Вообще. Можно просто удалить цикл и весь последующий код вместе с return'ом.

Оба раза компилятор сделал нечто умное и полезное. Удаление сравнения двух чисел и замена его на константу — это благо. Вам не придётся тратить на это процессорный такт. Что касается удаления бесконечного цикла, то тут о благостности можно поспорить, но с другой стороны, представьте, что кто-то бы после while (true) {} написал целую гору кода. Например. по ошибке. Компилятору бы пришлось её оптимизировать и тащить до самого конца, тратя на этот код своё время, притом, что он никогда не исполнится. Учитывая это, его удаление — это тоже полезно, по крайней мере для ускорения самой компиляции. Выходит, компилятор пытался сделать только добро, а сделал какую-то опасную ерунду.

UB - свойство времени исполнения

Многие задаются вопросом: ну хорошо, раз UB — это, потенциально, очень страшно и может привести к ужасным последствиям, почему бы компилятором просто не выдавать warning в тех ситуациях, когда вы написали опасный код? Мы могли бы с помощью опций сделать его ошибкой и вообще избавиться от этой проблемы.

Дело в том, что в языках вроде С++ очень многие конструкции потенциально могут иметь неопределённое поведение при определённых условиях. Деление ведёт к UB только если знаменатель равен нулю. Вряд ли кто-то специально написал там константу 0 (такое бывает, но это скорее сделано в рамках какого-то учебного опыта, а не практической задачи), скорее всего написано <выражение 1> / <выражение 2>, и чему равно выражение 2 — будет известно только во время исполнения. Аналогичным образом, бесконечным может оказаться не только цикл while (true), но и цикл с каким-то сложным, не анализируемым условием, которое, тем не менее, всегда истинно. Также сложение x + y может переполниться при передаче одних параметров (и породить UB), а может и не переполниться.

Если бы мы захотели иметь такой warning, он бы вылетал примерно на каждой первой строчке вашей программы. Очень редко когда значения выражений можно оценить и проанализировать на предмет переполнения/инвариантной истинности/нулёвости во время компиляции. Строго говоря, это можно сделать только для констант, constexpr'ов и их производных, да и то не всегда (иногда это слишком долго, чтобы компилятор занимался этим на практике). Поэтому чаще всего то, будет ли ваша программа иметь неопределённое поведение или нет, определяется входными данными во время исполнения.

Приведём пример:

int foo(int x) {
  int sum = 0;
  for (int i = 0; i < 1000; i++)
    if (cond(i))
      sum += i / x;
  return sum;
}

Данная функция будет иметь неопределённое поведение при одновременном соблюдении двух условий:

• Функция будет вызвана с x = 0

• cond(i) вернёт true хотя бы один раз

В этом случае произойдёт деление на 0, и программа имеет право закрашиться, повиснуть, вернуть какую-нибудь ерунду и т.д. Однако сам факт наличия в ней деления ещё не означает, что в программе всегда присутствует UB.

Неизбежное UB путешествует во времени

Интересно то, что если при каком-то сценарии неопределённое поведение в программе присутствует, то не имеет никакого значения, где именно и когда оно проявится. Приведём пример:

void foo(int *ptr) {
  printf("Before the loopn");
  for (int i = 0; i < 1000; i++) {
    printf("Before checkn");
    if (i == 17)
      *ptr = 1;
    printf("After checkn");
  }
  printf("After the loop the loopn");
}

Человеку наивному может показаться, что при вызове с ptr = nullptr поведение программы должно быть следующим:

• Программа точно напечатает "Before the loop";

• Программа точно 17 раз напечатает пару "Before check"/"After check";

• Потом для i = 17 ещё раз точно напечатается "Before check", а вот дальше может произойти краш/зависание/либо программа продолжит работать, но сделает что-нибудь странное.

Такое рассуждение возникает, если думать, что компилятор будет исполнять ровно ту программу, которую вы написали, и именно так же. На самом деле, современные оптимизирующие компиляторы так не делают. В данном случае компилятор вполне имеет право проделать следующую цепочку рассуждений:

• Условие i == 17 станет истинным (причём только 1 раз) в ходе выполнения данного цикла;

• Поэтому запись единицы в *ptr обязательно произойдёт;

• Чтобы не делать лишнюю проверку в цикле, компилятор имеет право сделать любое из следующих преобразований:

void foo(int *ptr) {
  *ptr = 1;
  printf("Before the loopn");
  for (int i = 0; i < 1000; i++) {
    printf("Before checkn");
    printf("After checkn");
  }
  printf("After the loop the loopn");
}

void foo(int *ptr) {
  printf("Before the loopn");
  for (int i = 0; i < 1000; i++) {
    printf("Before checkn");
    printf("After checkn");
  }
  printf("After the loop the loopn");
  *ptr = 1;
}

void foo(int *ptr) {
  printf("Before the loopn");
  for (int i = 0; i < 17; i++) {
    printf("Before checkn");
    printf("After checkn");
  }
  *ptr = 1;
  for (int i = 17; i < 1000; i++) {
    printf("Before checkn");
    printf("After checkn");
  }
  printf("After the loop the loopn");
}

Наверное, можно придумать и другие варианты, но довольно и этих. UB - свойство динамическое. Если ptr != nullptr, то его в этой программе вообще нет, и установка единицы в эту память может происходить вообще независимо от принтов, и внешних различий в поведении вы не увидите. Однако если ptr == nullptr, то компилятор рассуждает примерно так: раз UB неизбежно случится в этой программе (а это так, потому что i == 17 точно станет true рано или поздно), то всё равно, когда оно произойдёт. Вся эта программа динамически имеет неопределённое поведение . Поэтому если краш (или другой неожиданный эффект) случится до или после цикла и принтов, то это абсолютно нормально. UB — свойство не конкретной операции, а всей программы, в которой эта операция выполнится.

Таким образом, если программа закрашится до того, как будет напечатан первый принт, или после того, как будет напечатан последний — и то, и другое будет совершенно правильно. Данный эффект объясняет, почему баги, связанные с UB, так сложно диагностировать, обкладывая принтами, в оптимизирующем режиме. Лучше для этого использовать -O0. Там всё ещё нет железных гарантий, но есть надежда, что это сработает.

Безопасно ли выносить инварианты из циклов?

Некоторые оптимизации построены на так называемых спекулятивных вычислениях. Это когда какие-то выражения вычисляются заранее, притом не факт, что их результат вообще потребуется. Приведу простой пример.

bool cond(int idx);

int example_add(int x, int y) {
  int sum = 0;
  for (int i = 0; i < 1000; i++)
    if (cond(i))
      sum += x + y;
  return sum;
}

Понятно, что если cond() вернёт true хотя бы раз, а лучше — много раз, то имеет смысл вот такая оптимизация:

bool cond(int idx);

int example_add(int x, int y) {
  int sum = 0;
  int tmp = x + y;
  for (int i = 0; i < 1000; i++)
    if (cond(i))
      sum += tmp;
  return sum;
}

Такая оптимизация называется "вынос инвариантов из цикла", здесь значение выражения x + y не зависит от номера итерации и является т.н. инвариантом. Такие выражения достаточно вычислить один раз и в цикле переиспользовать результат. Нам бы хотелось, чтобы оптимизирующий компилятор был в состоянии проделать такое преобразование. Но давайте рассмотрим чуть-чуть другой пример.

bool cond(int idx);

int example_div(int x, int y) {
  int sum = 0;
  for (int i = 0; i < 1000; i++)
    if (cond(i))
      sum += x / y;
  return sum;
}

Можем ли мы предвычислить данное выражение, сделав что-то вроде

bool cond(int idx);

int example_div(int x, int y) {
  int sum = 0;
  int tmp = x / y;
  for (int i = 0; i < 1000; i++)
    if (cond(i))
      sum += tmp;
  return sum;
}

Казалось бы, всё то же самое. Но погодите-ка. А что если cond() всегда возвращает нам false, а y = 0? В этом случае изначальная функция никогда не выполняет операцию деления на 0, которая ведёт к неопределённому поведению, а оптимизированная - разделит на 0, после чего программа может повиснуть или покрашиться. Выходит, такое преобразование вот так в лоб делать нельзя.

Но что у нас там было со сложением? Ведь там-то всё безопасно? Ведь так?

Ну чисто формально, с точки зрения С++ и демон-оптимайзера — нет. Вспоминаем, что в С++ знаковые переполнения — это UB. В ситуации, когда x + y переполняется, а cond() всегда возвращает false, исходная программа не имела UB, а новая — имеет. Злобный демон-оптимайзер мог бы воспользоваться этим фактом и вставить rm -rf / в случае переполнения в оптимизированном коде. Неужели оптимизация невалидна?

Poison в LLVM

Может показаться, что по причинам, описанным выше, в С++ вообще ничего нельзя спекулировать. Малейший чих — и вы получите UB в месте, где его не было, и оптимизатор, из самых лучших побуждений, вас после этого похоронит вместе с программой и жёстким диском. К счастью, на самом деле всё не так плохо. В реальности clang сложение всё-таки выносит. Но как он это делает? Разве ему не страшно?

Не следует забывать, что оптимизации всё-таки происходят не в С++-коде, а на уровне IR. И курощение диких эффектов неопределённого поведения — в том числе лежит на плечах того, кто определяет, как оно моделируется в IR. Интересующиеся могут на эту тему почитать статьи Джона Рейгра из университета штата Юта и других, я же вкратце опишу, как этот вопрос решается сейчас в LLVM.

Для тех, кто не читал первые две части, сейчас самое время прочитать, ссылки есть в шапке.

На уровне IR-инструкций, существует 2 типа неопределённого поведения:

• Немедленное UB, которое происходит в момент исполнения соответствующей проблемной инструкции;

• Отложенное UB, выражаемое отравленным (poison) значением, и которое может при определённых условиях произойти после выполнения проблемной инструкции (а может и не произойти).

Там раньше было (и всё ещё остаётся) такая вещь, как undef, но она является более слабой формой poison'а, и о ней мы говорить сегодня не будем. Почему от неё отказались, пишет тот же Джон Рейгр. Poison не является никаким числом и обладает следующими удивительными свойствами:

• Любая инструкция, операндом которой является poison, либо ведёт к неопределённому поведению, либо также производит poison

  • Исключения: финода становится poison только если мы реально приходим из блока, откуда он приходит; select не становится poison, если он динамически не выбран, и есть ещё специальная freeze-инструкция. О ней мы поговорим как-нибудь в другой раз, желающие могут ознакомиться в LangRef.

• Таким образом, poison как бы распространяется по поддеревьям выражений, "отравляя" их, а если яд дотечёт до какой-то опасной инструкции и она исполнится, то случится непосредственное UB.

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

Чтобы понять, что это такое, давайте рассмотрим другой очень известный пример: в С++ программа

void foo(int x) {
  if (x + 1 > x)
    printf("true");
  else
    printf("false");
}

может быть соптимизирована просто в

void foo(int x) {
  printf("true");
}

При этом true напечатается даже при x = SINT_MAX, когда наивные люди могли бы ожидать, что x + 1 переполнится и сравнение даст false. На самом деле, происходит следующее:

...
  %x.plus.1 = add nsw i32 %x, 1
  %cmp = icmp sgt i32 %x.plus.1, %x
  br i1 %cmp, label %if.true, label %if.false
...

Тут стоит флаг nsw (no sign wrap), гарантирующий отсутствие знакового переполнения. Если оно всё же произойдёт (функция будет вызвана с x = SINT_MAX), то результатом этой инструкции будет poison. Компилятор же размышляет примерно так:

• У меня есть гарантия того, что при вычислении %x.plus.1 не будет переполнения.

  • Если это в самом деле так, то %x + 1 > %x, и я естественным образом могу заменить %cmp на true

  • Если мою гарантию нарушили, то результатом %x.plus.1 станет poison. Поскольку у инструкции %cmp есть операнд poison, то её результат также poison. Мне выгодно заменить этот poison на true.

• Поэтому всегда валидно заменить %cmp на true

На практике, nsw и им подобные флаги (есть ещё nuw у интов, всякие nnan, ninf и т.п. у флотов, а также метаданные диапазонов (!range) на лоадах, и многое другое) говорят: соответствующих ситуаций (переполнений, нанов, бесконечностей, значений вне диапазона) тут просто быть не может. Оптимизируйте так, будто бы их нет. А если они всё же будут, то там всё превратится в poison, который потом может привести к реальному UB, а может и не привести.

Отложенное UB и правильный вынос инвариантов

Для того, чтобы понять, как poison реализует отложенное UB, перепишем функции example_add и example_div на LLVM IR.

define noundef i32 @example_add(i32 noundef %x, i32 noundef %y) {
entry:
  br label %loop

loop:                                             ; preds = %backedge, %entry
  %sum = phi i32 [ 0, %entry ], [ %sum.merged, %backedge ]
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %loop.exit.cond = icmp slt i32 %iv, 1000
  br i1 %loop.exit.cond, label %check_cond, label %exit

exit:                                             ; preds = %loop
  ret i32 %sum

check_cond:                                       ; preds = %loop
  %cond = call zeroext i1 @cond(i32 %iv)
  br i1 %cond, label %update_sum, label %backedge

update_sum:                                       ; preds = %check_cond
  %x.plus.y = add nsw i32 %x, %y
  %sum.updated = add nsw i32 %sum, %x.plus.y
  br label %backedge

backedge:                                         ; preds = %update_sum, %check_cond
  %sum.merged = phi i32 [ %sum.updated, %update_sum ], [ %sum, %check_cond ]
  %iv.next = add nsw i32 %iv, 1
  br label %loop
}

define noundef i32 @example_div(i32 noundef %x, i32 noundef %y) {
entry:
  br label %loop

loop:                                             ; preds = %backedge, %entry
  %sum = phi i32 [ 0, %entry ], [ %sum.merged, %backedge ]
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %loop.exit.cond = icmp slt i32 %iv, 1000
  br i1 %loop.exit.cond, label %check_cond, label %exit

exit:                                             ; preds = %loop
  ret i32 %sum

check_cond:                                       ; preds = %loop
  %cond = call zeroext i1 @cond(i32 %iv)
  br i1 %cond, label %update_sum, label %backedge

update_sum:                                       ; preds = %check_cond
  %x.div.y = sdiv i32 %x, %y
  %sum.updated = add nsw i32 %sum, %x.div.y
  br label %backedge

backedge:                                         ; preds = %update_sum, %check_cond
  %sum.merged = phi i32 [ %sum.updated, %update_sum ], [ %sum, %check_cond ]
  %iv.next = add nsw i32 %iv, 1
  br label %loop
}

declare i1 @cond(i32)

На первый взгляд разницы никакой нет. Тут одинаковый CFG и плюс-минус одинаковые вычисления, отличается только инструкция в блоке update_sum (в одном случае add nsw, а в другом — sdiv). Однако различие между ними несколько больше, чем кажется на первый взгляд.

Дело в том, что sdiv представляет пример инструкции, которая имеет непосредственное неопределённое поведение при исполнении. Поэтому передвинуть её из блока update_sum в блок entry — нельзя, потому что в сценарии, когда cond() всегда возвращает false, в изначальной программы UB динамически не исполняется, а после переноса оно бы исполнялось.

Однако add nsw не ведёт к непосредственному UB. Он в случае переполнения произведёт poison, что само по себе не опасно. Однако poison имеет свойство отравлять другие инструкции, и в данном случае цепочка отравлений выглядит следующим образом:

• %x.plus.y — poison при переполнении

• %sum.updated — poison, если %x.plus.y — poison

• %sum.merged — poison, если %sum.updated — poison и мы пришли туда из блока %update_sum

• %sum — poison, если %sum.merged — poison, и мы пришли туда из блока %backedge

• ret i32 %sum — непосредственное UB, если %sum — poison (потому что функция помечена как noundef)

То есть, для того, чтобы тут случилось непосредственное UB, нужно чтобы одновременно:

• Poison возник в результате переполнения x + y

• Мы прошли по пути check_cond → update_sum → backedge

В противном случае poison может и возникнуть, но непосредственного UB не будет! Именно это и даёт полное основание выполнить инструкцию add спекулятивно в блоке entry. Это, например, может сделать оптимизация LICM.

Заметьте, что несмотря на то, что даже если x + y реально переполняется, но cond() всегда возвращает false, то мы не пойдём в блок update_sum, и, соответственно, не отравим всю эту цепочку вплоть до return'а.

Вместо заключения

Тема неопределённого поведения — большая. Людей, которые очень хорошо понимают все связанные с ним аспекты — в мире достаточно немного. Примеров, как оно может проявляться и использоваться компилятором — десятки. Я привёл лишь несколько самых простых, чтобы показать самую суть явления. Выпишу только ключевые тезисы, которые будут иметь значение дальше:

• Неопределённое поведение — динамическое свойство программ, которое может реализоваться или не реализоваться во время исполнения;

• Программа, в которой есть UB — "закоррапчена" вся вместе, и UB в ней может произойти в самых неожиданных местах, а не только там, где это бы было при наивном пошаговом исполнении программы;

• Компиляторы могут опираться на гарантии вида "такая ситуация не произойдёт", оптимизировать с учётом этих гарантий, а если ситуация всё же происходит — это и есть UB;

• В LLVM существует непосредственное и отложенное UB. Последнее реализуется через poison, и появление poison не обязательно приведёт к UB (для этого могут потребоваться некоторые другие условия).