Warum optimiert Clang x * 1.0 weg, aber NICHT x + 0.0?

125

Warum optimiert Clang die Schleife in diesem Code?

#include <time.h>
#include <stdio.h>

static size_t const N = 1 << 27;
static double arr[N] = { /* initialize to zero */ };

int main()
{
    clock_t const start = clock();
    for (int i = 0; i < N; ++i) { arr[i] *= 1.0; }
    printf("%u ms\n", (unsigned)(clock() - start) * 1000 / CLOCKS_PER_SEC);
}

aber nicht die Schleife in diesem Code?

#include <time.h>
#include <stdio.h>

static size_t const N = 1 << 27;
static double arr[N] = { /* initialize to zero */ };

int main()
{
    clock_t const start = clock();
    for (int i = 0; i < N; ++i) { arr[i] += 0.0; }
    printf("%u ms\n", (unsigned)(clock() - start) * 1000 / CLOCKS_PER_SEC);
}

(Markieren als C und C ++, da ich gerne wissen möchte, ob die Antwort für jeden unterschiedlich ist.)

user541686
quelle
2
Welche Optimierungsflags sind aktuell aktiv?
Iwillnotexist Idonotexist
1
@IwillnotexistIdonotexist: Ich habe gerade verwendet -O3, ich weiß nicht, wie ich überprüfen soll, was das aktiviert.
user541686
2
Es wäre interessant zu sehen, was passiert, wenn Sie -ffast-math zur Befehlszeile hinzufügen.
Plugwash
static double arr[N]ist in C nicht erlaubt; constVariablen zählen nicht als konstante Ausdrücke in dieser Sprache
MM
1
[Fügen Sie einen snarky Kommentar darüber ein, dass C nicht C ++ ist, obwohl Sie es bereits aufgerufen haben.]
user253751

Antworten:

164

Der IEEE 754-2008-Standard für Gleitkomma-Arithmetik und der ISO / IEC 10967- Standard für sprachunabhängige Arithmetik (LIA), Teil 1, beantworten, warum dies so ist.

IEEE 754 § 6.3 Das Vorzeichenbit

Wenn entweder eine Eingabe oder ein Ergebnis NaN ist, interpretiert dieser Standard das Vorzeichen eines NaN nicht. Beachten Sie jedoch, dass Operationen an Bitfolgen - copy, negate, abs, copySign - das Vorzeichenbit eines NaN-Ergebnisses angeben, manchmal basierend auf dem Vorzeichenbit eines NaN-Operanden. Das logische Prädikat totalOrder wird auch vom Vorzeichenbit eines NaN-Operanden beeinflusst. Für alle anderen Operationen gibt dieser Standard das Vorzeichenbit eines NaN-Ergebnisses nicht an, selbst wenn nur eine Eingabe NaN vorhanden ist oder wenn die NaN aus einer ungültigen Operation erzeugt wird.

Wenn weder die Eingaben noch das Ergebnis NaN sind, ist das Vorzeichen eines Produkts oder Quotienten das ausschließliche ODER der Vorzeichen der Operanden. Das Vorzeichen einer Summe oder einer Differenz x - y, die als Summe x + (−y) betrachtet wird, unterscheidet sich von höchstens einem der Vorzeichen der Addenden. und das Vorzeichen des Ergebnisses von Konvertierungen, der Quantisierungsoperation, der roundTo-Integral-Operationen und des roundToIntegralExact (siehe 5.3.1) ist das Vorzeichen des ersten oder einzigen Operanden. Diese Regeln gelten auch dann, wenn Operanden oder Ergebnisse Null oder unendlich sind.

Wenn die Summe zweier Operanden mit entgegengesetzten Vorzeichen (oder die Differenz zweier Operanden mit gleichen Vorzeichen) genau Null ist, muss das Vorzeichen dieser Summe (oder Differenz) in allen Rundungsrichtungsattributen außer roundTowardNegative +0 sein. Unter diesem Attribut muss das Vorzeichen einer exakten Nullsumme (oder Differenz) –0 sein. X + x = x - (−x) behält jedoch das gleiche Vorzeichen wie x, auch wenn x Null ist.

Der Fall der Hinzufügung

Unter dem Standardrundungsmodus (Round-to-Nearest, Krawatten-to-Even) , sehen wir , dass x+0.0produziert x, außer wenn xist -0.0: In diesem Fall wir eine Summe von zwei Operanden mit entgegengesetzten Vorzeichen , deren Summe haben gleich Null ist , und § 6.3 Absatz 3 Regeln, die dieser Zusatz erzeugt +0.0.

Da +0.0es nicht bitweise mit dem Original identisch -0.0ist und dies -0.0ein legitimer Wert ist, der als Eingabe auftreten kann, muss der Compiler den Code eingeben, der potenzielle negative Nullen in transformiert +0.0.

