KOTET'S
PERSONAL
BLOG

#dlang 君もDでx86_64向けCコンパイラを書こう

#dlang #tech #advent-calendar

これは、強い人が多すぎてもはやCコンパイラ書いた程度では面白味がない気がしてくる D言語 Advent Calendar 2018 11日目の記事です。

この記事の対象読者は過去の自分、 つまりコンパイラとかに興味があっていろいろ調べたりはするけどそこで満足してなかなか行動に移せないあなたです。 この記事を通して、 自分は読者であるあなたにD言語でCコンパイラを書いてもらえるように全力で説得していきます。

あなたもD言語を書きましょう。 Cコンパイラを書きましょう。 D言語でCコンパイラを書きましょう。

あなたとD、今すぐダウンロード

d9cc : A Small C Compiler Written in D

ここ最近9ccのコミットログをたどってCコンパイラを書いていました。

kotet/d9cc: A Small C Compiler Written in D

この記事を読んだのが書き始めた理由でした。

1人でがんばる自作Cコンパイラ

前々からコンパイラとか書いてみたいし、アセンブリも読めるようになりたいな、 とは思って定期的に勉強しようとしていましたが、 どうも途中でくじけてしまって毎回同じところをぐるぐるしていました。 そこで上の記事を見て、なるほどそういう勉強法がうまくいくんだなあと思い、 書き始めてみたら結構うまくいきました。

N-queen が動くくらいにはできています。 あと9ccにはないオリジナル機能として、 抽象構文木Graphviz のdotファイル形式で出力するオプションがあります。

上:int main(int argc, char **argv) {int a = (1+2+3)*7; return a;}のASTを可視化したもの(-dump-ast1オプションを渡すと生成される)
下:上のASTを意味解析したもの(-dump-ast2オプションを渡すと生成される)

9ccには浮動小数点数も存在しないのでこれもオリジナル機能として実装してみようかと思ったりもしましたが、 思ってるうちにやる気が減衰してきて実現できていません。

なぜCコンパイラを書くのか

しかしなぜいまさらx86_64向けCコンパイラなどというありふれたものを作るのでしょうか? 実はある種の分野の勉強をするのにCコンパイラは最適な題材なのです。

プログラミングの学習を始めたばかりの時、コンパイラは一種魔法のように見えました。 テキストデータであるプログラムの「構造を解析して」、「意味を与え」、「機械語に翻訳」する?! そんなことが本当に可能なのでしょうか?

かなり前に「コンピュータは論理の世界と現実の世界をどのようにつないでいるのですか?」 といったような質問をYahoo!知恵袋で見たことがあります。 その人にとってコンピュータはまさに魔法であり、異世界と通じあい問いと答えを交換するゲートだったのです。 それと同じことが自分にも、コンパイラにおいて起きていました。

しかし、Cコンパイラを一度書くとコンパイラは魔法ではなくなります。 理解できる技術として身につけることができるのです。

幅広い知識が自然に身につく

Cコンパイラを書くことで様々な知識を身につけることができて、 コンピュータの学習曲線の大きなジャンプを乗り越えることができます。 以下、自分が理解できて特に嬉しかったことを書いていきます。

アセンブリ

以前コンパイラを書こうと思った時は、 まずアセンブリ を読めるようになろうと思ってアセンブリ手書きから学習をはじめました。 しかしいきなりアセンブリを学ぼうとすると前提知識が大量に必要になり、 Hello Worldの文面を書き換える程度の改造しかできませんでした。

まずアセンブリの基本的な考え方を知らないので、 命令単体のリファレンスを読んでもそれが結局何をしたいのか理解できず、 したがってコードの意図が全くわからないのです。 他の言語と同じノリでいきなりHello Worldから始めてしまったのも敗因かもしれません。

9ccは非常に単純なアセンブリから出発しており、しかも期待される実行結果がテストとして書かれています。 プログラムに書いてあることがそのコードを生成するのに必要なすべてなので、 学習範囲をその中に書いてあることだけに絞ることができます。 また、コンパイラのコードは本質的にアセンブリを書いていく手順を表しているので、 アセンブリのこの行になぜこの命令があるのか、ということを理解する助けになります。

コンパイル対象のC言語が難しくなっていくにつれてアセンブリも長く複雑になっていきますが、 1コミットあたりの変更は少ないのでその場その場で学ばなければいけないことは非常に少なくなります。 実際1コミットあたりで学んだ命令は平均して1個未満という感じだったと思います。

パーサー

1つづつコミットを読んでいくといきなり「 再帰下降構文解析 器を作る」というコミットが現れます。 そこそこ行数が多くて苦労しましたが、その時点でのコンパイル対象はカッコもないただの四則演算だったので、 それを処理するパーサーも十分小さく、無事に理解できました。

基本がわかればあとは簡単です。 パーサジェネレータなどという自動化ツールが存在するくらいには同じことの繰り返しなので、 難しそうな構文もパターンにあてはめればスムースに理解できます。

意味解析

パースを行うと構文木ができあがります。 これを書き換えたりすることでさまざまな処理を行います。 意味解析、という言葉は具体的に何をすればいいのかわかりにくいです。 コンパイラについて述べた文章でも意味解析については抽象的な説明が行われることが多く、 なんだか魔法のような印象を受けます。

