c++ - пример - unspecified behavior




В какой момент цикла переполнение целых чисел становится неопределенным поведением? (8)

Главный ответ - неправильное (но распространенное) заблуждение:

Неопределенное поведение является свойством времени выполнения *. НЕ МОЖЕТ "путешествовать во времени"!

Определенные операции определены (стандартом) как побочные эффекты и не могут быть оптимизированы. Операции, которые выполняют ввод-вывод или получают доступ к переменным переменным, попадают в эту категорию.

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

На самом деле это согласуется с цитатой в верхнем ответе (выделено мной):

Соответствующая реализация, выполняющая правильно сформированную программу, должна производить то же наблюдаемое поведение, что и одно из возможных исполнений соответствующего экземпляра абстрактной машины с той же программой и тем же вводом.
Однако, если любое такое выполнение содержит неопределенную операцию, этот международный стандарт не предъявляет никаких требований к реализации, выполняющей эту программу с этим вводом (даже в отношении операций, предшествующих первой неопределенной операции).

Да, эта цитата говорит «даже не в отношении операций, предшествующих первой неопределенной операции» , но обратите внимание, что речь идет именно о коде, который выполняется , а не просто компилируется.
В конце концов, неопределенное поведение, которое на самом деле не достигнуто, ничего не делает, и для того, чтобы строка, содержащая UB, была фактически достигнута, код, предшествующий ему, должен выполняться первым!

Так что да, после выполнения UB любые эффекты предыдущих операций становятся неопределенными. Но пока это не произойдет, выполнение программы будет четко определено.

Обратите внимание, однако, что все исполнения программы, которые приводят к этому, могут быть оптимизированы для эквивалентных программ, включая любую, которая выполняет предыдущие операции, но затем не выполняет свои эффекты. Следовательно, предыдущий код можно оптимизировать всякий раз, когда это будет эквивалентно отмене их эффектов ; в противном случае это невозможно. Смотрите ниже пример.

* Примечание: это не противоречит UB, возникающему во время компиляции . Если компилятор действительно может доказать, что код UB всегда будет выполняться для всех входных данных, тогда UB может расширяться до времени компиляции. Однако для этого необходимо знать, что весь предыдущий код в конечном итоге возвращается , что является сильным требованием. Опять же, см. Ниже пример / объяснение.

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

printf("foo");
getchar();
*(char*)1 = 1;

Однако также обратите внимание, что нет никакой гарантии, что foo она останется на экране после появления UB, или что введенный вами символ больше не будет находиться во входном буфере; обе эти операции могут быть «отменены», что имеет эффект, аналогичный «перемещению во времени» UB.

Если бы getchar() строки там не было, то было бы законно оптимизировать эти строки, если и только если это было бы неотличимо от вывода, foo а затем «неделания» этого.

Независимо от того, будут ли эти два элемента неразличимыми, будет полностью зависеть от реализации (т.е. от вашего компилятора и стандартной библиотеки). Например, можете ли вы printf заблокировать ваш поток здесь, ожидая, пока другая программа прочитает вывод? Или он сразу вернется?

  • Если он может блокировать здесь, тогда другая программа может отказаться читать ее полный вывод, и она может никогда не вернуться, и, следовательно, UB может никогда не произойти.

  • Если он может немедленно вернуться сюда, то мы знаем, что он должен вернуться, и, следовательно, его оптимизация совершенно неотличима от его выполнения, а затем от его последствий.

Конечно, поскольку компилятор знает, какое поведение допустимо для его конкретной версии printf , он может соответствующим образом оптимизировать и, следовательно, printf может оптимизироваться в некоторых случаях, а не в других. Но, опять же, оправдание состоит в том, что это было бы неотличимо от невыполнения предыдущими операциями UB, а не того, что предыдущий код «отравлен» из-за UB.

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

#include <stdio.h>
int main()
{
    int a = 0;
    for (int i = 0; i < 3; i++)
    {
        printf("Hello\n");
        a = a + 1000000000;
    }
}

Эта программа содержит неопределенное поведение на моей платформе из- a переполнения в 3-м цикле.

