Switch lowering in GCC

Introductie

In dit artikel focus ik op GCC. Alle optimalisaties, behalve de bitset lowering, zijn ook van toepassing op Clang. Tenzij anders aangegeven, gebruik ik de optimalisatievlag -O3. Daarnaast heb ik de GCC-code licht bewerkt en bepaalde assertions verwijderd voor de leesbaarheid.

Voorbeelden

Laten we beginnen met een eenvoudig voorbeeld. We hebben een functie die twee integers, x en val, accepteert. Afhankelijk van de waarde van x wordt een corresponderende functie (f0, f1, enzovoort) aangeroepen met val als argument, waarna het resultaat wordt teruggegeven.

Als we dit handmatig zouden implementeren, zouden we een array van functiepointers gebruiken, waarbij de input dient als index voor de array.

int f0(int val);
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);

int compact(int x, int val) {
    switch (x) {
        case 0:
            return f0(val);
        case 1:
            return f1(val);
        case 2:
            return f2(val);
        case 3:
            return f3(val);
        case 4:
            return f4(val);
        default:
            return 0;
    }
    return 0;
}

De resulterende assembly:

compact:
mov	eax, edi
mov	edi, esi
cmp	eax, 4
ja	.L2
jmp	[QWORD PTR .L4[0+rax*8]]
.L4:
.quad	.L8
.quad	.L7
.quad	.L6
.quad	.L5
.quad	.L3
.L5:
jmp	f3
.L3:
jmp	f4
.L8:
jmp	f0
.L7:
jmp	f1
.L6:
jmp	f2
.L2:
xor	eax, eax
ret

De compiler is het eens met deze aanpak en transformeert de switch-statement in een jump table (sprongtabel). Bovendien kan de compiler herkennen wanneer de waarden zijn verschoven met een constante:

int f0(int val);
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);

int compact(int x, int val) {
    switch (x) {
        case 97:
            return f0(val);
        case 98:
            return f1(val);
        case 99:
            return f2(val);
        case 100:
            return f3(val);
        case 101:
            return f4(val);
        default:
            return 0;
    }
    return 0;
}

De resulterende assembly:

compact:
lea	eax, [rdi-97]
cmp	eax, 4
ja	.L2
mov	edi, esi
jmp	[QWORD PTR .L4[0+rax*8]]
.L4:
.quad	.L8
.quad	.L7
.quad	.L6
.quad	.L5
.quad	.L3
.L5:
jmp	f3
.L3:
jmp	f4
.L8:
jmp	f0
.L7:
jmp	f1
.L6:
jmp	f2
.L2:
xor	eax, eax
ret

Onze intuïtie suggereert dat hoe meer verspreid de waarden zijn, hoe minder voordelig de conversie naar een jump table is. Door experimenten merken we dat GCC de drempelwaarde stelt op ongeveer acht jump table-vermeldingen per case label.

In andere woorden: de volgende functie wordt gecompileerd naar een jump table:

int f0(int val);
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);

int compact_7(int x, int val) {
    switch (x) {
        case 0:
            return f0(val);
        case 7:
            return f1(val);
        case 14:
            return f2(val);
        case 21:
            return f3(val);
        case 34:
            return f4(val);
        default:
            return 0;
    }
    return 0;
}

compact_7:
mov	eax, edi
mov	edi, esi
cmp	eax, 34
ja	.L2
jmp	[QWORD PTR .L4[0+rax*8]]
.L4:
.quad	.L8
.quad	.L2
; ...
.quad	.L2
.quad	.L7
.quad	.L2
; ...
.quad	.L2
.quad	.L6
.quad	.L2
; ...
.quad	.L2
.quad	.L5
.quad	.L2
; ...
.quad	.L2
.quad	.L3
.L2:
xor	eax, eax
ret
.L8:
jmp	f0
.L7:
jmp	f1
.L6:
jmp	f2
.L5:
jmp	f3
.L3:
jmp	f4

Maar deze andere functie wordt uitgebreid als een boom van vergelijkingen:

int f0(int val);
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);

