Pourquoi GCC utilise-t-il la multiplication par un nombre étrange dans l’implémentation de la division entière?

J’ai lu sur les opérations d’assemblage div et mul et j’ai décidé de les voir en action en écrivant un programme simple en C:

Division de fichier.c

 #include  #include  int main() { size_t i = 9; size_t j = i / 5; printf("%zu\n",j); return 0; } 

Et puis générer le code du langage d’assemblage avec:

 gcc -S division.c -O0 -masm=intel 

Mais en regardant le fichier division.s généré, il ne contient aucune opération div! Au lieu de cela, il fait une sorte de magie noire avec des nombres décalés et des nombres magiques. Voici un extrait de code qui calcule i/5 :

 mov rax, QWORD PTR [rbp-16] ; Move i (=9) to RAX movabs rdx, -3689348814741910323 ; Move some magic number to RDX (?) mul rdx ; Multiply 9 by magic number mov rax, rdx ; Take only the upper 64 bits of the result shr rax, 2 ; Shift these bits 2 places to the right (?) mov QWORD PTR [rbp-8], rax ; Magically, RAX contains 9/5=1 now, ; so we can assign it to j 

Que se passe t-il ici? Pourquoi GCC n’utilise-t-il pas div? Comment génère-t-il ce nombre magique et pourquoi tout fonctionne-t-il?

La division d’entiers est l’une des opérations arithmétiques les plus lentes que vous pouvez effectuer sur un processeur moderne, avec une latence allant jusqu’à des dizaines de cycles et un débit médiocre. (Pour x86, voir les tableaux d’instructions et le guide de microarchie d’Agner Fog ).

Si vous connaissez le diviseur à l’avance, vous pouvez éviter la division en la remplaçant par un ensemble d’autres opérations (multiplications, ajouts et décalages) qui ont un effet équivalent. Même si plusieurs opérations sont nécessaires, il est souvent encore plus rapide que la division entière elle-même.

Implémenter l’opérateur C / C de cette façon au lieu d’une séquence multi-instructions impliquant div est juste le moyen par défaut de GCC de faire la division par constantes. Il ne nécessite pas d’optimiser les opérations et ne change rien, même pour le débogage. (L’utilisation de -Os pour un code de petite taille a cependant pour effet que GCC utilise div .) Utiliser un inverse multiplicatif au lieu de division lea utiliser lea au lieu de mul et add

Par conséquent, vous ne voyez généralement div ou idiv dans la sortie que si le diviseur n’est pas connu à la compilation.

Pour plus d’informations sur la façon dont le compilateur génère ces séquences, ainsi que sur le code pour vous permettre de les générer vous-même (presque certainement inutile sauf si vous travaillez avec un compilateur braindead ), consultez libdivide .