Делает ли это, что вся программа имеет неопределенное поведение, или только после того, как переполнение действительно происходит ? Может ли компилятор решить, что переполнение будет переполнено, чтобы он мог объявить весь цикл неопределенным и не беспокоиться о запуске printfs, даже если все они происходят до переполнения?

(С метками C и C ++, хотя они разные, потому что мне будут интересны ответы на оба языка, если они будут разными.)


TartanLlama ответ правильный. Неопределенное поведение может произойти в любое время, даже во время компиляции. Это может показаться абсурдным, но это ключевая функция, позволяющая компиляторам делать то, что им нужно. Быть компилятором не всегда легко. Вы должны делать именно то, что говорит спецификация, каждый раз. Однако иногда может быть чудовищно сложно доказать, что происходит определенное поведение. Если вы помните проблему остановки, достаточно просто разработать программное обеспечение, для которого вы не можете доказать, завершается ли оно или входит в бесконечный цикл при подаче определенного ввода.

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

Есть пример, который я люблю публиковать, хотя я признаю, что потерял источник, поэтому я должен перефразировать. Это было из определенной версии MySQL. В MySQL у них был кольцевой буфер, который был заполнен предоставленными пользователем данными. Они, конечно, хотели убедиться, что данные не переполняют буфер, поэтому у них была проверка:

if (currentPtr + numberOfNewChars > endOfBufferPtr) { doOverflowLogic(); }

Это выглядит достаточно вменяемым. Однако что, если numberOfNewChars действительно велико и переполняется? Затем он оборачивается и становится указателем, меньшим, чем endOfBufferPtr , поэтому логика переполнения никогда не будет вызвана. Поэтому они добавили вторую проверку перед этой:

if (currentPtr + numberOfNewChars < currentPtr) { detectWrapAround(); }

Похоже, вы позаботились об ошибке переполнения буфера, верно? Однако была отправлена ​​ошибка о том, что этот буфер переполнен в определенной версии Debian! Тщательное расследование показало, что эта версия Debian первой использовала особенно передовую версию gcc. В этой версии gcc компилятор распознал, что currentPtr + numberOfNewChars никогда не может быть меньшим указателем, чем currentPtr, потому что переполнение для указателей является неопределенным поведением! Этого было достаточно, чтобы gcc оптимизировал всю проверку, и вдруг вы не были защищены от переполнения буфера, даже если вы написали код для проверки!

Это было специальное поведение. Все было законно (хотя, как я слышал, gcc откатил это изменение в следующей версии). Это не то, что я бы назвал интуитивным поведением, но если вы немного напрягаете воображение, легко увидеть, как небольшой вариант этой ситуации может стать проблемой остановки для компилятора. Из-за этого авторы спецификаций сделали это «неопределенным поведением» и заявили, что компилятор может делать абсолютно все, что ему нравится.


Во-первых, позвольте мне исправить заголовок этого вопроса:

Неопределенное поведение не относится (конкретно) к сфере исполнения.

Неопределенное поведение влияет на все этапы: компиляция, компоновка, загрузка и выполнение.

Некоторые примеры, подтверждающие это, помните, что ни один раздел не является исчерпывающим:

  • компилятор может предположить, что части кода, которые содержат неопределенное поведение, никогда не выполняются, и, таким образом, предположить, что пути выполнения, которые привели бы к ним, являются мертвым кодом. Посмотрите, что каждый программист на С должен знать о неопределенном поведении никого, кроме Криса Латтнера.
  • компоновщик может предположить, что при наличии нескольких определений слабого символа (распознаваемого по имени) все определения идентичны благодаря правилу единого определения
  • загрузчик (если вы используете динамические библиотеки) может предполагать то же самое, выбирая первый найденный символ; это обычно (ab) используется для перехвата вызовов с помощью трюков LD_PRELOAD в Unixes
  • выполнение может завершиться ошибкой (SIGSEV), если вы используете висячие указатели

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

Я рекомендую посмотреть это видео от Майкла Спенсера (LLVM Developer): CppCon 2016: Мой маленький оптимизатор: Неопределенное поведение - это магия .


