¿Cómo funciona la implementación de módulo (%) de GCC y por qué no utiliza la instrucción div?

Question

Estaba tratando de calcular cómo calcular el módulo 10 en el ensamblaje, así que compilé el siguiente código c en gcc para ver qué ocurrió.

unsigned int i=999; 
unsigned int j=i%10; 

Para mi sorpresa me dieron

movl -4(%ebp), %ecx 
movl $-858993459, %edx 
movl %ecx, %eax 
mull %edx 
shrl $3, %edx 
movl %edx, %eax 
sall $2, %eax 
addl %edx, %eax 
addl %eax, %eax 
movl %ecx, %edx 
subl %eax, %edx 
movl %edx, %eax 
movl %eax, -12(%ebp) 

Dónde -4 (% ebp) o "i" es la entrada y -12 (% ebp) o "j" es la respuesta. Lo he probado y funciona, sin importar el número que hagas -4 (% ebp).

Mi pregunta es cómo funciona este código y cómo es mejor que usar el operando div.

Answer 1

Segunda pregunta primero: div es una instrucción muy lenta (más de 20 ciclos de reloj). La secuencia anterior consiste en más instrucciones, pero todas son relativamente rápidas, por lo que es una ganancia neta en términos de velocidad.

Las primeras cinco instrucciones (hasta e incluyendo el shrl) calculan i/10 (explicaré cómo hacerlo en un minuto).

Las siguientes instrucciones vuelven a multiplicar el resultado por 10, pero evitando las instrucciones mul/imul (el hecho de que gane o no depende del procesador exacto al que se dirige), los x86 más nuevos tienen multiplicadores muy rápidos, pero los más antiguos no lo haga).

movl %edx, %eax ; eax=i/10 
sall $2, %eax  ; eax=(i/10)*4 
addl %edx, %eax ; eax=(i/10)*4 + (i/10) = (i/10)*5 
addl %eax, %eax ; eax=(i/10)*5*2 = (i/10)*10 

Esto se resta entonces de i de nuevo para obtener i - (i/10)*10 que es i % 10 (para números sin signo).

Finalmente, en el cálculo de i/10: La idea básica es reemplazar la división por 10 con la multiplicación por 1/10. El compilador hace una aproximación de punto fijo de esto al multiplicar por (2 ** 35/10 + 1) - ese es el valor mágico cargado en edx, aunque se emite como un valor firmado a pesar de que en realidad no está firmado, y el desplazamiento a la derecha resultado por 35. Esto resulta para dar el resultado correcto para todos los enteros de 32 bits.

Hay algoritmos para determinar este tipo de aproximación que garantizan que el error es inferior a 1 (que para los enteros significa que es el valor correcto) y GCC, obviamente, utiliza una :) Observación final

: Si desea realidad ver GCC calcular un módulo, hacer que la variable del divisor (por ejemplo, un parámetro de función) por lo que no puede hacer este tipo de optimización. De todos modos, en x86, calcula el módulo usando div. div espera que el dividendo de 64 bits en edx:eax (32 bits en edx, 32 bits en eax - clear edx a cero si está trabajando con un número de 32 bits) y lo divide por el operando que especifique (p. Ej.div ebx divide edx:eax por ebx). Devuelve el cociente en eax y el resto en edx. idiv hace lo mismo para los valores firmados.

Answer 2

La primera parte, hasta shrl $3, %edx, implementa una división entera rápida por 10. Hay algunos algoritmos diferentes que funcionan cuando el número por el que se divide se conoce de antemano. Tenga en cuenta que 858993459 es "0.2 * 2^32". La razón para hacer esto es porque, aunque hay una instrucción de división entera div/idiv en el conjunto de instrucciones, por lo general es muy lenta, varias veces más lenta que la multiplicación.

La segunda parte calcula el resto multiplicando el resultado de la división por 10 (de forma indirecta, mediante cambios y agrega; presumiblemente el compilador cree que será más rápido) y luego restando ese del número original.