computer-science - 程序的控制流程图

Question

我现在正在学习一个编译器类，我们正处于必须构建一个 CFG 以实现优化的地步。我不知道的一件事是一个程序有多少个 CFG？我见过的每个示例似乎都是一个简单代码段的 CGF。因此，如果您有一个具有三个功能的程序。您是否为每个功能有一个单独的 CFG，或者整个程序是否有一个大的 CFG？

Answer 1

Per-function CFGs are connected by callsites. If one function calls another, e.g.:

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  }

then the control graph for baz will include an edge that goes to the graph for foo. Likewise, because foo will eventually returns to baz (and to wherever else it might've been called from), there will be an edge from the end of foo's graph back to the statement after the call to foo in baz. Here, that next statement is the call to bar on line 5. At that point, there's an edge from the bar callsite to bar's CFG, and lines from exit points in bar back to the end of baz.

Basically all you need to think about is "what code executes next". That tells you where the edges should go in your control graph. A function call transfers control until the function returns, which implies an edge from the callsite to the function CFG and back again.

Note that not all full-program CFGs are connected graphs. If there is unreachable code in the program you're analyzing, then that will be its own unconnected piece of the full CFG. e.g. if you took out the call to bar in the above example, then bar would have its own graph off to the side, while baz and foo would be connected by edges.

Answer 2

好吧，您可以为每个功能构造一个 CFG，然后 - 如果您想要做的事情 - 将它们组合成一个完整的功能。但是，整个程序 CFG 可能非常大，因此它们通常不能很好地用作示例。