GCC treeの視覚化 で作成したtreeを読んでみました。
treeはgccのfront endで使われている構文木を表すデータ構造です。
ソースコードとtreeの図
- 説明するソースコードと、gcc-4.xのtree dumpから作った図です。
int main() {
return 0;
}
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型です。
式の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の関数で作成する例が載っています。