Por que os compiladores insistem em usar um registro salvo por chamada aqui?

10

Considere este código C:

void foo(void);

long bar(long x) {
    foo();
    return x;
}

Ao compilá-lo no GCC 9.3 com -O3ou -Os, recebo o seguinte:

bar:
        push    r12
        mov     r12, rdi
        call    foo
        mov     rax, r12
        pop     r12
        ret

A saída do clang é idêntica, exceto pela escolha em rbxvez de r12como o registro salvo pelo chamado.

No entanto, eu quero / espero ver uma montagem mais parecida com esta:

bar:
        push    rdi
        call    foo
        pop     rax
        ret

Em inglês, aqui está o que vejo acontecendo:

  • Envie o valor antigo de um registro salvo por chamada para a pilha
  • Mover xpara o registro salvo no chamado
  • Ligar foo
  • Mover xdo registro salvo no chamado para o registro de valor retornado
  • Pop a pilha para restaurar o valor antigo do registro salvo por chamada

Por que se preocupar em mexer com um registro salvo no chamado? Por que não fazer isso? Parece mais curto, mais simples e provavelmente mais rápido:

  • Empurre xpara a pilha
  • Ligar foo
  • Salte xda pilha para o registro de valor retornado

Minha montagem está errada? De alguma forma, é menos eficiente do que mexer com um registro extra? Se a resposta para ambos é "não", por que o GCC ou o clang não fazem dessa maneira?

Link Godbolt .


Edit: Aqui está um exemplo menos trivial, para mostrar que isso acontece mesmo que a variável seja usada significativamente:

long foo(long);

long bar(long x) {
    return foo(x * x) - x;
}

Eu entendi isso:

bar:
        push    rbx
        mov     rbx, rdi
        imul    rdi, rdi
        call    foo
        sub     rax, rbx
        pop     rbx
        ret

Eu prefiro ter isso:

bar:
        push    rdi
        imul    rdi, rdi
        call    foo
        pop     rdi
        sub     rax, rdi
        ret

Desta vez, é apenas uma instrução desativada versus duas, mas o conceito principal é o mesmo.

Link Godbolt .

Joseph Sible-Restabelecer Monica
fonte
4
Otimização perdida interessante.
fuz 22/04
11
provavelmente a suposição de que o parâmetro passado será usado para que você queira salvar um registro volátil e manter o parâmetro passado em um registro que não esteja na pilha, pois os acessos subseqüentes a esse parâmetro são mais rápidos a partir do registro. passe x para foo e você verá isso. portanto, é provavelmente apenas uma parte genérica de sua configuração de quadro de pilha.
old_timer 22/04
concedido, vejo que, sem foo, ele não usa a pilha; portanto, é uma otimização perdida, mas algo que alguém precisaria adicionar, analisar a função e se o valor não for usado e não houver conflito com esse registro (geralmente há é).
old_timer 22/04
o backend do braço também faz isso no gcc. provavelmente não o back
old_timer 22/04
clang 10 mesma história (back-end do braço).
old_timer 22/04

Respostas:

5

TL: DR:

  • Os componentes internos do compilador provavelmente não estão configurados para procurar essa otimização facilmente, e provavelmente são úteis apenas em pequenas funções, não em grandes funções entre chamadas.
  • Inlining para criar grandes funções é uma solução melhor na maioria das vezes
  • Pode haver uma troca de latência x taxa de transferência se foonão salvar / restaurar o RBX.

Compiladores são peças complexas de máquinas. Eles não são "inteligentes" como humanos, e algoritmos caros para encontrar todas as otimizações possíveis geralmente não valem o custo em tempo de compilação extra.

Eu relatei isso como bug 69986 do GCC - código menor possível com -Os usando push / pop para vazar / recarregar em 2016 ; não houve atividade ou resposta dos desenvolvedores do GCC. : /

Ligeiramente relacionado: o bug 70408 do GCC - reutilizar o mesmo registro preservado de chamadas daria um código menor em alguns casos - os desenvolvedores do compilador me disseram que seria necessário muito trabalho para que o GCC pudesse fazer essa otimização porque requer ordem de seleção de duas foo(int)chamadas com base no que tornaria o destino mais simples.


Se foo não se salvar / restaurar rbx, há uma troca entre taxa de transferência (contagem de instruções) e uma latência extra de armazenamento / recarga na xcadeia de dependência -> retval.

Os compiladores geralmente favorecem a latência sobre a taxa de transferência, por exemplo, usando 2x LEA em vez de imul reg, reg, 10(latência de 3 ciclos, taxa de transferência de 1 / clock), porque a maioria dos códigos calcula a média significativamente menor que 4 uops / clock em tubulações típicas de 4 larguras como Skylake. (Mais instruções / uops ocupam mais espaço no ROB, reduzindo o quão à frente a mesma janela fora de ordem pode ver, porém, e a execução é realmente cheia de barracas, provavelmente representando alguns dos menos de 4 uops / média do relógio.)

Se foofor push / pop RBX, não há muito a ganhar em latência. O fato de a restauração ocorrer logo antes do em retvez de logo após provavelmente não é relevante, a menos que haja uma retfalha de previsão incorreta ou de cache em I que atrasa a busca de código no endereço de retorno.

