モジュロ（％）のGCC実装はどのように機能し、なぜdiv命令を使用しないのですか？

Question

アセンブリで10を計算する方法を工夫していたので、gccで次のようなCコードをコンパイルして、どうなっているのかを確認しました。私の驚きに

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

私は

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) 

-4（％のEBP）、または "i" は、入力および-12（％のEBP）または "j" が答えですが。です私はこれをテストしていて、あなたが何をしても何もしません-4（％ebp）。

私の質問は、このコードはどのように動作し、どのようにdivオペランドを使用するよりも優れているのですか？

Answer 1

第2の質問から最初に：divは非常に遅い命令（20クロックサイクル以上）です。上記のシーケンスはより多くの指示で構成されていますが、それらはすべて比較的高速です。したがって、速度に関して純粋な勝利です。

最初の5つの命令（shrlまで）はi/10を計算します（1分で説明します）。

mul/imul命令（これが勝っているかどうかは、ターゲットとするプロセッサによりますが、新しいx86では非常に高速な乗算器が使用されますが、それより古いものは避けます）しないでください）。

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 

これは再び（符号なし数値の場合）i % 10あるi - (i/10)*10を得るためiから減算されます。

最後に、i/10の計算について：基本的な考え方は、10による除算を1/10の乗算で置き換えることです。コンパイラは、（2 ** 35/10 + 1）を乗算することでこれを固定小数点近似します。つまり、それは実際に符号なしであっても符号付きの値として出力されますが、edxにロードされた魔法の値です。これはすべての32ビット整数に対して正しい結果をもたらすことが分かります。

最終発言があり（整数のためにそれが正しい値です意味）エラーが1未満であることを保証近似のこの種を決定するアルゴリズムはだとGCCは明らかに1を使用しています:)

：あなたが実際にしたい場合はGCCがモジュロを計算するのを参照して、このような最適化を行うことができないように除数変数（関数パラメータなど）を作ります。とにかく、x86では、divを使ってモジュロを計算します。 divは、edx:eaxの64ビット被除数（edxの上位32ビット、32ビットのビットを扱う場合、eax-clear edxの下位32ビットはゼロになります）を指定し、指定したオペランドで除算します。div ebxは、edx:eaxをebxで割る）。商はeaxに、残りはedxに戻ります。 idivは符号付きの値でも同じです。

Answer 2

最初の部分は最大でshrl $3, %edxで、10で高速整数除算を実装します。分割する数値が事前にわかっている場合は、いくつかのアルゴリズムが動作します。 858993459は「0.2 * 2^32」であることに注意してください。これは、命令セットに整数除算命令div/idivがあっても、通常は非常に遅く、乗算よりも数倍遅いためです。

2番目の部分は、除算の結果に10を掛けて（シフトと加算によって間接的に、おそらくコンパイラはそれが速いと考えていると思われます）、元の数から減算して剰余を計算します。