Dlaczego przepełnienie całkowitoliczbowe na x86 z GCC powoduje nieskończoną pętlę?

130

Poniższy kod przechodzi w nieskończoną pętlę w 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;
}

Oto umowa: Przepełnienie liczby całkowitej ze znakiem jest technicznie niezdefiniowanym zachowaniem. Ale GCC na x86 implementuje arytmetykę liczb całkowitych przy użyciu instrukcji całkowitych x86 - które zawijają się po przepełnieniu.

Dlatego spodziewałbym się, że zawinie się na przepełnieniu - pomimo tego, że jest to niezdefiniowane zachowanie. Ale tak nie jest. Zatem ... co mnie ominęło?

Skompilowałem to używając:

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

Wyjście GCC:

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

... (infinite loop)

Przy wyłączonych optymalizacjach nie ma nieskończonej pętli, a wyjście jest poprawne. Visual Studio również poprawnie to kompiluje i daje następujący wynik:

Prawidłowe wyjście:

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

Oto kilka innych odmian:

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

Oto wszystkie istotne informacje o wersji:

~/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$

Więc pytanie brzmi: czy to błąd w GCC? A może źle zrozumiałem coś o tym, jak GCC obsługuje arytmetykę liczb całkowitych?

* Oznaczam również to C, ponieważ zakładam, że ten błąd odtworzy się w C. (jeszcze go nie zweryfikowałem).

EDYTOWAĆ:

Oto montaż pętli: (jeśli dobrze ją rozpoznałem)

.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
c++  c  gcc  x86  undefined-behavior 
— Mistyczne
źródło
10
Byłoby to dużo bardziej odpowiedzialne, gdybyś dołączył wygenerowany kod asemblera z gcc -S.
— Greg Hewgill,
Montaż jest zaskakująco długi. Czy nadal mam go edytować?
— Mysticial
Tylko części związane z Twoją pętlą, proszę.
— Greg Hewgill
12
-1. mówisz, że jest to ściśle mówiąc niezdefiniowane zachowanie i pytasz, czy jest to niezdefiniowane zachowanie. więc to nie jest dla mnie prawdziwe pytanie.
— Johannes Schaub - litb
9
@ JohannesSchaub-litb Dzięki za komentarz. Prawdopodobnie złe sformułowanie z mojej strony. Zrobię co w mojej mocy, aby wyjaśnić, w jaki sposób zasłużyć na Twoje głosy nieodebrane (i odpowiednio zmodyfikuję pytanie). Zasadniczo wiem, że to UB. Ale wiem również, że GCC na x86 używa instrukcji całkowitych x86 - które zawijają się przy przepełnieniu. Dlatego spodziewałem się, że się zawinie, mimo że jest to UB. Jednak tak się nie stało i to mnie zdezorientowało. Stąd pytanie.
— Mysticial

Odpowiedzi:

179

Kiedy norma mówi, że jest to niezdefiniowane zachowanie, oznacza to . Wszystko może się zdarzyć. „Wszystko” obejmuje „zwykle zawijają się liczby całkowite, ale czasami zdarzają się dziwne rzeczy”.

Tak, na procesorach x86 liczby całkowite zwykle zawijają się tak, jak się spodziewasz. To jeden z tych wyjątków. Kompilator zakłada, że ​​nie spowoduje to niezdefiniowanego zachowania i optymalizuje test pętli. Jeśli naprawdę chcesz zawinąć, przekaż -fwrapvdo g++lub gccpodczas kompilacji; daje to dobrze zdefiniowaną (uzupełnienie dwóm) semantykę przepełnienia, ale może zaszkodzić wydajności.

