Почему этот цикл выдает «предупреждение: итерация 3u вызывает неопределенное поведение» и выводит более 4 строк?

Компилируя это:

#include <iostream>

int main()
{
    for (int i = 0; i < 4; ++i)
        std::cout << i*1000000000 << std::endl;
}

и gccвыдает следующее предупреждение:

warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
   std::cout << i*1000000000 << std::endl;
                  ^

Я понимаю, что есть целочисленное переполнение со знаком.

Чего я не могу получить, так это того, почему iзначение нарушается этой операцией переполнения?

Я прочитал ответы на вопросы. Почему целочисленное переполнение в x86 с GCC вызывает бесконечный цикл? , но я до сих пор не понимаю, почему это происходит - я понимаю, что «неопределенный» означает «все может случиться», но какова основная причина этого конкретного поведения ?

Онлайн: http://ideone.com/dMrRKR

Составитель: gcc (4.8)

Целочисленное переполнение со знаком (строго говоря, не существует такого понятия, как переполнение без знака), что означает неопределенное поведение . А это значит, что все может случиться, и обсуждать, почему это происходит по правилам C ++, не имеет смысла.

C ++ 11 черновик N3337: §5.4: ¹

Если во время вычисления выражения результат математически не определен или не находится в диапазоне представимых значений для его типа, поведение не определено. [Примечание: большинство существующих реализаций C ++ игнорируют целочисленные потоки. Обработка деления на ноль, формирования остатка с использованием делителя нуля и всех исключений с плавающей точкой варьируется в зависимости от машины и обычно настраивается библиотечной функцией. —Конечная записка]

Ваш код, скомпилированный с g++ -O3предупреждением о выбросах (даже без -Wall)

a.cpp: In function 'int main()':
a.cpp:11:18: warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
   std::cout << i*1000000000 << std::endl;
                  ^
a.cpp:9:2: note: containing loop
  for (int i = 0; i < 4; ++i)
  ^

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

Вот полный список сборки:

    .file   "a.cpp"
    .section    .text$_ZNKSt5ctypeIcE8do_widenEc,"x"
    .linkonce discard
    .align 2
LCOLDB0:
LHOTB0:
    .align 2
    .p2align 4,,15
    .globl  __ZNKSt5ctypeIcE8do_widenEc
    .def    __ZNKSt5ctypeIcE8do_widenEc;    .scl    2;  .type   32; .endef
__ZNKSt5ctypeIcE8do_widenEc:
LFB860:
    .cfi_startproc
    movzbl  4(%esp), %eax
    ret $4
    .cfi_endproc
LFE860:
LCOLDE0:
LHOTE0:
    .section    .text.unlikely,"x"
LCOLDB1:
    .text
LHOTB1:
    .p2align 4,,15
    .def    ___tcf_0;   .scl    3;  .type   32; .endef
___tcf_0:
LFB1091:
    .cfi_startproc
    movl    $__ZStL8__ioinit, %ecx
    jmp __ZNSt8ios_base4InitD1Ev
    .cfi_endproc
LFE1091:
    .section    .text.unlikely,"x"
LCOLDE1:
    .text
LHOTE1:
    .def    ___main;    .scl    2;  .type   32; .endef
    .section    .text.unlikely,"x"
LCOLDB2:
    .section    .text.startup,"x"
LHOTB2:
    .p2align 4,,15
    .globl  _main
    .def    _main;  .scl    2;  .type   32; .endef
_main:
LFB1084:
    .cfi_startproc
    leal    4(%esp), %ecx
    .cfi_def_cfa 1, 0
    andl    $-16, %esp
    pushl   -4(%ecx)
    pushl   %ebp
    .cfi_escape 0x10,0x5,0x2,0x75,0
    movl    %esp, %ebp
    pushl   %edi
    pushl   %esi
    pushl   %ebx
    pushl   %ecx
    .cfi_escape 0xf,0x3,0x75,0x70,0x6
    .cfi_escape 0x10,0x7,0x2,0x75,0x7c
    .cfi_escape 0x10,0x6,0x2,0x75,0x78
    .cfi_escape 0x10,0x3,0x2,0x75,0x74
    xorl    %edi, %edi
    subl    $24, %esp
    call    ___main
