GCC treeの視覚化

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 的语法树结构](http://d1.amobbs.com/bbs_upload782111/files_33/ourdev_584680VL3TGD.pdf) の図を見ながら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.png](https://qiita-image-store.s3.amazonaws.com/0/42120/cbcf20d1-1417-cc65-ce87-c342ceaf98c4.png)


* test.cの内容

```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  
```



## 変換ツールのソースコード調査
```awk:pre.awk
#! /usr/local/bin/gawk -f
/^[^;]/{
  gsub(/^@/, "~@", $0);
  gsub(/( *):( *)/, ":", $0);
  print;
}
```
* ソースコードの説明
 * RSを改行から@~に変えるための準備。
 * :前後の余計な空白を削除


```awk: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