Quais methods podem ser usados ​​para estender eficientemente o comprimento da instrução no x86 moderno?

Imagine que você queira alinhar uma série de instruções de assembly x86 a determinados limites. Por exemplo, você pode querer alinhar loops a um limite de 16 ou 32 bytes, ou instruções de pacote para que eles sejam eficientemente colocados no cache do uop ou o que for.

A maneira mais simples de conseguir isso é instruções NOP de byte único, seguidas de perto pelos NOPs multi-byte . Embora o último seja geralmente mais eficiente, nenhum método é gratuito: os NOPs usam resources de execução front-end e também contam com o limite de renomeação de 4 em 1 no x86 moderno.

Outra opção é de alguma forma aumentar algumas instruções para obter o alinhamento desejado. Se isso é feito sem introduzir novas barracas, parece melhor do que a abordagem NOP. Como as instruções podem ser mais eficientes em CPUs x86 recentes?

No mundo ideal, as técnicas de alongamento seriam simultaneamente:

  • Aplicável à maioria das instruções
  • Capaz de alongar a instrução por um valor variável
  • Não pare ou diminua a velocidade dos decodificadores
  • Seja eficientemente representado no cache uop

Não é provável que exista um único método que satisfaça simultaneamente todos os pontos acima, portanto, as boas respostas provavelmente abordarão várias compensações.


1 O limite é 5 ou 6 no AMD Ryzen.

Considere moderar o código de golfe para reduzir seu código em vez de expandi-lo , especialmente antes de um loop. Por exemplo, xor eax,eax / cdq se você precisar de dois registradores zerados, ou mov eax, 1 / lea ecx, [rax+1] para definir registradores para 1 e 2 em apenas 8 bytes totais em vez de 10. Consulte Definir todos os bits na CPU Registre-se para 1 de forma eficiente para mais sobre isso, e Dicas para jogar golfe em x86 / x64 código de máquina para idéias mais gerais. Provavelmente você ainda quer evitar falsas dependencies, no entanto.

Ou preencha um espaço extra criando uma constante vetorial ao invés de carregá-la da memory. (A adição de mais pressão no cache do uop poderia ser pior, no entanto, para o loop maior que contém o loop interno de setup +. Mas evita erros do d-cache para constantes, então ele tem um lado positivo para compensar a execução de mais uops.)

Se você ainda não estava usando para carregar constantes “compactadas”, pmovsxbd , movddup ou vpbroadcastd são mais longos que movaps . As cargas de transmissão dword / qword são gratuitas (sem ALU uop, apenas uma carga).

Se você está preocupado com o alinhamento do código, provavelmente você está preocupado sobre como ele está no cache L1I ou onde estão os limites do cache uop, então apenas contar o total de uops não é mais suficiente, e alguns uops extras no bloco antes do que você se preocupa pode não ser um problema de todo.

Mas, em algumas situações, você pode realmente querer otimizar o throughput de decodificação / uso do uop-cache / total uops para as instruções antes do bloco que você deseja alinhar.


Instruções de preenchimento, como a pergunta solicitada:

Agner Fog tem uma seção inteira sobre isso: “10.6 Tornando as instruções mais longas para fins de alinhamento” em seu guia “Otimizando as sub-rotinas na linguagem de assembly” . (As idéias lea , push r/m64 e SIB são de lá, e eu copiei uma frase / frase ou duas, caso contrário, essa resposta é o meu próprio trabalho, seja idéias diferentes ou escritas antes de verificar o guia de Agner.)

Ele não foi atualizado para CPUs atuais, embora: lea eax, [rbx + dword 0] tem mais desvantagens do que costumava usar vs mov eax, ebx , porque você perde zero-latência / nenhum mov unidade de execução . Se não estiver no caminho crítico, vá embora. O lea simples tem um rendimento razoavelmente bom, e um LEA com um modo de endereçamento grande (e talvez até mesmo alguns prefixos de segmento) pode ser melhor para o rendimento de decodificação / execução do que mov + nop .

