Warum verursacht ein Integer-Überlauf auf x86 mit GCC eine Endlosschleife?

129

Der folgende Code geht auf GCC in eine Endlosschleife:

#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;
}

Also hier ist der Deal: Signierter Integer-Überlauf ist technisch undefiniertes Verhalten. GCC auf x86 implementiert jedoch eine Ganzzahlarithmetik unter Verwendung von x86-Ganzzahlanweisungen, die den Überlauf umbrechen.

Daher hätte ich erwartet, dass es sich um einen Überlauf handelt - trotz der Tatsache, dass es sich um ein undefiniertes Verhalten handelt. Das ist aber eindeutig nicht der Fall. So ... Was habe ich verpasst?

Ich habe dies zusammengestellt mit:

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

GCC-Ausgabe:

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

... (infinite loop)

Bei deaktivierten Optimierungen gibt es keine Endlosschleife und die Ausgabe ist korrekt. Visual Studio kompiliert dies ebenfalls korrekt und liefert das folgende Ergebnis:

Richtige Ausgabe:

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

Hier sind einige andere Variationen:

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

Hier sind alle relevanten Versionsinformationen:

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

Die Frage ist also: Ist das ein Fehler in GCC? Oder habe ich etwas falsch verstanden, wie GCC mit Ganzzahlarithmetik umgeht?

* Ich markiere auch dieses C, da ich davon ausgehe, dass sich dieser Fehler in C reproduziert. (Ich habe ihn noch nicht überprüft.)

BEARBEITEN:

Hier ist die Zusammenstellung der Schleife: (wenn ich sie richtig erkannt habe)

.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
Mystisch
quelle
10
Dies wäre viel verantwortungsbewusster, wenn Sie den generierten Assemblycode von einfügen würden gcc -S.
Greg Hewgill
Die Montage ist überraschend lang. Soll ich es trotzdem bearbeiten?
Mysticial
Bitte nur die Teile, die für Ihre Schleife relevant sind.
Greg Hewgill
12
-1. Sie sagen, dass dies streng genommen undefiniertes Verhalten ist und fragen, ob dies undefiniertes Verhalten ist. Das ist also keine wirkliche Frage für mich.
Johannes Schaub - litb
8
@ JohannesSchaub-litb Danke für den Kommentar. Wahrscheinlich schlechte Formulierung meinerseits. Ich werde mein Bestes geben, um zu klären, wie Sie Ihre Undownvote verdienen können (und ich werde die Frage entsprechend bearbeiten). Grundsätzlich weiß ich, dass es UB ist. Ich weiß aber auch, dass GCC auf x86 x86-Integer-Anweisungen verwendet, die beim Überlauf umbrechen. Daher habe ich erwartet , dass es einwickelt, obwohl es UB ist. Das tat es jedoch nicht und das verwirrte mich. Daher die Frage.
Mysticial

Antworten:

178

Wenn der Standard sagt, dass es sich um undefiniertes Verhalten handelt, bedeutet dies es . Alles kann passieren. "Alles" beinhaltet "normalerweise ganze Zahlen, aber gelegentlich passieren seltsame Dinge".

Ja, auf x86-CPUs werden Ganzzahlen normalerweise so umbrochen, wie Sie es erwarten. Dies ist eine dieser Ausnahmen. Der Compiler geht davon aus, dass Sie kein undefiniertes Verhalten verursachen, und optimiert den Schleifentest. Wenn Sie wirklich eine Umgehung wünschen, übergeben Sie diese -fwrapvan g++oder gccbeim Kompilieren. Dies gibt Ihnen eine genau definierte Überlaufsemantik (Zweierkomplement), kann jedoch die Leistung beeinträchtigen.

