compilium v2 (in progress)の工夫点

この記事は、言語実装アドベントカレンダーの7日目にあたります。

ちなみに、これを書いている現在は2018年12月7日の12:00です。果たして今日中に記事を公開することはできるのでしょうか…。

compilium v2とは

github.com

compiliumは、hikaliumが開発しているC11準拠(予定)のCコンパイラです。C言語で書かれています。

compilium v2では、v1での反省点およびセキュリティ・キャンプ全国大会2018のCコンパイラ自作ゼミでの知見をもとに、よりわかりやすく単純でインクリメンタルに開発できることを目標に開発しています。

この記事では、これらの得られた知見とともに、それらが実際にどのようにcompilium v2に活かされているかを紹介します。

最初からレジスタマシンとしてアセンブリを出力する

当初、Cコンパイラゼミでは、スタックマシンとしてアセンブリを出力するよう受講者のみなさんにお願いしていました。

これは、レジスタ割り当てを最初から考慮するのは大変であり、スタックマシンならばシンプルに実装できるという予想に基づいたものでした。

実際、スタックマシンを採用したことで、式のコード生成については、かなりスムーズに習得してもらうことができました。

一方で、スタックマシンの弱点としては、アセンブリレベルでのデバッグが非常に困難になることが挙げられます。 これは、出力の多くが本質的な計算ではなくpush/popに占められることと、各計算の間で値がどのように伝播するかわかりづらいことが原因でした。

そこで、レジスタマシンの可能性を再考してみたところ、式に閉じたレジスタマシンであれば、複雑な式を与えない限り、単純なコードでもうまく生成でき、出力も自然に近いアセンブリになることがわかりました。

簡単なレジスタマシンの実装

式(Expression)に閉じたレジスタマシン、つまり、異なる式の間で値を引き継いだりしないようなものは容易に実装することができます。 具体的には、値であれば新しくレジスタを確保し、演算子であればその各オペランドに対してレジスタ割り当てを実行したのち、戻り値を戻すためのレジスタ一つをのぞいてすべて解放する、という手順を行えばよいです。

戻り値を戻すためのレジスタとして、演算子の左側のオペランドレジスタを利用することにした場合、2 + 3 * 5は、下の図のように割り当てることができます(R, G, Bはそれぞれレジスタ名です)。

f:id:hikalium:20181207192720g:plain
レジスタ割り当てのようす

実際には、この式は2つのレジスタで計算可能な式(3*5を先に計算すればよい)なのですが、そんなことは気にしたら負けです。 とにかく単純に実装することがcompiliumの目的ですからね!

利用可能なレジスタ

SystemV ABI において、保存せずに破壊しても問題ない汎用レジスタは、以下のものになります。

rax, rcx, rdx, rsi, rdi, r8, r9, r10, r11

このうち、

  • raxは戻り値の格納に使われる
  • rdxはmul, div系で変更される可能性がある(MUL r/m64: RDX:RAX ← RAX ∗ r/m64))
  • rcxはシフト系演算でオペランドとして利用される(シフト系演算のシフト量は、レジスタで指定する場合CLしか使えない)

ことから、単純のため利用しないことにすると、気軽に自由に使えるレジスタ

rsi, rdi, r8, r9, r10, r11

の6つになります。

なぜこれで大体うまくいくのか

f:id:hikalium:20181207200845p:plain
レジスタ割り当ての例

上の図を参照してもらえればわかるように、ASTが右に伸びるほど、必要なレジスタの個数が増えていることがわかります。

ASTが右に伸びるということは、右側のほうを先に計算する必要がある、つまり、右側の演算子の優先順位が高いか、同じ優先順位でも右結合の場合か、もしくはかっこで包まれている場合に限られます。

C言語二項演算子で右結合性のものはassignment-operatorのみであり、これを連続して使うような場合はあまり多くありません。

したがって、優先順位の異なる演算子や括弧をひとつの式の中で多用しないかぎり、このアルゴリズムでも大体うまくいくわけです。

うまくいかなかったらどうするかって?ソースを書き換えちゃいましょう!変数を使えばどんな式もコンパイルできる形に確実に書き直せますよ!

エラーメッセージの改善

compilium v1では、エラー時にその行番号を報告することしかできませんでした。 しかし、式のテストは1行にソースが押し込められてしまうことから、行番号は大して役にたちませんでした。 そこで、compilium v2では、エラー発生時に該当トークンの前後を表示できるように実装されました。

