制御フローグラフ

制御フローグラフ（せいぎょフローグラフ、英: Control Flow Graph, CFG）は、プログラムを実行したときに通る可能性のある全経路をグラフで表したものである。この場合、ノードは基本ブロック（すなわち、分岐を全く含まない逐次的コード列であって、途中に分岐先もない）を表し、ノードとノードをつなぐ有向エッジは、あるブロックから別ブロックへのジャンプを意味する。一般に、グラフ全体の入口となる入口ブロックと、出口となる出口ブロックがある。 CFGはコンパイラ最適化や静的コード解析ツールでよく使われる。 最適化において利用されるグラフの属性として、到達可能性(reachability)がある。あるブロックまたは部分グラフが、入口ブロックを含む部分グラフと連結していない場合、そのブロックは決して実行されることはなく、いわゆる到達不能コードであって、容易に削除可能である。出口ブロックが入口ブロックから到達不能な場合、無限ループとなっている（あらゆる無限ループを検出できるわけではない。停止性問題を参照のこと）。プログラマが明示的に到達できないコードや無限ループを書かなくても、そのような状況になることはある。例えば、定数伝播や定数畳み込みといった最適化を行った後にを行うと、元々は別々だった基本ブロックが1つにまとめられることがあり、エッジがCFGから除去され、グラフの一部が連結されなくなることがある。