Use o formulário geral em vez do formulário curto (sem ModR / M) de instruções como push reg ou mov reg,imm . por exemplo, use o push r/m64 2 bytes push r/m64 para push rbx . Ou use uma instrução equivalente que é mais longa, como add dst, 1 vez de inc dst , nos casos em que não há downsides de perf para inc então você já estava usando inc .

Use o byte SIB . Você pode obter o NASM para fazer isso usando um único registrador como um índice, como mov eax, [nosplit rbx*1] ( veja também ), mas isso prejudica a latência de uso de carga vs. simplesmente codificando mov eax, [rbx] com um byte SIB. Os modos de endereçamento indexados têm outras desvantagens na família SnB, como a falta de laminação e o não uso da porta 7 para as lojas .

Portanto , é melhor codificar base=rbx + disp0/8/32=0 usando ModR / M + SIB sem índice reg . (A codificação SIB para “nenhum índice” é a codificação que, de outra forma, significaria idx = RSP). [rsp + x] modos de endereçamento requerem um SIB já (base = RSP é o código de escape que significa que há um SIB), e isso aparece o tempo todo no código gerado pelo compilador. Portanto, há boas razões para esperar que isso seja totalmente eficiente para decodificar e executar (mesmo para registros de base que não sejam o RSP) agora e no futuro. A syntax do NASM não pode expressar isso, então você teria que codificar manualmente. Gás GNU A syntax Intel de objdump -d diz 8b 04 23 mov eax,DWORD PTR [rbx+riz*1] para o exemplo 10.20 da Agner Fog. ( riz é uma notação fictícia de índice zero que significa que existe um SIB sem índice). Eu não testei se o GAS aceita isso como input.

Use uma forma imm32 e / ou disp32 de uma instrução que só precisava de imm8 ou disp0/disp32 . O teste de Agner Fog sobre o cache uc de Sandybridge ( guia de microarquias tabela 9.1 ) indica que o valor real de um imediato / deslocamento é o que importa, não o número de bytes usados ​​na codificação de instruções. Eu não tenho nenhuma informação sobre o cache uop de Ryzen.

Então, NASM imul eax, [dword 4 + rdi], strict dword 13 (10 bytes: opcode + modrm + disp32 + imm32) usaria a categoria 32small, 32small e receberia 1 input no cache uop, ao contrário do imediato ou do disp32 na verdade tinha mais de 16 bits significativos. (Em seguida, seriam necessárias duas inputs e o carregamento do cache uop exigiria um ciclo extra.)

De acordo com a tabela de Agner, 8/16 / 32small são sempre equivalentes para SnB. E os modos de endereçamento com um registro são os mesmos, não havendo nenhum deslocamento, ou seja 32small, então mov dword [dword 0 + rdi], 123456 recebe 2 inputs, assim como mov dword [rdi], 123456789 . Eu não tinha percebido [rdi] + full imm32 levou 2 inputs, mas aparentemente que ‘é o caso de SnB.

Use jmp / jcc rel32 vez de rel8 . O ideal é tentar expandir as instruções em locais que não exigem mais codificações de salto fora da região que você está expandindo. Pad após o salto alvos para saltos para a frente anteriores, pad antes de saltar alvos para saltos para trás mais tarde, se eles estão perto de precisar de um rel32 em outro lugar. Por exemplo, tente evitar o preenchimento entre uma ramificação e seu destino, a menos que você queira que essa ramificação use um rel32 de qualquer maneira.


Você pode ser tentado a codificar mov eax, [symbol] como 6-byte a32 mov eax, [abs symbol] no código de 64 bits, usando um prefixo de tamanho de endereço para usar um endereço absoluto de 32 bits. Mas isso faz com que o Prefixo de Alteração de Comprimento pare quando decodificar nos processadores da Intel. Felizmente, nenhum dos NASM / YASM / gás / clang faz essa otimização de tamanho de código por padrão se você não especificar explicitamente um tamanho de endereço de 32 bits, em vez disso usando 7 bytes de mov r32, r/m32 com um ModR / M + SIB + disp32 modo de endereçamento absoluto para mov eax, [abs symbol] .