— bdonlan
źródło
24
Oh wow. Nie byłam tego świadoma -fwrapv. Dzięki za zwrócenie uwagi.
— Mysticial
1
Czy istnieje opcja ostrzegawcza, która próbuje zauważyć przypadkowe nieskończone pętle?
— Jeff Burdges
5
Znalazłem -Wunsafe-optymalizacje-pętli wspomniane tutaj: stackoverflow.com/questions/2982507/ ...
— Jeff Burdges,
1
-1 „Tak, na procesorach x86 liczby całkowite zwykle zawijają się tak, jak się spodziewasz”. to jest źle. ale to jest subtelne. o ile pamiętam, możliwe jest ich pułapkę na przepełnienie, ale nie o tym tutaj mówimy i nigdy nie widziałem, żeby to się stało. poza tym i pomijając operacje bcd x86 (niedozwolona reprezentacja w C ++) operacje na liczbach całkowitych x86 zawsze zawijają się, ponieważ są dopełnieniem do dwóch. mylisz g ++ wadliwą (lub skrajnie niepraktyczną i bezsensowną) optymalizację dla właściwości operacji x86 integer.
— Pozdrawiam i hth. - Alf
5
@ Cheersandhth.-Alf, przez „na procesorach x86” mam na myśli „kiedy tworzysz dla procesorów x86 przy użyciu kompilatora C”. Czy naprawdę muszę to przeliterować? Oczywiście cała moja mowa o kompilatorach i GCC jest nieistotna, jeśli tworzysz w asemblerze, w którym to przypadku semantyka przepełnienia całkowitoliczbowego jest rzeczywiście bardzo dobrze zdefiniowana.
— bdonlan,
18

To proste: niezdefiniowane zachowanie - zwłaszcza przy -O2włączonej optymalizacji ( ) - oznacza, że wszystko może się zdarzyć.

Twój kod zachowuje się zgodnie z oczekiwaniami bez -O2przełącznika.

Nawiasem mówiąc, działa całkiem dobrze z icl i tcc, ale nie możesz polegać na takich rzeczach ...

Zgodnie z tym optymalizacja gcc w rzeczywistości wykorzystuje przepełnienie liczb całkowitych ze znakiem. Oznaczałoby to, że „błąd” jest z założenia.

— Dennis
źródło
To trochę do bani, że kompilator wybrałby nieskończoną pętlę wszystkich rzeczy dla nieokreślonego zachowania.
— Inverse
27
@Inverse: Nie zgadzam się. Jeśli zakodowałeś coś z nieokreślonym zachowaniem, módl się o nieskończoną pętlę. Ułatwia wykrycie ...
— Dennis,
Chodzi mi o to, że jeśli kompilator aktywnie szuka UB, dlaczego nie wstawić wyjątku zamiast próbować hiperoptymalizować uszkodzony kod?
— Inverse
15
@Inverse: kompilator aktywnie nie szuka niezdefiniowanego zachowania , zakłada, że ​​nie występuje. Pozwala to kompilatorowi na optymalizację kodu. Na przykład zamiast obliczać for (j = i; j < i + 10; ++j) ++k;, po prostu ustawi się k = 10, ponieważ zawsze będzie to prawda, jeśli nie wystąpi przepełnienie ze znakiem.
— Dennis
@Inverse Kompilator niczego nie „wybrał”. Napisałeś pętlę w swoim kodzie. Kompilator tego nie wymyślił.
— Wyścigi lekkości na orbicie
13

Ważną rzeczą do zapamiętania jest to, że programy w C ++ są pisane dla maszyny abstrakcyjnej C ++ (która jest zwykle emulowana za pomocą instrukcji sprzętowych). Fakt, że kompilujesz dla x86, jest całkowicie bez znaczenia dla faktu, że ma to niezdefiniowane zachowanie.

Kompilator może wykorzystać istnienie niezdefiniowanego zachowania, aby ulepszyć swoje optymalizacje (poprzez usunięcie warunku z pętli, jak w tym przykładzie). Nie ma żadnego gwarantowanego, ani nawet użytecznego, mapowania między konstrukcjami poziomu C ++ a konstrukcjami kodu maszynowego na poziomie x86 poza wymogiem, że kod maszynowy po wykonaniu wygeneruje wynik wymagany przez maszynę abstrakcyjną C ++.

— Mankarse
źródło
2

