Rogue Engineer's Diary / やさぐれ日記(2006-06-15)

2006-06-15

■ [Modern Compiler Implementation in ML] 割り算のワナ

テストプログラムを実行して結果を確認しようと思うと、文字列だけでなく数値も表示させたくなる。だが Tiger には数値表示用の組み込み関数がないので、マージソートのサンプルプログラムから以下のような関数を引っ張ってきて使うことにした。

function printint(i: int) =
    let function f(i:int) = if i>0
        then (f(i/10); print(chr(i-i/10*10+ord("0"))))
    in if i<0 then (print("-"); f(-i))
       else if i>0 then f(i)
       else print("0")
    end

掛け算と割り算、if文、ネストした関数定義に、とどめは再帰呼び出しと、"Hello World"の次に試すプログラムとしては複雑・無謀きわまりない…というか、この後に作る予定の（例えば加減乗除といった）単純なテストプログラムの実行結果を確認するためにこんなものを用意するところからして、手段と目的がひっくり返っているのだが、そこは気にしないことにする。

…案の定ハマった。落とし穴はいくつかあったのだが、最後に残ったのがこれ。

$ ./a.exe
Floating point exception (core dumped)

浮動小数点演算は使っていない（というかこのコンパイラでは浮動小数点の計算はできない）のに一体何が起きているのだろうか。

printint()関数の中身を削っていって問題を絞り込んだ結果、最後に残ったのが、割り算であった。上記のエラーを再現できる最小のコードはこんな感じになる。

6 / 2

当初、このコンパイラは以下のようなアセンブリコードを出力していた（ちなみに、GCCでこのような定数同士の計算をさせると最適化によりアセンブリコードレベルでの割り算は実行されず、"6/2"の計算結果である"3"が直接レジスタに代入されるのだが、このコンパイラではそのような最適化はまだ実装されていない）

	movl	$6, %eax
	movl	$2, %ebx
	idivl	%ebx

ところが、このアセンブリコードはきちんと動作しない。

符号付き整数の割り算命令である"idivl"(IDIV) 命令を実行するときには、まず割られる数を64ビットで表現したもののうち、その上位32ビットをEDXレジスタに、下位32ビットをEAXレジスタに置く。割り算を実行した結果はEAXレジスタに格納されるが、この結果が32ビットに収まらない場合には#DE(divide error)例外が発生する。

上記のアセンブリコードでは、EDXレジスタの値については一切気にしていないため、実行時点でたまたまEDXレジスタに入っていた値が、割られる数の上位32ビットとして使われてしまっている。そのままIDIV命令を実行しても、ほとんどの場合割り算の実行結果は32ビットに収まらないために、例外が上がる、ということらしい。

解決の手がかりを得るために、同様の計算をするアセンブリコードをGCCで出力し、それを眺めてみると、"cltd"という命令が使われていることに気がついた。ところがIntelの"IA-32 Intel Architecture Software Developer’s Manual"を見ても、そのような名前の命令は見当たらない。そのまま使ってしまってもいいのだが、何をする命令か分からないままというのも気持ちが悪い。

いろいろと資料を探したあげく、as(GNU Assembler)のマニュアルにある"Opcode Naming"の項を見たところ、Intel記法（ニーモニック）で"cltd"に相当するのは"CDQ"という命令であることが分かった。また、説明文に"sign-extend dword in `%eax' to quad in `%edx:%eax'"と書かれているところからしても、今回のような符号付き整数の割り算を実行する前に必要な命令であることが見て取れる。ということでコンパイラを修正し、以下のようなアセンブリコードが出力されるようにした。

	movl	$6, %eax
	cltd	←コレを追加
	movl	$2, %ebx
	idivl	%ebx

これにて一件落着。"Floating Point Exception"も出なくなったし、printint()関数もうまく動作しているようだ…が、それにしても整数の割り算で「浮動小数点演算の例外」と出るのは一体なぜなのだろう？

本日のツッコミ(全2件) [ツッコミを入れる]

# フルタニアン (2006-10-20 13:10)

こういう経緯かもしれないそうです。
http://cclub.cc.tut.ac.jp/~pakuchan/hoge/2004/9/28
#参考になりました、どうも

# 福盛 (2006-10-23 20:06)

ありがとうございます。リンク先の情報はこのナゾに対する良い突破口になりました。
SIGFPEとINTDIVをキーワードに探すのがミソみたいですね。

http://en.wikipedia.org/wiki/SIGFPEあたりには

Although SIGFPE does not necessarily involve floating-point arithmetic, there is no way to change its name without breaking backward compatibility.

というシンプルな説明がありました。なるほど……

ツッコミ・コメントがあればどうぞ! E-mailアドレスは公開されません。

[TrackBack URL: http://fukumori.org/diary/tb.rb/20060615]

本日のリンク元