int sparse_8(int x, int val) {
    switch (x) {
        case 0:
            return f0(val);
        case 8:
            return f1(val);
        case 16:
            return f2(val);
        case 24:
            return f3(val);
        case 40:
            return f4(val);
        default:
            return 0;
    }
    return 0;
}

sparse_8:
mov	eax, edi
mov	edi, esi
cmp	eax, 16
je	.L2
jle	.L10
cmp	eax, 24
je	.L7
cmp	eax, 40
jne	.L1
jmp	f4
.L10:
test	eax, eax
je	.L4
cmp	eax, 8
jne	.L1
jmp	f1
.L1:
xor	eax, eax
ret
.L4:
jmp	f0
.L7:
jmp	f3
.L2:
jmp	f2

Hier is de visualisatie van de vergelijkingsboom ter verduidelijking:

G
├── ret 0
├── ret 0
├── call f0
├── call f0
├── call f1
├── call f1
├── call f2
├── call f2
├── cmp eax, 24
│   ├── call f3
│   └── call f4
└── cmp eax, 16
    ├── je -> call f2
    └── jle -> test eax, eax
        ├── je -> call f0
        └── cmp eax, 8
            ├── je -> call f1
            └── jne -> ret 0

Enkele observaties:

1. We hebben tot nu toe alleen waarden met gelijke tussenruimtes geprobeerd. Kan de compiler transformaties identificeren die voordelig zijn voor een subset van alle cases?
2. Tot nu toe leidde elke case tot een ander resultaat. Wat als verschillende cases hetzelfde resultaat hebben?
3. De switch in sparse_8 zou vereenvoudigd kunnen worden door x door acht te delen vóór de sprong. Interessant genoeg vindt GCC deze vereenvoudiging niet.

Laten we dieper ingaan op punt 1 en 2.

Uitschieters (Outliers)

Door ons eerste voorbeeld aan te passen door een uitschieter-waarde toe te voegen, zien we dat de compiler in staat is om compacte subsets van cases te herkennen.

int f0(int val);
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);
int f5(int val);

int outlier(int x, int val) {
    switch (x) {
        case 1:
            return f0(val);
        case 2:
            return f1(val);
        case 3:
            return f2(val);
        case 4:
            return f3(val);
        case 5:
            return f4(val);
        case 100:
            return f5(val);
        default:
            return 0;
    }
    return 0;
}

outlier:
mov	eax, edi
mov	edi, esi
cmp	eax, 5
jg	.L2
test	eax, eax
jle	.L1
cmp	eax, 5
ja	.L4
jmp	[QWORD PTR .L6[0+rax*8]]
.L6:
.quad	.L4
.quad	.L4
.quad	.L9
.quad	.L8
.quad	.L7
.quad	.L5
.L2:
cmp	eax, 100
jne	.L1
jmp	f5
.L7:
jmp	f3
.L5:
jmp	f4
.L9:
jmp	f1
.L8:
jmp	f2
.L4:
jmp	f0
.L1:
xor	eax, eax
ret

De compiler genereert een aparte vertakking (branch) voor case 100, maar gebruikt een jump table voor case 1 tot en met 5.

Aaneengesloten waarden (Contiguous)

In onze voorbeelden tot nu toe leidde elke case-statement naar een ander codeblok. Laten we testen wat er gebeurt als meerdere case labels dezelfde functie aanroepen.

int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);
int f5(int val);

int blocks_2(int x, int val) {
    switch (x) {
        case 0:  case 1:  case 2:  case 3:
            return f1(val);
        case 21: // ... case 24:
            return f2(val);
        case 42: // ... case 45:
            return f3(val);
        case 63: // ... case 66:
            return f4(val);
        case 84: // ... case 87:
            return f5(val);
        default:
            return 0;
    }
    return 0;
}

blocks_2:
mov	eax, edi
mov	edi, esi
cmp	eax, 45
jg	.L2
cmp	eax, 41
jg	.L3
cmp	eax, 3
jg	.L4
test	eax, eax
js	.L1
jmp	f1
.L2:
cmp	eax, 66
jg	.L8
cmp	eax, 62
jle	.L1
jmp	f4
.L4:
sub	eax, 21
cmp	eax, 3
ja	.L1
jmp	f2
.L8:
sub	eax, 84
cmp	eax, 3
ja	.L1
jmp	f5
.L3:
jmp	f3
.L1:
xor	eax, eax
ret

