Comment fonctionne l'implémentation GCC de modulo (%), et pourquoi n'utilise-t-elle pas l'instruction div?

Question

J'essayais de trouver comment calculer modulo 10 dans l'assemblage, donc j'ai compilé le code c suivant dans gcc pour voir ce qu'il a proposé.

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

À ma grande surprise j'ai eu

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) 

Où -4 (% ebp) ou "i" est l'entrée et -12 (% ebp) ou "j" est la réponse. J'ai testé cela et cela fonctionne quel que soit le nombre que vous faites -4 (% ebp).

Ma question est de savoir comment ce code fonctionne et comment est-il préférable d'utiliser l'opérande div.

Answer 1

Deuxième question en premier: div est une instruction très lente (plus de 20 cycles d'horloge). La séquence ci-dessus contient plus d'instructions, mais elles sont toutes relativement rapides, c'est donc une victoire nette en termes de vitesse.

Les cinq premières instructions (jusqu'à et y compris shrl) calculent i/10 (je vais vous expliquer comment dans une minute). Les instructions suivantes multiplient encore le résultat par 10, mais en évitant les instructions mul/imul (que ce soit une victoire ou non dépend du processeur exact que vous ciblez - les x86 récents ont des multiplicateurs très rapides, mais les plus anciens ne pas).

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 

Ceci est ensuite soustraite de i à nouveau pour obtenir i - (i/10)*10 qui est i % 10 (pour les nombres non signés). Finalement, sur le calcul de i/10: L'idée de base est de remplacer la division par 10 par une multiplication par 1/10. Le compilateur effectue une approximation à virgule fixe en multipliant par (2 ** 35/10 + 1) - c'est la valeur magique chargée dans edx, bien qu'elle soit sortie en tant que valeur signée même si elle est vraiment non signée - et résultat par 35. Cela donne le bon résultat pour tous les entiers de 32 bits.

Il y a des algorithmes pour déterminer ce type d'approximation qui garantit que l'erreur est inférieure à 1 (qui pour les entiers signifie qu'il est la valeur à droite) et GCC utilise évidemment un :)

Remarque finale: Si vous voulez réellement voir GCC calculer un modulo, faire la variable du diviseur (par exemple un paramètre de fonction) de sorte qu'il ne peut pas faire ce genre d'optimisation. Quoi qu'il en soit, sur x86, vous calculez modulo en utilisant div. div s'attend à ce que le dividende 64 bits dans edx:eax (haut 32 bits dans edx, bas 32 bits dans edx eax-clear à zéro si vous travaillez avec un nombre de 32 bits) et divise cela par n'importe quel opérande que vous spécifiez (par ex.div ebx divise edx:eax par ebx). Il renvoie le quotient en eax et le reste en edx. idiv fait la même chose pour les valeurs signées.

Answer 2

La première partie, jusqu'à shrl $3, %edx, implémente une division entière rapide de 10. Il existe quelques algorithmes différents qui fonctionnent lorsque le nombre avec lequel vous divisez est connu à l'avance. Notez que 858993459 est "0.2 * 2^32". La raison en est que, même s'il existe une instruction de division entière div/idiv dans l'ensemble d'instructions, elle est généralement très lente, plusieurs fois plus lente que la multiplication.

La deuxième partie calcule le reste en multipliant le résultat de la division par 10 (de manière indirecte, via des décalages et des additions, le compilateur pensant que ce sera plus rapide) et en soustrayant cela du nombre original.