Por que um loop simples é otimizado quando o limite é 959, mas não 960?

131

Considere este loop simples:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 959; i++)
    p += 1;
  return p;
}

Se você compilar com o gcc 7 (snapshot) ou clang (trunk), -march=core-avx2 -Ofastobterá algo muito semelhante.

.LCPI0_0:
        .long   1148190720              # float 960
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

Em outras palavras, apenas define a resposta para 960 sem repetir.

No entanto, se você alterar o código para:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 960; i++)
    p += 1;
  return p;
}

A montagem produzida realmente executa a soma do loop? Por exemplo, clang dá:

.LCPI0_0:
        .long   1065353216              # float 1
.LCPI0_1:
        .long   1086324736              # float 6
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        vxorps  ymm1, ymm1, ymm1
        mov     eax, 960
        vbroadcastss    ymm2, dword ptr [rip + .LCPI0_1]
        vxorps  ymm3, ymm3, ymm3
        vxorps  ymm4, ymm4, ymm4
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        vaddps  ymm0, ymm0, ymm2
        vaddps  ymm1, ymm1, ymm2
        vaddps  ymm3, ymm3, ymm2
        vaddps  ymm4, ymm4, ymm2
        add     eax, -192
        jne     .LBB0_1
        vaddps  ymm0, ymm1, ymm0
        vaddps  ymm0, ymm3, ymm0
        vaddps  ymm0, ymm4, ymm0
        vextractf128    xmm1, ymm0, 1
        vaddps  ymm0, ymm0, ymm1
        vpermilpd       xmm1, xmm0, 1   # xmm1 = xmm0[1,0]
        vaddps  ymm0, ymm0, ymm1
        vhaddps ymm0, ymm0, ymm0
        vzeroupper
        ret

Por que isso e por que é exatamente o mesmo para clang e gcc?


O limite para o mesmo loop se você substituir floatpor doubleé 479. É o mesmo para gcc e clang novamente.

Atualização 1

Acontece que o gcc 7 (instantâneo) e o clang (tronco) se comportam de maneira muito diferente. clang otimiza os loops para todos os limites inferiores a 960, tanto quanto eu posso dizer. O gcc, por outro lado, é sensível ao valor exato e não tem um limite superior. Por exemplo, ele não otimiza o loop quando o limite é 200 (assim como muitos outros valores), mas o faz quando o limite é 202 e 20002 (assim como muitos outros valores).

eleanora
fonte
3
O que Sulthan provavelmente significa é que 1) o compilador desenrola o loop e 2) uma vez desenrolado, vê que as operações de soma podem ser agrupadas em uma. Se o loop não for desenrolado, as operações não poderão ser agrupadas.
Jean-François Fabre
3
Ter um número ímpar de loops torna o desenrolar mais complicado, as últimas iterações precisam ser feitas especialmente. Isso pode ser suficiente para colocar o otimizador em um modo em que ele não possa mais reconhecer o atalho. É bem provável que primeiro seja necessário adicionar o código para o caso especial e, em seguida, será necessário removê-lo novamente. Usar o otimizador entre as orelhas é sempre melhor :)
Hans Passant
3
@HansPassant-se também optimizada para qualquer número menor do que 959.
eleanora
6
Isso normalmente não seria feito com a eliminação de variáveis ​​de indução, em vez de desenrolar uma quantidade insana? Desenrolar por um fator de 959 é uma loucura.
Harold
4
@eleanora Eu brinquei com esse compilre explorer e o seguinte parece válido (falando apenas do instantâneo gcc): se a contagem de loop for um múltiplo de 4 e pelo menos 72, o loop não será desenrolado (ou melhor, desenrolado por um fator de 4); caso contrário, o loop inteiro será substituído por uma constante - mesmo que a contagem de loop seja 2000000001. Minha suspeita: otimização prematura (como um prematuro "ei, um múltiplo de 4, isso é bom para desenrolar" que bloqueia a otimização adicional vs. mais aprofundado "Qual é o problema desse loop, afinal?")
Hagen von Eitzen

Respostas:

88

TL; DR

Por padrão, o instantâneo atual GCC 7 se comporta de forma inconsistente, enquanto as versões anteriores têm limite padrão devido a PARAM_MAX_COMPLETELY_PEEL_TIMES , que é 16. Ele pode ser substituído na linha de comando.

A lógica do limite é impedir o desenrolar excessivo do loop, que pode ser uma faca de dois gumes .

Versão do GCC <= 6.3.0

A opção de otimização relevante para o GCC é -fpeel-loops, que é ativada indiretamente junto com o sinalizador -Ofast(a ênfase é minha):

Descasca loops para os quais há informações suficientes para que eles não rolem muito (a partir do feedback do perfil ou análise estática ). Também ativa o descascamento completo do loop (ou seja, remoção completa de loops com pequeno número constante de iterações ).

Ativado com -O3e / ou -fprofile-use.

Mais detalhes podem ser obtidos adicionando -fdump-tree-cunroll:

$ head test.c.151t.cunroll 

;; Function f (f, funcdef_no=0, decl_uid=1919, cgraph_uid=0, symbol_order=0)

Not peeling: upper bound is known so can unroll completely

A mensagem é de /gcc/tree-ssa-loop-ivcanon.c:

if (maxiter >= 0 && maxiter <= npeel)
    {
      if (dump_file)
        fprintf (dump_file, "Not peeling: upper bound is known so can "
         "unroll completely\n");
      return false;
    }

conseqüentemente try_peel_loop função retorna false.

Saída mais detalhada pode ser alcançada com -fdump-tree-cunroll-details:

Loop 1 iterates 959 times.
Loop 1 iterates at most 959 times.
Not unrolling loop 1 (--param max-completely-peeled-times limit reached).
Not peeling: upper bound is known so can unroll completely

É possível ajustar os limites usando max-completely-peeled-insns=ne max-completely-peel-times=nparams:

max-completely-peeled-insns

O número máximo de insns de um loop completamente descascado.

max-completely-peel-times

O número máximo de iterações de um loop para ser adequado para descamação completa.

Para saber mais sobre insns, você pode consultar Manual interno do GCC .

Por exemplo, se você compilar com as seguintes opções:

-march=core-avx2 -Ofast --param max-completely-peeled-insns=1000 --param max-completely-peel-times=1000

então o código se transforma em:

f:
        vmovss  xmm0, DWORD PTR .LC0[rip]
        ret
.LC0:
        .long   1148207104

Clang

Não sei ao certo o que o Clang realmente faz e como ajustar seus limites, mas como observei, você pode forçá-lo a avaliar o valor final marcando o loop com pragma de desenrolamento , e ele o removerá completamente:

#pragma unroll
for (int i = 0; i < 960; i++)
    p++;

resulta em:

.LCPI0_0:
        .long   1148207104              # float 961
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret
Grzegorz Szpetkowski
fonte
Obrigado por esta resposta muito agradável. Como outros já apontaram, o gcc parece ser sensível ao tamanho limite exato. Por exemplo, falha na eliminação do loop para 912 godbolt.org/g/EQJHvT . O que diz fdump-tree-cunroll-details nesse caso?
eleanora
De fato, até 200 tem esse problema. Isso é tudo em um instantâneo do gcc 7 que o godbolt fornece. godbolt.org/g/Vg3SVs Isso não se aplica ao clang.
Eleanora
13
Você explica a mecânica do peeling, mas não o que a relevância de 960 é ou porque há ainda um limite em tudo
MM
1
@MM: O comportamento de peeling é completamente diferente entre o GCC 6.3.0 e o snaphost mais recente. No caso do primeiro, suspeito fortemente, que o limite codificados é imposta pelo PARAM_MAX_COMPLETELY_PEEL_TIMESparâmetro, que é definido no /gcc/params.def:321com o valor 16.
Grzegorz Szpetkowski
14
Você pode mencionar por que o GCC se limita deliberadamente dessa maneira. Especificamente, se você desenrola seus loops de forma muito agressiva, o binário aumenta e é menos provável que você se encaixe no cache L1. As falhas de cache são potencialmente muito caras em relação a salvar alguns saltos condicionais, assumindo uma boa previsão de ramificação (que você terá, para um loop típico).
Kevin
19

Depois de ler o comentário de Sulthan, acho que:

  1. O compilador desenrola totalmente o loop se o contador de loop for constante (e não muito alto)

  2. Uma vez desenrolado, o compilador vê que as operações de soma podem ser agrupadas em uma.

Se o loop não for desenrolado por algum motivo (aqui: ele geraria muitas instruções com 1000 ), as operações não poderão ser agrupadas.

O compilador pode ver que o desenrolar de 1000 instruções equivale a uma única adição, mas as etapas 1 e 2 descritas acima são duas otimizações separadas, portanto, não pode assumir o "risco" de desenrolar, sem saber se as operações podem ser agrupadas (exemplo: uma chamada de função não pode ser agrupada).

Nota: Este é um caso de canto: quem usa um loop para adicionar a mesma coisa novamente? Nesse caso, não confie no compilador possível de desenrolar / otimizar; escreva diretamente a operação correta em uma instrução.

Jean-François Fabre
fonte
1
então você pode se concentrar nessa not too highparte? Quero dizer, por que o risco não existe em caso de 100? Eu adivinhei algo ... no meu comentário acima .. pode ser a razão para isso?
user2736738
Penso que o compilador não está ciente da imprecisão do ponto flutuante que poderia desencadear. Eu acho que é apenas um limite de tamanho de instrução. Você tem max-unrolled-insnsao ladomax-unrolled-times
Jean-François Fabre
Ah, foi o meu pensamento ou palpite ... desejo obter um raciocínio mais claro.
usuário2736738
5
Curiosamente, se você alterar floatpara um int, o compilador gcc poderá reduzir com força o loop, independentemente da contagem de iterações, devido às otimizações das variáveis ​​de indução ( -fivopts). Mas esses não parecem funcionar para floats.
Tavian Barnes
1
@CortAmmon Certo, e lembro-me de ler algumas pessoas que ficaram surpresas e chateadas com o fato de o GCC usar o MPFR para calcular com precisão números muito grandes, fornecendo resultados bastante diferentes do que as operações equivalentes de ponto flutuante que teriam acumulado erro e perda de precisão. Isso mostra que muitas pessoas calculam o ponto flutuante da maneira errada.
Zan Lynx
12

Muito boa pergunta!

Você parece ter atingido um limite no número de iterações ou operações que o compilador tenta alinhar ao simplificar o código. Conforme documentado por Grzegorz Szpetkowski, existem maneiras específicas do compilador de ajustar esses limites com pragmas ou opções de linha de comando.

Você também pode jogar com o Compiler Explorer do Godbolt para comparar como diferentes compiladores e opções afetam o código gerado: gcc 6.2e icc 17ainda alinhar o código para o 960, enquanto clang 3.9isso não afeta (com a configuração padrão do Godbolt, ele na verdade para de inlinhar em 73).

chqrlie
fonte
Editei a pergunta para deixar clara as versões do gcc e do clang que estava usando. Veja godbolt.org/g/FfwWjL . Estou usando -Ofast, por exemplo.
22817 eleanora