We hebben 20 case labels met waarden tussen 0 en 87. De compiler zou deze switch kunnen omzetten naar een jump table met 88 vermeldingen.

Onze hypothese voor de heuristiek is dat een conversie naar een jump table voordelig is wanneer de grootte kleiner is dan 8 * aantalcaselabels. Aangezien $88 < 20 \times 8$, zou de conversie in dit geval voordelig moeten zijn, maar GCC koos ervoor om de switch om te zetten naar een reeks vergelijkingen.

Om te begrijpen waarom, bekijken we een specifiek blok case labels:

int blocks_2(int x, int val) {
    switch (x) {
        // ...
        case 42:  case 43:  case 44:
        case 45:
            return f3(val);
        // ...
    }
    return 0;
}

blocks_2:
mov	eax, edi ; Verplaats `val` naar $eax
mov	edi, esi
cmp	eax, 45
; Als val <= 45, spring dan NIET
jg	.L2
cmp	eax, 41
; Als val >= 42, spring dan naar L3
jg	.L3
; ...
.L2:
; ...
.L3:
; We bereiken L3 alleen als 42 <= val <= 45
jmp	f3        ; Roep f3(val) aan
; ...

De compiler realiseert zich dat de cases aaneengesloten zijn en kan ze implementeren met twee vergelijkingen in plaats van vier. Als de input voor de jump table-heuristiek het aantal vergelijkingen is in plaats van het aantal case labels, klopt het plaatje: we hebben in totaal 10 vergelijkingen. Aangezien $10 \times 8 < 88$, suggereert onze herziene heuristiek dat een jump table transformatie onvoordelig is.

Niet-aaneengesloten waarden (Non-contiguous)

Laten we een niet-aaneengesloten geval proberen.

int f1(int val);
int bittest(int x, int val) {
    switch (x) {
        case '0':  case '2':  case '4':
        case '5':  case '7':  case '9':
        case 'A':  case 'C':  case 'E':
            return f1(x);
        default:
            return 0;
    }
    return 0;
}

bittest:
lea	eax, [rdi-48]
cmp	eax, 21
ja	.L1
mov	edx, 2753205  ; ???
bt	rdx, rax
jc	.L7
.L1:
xor	eax, eax
ret
.L7:
jmp	f1

De compiler genereert niet-intuïtieve machinecode. Waarom zijn er geen cmp-instructies of jump tables? Waar komt de constante 2753205 vandaan?

Een aanwijzing komt van de instructie bt. Volgens de Intel-documentatie doet bt het volgende:

Selecteert het bit in een bitstring (gespecificeerd door het eerste operand, de bit base) op de bitpositie aangeduid door de bit offset (gespecificeerd door het tweede operand) en slaat de waarde van het bit op in de CF-vlag.

Als we de binaire representatie van 2753205 bekijken, zien we dat dit in feite een bitset is. De bits die op één staan, corresponderen met de ASCII-waarden van de case labels, waarbij elke waarde is verminderd met 48.

Implementatie

We zijn verschillende strategieën tegengekomen die GCC gebruikt voor lowering. Voor een dieper begrip kunnen we in de broncode van de compiler duiken.

De compilerpass die verantwoordelijk is voor het vertalen van switch-statements is passlowerswitch, die op zijn beurt analyzeswitchstatement aanroept. Omdat de GCC-broncode complex kan zijn, volgt hier een stapsgewijze versie met commentaar.

