Ist diese Gleitkommaoptimierung zulässig?

90

Ich habe versucht herauszufinden, wo floatdie Fähigkeit verloren geht, große Ganzzahlen genau darzustellen. Also habe ich diesen kleinen Ausschnitt geschrieben:

int main() {
    for (int i=0; ; i++) {
        if ((float)i!=i) {
            return i;
        }
    }
}

Dieser Code scheint mit allen Compilern außer clang zu funktionieren. Clang erzeugt eine einfache Endlosschleife. Godbolt .

Ist das erlaubt? Wenn ja, handelt es sich um ein QoI-Problem?

geza
quelle
@geza Ich würde mich freuen, die resultierende Nummer zu hören!
Nada
5
gccführt die gleiche Endlosschleifenoptimierung durch, wenn Sie -Ofaststattdessen mit kompilieren , sodass eine Optimierung gccals unsicher eingestuft wird, dies jedoch möglich ist.
12345ieee
3
g ++ generiert auch eine Endlosschleife, optimiert jedoch nicht die Arbeit von innen heraus. Sie können sehen, dass es tut ucomiss xmm0,xmm0, um (float)imit sich selbst zu vergleichen . Das war Ihr erster Hinweis darauf, dass Ihre C ++ - Quelle nicht das bedeutet, was Sie dachten. Wollen Sie behaupten, Sie hätten diese Schleife zum Drucken / Zurückgeben 16777216? Mit welchem ​​Compiler / Version / Optionen war das? Denn das wäre ein Compiler-Bug. gcc optimiert Ihren Code korrekt jnpals Schleifenzweig ( godbolt.org/z/XJYWeu ): Führen Sie eine Schleife durch, solange die Operanden != nicht NaN waren.
Peter Cordes
4
Insbesondere ist dies die -ffast-mathOption, die implizit aktiviert wird und -Ofastes GCC ermöglicht, unsichere Gleitkommaoptimierungen anzuwenden und somit denselben Code wie Clang zu generieren. MSVC verhält sich genauso: Ohne /fp:fastgeneriert es eine Menge Code, der zu einer Endlosschleife führt. mit /fp:fastgibt es eine einzelne jmpAnweisung aus. Ich gehe davon aus, dass diese Compiler, ohne unsichere FP-Optimierungen explizit zu aktivieren, an den IEEE 754-Anforderungen bezüglich NaN-Werten hängen bleiben. Ziemlich interessant, dass Clang das eigentlich nicht tut. Sein statischer Analysator ist besser. @ 12345ieee
Cody Gray
1
@geza: Wenn der Code das tun würde, was Sie beabsichtigt haben, und prüfen würde, ob der mathematische Wert von (float) ivom mathematischen Wert von abweicht i, wäre das Ergebnis (der in der returnAnweisung zurückgegebene Wert ) 16.777.217 und nicht 16.777.216.
Eric Postpischil

Antworten:

49

Wie @Angew hervorhob , benötigt der !=Bediener auf beiden Seiten den gleichen Typ. (float)i != iführt zu einer Förderung der RHS, um auch zu schweben, so haben wir (float)i != (float)i.


g ++ generiert auch eine Endlosschleife, optimiert jedoch nicht die Arbeit von innen heraus. Sie können sehen, dass es int-> float mit konvertiert cvtsi2ssund mit sich selbst ucomiss xmm0,xmm0vergleicht (float)i. (Das war Ihr erster Hinweis darauf, dass Ihre C ++ - Quelle nicht das bedeutet, was Sie für die Antwort von @ Angew gehalten haben.)

x != xist nur wahr, wenn es "ungeordnet" ist, weil xNaN war. ( INFINITYVergleiche in der IEEE-Mathematik gleich, aber NaN nicht. NAN == NANist falsch, NAN != NANist wahr).

