Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

GCC treeの読み方

More than 3 years have passed since last update.

GCC treeの視覚化 で作成したtreeを読んでみました。

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

ソースコードとtreeの図

  • 説明するソースコードと、gcc-4.xのtree dumpから作った図です。
int main() {
    return 0;
}

test.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で表示されません(例: 13のノード)。dumpでは値をsignedとして表示します。lowにuint64_tの最大値が入っていると-1と表示されます。(例:22のノード)
  • 値が負の場合は、2の補数で格納するので、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基本形は3つのノードが含まれます。
    • 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

式の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  

参考

eggman
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away