bdonlan
quelle
24
Oh wow. Ich war mir nicht bewusst -fwrapv. Vielen Dank für den Hinweis.
Mysticial
1
Gibt es eine Warnoption, die versucht, versehentliche Endlosschleifen zu bemerken?
Jeff Burdges
5
Ich fand -Wunsafe-Loop-Optimierungen hier erwähnt: stackoverflow.com/questions/2982507/…
Jeff Burdges
1
-1 "Ja, auf x86-CPUs werden Ganzzahlen normalerweise so umbrochen, wie Sie es erwarten." das ist falsch. aber es ist subtil. Soweit ich mich erinnere, ist es möglich, sie beim Überlaufen in eine Falle zu locken, aber darüber reden wir hier nicht , und ich habe es noch nie gesehen. anders als das und ohne Berücksichtigung von x86-bcd-Operationen (nicht zulässige Darstellung in C ++) x86-Ganzzahloperationen werden immer umbrochen, da sie zwei sind. Sie verwechseln die fehlerhafte (oder äußerst unpraktische und unsinnige) Optimierung von g ++ mit einer Eigenschaft von x86 Integer Ops.
Prost und hth. - Alf
5
@ Cheersandhth.-Alf, mit 'auf x86-CPUs' meine ich 'wenn Sie für x86-CPUs mit einem C-Compiler entwickeln'. Muss ich es wirklich buchstabieren? Offensichtlich ist mein ganzes Gespräch über Compiler und GCC irrelevant, wenn Sie in Assembler entwickeln. In diesem Fall ist die Semantik für den Ganzzahlüberlauf tatsächlich sehr gut definiert.
Bdonlan
18

Es ist ganz einfach: Undefiniertes Verhalten - insbesondere bei aktivierter Optimierung ( -O2) - bedeutet, dass alles passieren kann.

Ihr Code verhält sich wie erwartet ohne den -O2Schalter.

Es funktioniert übrigens ganz gut mit icl und tcc, aber man kann sich nicht auf solche Sachen verlassen ...

Nach diesem , gcc Optimierungs Exploits Integer - Überlauf tatsächlich unterzeichnet. Dies würde bedeuten, dass der "Fehler" beabsichtigt ist.

Dennis
quelle
Es ist schade, dass sich ein Compiler für eine unendliche Schleife aller Dinge für undefiniertes Verhalten entscheiden würde.
Inverse
27
@Inverse: Ich bin anderer Meinung. Wenn Sie etwas mit undefiniertem Verhalten codiert haben, beten Sie für eine Endlosschleife. Erleichtert das Erkennen ...
Dennis
Ich meine, wenn der Compiler aktiv nach UB sucht, warum nicht eine Ausnahme einfügen, anstatt zu versuchen, fehlerhaften Code zu optimieren?
Inverse
15
@Inverse: Der Compiler sucht nicht aktiv nach undefiniertem Verhalten , sondern geht davon aus, dass es nicht auftritt. Dadurch kann der Compiler den Code optimieren. Anstelle von Computing for (j = i; j < i + 10; ++j) ++k;wird beispielsweise nur festgelegt k = 10, da dies immer dann zutrifft, wenn kein signierter Überlauf auftritt.
Dennis
@Inverse Der Compiler hat sich für nichts "entschieden". Sie haben die Schleife in Ihren Code geschrieben. Der Compiler hat es nicht erfunden.
Leichtigkeitsrennen im Orbit
13

Hierbei ist zu beachten, dass C ++ - Programme für die abstrakte C ++ - Maschine geschrieben werden (die normalerweise über Hardwareanweisungen emuliert wird). Die Tatsache, dass Sie für x86 kompilieren, ist für die Tatsache, dass dies ein undefiniertes Verhalten aufweist, völlig irrelevant.

Dem Compiler steht es frei, das Vorhandensein von undefiniertem Verhalten zu verwenden, um seine Optimierungen zu verbessern (indem eine Bedingung wie in diesem Beispiel aus einer Schleife entfernt wird). Es gibt keine garantierte oder sogar nützliche Zuordnung zwischen Konstrukten auf C ++ - Ebene und Maschinencodekonstrukten auf x86-Ebene, abgesehen von der Anforderung, dass der Maschinencode bei seiner Ausführung das von der abstrakten C ++ - Maschine geforderte Ergebnis liefert.

Mankarse
quelle
5
i += i;

// Der Überlauf ist undefiniert.

Mit -fwrapv ist es richtig. -fwrapv

lostyzd
quelle
3