No código dependente da posição de 64 bits, o endereçamento absoluto é uma maneira barata de usar 1 byte extra vs. relativo ao RIP . Mas observe que o absoluto + imediato de 32 bits leva 2 ciclos para buscar a partir do cache uop, diferentemente do RIP-relative + imm8 / 16/32, que leva apenas 1 ciclo, embora ainda use 2 inputs para a instrução. (por exemplo, para um mov store ou um cmp ). Então, cmp [abs symbol], 123 é mais lento para buscar no cache uop do que cmp [rel symbol], 123 , mesmo que ambos recebam 2 inputs cada. Sem imediato, não há custo extra para

Note que os executáveis ​​do PIE permitem o ASLR até mesmo para o executável, e são o padrão em muitas distro Linux , então se você puder manter seu código PIC sem nenhuma desvantagem, então é preferível.


Use um prefixo REX quando não precisar de um, por exemplo, db 0x40 / add eax, ecx .

Em geral, não é seguro adicionar prefixos como o representante que as CPUs atuais ignoram, porque podem significar outra coisa em futuras extensões ISA.

Repetir o mesmo prefixo às vezes é possível (não com o REX, no entanto). Por exemplo, db 0x66, 0x66 / add ax, bx fornece os prefixos de tamanho de operando da instrução 3, que eu acho que é sempre estritamente equivalente a uma cópia do prefixo. Até 3 prefixos é o limite para decodificação eficiente em algumas CPUs. Mas isso só funciona se você tiver um prefixo que possa usar em primeiro lugar; você geralmente não está usando o tamanho de operando de 16 bits e geralmente não deseja um tamanho de endereço de 32 bits (embora seja seguro acessar dados estáticos em código dependente de posição).

Um prefixo ds ou ss em uma instrução que acessa a memory é um não-op e provavelmente não causa qualquer lentidão em qualquer CPU atual. (@prl sugeriu isso nos comentários).

Na verdade, o guia de movq [esi+ecx],mm0 Agner Fog usa um prefixo ds em um movq [esi+ecx],mm0 no Exemplo 7.1. Organizando blocos IFETCH para ajustar um loop para PII / PIII (sem buffer de loop ou cache uop), acelerando-o de 3 iterações por clock para 2.

Algumas CPUs (como AMD) decodificam lentamente quando as instruções têm mais de 3 prefixos. Em algumas CPUs, isso inclui os prefixos obrigatórios nas instruções SSE2 e especialmente SSSE3 / SSE4.1. Em Silvermont, até mesmo o byte de escape 0F conta.

As instruções AVX podem usar um prefixo VEX de 2 ou 3 bytes . Algumas instruções exigem um prefixo VEX de 3 bytes (a segunda origem é x / ymm8-15 ou prefixos obrigatórios para SSSE3 ou posterior). Mas uma instrução que poderia ter usado um prefixo de 2 bytes sempre pode ser codificada com um VEX de 3 bytes. NASM ou GAS {vex3} vxorps xmm0,xmm0 . Se o AVX512 estiver disponível, você também poderá usar o EVEX de 4 bytes.


Use tamanho de operando de 64 bits para mov mesmo quando não for necessário , por exemplo, mov rax, strict dword 1 força a codificação immta de sinal de 7 bytes estendida em NASM, o que normalmente o otimizaria para mov eax, 1 5 bytes mov eax, 1 .

 mov eax, 1 ; 5 bytes to encode (B8 imm32) mov rax, strict dword 1 ; 7 bytes: REX mov r/m64, sign-extended-imm32. mov rax, strict qword 1 ; 10 bytes to encode (REX B8 imm64). movabs mnemonic for AT&T. 

