Unix v6 の C コンパイラが面白かった話

Unix v6 の C コンパイラをいじってみようと見てたのですが、これがなかなかすごい物体でした。

読んでて、「いやいくらなんでもこんな作りなわけが…」と思って説明文を探して、

http://plan9.bell-labs.com/7thEdMan/v7vol2b.pdf

の「A Tour through the UNIX C Compiler」に説明あるよと教えてもらって読んでみたら、本当にそんな作りだった、みたいな。

コンパイラの1段目はプリプロセスして構文木的なものをファイルに吐いて終わりです。2段目は構文木を読みつつコード生成していく。

構文木のノードの種類に対して switch してやること決める…的なものが、データドリブンな方法で書かれてます。データを保存するフォーマットは、 JSON とかではなく、時代が時代ですのでアセンブリです。こういうやつ

https://github.com/mortdeus/legacy-cc/blob/master/last1120c/regtab.s

ちなみにこれは v6 より古い時代のコードらしく、だいぶ v6 のやつよりシンプルですが、まぁ v6 も本質的にだいたいいっしょです。

たとえば 60 番 (これは == のノード番号) を見てみると、

	60.;	cr60

となってて、 cr60 の定義は

/ relationals
cr60:
%n,n
	HC
	I	2f
	clr	R
	br	1f
2:	mov	$1,R
1:

です。

最初の %n,n みたいなやつは、構文木にぶらさがってる左右の子が何者か、を示してます。 n はなんでもいいよ、っていうやつ。例えば %n,z だと右の子が定数ゼロなのでちょっと良いコードを出力する…みたいなことができます。

そこからはちょっとした VM というかなんというかの命令列です。大文字は全部特殊な意味があって、それ以外はそのままアセンブリとして出力されます。

HC は構文木のこのノードを含めてここから下を評価して condition code に置いて、という意味です。 I は自分のノード番号に対応する命令を置いてね、という意味。対応する命令ってのは

https://github.com/mortdeus/legacy-cc/blob/master/last1120c/c1t.s

に表になっていて、

	60.; 0f; 1f; .data; 0:<beq\0>; 1:<bne\0>; .text

とあるので 60 番は beq です(2番目のエントリは bne ですがこれはちょっと特殊な用途や、命令 I' で出力できます)。 は当時のアセンブラの記法で、 .ascii と同じ意味と思ってください。

余談ですが 61 は != で、これの定義のしかたとかはちょっと素敵です。

	60.; 0f; 1f; .data; 0:<beq\0>; 1:<bne\0>; .text
	61.; 1b; 0b

1b は後ろにある最初にある 1: ってラベル、ってやつなんで、 1b; 0b だと bne beq となって、なるほどひっくりかえってるんですね。この c1t.s を見てやると、同じ定数文字列を意地でも二度出現させない、という気遣いが見てとれるかと思います。

話を戻して、 R は今使ってるレジスタです。というわけで元のコードは、 == が成り立ってれば beq 2f で 2: に飛ぶので R=1 、そうでなければ R=0 、という感じのコードを吐く…という雰囲気がわかるんでないかと思います。

今は regtab.s というファイルを見ていて、 regtab がデフォルトのコード生成戦略なんですが、他にもスタックに置きたいときの sptab 、 condition code をいじりたい時の cctab 、副作用が欲しいだけなので式を評価した値はいらない時の efftab 、の4つの戦略があって、さっきの HC だと cctab を参照するように変化してたわけですけど、これが例えば HS だと sptab を見るようになるはずです。

てーいうことで HC は regtab を使ってたのを cctab に切り替える効果があり、その実体は

https://github.com/mortdeus/legacy-cc/blob/master/last1120c/cctab.s

/ relationals
cc60:
%a,z
	tstB1	A1

...

%n,z
	F
	tst	R

...

%n,n
	FS
	S
	cmp	(sp)+,R

にあります。これは長いので少しだけ見てみると、 %a,z は片方が既に addressible (つまり operand にそのまま来れるってことですな)で、かつ片方がゼロの時。こういう時は tst 命令一発、と。 B1 は A1 に対応する物体が byte か word かで b がついたりつかなかったりするだけ。

%n,z の場合は一旦レジスタ R に来てもらって…みたいな感じ。

一番一般的なケースの %n,n は、 FS は左辺をスタックに置いてね、 S は右辺をレジスタに置いてね、という意味で、最後の cmp はスタックを pop しつつレジスタと比較してる感じ。そのまんまですな。

なんというか、言語処理系の実装って、作る人の好みもあってか、メタな感じの実装になりがちだよねえと思ってたんですが、最初のコンパイラからしてこういうメタな作りかたしてたんだなぁと思いました。あと DSL って、こんな超初期の C コンパイラの時代からあったんだなあと。アセンブラ使ってるあたりは時代を感じさせますけど。

こんな作りになってる理由については、特に書いてなかったように思うんですが、コンパイラ自体のサイズの節約ではないかな…と思ってます。 == と != なら上記のようなことをして…みたいなのを C で書くより、こういうデータドリブンぽいやりかたでやった方がサイズ節約になる気がします。まあでも間違ってるかもしれません。

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h