Warum generiert die Verwendung des ternären Operators zur Rückgabe einer Zeichenfolge einen erheblich anderen Code als die Rückgabe in einem äquivalenten if / else-Block?

71

Ich habe mit dem Compiler Explorer gespielt und bin auf ein interessantes Verhalten mit dem ternären Operator gestoßen, wenn ich so etwas verwendet habe:

std::string get_string(bool b)
{
    return b ? "Hello" : "Stack-overflow";
}

Der vom Compiler generierte Code dafür (Clang Trunk, mit -O3) lautet wie folgt:

get_string[abi:cxx11](bool):                 # @get_string[abi:cxx11](bool)
        push    r15
        push    r14
        push    rbx
        mov     rbx, rdi
        mov     ecx, offset .L.str
        mov     eax, offset .L.str.1
        test    esi, esi
        cmovne  rax, rcx
        add     rdi, 16 #< Why is the compiler storing the length of the string
        mov     qword ptr [rbx], rdi
        xor     sil, 1
        movzx   ecx, sil
        lea     r15, [rcx + 8*rcx]
        lea     r14, [rcx + 8*rcx]
        add     r14, 5 #< I also think this is the length of "Hello" (but not sure)
        mov     rsi, rax
        mov     rdx, r14
        call    memcpy #< Why is there a call to memcpy
        mov     qword ptr [rbx + 8], r14
        mov     byte ptr [rbx + r15 + 21], 0
        mov     rax, rbx
        pop     rbx
        pop     r14
        pop     r15
        ret
.L.str:
        .asciz  "Hello"

.L.str.1:
        .asciz  "Stack-Overflow"

Der vom Compiler generierte Code für das folgende Snippet ist jedoch erheblich kleiner und ohne Aufrufe memcpyund es ist nicht wichtig, die Länge beider Zeichenfolgen gleichzeitig zu kennen. Es gibt 2 verschiedene Bezeichnungen, zu denen gesprungen wird

std::string better_string(bool b)
{
    if (b)
    {
        return "Hello";
    }
    else
    {
        return "Stack-Overflow";
    }
}

Der vom Compiler generierte Code für das obige Snippet (Clang Trunk mit -O3) lautet wie folgt:

better_string[abi:cxx11](bool):              # @better_string[abi:cxx11](bool)
        mov     rax, rdi
        lea     rcx, [rdi + 16]
        mov     qword ptr [rdi], rcx
        test    sil, sil
        je      .LBB0_2
        mov     dword ptr [rcx], 1819043144
        mov     word ptr [rcx + 4], 111
        mov     ecx, 5
        mov     qword ptr [rax + 8], rcx
        ret
.LBB0_2:
        movabs  rdx, 8606216600190023247
        mov     qword ptr [rcx + 6], rdx
        movabs  rdx, 8525082558887720019
        mov     qword ptr [rcx], rdx
        mov     byte ptr [rax + 30], 0
        mov     ecx, 14
        mov     qword ptr [rax + 8], rcx
        ret

Das gleiche Ergebnis ist, wenn ich den ternären Operator verwende mit:

std::string get_string(bool b)
{
    return b ? std::string("Hello") : std::string("Stack-Overflow");
}

Ich möchte wissen, warum der ternäre Operator im ersten Beispiel diesen Compilercode generiert. Ich glaube, dass der Schuldige in der const char[].

PS: GCC ruft strlenim ersten Beispiel an, Clang jedoch nicht.

Link zum Compiler Explorer-Beispiel: https://godbolt.org/z/Exqs6G

Vielen Dank für Ihre Zeit!

Entschuldigung für die Codewand

Marius T.
quelle
18
Der Ergebnistyp des Ternärs ist, const char*während die Zeichenfolgen einzeln const char[N]s sind. Vermutlich könnte der Compiler letztere viel weiter optimieren
kmdreko
2
@kmdreko: Der Compiler weiß immer noch, dass er const char*auf eines von zwei möglichen bekannten konstanten String-Literalen verweist. Deshalb kann clang das strlenin der branchless Version vermeiden . (GCC vermisst diese Optimierung). Selbst die verzweigungslose Version von Clang ist nicht gut optimiert. Es wäre wesentlich besser möglich gewesen, z. B. 2x cmov, um zwischen Konstanten zu wählen, und vielleicht a cmov, um einen Versatz auszuwählen, bei dem gespeichert werden soll. (Beide Versionen können also 2 teilweise überlappende 8-Byte-Speicher ausführen und entweder 8 oder 14 Byte Daten schreiben, einschließlich nachfolgender Nullen.) Das ist besser als das Aufrufen von memcpy.
Peter Cordes
1
Oder da es ohnehin Konstanten aus dem Speicher movdqalädt , verwenden Sie SSE2- Ladevorgänge und verwandeln Sie den Booleschen Wert in eine Vektormaske, um zwischen ihnen auszuwählen. (Diese Optimierung setzt voraus, dass der Compiler weiß, dass es sicher ist, immer 16 Bytes im Retval-Objekt zu speichern, obwohl die C ++ - Quelle wahrscheinlich einige nachgestellte Bytes ungeschrieben lässt. Das Erfinden von Schreibvorgängen ist aus Compilersicherheit im Allgemeinen ein großes No-No für Compiler.)
Peter Cordes

Antworten:

61

Der übergeordnete Unterschied besteht darin, dass die erste Version verzweigungslos ist .

