compiler - c to asm

GCC optó por la oportunidad perdida

Question

Estoy compilando este código C:

int mode; // use aa if true, else bb
int aa[2];
int bb[2];
inline int auto0() { return mode ? aa[0] : bb[0]; }
inline int auto1() { return mode ? aa[1] : bb[1]; }
int slow() { return auto1() - auto0(); }
int fast() { return mode ? aa[1] - aa[0] : bb[1] - bb[0]; }

Las funciones slow() y fast() tienen la intención de hacer lo mismo, aunque fast() hace con una instrucción de rama en lugar de dos. Quería comprobar si GCC colapsaría las dos ramas en una sola. Lo he intentado con GCC 4.4 y 4.7, con varios niveles de optimización, como -O2, -O3, -Os y -Ofast. Siempre da los mismos resultados extraños:

lento():

 movl mode(%rip), %ecx
testl %ecx, %ecx
je .L10
movl aa+4(%rip), %eax
movl aa(%rip), %edx
subl %edx, %eax
ret
.L10:
movl bb+4(%rip), %eax
movl bb(%rip), %edx
subl %edx, %eax
ret

rápido():

 movl mode(%rip), %esi
testl %esi, %esi
jne .L18
movl bb+4(%rip), %eax
subl bb(%rip), %eax
ret
.L18:
movl aa+4(%rip), %eax
subl aa(%rip), %eax
ret

De hecho, solo se genera una rama en cada función. Sin embargo, slow() parece ser inferior de una manera sorprendente: utiliza una carga extra en cada rama, para aa[0] y bb[0] . El código fast() usa directamente desde la memoria en los subl sin cargarlos primero en un registro. Entonces slow() usa un registro extra y una instrucción adicional por llamada.

Un simple micro-benchmark muestra que llamar fast() mil millones de veces lleva 0,7 segundos, frente a 1,1 segundos para slow() . Estoy usando un Xeon E5-2690 a 2.9 GHz.

¿Por qué debería ser esto? ¿Puedes modificar mi código fuente de alguna manera para que GCC haga un mejor trabajo?

Editar: aquí están los resultados con clang 4.2 en Mac OS:

lento():

 movq _aa@GOTPCREL(%rip), %rax ; rax = aa (both ints at once)
movq _bb@GOTPCREL(%rip), %rcx ; rcx = bb
movq _mode@GOTPCREL(%rip), %rdx ; rdx = mode
cmpl $0, (%rdx) ; mode == 0 ?
leaq 4(%rcx), %rdx ; rdx = bb[1]
cmovneq %rax, %rcx ; if (mode != 0) rcx = aa
leaq 4(%rax), %rax ; rax = aa[1]
cmoveq %rdx, %rax ; if (mode == 0) rax = bb
movl (%rax), %eax ; eax = xx[1]
subl (%rcx), %eax ; eax -= xx[0]

rápido():

 movq _mode@GOTPCREL(%rip), %rax ; rax = mode
cmpl $0, (%rax) ; mode == 0 ?
je LBB1_2 ; if (mode != 0) {
movq _aa@GOTPCREL(%rip), %rcx ; rcx = aa
jmp LBB1_3 ; } else {
LBB1_2: ; // (mode == 0)
movq _bb@GOTPCREL(%rip), %rcx ; rcx = bb
LBB1_3: ; }
movl 4(%rcx), %eax ; eax = xx[1]
subl (%rcx), %eax ; eax -= xx[0]

Interesante: clang genera condicionales sin ramas para slow() pero una rama para fast() ! Por otro lado, slow() hace tres cargas (dos de las cuales son especulativas, una será innecesaria) frente a dos para fast() . La implementación fast() es más "obvia" y, como con GCC, es más corta y usa un registro menos.

GCC 4.7 en Mac OS generalmente sufre el mismo problema que en Linux. Sin embargo, utiliza el mismo patrón "carga 8 bytes luego dos veces extrae 4 bytes" como Clang en Mac OS. Eso es algo interesante, pero no muy relevante, ya que el problema original de emitir subl con dos registros en lugar de una memoria y un registro es el mismo en cualquiera de las plataformas para GCC.

