きまぎらすほしゅの不定記

■ 除法最適化解除のメモ

解析を行っているとき，たまにこの様な命令列と出会すことがある．場合によって，subが入ったり，sarではなくshrだったり，shrが二回続いたりすることもあるが，大体はこんな感じだ．

mov r0, A
imul r0
sar edx, B
mov r1, edx
shr r1, C
add r1, edx

何か掛け算したりシフトしたり足したりと，わけの分からない計算をしているように見えるが，見た目にダマされてはいけない．命令列を実際の式に落として，単純化を行うと，本来の姿が見えてくる．

例えば，A=1374389535，B=3，C=31とすると，

((eax * A) >> 32 >> B) + ((eax * A) >> 32 >> B >> C)
＝(eax * 1374389535)/2^32/2^3+(eax * 1374389535)/2^32/2^3/2^31
≒ eax * 0.040000000026775524023989714927918015519026084803

計算して確認すると分かるが，最大の誤差でもeax * 0.04と等しい値が得られることから

eax * 0.040000000026775524023989714927918015519026084803
→eax * 0.04
＝eax / 25

となり，この命令列はeaxを25で割る演算を行うことが分かる．他の演算数の場合でも同様にして，元の式を得ることができる．

しかし，何故idivやdivを使わないのだろうか．各命令のスループットやレイテンシを確認してみると，その理由が分かるかもしれない．