C言語完全に理解したい　LLVMと変数編

お約束
C言語なんもわからん≒C言語のコンパイラ書ける
C言語完全に理解≒ズルすればC言語のコンパイラ書ける
C++のライブラリを使って、C言語からLLVM-IRを出力するフロントエンド部を作りたい。

変数を扱ってみよう

前回か前々回の投稿までで、数式を評価できるところまで行きましたが、まだ変数を扱う機能は入れていません。変数を扱うのはそんなに難しいことではないのですが、LLVMのレジスタにはいくつか著しい特徴があるのでそれに気をつけなければなりません。

LLVMってなんだっけ

またそこからってなるかもしれませんがお付き合いください。
LLVMはかつてLow Level Virtual Machineと言われていたとおり、JavaにおけるVMのような存在ですが、VM向けのコードを中間表現として任意の処理系（x86とかarmとか）に向けたバイナリを出力することが多いです。LLVMは中間表現(LLVM-IR)での最適化のツールを提供することによってコンパイラを手軽に作れるというのが強みです。LLVMを利用した最も有名なものはC/C++向けのclang/clang++でしょう。

必然的にclang/clang++やLLVMはgccとはライバル関係にありますし、多くのLinuxディストリビューションでgccが標準的なコンパイラであるのに対し、BSD系ではclang/clang++がその地位にあるのは興味深いです。実際のところLinuxのカーネルはgccの拡張機能に頼るところが大きくかなり相性は悪いみたいです。

私はGentoo Linuxを使っているので何のツールチェインでビルドするかはまったく自由ですが、やっぱり普段はgccを使ってしまいます。

LLVMのレジスタ

LLVM-IRのレジスタは少し特殊で、一回しか値を代入できない決まりになっています。こんなマシンが実際にあったらおかしい気もしますが、これは静的単一代入と呼ばれるコンパイラの中間表現ではよく使われるもので、物理的なレジスタへの割当や、無駄コードの削除などさまざまなメリットがあるらしいですが実装は難しいです。例えば分岐があったときにどういう振る舞いをするか考えるだけで怖いです。

int x = A;
if(cond)
    x--;
else
    x++;

y = x;

これを静的単一代入に直したらどうなるでしょうか？ファイノードなるものによって解決するらしいですが、正直知恵熱がでそうなくらい難しそうです。しかし、LLVMではそこまで気にする必要はありません。なぜならメモリは静的単一代入ではないからです。

LLVMではalloca命令をつかってスタックメモリを確保して、レジスタにそのアドレスを保存することができます。そして静的単一代入のルールはそのアドレスに対する操作を何ら縛りません。

%1 = add i32 1, %1 ; NG

%3 = load i32, i32* %2
%4 = add i32 1, %3
store i32 %4, i32* %2

意味するところとしては上のコードと下のコードは%1にインクリメントするか%2の指すアドレスにインクリメントするかの違いしかありません。ですが上のコードは弾かれ、下のコードは通ります。怖いですね。

ここまで引っ張ってアレですが、要するにallocaでスタックメモリを確保しておけば大丈夫そうってことですね。パフォーマンスのことはしりません。

書いてて疲れたのであとのことはまた来週考えます。