みんなでコンパイラの実装に挑戦する勉強会です。バイナリいじりの基礎から始めて、実行ファイルを自前のコンパイラで作って動かすことを目標にします。コンパイラをきっかけにして、各種マシンコードやOSのメモリ管理について理解を深めるのが狙いです。
特にセッションはなく、みんなで開発や質問をする形式です。全体での目標は定めずに、各自で好きなものを実装していただきます。どこから手を付けて良いのか分からないという方には、Brain*uckのインタプリタから始めていただくことをお勧めします。
会場はだくとさんの主催するZIP実装会と共同で利用します。特に何かを共同で進行するわけではありませんが、お互いの交流は自由です。
第4回 コンパイラ実装会で出た質問です。
※ 例は32bit Windows限定のコードです。
レジスタ経由で呼び出せば、相対アドレス計算が不要になります。
関数を呼び出す部分で毎回書き換えをするのは面倒です。関数のアドレスを引数で渡すと書き換えずに済みます。
call命令が実行されるとき、スタックの状態は以下のようになっています。
| [esp+0] | 65 |
| [esp+4] | 戻り先のアドレス |
| [esp+8] | 引数 |
第3回 コンパイラ実装会で@uho_iiotokoさんがBrainf*ckのトランスレータを実装されているとき、ちょっと面白いことが起きました。
元はC言語で実装されたBrainf*ckからアセンブラへのトランスレータです。トランスレート対象がC言語でも同じ結果となるため、Pythonで再実装した再現コードを掲載します。
【注】無限ループや入力は想定していません。
インタプリタとトランスレータの両方が実装されています。トランスレータではループ（ [ と ] ）を実装していないにも関わらず、トランスレートされたコードは正常に動作します。
$ ./bf.py helloworld.bf Hello World! $ gcc bf.c $ ./a.exe Hello World!
これはなぜなのか首をひねりました。結論から言うと、インタプリタを実行しながらトランスレートしているため、結果的にループを展開したコードが出力されていました。
たとえば次のようなBrainf*ckのコードを変換してみます。
ループを2回繰り返しますが、それが展開されます。
参加者の@furandon_pigさんより、このようなループの展開を loop unrolling と呼ぶことを教えていただきました。調べるとWikipediaにも書いてありました。
最適化でループに細工をするような事例は知っていましたが、用語があることまでは知りませんでした。
Pythonでは関数のアドレスを指定して呼び出せます。以下の例は適当なアドレスなので、呼び出してもエラーになります。
>>> from ctypes import * >>> f = CFUNCTYPE(None)(0x1234) >>> f() Traceback (most recent call last): File "<stdin>", line 1, in <module> WindowsError: exception: access violation writing 0x00001234
逆に、fから0x1234を取り出すやり方がわかりません。結論から言うと、関数を作って通すしかないようです。
>>> getaddr = CFUNCTYPE(c_void_p, c_void_p)(lambda p: p) >>> hex(getaddr(f)) '0x1234'
DLLからインポートした関数のアドレスや、Pythonから作ったサンクのアドレスも取り出せます。
>>> putchar = cdll.msvcrt.putchar >>> hex(getaddr(putchar)) '0x77beef74' >>> hex(getaddr(getaddr)) '0xa40fc0'
取り出したアドレスを直接指定すると、ちゃんと呼び出せることが確認できます。
>>> CFUNCTYPE(c_int, c_int)(0x77beef74)(65) A65
上の例のputcharとgetaddrは、_objectsにデータを持っているようです。fにはありません。
>>> f._objects
>>> putchar._objects
{'0': <CDLL 'msvcrt', handle 77bc0000 at c7a7b0>}
>>> getaddr._objects
{'0': <_ctypes.CThunkObject object at 0x00C7FF38>}
CDLLやCThunkObjectはC言語で実装されているため、Pythonからポインタを取り出すことはできないようです。仮に取り出せたとしても種類によって内部のオブジェクトが異なるため、統一的にアドレスを取り出すにはgetaddrのような関数を使うしかなさそうです。
Windows x64用のクロスgccをビルドしました。MSYSで作業しましたが、他のUNIX系OSでも同じ手順が使えるはずです。
今回はmultilibを使用せずにx64専用とします。
gccが依存する数値計算ライブラリ gmp, mpfr, mpc をビルドします。
$ curl -LO ftp://ftp.gnu.org/gnu/gmp/gmp-5.0.5.tar.xz $ tar xvf gmp-5.0.5.tar.xz $ cd gmp-5.0.5 $ ./configure $ make $ make install $ cd ..
$ curl -LO http://www.mpfr.org/mpfr-current/mpfr-3.1.0.tar.xz $ tar xvf mpfr-3.1.0.tar.xz $ cd mpfr-3.1.0 $ CPPFLAGS=-I/usr/local/include LDFLAGS=-L/usr/local/lib ./configure $ make $ make install $ cd ..
$ curl -LO http://www.multiprecision.org/mpc/download/mpc-0.9.tar.gz $ tar xvf mpc-0.9.tar.gz $ cd mpc-0.9 $ CPPFLAGS=-I/usr/local/include LDFLAGS=-L/usr/local/lib ./configure $ make $ make install $ cd ..
binutils（アセンブラ・リンカなど）をビルドします。
$ curl -LO ftp://ftp.gnu.org/gnu/binutils/binutils-2.22.tar.bz2 $ tar xvf binutils-2.22.tar.bz2 $ mkdir -p x86_64-pc-mingw32/binutils $ cd x86_64-pc-mingw32/binutils $ ../../binutils-2.22/configure --target=x86_64-pc-mingw32 --disable-nls $ make $ make install $ cd ../..
gccをコンパイラだけビルドします。gcc付属ライブラリはランタイムがないとビルドできませんが、ランタイムはコンパイラがないとビルドできないためです。
$ curl -LO ftp://ftp.gnu.org/gnu/gcc/gcc-4.7.0/gcc-4.7.0.tar.bz2 $ tar xvf gcc-4.7.0.tar.bz2 $ mkdir -p x86_64-pc-mingw32/gcc $ cd x86_64-pc-mingw32/gcc $ CPPFLAGS=-I/usr/local/include LDFLAGS=-L/usr/local/lib ../../gcc-4.7.0/configure --target=x86_64-pc-mingw32 --disable-nls $ CPPFLAGS=-I/usr/local/include LDFLAGS=-L/usr/local/lib make all-gcc $ make install-gcc $ cd ../..
ランタイムのソースをダウンロードして展開します。
$ curl -LO http://sourceforge.net/projects/mingw-w64/files/mingw-w64/mingw-w64-release/mingw-w64-v2.0.3.tar.gz $ tar xvf mingw-w64-v2.0.3.tar.gz
ヘッダをビルドします。ランタイムをビルドする前にヘッダをインストールしないとエラーになるためです。
※ configureのオプションは--targetではなく--hostです。
$ mkdir -p x86_64-pc-mingw32/headers $ cd x86_64-pc-mingw32/headers $ ../../mingw-w64-v2.0.3/mingw-w64-headers/configure --host=x86_64-pc-mingw32 $ make $ make install $ cd ..
ランタイムをビルドします。
※ configureのオプションは--targetではなく--hostです。
$ mkdir runtime $ cd runtime $ ../../mingw-w64-v2.0.3/configure --host=x86_64-pc-mingw32 --without-headers $ make $ make install $ cd ..
gccのビルドに戻ります。コンパイラはビルド済みのため、付属ライブラリがビルドされます。
$ cd gcc $ make $ make install $ cd ../..
以上でビルドとインストールは完了です。
$ x86_64-pc-mingw32-gcc hello.c $ file a.exe a.exe: PE32+ executable for MS Windows (console) Mono/.Net assembly $ ./a.exe hello
32bitのAlphaのコードがどのようなものか見たくなり、Windows NT/Alpha用のクロスgccをビルドしてみました。ビルドに成功したのはgcc-3.0.4です。binutilsはビルドできるバージョンが見つからなかったため、PEバイナリは出力できません。gcc -Sでアセンブリコードを出力することはできます。
ソースにパッチを当て、ソースの外にディレクトリを作ってビルドします。
$ tar xvzf gcc-core-3.0.4.tar.gz $ patch -p0 < gcc-3.0.4-alpha-winnt.diff $ mkdir alpha-winnt $ cd alpha-winnt $ ../gcc-3.0.4/configure --target=alpha-winnt --disable-nls $ make $ make install
64bit用のalpha-elf-gccとの違いを比べてみます。alpha-elf-gccのビルドはパッチが必要です。
簡単なプログラムをアセンブリ出力して結果を比べてみます。
gccからアセンブリを出力します。プロローグやエピローグを簡略化するため最適化を掛けます。
$ alpha-elf-gcc -O -S -o alpha-elf.s alpha.c
binutilsが使えるので、逆アセンブルも試します。C言語との対応関係が分かります。
$ alpha-elf-gcc -nostdlib -O -g -o alpha-elf.x alpha.c $ alpha-elf-objdump -S alpha-elf.x > alpha-elf.txt
レジスタが番号ではなく名前で示されるため読みやすいです。擬似命令が展開されるため、実際のバイナリが確認できます。
両者を見比べると以下のことが分かります。
lda $16,4 # sizeof(int) lda $16,4 # sizeof(long) lda $16,4 # sizeof(void *)
lda a0,4 # sizeof(int) lda a0,8 # sizeof(long) lda a0,8 # sizeof(void *)
lda $1,global => ldq t0,-32760(gp)
sw $4,global => lui at,0x40; sw a0,8192(at) # [0x402000] = a0
gcc-3.0.4にはalpha-interixのコンフィギュレーションもあります。出力するコードはalpha-winntとほぼ同じようです。こちらも対応するbinutilsが見つかりませんでした。
Alpha版のInterixは存在すら知らなかったので驚きました。WikipediaにはInterix 2.2までは対応していたような記述があります。
現物は見たことも聞いたこともないので詳細不明です。
MSYSでのGTK+のビルドと、コマンドライン引数の問題が解決したので、ようやくGtk#のビルドに成功しました。
今回は.NET Framework 4.0をバックエンドとして動かすため、Monoは使用しません。
MSYSが勝手に引数を変換しないように細工した.NET関連のラッパーを用意しました。ビルドにはmsys-core-devが必要です。
$ mingw-get install msys-core-dev
$ make $ make install
Gtk#のソースをダウンロードして展開します。
$ curl -LO http://download.mono-project.com/sources/gtk-sharp212/gtk-sharp-2.12.10.tar.bz2 $ tar xvf gtk-sharp-2.12.10.tar.bz2 $ cd gtk-sharp-2.12.10
configureがCygwinを想定しているため、-mno-cygwinを取り除くパッチを当てます。今回使用したGLib 2.32.2は想定されているものより新しいらしく、ヘッダがエラーになるのでパッチを当てます。
ビルドします。make installすると動作がおかしくなるので、敢えてしません。
$ ./configure $ make
インストールでおかしくなる原因は未調査です。インストールせずに単体では問題なく動くため、ビルド自体は正常にできているようです。今後の課題とします。
配布する際のランタイムとしては、Gtk#のバイナリ配布物をインストールすれば良いので、差し当たって問題はありません。