程序的控制流程图

发布于 2024-10-31 08:28:23 字数 143 浏览 7 评论 0 原文

我现在正在学习编译器课程，我们必须构建 CFG 才能实现优化。我不明白的一件事是一个程序有多少个 CFG？我见过的每个例子似乎都是一个简单代码段的 CGF。因此，如果您有一个具有三个功能的程序。您是否为每个函数都有一个单独的 CFG，或者是否为整个程序有一个大的 CFG？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

你的呼吸 2024-11-07 08:28:23

每个功能的 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 （以及可能从其调用的其他任何地方），因此从 foo 的末尾将有一条边 的图表返回到在 baz 中调用 foo 后的语句。在这里，下一个语句是第 5 行对 bar 的调用。此时，从 bar 调用站点到 bar 的CFG，以及从 bar 中的出口点到 baz 末尾的线。

基本上您需要考虑的是“接下来执行什么代码”。这告诉您边缘应该在控制图中的位置。函数调用会传输控制权，直到函数返回，这意味着从调用点到函数 CFG 并再次返回的边缘。

请注意，并非所有完整程序 CFG 都是连通图。如果您正在分析的程序中有无法访问的代码，那么这将是它自己的未连接完整 CFG 的一部分。例如，如果您在上面的示例中取出对 bar 的调用，那么 bar 将在侧面拥有自己的图形，而 baz 和foo 将通过边连接。

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.