O MOV do x86 pode realmente ser “grátis”? Por que não consigo reproduzir isso?

Eu continuo vendo pessoas afirmarem que a instrução MOV pode ser livre em x86, por causa da renomeação de registradores.

Para a vida de mim, não posso verificar isso em um único caso de teste. Cada caso de teste eu tento desmembrá-lo.

Por exemplo, aqui está o código que estou compilando com o Visual C ++:

#include  #include  #include  int main(void) { unsigned int k, l, j; clock_t tstart = clock(); for (k = 0, j = 0, l = 0; j < UINT_MAX; ++j) { ++k; k = j; // <-- comment out this line to remove the MOV instruction l += j; } fprintf(stderr, "%d ms\n", (int)((clock() - tstart) * 1000 / CLOCKS_PER_SEC)); fflush(stderr); return (int)(k + j + l); } 

Isso produz o seguinte código assembly para o loop (fique à vontade para produzir isso como quiser; obviamente você não precisa do Visual C ++):

 LOOP: add edi,esi mov ebx,esi inc esi cmp esi,FFFFFFFFh jc LOOP 

Agora eu corro este programa várias vezes, e observo uma diferença bastante consistente de 2% quando a instrução MOV é removida:

 Without MOV With MOV 1303 ms 1358 ms 1324 ms 1363 ms 1310 ms 1345 ms 1304 ms 1343 ms 1309 ms 1334 ms 1312 ms 1336 ms 1320 ms 1311 ms 1302 ms 1350 ms 1319 ms 1339 ms 1324 ms 1338 ms 

Então, o que dá? Por que o MOV não é “grátis”? Esse loop é muito complicado para o x86?
Existe um único exemplo lá fora que pode demonstrar que o MOV é livre como as pessoas dizem?
Se assim for, o que é? E se não, por que todos continuam alegando MOV é livre?

A taxa de transferência do loop na questão não depende da latência do MOV ou (no Haswell) do benefício de não usar uma unidade de execução.

O loop ainda é de apenas 4 uops para o front-end entrar no núcleo fora de ordem. (O mov ainda precisa ser rastreado pelo núcleo fora de ordem, mesmo que não precise de uma unidade de execução, mas de macro-fusões cmp/jc em um único uop).

Os processadores da Intel desde o Core2 tiveram uma largura de emissão de 4 ups por clock, então o mov não o impede de executar em (perto de) um iter por clock no Haswell. Ele também seria executado em um por clock em Ivybridge (com eliminação de mov), mas não em Sandybridge (sem eliminação de movimento). No SnB, seria cerca de um iter por 1.333c ciclos, gargalo na taxa de transferência de ALU porque o mov sempre precisaria de um . (SnB / IvB tem apenas três portas ALU, enquanto Haswell tem quatro).

Note que o manuseio especial no estágio de renomeação tem sido algo para o x87 FXCHG (swap st0 com st1 ) por muito mais tempo que o MOV. Agner Fog lista FXCHG como 0 latência em PPro / PII / PIII (núcleo P6 de primeira geração).


O loop na questão tem duas cadeias de dependência de intertravamento (o add edi,esi depende do EDI e do contador de loop ESI), o que o torna mais sensível ao agendamento imperfeito. Uma desaceleração de 2% em relação à previsão teórica devido a instruções aparentemente não relacionadas não é incomum, e pequenas variações na ordem das instruções podem fazer esse tipo de diferença. Para executar exatamente 1c por iter, todo ciclo precisa executar um INC e um ADD. Uma vez que todos os INCs e ADDs são dependentes da iteração anterior, a execução fora de ordem não pode ser executada executando dois em um único ciclo. Pior ainda, o ADD depende do INC no ciclo anterior, que é o que eu quis dizer com “intertravamento”, então perder um ciclo na cadeia de INC INC também paralisa a cadeia ADD dep.

Além disso, as ramificações previstas só podem ser executadas na porta6, portanto, qualquer ciclo em que a porta6 não executa um cmp / jc é um ciclo de taxa de transferência perdida . Isso acontece toda vez que um INC ou ADD rouba um ciclo na porta6 em vez de rodar nas portas 0, 1 ou 5. IDK se este for o culpado, ou se a perda de ciclos nas cadeias de debugging de INC / ADD for o problema, ou talvez alguns dos dois.