Você pode até usar mov reg, 0 vez de xor reg,reg .

mov r64, imm64 se encheckbox de forma eficiente no cache uop quando a constante é realmente pequena (ajusta-se no sinal de 32 bits estendido). 1 input de cache uop e tempo de carregamento = 1, o mesmo que para mov r32, imm32 . Decodificar uma instrução gigante significa que provavelmente não há espaço em um bloco de decodificação de 16 bytes para que outras três instruções sejam decodificadas no mesmo ciclo, a menos que sejam todas de 2 bytes. Possivelmente alongar várias outras instruções pode ser melhor do que ter uma instrução longa.


Decodifique as penalidades para prefixos extras:

  • P5: os prefixos evitam o emparelhamento, exceto para o tamanho do endereço / operando apenas no PMMX.
  • PPro a PIII: sempre haverá uma penalidade se uma instrução tiver mais de um prefixo. Esta penalidade é geralmente um relógio por prefixo extra. (Guia microarch de Agner, fim da seção 6.3)
  • Silvermont: é provavelmente a restrição mais rígida sobre quais prefixos você pode usar, se você se importa com isso. Decodifica barracas em mais de 3 prefixos, contando prefixos obrigatórios + 0F byte de escape. As instruções SSSE3 e SSE4 já possuem 3 prefixos, portanto, até um REX faz com que demorem a decodificar.
  • alguma AMD: talvez um limite de 3-prefixo, não incluindo bytes de escape, e talvez não incluindo prefixos obrigatórios para instruções SSE.

… TODO: termine esta seção. Até lá, consulte o guia de microarcas da Agner Fog.


Depois de codificar manualmente, sempre desmonte seu binário para ter certeza de que está certo . É lamentável que a NASM e outras montadoras não tenham um suporte melhor para escolher o preenchimento barato em uma região de instruções para alcançar um determinado limite de alinhamento.


Sintaxe assembler

O NASM possui alguma syntax de substituição de codificação : {vex3} e {evex} prefixos, NOSPLIT e strict byte / dword , e forçando disp8 / disp32 dentro dos modos de endereçamento. Note que [rdi + byte 0] não é permitido, a palavra chave byte deve vir primeiro. [byte rdi + 0] é permitido, mas acho que isso parece estranho.

Listando de nasm -l/dev/stdout -felf64 padding.asm

  line addr machine-code bytes source line num 4 00000000 0F57C0 xorps xmm0,xmm0 ; SSE1 *ps instructions are 1-byte shorter 5 00000003 660FEFC0 pxor xmm0,xmm0 6 7 00000007 C5F058DA vaddps xmm3, xmm1,xmm2 8 0000000B C4E17058DA {vex3} vaddps xmm3, xmm1,xmm2 9 00000010 62F1740858DA {evex} vaddps xmm3, xmm1,xmm2 10 11 12 00000016 FFC0 inc eax 13 00000018 83C001 add eax, 1 14 0000001B 4883C001 add rax, 1 15 0000001F 678D4001 lea eax, [eax+1] ; runs on fewer ports and doesn't set flags 16 00000023 67488D4001 lea rax, [eax+1] ; address-size and REX.W 17 00000028 0501000000 add eax, strict dword 1 ; using the EAX-only encoding with no ModR/M 18 0000002D 81C001000000 db 0x81, 0xC0, 1,0,0,0 ; add eax,0x1 using the ModR/M imm32 encoding 19 00000033 81C101000000 add ecx, strict dword 1 ; non-eax must use the ModR/M encoding 20 00000039 4881C101000000 add rcx, strict qword 1 ; YASM requires strict dword for the immediate, because it's still 32b 21 00000040 67488D8001000000 lea rax, [dword eax+1] 22 23 24 00000048 8B07 mov eax, [rdi] 25 0000004A 8B4700 mov eax, [byte 0 + rdi] 26 0000004D 3E8B4700 mov eax, [ds: byte 0 + rdi] 26 ****************** warning: ds segment base generated, but will be ignored in 64-bit mode 27 00000051 8B8700000000 mov eax, [dword 0 + rdi] 28 00000057 8B043D00000000 mov eax, [NOSPLIT dword 0 + rdi*1] ; 1c extra latency on SnB-family for non-simple addressing mode 