Die Zusammenfassung: Im Standardrundungsmodus in x+0.0, wennx

  • ist nicht -0.0 , dann ist xselbst ein akzeptabler Ausgabewert.
  • ist -0.0 , dann muss der Ausgabewert sein +0.0 , der nicht bitweise identisch ist mit -0.0.

Der Fall der Multiplikation

Im Standardrundungsmodus tritt kein solches Problem auf x*1.0. Wenn x:

  • ist immer eine (sub) normale Zahl x*1.0 == x.
  • ist +/- infinity, dann hat das Ergebnis +/- infinitydas gleiche Vorzeichen.
  • ist NaNdann nach

    IEEE 754 § 6.2.3 NaN-Ausbreitung

    Eine Operation, die einen NaN-Operanden zu seinem Ergebnis weitergibt und ein einzelnes NaN als Eingabe hat, sollte ein NaN mit der Nutzlast des eingegebenen NaN erzeugen, wenn es im Zielformat darstellbar ist.

    was bedeutet , dass der Exponent und Mantisse (wenn auch nicht das Zeichen) von NaN*1.0werden empfohlen , um vom Eingang unverändert NaN. Das Zeichen ist gemäß §6.3p1 oben nicht spezifiziert, aber eine Implementierung kann spezifizieren, dass es mit der Quelle identisch ist NaN.

  • ist +/- 0.0, dann ist das Ergebnis ein 0mit seinem Vorzeichenbit XORed mit dem Vorzeichenbit von 1.0, in Übereinstimmung mit §6.3p2. Da das Vorzeichenbit von 1.0ist 0, bleibt der Ausgabewert gegenüber dem Eingang unverändert. Somit ist x*1.0 == xauch dann, wenn xeine (negative) Null ist.

Der Fall der Subtraktion

Im Standardrundungsmodus ist die Subtraktion x-0.0ebenfalls ein No-Op, da sie äquivalent zu ist x + (-0.0). Wenn xja

  • ist NaN, dann gelten §6.3p1 und §6.2.3 ähnlich wie für Addition und Multiplikation.
  • ist +/- infinity, dann hat das Ergebnis +/- infinitydas gleiche Vorzeichen.
  • ist immer eine (sub) normale Zahl x-0.0 == x.
  • ist -0.0, dann haben wir nach §6.3p2 " [...] das Vorzeichen einer Summe oder einer Differenz x - y, die als Summe x + (−y) betrachtet wird, von höchstens einem der Vorzeichen der Addenden; ". Dies zwingt uns, -0.0als Ergebnis von zuzuweisen (-0.0) + (-0.0), da -0.0sich das Vorzeichen von keinem der Addenden unterscheidet, während +0.0sich das Vorzeichen von zwei der Addenden unterscheidet, was gegen diese Klausel verstößt.
  • ist +0.0, dann reduziert sich dies auf den (+0.0) + (-0.0)oben in The Case of Addition betrachteten Additionsfall , der nach §6.3p3 zu geben gilt +0.0.

Da in allen Fällen der Eingabewert als Ausgabe zulässig ist, ist es zulässig, x-0.0ein No-Op und x == x-0.0eine Tautologie zu berücksichtigen .

Wertverändernde Optimierungen

Der IEEE 754-2008 Standard hat das folgende interessante Zitat:

IEEE 754 § 10.4 Wörtliche Bedeutung und wertverändernde Optimierungen

[...]

Die folgenden wertverändernden Transformationen behalten unter anderem die wörtliche Bedeutung des Quellcodes bei:

  • Anwenden der Identitätseigenschaft 0 + x, wenn x nicht Null ist und kein signalisierendes NaN ist und das Ergebnis den gleichen Exponenten wie x hat.
  • Anwenden der Identitätseigenschaft 1 × x, wenn x kein signalisierendes NaN ist und das Ergebnis den gleichen Exponenten wie x hat.
  • Ändern der Nutzlast oder des Vorzeichens eines leisen NaN.
  • [...]

Da alle NaNs und alle Unendlichkeiten denselben Exponenten haben und das korrekt gerundete Ergebnis von x+0.0und x*1.0für endlich xgenau die gleiche Größe hat wie x, ist ihr Exponent der gleiche.

sNaNs

Signalisierende NaNs sind Gleitkomma-Trap-Werte. Dies sind spezielle NaN-Werte, deren Verwendung als Gleitkommaoperand zu einer ungültigen Operationsausnahme (SIGFPE) führt. Wenn eine Schleife, die eine Ausnahme auslöst, optimiert würde, würde sich die Software nicht mehr gleich verhalten.

Wie user2357112 in den Kommentaren ausführt , lässt der C11-Standard das Verhalten der Signalisierung von NaNs ( sNaN) explizit undefiniert , sodass der Compiler davon ausgehen kann, dass sie nicht auftreten und die von ihnen ausgelösten Ausnahmen auch nicht auftreten. Der C ++ 11-Standard lässt die Beschreibung eines Verhaltens zum Signalisieren von NaNs aus und lässt es daher auch undefiniert.

Rundungsmodi

