C言語完全に理解したい　木構造編

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

生きています

前から更新が大分空きましたが生きています。よかったですね。勉強はちょっとずつ進んでいるので木構造とLLVM-IRについて書こうと思います。

木構造

木構造は自己参照構造体などで実装される、平たく言えばリスト構造の仲間です。リスト構造ではノードとノードが直線的につながっているのに対し、木構造は一つのノードから複数のノードが派生する構造になっています。一番根っこから幹を、枝を伸ばしていく姿から木構造と呼ばれるそうです。

式の評価と二分木

二分木は木構造のうち、親ノードから子ノードがかならず2つ派生するものを指します。二分木は主に2分探索に使われますが、四則演算の構文木を構成することにも向いています。なぜなら四則演算はすべて二項演算子で表されるからです。
　例えば2 * (4 + 5)という式なら

みたいな図で表すことができますね！この構造がわかれば式を評価するまで後少しです。計算は枝の先の方から順にやっていく必要が有りますが、それは簡単なルールで実装できます。*から出発して、左→右の順で子ノードを見ていき（赤い矢印）、子ノードがなければ親ノードに戻る（青い矢印）

親ノードに戻る前に処理を実行するとすると実行される順番は

このようになりますね！後は適当に処理をしていけばいいです。簡単なのだとこんな感じかな？

1. 1番目のレジスタに2を書き込む
2. 2番目のレジスタに4を書き込む
3. 3番目のレジスタに5を書き込む
4. 4番目のレジスタに2番目のレジスタの値と3番目のレジスタの値の和を書き込む
5. 5番目のレジスタに1番目のレジスタの値と4番目のレジスタの値の積を書き込む

これをLLVM-IR風に書くと

%1= alloca i32, align 4
store i32 2, i32* %1, align 4
%2= load i32, i32* %1, align 4
%3= alloca i32, align 4
store i32 4, i32* %3, align 4
%4= load i32, i32* %3, align 4
%5= alloca i32, align 4
store i32 5, i32* %5, align 4
%6= load i32, i32* %5, align 4
%7 = add i32 %4, %6
%8 = mul i32 %2, %7

となるわけです。意味がわかりませんね！

LLVMの命令

詳しいことはリファレンスを見ればいいんですが…

https://llvm.org/docs/LangRef.html

ここに出てくる命令はalloca, store, load, add, mulの5つです。
allocaはその名の通りメモリを確保してポインタを返す命令です。
storeはポインタが指すメモリに値を書き込む命令、
loadはポインタが指すメモリの内容を読み込む命令です。

add, mul命令は足し算、掛け算ですが、普通の機械とは違っていて3オペランドコードとなっているのが特徴です。%からはじまる%1みたいな文字はレジスタを表しています。詳しい話はレジスタの割当とつながっているのですが、中間表現の段階では無限にレジスタを使え、一度代入したら変更することはできないという特徴をもっています。

ここまで来ると大体四則演算のみの数式をLLVMの命令に直すことができるようになっているでしょう。まず、子ノードがあるノードはかならず四則演算のノードです。逆に子ノードがなければそのノードは数字のノードです。この前提の上で数式の木構造を評価するには、以下のルールに従えばいいのです。

1. 数字のノード（子ノードを持たない）が呼び出されたら
　ノードが持ってる値を次のレジスタに入れる。

2. 四則演算のノードが呼び出されたら
　左の子ノードを呼び出す、右の子ノードを呼び出す→それぞれノードの値が入っているレジスタどうしの計算結果を次のレジスタに入れる。

どうです簡単でしょう！？コードはもうなんかしんどいのでここには書きません。