Answer 1

¿Ha intentado modificar los parámetros de los compiladores internos (--param name = value en la página man)? Esos no se cambian con ningún nivel de optimizaciones (con tres excepciones menores).

Algunos de ellos controlan la reducción / deduplicación del código.

Para algunas optimizaciones en esta sección, puede leer cosas como «valores más grandes pueden aumentar exponencialmente el tiempo de compilación».

Answer 2

La razón es que en el código intermedio inicial, emitido para slow() , la carga de memoria y la resta están en diferentes bloques básicos:

slow ()
{
int D.1405;
int mode.3;
int D.1402;
int D.1379;
# BLOCK 2 freq:10000
mode.3_5 = mode;
if (mode.3_5 != 0)
goto <bb 3>;
else
goto <bb 4>;
# BLOCK 3 freq:5000
D.1402_6 = aa[1];
D.1405_10 = aa[0];
goto <bb 5>;
# BLOCK 4 freq:5000
D.1402_7 = bb[1];
D.1405_11 = bb[0];
# BLOCK 5 freq:10000
D.1379_3 = D.1402_17 - D.1405_12;
return D.1379_3;
}

mientras que en fast() están en el mismo bloque básico:

fast ()
{
int D.1377;
int D.1376;
int D.1374;
int D.1373;
int mode.1;
int D.1368;
# BLOCK 2 freq:10000
mode.1_2 = mode;
if (mode.1_2 != 0)
goto <bb 3>;
else
goto <bb 4>;
# BLOCK 3 freq:3900
D.1373_3 = aa[1];
D.1374_4 = aa[0];
D.1368_5 = D.1373_3 - D.1374_4;
goto <bb 5>;
# BLOCK 4 freq:6100
D.1376_6 = bb[1];
D.1377_7 = bb[0];
D.1368_8 = D.1376_6 - D.1377_7;
# BLOCK 5 freq:10000
return D.1368_1;
}

GCC se basa en la combinación de instrucciones para manejar casos como este (es decir, aparentemente no en el pase de optimización de mirilla) y la combinación de trabajos en el alcance de un bloque básico. Es por eso que la resta y la carga se combinan en una sola entrada en fast() y ni siquiera se consideran para combinar en slow() .

Más tarde, en el paso de reordenamiento del bloque básico, la resta en slow() se duplica y se mueve a los bloques básicos, que contienen las cargas. Ahora hay una oportunidad para que el combinador combine la carga y la resta, pero desafortunadamente, el pase combinador no se ejecuta nuevamente (y tal vez no se puede ejecutar tan tarde en el proceso de compilación con los registros duros ya asignados y esas cosas).

Answer 3

No tengo una respuesta en cuanto a por qué GCC no puede optimizar el código de la forma en que lo desea, pero tengo una forma de reorganizar su código para lograr un rendimiento similar. En lugar de organizar su código de la manera en que lo hizo en slow() o fast() , le recomendaría que defina una función en línea que devuelva aa o bb función del mode sin necesidad de una bifurcación:

inline int * xx () { static int *xx[] = { bb, aa }; return xx[!!mode]; }
inline int kwiky(int *xx) { return xx[1] - xx[0]; }
int kwik() { return kwiky(xx()); }

Cuando compilado por GCC 4.7 con -O3 :

 movl mode, %edx
xorl %eax, %eax
testl %edx, %edx
setne %al
movl xx.1369(,%eax,4), %edx
movl 4(%edx), %eax
subl (%edx), %eax
ret

Con la definición de xx() , puede redefinir auto0() y auto1() manera:

inline int auto0() { return xx()[0]; }
inline int auto1() { return xx()[1]; }

Y, a partir de esto, debería ver que slow() ahora compila en código similar o idéntico a kwik() .