Flot de contrôle : if, boucles, switch

Le CPU n’a ni if, ni for, ni switch. Il exécute les instructions l’une après l’autre, et le seul moyen de changer cet ordre est un saut, conditionnel ou non. Chaque instruction structurée du C est un motif de comparaisons et de sauts. Le chapitre sur les indicateurs a montré la brique de base : cmp positionne les indicateurs, un saut conditionnel les lit, et le saut teste en général l’inverse de la condition C, pour sauter par-dessus le bloc « alors ». Ce chapitre assemble ces briques en chacune des structures de contrôle du C, et montre ce qu’en fait un compilateur optimisant. Reconnaître ces formes représente l’essentiel du travail de lecture d’un désassemblage.

if et else

if (cond) A; else B;

devient :

    ; évaluer cond
    j<non cond> else     ; sauter A si la condition est fausse
    A
    jmp end              ; sauter B
else:
    B
end:

Sans else, le jmp end et le bloc else disparaissent. Une chaîne else if n’est qu’un autre if à l’intérieur du bloc else. Dans un désassemblage, un saut conditionnel vers l’avant par-dessus un bloc, suivi d’un saut inconditionnel par-dessus un second bloc, est la signature d’un if/else.

Les boucles

Une boucle est un if dont la dernière instruction remonte. La seule question est où placer le test. Tanenbaum décrit les deux options : le test au début (while, for), qui exécute correctement zéro fois le corps si la condition est fausse d’emblée, et le test à la fin (do … while), qui exécute toujours le corps au moins une fois. Sa figure 5-29 contient une petite erreur : la version avec test à la fin compte i à partir de 1 et reboucle tant que i < n, elle fait donc une itération de moins que la version avec test au début placée à côté, qui en fait n. Il faudrait tester i <= n.

Le compilateur du simulateur, comme clang -O0, compile un for avec le test au début et l’incrément en bas :

Elle renvoie 10. Zoomez jusqu’à l’assembleur pour voir la forme : cmp [i], 4 / jg hors de la boucle en haut, le corps, add [i], 1, et un jmp qui remonte au test. Cela fait deux sauts par itération : le conditionnel en haut, et l’inconditionnel en bas. gcc -O0 fait l’inverse : un jmp direct vers un test placé après le corps, qui remonte tant que la condition est vraie.

Les compilateurs optimisants font pivoter la boucle (loop rotation) pour en économiser un : un seul test avant la boucle pour traiter le cas zéro itération, puis une boucle avec test à la fin. C’est la combinaison que recommande le livre quand le compilateur ne peut pas prouver que la boucle s’exécute au moins une fois. clang -O2 pour for (int i = 0; i < n; i++) work(i); :

loop:
    test edi, edi
    jle  .done            ; n <= 0 : ne pas entrer dans la boucle
    …                     ; sauvegarde des registres, i = 0 dans ebp, n dans ebx
.body:
    mov  edi, ebp
    call work
    inc  ebp              ; i++
    cmp  ebx, ebp
    jne  .body            ; test à la fin : un saut par itération
    …
.done:
    ret

Un saut conditionnel vers l’arrière — vers une adresse plus basse — est la façon de repérer une boucle dans du code machine. Le prédicteur de branchements s’appuie sur le même fait : les branchements vers l’arrière sont en général pris.

break, continue, goto

break est un saut vers l’instruction qui suit la boucle, et continue un saut vers l’incrément ou le test de la boucle. Ils n’ont pas de forme machine particulière, ce qui explique aussi que le C ait un goto : c’est la seule instruction C qui correspond à une seule instruction machine. Il reste utile pour sauter vers un bloc de nettoyage commun en fin de fonction, comme le fait partout le noyau Linux.

Elle renvoie 2 : la boucle s’arrête sur 15, et 23 n’est jamais examiné.

&& et || sont aussi des sauts

En C, a && b n’évalue pas b si a est faux, et a || b n’évalue pas b si a est vrai. C’est l’évaluation en court-circuit, et c’est ce qui rend p != NULL && p->x > 0 sûr. Cela signifie que && et || se compilent en sauts, pas en instruction and ou or. return x >= 10 && x <= 20; devient deux comparaisons, chacune sautant directement à « faux » si elle échoue :

    cmp DWORD PTR [rbp-4], 10
    jl  .false            ; x < 10 : tout le && est faux, sauter le second test
    cmp DWORD PTR [rbp-4], 20
    jg  .false
    mov eax, 1
    jmp .end
.false:
    mov eax, 0

On peut voir le second opérande être sauté :

Il renvoie 2. check(0) && … s’arrête après son premier appel car le côté gauche est faux, et check(1) || … s’arrête après son premier appel car le côté gauche est vrai. Quatre appels sont écrits ; deux s’exécutent.

Quatre façons de compiler un switch

