Почему этот цикл создает "предупреждение: итерация 3u вызывает undefined поведение" и выводит более 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 вызывает бесконечный цикл?, но я все еще не понимаю, почему это происходит - Я понимаю, что "undefined" означает "что-нибудь может случиться", но какова основная причина этого конкретного поведения?
В сети: http://ideone.com/dMrRKR
Компилятор: gcc (4.8)
Ответы
Ответ 1
Подписанное целочисленное переполнение (поскольку, строго говоря, нет такой вещи, как "беззнаковое целочисленное переполнение" ) означает поведение undefined. И это означает, что все может случиться, и обсуждение того, почему это происходит в соответствии с правилами С++, не имеет смысла.
С++ 11 черновик N3337: §5.4: 1
Если во время оценки выражения результат не определяется математически или нет в диапазоне представляемые значения для своего типа, поведение не определено. [Примечание: большинство существующих реализаций С++ игнорировать целочисленные потоки. Обработка деления на ноль, формирование остатка с использованием делителя нуля и все исключения исключений из-за разницы между машинами и обычно регулируются библиотечной функцией. -end note]
Ваш код, скомпилированный с помощью 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;
Этот комментарий от @T.C.:
Я подозреваю, что это что-то вроде: (1), потому что каждая итерация с i любого значения больше 2 имеет поведение undefined → (2), мы можем предположить, что i <= 2 для целей оптимизации → (3 ) условие цикла всегда верно → (4) оно оптимизировано в бесконечный цикл.
дал мне идею сравнить код сборки кода OP с кодом сборки следующего кода без поведения undefined.
#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...
OMG, это совершенно не очевидно! Это несправедливо! Я требую суда от огня!
Справьтесь с этим, вы написали код багги, и вам должно быть плохо. Нести последствия.
... или, наоборот, правильно использовать лучшую диагностику и улучшать инструменты отладки - что они предназначены для:
У меня есть спагетти беспорядка программы, не написанной мной, которая должна быть отправлена завтра! HELP!!!!!! 111oneone
Использовать gcc -fwrapv
Этот параметр указывает компилятору предположить, что подписанное арифметическое переполнение сложения, вычитания и умножения обертывается с использованием представления двухкомпонента.
1 - это правило не относится к "беззнаковому целочисленному переполнению", поскольку в §3.1.1.4 говорится, что
Беззнаковые целые числа, объявленные без знака, должны подчиняться законам арифметики по модулю 2 n где n - число бит в представлении значений этого конкретного размера целых чисел.
<p → результат UINT_MAX + 1 математически определен - по правилам арифметики по модулю 2 n
Ответ 2
Короткий ответ, gcc специально зафиксировал эту проблему, мы можем видеть, что в gcc 4.8 примечания к выпуску, в котором говорится (акцент мой вперед):
В настоящее время GCC использует более агрессивный анализ , чтобы получить верхнюю оценку для число итераций циклов с использованием ограничений, налагаемых языковые стандарты. Это может привести к несоответствующим программам как ожидалось, например, SPEC CPU 2006 464.h264ref и 416.gamess. Для отключения этого агрессивного анализа была добавлена новая опция -fno-aggressive-loop-optimizations. В некоторых циклах, которые имеют известное постоянное число итераций, но известно поведение undefinedпроисходить в цикле до достижения или во время последней итерации, GCC будет предупреждать о поведении undefined в цикле вместо получения нижняя верхняя граница числа итераций для цикла. предупреждение может быть отключено с помощью -Wno-агрессивных циклов-оптимизации.
и, действительно, если мы используем -fno-aggressive-loop-optimizations, поведение бесконечного цикла должно прекратиться, и оно будет выполняться во всех случаях, которые я тестировал.
Длительный ответ начинается с того, что знаковое переполнение целых чисел является undefined, просмотрев проект стандартного раздела С++ 5 Выражения, который гласит:
Если во время оценки выражения результат не математически определены или нет в диапазоне представимых значений для его тип, поведение undefined. [Примечание: большинство существующих реализации С++ игнорируют целые переполнения. Лечение деления на ноль, образуя остаток, используя делитель нуля, и все плавающие точечные исключения различаются между машинами и обычно регулируются библиотечная функция. -end note
Мы знаем, что стандарт говорит, что поведение undefined непредсказуемо из примечания, которое приходит с определением, которое гласит:
[Примечание: поведение undefined можно ожидать, когда этот международный Стандарт исключает любое явное определение поведения или когда программа использует ошибочную конструкцию или ошибочные данные. Допустимый undefinedповедение варьируется от полного игнорирования ситуации непредсказуемые результаты, чтобы вести себя во время перевода или программы исполнение в документированном виде, характерном для окружающей среды (с выдачей диагностического сообщения или без него), до завершения перевод или исполнение (с выдачей диагностического сообщение). Многие ошибочные программные конструкции не порождают undefinedповедение; они должны быть диагностированы. -end note]
Но что может сделать оптимизатор 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;
}
в статье говорится:
Поведение undefined обращается к d [16] непосредственно перед выходом из петля. В C99 законно создавать указатель на элемент один позицию за конец массива, но этот указатель не должен быть разыменованный.
а затем говорит:
В деталях, вот что происходит. Компилятор C, увидев d [++ k], разрешено считать, что приращение k равно array, поскольку в противном случае происходит поведение undefined. Для кода здесь GCC может заключить, что k находится в диапазоне 0..15. Немного позже, когда GCC видит k < 16, он говорит себе: "Aha- это выражение всегда true, поэтому мы имеем бесконечный цикл". Ситуация здесь, где компилятор использует предположение о корректности, чтобы сделать полезную факт потока данных,
То, что должен делать компилятор в некоторых случаях, предполагает, что после того, как подписанное целочисленное переполнение - это поведение undefined, тогда i всегда должно быть меньше 4 и, следовательно, мы имеем бесконечный цикл.
Он объясняет, что это очень похоже на печально известный удаление нулевого указателя ядра Linux, где при просмотре этого кода:
struct foo *s = ...;
int x = s->f;
if (!s) return ERROR;
gcc вывел, что, поскольку s отсрочен в s->f;, и поскольку разыменование нулевого указателя имеет поведение undefined, то s не должно быть нулевым и, следовательно, оптимизирует проверку if (!s) на следующей строке.
Урок состоит в том, что современные оптимизаторы очень агрессивны в использовании поведения undefined и, скорее всего, будут только более агрессивными. Ясно, что с помощью всего лишь нескольких примеров мы видим, что оптимизатор делает вещи, которые кажутся совершенно необоснованными для программиста, но в ретроспективе с точки зрения оптимизаторов имеет смысл.
Ответ 3
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 inlining 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).
Ответ 4
То, что я не могу получить, - это то, почему значение я нарушено этой операцией переполнения?
Кажется, что целочисленное переполнение происходит на 4-й итерации (для i = 3).
signed integer overflow вызывает undefined поведение. В этом случае ничего нельзя предсказать. Цикл может повторять только 4 раз, или он может перейти в бесконечность или что-то еще!
Результат может отличаться от компилятора для компилятора или даже для разных версий одного и того же компилятора.
C11:1.3.24 undefined поведение:
для которого настоящий международный стандарт не налагает требований [Примечание: поведение undefined можно ожидать, если в этом Международном стандарте отсутствует явное определение поведения или когда программа использует ошибочную конструкцию или ошибочные данные. Допустимый диапазон undefined варьируется от полного игнорирования ситуации с непредсказуемыми результатами, ведения во время перевода или выполнения программы документированным образом, характерным для среды (с выдачей диагностического сообщения или без него), до прекращения перевода или выполнение (с выдачей диагностического сообщения). Многие ошибочные программные конструкции не порождают поведение undefined; они должны быть диагностированы. -end note]
Ответ 5
Другой пример этой ошибки, сообщаемой в gcc, - это когда у вас есть цикл, который выполняется для постоянного количества итераций, но вы используете переменную счетчика как индекс в массив, который имеет меньше, чем это количество элементов, например как:
int a[50], x;
for( i=0; i < 1000; i++) x = a[i];
Компилятор может определить, что этот цикл попытается получить доступ к памяти за пределами массива 'a'. Компилятор жалуется на это довольно загадочным сообщением:
Итерация xxu вызывает поведение undefined [-Werror = агрессивные петли-оптимизации]
