Wie Glass eine C#-switch-Anweisung aus einer IL-Sprungtabelle rekonstruiert

Eine C#-switch-Anweisung sieht im Quelltext aus wie eine ordentliche mehrwegige Verzweigung. Unter der Haube ist sie über einen dichten Ganzzahlbereich etwas Interessanteres: eine einzige IL-Anweisung (der switch-Opcode), die eine geordnete Tabelle von Sprungzielen trägt und in konstanter Zeit verteilt, indem sie den switch-Wert als Index verwendet. Es gibt überhaupt keine Vergleiche. Das macht sie schnell, und es macht die Ausgabe eines naiven Dekompilers zu einem Wirrwarr aus gotos und nummerierten Sprungmarken. Das saubere switch (x) { case 10: ... } aus dieser Tabelle zu rekonstruieren, ist ein kleines, in sich geschlossenes Dekompilierungsproblem und ein gutes Prisma dafür, was ein Dekompiler tatsächlich leistet.

Glass.NET ist ein kostenloser .NET-Dekompiler und Assembly-Inspektor mit einer Avalonia-Oberfläche im Visual-Studio-Stil und einem glass-Kommandozeilenwerkzeug. Alles Folgende ist statische Analyse: Es liest die Metadaten und Methodenrümpfe eines Assemblys, das Sie bereits besitzen und zu inspizieren berechtigt sind, und es lädt oder führt das Ziel niemals aus.

Der switch-Opcode ist eine Sprungtabelle

Beginnen wir mit einem dichten switch: Die Fälle bilden einen zusammenhängenden Ganzzahlbereich:

public static string Grade(int score)
{
    switch (score)
    {
        case 10: return "A";
        case 11: return "B";
        case 12: return "C";
        case 13: return "D";
        case 14: return "E";
        default: return "?";
    }
}

Die fünf Fälle laufen von 10 bis 14 ohne Lücken. Roslyn emittiert keine fünf Vergleiche. Es emittiert einen einzigen switch-Opcode, dessen Operand eine Tabelle von fünf Sprungzielen ist, vorangestellt die Arithmetik, die score in einen nullbasierten Index verwandelt:

IL_0000: ldarg.0
IL_0001: ldc.i4.s   10
IL_0003: sub
IL_0004: switch     (IL_001F, IL_0023, IL_0027, IL_002B, IL_002F)
IL_001A: br.s       IL_0033
IL_001F: ldstr      "A"
IL_0021: br.s       IL_0035
IL_0023: ldstr      "B"
IL_0025: br.s       IL_0035
IL_0027: ldstr      "C"
IL_0029: br.s       IL_0035
IL_002B: ldstr      "D"
IL_002D: br.s       IL_0035
IL_002F: ldstr      "E"
IL_0031: br.s       IL_0035
IL_0033: ldstr      "?"
IL_0035: ret

Lesen Sie die switch-Zeile aufmerksam, denn sie ist der ganze Mechanismus. Der Opcode holt eine vorzeichenlose Ganzzahl vom Stack (hier den normalisierten Index) und behandelt sie als Position in der Zielliste. Index 0 verzweigt zu IL_001F, 1 zu IL_0023, 2 zu IL_0027 und so weiter. Ist der Index größer oder gleich 5 (der Anzahl der Einträge), tut der Opcode nichts, und die Ausführung fällt zur unmittelbar folgenden Anweisung IL_001A durch, einem unbedingten br.s zum default-Rumpf bei IL_0033. Eine Anweisung, O(1)-Verteilung und ein eingebautes Durchfallen für default.

Den switch-Wert normalisieren

Die Fälle beginnen bei 10, aber eine Sprungtabelle wird stets ab null indiziert. Diese Lücke schließen die beiden Anweisungen vor dem switch:

ldc.i4.s   10
sub

Der Compiler subtrahiert die kleinste Fallbezeichnung (10) von score. Nun wird score == 10 zu Index 0, score == 11 zu Index 1, bis score == 14 zu Index 4 wird. Die Subtraktion ist auch das, was das Durchfallen beide Enden des default-Bereichs auf einmal behandeln lässt: Ist score gleich 9, ergibt die Subtraktion -1, was als vorzeichenloser Wert 0xFFFFFFFF ist (riesig, mit Sicherheit >= 5), also fällt es zu default durch. Ist score gleich 100, ist das Ergebnis 90, ebenfalls >= 5, dasselbe Durchfallen. Ein einziger vorzeichenloser Vergleich, implizit im Opcode, deckt alles außerhalb des Bereichs in beide Richtungen ab.

