制御フローグラフ

制御フローグラフ（せいぎょフローグラフ、英: Control Flow Graph, CFG）は、プログラムを実行したときに通る可能性のある全経路をグラフで表したものである。この場合、ノードは基本ブロック（すなわち、分岐を全く含まない逐次的コード列であって、途中に分岐先もない）を表し、ノードとノードをつなぐ有向エッジは、あるブロックから別ブロックへのジャンプを意味する。一般に、グラフ全体の入口となる入口ブロックと、出口となる出口ブロックがある。

CFGはコンパイラ最適化や静的コード解析ツールでよく使われる。

最適化において利用されるグラフの属性として、到達可能性(reachability)がある。あるブロックまたは部分グラフが、入口ブロックを含む部分グラフと連結していない場合、そのブロックは決して実行されることはなく、いわゆる到達不能コードであって、容易に削除可能である。出口ブロックが入口ブロックから到達不能な場合、無限ループとなっている（あらゆる無限ループを検出できるわけではない。停止性問題を参照のこと）。プログラマが明示的に到達できないコードや無限ループを書かなくても、そのような状況になることはある。例えば、定数伝播や定数畳み込みといった最適化を行った後に分岐スレッディングを行うと、元々は別々だった基本ブロックが1つにまとめられることがあり、エッジがCFGから除去され、グラフの一部が連結されなくなることがある。

用語

制御フローグラフに関連して使われる用語を列挙する。

入口ブロック(enter block): グラフの制御の入口となるブロック
出口ブロック(exit block): グラフの制御の出口となるブロック
後退エッジ(back edge): グラフを深さ優先探索したときに、上位のノードに戻るようになっているエッジ
クリティカルエッジ(critical edge): あるブロックから出ている唯一のエッジでもなく、あるブロックに入っている唯一のエッジでもないエッジ。このようなエッジ群は途中に新たなノード（ブロック）を追加して、そこで何からの計算が行われると考えられる。
異常エッジ(abnormal edge): 行き先が不明なエッジ。最適化の妨げとなる傾向がある。例外処理によってこのようなエッジが生成される。
不可能エッジ(impossible edge): 全ブロックから最終的に出口ブロックに到達するよう意図的に加えられたエッジ。実際にそこを通る制御フローは存在しない。
支配ノード(dominator): ブロックMがブロックNを支配するとは、ブロックNに入っていくる全経路が必ず事前にブロックMを通っていることを意味する。入口ブロックは他の全ブロックから見て支配ノードである。
後支配ノード(postdominator): ブロックNから出口ブロックまでの全経路で必ずブロックMを通るとき、ブロックMを後支配ノードと呼ぶ。出口ブロックは他の全ブロックから見て後支配ノードである。
直接支配ノード(immediate dominator): ブロックMがブロックNの支配ノードで、かつその途中の経路にブロックNにとっての支配ノードが存在しない場合、ブロックMをブロックNの直接支配ノードという。あるブロックに支配ノードがある場合、直接支配ノードは唯一存在する。
直接後支配ノード(immediate postdominator): 直接支配ノードと同様の考え方。
支配木(dominator tree): 支配関係だけを示した補助的なデータ構造。ブロックMがブロックNの支配ノードである場合、ブロックMからブロックNへのエッジが描かれる。直接支配ノードは唯一なので、このグラフは木構造となる。根となるのは入口ブロックである。
後支配木(postdominator tree): 支配木と同様。出口ブロックが根となる。
ループヘッダ(loop header): ループ構造の入口となるブロック。ループを構成する後退エッジが指すことになる。ループ本体を構成する全ブロックの支配ノードとなる。
ループ前ヘッダ(loop pre-header): ブロックMがループヘッダとする。いくつかの最適化技法では、ブロックMを M_pre と M_loop の2つに分割する。Mの中身は M_loop に移行し、後退エッジはこれを指すようにする。一方、それ以外のエッジは M_pre を指すようにし、M_pre から M_loop へのエッジを追加する（M_pre は M_loop の直接支配ノードとなる）。M_pre は当初は何もしない（コードを含まない）が、ループ不変量コード移動などの最適化でコードが移される。この M_pre をループ前ヘッダという。M_loop はループヘッダである。

例

次のようなコード断片があるとする。

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0 goto 4
2: (B)   print t0 + " is odd."
3: (B)   goto 5
4: (C) print t0 + " is even."
5: (D) end program

括弧内のアルファベットがブロックを意味し、ここでは4つのブロックがある。A は入口ブロック、D は出口ブロックであり、4行目と5行目が分岐先である。これを制御フローグラフで表した場合、エッジは AからB、AからC、BからD、CからD の4本になる。

外部リンク

The Machine-SUIF Control Flow Graph Library
Compiler Collection Internals
Yousefi, Javad (2015). Masking wrong-successor Control Flow Errors employing data redundancy. IEEE. pp. 201–205. doi:10.1109/ICCKE.2015.7365827。
Paper "Infrastructure for Profile Driven Optimizations in GCC Compiler" by Zdeněk Dvořák, Jan Hubička, Pavel Nejedlý and Josef Zlomek

例

用語

例

関連項目

外部リンク

例