Bitte Leute, undefiniertes Verhalten ist genau das, undefiniert . Es bedeutet, dass alles passieren könnte. In der Praxis (wie in diesem Fall) kann der Compiler davon ausgehen, dass dies nicht der Fall istaufgerufen werden und tun, was immer es will, wenn dies den Code schneller / kleiner machen könnte. Was mit Code passiert, der nicht ausgeführt werden sollte, ist unklar. Dies hängt vom umgebenden Code ab (abhängig davon kann der Compiler durchaus unterschiedlichen Code generieren), den verwendeten Variablen / Konstanten, den Compiler-Flags, ... Oh, und der Compiler könnte aktualisiert werden und denselben Code anders schreiben, oder Sie könnten Holen Sie sich einen anderen Compiler mit einer anderen Sicht auf die Codegenerierung. Oder holen Sie sich einfach eine andere Maschine, sogar ein anderes Modell in derselben Architekturlinie könnte sehr wohl ein eigenes undefiniertes Verhalten haben (suchen Sie nach undefinierten Opcodes, einige unternehmungslustige Programmierer fanden heraus, dass einige dieser frühen Maschinen manchmal nützliche Dinge taten ...) . Es gibt keine"Der Compiler gibt ein bestimmtes Verhalten bei undefiniertem Verhalten an". Es gibt Bereiche, die implementierungsdefiniert sind, und dort sollten Sie sich darauf verlassen können, dass sich der Compiler konsistent verhält.

vonbrand
quelle
1
Ja, ich weiß sehr gut, was undefiniertes Verhalten ist. Wenn Sie jedoch wissen, wie bestimmte Aspekte der Sprache für eine bestimmte Umgebung implementiert sind, können Sie erwarten, dass bestimmte Arten von UB und nicht andere angezeigt werden. Ich weiß, dass GCC Ganzzahlarithmetik als x86-Ganzzahlarithmetik implementiert - was den Überlauf umschließt. Also nahm ich das Verhalten als solches an. Was ich nicht erwartet hatte, war, dass GCC etwas anderes tun würde, wie bdonlan geantwortet hat.
Mysticial
7
Falsch. Was passiert ist, dass GCC davon ausgehen darf, dass Sie kein undefiniertes Verhalten aufrufen, also nur Code ausgibt, als ob es nicht passieren könnte. Wenn es nicht geschehen, um die Anweisungen zu tun , was Sie verlangen mit keinem undefinierten Verhalten ausgeführt werden soll , und das Ergebnis ist , was die CPU tut. Dh auf x86 macht x86 Sachen. Wenn es sich um einen anderen Prozessor handelt, kann dies etwas völlig anderes bewirken. Oder der Compiler könnte klug genug sein, um herauszufinden, dass Sie undefiniertes Verhalten aufrufen und Nethack starten (ja, einige alte Versionen von gcc haben genau das getan).
vonbrand
4
Ich glaube, Sie haben meinen Kommentar falsch verstanden. Ich sagte: "Was ich nicht erwartet habe" - deshalb habe ich die Frage zuerst gestellt. Ich hatte nicht erwartet, dass GCC irgendwelche Tricks macht.
Mysticial
1

Selbst wenn ein Compiler angeben würde, dass ein Ganzzahlüberlauf als "unkritische" Form des undefinierten Verhaltens (wie in Anhang L definiert) betrachtet werden muss, sollte das Ergebnis eines Ganzzahlüberlaufs ohne ein spezifisches Plattformversprechen eines spezifischeren Verhaltens vorliegen mindestens als "teilweise unbestimmter Wert" angesehen. Nach solchen Regeln könnte das Hinzufügen von 1073741824 + 1073741824 willkürlich als Ergebnis von 2147483648 oder -2147483648 oder einem anderen Wert angesehen werden, der mit 2147483648 mod 4294967296 kongruent ist, und durch Addition erhaltene Werte können willkürlich als jeder Wert angesehen werden, der mit 0 mod 4294967296 kongruent ist.

Regeln, die es einem Überlauf ermöglichen, "teilweise unbestimmte Werte" zu erhalten, wären hinreichend genau definiert, um den Buchstaben und den Geist von Anhang L einzuhalten, würden jedoch einen Compiler nicht daran hindern, dieselben allgemein nützlichen Schlussfolgerungen zu ziehen, die gerechtfertigt wären, wenn Überläufe nicht eingeschränkt wären Undefiniertes Verhalten. Dies würde einen Compiler daran hindern, falsche "Optimierungen" vorzunehmen, deren Hauptwirkung in vielen Fällen darin besteht, dass Programmierer dem Code zusätzliche Unordnung hinzufügen müssen, dessen einziger Zweck darin besteht, solche "Optimierungen" zu verhindern. ob das gut wäre oder nicht, hängt vom eigenen Standpunkt ab.

Superkatze
quelle