Diese Normalisierung ist das Wichtigste, was ein Dekompiler hier richtig machen muss. Die Sprungtabelle verzeichnet Index 0 bis Index 4, aber der Quelltext erwähnte nie 0; er sagte case 10. Um die ursprünglichen Bezeichnungen zu rekonstruieren, muss der Dekompiler die subtrahierte Konstante finden und wieder hinzuaddieren: Fallbezeichnung = Tabellenindex + 10. Übersieht man das sub, ist jeder rekonstruierte Fall um das Minimum verschoben.

Was ein naiver Dekompiler erzeugt

Hält ein Dekompiler beim Kontrollflussgraphen an, ohne das Muster zu erkennen, emittiert er getreulich genau das, was die IL sagt: eine berechnete Verzweigung zu Sprungmarken, die Normalisierung als arithmetischer Ausdruck belassen. Das Ergebnis ist korrekt, aber unlesbar:

// naive, musterunbewusste Ausgabe
int num = score - 10;
switch (num)   // oder schlimmer: eine Kaskade von "if (num == 0) goto IL_001F;"
{
    default: goto IL_0033;
    case 0: goto IL_001F;
    case 1: goto IL_0023;
    case 2: goto IL_0027;
    case 3: goto IL_002B;
    case 4: goto IL_002F;
}
IL_001F: return "A";
IL_0023: return "B";
// ...
IL_0033: return "?";

Das num = score - 10 lässt die Normalisierung durchscheinen, die der Compiler hinzugefügt hat. Die Fälle sind 0..4 statt 10..14 nummeriert. Und die Rümpfe werden per goto zu Sprungmarken erreicht, statt im switch zu sitzen. Es kompiliert und ist korrekt, aber es ähnelt dem Quelltext in nichts.

Wie Glass das saubere switch zurückgewinnt

Glass.NET behandelt die gesamte Sequenz (das Laden, die Subtraktion, den switch-Opcode, das durchfallende br und die Zielrümpfe) als ein einziges erkennbares Idiom und kehrt jeden Schritt um:

1. Die Sprungtabelle lesen. Der switch-Operand ist eine geordnete Liste von Offsets: IL_001F, IL_0023, IL_0027, IL_002B, IL_002F. Index i bildet auf den Rumpf am Offset i ab.
2. Die Normalisierung zurückgewinnen. Glass sieht das ldc.i4.s 10; sub, das den switch-Wert speist, und verzeichnet das subtrahierte Minimum als 10. Die Fallbezeichnung für den Tabellenindex i ist daher i + 10.
3. Das default zuordnen. Die Anweisung unmittelbar nach dem switch ist das Durchfallen (hier br.s IL_0033). Dieser Offset ist der default-Rumpf. Glass faltet auch das implizite Außer-Bereich-Verhalten in default ein, statt eine explizite Bereichsprüfung zu emittieren.
4. Die Rümpfe anhängen. Jeder Ziel-Offset wird zu einem case, dessen Rumpf der geradlinige Code an diesem Offset ist, wobei das abschließende br zum gemeinsamen Ausgang als Ende des Falls erkannt wird.

Die rekonstruierte Ausgabe ist exakt das Original:

public static string Grade(int score)
{
    switch (score)
    {
        case 10: return "A";
        case 11: return "B";
        case 12: return "C";
        case 13: return "D";
        case 14: return "E";
        default: return "?";
    }
}

Kein goto, kein durchscheinendes score - 10, Fälle ab 10 nummeriert, wie geschrieben.

Dünn besetzte switch sind keine Sprungtabellen

Die Sprungtabelle lohnt sich nur, wenn die Fälle dicht liegen. Spreizen Sie sie, und eine Tabelle wäre größtenteils leere Plätze: Ein switch über 1, 1000 und 100000 bräuchte eine Tabelle mit hunderttausend Einträgen, um drei Rümpfe unterzubringen. Also wechselt der Compiler die Strategie. Betrachten Sie:

public static string Classify(int code)
{
    switch (code)
    {
        case 1:    return "low";
        case 1000: return "mid";
        case 100000: return "high";
        default:   return "none";
    }
}

Hier emittiert Roslyn gar keinen switch-Opcode. Stattdessen baut es einen Binärsuchbaum aus Vergleichen, indem es zuerst den mittleren Wert prüft, um die Suche zu halbieren:

