GCC treeの視覚化

13053 ワード
GCC C データ構造 C テキストリンク

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で図にしてみました。　その話は割愛します

変換ツールを使ってみた

変換手順

  • 上記の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の意味

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

参考