コンパイラが剰余算を掛け算に変換する様子

はじめに

このふとしたtweetから、コンパイラがmod計算を掛け算で頑張る姿を見てみようと思いったたのが動機です。

コンパイラというより、機械語・CPUアーキの話じゃないかと言う気もしますが、軽いネタとして。

スクリプト

以下のスクリプトを用意しました。

modの除数が決まってない関数と、除数が定数になっている関数を用意し、コンパイラによってアセンブリを作り出すものです。
※定数の除数は標準入力として与えます ( 1行1数値で複数可 )。

なお、簡単のために符号なし整数を扱うものとします。

アセンブリ表示スクリプト

cd $TMPDIR
uname -a
gcc --version
cat > mod1.c <<'_EOS_'
#include <stdint.h>
uint32_t modGENERIC(uint32_t x,uint32_t y) {
  return x % y;
}
_EOS_
cat > mod2.c <<'_EOS_'
#ifndef MOD_BASE
# error "define MOD_BASE with 'gcc -DMOD_BASE=xx'"
#endif
#include <stdint.h>
uint32_t modCONSTANT(uint32_t x) {
  return x % MOD_BASE;
}
_EOS_

echo "** assembly code for generic MOD **"
gcc -std=c99 -fno-asynchronous-unwind-tables -S -o /dev/stdout -O3 mod1.c | sed -ne '/\.size/q;/^mod/,$p'
echo

while read base; do
  [ -n "$base" ] || continue
  echo "** assembly code for constant MOD by $base **"
  gcc -DMOD_BASE=$base -std=c99 -fno-asynchronous-unwind-tables -S -o /dev/stdout -O3 mod2.c </dev/null | sed -ne '/\.size/q;/^mod/,$p'
  echo
done

なお、実行は ideoneで試しました。C言語の話ですが、実行自体はシェルスクリプトとして行います。

入力を125 と 333 の2行としたところ、次のような出力が得られました。

ideone実行結果サンプル

Linux checker 3.16.0-4-amd64 #1 SMP Debian 3.16.43-2+deb8u5 (2017-09-19) x86_64 x86_64 x86_64 GNU/Linux
gcc (Ubuntu 8.3.0-6ubuntu1) 8.3.0
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

** assembly code for generic MOD **
modGENERIC:
    movl    %edi, %eax
    xorl    %edx, %edx
    divl    %esi
    movl    %edx, %eax
    ret

** assembly code for constant MOD by 125 **
modCONSTANT:
    movl    %edi, %eax
    movl    $274877907, %edx
    mull    %edx
    movl    %edx, %eax
    shrl    $3, %eax
    imull   $125, %eax, %eax
    subl    %eax, %edi
    movl    %edi, %eax
    ret

** assembly code for constant MOD by 333 **
modCONSTANT:
    movl    %edi, %eax
    movl    $-1986261151, %edx
    mull    %edx
    movl    %edi, %eax
    subl    %edx, %eax
    shrl    %eax
    addl    %edx, %eax
    shrl    $8, %eax
    imull   $333, %eax, %eax
    subl    %eax, %edi
    movl    %edi, %eax
    ret

考察

さて。結果を読み解くにはアセンブリの知識が必要になりますが、そこはノリでお願いします。

結果抜粋-除数が変数

** assembly code for generic MOD **
modGENERIC:
    movl    %edi, %eax
    xorl    %edx, %edx
    divl    %esi
    movl    %edx, %eax
    ret

まず、除数が変数、つまり定数として固定されていない場合は、流石に機械語の除算・剰余算を使うしかありません。上の結果にあるdivlがそれで、x86の剰余付き除算命令を使うことになります。

しかしこの命令は非常に遅いので、除数が定数の場合は掛け算等で高速化を図ります。続いてmod 125の場合です。

結果抜粋-除数が定数(125)

** assembly code for constant MOD by 125 **
modCONSTANT:
    movl    %edi, %eax
    movl    $274877907, %edx
    mull    %edx
    movl    %edx, %eax
    shrl    $3, %eax
    imull   $125, %eax, %eax
    subl    %eax, %edi
    movl    %edi, %eax
    ret

簡単に言うと、x mod 125を計算するために、以下の計算を行っています。

• ( x * 274877907 ) >> 35 により x / 125 の商を計算
  • 出力中のmullが x * 274877907の掛け算に相当
  • 結果(64bit分)の上位32bitに対して、3bitの右シフト ( shrl ) をかけることで、>> 35を計算
• x - (商の値) * 125 により x mod 125 を得る
  • imullで、商の値に対して125をかけている
  • sublで引き算を行い、最終的な剰余を計算している

なぜこれでうまく行くかと言うと、( x * 274877907 ) >> 35 と x / 125 が、32bit整数の範囲でちゃんと一致してくれるからです。
そのカラクリは、

• 1<<35 = 2^35 = 34,359,738,368
• 274877907 * 125 = 34,359,738,375

この両者が、その差わずか 7 とほとんど一致している点にあります。
逆に言えば、コンパイラがこのように都合の良い数を見つけ出して、mod を掛け算ベースの計算に変換してくれているということですね。

終わりに

ネタなので大した結論はありませんが、実行速度の遅い剰余算の最適化のために、コンパイラが色々頑張ってくれているということです。
…出力例にある mod 333 なんかだと、もっと計算内容が複雑になってますが、それでも除算命令よりもマシと判断されるのでしょう。

興味の湧いた方は、紹介したスクリプトで色々な除数を試してみても良いのではないでしょうか。