IL_0000: ldarg.0
IL_0001: ldc.i4     1000
IL_0006: bgt.un.s   IL_0015        // code > 1000 ? go check the high half
IL_0008: ldarg.0
IL_0009: ldc.i4.1
IL_000A: beq.s      IL_0024        // code == 1 ?
IL_000C: ldarg.0
IL_000D: ldc.i4     1000
IL_0012: beq.s      IL_002A        // code == 1000 ?
IL_0014: br.s       IL_0036        // default
IL_0015: ldarg.0
IL_0016: ldc.i4     100000
IL_001B: beq.s      IL_0030        // code == 100000 ?
IL_0023: br.s       IL_0036        // default
IL_0024: ldstr      "low"
// ... each body returns
IL_0036: ldstr      "none"
IL_0038: ret

Das bgt.un.s an der Spitze teilt den Bereich, und die beq.s-Anweisungen prüfen einzelne Werte. bgt.un (das vorzeichenlose Größer-als) ist derselbe Kniff wie zuvor: Der vorzeichenlose Vergleich lässt eine einzige Verzweigung auch alles unterhalb des Falls auffangen, weshalb Sie .un sogar bei vermeintlich vorzeichenbehafteten int-switch sehen. Für eine größere dünn besetzte Menge wird der Baum tiefer, aber die Form ist immer diese Vergleichsleiter, niemals die Tabelle mit einem einzigen Opcode.

Glass.NET rekonstruiert auch dieses zum identischen switch (code) { case 1: ... case 1000: ... }. Die Arbeit ist anders (keine Tabelle zu lesen, kein Minimum wieder hinzuzuaddieren; Glass muss stattdessen den Binärsuch-Vergleichsbaum erkennen und ihn zu Fallbezeichnungen zusammenfalten), aber die Ausgabe ist in beiden Fällen das saubere C#-switch. Ein realweltliches switch kompiliert oft zu einem Hybrid: dichte Cluster von Bezeichnungen werden zu kleinen Sprungtabellen, und die vereinzelten Ausreißer werden zu beq-Vergleichen, die an den Baum angesetzt sind. Glass bewältigt die gemischte Form, indem es jede Region mit der passenden Strategie rekonstruiert und sie unter einem einzigen switch zusammenführt.

Es mit der glass-CLI ausprobieren

Um irgendetwas davon selbst zu sehen, richten Sie die CLI auf den Typ. Die dekompilierte C#-Ansicht liefert Ihnen das rekonstruierte switch:

glass decompile MyApp.dll --type MyApp.Grading.Scorer

Um die Mechanik darunter zu sehen (den switch-Opcode mit seiner Zielliste, die sub-Normalisierung und das durchfallende br) wechseln Sie für eine einzelne Methode zur IL-Ansicht:

glass decompile MyApp.dll --type MyApp.Grading.Scorer --member Grade --il

Beides nebeneinander zu lesen ist der Punkt. Das C# zeigt Ihnen die Form, die der Autor geschrieben hat; die IL zeigt Ihnen, ob der Compiler eine Sprungtabelle oder eine Vergleichsleiter gewählt hat, um sie umzusetzen. Beide sind statische Lesarten desselben Assemblys (nichts wird geladen oder ausgeführt), was dies zu einer sicheren, legitimen Methode macht, kompilierten Code zu verstehen und zu debuggen, den Sie zu inspizieren berechtigt sind, sei es Ihr eigener Build oder eine Drittanbieter-Bibliothek, von der Sie abhängen.

Fazit

Ein dichtes C#-switch ist keine Kette von ifs, sondern eine Sprungtabelle, verteilt durch einen einzigen switch-IL-Opcode, mit dem switch-Wert normalisiert durch Subtraktion des kleinsten Falls, damit die Tabelle ab null indiziert werden kann, und einem impliziten vorzeichenlosen Bereichs-Durchfallen, das für default einsteht. Ein dünn besetztes switch ist das Gegenteil: eine Binärsuch-Leiter aus beq/bgt.un-Vergleichen. Ein naiver Dekompiler zeigt Ihnen die gotos und die durchscheinende Subtraktion; Glass.NET liest die Tabelle, addiert das subtrahierte Minimum wieder hinzu, ordnet das default-Ziel zu und gibt Ihnen das saubere switch (x) { case 10: ... } zurück, das der Autor tatsächlich geschrieben hat.