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

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).

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

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.

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).