La division par 5 équivaut à multiplier 1/5, ce qui revient à multiplier par 4/5 et à déplacer 2 bits vers la droite. La valeur concernée est CCCCCCCCCCCCD en hexadécimal, qui est la représentation binary de 4/5 si elle est placée après un point hexadécimal (c’est-à-dire que le binary pour les quatre cinquièmes est 0.110011001100 récurrent – voir ci-dessous pourquoi). Je pense que vous pouvez le prendre d’ici! Vous voudrez peut-être vérifier l’ arithmétique à virgule fixe (notez cependant qu’elle est arrondie à un entier à la fin.

Pour ce faire, la multiplication est plus rapide que la division, et lorsque le diviseur est fixe, il s’agit d’un itinéraire plus rapide.

Voir Multiplication réciproque, un tutoriel pour une description détaillée de son fonctionnement, expliquant en termes de point fixe. Il montre comment fonctionne l’algorithme de recherche de réciprocité et comment gérer la division signée et le modulo.

Considérons un instant pourquoi 0.CCCCCCCC... (hex) ou 0.110011001100... binary est 4/5. Diviser la représentation binary par 4 (décalage à droite 2), et nous aurons 0.001100110011... qui par inspection sortingviale peut être ajouté à l’original pour obtenir 0.111111111111... , ce qui est évidemment égal à 1, de la même manière 0.9999999... en décimal est égal à un. Par conséquent, nous soaps que x + x/4 = 1 , donc 5x/4 = 1 , x=4/5 . Ceci est alors représenté comme CCCCCCCCCCCCD en hexadécimal pour l’arrondi (comme le chiffre binary au-delà du dernier présent serait un 1 ).

En général, la multiplication est beaucoup plus rapide que la division. Donc, si nous pouvons nous en sortir en multipliant par la réciproque, nous pouvons accélérer considérablement la division par une constante

Une ride est que nous ne pouvons pas représenter exactement la réciproque (à moins que la division soit par une puissance de deux, mais dans ce cas, nous pouvons généralement convertir la division en un décalage binary). Donc, pour assurer des réponses correctes, nous devons faire attention à ce que l’erreur dans notre réciproque ne provoque pas d’erreurs dans notre résultat final.

-3689348814741910323 est 0xCCCCCCCCCCCCCCCD qui est une valeur d’un peu plus de 4/5 exprimée en 0,64 point fixe.

Lorsque nous multiplions un entier de 64 bits par un nombre à 0,64, nous obtenons un résultat de 64,64. Nous tronquons la valeur en un entier de 64 bits (arrondissant effectivement vers zéro) et effectuons ensuite un autre décalage qui divise par quatre et encore en tronquant En examinant le niveau de bit, il est clair que nous pouvons traiter les deux troncatures comme une seule troncature.

Cela nous donne clairement au moins une approximation de la division par 5 mais cela nous donne-t-il une réponse exacte correctement arrondie vers zéro?

Pour obtenir une réponse exacte, l’erreur doit être suffisamment faible pour ne pas pousser la réponse sur une limite d’arrondi.

La réponse exacte à une division par 5 aura toujours une fraction de 0, 1/5, 2/5, 3/5 ou 4/5. Par conséquent, une erreur positive inférieure à 1/5 du résultat multiplié et décalé ne poussera jamais le résultat sur une limite arrondie.

L’erreur dans notre constante est (1/5) * 2 -64 . La valeur de i est inférieure à 2 64, donc l’erreur après multiplication est inférieure à 1/5. Après la division par 4, l’erreur est inférieure à (1/5) * 2 −2 .

(1/5) * 2 −2 <1/5 donc la réponse sera toujours égale à faire une division exacte et à arrondir vers zéro.


Malheureusement, cela ne fonctionne pas pour tous les diviseurs.

Si nous essayons de représenter 4/7 comme un nombre à 0,64 avec arrondi à zéro, nous nous retrouvons avec une erreur de (6/7) * 2 -64 . Après avoir multiplié par une valeur d’à peine moins de 2 64, nous nous retrouvons avec une erreur juste en dessous de 6/7 et après une division par 4, nous nous retrouvons avec une erreur d’un peu moins de 1,5 / 7 qui est supérieure à 1/7.

Donc, pour mettre en œuvre la division par 7 correctement, nous devons multiplier par un nombre à 0,65 point fixe. Nous pouvons implémenter cela en multipliant par les 64 bits inférieurs de notre nombre à virgule fixe, puis en ajoutant le nombre original (cela peut déborder dans le bit de retenue), puis effectuer une rotation à travers le report.

Voici un lien vers un document d’un algorithme qui produit les valeurs et le code que je vois avec Visual Studio (dans la plupart des cas) et que je suppose toujours utilisé dans GCC pour la division d’un entier variable par un entier constant.

http://gmplib.org/~tege/divcnst-pldi94.pdf

Dans l’article, un uword a N bits, un udword a 2N bits, n = numérateur, d = dénominateur = diviseur, ℓ est initialement défini à ceil (log2 (d)), shpre est pré-décalage (utilisé avant multiplication) = e = nombre de bits de fin de zéro dans d, shpost est post-décalage (utilisé après la multiplication), prec est la précision = N – e = N – shpre. L’objective est d’optimiser le calcul de n / d en utilisant un pré-changement, une multiplication et un post-décalage.

Faites défiler jusqu’à la figure 6.2, qui définit comment un multiplicateur udword (taille maximale N + 1 bits) est généré, mais n’explique pas clairement le processus. Je vais vous expliquer ci-dessous.

La Figure 4.2 et la Figure 6.2 montrent comment le multiplicateur peut être réduit à un multiplicateur de N bits ou moins pour la plupart des diviseurs. L’équation 4.5 explique comment la formule utilisée pour traiter les multiplicateurs N + 1 bits des figures 4.1 et 4.2 a été calculée.

Revenons à la figure 6.2. Le numérateur peut être plus grand qu’un udword seulement quand un diviseur> 2 ^ (N-1) (quand ℓ == N), dans ce cas le remplacement optimisé pour n / d est une comparaison (si n> = d, q = 1 , sinon q = 0), donc aucun multiplicateur n’est généré. Les valeurs initiales de mlow et mhigh seront N + 1 bits, et deux divisions udword / uword peuvent être utilisées pour produire chaque valeur N + 1 bits (mlow ou mhigh). En utilisant X86 en mode 64 bits comme exemple:

 ; upper 8 bytes of numerator = 2^(ℓ) = (upper part of 2^(N+ℓ)) ; lower 8 bytes of numerator for mlow = 0 ; lower 8 bytes of numerator for mhigh = 2^(N+ℓ-prec) = 2^(ℓ+shpre) = 2^(ℓ+e) numerator dq 2 dup(?) ;16 byte numerator divisor dq 1 dup(?) ; 8 byte divisor ; ... mov rcx,divisor mov rdx,0 mov rax,numerator+8 ;upper 8 bytes of numerator div rcx ;after div, rax == 1 mov rax,numerator ;lower 8 bytes of numerator div rcx mov rdx,1 ;rdx:rax = N+1 bit value = 65 bit value 

Vous pouvez tester cela avec GCC. Vous avez déjà vu comment j = i / 5 est traité. Regardez comment j = i / 7 est géré (ce qui devrait être le cas multiplicateur de N + 1 bits).