L4:
    movl    %edi, (%esp)
    movl    $__ZSt4cout, %ecx
    call    __ZNSolsEi
    movl    %eax, %esi
    movl    (%eax), %eax
    subl    $4, %esp
    movl    -12(%eax), %eax
    movl    124(%esi,%eax), %ebx
    testl   %ebx, %ebx
    je  L15
    cmpb    $0, 28(%ebx)
    je  L5
    movsbl  39(%ebx), %eax
L6:
    movl    %esi, %ecx
    movl    %eax, (%esp)
    addl    $1000000000, %edi
    call    __ZNSo3putEc
    subl    $4, %esp
    movl    %eax, %ecx
    call    __ZNSo5flushEv
    jmp L4
    .p2align 4,,10
L5:
    movl    %ebx, %ecx
    call    __ZNKSt5ctypeIcE13_M_widen_initEv
    movl    (%ebx), %eax
    movl    24(%eax), %edx
    movl    $10, %eax
    cmpl    $__ZNKSt5ctypeIcE8do_widenEc, %edx
    je  L6
    movl    $10, (%esp)
    movl    %ebx, %ecx
    call    *%edx
    movsbl  %al, %eax
    pushl   %edx
    jmp L6
L15:
    call    __ZSt16__throw_bad_castv
    .cfi_endproc
LFE1084:
    .section    .text.unlikely,"x"
LCOLDE2:
    .section    .text.startup,"x"
LHOTE2:
    .section    .text.unlikely,"x"
LCOLDB3:
    .section    .text.startup,"x"
LHOTB3:
    .p2align 4,,15
    .def    __GLOBAL__sub_I_main;   .scl    3;  .type   32; .endef
__GLOBAL__sub_I_main:
LFB1092:
    .cfi_startproc
    subl    $28, %esp
    .cfi_def_cfa_offset 32
    movl    $__ZStL8__ioinit, %ecx
    call    __ZNSt8ios_base4InitC1Ev
    movl    $___tcf_0, (%esp)
    call    _atexit
    addl    $28, %esp
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc
LFE1092:
    .section    .text.unlikely,"x"
LCOLDE3:
    .section    .text.startup,"x"
LHOTE3:
    .section    .ctors,"w"
    .align 4
    .long   __GLOBAL__sub_I_main
.lcomm __ZStL8__ioinit,1,1
    .ident  "GCC: (i686-posix-dwarf-rev1, Built by MinGW-W64 project) 4.9.0"
    .def    __ZNSt8ios_base4InitD1Ev;   .scl    2;  .type   32; .endef
    .def    __ZNSolsEi; .scl    2;  .type   32; .endef
    .def    __ZNSo3putEc;   .scl    2;  .type   32; .endef
    .def    __ZNSo5flushEv; .scl    2;  .type   32; .endef
    .def    __ZNKSt5ctypeIcE13_M_widen_initEv;  .scl    2;  .type   32; .endef
    .def    __ZSt16__throw_bad_castv;   .scl    2;  .type   32; .endef
    .def    __ZNSt8ios_base4InitC1Ev;   .scl    2;  .type   32; .endef
    .def    _atexit;    .scl    2;  .type   32; .endef

Я едва могу даже прочитать сборку, но даже я вижу addl $1000000000, %ediлинию. Полученный код больше похож на

for(int i = 0; /* nothing, that is - infinite loop */; i += 1000000000)
    std::cout << i << std::endl;

Этот комментарий @TC:

Я подозреваю, что это что-то вроде: (1) потому что каждая итерация с iлюбым значением больше 2 имеет неопределенное поведение -> (2) мы можем предположить, что i <= 2в целях оптимизации -> (3) условие цикла всегда выполняется -> (4) ) он оптимизирован в бесконечный цикл.

дал мне идею сравнить код сборки кода OP с кодом сборки следующего кода без неопределенного поведения.

#include <iostream>