Proszę, ludzie, niezdefiniowane zachowanie jest dokładnie tym, niezdefiniowane . To znaczy, że wszystko może się zdarzyć. W praktyce (jak w tym przypadku) kompilator może założyć, że tak się nie staniebyć wezwanym i rób, co tylko zechcesz, jeśli dzięki temu kod będzie szybszy / mniejszy. Nikt nie zgaduje, co dzieje się z kodem, który nie powinien działać. Będzie to zależeć od otaczającego kodu (w zależności od tego kompilator może wygenerować inny kod), użytych zmiennych / stałych, flag kompilatora, ... Aha, a kompilator może zostać zaktualizowany i napisać ten sam kod inaczej, lub możesz pobierz inny kompilator z innym widokiem na generowanie kodu. Lub po prostu zdobądź inną maszynę, nawet inny model w tej samej linii architektury może mieć swoje własne niezdefiniowane zachowanie (sprawdź niezdefiniowane kody operacyjne, niektórzy przedsiębiorczy programiści odkryli, że na niektórych z tych wczesnych maszyn czasami robili użyteczne rzeczy ...) . Jest ma„kompilator zapewnia określone zachowanie przy niezdefiniowanym zachowaniu”. Są obszary, które są zdefiniowane w ramach implementacji i tam powinieneś być w stanie liczyć na konsekwentne zachowanie kompilatora.

— vonbrand
źródło
1
Tak, wiem bardzo dobrze, co to jest niezdefiniowane zachowanie. Ale kiedy wiesz, jak pewne aspekty języka są zaimplementowane w określonym środowisku, możesz spodziewać się pewnych typów UB, a nie innych. Wiem, że GCC implementuje arytmetykę liczb całkowitych jako arytmetykę liczb całkowitych x86 - co obejmuje przepełnienie. Więc przyjąłem takie zachowanie. Nie spodziewałem się, że GCC zrobi coś innego, jak odpowiedział bdonlan.
— Mysticial
7
Źle. Dzieje się tak, że GCC może założyć, że nie wywołasz niezdefiniowanego zachowania, więc po prostu emituje kod, jakby to się nie mogło zdarzyć. Jeśli tak się stanie, instrukcje robienia tego, o co prosisz, bez niezdefiniowanego zachowania, zostaną wykonane, a rezultatem będzie wszystko, co robi procesor. To znaczy, na x86 robi rzeczy x86. Jeśli jest to inny procesor, mógłby zrobić coś zupełnie innego. Lub kompilator może być wystarczająco inteligentny, aby dowiedzieć się, że wywołujesz niezdefiniowane zachowanie i uruchomić nethack (tak, niektóre starożytne wersje gcc robiły dokładnie to).
— vonbrand
4
Myślę, że źle odczytałeś mój komentarz. Powiedziałem: „Czego się nie spodziewałem” - dlatego zadałem to pytanie w pierwszej kolejności. I nie oczekiwać GCC wyciągnąć żadnych sztuczek.
— Mysticial
1

Nawet jeśli kompilator miałby określić, że przepełnienie całkowitoliczbowe należy uznać za „niekrytyczną” formę niezdefiniowanego zachowania (zgodnie z definicją w załączniku L), wynik przepełnienia liczb całkowitych powinien, w przypadku braku określonej platformy, obiecać bardziej specyficzne zachowanie co najmniej traktowane jako „wartość częściowo nieokreślona”. Zgodnie z takimi zasadami dodanie 1073741824 + 1073741824 można arbitralnie uznać za dające 2147483648 lub -2147483648 lub jakąkolwiek inną wartość, która była zgodna z 2147483648 mod 4294967296, a wartości uzyskane w wyniku dodawania można arbitralnie uznać za dowolną wartość zgodną z 0 mod 4294967296.

Reguły zezwalające na przepełnienie w celu uzyskania „częściowo nieokreślonych wartości” byłyby wystarczająco dobrze zdefiniowane, aby były zgodne z literą i duchem załącznika L, ale nie uniemożliwiałyby kompilatorowi wyciągania tych samych ogólnie użytecznych wniosków, które byłyby uzasadnione, gdyby przepełnienia nie były ograniczone Niezdefiniowane zachowanie. Uniemożliwiłoby to kompilatorowi dokonywanie fałszywych „optymalizacji”, których głównym efektem w wielu przypadkach jest wymaganie od programistów dodania dodatkowego bałaganu do kodu, którego jedynym celem jest zapobieganie takim „optymalizacjom”; czy to byłoby dobre, czy nie, zależy od punktu widzenia.

— supercat
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.