Código sem ramificações em

Sobre Código sem ramificações

O conceito de condicionais apresenta o jcc, a família de instruções para desviar com base em uma condição. Uma jcc transfere a execução para outro ponto do programa apenas se a condição dela for satisfeita.

No entanto, as CPUs modernas são rápidas e capazes de executar muitas instruções em paralelo. Seria custoso demais parar todo o trabalho enquanto a CPU espera por uma verificação de condição em tempo de execução.

É por isso que, internamente, a CPU não espera. Ela usa um preditor de desvio para adivinhar o resultado de uma condição e começa a executar especulativamente o caminho previsto.

Se a predição estiver correta, a execução segue como se não houvesse desvio. No entanto, se a predição estiver errada, a CPU precisa descartar o trabalho feito no caminho previsto e recomeçar no caminho correto.

Isso se chama erro de predição de desvio e é caro, causando um atraso.

Quando um desvio é difícil de prever, esses erros de predição se acumulam. Nesses casos, às vezes é preferível evitar o desvio por completo, para que as mesmas instruções sejam executadas independentemente da condição. O código que escolhe entre valores sem usar uma jcc é chamado de código sem desvios.

Existem várias maneiras de estruturar o código para que ele desvie com menos frequência, ou para que os desvios que ele tem sejam mais previsíveis. Em particular, o x86-64 oferece duas famílias de instruções usadas com frequência para escrever código sem desvios.

Movimentos condicionais

A família de instruções cmovcc copia o operando de origem para o destino apenas se uma condição específica for satisfeita. Caso contrário, o destino permanece inalterado.

O sufixo cc segue a mesma nomenclatura de jcc, com o mesmo significado:

As regras são parecidas com as de jcc:

1. l e g são usados para comparações com sinal; b e a são usados para comparações sem sinal.
2. Adicionar e a um sufixo inclui a igualdade.
3. Adicionar n nega a condição.
4. Também existem variantes que se referem à flag definida. Por exemplo, cmovz e cmovc.

Considere o valor absoluto de um inteiro com sinal em rdi, retornado em rax. Escrita com jcc, a função escolhe um de dois caminhos:

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

Escrita com cmovcc, os dois valores candidatos são calculados incondicionalmente e o movimento condicional escolhe um:

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

A versão sem desvios sempre executa as mesmas instruções. Não há nenhuma jcc para o preditor adivinhar.

O destino de uma cmovcc precisa ser um registrador. A origem pode ser um registrador ou um endereço de memória, mas não um valor imediato.

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

Atribuição condicional

A família de instruções setcc define o operando de destino como 1 se uma condição específica for satisfeita, e como 0 caso contrário. O destino é sempre um operando de 8 bits.

O sufixo cc segue a mesma nomenclatura de jcc e cmovcc. Por exemplo, setz define o destino como 1 se ZF == 1 e como 0 caso contrário.

Como o destino tem 8 bits, é comum usar movzx depois de setcc quando um valor mais largo é necessário:

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

Esse é um idioma comum para transformar o resultado de uma comparação no inteiro 0 ou 1.

Quando usar código sem desvios

Código sem desvios nem sempre é mais rápido do que código com desvios. Quando um desvio é altamente previsível, o preditor acerta quase sempre e a jcc praticamente não custa nada. O código sem desvios que substitui esse tipo de desvio é mais lento, porque sempre executa os dois cálculos candidatos.

Um contador de laço é o exemplo canônico. Considere uma função que soma rsi inteiros de 64 bits começando em 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

Esse é exatamente o tipo de padrão que os preditores de desvio lidam bem, então o desvio praticamente não tem custo, não importa quantos elementos o sum_array processe.

O código sem desvios compensa quando o desvio é difícil de prever, ou quando é preciso um tempo de execução consistente independentemente das entradas.