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 が使えるようです。