Código muerto
Hola amigos digitales, hoy vamos a hablar de un pequeño problema de optimización en Visual C.
Seguramente ya conozcan lo que es la eliminación de código muerto, pero por las dudas (y para que este post llegue al menos a las 10 lineas) voy a hacer una breve explicación.
Dead code elimination es una optimización muy utilizada que se encarga de eliminar código que realmente no afecta al programa. Por ejemplo, si tenemos:
x >>= 1;
El compilador eliminara el or ya que ese bit se perderá cuando se realice el shift. Entendido esto sigamos con los nuestro…
A partir de C99 (o por extensiones en algunos compiladores) existe el tipo «long long» que es de al menos 64bits. El tema es que en arquitecturas de 32bits el compilador debe seccionar este tipo en dos y generar código para trabajar como si se tratase de un solo valor de 64bits.
Curiosamente parece que el VC no se preocupa mucho por optimizar este tipo de código, consideremos el siguiente ejemplo:
int main(int argc, char *argv[])
{
unsigned int x = atoi(argv[1]);
unsigned __int64 y, z = strtoui64(argv[2], NULL, 10);
y = (unsigned __int64) x;
z -= 2;
if (z < y)
return 1;
return 0;
}
He utilizado las llamadas a atoi y strtoui64 por no poner valores constantes, ya que necesitamos compilar el código con optimizaciones y si se aplica propagación de valores se terminaría eliminando todo el código.
En este ejemplo se toma un entero de 32 bits y se convierte a un entero sin signo de 64bits, luego te toma otro entero sin signo de 64 y se le resta 2, por útlimo se comparan las dos variables.
Utilizando Visual Studio 2k8 y compilando con /O2, se genera el siguiente código:
push esi
; Line 5
mov esi, DWORD PTR _argv$[esp]
mov eax, DWORD PTR [esi+4]
push edi
push eax
call _atoi
; Line 6
mov ecx, DWORD PTR [esi+8]
push 10 ; 0000000aH
push 0
push ecx
mov edi, eax
call _strtoui64
; Line 11
cdq
add esp, 16 ; 00000010H
add eax, -2 ; fffffffeH
adc edx, -1
xor ecx, ecx
cmp edx, ecx
ja SHORT $LN1@main
jb SHORT $LN4@main
cmp eax, edi
jae SHORT $LN1@main
$LN4@main:
pop edi
; Line 12
mov eax, 1
pop esi
; Line 15
ret 0
$LN1@main:
pop edi
; Line 14
xor eax, eax
pop esi
; Line 15
ret 0
Podemos observar que el par edx:eax representa z, edi representa x y ecx:edi a y. Por lo tanto la expresión z < y es equivalente a edx:eax < ecx:edi.
Para realizar la comparación tenemos realmente un máximo de tres expresiones a evaluar:
- edx > ecx: si la expresión es verdadera evitamos el resto de las comparaciones.
- edx < ecx: si la expresión es verdadera sabemos evitamos la comparación final.
En este punto sabemos que edx == ecx y procedemos a comparar la parte menos significativa de las dos variables:
- eax < edi: el resultado de esta expresión determinara si z < y.
Hasta aquí todo perfecto para comparar dos variables de 64bits, el problema es que el VC no se da cuenta de algunos casos particulares, como el de este ejemplo donde uno de los valores se obtiene a partir de un cast de un valor de 32bits. El cast garantiza que la parte alta va a ser siempre cero por lo que se puede reducir la cantidad de expresiones. VC no solo no se da cuenta, sino que ademas genera el caso imposible edx < 0.
Para este tipo de casos el compilador debería reducir el código a un máximo de dos expresiones:
- edx != 0: si es verdadero se evita la segunda comparación.
- eax < edi
Para cerrar, he probado un código similar en gcc 4.3.3 con flag -O2:
int main(int argc, char *argv[])
{
unsigned int x = atoi(argv[1]);
unsigned long long y, z = atoll(argv[2]);
y = (unsigned long long) x;
z -= 2;
if (z < y)
return 1;
return 0;
}
El resultado fue:
leal 4(%esp), %ecx
andl $-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
subl $24, %esp
movl %ecx, -12(%ebp)
movl %esi, -4(%ebp)
movl %ebx, -8(%ebp)
movl 4(%ecx), %ebx
movl 4(%ebx), %eax
movl %eax, (%esp)
call atoi
movl %eax, %esi
movl 8(%ebx), %eax
movl %eax, (%esp)
call atoll
movl $1, %ecx
movl %eax, %edx
sarl $31, %edx
addl $-2, %eax
adcl $-1, %edx
testl %edx, %edx
jne .L3
cmpl %eax, %esi
jbe .L3
.L2:
movl %ecx, %eax
movl -12(%ebp), %ecx
movl -8(%ebp), %ebx
movl -4(%ebp), %esi
movl %ebp, %esp
popl %ebp
leal -4(%ecx), %esp
ret
.p2align 4,,7
.p2align 3
.L3:
xorl %ecx, %ecx
jmp .L2
Como se puede observar el gcc realiza este tipo de optimizaciones.
Bueno eso fue todo el trolling por hoy, saludos digitales 🙂