Code sans branchement en

À propos de Code sans branchement

Le concept des conditionnels présente jcc, la famille d'instructions qui permettent de brancher selon une condition. Un jcc transfère l'exécution vers un autre point du programme uniquement si sa condition est remplie.

Cependant, les CPU modernes sont rapides et capables d'exécuter de nombreuses instructions en parallèle. Il serait trop coûteux de tout mettre en attente pendant que le CPU attend une vérification de condition au moment de l'exécution.

C'est pourquoi, en interne, le CPU n'attend pas. Il utilise un prédicteur de branchement pour deviner le résultat d'une condition, puis commence à exécuter spéculativement le chemin prédit.

Si la prédiction est correcte, l'exécution se poursuit comme s'il n'y avait pas de branchement. En revanche, si la prédiction est fausse, le CPU doit abandonner le travail effectué sur le chemin prédit et repartir sur le bon.

C'est ce qu'on appelle une erreur de prédiction de branchement, et c'est coûteux, car cela entraîne un délai.

Lorsqu'un branchement est difficile à prédire, ces erreurs de prédiction s'accumulent. Dans ce cas, il est parfois préférable d'éviter complètement le branchement, afin que les mêmes instructions s'exécutent quelle que soit la condition. Le code qui choisit entre des valeurs sans jcc est dit sans branchement.

Il existe plusieurs façons de structurer le code pour qu'il branche moins souvent, ou pour que les branchements qu'il contient soient plus prévisibles. En particulier, le x86-64 fournit deux familles d'instructions couramment utilisées pour écrire du code sans branchement.

Déplacements conditionnels

La famille d'instructions cmovcc copie l'opérande source dans la destination uniquement si une condition précise est remplie. Sinon, la destination reste inchangée.

Le suffixe cc suit la même convention de nommage que dans jcc, avec la même signification :

Les règles sont semblables à celles de jcc :

1. l et g servent aux comparaisons signées ; b et a aux comparaisons non signées.
2. Ajouter e à un suffixe inclut l'égalité.
3. Ajouter n nie la condition.
4. Il existe aussi des variantes qui font référence au drapeau lorsqu'il est activé. Par exemple, cmovz et cmovc.

Prenons la valeur absolue d'un entier signé contenu dans rdi, renvoyée dans rax. Écrite avec jcc, la fonction emprunte l'un de deux chemins :

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

Écrite avec cmovcc, les deux valeurs candidates sont calculées sans condition, et le déplacement conditionnel en choisit une :

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; if rdi >= 0, rax = rdi
                       ; otherwise rax stays = -rdi
    ; now rax = abs(rdi)
    ret

La version sans branchement exécute toujours les mêmes instructions. Il n'y a aucun jcc que le prédicteur puisse deviner.

La destination d'un cmovcc doit être un registre. La source peut être un registre ou un emplacement mémoire, mais pas une valeur immédiate.

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF = 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

Écriture conditionnelle

La famille d'instructions setcc met l'opérande destination à 1 si une condition précise est remplie, et à 0 sinon. La destination est toujours un opérande de 8 bits.

Le suffixe cc suit la même convention de nommage que dans jcc et cmovcc. Par exemple, setz met la destination à 1 si ZF == 1 et à 0 sinon.

Comme la destination fait 8 bits, il est courant de faire suivre setcc d'un movzx lorsqu'une valeur plus large est nécessaire :

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

C'est une tournure courante pour transformer le résultat d'une comparaison en un entier 0 ou 1.

Quand utiliser du code sans branchement

Le code sans branchement n'est pas toujours plus rapide que le code avec branchements. Lorsqu'un branchement est très prévisible, le prédicteur voit juste presque à chaque fois et jcc ne coûte pratiquement rien. Un code sans branchement qui remplace un tel branchement est plus lent, car il exécute toujours les deux calculs candidats.

Un compteur de boucle en est l'exemple canonique. Prenons une fonction qui additionne rsi entiers 64 bits à partir de rdi :

sum_array:
    xor rax, rax
.loop:
    add rax, [rdi]
    add rdi, 8
    dec rsi
    jnz .loop          ; taken on every iteration except the last
    ret

C'est exactement le type de motif que les prédicteurs de branchement gèrent bien, donc le branchement est pratiquement gratuit quel que soit le nombre d'éléments que sum_array traite.

Le code sans branchement est payant lorsque le branchement est difficile à prédire, ou lorsqu'un temps d'exécution constant est nécessaire quelles que soient les entrées.