【算術演算小話その三】コンパイラの除算最適化

最後です。

これも@machyさんから、2の冪乗での除算の場合、intとunsigned intで発行される命令数が違うという話を聞いて、詳しく調べてみた話です。で、実際に検証するために、以下のコードをコンパイルしてみました。

int main(int argc, char *argv[])
{
  int x = -5;
  return x / 4;
}

xをそれぞれint,unsigned intと変えてコンパイルし、作成されたアセンブリコードのdiffを取ります。

ちなみにコンパイラはgcc-3.4.6(Linux), コンパイルオプションは「-m32 -S」です。 (gcc4系列の場合さらに最適化されてストリング命令を利用するようになるので今回の実験結果には沿いません。)

以下がアセンブリコードのdiffです。通常除算というとidiv命令やdiv命令が使われるのですが、2の冪乗の場合、コンパイラの最適化によって除算がシフト演算に置き換わります。

@@ -1,23 +1,29 @@
        .file   "printbit2.c"
        .text
 .globl main
        .type   main, @function
 main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        andl    $-16, %esp
        movl    $0, %eax
        addl    $15, %eax
        addl    $15, %eax
        shrl    $4, %eax
        sall    $4, %eax
        subl    %eax, %esp
        movl    $-5, -4(%ebp)
        movl    -4(%ebp), %eax
-       shrl    $2, %eax
+       movl    %eax, -8(%ebp)
+       cmpl    $0, -8(%ebp)
+       jns     .L2
+       addl    $3, -8(%ebp)
+.L2:
+       movl    -8(%ebp), %eax
+       sarl    $2, %eax
        leave
        ret
        .size   main, .-main
        .section        .note.GNU-stack,"",@progbits
        .ident  "GCC: (GNU) 3.4.6 (Ubuntu 3.4.6-6ubuntu5)"

int型でコンパイルした場合、確かに条件分岐を含めた結構な命令数が増加しています。 intでコンパイルした時のアセンブリコードを、わかりやすい用にCのコードに直すと、下記のようになります。 (実際コンパイルして見るとほぼ同じアセンブリコードを吐きます。)

int main(int argc, char *argv[])
{
  int x = -5;
  if(x < 0){
    x += 3;
  }
  return x >> 2;
}

なぜか、負の数かどうかをチェックし、負の数の場合は3を足しています。この謎を解いて行きたいと思います。

まず、3を足さない場合、結果がどうなっていたかを確認してみると、返される戻り値は「-2」になりました。 3を足す場合は「-1」です。「算術演算小話その二」で調査した結果、Cでの除算の結果はどちらが正しいかというと、「-5 / 4 = -1」であり、0に近い整数に丸める必要があるので、3を足さなければ仕様に合わなくなってしまうようです。

では次に、3という数字はどこから来ているかについて考えるため、除算の値をいろいろ変えてコンパイルしてみました。その結果、「32」で割る場合は「31」を足し、「64」で割る場合は「63」を足していました。

これは、実は右シフト演算は常に切り下げ(マイナス無限大方向への丸め)を行ってしまうので、「算術演算小話その一」で書かれた手法を使ってm-1を足すことによって、0方向への切り上げ処理を行っているようです。（たぶん合っていると思います)

以上で一連の話は終わりです。この３回を書くに当たって、個人的には自分の中でちゃんと把握できていない、曖昧だった部分を整理できたので、書いてよかったなーと思っています。興味深いことをお教え頂いた@machyさん、ありがとうございました。

・【算術演算小話その一】倍数への切り上げ・【算術演算小話その二】負の剰余について・【算術演算小話その三】コンパイラの除算最適化