Forçando a barra nas comparações

O seu compilador tende a arrumar o código da melhor maneira possível fazendo algumas adivinhações sobre o que o programador quis fazer. Um exemplo clássico são as comparações. Quando você escreve um simples if o compilador não tem como saber se a condição vai ser verdadeira na maioria das vezes que for feita. Ele não tem escolha senão assumir que ela será, mas “a maioria” não significa “todas” e ele poderá escolher interpretar a condição como falsa “na maioria das vezes” se o código gerado for “melhor”… Por “melhor” entenda “mais rápido”.

; void f(int x)
; { if (x==2) foo(); else bar(); }
f:
  cmp edi,2
  je  .callfoo
  jmp bar
.callfoo:
  jmp foo

O que o compilador fez aqui? Ele escolheu assumir que a condição não será verdadeira na maioria das vezes (Por quê?! explico adiante!). O salto condicional é sempre o principal problema quando falamos de branch prediction e, especialmente, saltos “para frente” são os mais problemáticos. Relembrando, a previsão de saltos mantém registros da quantidade de saltos condicionais feitos e o sentido em que o foram. Assim, se houverem mais saltos para trás que foram feitos, o próximo salto para trás é assumido como passível de ser feito. Da mesma forma, quanto mais saltos condicionais para frente não forem feitos, o próximo é assumido como passível de ser ignorado.

No caso acima, o código foi arranjado de tal forma que, se a comparação resultar no flag ZF=0 o salto condicional não é executado… Isso significa que o GCC assumiu que (x == 2) será falso na maioria das vezes que a função for executada… É claro que ele poderia assumir algo completamente diferente, de acordo com a complexidade do código. Para obter o controle do que é assumido na comparação podemos usar a função interna do GCC chamada __builtin_expect. Ela espera dois valores booleanos (0 ou 1): O primeiro vem da expressão da comparação e o segundo será o valor esperado. O que ela faz é dizer ao compilador o que ele deve assumir a respeito da expressão booleana… No caso da função acima, se esperamos que a comparação será verdadeira na maioria das vezes, poderíamos reescrevê-la como abaixo (no código em C comentado e o respectivo código gerado):

; void f(int x)
; { if (__builtin_expect(x==2, 1)) foo(); else bar(); }
f:
  cmp edi,2
  jne  .callbar     ; Só salta se ZF=0. É o mesmo que 
                    ; dizer que assumimos que ZF=1 na
                    ; maioria das vezes.
  jmp foo
.callbar:
  jmp bar

Note que __builtin_expect não usa os prefixos 0x2E e 0x3E antes das instruções de salto condicional para dar dicas ao processador sobre o destino do salto. Usar o prefixo 0x3E antes do salto condicional, no primeiro exemplo, indica para o processador que o salto deve ser considerado como sendo feito na maioria das vezes. Já o prefixo 0x2E é o contrário. O compilador provavelmente não faz isso porque esses prefixos são mais comuns nas referências à memória (ponteiros). Repare as instruções abaixo (i386), criadas com NASM:

89 07      mov [edi],eax
2E 89 07   mov [cs:edi],eax
3E 89 07   mov [ds:edi],eax

Usar esses prefixos de seleção de seletores para um ponteiro nas instruções de salto condicional cria código meio confuso de ler:

; void f(int x)
; { if (x==2) foo(); else bar(); }
f:
  cmp edi,2
  db  0x3E      ; O salto abaixo será feito
                ; na maioria das vezes!
  je  .callfoo
  jmp bar
.callfoo:
  jmp foo

A inclusão de uma definição de byte (db), solta, meio que polui a listagem. Pior ainda: note que o prefixo é apenas uma dica que pode ser prontamente desobedecida pelo processador. É melhor usar uma estratégia coerente para os sentidos dos saltos condicionais, tentando deixar o processador num estado conhecido, do que recorrer à dicas que podem ou não serem seguidas.

O motivo pelo qual o GCC tenta sempre evitar saltos condicionais “para frente” ou assumí-los como “não executados na maioria das vezes” são os loops. Loop, por definição, é uma estrutura de controle de fluxo de programa onde, em algum momento, será feito um salto “para trás”. E se tivermos mais saltos condicionais “para trás” em nossos códigos do que “para frente”, faz todo sentido privilegiar os primeiros, inclusive nos códigos condicionais (if..then..else, switch). Vejamos um exemplo:

...
for (i = 0; i < n; i++)
  x++;
...

Você poderia esperar um código em assembly, equivalente, como este:

; Assume que ecx=i, edx=n e eax=x.
  ...
  xor ecx,ecx
.L1:
  cmp ecx,edx
  jge .L2        ; Salto condicional para frente!!!
                 ; Falha n vezes e acerta na última.
  add  eax,1
  add  ecx,1
  jmp  .L1       ; Salta n vezes.
.L2:
  ...

Mas, desconsiderando otimizações, o compilador tende a criar um código como o mostrado abaixo, garantindo que o salto condicional “para trás” seja feito todas as vezes (exceto na última) e o único salto “para frente” é incondicional (e não afeta a previsão de saltos do processador):

; Assume que ecx=i, edx=n e eax=x.
  ...
  xor ecx,ecx
  jmp .L2       ; ────┐ salta apenas 1 vez
.L1:            ;     │
  add  eax,1    ; <┄┄┄│┄┄┄┐
  add  ecx,1    ;     │   ┆
.L2:            ;     │   ┆
  cmp ecx,edx   ; <───┘   ┆
  jl  .L1       ; ┄┄┄┄┄┄┄┄┘ salta n vezes
  ...

A vantagem da segunda abordagem me parece óbvia.

Então, evide contradizer as escolhas do compilador. A função __builtin_expect só deve ser usada nos casos especiais e, mesmo assim, é prudente verificar o que o compilador fez para ter certeza de que obterá o melhor código possível.

Anúncios