gcc7.4 und älter optimiert Ihren Code korrekt jnpals Schleifenzweig ( https://godbolt.org/z/fyOhW1 ): Führen Sie eine Schleife durch, solange die Operanden x != x nicht NaN waren. (gcc8 und höher prüfen auch, ob jedie Schleife unterbrochen wurde, und können nicht optimieren, da dies für alle Nicht-NaN-Eingaben immer der Fall ist.) x86 FP vergleicht den eingestellten PF mit ungeordnet.


Übrigens, das bedeutet, dass die Optimierung von clang auch sicher ist : Es muss nur CSE (float)i != (implicit conversion to float)ials gleich sein und beweisen, dass i -> floates für den möglichen Bereich von niemals NaN ist int.

(Obwohl diese Schleife UB mit vorzeichenbehaftetem Überlauf trifft, darf sie buchstäblich jeden gewünschten Asm ausgeben, einschließlich einer ud2illegalen Anweisung oder einer leeren Endlosschleife, unabhängig davon, was der Schleifenkörper tatsächlich war.) Ignoriert jedoch den UB mit vorzeichenbehaftetem Überlauf ist diese Optimierung noch zu 100% legal.


GCC kann den Schleifenkörper nicht optimieren, selbst wenn der -fwrapvÜberlauf mit vorzeichenbehafteten Ganzzahlen genau definiert ist (als 2er-Komplement-Wraparound). https://godbolt.org/z/t9A8t_

Auch das Aktivieren -fno-trapping-mathhilft nicht. (Die Standardeinstellung von GCC ist leider die Aktivierung
-ftrapping-math, obwohl die Implementierung von GCC fehlerhaft / fehlerhaft ist .) Die Int-> Float-Konvertierung kann eine ungenaue FP-Ausnahme verursachen (für Zahlen, die zu groß sind, um genau dargestellt zu werden). Mit möglicherweise nicht maskierten Ausnahmen ist es daher sinnvoll, dies nicht zu tun Optimieren Sie den Schleifenkörper. (Da die Konvertierung 16777217in Float einen beobachtbaren Nebeneffekt haben kann, wenn die ungenaue Ausnahme nicht maskiert ist.)

Aber mit -O3 -fwrapv -fno-trapping-math, es ist 100% verpasste Optimierung, dies nicht zu einer leeren Endlosschleife zu kompilieren. Ohne #pragma STDC FENV_ACCESS ONist der Status der Sticky-Flags, die maskierte FP-Ausnahmen aufzeichnen, kein beobachtbarer Nebeneffekt des Codes. Nein int-> floatKonvertierung kann zu NaN führen, x != xkann also nicht wahr sein.


Diese Compiler sind alle für C ++ - Implementierungen optimiert, die IEEE 754 Single-Precision (Binary32) floatund 32-Bit verwenden int.

Die Bugfixed-(int)(float)i != i Schleife hätte UB in C ++ - Implementierungen mit schmalem 16-Bit intund / oder breiter float, da Sie vor dem Erreichen der ersten Ganzzahl, die nicht genau als dargestellt werden konnte, den Überlauf UB mit vorzeichenbehafteten Ganzzahlen erreichen würden float.

UB unter einer anderen Reihe von implementierungsdefinierten Auswahlmöglichkeiten hat jedoch keine negativen Konsequenzen beim Kompilieren für eine Implementierung wie gcc oder clang mit dem x86-64 System V ABI.


Übrigens können Sie das Ergebnis dieser Schleife statisch aus FLT_RADIXund berechnen FLT_MANT_DIG, definiert in <climits>. Zumindest können Sie dies theoretisch floattun , wenn es tatsächlich zum Modell eines IEEE-Floats passt und nicht zu einer anderen Art der Darstellung reeller Zahlen wie Posit / Unum.

Ich bin mir nicht sicher, wie sehr sich der ISO C ++ - Standard auf das floatVerhalten auswirkt und ob ein Format, das nicht auf Exponentenfeldern mit fester Breite und Signifikantenfeldern basiert, standardkonform wäre.


In Kommentaren:

@geza Ich würde mich freuen, die resultierende Nummer zu hören!

@nada: Es ist 16777216

Wollen Sie behaupten, Sie hätten diese Schleife zum Drucken / Zurückgeben 16777216?

Update: Da dieser Kommentar gelöscht wurde, denke ich nicht. Wahrscheinlich zitiert das OP nur die floatvor der ersten Ganzzahl, die nicht genau als 32-Bit dargestellt werden kann float. https://en.wikipedia.org/wiki/Single-precision_floating-point_format#Precision_limits_on_integer_values, dh was sie mit diesem fehlerhaften Code überprüfen wollten.

Die Bugfixed-Version würde natürlich drucken 16777217, die erste Ganzzahl, die nicht genau darstellbar ist, und nicht der Wert davor.

(Alle höheren Float-Werte sind exakte Ganzzahlen, aber sie sind Vielfache von 2, dann 4, dann 8 usw. für Exponentenwerte, die höher als die Signifikantenbreite sind. Viele höhere Ganzzahlwerte können dargestellt werden, aber 1 Einheit an letzter Stelle (des Signifikanten) ist größer als 1, es handelt sich also nicht um zusammenhängende ganze Zahlen. Die größte Endlichkeit floatliegt knapp unter 2 ^ 128, was für gerade zu groß ist int64_t.)

Wenn ein Compiler die ursprüngliche Schleife verlassen und diese drucken würde, wäre dies ein Compiler-Fehler.

Peter Cordes
quelle
3
@ SombreroChicken: Nein, ich habe zuerst Elektronik gelernt (aus einigen Lehrbüchern, die mein Vater herumliegen hatte; er war Physikprofessor), dann digitale Logik und bin danach in CPUs / Software eingestiegen. : P Ich habe es immer sehr gemocht, Dinge von Grund auf zu verstehen, oder wenn ich mit einem höheren Level beginne, möchte ich zumindest etwas über das Level darunter lernen, das Einfluss darauf hat, wie / warum die Dinge in dem Level funktionieren, in dem ich bin nachdenken über. (zB wie asm funktioniert und wie man es optimiert, wird durch Einschränkungen des CPU-Designs / CPU-Architektur beeinflusst. Was wiederum aus Physik + Mathematik stammt.)
Peter Cordes
1
GCC ist möglicherweise nicht in der Lage, selbst mit zu optimieren frapw, aber ich bin sicher, dass GCC 10 -ffinite-loopsfür solche Situationen entwickelt wurde.
MCCCS
64

Beachten Sie, dass der integrierte Operator !=verlangt, dass seine Operanden vom gleichen Typ sind, und dies bei Bedarf mithilfe von Promotions und Conversions erreicht. Mit anderen Worten, Ihr Zustand entspricht:

(float)i != (float)i

Das sollte niemals fehlschlagen, und so läuft der Code irgendwann über i, was Ihrem Programm undefiniertes Verhalten verleiht. Jedes Verhalten ist daher möglich.

Um zu überprüfen, was Sie überprüfen möchten, sollten Sie das Ergebnis auf Folgendes zurücksetzen int:

if ((int)(float)i != i)
Angew ist nicht mehr stolz auf SO
quelle
8
@ Džuris Es ist UB. Es gibt kein eindeutiges Ergebnis. Der Compiler erkennt möglicherweise, dass er nur in UB enden kann, und beschließt, die Schleife vollständig zu entfernen.
Fund Monica Klage
4
@opa meinst du static_cast<int>(static_cast<float>(i))? reinterpret_castist offensichtlich UB dort
Caleth
6
@NicHartley: Wollen Sie damit sagen, (int)(float)i != iist UB? Wie schließen Sie das? Ja, es hängt von den durch die Implementierung definierten Eigenschaften ab (da floatIEEE754 binary32 nicht erforderlich ist), aber von jeder Implementierung ist sie gut definiert, es sei denn, sie floatkann alle positiven intWerte genau darstellen , sodass wir einen UB-Überlauf mit vorzeichenbehafteten Ganzzahlen erhalten. ( en.cppreference.com/w/cpp/types/climits definiert FLT_RADIXund FLT_MANT_DIGbestimmt dies). Im Allgemeinen drucken implementierungsdefinierte Dinge, wie std::cout << sizeof(int)ist nicht UB ...
Peter Cordes
2
@Caleth: reinterpret_cast<int>(float)ist nicht genau UB, es ist nur ein Syntaxfehler / schlecht geformt. Es wäre schön, wenn diese Syntax das Typ-Punning von Float intals Alternative zu memcpy(was gut definiert ist) zulässt , aber reinterpret_cast<>nur bei Zeigertypen funktioniert, denke ich.
Peter Cordes
2
@ Peter Nur für NaN, x != xist wahr. Live auf Coliru sehen . Auch in C.
Deduplikator