GCC treeの読み方

[GCC treeの視覚化](http://qiita.com/eggman/items/2a98c9c901290bfde703) で作成したtreeを読んでみました。

treeはgccのfront endで使われている構文木を表すデータ構造です。

# ソースコードとtreeの図
* 説明するソースコードと、gcc-4.xのtree dumpから作った図です。

```c
int main() {
    return 0;
}
```

![test.png](https://qiita-image-store.s3.amazonaws.com/0/42120/d0f7f218-69dc-db3f-c306-b021d20bb108.png)

# treeの読み方
* 四角形がtree nodeに1対1に対応しています。
* 四角形上段の数字はnodeのユニークIDです。
* 四角形下段の左端の要素はnodeのcodeです。nodeの種類を表します。
* 四角形下段codeより右にある要素はtree codeや、その他条件により異なります。
* 矢印がnodeの要素からnodeへ参照していることを示します。
* nodeの情報はnode内に保持する場合、nodeを参照する場合、ポインタを参照する場合があります。
* gccのtree dumpは、treeのすべての情報を出力しているわけではないです。もっと詳しい情報が知りたい人はソースコードを読みましょう。

# 整数定数のtree
* 整数定数のcodeはinteger_cstです。　要素として型(type)と値(high,low)を持ちます。
* 値は上位 highと下位 low にわかれています。highが0の場合は、highはdumpで表示されません(例:
１３のノード)。dumpでは値をsignedとして表示します。lowにuint64_tの最大値が入っていると-1と表示されます。（例:22のノード)
* 値が負の場合は、２の補数で格納するので、highが-1 になります。(例:12のノード)
* tree dumpの図では、9, 11, 12,　13, 20, 21, 22が整数定数のnodeです。
* 図の中のinteger_cstのtree
 * 9 int型で値が0
 * 11 bitsizetype型で値が32
 * 12 int型-2147483648
 * 13 int型で値が2147483647
 * 20 bitsizetype型で値が64
 * 21 bitsizetype型で値が0
 * 21 bitsizetype型で値が0xFFFFFFFF

# 型宣言のtree

* treeの図には、voidの型宣言 と intの型宣言 があります。
*  型宣言のtree基本形は３つのノードが含まれます。
 * type_decl 型宣言 nameとtypeの参照を持つ
 * identifer_node 型名 文字列のポインタ参照strgと文字列長lengtを持つ
 * なんとか_type 型 型により持つ要素が異なる。nameとalgnは最低限ある。 (algnがよくわからない。)
* 2, 4, 8がvoidの型宣言です。
 * 4 型宣言
 * 6 型名 "void" 
 * 2 型 void_typeでalgnが8
* 7, 10, 12, 13, 15がintの型宣言です。
 * 10 型を宣言
 * 15 型名 "int"
 * 7 型はintegerで精度、signed、alignが32で、名前、サイズ、最小値、最大値の参照を持つ。
 * 11 型のサイズが32
 * 12 型の最小値が-2147483648
 * 13 型の最大値が2147483647
* 図を見ると分かるのですが、tree内で型を参照する場合は2,11の型のtreeを参照します。

# GCC internal types のtree
* GCC internal typesはGCCが内部で使う型です。通常と異なり型宣言がありません。
* 16, 19, 20, 21, 23 がGCC internal types の bitsizetypeのtreeす。 type_declがリンクされていません。
　* 16 型 integerでサイズ、精度、unsigned、最小値、最大値
　* 19 型名 "bitsizetype"
　* 20 型のサイズが64bit
　* 21 型の最小値0
　* 22 型の最大値0xFFFFFFFF
 

# 型宣言を省略したtree の図
* 型を解説したので、型の宣言を省略した図を描画しました。
* 2がvoid型、7がint型、16がbitsizetype型です。

![t1.png](https://qiita-image-store.s3.amazonaws.com/0/42120/fe20da16-beb7-b182-01a3-e54dcd9eb4ff.png)

# 式のtree
* treeでは演算などを式で表現します。 _exprが末尾にあるcodeを持つnodeが式です。
* tree dumpの図ではbind_exprとreturn_exprとmodify_exprがあります。
* modify_expr
 * modify_exprは代入文です。ソースコードに代入文はありませんが、関数の戻り値を表すのにmodify_exprを使います。
 * modify_exprは要素にtypeとop1とop2を持ちます。　typeは式の型、op1は代入先のnode、op2は代入元のnode
 * なので5のノードは、整数定数0を戻り値にint型で代入するという意味です。 (戻り値に代入というのがよく分からないのですが…)
* return_expr
 * return_exprは関数からのリターンです。
 * return_epxrは要素にtypeとexprを持ちます。
 * なので3のノードは、5のmodifi_exprをvoid型でリターンするという意味です。  
* bind_expr
 * bind_exprはblockを表現するnodeです。
 * tree dumpの図ではmain関数全体を一つのブロックとして表現しています。
 * bind_epxrは実際はもっと要素があるのですが、この例では型typeとブロックの中身bodyのみです。

# 関数のtree
* 関数の定義は以下のnodeからできています。
 * function_decl 関数宣言
 * function_type 引数の型
 * result_decl 戻り値の宣言
* 7, 8, 9, 11, 14, 17, 18 が関数定義です。
 * 14 関数宣言 名前は"main"、sizeの参照、ファイル名と行数、extern
 * 18 関数の型 sizeは32 戻り値はint型 unqlがよく分からない unqualified の意味らしい
 * 23 関数の型 sizeは32 戻り値はint型
 * 8 戻り値の宣言 型はint、scpeはノード14、ファイル名と行数、sizeの参照、algnが32


# つづく
* だいぶtreeを読めるようになってきたけど、まだ足りないので、変数、if文、for文、関数呼び出し、などのtreeの読み方を調査する予定。

# その他
* よく分からない return_exprがvoid型なのはどうしてか
* function_typeが2個あるのはなぜか

# tree dump
* treeのdumpも置いときます。

```

;; Function main (null)
;; enabled by -tree-original

@1      bind_expr        type: @2       body: @3      
@2      void_type        name: @4       algn: 8       
@3      return_expr      type: @2       expr: @5      
@4      type_decl        name: @6       type: @2      
@5      modify_expr      type: @7       op 0: @8       op 1: @9      
@6      identifier_node  strg: void     lngt: 4       
@7      integer_type     name: @10      size: @11      algn: 32      
                         prec: 32       sign: signed   min : @12     
                         max : @13     
@8      result_decl      type: @7       scpe: @14      srcp: test.c:1      
                         note: artificial              size: @11     
                         algn: 32      
@9      integer_cst      type: @7       low : 0       
@10     type_decl        name: @15      type: @7      
@11     integer_cst      type: @16      low : 32      
@12     integer_cst      type: @7       high: -1       low : -2147483648 
@13     integer_cst      type: @7       low : 2147483647 
@14     function_decl    name: @17      type: @18      srcp: test.c:1      
                         link: extern  
@15     identifier_node  strg: int      lngt: 3       
@16     integer_type     name: @19      size: @20      algn: 64      
                         prec: 64       sign: unsigned min : @21     
                         max : @22     
@17     identifier_node  strg: main     lngt: 4       
@18     function_type    unql: @23      size: @11      algn: 32      
                         retn: @7      
@19     identifier_node  strg: bitsizetype             lngt: 11      
@20     integer_cst      type: @16      low : 64      
@21     integer_cst      type: @16      low : 0       
@22     integer_cst      type: @16      low : -1      
@23     function_type    size: @11      algn: 32       retn: @7  
```


# 参考
* http://www.ospn.jp/osc2008-do/gcc_hacks.pdf
 * 今回のサンプルソースと同じコードををgccの関数で作成する例が載っています。