Warum wird ein Schalter nicht auf die gleiche Weise optimiert wie verkettet, wenn sonst in c/c++?

Question 1

Die folgende Implementierung von square erzeugt eine Reihe von cmp/je-Anweisungen, wie ich es von einer verketteten if-Anweisung erwarten würde:

int square(int num) {
    if (num == 0){
        return 0;
    } else if (num == 1){
        return 1;
    } else if (num == 2){
        return 4;
    } else if (num == 3){
        return 9;
    } else if (num == 4){
        return 16;
    } else if (num == 5){
        return 25;
    } else if (num == 6){
        return 36;
    } else if (num == 7){
        return 49;
    } else {
        return num * num;
    }
}

Und das Folgende erzeugt eine Datentabelle für die Rückgabe:

int square_2(int num) {
    switch (num){
        case 0: return 0;
        case 1: return 1;
        case 2: return 4;
        case 3: return 9;
        case 4: return 16;
        case 5: return 25;
        case 6: return 36;
        case 7: return 49;
        default: return num * num;
    }
}

Warum ist gcc nicht in der Lage, das obere in das untere zu optimieren?

Demontage als Referenz: https://godbolt.org/z/UP_igi

BEARBEITEN: Interessanterweise generiert MSVC eine Sprungtabelle anstelle einer Datentabelle für den Schalterfall. Und überraschenderweise optimiert clang sie auf das gleiche Ergebnis.

Question 2

Der generierte Code für switch-case verwendet herkömmlicherweise eine Sprungtabelle. In diesem Fall scheint die direkte Rückgabe durch eine Nachschlagetabelle eine Optimierung zu sein, die sich die Tatsache zunutze macht, dass es sich hier in jedem Fall um eine Rückgabe handelt. Obwohl der Standard diesbezüglich keine Garantien gibt, wäre ich überrascht, wenn ein Compiler anstelle einer Sprungtabelle für einen herkömmlichen Switch-Fall eine Reihe von Vergleichen generieren würde.

Jetzt kommen if-else, es ist genau das Gegenteil. Während switch-case wird in konstanter Zeit ausgeführt, unabhängig von der Anzahl der Verzweigungen, if-else ist für eine kleinere Anzahl von Filialen optimiert. Hier würden Sie erwarten, dass der Compiler grundsätzlich eine Reihe von Vergleichen in der Reihenfolge generiert, in der Sie sie geschrieben haben.

Also wenn ich gebraucht hätte if-else da erwarte ich die meisten anrufe square() dafür sein 0 oder 1 und selten für andere Werte, dann könnte das ‘Optimieren’ für eine Tabellensuche tatsächlich dazu führen, dass mein Code langsamer als erwartet ausgeführt wird, was meinen Zweck für die Verwendung von zunichte macht if anstelle einer switch. Obwohl es umstritten ist, denke ich, dass GCC das Richtige tut und Clang bei seiner Optimierung übermäßig aggressiv ist.

Jemand hatte in den Kommentaren einen Link geteilt, wo clang tut diese Optimierung und generiert auf Nachschlagetabellen basierenden Code für if-else auch. Etwas Bemerkenswertes passiert, wenn wir die Anzahl der Fälle mit Clang auf nur zwei (und einen Standardwert) reduzieren. Es generiert wieder identischen Code für if und switch, aber diesmal
schaltet um auf vergleichen und bewegen anstelle des Lookup-Table-Ansatzes für beide. Das bedeutet, dass selbst der Switch-begünstigende Klang weiß, dass das ‘if’-Muster optimaler ist, wenn die Anzahl der Fälle klein ist!

Zusammenfassend lässt sich sagen, dass eine Folge von Vergleichen für if-else und eine Sprungtabelle für switch-case ist das Standardmuster, dem Compiler tendenziell folgen und Entwickler erwarten, wenn sie Code schreiben. In bestimmten Sonderfällen entscheiden sich einige Compiler jedoch möglicherweise dafür, dieses Muster zu durchbrechen, wenn sie der Meinung sind, dass es eine bessere Optimierung bietet. Andere Compiler entscheiden sich möglicherweise trotzdem dafür, sich an das Muster zu halten, auch wenn es scheinbar suboptimal ist, und vertrauen darauf, dass der Entwickler weiß, was er will. Beides sind gültige Ansätze mit ihren eigenen Vor- und Nachteilen.

Question 3

Eine mögliche Begründung ist, dass bei niedrigen Werten von num wahrscheinlicher sind, zum Beispiel immer 0, könnte der generierte Code für den ersten schneller sein. Der generierte Code für den Schalter benötigt für alle Werte die gleiche Zeit.

Vergleicht man die besten Fälle, gem dieser Tisch. Siehe diese Antwort für die Erklärung der Tabelle.

Wenn num == 0, für “if” haben Sie xor, test, je (mit Sprung), ret. Latenz: 1 + 1 + Sprung. xor und test sind jedoch unabhängig, sodass die tatsächliche Ausführungsgeschwindigkeit schneller als 1 + 1 Zyklen wäre.

Wenn num < 7, für “switch” haben Sie mov, cmp, ja (ohne Sprung), mov, ret. Latenz: 2 + 1 + kein Sprung + 2.

Ein Sprungbefehl, der nicht zum Springen führt, ist schneller als einer, der zum Springen führt. Allerdings definiert die Tabelle nicht die Latenz für einen Sprung, daher ist mir nicht klar, welche besser ist. Es ist möglich, dass letzteres immer besser ist und GCC einfach nicht in der Lage ist, es zu optimieren.