computer-science - プログラムの制御フローグラフ

Question

私は現在コンパイラクラスを受講しており、最適化を実装するためにCFGを構築する必要があります。私が理解できないことの1つは、プログラムにCFGがいくつあるかということです。私が今まで見たすべての例は、単純なコードセグメントのCGFのようです。したがって、3つの機能を持つプログラムがある場合。機能ごとに個別のCFGがありますか、それともプログラム全体に1つの大きなCFGがありますか？

Answer 1

機能ごとのCFGは、コールサイトによって接続されます。ある関数が別の関数を呼び出す場合、例：

0  void foo() { /* do stuff */ }
1  void bar() { /* do stuff */ }
2
3  void baz() {
4     foo();  // Callsite for foo. Control transfers to foo, then foo returns here.
5     bar();  // Callsite for bar. Control transfers to bar, then bar returns here.
6  }

その場合、の制御グラフにbazは、のグラフに移動するエッジが含まれfooます。同様に、fooは最終的にに戻るので（そして、それが呼び出された可能性のある他の場所に）、の呼び出しの後に、グラフbazの終わりからステートメントに戻るエッジがあります。ここで、その次のステートメントは5行目の呼び出しです。その時点で、呼び出しサイトからのCFGへのエッジがあり、出口点からの行はの終わりに戻ります。foofoobazbarbarbarbarbaz

基本的に、考える必要があるのは「次に実行されるコード」だけです。これにより、コントロールグラフのどこにエッジを配置するかがわかります。関数呼び出しは、関数が戻るまで制御を転送します。これは、呼び出しサイトから関数CFGにエッジがあり、また戻ることを意味します。

すべてのフルプログラムCFGが接続されたグラフであるとは限らないことに注意してください。分析しているプログラムに到達不能コードがある場合、それは完全なCFGのそれ自体の接続されていない部分になります。barたとえば、上記の例でへの呼び出しを取得した場合、は、エッジによって接続されている間、bar横に独自のグラフがあります。bazfoo

Answer 2

さて、関数ごとにCFGを作成してから、必要に応じてそれらを組み合わせて完全な関数にすることができます。ただし、プログラム全体のCFGはかなり大きくなる可能性があるため、通常、例としてはうまく機能しません。