Codice senza rami in

Informazioni su Codice senza rami

Il concetto di condizionali introduce jcc, la famiglia di istruzioni per eseguire salti in base a una condizione. Un jcc trasferisce l'esecuzione a un altro punto del programma solo se la sua condizione è soddisfatta.

Tuttavia, le CPU moderne sono veloci e capaci di eseguire molte istruzioni in parallelo. Sarebbe troppo costoso bloccare tutto il lavoro mentre la CPU aspetta di verificare una condizione a runtime.

Ecco perché, al suo interno, la CPU non aspetta. Usa un predittore di salti per indovinare l'esito di una condizione e inizia a eseguire speculativamente il percorso previsto.

Se la previsione è corretta, l'esecuzione procede come se il salto non ci fosse. Se invece la previsione è sbagliata, la CPU deve scartare il lavoro svolto sul percorso previsto e ricominciare da quello corretto.

Questo fenomeno si chiama previsione errata del salto ed è costoso, perché introduce un ritardo.

Quando un salto è difficile da prevedere, queste previsioni errate si accumulano. In questi casi, a volte è preferibile evitare del tutto il salto, così che vengano eseguite le stesse istruzioni indipendentemente dalla condizione. Il codice che sceglie tra valori senza un jcc si dice senza salti.

Ci sono diversi modi per strutturare il codice in modo che esegua meno salti, o che i salti che esegue siano più prevedibili. In particolare, x86-64 fornisce due famiglie di istruzioni comunemente usate per scrivere codice senza salti.

Spostamenti condizionali

La famiglia di istruzioni cmovcc copia l'operando sorgente nella destinazione solo se una condizione specifica è soddisfatta. Altrimenti, la destinazione resta invariata.

Il suffisso cc segue la stessa nomenclatura di jcc, con lo stesso significato:

Le regole sono simili a quelle di jcc:

1. l e g si usano per i confronti con segno; b e a per quelli senza segno.
2. Aggiungere e a un suffisso include l'uguaglianza.
3. Aggiungere n nega la condizione.
4. Esistono anche varianti che si riferiscono al flag impostato. Per esempio, cmovz e cmovc.

Consideriamo il valore assoluto di un intero con segno in rdi, restituito in rax. Scritta con jcc, la funzione sceglie uno di due percorsi:

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

Scritta con cmovcc, entrambi i valori candidati vengono calcolati incondizionatamente e lo spostamento condizionale ne sceglie uno:

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 versione senza salti esegue sempre le stesse istruzioni. Non c'è alcun jcc che il predittore possa indovinare.

La destinazione di un cmovcc deve essere un registro. La sorgente può essere un registro o una locazione di memoria, ma non un valore immediato.

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

Impostazione condizionale

La famiglia di istruzioni setcc imposta l'operando di destinazione a 1 se una condizione specifica è soddisfatta, e a 0 altrimenti. La destinazione è sempre un operando a 8 bit.

Il suffisso cc segue la stessa nomenclatura di jcc e cmovcc. Per esempio, setz imposta la destinazione a 1 se ZF == 1 e a 0 altrimenti.

Dato che la destinazione è a 8 bit, è comune far seguire setcc da un movzx quando serve un valore più ampio:

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

È un modo di scrivere comune per trasformare il risultato di un confronto in un intero 0 o 1.

Quando usare il codice senza salti

Il codice senza salti non è sempre più veloce di quello con salti. Quando un salto è altamente prevedibile, il predittore ha ragione quasi sempre e un jcc non costa praticamente nulla. Il codice senza salti che sostituisce un salto di questo tipo è più lento, perché esegue sempre entrambi i calcoli candidati.

Un contatore di ciclo è l'esempio canonico. Consideriamo una funzione che somma rsi interi a 64 bit a partire da 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

Questo è esattamente il tipo di schema che i predittori di salti gestiscono bene, quindi il salto non costa praticamente nulla, indipendentemente da quanti elementi elabora sum_array.

Il codice senza salti conviene quando il salto è difficile da prevedere, o quando serve una temporizzazione costante indipendentemente dagli input.