O GAS tem pseudo-prefixos de substituição de codificação {vex3} , {evex} , {disp8} e {disp32} Eles substituem os sufixos .s , .d8 e .d32 agora foram preteridos .

O GAS não tem um override para tamanho imediato, apenas deslocamentos.

O GAS permite adicionar um prefixo ds explícito, com ds mov src,dst

gcc -g -c padding.S && objdump -drwC padding.o -S , com edição manual:

  # no CPUs have separate ps vs. pd domains, so there's no penalty for mixing ps and pd loads/shuffles 0: 0f 28 07 movaps (%rdi),%xmm0 3: 66 0f 28 07 movapd (%rdi),%xmm0 7: 0f 58 c8 addps %xmm0,%xmm1 # not equivalent for SSE/AVX transitions, but sometimes safe to mix with AVX-128 a: c5 e8 58 d9 vaddps %xmm1,%xmm2, %xmm3 # default {vex2} e: c4 e1 68 58 d9 {vex3} vaddps %xmm1,%xmm2, %xmm3 13: 62 f1 6c 08 58 d9 {evex} vaddps %xmm1,%xmm2, %xmm3 19: ff c0 inc %eax 1b: 83 c0 01 add $0x1,%eax 1e: 48 83 c0 01 add $0x1,%rax 22: 67 8d 40 01 lea 1(%eax), %eax # runs on fewer ports and doesn't set flags 26: 67 48 8d 40 01 lea 1(%eax), %rax # address-size and REX # no equivalent for add eax, strict dword 1 # no-ModR/M .byte 0x81, 0xC0; .long 1 # add eax,0x1 using the ModR/M imm32 encoding 2b: 81 c0 01 00 00 00 add $0x1,%eax # manually encoded 31: 81 c1 d2 04 00 00 add $0x4d2,%ecx # large immediate, can't get GAS to encode this way with $1 other than doing it manually 37: 67 8d 80 01 00 00 00 {disp32} lea 1(%eax), %eax 3e: 67 48 8d 80 01 00 00 00 {disp32} lea 1(%eax), %rax mov 0(%rdi), %eax # the 0 optimizes away 46: 8b 07 mov (%rdi),%eax {disp8} mov (%rdi), %eax # adds a disp8 even if you omit the 0 48: 8b 47 00 mov 0x0(%rdi),%eax {disp8} ds mov (%rdi), %eax # with a DS prefix 4b: 3e 8b 47 00 mov %ds:0x0(%rdi),%eax {disp32} mov (%rdi), %eax 4f: 8b 87 00 00 00 00 mov 0x0(%rdi),%eax {disp32} mov 0(,%rdi,1), %eax # 1c extra latency on SnB-family for non-simple addressing mode 55: 8b 04 3d 00 00 00 00 mov 0x0(,%rdi,1),%eax 

O GAS é estritamente menos poderoso que o NASM para expressar codificações mais longas que as necessárias.

Eu posso pensar em quatro maneiras fora do topo da minha cabeça:

Primeiro: use codificações alternativas para instruções (Peter Cordes mencionou algo similar). Há muitas maneiras de chamar a operação ADD, por exemplo, e algumas delas ocupam mais bytes:

http://www.felixcloutier.com/x86/ADD.html

Normalmente, um montador tentará escolher a “melhor” codificação para a situação, seja ela otimizada para velocidade ou comprimento, mas você sempre pode usar outra e obter o mesmo resultado.

