Wie funktioniert die GCC-Implementierung von Modulo (%), und warum verwendet sie nicht den Div-Befehl?

Question

Ich habe versucht, herauszufinden, wie man Modulo 10 in Assembly berechnet, also habe ich den folgenden c-Code in gcc kompiliert, um zu sehen, woraus er entstanden ist.

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

Zu meiner Überraschung bekam ich

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) 

Wo -4 (% EBP) oder "i" der Eingang und -12 (% EBP) oder "j" ist die Antwort. Ich habe das getestet und es funktioniert, egal welche Nummer Sie machen -4 (% ebp).

Meine Frage ist, wie funktioniert dieser Code und wie ist es besser als mit dem Div-Operanden.

Answer 1

Zweite Frage zuerst: div ist eine sehr langsame Anweisung (mehr als 20 Taktzyklen). Die obige Sequenz besteht aus mehr Anweisungen, aber sie sind alle relativ schnell, also ist es ein Nettogewinn in Bezug auf die Geschwindigkeit.

Die ersten fünf Anweisungen (bis einschließlich shrl) berechnen i/10 (ich werde erklären, wie in einer Minute).

Die nächsten paar Anweisungen multiplizieren das Ergebnis erneut mit 10, aber vermeiden Sie die mul/imul Anweisungen (ob dies ein Gewinn ist oder nicht hängt von der genauen Prozessor abzielen - neuere x86s haben sehr schnelle Multiplikatoren, aber ältere nicht).

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 

Dies wird dann von i wieder subtrahiert i - (i/10)*10 zu erhalten, welche i % 10 (für Zahlen ohne Vorzeichen).

Schließlich, bei der Berechnung von i/10: Die Grundidee ist, Division durch 10 mit der Multiplikation mit 1/10 zu ersetzen. Der Compiler führt eine Festkomma-Approximation durch Multiplikation mit (2 ** 35/10 + 1) durch - das ist der magische Wert, der in edx geladen wird, obwohl er als signierter Wert ausgegeben wird, obwohl er wirklich nicht signiert ist Ergebnis um 35. Dies ergibt das richtige Ergebnis für alle 32-Bit-Ganzzahlen.

Es gibt Algorithmen, diese Art von Annäherung zu bestimmen, die garantieren, dass der Fehler kleiner als 1 ist (was für ganze Zahlen bedeutet, es ist der richtige Wert ist) und GCC verwendet offenbar eine :)

Schlussbemerkung: Wenn Sie wirklich wollen siehe GCC compute a modulo, mache die Divisorvariable (zB einen Funktionsparameter), damit diese Art der Optimierung nicht möglich ist. Anyway, auf x86, berechnen Sie modulo mit div. div erwartet die 64-Bit-Dividende in edx:eax (32 Bit hoch in edx, niedrig 32 Bit in eax - clear edx auf Null, wenn Sie mit einer 32-Bit-Zahl arbeiten) und teilt das mit dem von Ihnen angegebenen Operanden (z.div ebx teilt edx:eax von). Sie gibt den Quotienten in eax und den Rest in edx zurück. idiv macht das gleiche für vorzeichenbehaftete Werte.

Answer 2

Der erste Teil, bis zu shrl $3, %edx, implementiert eine schnelle Ganzzahl-Division durch 10. Es gibt ein paar verschiedene Algorithmen, die funktionieren, wenn die Anzahl, mit der Sie teilen, im Voraus bekannt ist. Beachten Sie, dass 858993459 "0,2 * 2^32" ist. Der Grund dafür ist, dass, obwohl es einen Integer-Division-Befehl div/idiv im Befehlssatz gibt, dieser typischerweise sehr langsam ist, mehrere Male langsamer als die Multiplikation. Der zweite Teil berechnet den Rest, indem er das Ergebnis der Division mit 10 multipliziert (indirekt über Verschiebungen und Additionen; vermutlich denkt der Compiler, dass es so schneller geht) und dann subtrahiere das von der ursprünglichen Zahl.