16 ist hier nicht die Länge eines Strings (der längere mit NUL ist nur 15 Bytes lang); Dies ist ein Offset in das Rückgabeobjekt (dessen Adresse in RDI zur Unterstützung von RVO übergeben wird), das angibt, dass die Optimierung für kleine Zeichenfolgen verwendet wird (beachten Sie die fehlende Zuordnung). Die Längen sind 5 oder 5 + 1 + 8, die in R14 gespeichert sind. Diese werden in gespeichert und std::stringan memcpy(zusammen mit einem von CMOVNE ausgewählten Zeiger) übergeben, um die tatsächlichen Zeichenfolgenbytes zu laden.

Die andere Version hat einen offensichtlichen Zweig (obwohl ein Teil der std::stringKonstruktion darüber gehisst wurde) und hat tatsächlich explizit 5 und 14, wird jedoch durch die Tatsache verschleiert, dass die Zeichenfolgenbytes als unmittelbare Werte (ausgedrückt als Ganzzahlen) von enthalten sind verschiedene Größen.

Was den Grund betrifft, warum diese drei äquivalenten Funktionen zwei verschiedene Versionen des generierten Codes erzeugen, kann ich nur anbieten, dass Optimierer iterative und heuristische Algorithmen sind. Sie finden nicht zuverlässig die gleiche „beste“ Baugruppe, unabhängig von ihrem Ausgangspunkt.

Davis Herring
quelle
4
In diesem Fall sollte insbesondere beachtet werden, dass die Optimierung von Speicherschreibvorgängen viel schwieriger ist - selbst wenn dies memcpyintern ein intrinsischer Fehler ist, muss der Optimierer immer noch über die möglichen Nebenwirkungen eines früher oder später auftretenden Schreibvorgangs nachdenken. Im ersten Snippet wird der ternäre Ausdruck ausgewertet und dann erfolgt ein Schreibvorgang, im zweiten erfolgt der Schreibvorgang als Teil der Auswertung des ternären Ausdrucks.
Matthieu M.
2
Ich stimme zu, sollte es nicht , aber wie Sie erwähnen, da Optimierer iterativ und heuristisch sind, ... ist es nicht allzu überraschend, dass dies der Fall ist :)
Matthieu M.
2
Verzweigungslos zu sein ist hier ein roter Hering. Jürgens Antwort ist die richtige. Der Unterschied ist der Typ, für den die Auswahl durchgeführt wird ( std::stringvs. char*) und ob ein Konstruktor mit dem Ergebnis der Auswahl aufgerufen werden muss oder nicht.
cmaster - wieder herstellen Monica
4
@ cmaster-reinstatemonica: Verzweigungslos zu sein ist einfach eine Beschreibung der resultierenden Assembly in einem Fall (was hilfreich ist, um die anderen Unterschiede zu verstehen). Der Konstruktor ist hier in allen Fällen vollständig inline ("zur Kompilierungszeit ausgewertet"); Der Typ des Operanden der return-Anweisung ist in keiner Weise eine Einschränkung für den generierten Code (da keine Adresse eines Zeichenfolgenliterals maskiert wird).
Davis Herring
2
Wenn der Compiler die Konstantwert-Ausbreitungsanalyse bis zum bitteren Ende durchführen konnte, sollte er in allen drei Fällen genau die gleiche Ausgabe generieren. Aber das tut es nicht. Anscheinend hat es diese Analyse nicht beendet. Und offensichtlich wird es durch die Tatsache abgeworfen, dass es im ersten Fall ein einzelnes Objekt mit einem von zwei möglichen Argumenten konstruieren muss, während es in den anderen Fällen die Konstruktion von zwei verschiedenen Objekten auswählen muss. Der Vergleich zwischen dem Verhalten des ersten und des letzten Codebeispiels ist aufschlussreich.
cmaster - wieder herstellen Monica
13

Die erste Version gibt ein Zeichenfolgenobjekt zurück, das mit einem nicht konstanten Ausdruck initialisiert wird, der eines der Zeichenfolgenliterale ergibt. Daher wird der Konstruktor wie für jedes andere variable Zeichenfolgenobjekt ausgeführt, sodass der Memcpy die Initialisierung durchführt.

Die anderen Varianten geben entweder ein mit einem Zeichenfolgenliteral initialisiertes Zeichenfolgenobjekt oder ein anderes mit einem anderen Zeichenfolgenliteral initialisiertes Zeichenfolgenobjekt zurück. Beide können für ein Zeichenfolgenobjekt optimiert werden, das aus einem konstanten Ausdruck erstellt wird, für den kein Memcpy erforderlich ist.

Die eigentliche Antwort lautet also: Die erste Version führt den Operator ?: Für char [] -Ausdrücke aus, bevor die Objekte initialisiert werden, und die anderen Versionen für die bereits initialisierten Zeichenfolgenobjekte.

Es spielt keine Rolle, ob eine der Versionen verzweigungslos ist.

Jürgen
quelle
4
Auch memcpyim verzweigten Asm wurde wirklich nichts gebraucht; Dies ist eine verpasste Optimierung im cmovVergleich zur Verwendung weiterer Anweisungen für Sofortoperanden oder zum Vergleichen von SSE2. Ihre Antwort erklärt jedoch, warum die Quelle den Compiler in die Richtung geführt hat, in die er gegangen ist. Compiler sind alles andere als perfekt.
Peter Cordes
3
Beachten Sie, dass in dem Godbolt Verbindung des OP mit allen drei Versionen unkommentiert, godbolt.org/z/597Kzd , return b ? std::string("Hello") : std::string("Stack-Overflow");compiliert zu einem Zweig mit GCC und Klirren (gleiche wie die ifVersion), trotz der Möglichkeit für konstante Ausbreitungs konst zu machen stringObjekte.
Peter Cordes