int main()
{
    // changed the termination condition
    for (int i = 0; i < 3; ++i)
        std::cout << i*1000000000 << std::endl;
}

И действительно, правильный код имеет условие завершения.

    ; ...snip...
L6:
    mov ecx, edi
    mov DWORD PTR [esp], eax
    add esi, 1000000000
    call    __ZNSo3putEc
    sub esp, 4
    mov ecx, eax
    call    __ZNSo5flushEv
    cmp esi, -1294967296 // here it is
    jne L7
    lea esp, [ebp-16]
    xor eax, eax
    pop ecx
    ; ...snip...

О боже, это совершенно не очевидно! Это нечестно! Я требую испытания огнем!

Смирившись с этим, вы написали глючный код, и вам должно быть плохо. Нести последствия.

... или, наоборот, правильно использовать улучшенные средства диагностики и отладки - вот для чего они нужны:

• включить все предупреждения

  • -Wallопция gcc, которая включает все полезные предупреждения без ложных срабатываний Это минимум, который вы всегда должны использовать.
  • У gcc есть много других опций предупреждения , однако они не включены, так -Wallкак могут предупреждать о ложных срабатываниях
  • Visual C ++, к сожалению, отстает со способностью давать полезные предупреждения. По крайней мере, в среде IDE некоторые включены по умолчанию.

• использовать отладочные флаги для отладки

  • для целочисленного переполнения -ftrapvперехватывает программу при переполнении,
  • Clang компилятор отлично подходит для этого: -fcatch-undefined-behaviorловит много случаев неопределенного поведения (примечание: "a lot of" != "all of them")

У меня есть беспорядок спагетти программы, не написанной мной, которая должна быть отправлена ​​завтра! HELP !!!!!! 111oneone

Используйте GCC -fwrapv

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

¹ - это правило не применяется к "переполнению целых чисел без знака", так как в п. 3.9.1.4 сказано, что

Целые числа без знака, объявленные как без знака, должны подчиняться законам арифметики по модулю 2 ^n, где n - количество битов в представлении значения этого конкретного размера целого числа.

и, например, результат UINT_MAX + 1математически определяется - по правилам арифметики по модулю 2 ⁿ

Короткий ответ, в gccчастности, задокументировал эту проблему, мы можем видеть, что в примечаниях к выпуску gcc 4.8, который говорит ( выделение мое в будущем ):

GCC теперь использует более агрессивный анализ, чтобы получить верхнюю границу для числа итераций циклов, используя ограничения, наложенные языковыми стандартами . Это может привести к тому, что несоответствующие программы перестанут работать должным образом, например, SPEC CPU 2006 464.h264ref и 416.gamess. Для отключения этого агрессивного анализа была добавлена ​​новая опция -fno -gressive-loop-optimizations. В некоторых циклах, в которых известно постоянное число итераций, но известно, что неопределенное поведение происходит в цикле до достижения или во время последней итерации, GCC будет предупреждать о неопределенном поведении в цикле вместо получения нижней верхней границы числа итераций. для петли. Предупреждение можно отключить с помощью -Wno -gressive-loop-optimizations.

и действительно, если мы используем -fno-aggressive-loop-optimizationsбесконечный цикл, поведение должно прекратиться, и это происходит во всех случаях, которые я проверял.

Длинные начинает ответ с зная , что знаковое целое переполнение не определено поведение, глядя на проект C ++ стандартный раздел 5 Выражения пункт 4 , который гласит:

