(A + B + C) ≠ (A + C + B​) und Compiler-Neuordnung

Lesezeit: 10 Minuten

Tals Benutzeravatar
Tal

Das Addieren von zwei 32-Bit-Ganzzahlen kann zu einem Ganzzahlüberlauf führen:

uint64_t u64_z = u32_x + u32_y;

Dieser Überlauf kann vermieden werden, wenn eine der 32-Bit-Ganzzahlen zuerst umgewandelt oder zu einer 64-Bit-Ganzzahl hinzugefügt wird.

uint64_t u64_z = u32_x + u64_a + u32_y;

Wenn der Compiler jedoch beschließt, die Addition neu zu ordnen:

uint64_t u64_z = u32_x + u32_y + u64_a;

Der Integer-Überlauf kann immer noch auftreten.

Dürfen Compiler eine solche Neuordnung vornehmen oder können wir darauf vertrauen, dass sie die Ergebnisinkonsistenz bemerken und die Ausdrucksreihenfolge unverändert beibehalten?

  • Sie zeigen nicht wirklich einen ganzzahligen Überlauf, weil Sie hinzugefügt zu sein scheinen uint32_t Werte – die nicht überlaufen, wickeln sie ein. Das sind keine unterschiedlichen Verhaltensweisen.

    – Martin Bonner unterstützt Monika

    25. Juli 2016 um 9:13 Uhr

  • Siehe Abschnitt 1.9 der C++-Standards, er beantwortet Ihre Frage direkt (es gibt sogar ein Beispiel, das fast genau mit Ihrem übereinstimmt).

    – Holt

    25. Juli 2016 um 9:18 Uhr

  • @Tal: Wie andere bereits gesagt haben: Es gibt keinen Überlauf von Ganzzahlen. Unsigned sind zum Wrapping definiert, für signed ist es ein undefiniertes Verhalten, sodass jede Implementierung ausreicht, einschließlich nasaler Daemons.

    – zu ehrlich für diese Seite

    25. Juli 2016 um 10:22 Uhr

  • @Tal: Unsinn! Wie ich schon geschrieben habe: Der Standard ist sehr klar und erfordert Umbruch, nicht Sättigung (das wäre mit signiert möglich, da das UB ab dem Standard ist.

    – zu ehrlich für diese Seite

    25. Juli 2016 um 11:09 Uhr

  • @rustyx: Ob du Anruf es wickelt oder überläuft, der Punkt bleibt das ((uint32_t)-1 + (uint32_t)1) + (uint64_t)0 ergibt sich 0wohingegen (uint32_t)-1 + ((uint32_t)1 + (uint64_t)0) ergibt sich 0x100000000, und diese beiden Werte sind nicht gleich. Es ist also von Bedeutung, ob der Compiler diese Transformation anwenden kann oder nicht. Aber ja, der Standard verwendet das Wort “Überlauf” nur für vorzeichenbehaftete Ganzzahlen, nicht für vorzeichenlose.

    – Steve Jessop

    25. Juli 2016 um 11:30 Uhr


Benutzeravatar von Klas Lindbäck
Klas Lindbäck

Wenn der Optimierer eine solche Neuordnung durchführt, ist er immer noch an die C-Spezifikation gebunden, sodass eine solche Neuordnung wie folgt aussehen würde:

uint64_t u64_z = (uint64_t)u32_x + (uint64_t)u32_y + u64_a;

Begründung:

Wir beginnen mit

uint64_t u64_z = u32_x + u64_a + u32_y;

Die Addition erfolgt von links nach rechts.

Die Integer-Promotion-Regeln besagen, dass bei der ersten Addition im ursprünglichen Ausdruck u32_x befördert werden uint64_t. In der zweiten Ergänzung u32_y wird auch befördert uint64_t.

Um also mit der C-Spezifikation konform zu sein, muss jeder Optimierer fördern u32_x und u32_y auf 64-Bit-Werte ohne Vorzeichen. Dies entspricht dem Hinzufügen einer Besetzung. (Die eigentliche Optimierung erfolgt nicht auf C-Ebene, aber ich verwende die C-Notation, weil das eine Notation ist, die wir verstehen.)

  • Ist es nicht linksassoziativ, also (u32_x + u32_t) + u64_a ?

    – Nicht zu gebrauchen

    25. Juli 2016 um 9:18 Uhr

  • @Useless: Klas hat alles auf 64 Bit umgestellt. Jetzt spielt die Reihenfolge keine Rolle mehr. Der Compiler muss nicht der Assoziativität folgen, er muss nur genau das gleiche Ergebnis liefern, als ob er es getan hätte.

    – gnasher729

    25. Juli 2016 um 9:19 Uhr

  • Es scheint darauf hinzudeuten, dass der Code von OP so ausgewertet würde, was nicht stimmt.

    – Nicht zu gebrauchen

    25. Juli 2016 um 9:21 Uhr

  • @Klas – bitte erklären warum dies ist der Fall und wie genau kommst du bei deinem Codebeispiel an?

    – rostig

    25. Juli 2016 um 10:00 Uhr

  • @rustyx Es brauchte eine Erklärung. Danke, dass du mich gedrängt hast, einen hinzuzufügen.

    – Klas Lindbäck

    25. Juli 2016 um 10:28 Uhr

Martin Bonner unterstützt Monicas User-Avatar
Martin Bonner unterstützt Monika

Ein Compiler darf nur unter der nachbestellen als ob Regel. Das heißt, wenn die Neuordnung immer das gleiche Ergebnis wie die angegebene Ordnung ergibt, dann ist sie erlaubt. Sonst (wie in deinem Beispiel) nicht.

Zum Beispiel der folgende Ausdruck gegeben

i32big1 - i32big2 + i32small

die sorgfältig konstruiert wurde, um die beiden Werte zu subtrahieren, von denen bekannt ist, dass sie groß, aber ähnlich sind, und nur dann Fügen Sie den anderen kleinen Wert hinzu (um einen Überlauf zu vermeiden), kann der Compiler neu anordnen in:

(i32small - i32big2) + i32big1

und verlassen Sie sich darauf, dass die Zielplattform Zweierkomplement-Arithmetik mit Wrap-Round verwendet, um Probleme zu vermeiden. (Eine solche Neuordnung könnte sinnvoll sein, wenn der Compiler auf Register drückt und zufällig hat i32small bereits in einem Register).

  • Das Beispiel von OP verwendet vorzeichenlose Typen. i32big1 - i32big2 + i32small impliziert signierte Typen. Zusätzliche Bedenken kommen ins Spiel.

    – chux – Wiedereinsetzung von Monica

    25. Juli 2016 um 13:10 Uhr

  • @chux Absolut. Der Punkt, den ich zu machen versuchte, ist, dass ich zwar nicht schreiben konnte (i32small-i32big2) + i32big1(weil es UB verursachen könnte), kann der Compiler es effektiv neu anordnen, weil der Compiler sicher sein kann, dass das Verhalten korrekt sein wird.

    – Martin Bonner unterstützt Monika

    25. Juli 2016 um 13:13 Uhr

  • @chux: Zusätzliche Bedenken wie UB spielen keine Rolle, da es sich um eine Neuordnung des Compilers gemäß der Als-ob-Regel handelt. Ein bestimmter Compiler kann davon profitieren, sein eigenes Überlaufverhalten zu kennen.

    – MSalter

    26. Juli 2016 um 7:15 Uhr

Benutzeravatar von gnasher729
gnasher729

In C, C++ und Objective-C gibt es die „Als-ob“-Regel: Der Compiler darf machen, was er will, solange kein konformes Programm den Unterschied erkennen kann.

In diesen Sprachen ist a + b + c gleichbedeutend mit (a + b) + c. Wenn Sie den Unterschied zwischen diesem und beispielsweise a + (b + c) erkennen können, kann der Compiler die Reihenfolge nicht ändern. Wenn Sie den Unterschied nicht erkennen können, steht es dem Compiler frei, die Reihenfolge zu ändern, aber das ist in Ordnung, da Sie den Unterschied nicht erkennen können.

In Ihrem Beispiel mit b = 64 Bit, a und c 32 Bit könnte der Compiler (b + a) + c oder sogar (b + c) + a auswerten, weil Sie den Unterschied nicht erkennen könnten, aber nicht (a + c) + b, weil Sie den Unterschied erkennen können.

Mit anderen Worten, der Compiler darf nichts tun, was dazu führt, dass sich Ihr Code anders verhält als er sollte. Es ist nicht erforderlich, den Code zu produzieren, von dem Sie denken, dass er produzieren würde oder von dem Sie glauben, dass er produzieren sollte, sondern den Code Wille geben Ihnen genau die Ergebnisse, die es sollte.

  • Aber mit einer großen Einschränkung; es steht dem Compiler frei, kein undefiniertes Verhalten anzunehmen (in diesem Fall Überlauf). Dies ähnelt einer Überlaufprüfung if (a + 1 < a) herausoptimiert werden können.

    – csiz

    25. Juli 2016 um 12:57 Uhr

  • @csiz … an unterzeichnet Variablen. Vorzeichenlose Variablen haben eine wohldefinierte Überlaufsemantik (Wrap-Around).

    – Gavin S. Yancey

    25. Juli 2016 um 14:27 Uhr

Zitat aus der Normen:

[ Note: Operators can be regrouped according to the usual
mathematical rules only where the operators really are associative or
commutative.7 For example, in the following fragment int a, b;

/∗ ... ∗/
a = a + 32760 + b + 5;

the expression statement behaves exactly the same as

a = (((a + 32760) + b) + 5);

due to the associativity and precedence of these operators. Thus, the
result of the sum (a + 32760) is next added to b, and that result is
then added to 5 which results in the value assigned to a. On a machine
in which overflows produce an exception and in which the range of
values representable by an int is [-32768,+32767]kann die Implementierung diesen Ausdruck nicht umschreiben als

a = ((a + b) + 32765);

denn wenn die Werte für a und b jeweils -32754 und -15 wären, würde die Summe a + b eine Ausnahme erzeugen, während der ursprüngliche Ausdruck dies nicht tun würde; der Ausdruck kann auch nicht umgeschrieben werden als

a = ((a + 32765) + b);

oder

a = (a + (b + 32765));

da die Werte für a und b jeweils 4 und -8 oder -17 und 12 gewesen sein könnten. Auf einer Maschine jedoch, in der Überläufe keine Ausnahme erzeugen und in der die Ergebnisse von Überläufen umkehrbar sind, kann die obige Ausdrucksanweisung dies von der Implementierung auf eine der oben genannten Arten neu geschrieben werden, da das gleiche Ergebnis auftreten wird. — Endnote]

Benutzeravatar von Useless
Nicht zu gebrauchen

Dürfen Compiler eine solche Neuordnung vornehmen oder können wir darauf vertrauen, dass sie die Ergebnisinkonsistenz bemerken und die Ausdrucksreihenfolge unverändert beibehalten?

Der Compiler kann nur dann neu ordnen, wenn er das gleiche Ergebnis liefert – hier, wie Sie beobachtet haben, ist dies nicht der Fall.


Es ist möglich, eine Funktionsvorlage zu schreiben, wenn Sie eine möchten, die alle Argumente zu befördert std::common_type vor dem Hinzufügen – dies wäre sicher und würde sich weder auf die Argumentreihenfolge noch auf das manuelle Casting verlassen, aber es ist ziemlich klobig.

  • Ich weiß, dass explizites Casting verwendet werden sollte, aber ich möchte wissen, wie sich der Compiler verhält, wenn ein solches Casting fälschlicherweise weggelassen wurde.

    – Tal

    25. Juli 2016 um 9:26 Uhr

  • Wie gesagt, ohne explizites Casting: Die linke Addition wird zuerst ausgeführt, ohne integrale Beförderung, und unterliegt daher dem Wrapping. Das Ergebnis von diesem Zusatz, möglicherweise verpackt, ist dann befördert zu uint64_t für die Addition zum Wert ganz rechts.

    – Nicht zu gebrauchen

    25. Juli 2016 um 10:30 Uhr

  • Ihre Erklärung zur Als-Ob-Regel ist völlig falsch. Die C-Sprache gibt beispielsweise an, welche Operationen auf einer abstrakten Maschine ausgeführt werden sollen. Die „Als-Ob“-Regel erlaubt ihm, absolut zu tun, was er will, solange niemand den Unterschied erkennen kann.

    – gnasher729

    25. Juli 2016 um 11:07 Uhr

  • Das bedeutet, dass der Compiler tun kann, was er will, solange das Ergebnis dasselbe ist wie das, das durch die gezeigte Linksassoziativität und die arithmetischen Konvertierungsregeln bestimmt wird.

    – Nicht zu gebrauchen

    25. Juli 2016 um 11:25 Uhr


Es hängt von der Bitbreite von ab unsigned/int.

Die folgenden 2 sind nicht gleich (wann unsigned <= 32 Bits). u32_x + u32_y wird 0.

u64_a = 0; u32_x = 1; u32_y = 0xFFFFFFFF;
uint64_t u64_z = u32_x + u64_a + u32_y;
uint64_t u64_z = u32_x + u32_y + u64_a;  // u32_x + u32_y carry does not add to sum.

Sie sind gleich (wann unsigned >= 34 Bits). Ganzzahlige Beförderungen verursacht u32_x + u32_y Hinzufügung bei 64-Bit-Mathematik. Die Reihenfolge ist irrelevant.

Es ist UB (wann unsigned == 33 Bits). Ganzzahlige Beförderungen verursachten eine Addition bei vorzeichenbehafteter 33-Bit-Mathematik und ein vorzeichenbehafteter Überlauf ist UB.

Dürfen Compiler eine solche Neuordnung vornehmen …?

(32-Bit-Mathematik): Neuordnung ja, aber gleiche Ergebnisse müssen auftreten, also nicht das Nachbestellung OP schlägt vor. Unten sind die gleichen

// Same
u32_x + u64_a + u32_y;
u64_a + u32_x + u32_y;
u32_x + (uint64_t) u32_y + u64_a;
...

// Same as each other below, but not the same as the 3 above.
uint64_t u64_z = u32_x + u32_y + u64_a;
uint64_t u64_z = u64_a + (u32_x + u32_y);

… können wir darauf vertrauen, dass sie die Ergebnisinkonsistenz bemerken und die Ausdrucksreihenfolge unverändert beibehalten?

Vertrauen Sie ja, aber das Codierungsziel von OP ist nicht glasklar. Sollte u32_x + u32_y beitragen? Wenn OP diesen Beitrag will, sollte Code sein

uint64_t u64_z = u64_a + u32_x + u32_y;
uint64_t u64_z = u32_x + u64_a + u32_y;
uint64_t u64_z = u32_x + (u32_y + u64_a);

Aber nicht

uint64_t u64_z = u32_x + u32_y + u64_a;

  • Ich weiß, dass explizites Casting verwendet werden sollte, aber ich möchte wissen, wie sich der Compiler verhält, wenn ein solches Casting fälschlicherweise weggelassen wurde.

    – Tal

    25. Juli 2016 um 9:26 Uhr

  • Wie gesagt, ohne explizites Casting: Die linke Addition wird zuerst ausgeführt, ohne integrale Beförderung, und unterliegt daher dem Wrapping. Das Ergebnis von diesem Zusatz, möglicherweise verpackt, ist dann befördert zu uint64_t für die Addition zum Wert ganz rechts.

    – Nicht zu gebrauchen

    25. Juli 2016 um 10:30 Uhr

  • Ihre Erklärung zur Als-Ob-Regel ist völlig falsch. Die C-Sprache gibt beispielsweise an, welche Operationen auf einer abstrakten Maschine ausgeführt werden sollen. Die „Als-Ob“-Regel erlaubt ihm, absolut zu tun, was er will, solange niemand den Unterschied erkennen kann.

    – gnasher729

    25. Juli 2016 um 11:07 Uhr

  • Das bedeutet, dass der Compiler tun kann, was er will, solange das Ergebnis dasselbe ist wie das, das durch die gezeigte Linksassoziativität und die arithmetischen Konvertierungsregeln bestimmt wird.

    – Nicht zu gebrauchen

    25. Juli 2016 um 11:25 Uhr


1421640cookie-check(A + B + C) ≠ (A + C + B​) und Compiler-Neuordnung

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy