GCCのtreeを理解するために、treeをgraphvizで視覚化してみました。

treeはgccのfront endで使われている構文木を表すデータ構造です。
最初はテキストエディタでgraphvizのdot形式で書いてみたけど、変換ツールがあったので、変換ツールを使ってみました。

まとめ

gccのオプション -fdump-tree-original-raw で最適化前のtreeをdumpすることができる。
treeのdumpは独自のフォーマットで関数毎に生成する。
関数が一つの場合に、treeのdumpをgraphvizのdot形式に変換するツールがある。
変換したdotファイルをgraphvizで描画するとtreeが視覚化できる。

図の読み方は別エンントリで説明する予定とします。

テキストエディタで書いてみた

変数宣言のtreeを GCC 的语法树结构の図を見ながらgraphvizで図にしてみました。　その話は割愛します

変換ツールを使ってみた

テキストエディタで書くのは、勉強になって良いのですが、時間もかかるし、正確に書けたかどうかも良くわからないです。
treeのdumpをgraphvizに変換するツールを探したら、alohakunさんのツールがあったので使ってみました。
元記事は http://alohakun.blog7.fc2.com/blog-entry-355.html にあったのですが、現在消えています。
web archive に残っていました。 http://web.archive.org/web/20080724225353/http://alohakun.blog7.fc2.com/blog-entry-355.html
英語での解説もありました。 http://digitocero.com/en/blog/exporting-and-visualizing-gccs-abstract-syntax-tree-ast
githubのgistにもありました。 https://gist.github.com/tonyseek/4161012

変換手順

上記のURLからpre.awkとtree.awkを入手する。
gawk (GNU awk)をインストールする。
pre.awkとtree.awkの先頭にあるawkのpathを修正する。
chmod で実行権限を付加する。
gcc のオプション -fdump-tree-original-raw を使って、パース直後のtreeをdumpする。

gcc -fdump-tree-original-raw test.c

test.c.003t.originalが生成される。
変換ツールpre.awkとtreeviz.awkを使う。

./pre.awk test.c.003t.original |./treeviz.awk  >test.dot

graphvizでグラフを描画する。

dot -Tpng test.dot  -o test.png

test.pngを表示する

test.cの内容

int main() {
    return 0;
}

test.c.003t.original の内容内容
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

変換ツールのソースコード調査

pre.awk

# ! /usr/local/bin/gawk -f
/^[^;]/{
  gsub(/^@/, "~@", $0);
  gsub(/( *):( *)/, ":", $0);
  print;
}

ソースコードの説明
RSを改行から@~に変えるための準備。
:前後の余計な空白を削除

treeviz.awk

# ! /usr/local/bin/gawk -f
BEGIN {RS = "~@"; printf "digraph G {\n  node [shape = record];";}
/^[0-9]/{
  gsub("op ", "op");
  s = sprintf("%s [label = \"{%s | {", $1, $1);
  for(i = 2; i < NF ; i++)
    s = s sprintf("%s | ", $i);  
  s = s sprintf("%s}}\"];\n", $i);
 
  $0 = s;
  while (/([a-zA-Z0-9]+):@([0-9]+)/){
    format = sprintf("<\\1>\\1 \\3\n   %s:\\1 -> \\2;", $1);
    $0 = gensub(/([a-zA-Z0-9]+):@([0-9]+)(.*)$/, format, "g"); 
  };
  printf "    %s\n", $0;
}
END {print "}"}

ソースコードの説明
複数行にまたがるノードを簡単に取り扱うために、awkのRSを改行から"~@"に変更、こうするとノードと行が1対1に対応する。
graphvizのヘッダー部分を表示
要素名に"op 1"のように空白があると面倒なので、空白を除去
ノードのラベルの先頭を追加
各要素を取り出し、ラベルに追加
ラベルを終了
ラベルのうち、リンクを張る必要があるものを抽出
リンクをはるものはラベルをからに修正
リンクを追加
変更箇所
要素名に"op 1"のように空白があると面倒なので、空白を除去
リンクを張る必要のある要素を抽出する正規表現を変更
制限事項
このツールはdumpファイルにtreeが1つの場合にのみ動作する。複数の関数があると、同じ名前のノードが複数存在してしまうので変換に失敗する。

gccの-fdump-tree-original-rawの意味

gcc 4.9.3 のマニュアルによると https://gcc.gnu.org/onlinedocs/gcc-4.9.3/gcc/Debugging-Options.html
-fdump-tree と -original と -raw と区分けして説明を読む。

-fdump-tree-switch
-fdump-tree-switch-options
-fdump-tree-switch-options=filename
Control the dumping at various stages of processing the intermediate language tree to a file. 
The file name is generated by appending a switch-specific suffix to the source file name, and 
the file is created in the same directory as the output file. In case of =filename option, the 
dump is output on the given file instead of the auto named dump files. If the ‘-options’ form is 
used, options is a list of ‘-’ separated options which control the details of the dump. Not all 
options are applicable to all dumps; those that are not meaningful are ignored. The following 
options are available

...

‘raw’
Print a raw representation of the tree. By default, trees are pretty-printed into a C-like representation. 

...

‘original’
Dump before any tree based optimization, to file.original.

dumpの実装は、dumpfile.cにあります。
-fdumpオプションの解析は dumpfile.c の dump_switch_p_1()で行います。
-fdumpオプションはテーブル dump_files[] と dump_options[]の文字列を比較する。
dump_files はtree-original の部分の文字列
dump_optionsはrawの部分の文字列
過去のマニュアルを見たところ gcc-4.x以降ならCで-fdump-tree-original-raw が使えるようです。

参考

GCC treeのデータ構造 http://qiita.com/eggman/items/73cc4be27e5db9c6d6b9
GCC 的语法树结构
http://d1.amobbs.com/bbs_upload782111/files_33/ourdev_584680VL3TGD.pdf