Rogue Engineer's Diary / やさぐれ日記

■ [Modern Compiler Implementation in ML] 第12章突入、"Hello World"

"Modern Compile Implementation in ML"もついに第12章"Putting It All Together"に突入。ようやくコンパイラの動作確認フェーズに到達することができた。ちなみに今まですっかり書き忘れていたが、僕の使っている作業 環境は以 下の通り：

• Standard ML of New Jersey v110.54
• cygwin on Windows XP(SP2)
• gcc (GCC) 3.4.4（バックエンドに使用）

今回製作したコンパイラは"Modern Compile Implementation in ML"用に設計された教材用言語"Tiger"（Tigerについては2004年2月8日のエントリでも若干説明した）で書 かれたプログラムを入力と する。最初にコンパイルするテストプログラムは（お約束の）"Hello World"である。ファイル名は"hello.tig"。

/* hello world */
print("Hello, World!\n")

"Modern Compile Implementation in ML"のサポートページにあるライブラリ、runtime.cを コンパイルし、現在製作しているコンパイラの出力とリンクすることにより、"print"などの基本的関数がTigerから利用できるようになるのだが、 そのままコンパイル しようとするとこんなエラーが発生する。

$ gcc -c runtime.c
runtime.c:1:8: warning: undefining "__STDC__"
runtime.c:106: error: conflicting types for 'getchar'
/usr/include/stdio.h:190: error: previous declaration of 'getchar' was here

エラーが発生している、runtime.cの該当部分はこんな感じ。

.....
#undef getchar

struct string *getchar()
{.....

ざっと見た限り、（#undef getcharによって）Cの標準入出力ライブラリにある同名の関数/マクロとの衝突回避をしようとしている気配はあるものの、 それがうまく機能していない。いろいろな手を試してみたが、結局runtime.c内の"*getchar()"を"*getchr()"に書き換えると いう姑息な方法を使い、 一旦しのぐことにした。

やっと本番。まずはStandard ML of New Jerseyの対話型環境にて、"hello.tig"をコンパイルする。

- Main.compile "test/hello.tig";
emit tigermain
val it = () : unit

コンパイルされた結果は"hello.tig.s"というファイル名で出力される。中を見るとそれらしいIA32のアセンブリコードが 出来上がっ ているのが分かる：

.globl _tigermain
 .def _tigermain; .scl 2; .type 32; .endef
_tigermain:
 pushl %ebp
 movl %esp, %ebp
 subl $4, %esp
.....

出てきたアセンブリコードの全体像はこ ちらを参照。余計な"movl"や"jmp"が目に付くが、これらは追々取り除いていく予定。

これをgccでコンパイルし、先ほどのruntime.cのコンパイル結果とリンク、そして（やや緊張しつつ）実行：

$ gcc hello.tig.s runtime.o
$ ./a.exe
o, World!
 瑞U牙・ ・・$・右・E・E・} 畿・・UE・ 孔・・畿
（……中略……）
ModuleHandleA P P P P P P P P P P P P P P cygwin1.dll P KERNEL32.dll
Segmentation fault (core dumped)

クラッシュ。派手に散った。

実行直後に"o, World!"と出ているところからして、最初の4バイト(="Hell")が切れていることはすぐに分かる。なにかズレているのかと思いながらアセンブ リコードを眺める…が、よくわからない。

Cで同様の動作をするプログラムを書いて、runtime.oとリンク、実行させると、同じようにSegmentation faultでクラッシュする。コンパイラの問題ではなく、リンクしたライブラリ"runtime.o"に何かあるようだ。

問題のライブラリのソースであるruntime.cを 眺めたところ、原因はあっけなく判明した。TigerではCのようなNULL終端文字列ではなく、Pascal形式、つまり長さ(4バイト)＋文字列本体 という構成の文字列を使っていたので あった。本にも書いてあったようだがすっかり忘れていたよ。

ということで、コンパイラから出力されるアセンブリコード中で

...
L0:
 .ascii "Hello, World!\n\0"

となっていた箇所を、

...
L0:
  .int 14
 .ascii "Hello, World!\n"

と出力するようにプログラムを修正し、再度コンパイル、実行する：

$ gcc hello.tig.s runtime.o
$ ./a.exe
Hello, World!

ついに動いた。

まずは第一歩。でもここからが長い…のだろうな、やはり。

■ [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()関数もうまく動作しているようだ…が、それにしても整数の割り算で 「浮動小数点演算の例外」と出るのは一体なぜなのだろう？