Un switch compare une valeur à de nombreuses constantes. Les compilateurs choisissent entre plusieurs stratégies selon la répartition des valeurs des case — et le choix se voit dans le binaire.

Une chaîne de comparaisons. Pour quelques cas, ou des valeurs très espacées, le compilateur les teste simplement un par un : cmp eax, 1 / je, cmp eax, 100 / je, et ainsi de suite. C’est ce que fait clang -O0 pour les cas 1, 100, 1000 et 10000.

Une table de sauts. Quand les cas sont denses — de 0 à 4, ou de 1 à 6 —, le compilateur construit dans .rodata une table d’adresses de code, une par valeur, et saute à travers elle en une seule étape, quel que soit le nombre de cas. clang le fait même en -O0, et le compilateur du simulateur aussi. Le seuil de gcc dépend de la cible et du niveau d’optimisation : pour le switch à cinq cas ci-dessous, gcc 12 en -O0 pour ARM64 produit encore une chaîne de comparaisons.

Il renvoie 42. Zoomez jusqu’à l’assembleur pour voir la table :

    mov eax, DWORD PTR [rbp-4]     ; k
    cmp eax, 4
    ja  .default                   ; k < 0 ou k > 4 (la comparaison non signée attrape les deux)
    lea rdx, [rip+.table]
    jmp QWORD PTR [rdx+rax*8]      ; sauter à table[k]
    …
.table:
    .quad .case0, .case1, .case2, .case3, .case4

Une astuce mérite d’être remarquée : ja, une comparaison non signée, rejette aussi les valeurs négatives, puisque −1 vu comme non signé vaut 4 294 967 295. Si les cas commencent à 1 au lieu de 0, le compilateur soustrait d’abord 1. Les trous dans l’intervalle pointent vers default. Dans un désassemblage, cette séquence — une vérification de bornes, puis un jmp indirect à travers [table + index × 8] — signifie switch, et la table indique où se trouve chaque cas.

Une recherche dichotomique. Pour des valeurs clairsemées, les compilateurs optimisants trient les cas et les cherchent par dichotomie : clang -O2 compile le switch 1/100/1000/10000 en commençant par cmp edi, 999 / jg, qui coupe les cas en deux, puis teste dans chaque moitié. Cela fait log₂ n comparaisons au lieu de n.

Une table de valeurs. Quand chaque cas renvoie simplement une constante, clang -O2 ne saute pas du tout. Le switch des jours par mois ci-dessous devient une vérification de bornes et un chargement :

int days(int month) {
    switch (month) {
    case 1: return 31;  case 2: return 28;  case 3: return 31;
    case 4: return 30;  case 5: return 31;  case 6: return 30;
    default: return 0;
    }
}

days:
    dec  edi                                  ; month - 1
    xor  eax, eax                             ; par défaut : 0
    cmp  edi, 5
    ja   .done
    mov  eax, DWORD PTR [.table + 4*rdi]      ; table = {31, 28, 31, 30, 31, 30}
.done:
    ret

Parfois, aucun branchement

Les branchements coûtent peu quand ils sont bien prédits, mais un branchement mal prédit coûte une vidange du pipeline, 15 à 20 cycles sur les cœurs actuels. Quand les deux côtés d’un choix sont peu coûteux, les compilateurs optimisants calculent les deux et sélectionnent l’un d’eux, sans saut. return a > b ? a : b; avec clang -O2 :

max:
    mov    eax, esi       ; supposer b
    cmp    edi, esi
    cmovg  eax, edi       ; si a > b, prendre a à la place
    ret

cmovg — déplacement conditionnel si supérieur — lit les indicateurs comme le ferait un saut, mais ne change jamais le flot d’instructions : il n’y a rien à mal prédire. La table de valeurs de days relève de la même idée : transformer du flot de contrôle en flot de données. Pour un rétro-ingénieur, cela signifie qu’un if du source peut apparaître sans aucun saut dans le binaire.

À retenir

• Chaque structure de contrôle du C est faite de comparaisons et de sauts. Le saut teste en général l’inverse de la condition C, pour sauter le bloc qu’elle garde.
• if/else, c’est un saut vers l’avant par-dessus « alors » plus un saut par-dessus « sinon ». Un saut vers l’arrière signale une boucle.
• Les boucles testent au début (while, for) ou à la fin (do … while). Les optimiseurs font pivoter les boucles : un test de garde, puis un test en bas, un seul saut par itération.
• && et || court-circuitent : ils se compilent en sauts, et leur côté droit peut ne jamais s’exécuter.
• Un switch devient une chaîne de comparaisons, une table de sauts (cas denses : vérification de bornes avec ja, puis jmp [table + index × 8]), une recherche dichotomique (cas clairsemés) ou une table de valeurs.
• Les optimiseurs suppriment certains branchements avec cmov et des tables : le code machine peut contenir moins de sauts que le source.