In alternativen Rundungsmodi können sich die zulässigen Optimierungen ändern. Beispielsweise wird im Modus " Rund auf Negativ-Unendlich" die Optimierung x+0.0 -> xzulässig, jedoch x-0.0 -> xverboten.

Um zu verhindern, dass GCC Standardrundungsmodi und -verhalten annimmt, kann das experimentelle Flag -frounding-mathan GCC übergeben werden.

Fazit

Clang und GCC-O3 bleiben auch bei IEEE-754-konform. Dies bedeutet, dass die oben genannten Regeln des IEEE-754-Standards eingehalten werden müssen. x+0.0ist nicht Bit-identisch zu xallen für xunter diesen Regeln, aber x*1.0 so gewählt werden kann : Nämlich, wenn wir

  1. Befolgen Sie die Empfehlung, die Nutzlast xeines NaN unverändert weiterzugeben .
  2. Lassen Sie das Vorzeichenbit eines NaN-Ergebnisses um unverändert * 1.0.
  3. Befolgen Sie die Anweisung, das Vorzeichenbit während eines Quotienten / Produkts zu XOREN , wenn xes sich nicht um ein NaN handelt.

Um die IEEE-754-unsichere Optimierung zu aktivieren (x+0.0) -> x, muss das Flag -ffast-mathan Clang oder GCC übergeben werden.

Iwillnotexist Idonotexist
quelle
2
Vorsichtsmaßnahme: Was ist, wenn es sich um ein signalisierendes NaN handelt? (Ich dachte tatsächlich, dass das irgendwie der Grund gewesen sein könnte, aber ich wusste nicht wirklich wie, also fragte ich.)
user541686
6
@Mehrdad: Anhang F, der (optionale) Teil des C-Standards, der die C-Einhaltung von IEEE 754 spezifiziert, behandelt explizit keine Signalisierungs-NaNs. (C11 F.2.1., Erste Zeile: "Diese Spezifikation definiert nicht das Verhalten der Signalisierung von NaNs.") Implementierungen, die die Konformität mit Anhang F erklären, können mit der Signalisierung von NaNs frei tun, was sie wollen. Der C ++ - Standard hat eine eigene Handhabung von IEEE 754, aber was auch immer es ist (ich bin nicht vertraut), ich bezweifle, dass es auch das NaN-Signalisierungsverhalten spezifiziert.
user2357112 unterstützt Monica
2
@Mehrdad: sNaN ruft gemäß dem Standard undefiniertes Verhalten auf (aber es wird wahrscheinlich von der Plattform gut definiert), sodass das Compashing des Compilers hier zulässig ist.
Joshua
1
@ user2357112: Die Möglichkeit der Fehlerbehebung als Nebeneffekt für ansonsten nicht verwendete Berechnungen beeinträchtigt im Allgemeinen viele Optimierungen. Wenn das Ergebnis einer Berechnung manchmal ignoriert wird, kann ein Compiler die Berechnung sinnvoll verschieben, bis er weiß, ob das Ergebnis verwendet wird. Wenn die Berechnung jedoch ein wichtiges Signal erzeugt hätte, kann dies schlecht sein.
Supercat
2
Oh, schauen Sie, eine Frage, die zu Recht sowohl für C als auch für C ++ gilt und für beide Sprachen durch einen Verweis auf einen einzelnen Standard genau beantwortet wird . Wird dies dazu führen, dass sich Menschen weniger über Fragen beschweren, die sowohl mit C als auch mit C ++ gekennzeichnet sind, selbst wenn es sich um eine Sprachgemeinschaft handelt? Leider denke ich nicht.
Kyle Strand
35

x += 0.0ist kein NOOP wenn xist -0.0. Der Optimierer könnte ohnehin die gesamte Schleife entfernen, da die Ergebnisse jedoch nicht verwendet werden. Im Allgemeinen ist es schwer zu sagen, warum ein Optimierer die Entscheidungen trifft, die er trifft.

user2357112 unterstützt Monica
quelle
2
Ich habe dies tatsächlich gepostet, nachdem ich gerade gelesen hatte, warum x += 0.0es kein No-Op ist, aber ich dachte, dass dies wahrscheinlich nicht der Grund ist, weil die gesamte Schleife so oder so optimiert werden sollte. Ich kann es kaufen, es ist einfach nicht so überzeugend, wie ich gehofft hatte ...
user541686
Angesichts der Neigung objektorientierter Sprachen, Nebenwirkungen hervorzurufen, würde ich mir vorstellen, dass es schwierig ist, sicher zu sein, dass der Optimierer das tatsächliche Verhalten nicht ändert.
Robert Harvey
Könnte der Grund sein, da mit long longder Optimierung in Kraft ist (hat es mit gcc gemacht, das sich mindestens für double gleich verhält )
e2-e4
2
@ ringø: long longist ein integraler Typ, kein IEEE754-Typ.
MSalters
1
Was ist mit x -= 0, ist es das gleiche?
Viktor Mellgren