Segundo: Use outras instruções que sigam a mesma coisa e tenham comprimentos diferentes. Tenho certeza que você pode pensar em inúmeros exemplos onde você pode colocar uma instrução no código para replace uma existente e obter os mesmos resultados. As pessoas que otimizam o código fazem isso o tempo todo:

 shl 1 add eax, eax mul 2 etc etc 

Terceiro: Use a variedade de NOPs disponíveis para preencher o espaço extra:

 nop and eax, eax sub eax, 0 etc etc 

Em um mundo ideal, você provavelmente teria que usar todos esses truques para obter o código com o comprimento exato de bytes que você deseja.

Quarto: Mude seu algoritmo para obter mais opções usando os methods acima.

Uma nota final: Obviamente, segmentar processadores mais modernos proporcionará melhores resultados devido ao número e à complexidade das instruções. Ter access às instruções MMX, XMM, SSE, SSE2, ponto flutuante, etc. pode facilitar seu trabalho.

Vamos ver uma parte específica do código:

  cmp ebx,123456 mov al,0xFF je .foo 

Para este código, nenhuma das instruções pode ser substituída por qualquer outra coisa, portanto, as únicas opções são prefixos redundantes e NOPs.

No entanto, e se você alterar a ordem das instruções?

Você poderia converter o código para isso:

  mov al,0xFF cmp ebx,123456 je .foo 

Depois de reordenar as instruções; o mov al,0xFF pode ser substituído por or eax,0x000000FF ou or ax,0x00FF .

Para a primeira ordem de instrução existe apenas uma possibilidade, e para a segunda ordem de instrução existem 3 possibilidades; Portanto, há um total de 4 possíveis permutações para escolher sem usar prefixos redundantes ou NOPs.

Para cada uma dessas 4 permutações, você pode adicionar variações com diferentes quantidades de prefixos redundantes e NOPs de um ou vários bytes para fazer com que ele termine em um alinhamento / s específico. Eu sou muito preguiçoso para fazer as contas, então vamos supor que talvez se expanda para 100 permutações possíveis.

E se você desse a cada uma dessas 100 permutações uma pontuação (baseada em coisas como quanto tempo levaria para executar, quão bem ela alinha a instrução após essa peça, se o tamanho ou a velocidade é importante, …). Isso pode include a segmentação de microarquitetura (por exemplo, talvez para algumas CPUs a permutação original interrompe a fusão de microinício e piora o código).

Você poderia gerar todas as permutações possíveis e dar-lhes uma pontuação e escolher a permutação com a melhor pontuação. Observe que isso pode não ser a permutação com o melhor alinhamento (se o alinhamento for menos importante do que outros fatores e só piorar o desempenho).

É claro que você pode dividir grandes programas em vários pequenos grupos de instruções lineares separadas por mudanças no stream de controle; e então faça essa “busca exaustiva pela permutação com a melhor pontuação” para cada pequeno grupo de instruções lineares.

O problema é que a ordem de instrução e a seleção de instruções são co-dependentes.

Para o exemplo acima, você não poderia replace mov al,0xFF até que nós tenhamos reordenado as instruções; e é fácil encontrar casos em que você não pode reordenar as instruções até depois de ter substituído (algumas) instruções. Isso dificulta uma busca exaustiva pela melhor solução, por qualquer definição de “melhor”, mesmo que você apenas se importe com o alinhamento e não se importe com o desempenho.

Depende da natureza do código.

Código pesado Floatingpoint

Prefixo AVX

Pode-se recorrer ao prefixo AVX mais longo para a maioria das instruções SSE. Observe que há uma penalidade fixa ao alternar entre o SSE e o AVX nos processadores intel [1] [2] . Isso requer o vzeroupper, que pode ser interpretado como outro NOP para código SSE ou código AVX que não requer os 128 bits mais altos.

SSE / AVX NOPS

NOPs típicos que eu posso pensar são:

  • XORPS o mesmo registro, use variações SSE / AVX para números inteiros desses
  • ANDPS o mesmo registro, use variações SSE / AVX para números inteiros desses