しかし具体的なコードを読めば何をしているか理解できます。 具体的な内容を理解した上で感想を言うと、 どうも直接関連しないさまざまな処理をおおざっぱにまとめて「意味解析」 と呼んでいることで混乱を呼ぶのではないか、という気がします。

各種ツール

開発に関連したツールにも習熟しました。 gccのオプションも知らないものがたくさんあったし、 そもそもC言語の仕様をここまで詳細に調べたこともありませんでした。 gitの使い方もかなり上手になりました。 何度もコミットを移動するので、効率的な方法を多数身につけました。

gdbの使い方を理解したのはかなり大きいかもしれません。 これまではセグフォが起きると原因になりそうなところを総当りでprintfデバッグして、 結局わからなくて諦めていた記憶があります。

色んな応用の世界が広がる

一度Cコンパイラの具体的実装を理解すると、それを応用してさまざまなものが作れるとわかります。 まず他の言語やISAに対するコンパイラを書くことができます。 今到達している範囲で定数畳み込みはまだ出てきていませんが、 今までのコードからどんなものを書けばいいか大体推測できます。 さらに、式変形を自動で行うタイプのプログラムもだいたい作れそうな気がしてきます。 実際論理式の展開くらいなら1日あればフルスクラッチから書けるようになります。

あとmalloc動画 の言ってることが理解できるようになりました。

Cコンパイラを作ったことによって、その知識を応用できるようになり、 作れるものの範囲が一気に広がりました。

9ccと「低レイヤを知りたい人のための Cコンパイラ作成入門」の相違点

d9ccを書いている途中で「低レイヤを知りたい人のための Cコンパイラ作成入門」の一部が 公開されましたが、 9ccはこの本と作成過程が異なるようです。 本ではスタックマシンを作っていましたが、9ccでは最初からレジスタマシンを書き始めています。 スタックにまかせている部分を自分で書くことになるわけですが、そんなに難しいとも思わなかったので、 人によっては自分のように9ccのコミットログをたどる学習法のほうがしっくりくるかもしれません。

なぜD言語なのか

Cコンパイラを書くメリットは上のとおりですが、ではなぜD言語でなければいけないのでしょうか? 一般的には他の言語で書いてもいいし、C言語で書けばセルフホストができます。 しかし自分にはD言語を使う理由があります。

コンパイラが書ける

Cコンパイラくらいbrainf*ckですら作れる のでこれはそんなに重要ではないですが、 D言語で書かれたコンパイラがたくさんあります。 まずD言語のコンパイラDMDそのものがD言語で書かれています。

9ccを元にD言語でコンパイラを書いた人が自分以外にいたりもします。

alphaKAI/d9cc: A tiny C compiler in Dlang

これはコミットログを順にたどっている自分とは違い、9ccの最新バージョンを直接Dに移植したもののようです。 自分のd9ccは9ccのコードの意味を少しづつ理解しながら手探りで書いたのでだいぶコードが混乱していますが、 こちらのd9ccはビルドツールとしてDUBを使っていたりして、少しすっきりしています。

ともかく、言語の知名度の割に9ccの移植が複数存在するほどD言語はこの分野に向いているわけです。

C言語に近い

D言語は「C言語風の構文を持つ静的型付け言語」であり、 基本的には高機能なCとして書くことができます。 コピペにならないようにC以外の言語を使いたかったのですが、 一方でC言語から離れすぎると書き直すのが大変になるので、 C言語と似ていながらC++のように完全な互換性があるわけでもないD言語は妥当な選択肢のひとつでした。

書き慣れている

そしてこれが最も大きな理由かもしれません。 自分はD言語を書き慣れていました。 先程話したように自分はコンパイラを作ろうとして何度も挫折してきました。 できればセルフホストとかしてみたいですが、 まず一度スタンダードなものを完成させられないようでは、応用もできません。

なので今回こそは成功させようと、「Cコンパイラを作る」以外のあらゆる点で背伸びをせず、 「まず一度完成させること」を大事にしました。 言語選択においてもそれを考慮した結果、言語特有の問題で詰んだりしないような、 書き慣れているD言語が選ばれました。

D言語は非常に書きやすく、やりたいことを実現するのがとても簡単な言語です。 あなたも「現実的なプログラマのための、 現実的な言語」でコンパイラを書きましょう。

Cコンパイラを書け

自分はCコンパイラを書いて得た知識で作ってみたいものがいろいろできたので今後はそれを書きます。 言語やISAを変えて別のコンパイラを作ってみるのもいいかもしれません。

Cコンパイラは書くだけで大量の知識が手に入る最強の教材です。 そしてD言語は書くだけで救われる最強の言語です。 したがって全人類はD言語でCコンパイラを書くべきです。

コンパイラの構造などに関してコメントが書かれている9ccに対して、 d9ccはアセンブリなどの周辺知識に関して多くのコメントを残しており、 しかも日本語なので(何かのバグでちょっと壊れてるけど)、 9ccと一緒に読むと9cc単体よりも理解がしやすいと思います。

以下はd9ccのコミットログを整形したものです。 途中調べたサイトなどのリンクが残してあるので、 この記事を読んでコンパイラが作りたくなったら参考にするといいかもしれません。

日記(コミットログ)

1 file changed, 21 insertions(+)