{int *a; return sizeof(a);}
                ^^^^^^
Error: Generate: Not implemented unary prefix op

assignment-expression のパーストリック

assignment-expression:
    conditional-expression
    unary-expression assignment-operator assignment-expression

assignment-expressionが右再帰であることは先ほど触れましたが、右再帰とはいっても単純な右再帰ではありません。 再帰の終端点では conditional-expression が許されるのに対し、再帰途中の左辺には unary-expressionしか許されません。 パーサを書いていて、ここをどう処理するか悩んでいるみなさんも多いのではないでしょうか。(もしかしてみんな悩まない!?)

compilium v2の実装にあたり、この問題の解決策をいくつか考えてみました。

方法1: unary-expressionを先読みする

conditional-expressionは、cast-expressionの場合を除いて、先頭にunary-expressionがくる。

そして、cast-expressionの場合に左側に来る要素はunary-expressionとして認識される可能性がない( type-name ) ので、unary-expressionを先読みして直後にassignment-operatorがくるか調べ、来なければそのunary-expressionを渡しつつconditional-expressionをパースすれば良い。

  • 利点:
    • 文法に沿ったパース結果を得られる
  • 欠点:
    • パーサの一部のみ引数が増える

方法2: 試してみてだめだったら巻き戻す

compilium v1で採用していた方法

  • 利点
    • 文法に沿ったパース結果を得られる
  • 欠点
    • 巻き戻すのはださい(このためだけにTokenStreamの位置を保存しなければいけない)
    • 効率が悪い(2回同じことをすることになる可能性がある)

方法3: conditional-expressionとして読んでから、読んだトークンのクラスを判定する

  • 利点:
    • 文法に沿ったパース結果を得られる
    • パーサの引数の数を統一できる
  • 欠点:
    • ASTのタイプを注意深く設計しなければならない
    • unary-expression以下のASTタイプを新たに実装した際に判定条件に追加しなければならない
      • unary-expression, postfix-expression, primary-expression がunary-expressionに含まれる。

方法4: 単純な右再起になるよう構文を変更してしまう

assignment-expression:
    conditional-expression
    conditional-expression assignment-operator assignment-expression
    ^^^^^^^^^^^^^^^^^^^^^^

9ccで採用されている方法 compilium v2でもこれを採用することにした。

  • 利点:
    • パーサの記述が楽
  • 欠点:
    • 構文にあてはまらない入力をパースできてしまう
      • a+1 = 2 のような構文は本来パースできない
    • ただし意味解析で除去できる(左辺がlvalueかどうかチェックすればよい)
    • 副作用として、条件演算子を左辺値として用いることができるようになる。
      • これはgcc拡張である
      • しかもこの構文はC++ではvalid(つまりこっちのほうが自然)

というわけで、皆さんも方法4を採用するといいと思います!(楽なので)

主要な構造体をTokenとASTNodeのみに集約

compilium v1 では、型がついていないと不安だし、メモリを効率よく使いたいという思いから、ASTの各タイプごとに構造体を用意していました。

しかし、これは機能追加ごとのコード量が増大する要因となり、またほぼ同一内容のコードがソース中に増える原因となりました。

compilium v2 では、思い切ってASTおよび型情報を単一の構造体ASTNodeに押し込めることにしました。

これは、メモリ効率の低下を招きますが、まあ昨今みんなRAMは32GB以上積んでいると思われますので問題ないでしょう…。

(やっぱり無理して書くよりも気楽に書いた方がいいですよ。)

おわりに

本来はもっと真面目にもっと詳細に語りたかったのですが、ちょっと疲れてしまってゆるふわになってしまいました。ごめんなさい…。

特に型の話についてはもう少し語りたいので、12/23のC言語アドベントカレンダーでまた書きたいと思います。

私もコンパイラ初心者なので、何か指摘や質問等あればぜひTwitterのほうまでお願いします!

年内にはv2がセルフホストできるようにがんばりますので、どうか生暖かい目で見守っていてください…。

今年度セキュリティキャンプ2018のCコンパイラゼミに参加してくださったみなさん、そして一緒に講師を担当していただいたRuiさんには、実装方法など様々な面でよい刺激をいただきました。ありがとうございます。

ということで、

みなさんもCコンパイラ書きましょうね?

楽しいぞ!

参考文献