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

131

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

eleanora
fuente
3
Lo que Sulthan probablemente quiere decir es que 1) el compilador desenrolla el bucle y 2) una vez que se desenrolla ve que las operaciones de suma se pueden agrupar en una. Si el bucle no se desenrolla, las operaciones no se pueden agrupar.
Jean-François Fabre
3
Tener un número impar de bucles hace que el desenrollado sea más complicado, las últimas iteraciones tienen que hacerse especialmente. Eso podría ser suficiente para colocar el optimizador en un modo en el que ya no pueda reconocer el acceso directo. Es muy probable que primero tenga que agregar el código para el caso especial y luego tenga que eliminarlo nuevamente. Usar el optimizador entre las orejas siempre es mejor :)
Hans Passant
3
@HansPassant También está optimizado para cualquier número menor que 959.
eleanora
66
¿No se haría esto generalmente con la eliminación de la variable de inducción, en lugar de desenrollar una cantidad increíble? Desenrollarse por un factor de 959 es una locura.
harold
44
@eleanora Jugué con ese explorador de compilación y parece que se cumple lo siguiente (hablando solo de la instantánea de gcc): si el recuento de bucles es un múltiplo de 4 y al menos 72, entonces el bucle no se desenrolla (o más bien, se desenrolla por un factor de 4); de lo contrario, todo el bucle se reemplaza por una constante, incluso si el recuento del bucle es 2000000001. Mi sospecha: optimización prematura (como en, un "oye, un múltiplo de 4 prematuro, eso es bueno para desenrollar" que bloquea la optimización adicional frente a un más completo "¿Cuál es el problema con este circuito de todos modos?")
Hagen von Eitzen

Respuestas:

88

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
Grzegorz Szpetkowski
fuente
Gracias por esta muy buena respuesta. Como otros han señalado, gcc parece ser sensible al tamaño límite exacto. Por ejemplo, no puede eliminar el ciclo para 912 godbolt.org/g/EQJHvT . ¿Qué dice fdump-tree-cunroll-details en ese caso?
eleanora
De hecho, incluso 200 tiene este problema. Todo esto está en una instantánea de gcc 7 que proporciona godbolt. godbolt.org/g/Vg3SVs Esto no se aplica al sonido metálico en absoluto.
eleanora
13
Explicas la mecánica del pelado, pero no cuál es la relevancia del 960 o por qué hay incluso un límite
MM
1
@MM: El comportamiento de pelado es completamente diferente entre GCC 6.3.0 y el último snaphost. En el primer caso, sospecho firmemente que el límite codificado es forzado por el PARAM_MAX_COMPLETELY_PEEL_TIMESparámetro, que se define /gcc/params.def:321con el valor 16.
Grzegorz Szpetkowski
14
Es posible que desee mencionar por qué GCC se limita deliberadamente de esta manera. Específicamente, si desenrollas tus bucles de forma demasiado agresiva, el binario se hace más grande y es menos probable que quepa en el caché L1. Las fallas de caché son potencialmente bastante caras en relación con el ahorro de algunos saltos condicionales, suponiendo una buena predicción de ramificación (que tendrá, para un bucle típico).
Kevin
19

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.

Jean-François Fabre
fuente
1
entonces puedes concentrarte en esa not too highparte? Quiero decir, ¿por qué el riesgo no existe en caso de 100? He adivinado algo ... en mi comentario anterior ... ¿puede ser la razón de eso?
user2736738
Creo que el compilador no es consciente de la imprecisión de coma flotante que podría desencadenar. Supongo que es solo un límite de tamaño de instrucción. Tienes al max-unrolled-insnsladomax-unrolled-times
Jean-François Fabre
Ah, fue algo así como mi pensamiento o suposición ... deseo obtener un razonamiento más claro.
usuario2736738
55
Curiosamente, si cambia el floata un int, el compilador gcc es capaz de reducir la fuerza del bucle independientemente del recuento de iteraciones, debido a sus optimizaciones variables de inducción ( -fivopts). Pero esos no parecen funcionar para el floats.
Tavian Barnes
1
@CortAmmon Right, y recuerdo haber leído a algunas personas que estaban sorprendidas y molestas de que GCC usa MPFR para calcular con precisión números muy grandes, dando resultados bastante diferentes que las operaciones de coma flotante equivalentes que habrían acumulado errores y pérdidas de precisión. Demuestra que muchas personas calculan el punto flotante de la manera incorrecta.
Zan Lynx
12

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

chqrlie
fuente
He editado la pregunta para dejar en claro las versiones de gcc y clang que estaba usando. Ver godbolt.org/g/FfwWjL . Estoy usando -Ofast por ejemplo.
eleanora