Présentation

Le post analyse la façon dont gcc abaisse les instructions switch sous -O3. Deux stratégies principales apparaissent : la génération d’une jump table (table de sauts) ou la construction d’un arbre de comparaisons. L’article s’appuie sur plusieurs fonctions testées, chacune illustrant un critère de décision propre au compilateur.

Heuristique de conversion en table de sauts

Gcc semble appliquer une règle empirique : une table de sauts est privilégiée lorsque le nombre d’entrées de la table est inférieur à huit fois le nombre d’étiquettes de cas. Dans l’exemple compact, cinq étiquettes (0‑4) entraînent la création d’une table de huit octets, ce qui satisfait 5 < 8 × 5. Le code généré montre un accès direct via 

jmp    [QWORD PTR .L4[0+rax*8]]
après un test de borne cmp eax,4. Même lorsqu’un offset constant est présent (lea eax,[rdi-97]), gcc décale les valeurs et conserve la même table.

En revanche, lorsque la densité chute, la stratégie change. La fonction sparse_8 possède huit étiquettes très dispersées (0, 8, 16, 24, 40) et gcc génère un arbre de comparaisons imbriquées, comme le montre le fragment 

cmp    eax,16
je     .L2
jle    .L10
...
. Le seuil de huit entrées par étiquette n’est plus respecté, la table aurait nécessité 9 entrées, ce qui dépasse la limite heuristique.

Gestion des cas redondants et des sous‑ensembles denses

Lorsque plusieurs étiquettes mappent vers le même bloc, gcc ne crée pas automatiquement une table plus petite. Dans blocks_2, vingt étiquettes couvrent l’intervalle 0‑87. Une table de 88 entrées aurait coûté 88 < 20 × 8, mais le compilateur préfère un arbre de dix comparaisons, car 10 × 8 = 80 reste inférieur à 88. Ainsi, le critère réel semble être comparaisons × 8 plutôt que étiquettes × 8. Le code résultant combine plusieurs tests (cmp eax,45, cmp eax,41, …) avant d’appeler les fonctions cibles.

Dans le cas où plusieurs étiquettes partagent la même cible, gcc ne fusionne pas les entrées de la table. L’exemple outlier montre une table dense pour les valeurs 1‑5, mais un branchement séparé pour l’étiquette 100, illustrant que le compilateur détecte les sous‑ensembles denses et les traite indépendamment.

Optimisation bitset et passage pass_lower_switch

Le cas bittest révèle une optimisation moins intuitive : gcc encode les valeurs admissibles dans un bitset et utilise l’instruction bt pour tester le bit correspondant. Le constant 2753205 (0b001010011111001001010101) représente les caractères ASCII des étiquettes, chaque bit décalé de 48. Le code produit 

lea    eax,[rdi-48]
cmp    eax,21
ja     .L1
mov    edx,2753205
bt     rdx,rax
jc     .L7
, évitant toute table ou chaîne de comparaisons.

Le passage responsable de ces décisions est pass_lower_switch, qui invoque analyze_switch_statement. Il collecte le nombre total d’étiquettes, les plages contiguës, et les probabilités de profilage (uniformes par défaut) afin de choisir entre table, arbre ou bitset. Cette analyse détaillée montre que gcc applique plusieurs heuristiques basées sur la densité, la taille et la redondance des cas, plutôt qu’une simple conversion en table de sauts.