A maioria das funções não triviais salvará / restaurará o RBX, portanto, muitas vezes não é uma boa suposição que deixar uma variável no RBX signifique que ele realmente permaneceu em um registro durante a chamada. (Embora a escolha aleatória de quais funções de registradores preservados de chamada escolhem pode às vezes ser uma boa idéia para mitigar isso)


Portanto, sim push rdi/ pop raxseria mais eficiente nesse caso, e provavelmente essa é uma otimização perdida para pequenas funções que não são folhas, dependendo do que foofaz e do equilíbrio entre a latência extra de armazenamento / recarga xe mais instruções para salvar / restaurar o chamador rbx.

É possível que os metadados de desenrolamento de pilha representem as alterações no RSP aqui, como se tivessem usado sub rsp, 8para derramar / recarregar xem um slot de pilha. (Mas compiladores não sei essa otimização, quer, de utilizar pusho espaço de reserva e inicializar uma variável. O que C / C ++ compilador pode usar instruções impulso pop para a criação de variáveis locais, em vez de apenas aumentar esp uma vez? . E fazendo isso por mais de um var local levaria a .eh_framemetadados de desenrolamento de pilha maiores, porque você está movendo o ponteiro de pilha separadamente a cada envio. Isso não impede que os compiladores usem push / pop para salvar / restaurar registros preservados de chamada.)


IDK se valeria a pena ensinar aos compiladores a procurar essa otimização

Talvez seja uma boa idéia em torno de uma função inteira, não em uma chamada dentro de uma função. E como eu disse, é baseado na suposição pessimista de que foovocê salvará / restaurará o RBX de qualquer maneira. (Ou otimizar a taxa de transferência se você souber que a latência de x para retornar valor não é importante. Mas os compiladores não sabem disso e geralmente otimizam para latência).

Se você começar a fazer essa suposição pessimista em muitos códigos (como em torno de chamadas de função única dentro de funções), começará a receber mais casos em que o RBX não é salvo / restaurado e você poderia ter aproveitado.

Você também não deseja salvar / restaurar extra push / pop em um loop, apenas salve / restaure o RBX fora do loop e use registros preservados de chamadas em loops que fazem chamadas de função. Mesmo sem loops, no caso geral, a maioria das funções faz várias chamadas de função. Essa idéia de otimização pode ser aplicada se você realmente não usar xentre nenhuma das chamadas, imediatamente antes da primeira e após a última, caso contrário , você terá um problema em manter o alinhamento da pilha de 16 bytes para cada uma, callse estiver fazendo um pop após um antes de outra chamada.

Compiladores não são bons em pequenas funções em geral. Mas também não é ótimo para CPUs. As chamadas de função não em linha afetam a otimização o melhor dos momentos, a menos que os compiladores possam ver as partes internas do chamado e fazer mais suposições do que o habitual. Uma chamada de função não embutida é uma barreira implícita à memória: o chamador deve assumir que uma função pode ler ou gravar qualquer dado acessível globalmente, para que todos esses vars tenham que estar sincronizados com a máquina abstrata C. (A análise de escape permite manter os habitantes locais em registros nas chamadas, se o endereço deles não tiver escapado da função.) Além disso, o compilador deve assumir que os registros com excesso de chamada estão com excesso. Isso é péssimo para o ponto flutuante no x86-64 System V, que não possui registros XMM preservados por chamada.

Funções minúsculas, como bar()é melhor incluir os chamadores. Compile -fltopara que isso possa acontecer mesmo dentro dos limites do arquivo na maioria dos casos. (Ponteiros de função e limites de biblioteca compartilhada podem anular isso.)


Acho que um dos motivos pelos quais os compiladores não se deram ao trabalho de tentar fazer essas otimizações é que isso exigiria um monte de código diferente nas partes internas do compilador , diferente da pilha normal e do código de alocação de registro que sabe como salvar chamadas preservadas registradores e usá-los.

ou seja, seria muito trabalho para implementar e muito código para manter, e se ficar entusiasmado demais com isso, poderá piorar o código.

E também que (espero) não é significativo; Se é importante, você deve ser inlining barem seu chamador, ou inlining fooem bar. Isso é bom, a menos que haja muitas barfunções semelhantes e fooseja grande e , por algum motivo, elas não possam ser incorporadas aos chamadores.

Peter Cordes
fonte
não tenho certeza se faz sentido perguntar por que algum compilador traduz código dessa maneira, quando pode ser melhor usar .., se não erro na tradução. por exemplo possível perguntar por que clang tão estranho (não otimizado) thranslated este loop, compare com gcc, icc e até msvc
RbMm
11
@RbMm: Eu não entendo o seu ponto. Isso parece uma otimização perdida totalmente separada para o clang, não relacionada ao que é essa pergunta. Existem erros de otimizações perdidos e, na maioria dos casos, devem ser corrigidos. Vá em frente e relate-o em bugs.llvm.org
Peter Cordes
sim, meu exemplo de código é absolutamente independente da pergunta original. simplesmente outro exemplo de tradução estranha (para minha aparência) (e apenas para um compilador de clang único). mas resultar código ASM de qualquer maneira correto. só não é melhor e eveen não nativo comparar gcc / icc / msvc
RbMm 23/04