Если во время вычисления выражения результат не определен математически или не находится в диапазоне представляемых значений для его типа, поведение не определено . [Примечание: большинство существующих реализаций C ++ игнорируют целочисленные переполнения. Обработка деления на ноль, формирования остатка с использованием делителя нуля и всех исключений с плавающей запятой варьируется в зависимости от машины и обычно настраивается библиотечной функцией. Конец

Мы знаем, что стандарт говорит, что неопределенное поведение непредсказуемо из примечания, которое идет с определением, которое говорит:

[Примечание: неопределенного поведения можно ожидать, когда в этом международном стандарте опущено какое-либо явное определение поведения или когда программа использует ошибочную конструкцию или ошибочные данные. Допустимое неопределенное поведение варьируется от полного игнорирования ситуации с непредсказуемыми результатами до поведения во время перевода или выполнения программы документированным образом, характерным для среды (с выдачей или без выдачи диагностического сообщения), до прекращения перевода или выполнения (с выдачей диагностического сообщения). Многие ошибочные программные конструкции не порождают неопределенного поведения; они должны быть диагностированы. —Конечная записка]

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

warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
   std::cout << i*1000000000 << std::endl;
                  ^

Подсказка в том Waggressive-loop-optimizations, что это значит? К счастью для нас, это не первый раз, когда эта оптимизация ломает код таким образом, и нам повезло, потому что Джон Регер задокументировал случай в статье GCC pre-4.8 Breaks Broken SPEC 2006 Benchmarks, в которой показан следующий код:

int d[16];

int SATD (void)
{
  int satd = 0, dd, k;
  for (dd=d[k=0]; k<16; dd=d[++k]) {
    satd += (dd < 0 ? -dd : dd);
  }
  return satd;
}

в статье говорится:

Неопределенное поведение обращается к d [16] непосредственно перед выходом из цикла. В C99 допустимо создавать указатель на элемент на одну позицию после конца массива, но этот указатель не должен быть разыменован.

и позже говорит:

Подробно, вот что происходит. Компилятор AC, увидев d [++ k], может предположить, что увеличенное значение k находится в пределах массива, поскольку в противном случае происходит неопределенное поведение. Для кода здесь GCC может сделать вывод, что k находится в диапазоне 0..15. Чуть позже, когда GCC видит k <16, он говорит себе: «Ага - это выражение всегда верно, поэтому у нас бесконечный цикл». Ситуация здесь, где компилятор использует допущение четкости для вывода полезного факта потока данных,

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

Он объясняет, что это очень похоже на печально известное удаление проверки нулевого указателя ядра Linux, когда мы видим этот код:

struct foo *s = ...;
int x = s->f;
if (!s) return ERROR;

gccПредполагается, что, поскольку он sбыл определен в s->f;и так как разыменование нулевого указателя является неопределенным поведением, то он sне должен быть нулевым, и поэтому оптимизирует if (!s)проверку на следующей строке.

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

tl; dr Код генерирует тест, в котором целое число + положительное целое число == отрицательное целое число . Обычно оптимизатор не оптимизирует это, но в конкретном случае std::endlследующего использования компилятор оптимизирует этот тест. Я еще не понял, что особенного в endlэтом.

Из кода сборки на уровне -O1 и выше видно, что gcc рефакторинг цикла:

i = 0;
do {
    cout << i << endl;
    i += NUMBER;
} 
while (i != NUMBER * 4)

Самое большое значение, которое работает правильно, это 715827882, например, floor ( INT_MAX/3). Сборочный фрагмент по адресу -O1:

L4:
movsbl  %al, %eax
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
addl    $715827882, %esi
cmpl    $-1431655768, %esi
jne L6
    // fallthrough to "return" code

Обратите внимание, что -1431655768это 4 * 715827882в дополнении 2.

Удар -O2оптимизирует это к следующему:

L4:
movsbl  %al, %eax
addl    $715827882, %esi
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
cmpl    $-1431655768, %esi
jne L6
leal    -8(%ebp), %esp
jne L6 
   // fallthrough to "return" code

Таким образом, оптимизация была сделана просто потому, что addlона поднялась выше.

Если мы перекомпилируем 715827883вместо этого, тогда версия -O1 идентична, кроме измененного номера и тестового значения. Однако -O2 вносит изменения:

L4:
movsbl  %al, %eax
addl    $715827883, %esi
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
jmp L2

Там , где было cmpl $-1431655764, %esiна -O1, что линия была удалена для -O2. Оптимизатор должен решил , что добавление 715827883к %esiникогда не сравнится -1431655764.

Это довольно загадочно. Добавим , что в INT_MIN+1 это генерировать ожидаемый результат, поэтому оптимизатор должен решил , что %esiникогда не может быть , INT_MIN+1и я не знаю , почему это было бы решить , что.

В рабочем примере кажется одинаково верным заключить, что добавление 715827882к числу не может быть равным INT_MIN + 715827882 - 2! (это возможно только в том случае, если на самом деле имеет место перенос), но в этом примере он не оптимизирует строку.

Код, который я использовал:

#include <iostream>
#include <cstdio>

int main()
{
    for (int i = 0; i < 4; ++i)
    {
        //volatile int j = i*715827883;
        volatile int j = i*715827882;
        printf("%d\n", j);

        std::endl(std::cout);
    }
}

Если std::endl(std::cout)удалить, то оптимизация больше не происходит. Фактически, его замена std::cout.put('\n'); std::flush(std::cout);также приводит к тому, что оптимизация не происходит, даже если std::endlона встроена.

Кажется, что встраивание элемента std::endlвлияет на более раннюю часть структуры цикла (что я не совсем понимаю, что она делает, но я опубликую ее здесь на случай, если кто-то другой):

С оригинальным кодом и -O2:

L2:
movl    %esi, 28(%esp)
movl    28(%esp), %eax
movl    $LC0, (%esp)
movl    %eax, 4(%esp)
call    _printf
movl    __ZSt4cout, %eax
movl    -12(%eax), %eax
movl    __ZSt4cout+124(%eax), %ebx
testl   %ebx, %ebx
je  L10
cmpb    $0, 28(%ebx)
je  L3
movzbl  39(%ebx), %eax
L4:
movsbl  %al, %eax
addl    $715827883, %esi
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
jmp L2                  // no test

С mymanual встраивание в std::endl, -O2:

L3:
movl    %ebx, 28(%esp)
movl    28(%esp), %eax
addl    $715827883, %ebx
movl    $LC0, (%esp)
movl    %eax, 4(%esp)
call    _printf
movl    $10, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    $__ZSt4cout, (%esp)
call    __ZNSo5flushEv
cmpl    $-1431655764, %ebx
jne L3
xorl    %eax, %eax

Одно из различий между этими двумя заключается в том, что они %esiиспользуются в оригинале и %ebxво второй версии; Есть ли разница в семантике, определенной между %esiи %ebxв целом? (Я не знаю много о сборке x86).

Другой пример этой ошибки, о которой сообщается в gcc, - это когда у вас есть цикл, который выполняется для постоянного числа итераций, но вы используете переменную counter в качестве индекса в массиве, который содержит меньше этого числа элементов, например:

int a[50], x;

for( i=0; i < 1000; i++) x = a[i];

Компилятор может определить, что этот цикл будет пытаться получить доступ к памяти вне массива «a». Компилятор жалуется на это с довольно загадочным сообщением:

итерация xxu вызывает неопределенное поведение [-Werror = агрессивный цикл-оптимизация]

Что я не могу получить, так это то, почему значение i нарушается этой операцией переполнения?

Кажется, что целочисленное переполнение происходит в 4-й итерации (для i = 3). signedЦелочисленное переполнение вызывает неопределенное поведение . В этом случае ничего нельзя предсказать. Цикл может повторяться только4 раз, или он может идти до бесконечности или что-то еще!
Результат может варьироваться от компилятора к компилятору или даже для разных версий одного и того же компилятора.

C11: 1.3.24 неопределенное поведение:

к поведению, для которого настоящий международный стандарт не предъявляет никаких требований
[Примечание. Неопределенное поведение может ожидаться, когда в этом международном стандарте отсутствует какое-либо явное определение поведения или когда программа использует ошибочную конструкцию или ошибочные данные. Допустимое неопределенное поведение варьируется от полного игнорирования ситуации с непредсказуемыми результатами до поведения во время перевода или выполнения программы документированным образом, характерным для среды (с выдачей или без выдачи диагностического сообщения), до прекращения перевода или выполнения (с выдачей диагностического сообщения) . Многие ошибочные программные конструкции не порождают неопределенного поведения; они должны быть диагностированы. —Конечная записка]