程序的控制流图

Question

我现在正在学习编译器课程，我们到了构建CFG的阶段，以实现优化。有一件事情我无法理解，就是一个程序有多少个CFG？我见过的每个例子似乎都只是一个简单代码段的CGF。因此，如果你有一个包含三个函数的程序，那么你是为每个函数单独创建一个CFG，还是创建一个大的CFG来覆盖整个程序呢？

- Ian Burris

---

这个问题是否适合在程序员版块讨论？ - user7116

Answer 1

函数级别的控制流图通过调用点相互连接。如果一个函数调用了另一个函数，例如:

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将通过边缘相连。

- Todd Gamblin

---

嗯...我想让我困惑的一件事是，在课堂上教授说基本块应该只有一个入边和最多两个出边（一个指向下一个块，第二个指向其他地方的标签，如果有分支）。因此，如果我连接不同的图形，则函数的第一个块可能具有多个入边，而最后一个块可能具有多于两个的出边。你有什么想法吗？你会说这个“1入2出”的说法是错误的吗？ - Ian Burris

基本块通常是这样定义的，它们只有一个入口点，但可以有多个指向入口点的边缘。 你只是不能跳到块的中间，因为这不是BB的定义方式。为了方便分析，您希望设置块，以便如果执行块中的任何语句，则会执行块中的所有语句。 - Todd Gamblin

只要跳转到第一条语句，您仍然可以将多个边缘进入块中。这适用于函数，可以从多个位置调用它们，以及循环条目，其中该块可以从循环之前的代码或从循环末尾的分支进入（如果循环尚未完成）。通常称从循环末尾回到开头的边缘为后向边。 - Todd Gamblin

至于出度，基本块通常只有两个边。如果你有一个三路分支指令，我想你可能会有更多的出边，但是我想不出一种架构能够做到这一点。也许你的教授现在只是想保持简单。 - Todd Gamblin

在网上很容易找到控制流图的例子——只需谷歌一下即可。请注意这里入边的数量（>1）：http://www.cs.arizona.edu/~collberg/Teaching/453/2009/Handouts/Handout-15.pdf - Todd Gamblin

每个函数图通常不会包括到被调用函数的控制流图中的边缘。这相当于内联函数。那么如何表示对已编译库函数的调用，递归函数又该如何处理呢？函数调用通常由一个特殊节点表示，其中包含函数名称和调用时使用的参数。 - Björn Lindqvist

Answer 2

你可以为每个函数构建一个CFG，然后根据需要将它们组合成完整的CFG。整个程序的CFG可能非常大，因此通常不适合作为示例。

- 500 - Internal Server Error