Ist die bedingte Bewegungsoptimierung gegen den C-Standard?

Lesezeit: 5 Minuten

Benutzer-Avatar
jahengm

Es ist eine übliche Optimierung, bedingtes Verschieben (assembly cmov), um den bedingten Ausdruck zu optimieren ?: in C. Der C-Standard sagt jedoch:

Der erste Operand wird ausgewertet; Es gibt einen Sequenzpunkt zwischen seiner Auswertung und der Auswertung des zweiten oder dritten Operanden (je nachdem, welcher ausgewertet wird). Der zweite Operand wird nur ausgewertet, wenn der erste ungleich 0 ist; der dritte Operand wird nur ausgewertet, wenn der erste gleich 0 ist; das Ergebnis ist der Wert des zweiten oder dritten Operanden (je nachdem, welcher ausgewertet wird), umgewandelt in den unten beschriebenen Typ.110)

Beispielsweise der folgende C-Code

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int c= a > b ? a + 1 : 2 + b;
    printf("%d", c);
    return 0;
}

wird wie folgt optimierten verwandten ASM-Code generieren:

call    __isoc99_scanf
movl    (%rsp), %esi
movl    4(%rsp), %ecx
movl    $1, %edi
leal    2(%rcx), %eax
leal    1(%rsi), %edx
cmpl    %ecx, %esi
movl    $.LC1, %esi
cmovle  %eax, %edx
xorl    %eax, %eax
call    __printf_chk

Gemäß dem Standard wird für den bedingten Ausdruck nur eine Verzweigung ausgewertet. Aber hier werden beide Zweige ausgewertet, was der Semantik des Standards widerspricht. Ist diese Optimierung gegen den C-Standard? Oder haben viele Compiler-Optimierungen etwas im Widerspruch zum Sprachstandard?

  • Wenn der Compiler beweisen kann, dass das Verhalten gleich ist, kann er natürlich verwenden cmov. Sonst ist es ein Bug.

    – Narr

    21. Mai 2018 um 19:36 Uhr

  • Eine Optimierungstechnik allein kann nicht „gegen den Standard“ sein. Ein Compiler, der eine Optimierungstechnik anwendet, die ein ungültiges Programmverhalten erzeugt, hat einfach einen Fehler.

    – n. 1.8e9-wo-ist-meine-Aktie m.

    21. Mai 2018 um 19:38 Uhr


  • Wie können Sie feststellen, ob 2+b ausgewertet wurde?

    – Benutzer253751

    22. Mai 2018 um 3:55 Uhr

  • @immibis Ich habe den ASM-Code aktualisiert, der nicht mit dem vorherigen C-Code übereinstimmt. Beide werden von der ausgewertet lea Befehl, der effektiv zwei Zahlen addiert (aber keine Bedingungs-Flags setzt).

    – jahengm

    22. Mai 2018 um 5:43 Uhr

  • @manifold: Du verfehlst den Punkt. Wie kann ein konformes C-Programm Nenne den Unterschied? Das Betrachten / Zerlegen des eigenen Maschinencodes gehört nicht zu den Garantien des C-Standards. Dies ist nur eine weitere Art, darauf hinzuweisen, dass die Als-ob-Regel dies zulässt.

    – Peter Cordes

    22. Mai 2018 um 5:45 Uhr


Benutzer-Avatar
Antti Haapala – Слава Україні

Die Optimierung ist legal, aufgrund der „Als-ob-Regel“, dh C11 5.1.2.3p6.

Eine konforme Implementierung ist nur erforderlich, um ein Programm zu erstellen, das beim Ausführen die erzeugt gleich beobachtbares Verhalten wie die Ausführung des Programms unter Verwendung der abstrakten Semantik hervorgebracht hätte. Der Rest des Standards beschreibt nur diese abstrakte Semantik.

