Почему целочисленное переполнение в x86 с GCC вызывает бесконечный цикл?

Question

Следующий код входит в бесконечный цикл на GCC:

#include <iostream>
using namespace std;

int main(){
    int i = 0x10000000;

    int c = 0;
    do{
        c++;
        i += i;
        cout << i << endl;
    }while (i > 0);

    cout << c << endl;
    return 0;
}

Итак, вот в чем дело: переполнение целыми числами со знаком является технически неопределенным поведением. Но в GCC на x86 реализована целочисленная арифметика с использованием целочисленных инструкций x86, которые переносятся при переполнении.

Следовательно, я ожидал, что это будет связано с переполнением - несмотря на то, что это неопределенное поведение. Но это явно не тот случай. Так что я пропустил?

Я скомпилировал это, используя:

~/Desktop$ g++ main.cpp -O2

Выход GCC:

~/Desktop$ ./a.out
536870912
1073741824
-2147483648
0
0
0

... (infinite loop)

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

Правильный вывод:

~/Desktop$ g++ main.cpp
~/Desktop$ ./a.out
536870912
1073741824
-2147483648
3

Вот некоторые другие варианты:

i *= 2;   //  Also fails and goes into infinite loop.
i <<= 1;  //  This seems okay. It does not enter infinite loop.

Вот вся соответствующая информация о версии:

~/Desktop$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/x86_64-linux-gnu/gcc/x86_64-linux-gnu/4.5.2/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ..

...

Thread model: posix
gcc version 4.5.2 (Ubuntu/Linaro 4.5.2-8ubuntu4) 
~/Desktop$ 

Итак, вопрос: это ошибка в GCC? Или я что-то неправильно понял о том, как GCC обрабатывает целочисленную арифметику?

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

РЕДАКТИРОВАТЬ:

Вот сборка цикла: (если я правильно его распознал)

.L5:
addl    %ebp, %ebp
movl    $_ZSt4cout, %edi
movl    %ebp, %esi
.cfi_offset 3, -40
call    _ZNSolsEi
movq    %rax, %rbx
movq    (%rax), %rax
movq    -24(%rax), %rax
movq    240(%rbx,%rax), %r13
testq   %r13, %r13
je  .L10
cmpb    $0, 56(%r13)
je  .L3
movzbl  67(%r13), %eax
.L4:
movsbl  %al, %esi
movq    %rbx, %rdi
addl    $1, %r12d
call    _ZNSo3putEc
movq    %rax, %rdi
call    _ZNSo5flushEv
cmpl    $3, %r12d
jne .L5

Answer 1

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

Да, на процессорах x86 целые числа обычно переносятся так, как вы ожидаете. Это одно из тех исключений. Компилятор предполагает, что вы не будете вызывать неопределенное поведение, и оптимизирует проверку цикла. Если вы действительно хотите обернуть, пройти -fwrapv в g++ или же gcc при компиляции; это дает вам четко определенную семантику переполнения (с двумя дополнениями), но может снизить производительность.

Answer 2

Все просто: неопределенное поведение - особенно с оптимизацией (-O2) включен - значит все может быть.

Ваш код ведет себя так, как вы ожидали, без -O2 переключатель.

Кстати, с icl и tcc он работает довольно хорошо, но на подобные вещи нельзя полагаться...

Согласно этому, оптимизация gcc фактически использует целочисленное переполнение со знаком. Это будет означать, что "ошибка" является разработкой.

Answer 3

Здесь важно отметить, что программы на C++ написаны для абстрактной машины C++ (которая обычно эмулируется с помощью аппаратных инструкций). Тот факт, что вы компилируете для x86, совершенно не имеет отношения к тому факту, что это имеет неопределенное поведение.

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

Answer 4

Пожалуйста, люди, неопределенное поведение это именно то, неопределенное. Это означает, что все может случиться. На практике (как и в этом случае) компилятор может предположить, что он не будет вызываться, и делать все, что пожелает, если это может сделать код быстрее / меньше. То, что происходит с кодом, который не должен запускаться, является догадкой. Это будет зависеть от окружающего кода (в зависимости от того, что компилятор вполне может генерировать другой код), используемых переменных / констант, флагов компилятора,... О, и компилятор может обновляться и писать один и тот же код по-разному, или вы могли бы получить другой компилятор с другим взглядом на генерацию кода. Или просто получить другую машину, даже другая модель в той же линейке архитектуры вполне может иметь свое собственное неопределенное поведение (посмотрите неопределенные коды операций, некоторые предприимчивые программисты обнаружили, что на некоторых из этих ранних машин иногда делали полезные вещи...), Нет "компилятор дает определенное поведение для неопределенного поведения". Есть области, которые определяются реализацией, и там вы должны быть в состоянии рассчитывать на последовательное поведение компилятора.

Answer 5

i += i;

// переполнение не определено.

С -fwrapv это правильно. -fwrapv

Answer 6

Даже если компилятор должен был указать, что целочисленное переполнение должно рассматриваться как "некритическая" форма неопределенного поведения (как определено в Приложении L), результат целочисленного переполнения должен, при отсутствии конкретного обещания платформы о более конкретном поведении, быть как минимум, рассматривается как "частично неопределенное значение". Согласно таким правилам, добавление 1073741824+1073741824 может произвольно рассматриваться как выход 2147483648 или -2147483648 или любое другое значение, которое было конгруэнтно модулю 2147483648 мод 4294967296, а значения, полученные путем сложения, могут произвольно рассматриваться как любое значение, которое конгруэнтно модулю 0 мод 4294967296.

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