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の関数で作成する例が載っています。