¿Por qué se optimiza un bucle simple cuando el límite es 959 pero no 960?

gcc optimization

Question

Considere este simple ciclo:

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

Si compila con gcc 7 (instantánea) o clang (trunk) con -march=core-avx2 -Ofast obtendrá algo muy similar a.

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

En otras palabras, solo establece la respuesta a 960 sin bucles.

Sin embargo, si cambia el código a:

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

¿El ensamblaje producido realmente realiza la suma de bucle? Por ejemplo, clang da:

.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 qué es esto y por qué es exactamente lo mismo para clang y gcc?

El límite para el mismo ciclo si reemplaza float con double es 479. Esto es lo mismo para gcc y clang nuevamente.

Actualización 1

Resulta que gcc 7 (instantánea) y clang (trunk) se comportan de manera muy diferente. clang optimiza los bucles para todos los límites inferiores a 960 por lo que puedo decir. gcc por otro lado es sensible al valor exacto y no tiene un límite superior. Por ejemplo, no optimiza el ciclo cuando el límite es 200 (así como muchos otros valores) pero lo hace cuando el límite es 202 y 20002 (así como muchos otros valores).

Answer 1

TL; DR

De manera predeterminada, la instantánea actual GCC 7 se comporta de manera inconsistente, mientras que las versiones anteriores tienen un límite predeterminado debido a PARAM_MAX_COMPLETELY_PEEL_TIMES , que es 16. Se puede anular desde la línea de comandos.

La razón del límite es evitar el desenrollamiento de bucles demasiado agresivo, que puede ser una espada de doble filo .

Versión GCC <= 6.3.0

La opción de optimización relevante para GCC es -fpeel-loops , que se habilita indirectamente junto con el indicador -Ofast (el énfasis es mío):

Pela los bucles para los cuales hay suficiente información para que no se acumulen demasiado (de los comentarios de perfil o análisis estático ) También activa el pelado completo del bucle (es decir, la eliminación completa de bucles con un pequeño número constante de iteraciones ).

Habilitado con -O3 y / o -fprofile-use .

Se pueden obtener más detalles agregando -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

El mensaje es 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;
    }

por try_peel_loop tanto, la función try_peel_loop devuelve false .

Se puede alcanzar una salida más detallada con -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

Es posible ajustar los límites mediante el uso de max-completely-peeled-insns=n y max-completely-peel-times=n params:

max-completely-peeled-insns

El número máximo de entradas de un bucle completamente pelado.

max-completely-peel-times

El número máximo de iteraciones de un bucle para que sea adecuado para el pelado completo.

Para obtener más información sobre insns, puede consultar el Manual interno de GCC .

Por ejemplo, si compila con las siguientes opciones:

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

entonces el código se convierte en:

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

Sonido metálico

No estoy seguro de lo que Clang realmente hace y cómo ajustar sus límites, pero como observé, podría forzarlo a evaluar el valor final marcando el bucle con desenrollar pragma , y lo eliminará por completo:

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

resultados en:

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

Answer 2

Después de leer el comentario de Sulthan, supongo que:

1. El compilador desenrolla completamente el bucle si el contador del bucle es constante (y no demasiado alto)

2. Una vez que se desenrolla, el compilador ve que las operaciones de suma se pueden agrupar en una.

Si el ciclo no se desenrolla por alguna razón (aquí: generaría demasiadas declaraciones con 1000 ), las operaciones no se pueden agrupar.

El compilador podría ver que el desenrollado de 1000 declaraciones equivale a una sola adición, pero los pasos 1 y 2 descritos anteriormente son dos optimizaciones separadas, por lo que no puede correr el "riesgo" de desenrollar, sin saber si las operaciones se pueden agrupar (ejemplo: una llamada de función no se puede agrupar).

Nota: Este es un caso de esquina: ¿Quién usa un bucle para agregar lo mismo nuevamente? En ese caso, no confíe en el posible compilador de desenrollar / optimizar; escriba directamente la operación adecuada en una instrucción.

Answer 3

Muy buena pregunta!

Parece que has alcanzado un límite en el número de iteraciones u operaciones que el compilador intenta alinear al simplificar el código. Según lo documentado por Grzegorz Szpetkowski, existen formas específicas del compilador para ajustar estos límites con pragmas u opciones de línea de comando.

También puedes jugar con el Explorador de compiladores de Godbolt para comparar cómo los diferentes compiladores y opciones impactan el código generado: gcc 6.2 e icc 17 todavía alinean el código para 960, mientras que clang 3.9 no (con la configuración predeterminada de Godbolt, en realidad deja de alinearse en 73 )