Adicionar o MOV extra não adiciona nenhuma pressão de porta de execução, supondo que seja eliminado em 100%, mas impede que o front-end seja executado à frente do núcleo de execução . (Apenas 3 dos 4 uops no loop precisam de uma unidade de execução, e sua CPU Haswell pode rodar INC e ADD em qualquer uma das suas 4 portas ALU: 0, 1, 5 e 6. Assim, os gargalos são:

  • o throughput máximo do front-end de 4 uops por clock. (O loop sem MOV é de apenas 3 uops, então o front-end pode ser executado adiante).
  • taxa de transferência de uma tomada por relógio.
  • a cadeia de dependência envolvendo esi (latência de 1 por clock do INC)
  • a cadeia de dependência envolvendo edi (latência ADD de 1 por clock e também dependente do INC da iteração anterior)

Sem o MOV, o front-end pode emitir os três uops do loop em 4 por clock até que o núcleo fora de ordem esteja cheio. (AFAICT, “desenrola” minúsculos loops no loop-buffer (Loop Stream Detector: LSD), então um loop com ABC uops pode emitir em um padrão ABCA BCAB CABC … O contador perf para lsd.cycles_4_uops confirma que principalmente problemas em grupos de 4 quando emite algum uops.)

Os processadores Intel atribuem uops às portas à medida que são emitidas para o núcleo fora de ordem . A decisão é baseada em contadores que rastreiam quantos uops para cada porta já estão no agendador (também conhecido como Reservation Station, RS). Quando há muitos uops no RS esperando para serem executados, isso funciona bem e geralmente deve evitar o agendamento de INC ou ADD para port6. E eu também acho que evita programar o INC e ADD de tal forma que o tempo é perdido de qualquer uma dessas cadeias de dep. Mas se o RS estiver vazio ou quase vazio, os contadores não impedirão que um ADD ou INC roube um ciclo na porta6.

Eu pensei que estava em algo aqui, mas qualquer programação abaixo do ideal deveria deixar o front-end alcançar e manter o back-end cheio. Não acho que devemos esperar que o front-end cause bolhas suficientes no pipeline para explicar uma queda de 2% abaixo do throughput máximo, já que o pequeno loop deve ser executado a partir do buffer de loop com uma taxa consistente de 4 por clock. Talvez haja outra coisa acontecendo.


Um exemplo real do benefício da eliminação de mov .

Eu usei o lea para construir um loop que tem apenas um mov por clock, criando uma demonstração perfeita onde o MOV-elimination obtém 100%, ou 0% do tempo com mov same,same para demonstrar o gargalo de latência que produz.

Como o dec/jnz com fusível macro faz parte da cadeia de dependência que envolve o contador de loops, o agendamento imperfeito não pode atrasá-lo. Isso é diferente do caso em que cmp/jc “forks off” da cadeia de dependência de caminho crítico a cada iteração.

 _start: mov ecx, 2000000000 ; each iteration decrements by 2, so this is 1G iters align 16 ; really align 32 makes more sense in case the uop-cache comes into play, but alignment is actually irrelevant for loops that fit in the loop buffer. .loop: mov eax, ecx lea ecx, [rax-1] ; we vary these two instructions dec ecx ; dec/jnz macro-fuses into one uop in the decoders, on Intel jnz .loop .end: xor edi,edi ; edi=0 mov eax,231 ; __NR_exit_group from /usr/include/asm/unistd_64.h syscall ; sys_exit_group(0) 

Na família Intel SnB, o LEA com um ou dois componentes no modo de endereçamento é executado com latência 1c (consulte http://agner.org/optimize/ e outros links no wiki da marca x86 ).

Eu construí e executei isso como um binário estático no Linux, de modo que os contadores de desempenho do espaço do usuário para todo o processo estão medindo apenas o loop com sobrecarga desprezível de boot / desligamento. ( perf stat é realmente fácil comparado a colocar consultas de perf-counter no próprio programa)

 $ yasm -felf64 -Worphan-labels -gdwarf2 mov-elimination.asm && ld -o mov-elimination mov-elimination.o && objdump -Mintel -drwC mov-elimination && taskset -c 1 ocperf.py stat -etask-clock,context-switches,page-faults,cycles,instructions,branches,uops_issued.any,uops_executed.thread -r2 ./mov-elimination Disassembly of section .text: 00000000004000b0 <_start>: 4000b0: b9 00 94 35 77 mov ecx,0x77359400 4000b5: 66 66 2e 0f 1f 84 00 00 00 00 00 data16 nop WORD PTR cs:[rax+rax*1+0x0] 00000000004000c0 <_start .loop>: 4000c0: 89 c8 mov eax,ecx 4000c2: 8d 48 ff lea ecx,[rax-0x1] 4000c5: ff c9 dec ecx 4000c7: 75 f7 jne 4000c0 <_start .loop> 00000000004000c9 <_start .end>: 4000c9: 31 ff xor edi,edi 4000cb: b8 e7 00 00 00 mov eax,0xe7 4000d0: 0f 05 syscall perf stat -etask-clock,context-switches,page-faults,cycles,instructions,branches,cpu/event=0xe,umask=0x1,name=uops_issued_any/,cpu/event=0xb1,umask=0x1,name=uops_executed_thread/ -r2 ./mov-elimination Performance counter stats for './mov-elimination' (2 runs): 513.242841 task-clock:u (msec) # 1.000 CPUs utilized ( +- 0.05% ) 0 context-switches:u # 0.000 K/sec 1 page-faults:u # 0.002 K/sec 2,000,111,934 cycles:u # 3.897 GHz ( +- 0.00% ) 4,000,000,161 instructions:u # 2.00 insn per cycle ( +- 0.00% ) 1,000,000,157 branches:u # 1948.396 M/sec ( +- 0.00% ) 3,000,058,589 uops_issued_any:u # 5845.300 M/sec ( +- 0.00% ) 2,000,037,900 uops_executed_thread:u # 3896.865 M/sec ( +- 0.00% ) 0.513402352 seconds time elapsed ( +- 0.05% ) 

Como esperado, o loop executa 1G vezes ( branches ~ = 1 bilhão). Os ciclos “extras” do 111k além do 2G são a sobrecarga presente nos outros testes, incluindo o que não tem mov . Não é de falhas ocasionais de eliminação de movimentos, mas é escalável com a contagem de iteração, portanto, não é apenas uma sobrecarga de boot. Provavelmente é a partir de interrupções temporizadas, já que o IIRC Linux perf não brinca com os contadores de perfurações enquanto lida com interrupções, e apenas permite que elas continuem contando. (O perf virtualiza os contadores de desempenho de hardware para que você possa obter contagens por processo mesmo quando um encadeamento migra pelas CPUs.) Além disso, as interrupções do timer no núcleo lógico do irmão que compartilha o mesmo núcleo físico perturbarão um pouco as coisas.

O gargalo é a cadeia de dependencies carregada de loop envolvendo o contador de loops. Ciclos de 2G para iters de 1G são 2 clocks por iteração, ou 1 clock por decremento. O confirma que o comprimento da cadeia dep é de 2 ciclos. Isso só é possível se o mov tiver zero de latência . (Eu sei que isso não prova que não há algum outro gargalo. Isso só prova que a latência é de no máximo 2 ciclos, se você não acredita na minha afirmação de que a latência é o único gargalo. Há um resource_stalls.any contador de perf, mas ele não tem muitas opções para quebrar qual recurso microarchitectural foi esgotado.)

O loop tem 3 uops de domínio fundido: mov , lea e macro- dec/jnz . O 3G uops_issued.any contagem confirma que: Conta no domínio fundido, que é todo o pipeline dos decodificadores até a retirada, com exceção do agendador (RS) e das unidades de execução. (pares de instruções com fusível macro permanecem como uop único em todos os lugares. É apenas para microfusão de lojas ou ALU + carregar esse uop de domínio fundido no ROB rastreia o progresso de dois uops de domínio não fundido.)

2G uops_executed.thread ( uops_executed.thread -domain) informa que todos os mov foram eliminados (ou seja, manipulados pelo estágio de emissão / renomeação e colocados no ROB em um estado já executado). Eles ainda ocupam largura de banda de emissão / retirada, espaço no cache uop e tamanho de código. Eles ocupam espaço no ROB, limitando o tamanho da janela fora de ordem. Uma instrução mov nunca é livre. Há muitos gargalos de microarquitetura possíveis, além de portas de latência e execução, sendo a mais importante, geralmente, a taxa de emissão de 4 níveis do front-end.

Nos processadores Intel, a latência zero é muitas vezes maior do que a necessidade de uma unidade de execução, especialmente em Haswell e, posteriormente, onde há 4 portas ALU. (Mas apenas 3 deles podem lidar com uops vetoriais, portanto movimentos vetoriais não eliminados seriam um gargalo mais facilmente, especialmente em código sem muitos carregamentos ou lojas levando largura de banda de front-end (4 uops de domínio fundido por clock) longe de UUs da ALU Além disso, agendar uops para unidades de execução não é perfeito (mais como o mais antigo pronto primeiro), portanto uops que não estão no caminho crítico podem roubar ciclos do caminho crítico.

Se colocarmos um nop ou um xor edx,edx no loop, esses também seriam emitidos, mas não executados em CPUs da família Intel SnB.

A eliminação de movimento de latência zero pode ser útil para estender de zero de 32 a 64 bits e de 8 a 64. ( movzx eax, bl é eliminado, movzx eax, bx não é ).


Sem mov-eliminação

 mov ecx, ecx # Intel can't eliminate mov same,same lea ecx, [rcx-1] dec ecx jnz .loop 3,000,320,972 cycles:u # 3.898 GHz ( +- 0.00% ) 4,000,000,238 instructions:u # 1.33 insn per cycle ( +- 0.00% ) 1,000,000,234 branches:u # 1299.225 M/sec ( +- 0.00% ) 3,000,084,446 uops_issued_any:u # 3897.783 M/sec ( +- 0.00% ) 3,000,058,661 uops_executed_thread:u # 3897.750 M/sec ( +- 0.00% ) 

Isso leva ciclos 3G para iterações 1G, porque o comprimento da cadeia de dependência agora é de 3 ciclos.

A contagem de upl do domínio fundido não mudou, ainda 3G.

O que mudou é que agora a contagem de domínios não fundidos é a mesma do domínio fundido. Todos os uops precisavam de uma unidade de execução; Nenhuma das instruções mov foi eliminada, então todas adicionaram 1C de latência à cadeia dep.

(Quando há uops micro fundidos, como add eax, [rsi] , a contagem uops_executed pode ser maior que uops_issued . Mas não temos isso.)


Sem o mov todo:

 lea ecx, [rcx-1] dec ecx jnz .loop 2,000,131,323 cycles:u # 3.896 GHz ( +- 0.00% ) 3,000,000,161 instructions:u # 1.50 insn per cycle 1,000,000,157 branches:u # 1947.876 M/sec 2,000,055,428 uops_issued_any:u # 3895.859 M/sec ( +- 0.00% ) 2,000,039,061 uops_executed_thread:u # 3895.828 M/sec ( +- 0.00% ) 

Agora estamos de volta à latência de 2 ciclos para a cadeia dep carregada de loop.

Nada é eliminado.


Eu testei em um Skylake 3.9GHz i7-6700k. Eu recebo resultados idênticos em um Haswell i5-4210U (para dentro de 40k de contagens de 1G) para todos os events perf. Essa é a mesma margem de erro que reexecutar no mesmo sistema.

Note que se eu rodasse perf como root e contasse cycles vez de cycles:u (apenas espaço de usuário), ele mede a freqüência do CPU exatamente como 3.900 GHz. (IDK porque o Linux apenas obedece as configurações da bios para o máximo turbo logo após a reboot, mas depois cai para 3.9GHz se eu deixá-lo ocioso por alguns minutos. Asus Z170 Pro Gaming mobo, Arch Linux com kernel 4.10.11-1-ARCH Vi o mesmo com o Ubuntu. Escrevendo balance_performance para cada um dos /sys/devices/system/cpu/cpufreq/policy[0-9]*/energy_performance_preference de /etc/rc.local corrige isso, mas escrever balance_power para 3.9GHz novamente mais tarde.)


Você deve obter os mesmos resultados no AMD Ryzen, pois ele pode eliminar mov inteiros. A família AMD Bulldozer só pode eliminar cópias de registro xmm. (De acordo com Agner Fog, as cópias de registro de ymm são uma metade eliminada e uma ALU op para a metade alta.)

Por exemplo, o AMD Bulldozer e o Intel Ivybridge podem suportar uma taxa de transferência de 1 por

  movaps xmm0, xmm1 movaps xmm2, xmm3 movaps xmm4, xmm5 dec jnz .loop 

Mas a Intel Sandybridge não pode eliminar os movimentos, por isso seria um gargalo em 4 UU Uops para 3 portas de execução. Se fosse pxor xmm0,xmm0 vez de movaps, SnB também poderia sustentar uma iteração por clock. (Mas a família Bulldozer não poderia, porque o xor-zero ainda precisa de uma unidade de execução na AMD, mesmo que seja independente do valor antigo do registrador. E a família Bulldozer tem apenas 0,5c de taxa de transferência para o PXOR.)


Limitações da eliminação de movimentos

Duas instruções MOV dependentes seguidas expõem uma diferença entre Haswell e Skylake.

 .loop: mov eax, ecx mov ecx, eax sub ecx, 2 jnz .loop 

Haswell: menor variabilidade entre execuções (1.746 a 1.749 c / iter), mas isso é típico:

  1,749,102,925 cycles:u # 2.690 GHz 4,000,000,212 instructions:u # 2.29 insn per cycle 1,000,000,208 branches:u # 1538.062 M/sec 3,000,079,561 uops_issued_any:u # 4614.308 M/sec 1,746,698,502 uops_executed_core:u # 2686.531 M/sec 745,676,067 lsd_cycles_4_uops:u # 1146.896 M/sec 

Nem todas as instruções do MOV foram eliminadas: cerca de 0,75 dos 2 por iteração usaram uma porta de execução. Cada MOV que executa em vez de ser eliminado adiciona 1c de latência à cadeia de transporte carregada por loop, portanto, não é uma coincidência que uops_executed e cycles sejam muito semelhantes. Todos os uops fazem parte de uma única cadeia de dependência, portanto não há paralelismo possível. cycles é sempre cerca de 5M maior do que uops_executed independentemente da uops_executed de execução para execução, então eu acho que há apenas 5 milhões de ciclos sendo usados ​​em algum outro lugar.

Skylake: mais estável que os resultados de HSW, e mais eliminação de movimento: apenas 0,6666 MOVs de cada 2 precisavam de uma unidade de execução.

  1,666,716,605 cycles:u # 3.897 GHz 4,000,000,136 instructions:u # 2.40 insn per cycle 1,000,000,132 branches:u # 2338.050 M/sec 3,000,059,008 uops_issued_any:u # 7014.288 M/sec 1,666,548,206 uops_executed_thread:u # 3896.473 M/sec 666,683,358 lsd_cycles_4_uops:u # 1558.739 M/sec 

Em Haswell, lsd.cycles_4_uops responsável por todos os uops. (0,745 * 4 ~ = 3). Assim, em quase todos os ciclos em que os uops são emitidos, um grupo completo de 4 é emitido (do buffer de loop. Eu provavelmente deveria ter olhado para um contador diferente que não se importa de onde eles vieram, como uops_issued.stall_cycles para contar ciclos onde nenhum uops é emitido).

Mas na SKL, 0.66666 * 4 = 2.66664 é menor que 3, então em alguns ciclos o front-end emitiu menos de 4 uops. (Geralmente, ele fica parado até que haja espaço no núcleo fora de ordem para emitir um grupo completo de 4, em vez de emitir grupos não completos).

É estranho, IDK, qual é a limitação microarquitetural exata. Como o loop é de apenas 3 uops, cada grupo de problemas de 4 uops é mais que uma iteração completa. Assim, um grupo de problemas pode conter até 3 MOVs dependentes. Talvez Skylake é projetado para quebrar isso às vezes, para permitir mais eliminação de movimentos?

update : na verdade, isso é normal for loops 3-uop no Skylake. uops_issued.stall_cycles mostra que o HSW e o SKL emitem um simples loop 3 uop sem eliminação de mov da mesma forma que eles emitem este. Portanto, uma melhor eliminação dos movimentos é um efeito colateral da divisão de grupos de problemas por algum outro motivo. (Não é um gargalo porque as ramificações tomadas não podem ser executadas mais rápido do que 1 por relógio, independentemente da rapidez com que são emitidas). Eu ainda não sei por que a SKL é diferente, mas não acho que seja algo para se preocupar.


Em um caso menos extremo, SKL e HSW são os mesmos, com ambos não eliminando 0,3333 de cada 2 instruções MOV:

 .loop: mov eax, ecx dec eax mov ecx, eax sub ecx, 1 jnz .loop 

  2,333,434,710 cycles:u # 3.897 GHz 5,000,000,185 instructions:u # 2.14 insn per cycle 1,000,000,181 branches:u # 1669.905 M/sec 4,000,061,152 uops_issued_any:u # 6679.720 M/sec 2,333,374,781 uops_executed_thread:u # 3896.513 M/sec 1,000,000,942 lsd_cycles_4_uops:u # 1669.906 M/sec 

Todos os uops são emitidos em grupos de 4. Qualquer grupo contíguo de 4 uops conterá exatamente dois MOOP uops candidatos à eliminação. Como claramente consegue eliminar ambos em alguns ciclos, o IDK não pode fazer isso sempre.


O manual de otimização da Intel diz que sobrescrever o resultado da eliminação dos movimentos o mais cedo possível libera os resources da microarquitetura para que possa ter sucesso com mais frequência, pelo menos para o movzx . Veja o Exemplo 3-25. Reordenando Sequência para Melhorar a Eficácia das Instruções MOV de Latência Zero .

Então, talvez ele seja rastreado internamente com uma tabela de tamanho reduzido de contagens de referência? Algo precisa impedir que a input do arquivo de registro físico seja liberada quando não for mais necessária como o valor do registro de arquitetura original, se ainda for necessário como o valor do destino de movimento. Liberar inputs PRF o mais rápido possível é fundamental, porque o tamanho do PRF pode limitar a janela fora de ordem a um tamanho menor que o do ROB.

Eu tentei os exemplos em Haswell e Skylake, e descobri que a eliminação de movimento de fato trabalhava significantemente mais do tempo ao fazer isso, mas que na verdade era um pouco mais lento em ciclos totais, ao invés de mais rápido. O exemplo pretendia mostrar o benefício no IvyBridge, o que provavelmente compromete as suas 3 portas ALU, mas o HSW / SKL apenas afunila nos conflitos de resources nas cadeias dep e não parece ser incomodado por precisar de uma porta ALU para mais do instruções movzx .

Veja também Por que o XCHG reg registra 3 instruções de microinstruções em arquiteturas modernas da Intel? para mais pesquisa + adivinhação sobre como funciona a eliminação de mov e se ela poderia funcionar para xchg eax, ecx . (Na prática xchg reg,reg é de 3 ALU na Intel, mas 2 eliminaram os uops no Ryzen. É interessante adivinhar se a Intel poderia ter implementado isso de forma mais eficiente.)


BTW, como uma solução alternativa para uma errata no Haswell, o Linux não fornece uops_executed.thread quando o hyperthreading está ativado, apenas o uops_executed.core . O outro núcleo foi definitivamente ocioso o tempo todo, nem mesmo as interrupções do timer, porque eu o coloquei offline com o echo 0 > /sys/devices/system/cpu/cpu3/online . Infelizmente isso não pode ser feito antes que o perf conclua que o HT está habilitado e meu laptop Dell não tem uma opção de BIOS para desabilitar o HT. Então eu não posso obter perf para usar todos os 8 contadores de PMU de hardware de uma vez nesse sistema, apenas 4.: /

Aqui estão dois pequenos testes que acredito conclusivamente mostram evidências para a eliminação de movimentos:

 __loop1: add edx, 1 add edx, 1 add ecx, 1 jnc __loop1 

versus

 __loop2: mov eax, edx add eax, 1 mov edx, eax add edx, 1 add ecx, 1 jnc __loop2 

Se mov adicionou um ciclo a uma cadeia de dependência, seria esperado que a segunda versão levasse cerca de 4 ciclos por iteração. No meu Haswell, ambos demoram cerca de 2 ciclos por iteração, o que não pode acontecer sem eliminação de movimento.