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