bool switch_decision_tree::analyze_switch_statement ()
{
    unsigned l = gimple_switch_num_labels (m_switch);
    auto_vec<cluster *> clusters;
    // ...
    compute_cases_per_edge ();
    /*
       Preamble code. m_switch wijst naar een gimple-object.
       Gimple is de interne representatie die door GCC wordt gebruikt.
       Hieruit halen we het totale aantal cases en het aantal cases per uitgaande edge.
       We alloceren ook een vector om de gekozen lowering-strategie per case label vast te leggen.
    */

    for (unsigned i = 1; i < l; i++)
    {
        tree elt = gimple_switch_label (m_switch, i);
        // ...
        tree low = CASE_LOW (elt);
        tree high = CASE_HIGH (elt);
        profile_probability p
        = case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux));
        clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest, p));
        // ...
    }
    /*
       Meer setup code. We zien dat gimple het concept 'high' en 'low' waarden heeft voor elk label.
       Aaneengesloten case labels zijn in dit stadium al samengevoegd.
       Voor elk case label alloceren we een simple_cluster. Dit dient als record voor het
       bereik van de waarden, de relevante output edge en de waarschijnlijkheid (via PGO).
    */

    // ...
    vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters);
    /* We transformeren de vector van clusters. De naam bit_test_cluster verwijst naar de bitset-strategie. */

    /* Zoek naar jump table clusters.  */
    vec<cluster *> output2;
    auto_vec<cluster *> tmp;
    // ...
    for (unsigned i = 0; i < output.length (); i++) {
        cluster *c = output[i];
        if (c->get_type () != SIMPLE_CASE) {
            if (!tmp.is_empty ()) {
                // ...
                tmp.truncate (0);
            }
            output2.safe_push (c);
        }
        else
            tmp.safe_push (c);
    }
    /*
       Deze sectie allocereert een vector voor de getransformeerde cases en een scratch vector.
       Cases die niet zijn aangepast tijdens de bitset-transformatie worden verzameld in de scratch vector.
       In feite zoeken we hier naar sequenties van case labels die niet naar bitset clusters konden worden omgezet.
    */

    vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
    output2.safe_splice (n);
    n.release ();
    /* We proberen deze opeenvolgende labels om te zetten naar een jump table. */

    /* We kunnen nog een tijdelijke vector hebben om te testen.  */
    if (!tmp.is_empty ()) {
        vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
        output2.safe_splice (n);
        n.release ();
    }

    // ...
    bool expanded = try_switch_expansion (output2);
    release_clusters(output2);
    return expanded;
}

Alles wat overblijft gaat door een laatste pass, die de switch-statement omzet in een beslisboom. Bitsets en jump tables vormen de bladeren van deze boom.

Bitsets

Laten we dieper kijken naar bittestcluster::findbittests. De hoofdstructuur is als volgt:

1. Er wordt geprobeerd de optimale methode te vinden om alle clusters in bitsets te bundelen (minimaliseren van het aantal gebruikte bitsets via dynamisch programmeren).
2. Vervolgens wordt een winstgevigheidsheuristiek toegepast. Voldoen de bitsets aan deze heuristiek, dan wordt een bittestcluster gegenereerd; anders blijven de originele simple_clusters behouden.

vec<cluster *> bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
{
    // ...
    unsigned l = clusters.length ();
    auto_vec<min_cluster_item> min;
    // ...
    min.quick_push (min_cluster_item (0, 0, 0));
    for (unsigned i = 1; i <= l; i++)
    {
        /* Zet minimaal aantal clusters met i-de item op oneindig.  */
        min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
        for (unsigned j = 0; j < i; j++)
        {
            if (min[j].m_count + 1 < min[i].m_count
            && can_be_handled (clusters, j, i - 1))
                min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX);
        }
        gcc_checking_assert (min[i].m_count != INT_MAX);
    }
    /*
       Voor het dynamisch programmeren gebruiken we een vector van min_cluster_item structuren.
       De eerste component registreert hoeveel bitsets nodig zijn voor de eerste i case labels.
       De tweede registreert het begin van de laatste bitset.
    */
    // ...
}

De functie canbehandled controleert of een bereik van labels kan worden omgezet naar een bitset-test op basis van twee criteria:

1. Het gecombineerde bereik van alle case labels moet kleiner zijn dan de breedte van een register (op moderne systemen < 64).
2. De case labels mogen maximaal 3 unieke uitgaande edges hebben.

Vervolgens worden alleen bitsets geconverteerd die de is_beneficial test passeren:

bool bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
{
    return (((uniq == 1 && count >= 3)
    || (uniq == 2 && count >= 5)
    || (uniq == 3 && count >= 6)));
}

Sprongtabellen (Jump Tables)

