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

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 (troncal) -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 floatcon doublees 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).

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_TIMESque es 16. Puede anularse 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 -O3y / 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 lo tanto, la try_peel_loopfunción vuelve 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 al utilizar max-completely-peeled-insns=ny max-completely-peel-times=nparams:

max-completely-peeled-insns

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

max-completely-peel-times

El número máximo de iteraciones de un bucle para ser 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 lo observé, podría forzarlo a evaluar el valor final marcando el bucle con pragma desenrollado , 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

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

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

También puede jugar con el Explorador de compiladores de Godbolt para comparar cómo los diferentes compiladores y opciones impactan el código generado: gcc 6.2y icc 17aún en línea el código para 960, mientras queclang 3.9 que no lo hace (con la configuración predeterminada de Godbolt, en realidad se detiene en 73).