Если вас интересует чисто теоретический ответ, стандарт C ++ позволяет неопределенному поведению «путешествовать во времени»:

[intro.execution]/5: Соответствующая реализация, выполняющая правильно сформированную программу, должна производить то же наблюдаемое поведение, что и одно из возможных исполнений соответствующего экземпляра абстрактной машины с той же программой и тем же вводом. Однако, если любое такое выполнение содержит неопределенную операцию, этот международный стандарт не предъявляет никаких требований к реализации, выполняющей эту программу с этим вводом (даже в отношении операций, предшествующих первой неопределенной операции)

Таким образом, если ваша программа содержит неопределенное поведение, то поведение всей вашей программы не определено.


Одна вещь, которую ваш пример не учитывает, это оптимизация. a установлен в цикле, но никогда не используется, и оптимизатор может решить это. Таким образом, для оптимизатора вполне законно отказаться полностью, и в этом случае все неопределенное поведение исчезает, как жертва бужума.

Однако, конечно, это само по себе не определено, потому что оптимизация не определена. :)


Помимо теоретических ответов, практическое наблюдение состояло бы в том, что в течение длительного времени компиляторы применяли различные преобразования к циклам, чтобы уменьшить объем работы, выполняемой в них. Например, учитывая:

for (int i=0; i<n; i++)
  foo[i] = i*scale;

компилятор может преобразовать это в:

int temp = 0;
for (int i=0; i<n; i++)
{
  foo[i] = temp;
  temp+=scale;
}

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

if (n > 0)
{
  int temp1 = n*scale;
  int *temp2 = foo;
  do
  {
    temp1 -= scale;
    *temp2++ = temp1;
  } while(temp1);
}

Даже на машинах с бесшумным циклическим переполнением при переполнении это может привести к сбоям в работе, если существует некоторое число, меньшее n, которое при умножении на масштабирование даст 0. Это также может превратиться в бесконечный цикл, если масштабирование читается из памяти более одного раза и что-то еще изменил его значение неожиданно (в любом случае, когда «scale» мог изменить середину цикла без вызова UB, компилятору не разрешили бы выполнить оптимизацию).

Хотя большинство таких оптимизаций не будет иметь проблем в случаях, когда два коротких типа без знака умножаются, чтобы получить значение, которое находится между INT_MAX + 1 и UINT_MAX, в некоторых случаях gcc может привести к преждевременному выходу из цикла. , Я не заметил такого поведения, вытекающего из инструкций сравнения в сгенерированном коде, но это наблюдается в тех случаях, когда компилятор использует переполнение, чтобы сделать вывод, что цикл может выполняться максимум 4 или меньше раз; по умолчанию он не генерирует предупреждения в тех случаях, когда одни входы вызывают UB, а другие - нет, даже если его выводы приводят к игнорированию верхней границы цикла.


Предполагая, что int 32-битный, неопределенное поведение происходит на третьей итерации. Таким образом, если, например, цикл был только условно достижимым или мог быть условно завершен до третьей итерации, не было бы неопределенного поведения, если третья итерация фактически не достигнута. Тем не менее, в случае неопределенного поведения, все выходные данные программы не определены, включая выходные данные, которые «в прошлом» относительно вызова неопределенного поведения. Например, в вашем случае это означает, что нет гарантии, что вы увидите 3 сообщения «Hello» в выходных данных.


Технически, в соответствии со стандартом C ++, если программа содержит неопределенное поведение, поведение всей программы, даже во время компиляции (даже до того, как программа будет выполнена), является неопределенным.

На практике, поскольку компилятор может предположить (как часть оптимизации), что переполнение не произойдет, по крайней мере, поведение программы на третьей итерации цикла (при условии, что 32-битный компьютер) будет неопределенным, хотя скорее всего, вы получите правильные результаты до третьей итерации. Однако, поскольку поведение всей программы технически не определено, ничто не мешает программе генерировать совершенно неверный вывод (включая отсутствие вывода), сбой во время выполнения в любой момент во время выполнения или даже невозможность компиляции полностью (так как неопределенное поведение распространяется на время компиляции).

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






integer-overflow