Was das kompilierte Programm intern tut, spielt überhaupt keine Rolle, wichtig ist nur, dass es beim Beenden des Programms kein anderes beobachtbares Verhalten hat, außer dem Lesen der a und b und Drucken des Wertes von a + 1 oder b + 2 je nachdem welche a oder bgrößer ist, es sei denn, es tritt etwas auf, das dazu führt, dass das Verhalten undefiniert ist. (Eine fehlerhafte Eingabe führt dazu, dass a, b nicht initialisiert werden und daher auf undefiniert zugreifen; Bereichsfehler und vorzeichenbehafteter Überlauf können ebenfalls auftreten.) Wenn ein undefiniertes Verhalten auftritt, sind alle Wetten ungültig.


Da Zugriffe auf flüchtige Variablen streng nach der abstrakten Semantik ausgewertet werden müssen, können Sie den bedingten Move durch using beseitigen volatile hier:

#include <stdio.h>

int main() {
    volatile int a, b;
    scanf("%d %d", &a, &b);
    int c = a > b ? a + 1 : 2 + b;
    printf("%d", c);
    return 0;
}

kompiliert zu

        call    __isoc99_scanf@PLT
        movl    (%rsp), %edx
        movl    4(%rsp), %eax
        cmpl    %eax, %edx
        jg      .L7
        movl    4(%rsp), %edx
        addl    $2, %edx
.L3:
        leaq    .LC1(%rip), %rsi
        xorl    %eax, %eax
        movl    $1, %edi
        call    __printf_chk@PLT

        [...]

.L7:
        .cfi_restore_state
        movl    (%rsp), %edx
        addl    $1, %edx
        jmp     .L3

von meinem GCC Ubuntu 7.2.0-8ubuntu3.2

  • @ArturBiesiadowski: Guter Punkt: Die Definition von beobachtbar im C-Standard beinhaltet keine Leistung und ist streng auf das beschränkt, was sein kann tragbar beobachtet von einem konformen C-Programm (ohne UB like (char*)my_func), sodass die Überprüfung auf verzweigte/verzweigte Daten durch Profilerstellung mit vorhersehbaren/unvorhersehbaren Daten ausgeschlossen wird (Warum ist es schneller, ein sortiertes Array zu verarbeiten als ein unsortiertes Array?). Aus diesem Grund sind sowohl das Kompilieren mit De-Optimierung im Debug-Modus als auch die vollständige Optimierung (Halten von Dingen in Registern und sogar Auto-Vektorisierung) legal.

    – Peter Cordes

    22. Mai 2018 um 10:12 Uhr


Der C-Standard beschreibt eine abstrakte Maschine, die C-Code ausführt. Ein Compiler kann beliebige Optimierungen durchführen, solange diese Abstraktion nicht verletzt wird, dh ein konformes Programm kann den Unterschied nicht erkennen.

  • Insbesondere solange der 2./3. Operand keine sichtbaren Seiteneffekte hat, kann der Compiler sie immer beide auswerten, ohne dass der Standard in irgendeiner Weise verletzt wird.

    – Matteo Italien

    21. Mai 2018 um 19:41 Uhr


  • Nach der Norm „umfasst die Bewertung eines Ausdrucks im Allgemeinen sowohl Wertberechnungen als auch das Auslösen von Seiteneffekten“. Aber hier generiert der Compiler Code, der diese Berechnung durchführt, während der Standard nur die Auswertung eines Operanden erfordert. Da bin ich verwirrt.

    – jahengm

    21. Mai 2018 um 19:50 Uhr

  • @manifold: Ja, aber aus Sicht der abstrakten Maschine wurde nur eine ausgewertet.

    – Eichel

    21. Mai 2018 um 20:02 Uhr

  • @manifold Das Programm kann nicht sagen, ob es ausgewertet wurde, spielt es also eine Rolle?

    – Benutzer253751

    22. Mai 2018 um 5:50 Uhr

  • @manifold Ja, aber in diesem Fall sind keine Nebenwirkungen zu initiieren, daher wurde in Bezug auf das beobachtbare Verhalten nur eine ausgewertet. In der generierten Assembly findet übrigens auch die eigentliche Berechnung des nicht ausgewerteten Operanden statt, die jedoch nicht beobachtbar ist.

    – Angew ist nicht mehr stolz auf SO

    22. Mai 2018 um 8:50 Uhr

1353760cookie-checkIst die bedingte Bewegungsoptimierung gegen den C-Standard?

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

Privacy policy