De logica voor de conversie naar een jump table spiegelt die van de bitset-conversie en maakt eveneens gebruik van dynamisch programmeren.

vec<cluster *> jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
{
    if (!is_enabled ())
        return clusters.copy ();
    unsigned l = clusters.length ();
    auto_vec<min_cluster_item> min;
    min.reserve (l + 1);
    min.quick_push (min_cluster_item (0, 0, 0));

    unsigned HOST_WIDE_INT max_ratio = /* Gebruikt in de hoofdheuristiek */;
    for (unsigned i = 1; i <= l; i++)
    {
        min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
        HOST_WIDE_INT comparison_count = 0;
        for (unsigned k = 0; k <= i - 1; k++)
        {
            simple_cluster *sc = static_cast<simple_cluster *> (clusters[k]);
            comparison_count += sc->get_comparison_count ();
        }
        for (unsigned j = 0; j < i; j++)
        {
            unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
            if (i - j < case_values_threshold ())
                s += i - j;

            if ((min[j].m_count + 1 < min[i].m_count)
            || (min[j].m_count + 1 == min[i].m_count && s < min[i].m_non_jt_cases)
            && can_be_handled (clusters, j, i - 1, max_ratio, comparison_count))
            {
                min[i] = min_cluster_item (min[j].m_count + 1, j, s);
            }
            simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
            comparison_count -= sc->get_comparison_count ();
        }
    }
    // ...
}

Er is een overhead verbonden aan het aanroepen van een jump table vanwege de indirecte sprong en de noodzaak om grenzen te controleren. GCC vereist daarom een minimumaantal case labels om een jump table te genereren.

De max_ratio bepaalt wanneer een jump table voordeliger is dan een beslisboom. Er worden verschillende ratio's gebruikt afhankelijk van de optimalisatievlag:

• Snelheid (-O1, -O2, -O3, -Ofast): Ratio van 8.
• Grootte (-Os): Ratio van 2.

De functie canbehandled controleert uiteindelijk of de ratio tussen het aantal vermeldingen in de jump table en het aantal vergelijkingen binnen de max_ratio valt:

return lhs <= max_ratio * comparison_count;

Ten slotte worden kleine jump tables gepruned via isbeneficial, die controleert of het aantal cases boven de casevalues_threshold ligt (standaard 5 op moderne x64 en Arm64 machines).

Binaire boom (Binary Tree)

Als GCC geen bitset of jump table kan genereren, valt het terug op een binaire boom van vergelijkingen. Bij het genereren van de boom wordt rekening gehouden met de waarschijnlijkheid van elk case label (via PGO of __builtinexpectwith_probability).

void switch_decision_tree::balance_case_nodes (case_tree_node **head, case_tree_node *parent)
{
    case_tree_node *np = *head;
    if (np) {
        // ...
        /* Tel het aantal entries en sommeer de waarschijnlijkheid van alle case labels. */
        while (np) {
            i++;
            prob += np->m_c->m_prob;
            np = np->m_right;
        }

        /* Splits de lijst zodanig dat beide helften een gelijke waarschijnlijkheid hebben. */
        if (i > 2) {
            // ...
            profile_probability pivot_prob = prob.apply_scale (1, 2);
            while (1) {
                prob -= (*npp)->m_c->m_prob;
                if ((prob.initialized_p () && prob < pivot_prob) || ! (*npp)->m_right)
                    break;
                npp = &(*npp)->m_right;
            }
            // ...
            /* Recurseer in beide helften om de binaire boom op te bouwen. */
            balance_case_nodes (&np->m_left, np);
            balance_case_nodes (&np->m_right, np);
            // ...
        } else {
            // Base case
        }
    }
}

Conclusie

We hebben de heuristieken en strategieën bekeken die GCC gebruikt bij het compileren van switch-statements:

• Het comprimeren van meerdere case labels in een bitset.
• Het transformeren van de switch-statement in een jump table.
• Het transformeren van de switch-statement in een binaire beslisboom.

Voor wie dieper in de materie wil duiken, raad ik aan om de GCC-broncode te bestuderen en relevante academische papers over dit onderwerp te lezen.