问题标签 [control-flow-graph]

想象一下，我有一种基于堆栈的玩具语言，它带有 Push、Pop、Jump 和 If 操作。

我有一个程序，它的输入是玩具语言。例如我得到序列

在这种情况下，最大堆栈将为 2。更复杂的示例将使用分支。

在这种情况下，最大堆栈将为 3。但是，如本例所示，通过从上到下遍历是不可能获得最大堆栈的，因为它实际上会导致堆栈下溢错误。

CFG 可以帮助您构建图表并遍历您拥有的基本块的每条可能路径。然而，由于路径的数量对于 n 个顶点可以快速增长，因此您得到 (n-1)！可能的路径。

我目前的方法是尽可能简化图表并减少可能的路径。这行得通，但我认为它很难看。有没有更好（阅读：更快）的方法来解决这个问题？如果算法产生的堆栈深度不是最优的，我很好。如果正确的堆栈大小是 m，那么我唯一的限制是结果 n 是 n >= m。是否有可用的贪心算法可以在这里产生良好的结果？

更新：我知道循环和所有控制流合并具有相同堆栈深度的不变量。我想我写下一个简单的玩具般的语言来说明这个问题。基本上我有一个确定性的基于堆栈的语言（JVM 字节码），所以每个操作都有一个已知的堆栈增量。

请注意，对于这个问题，我确实有一个可行的解决方案，可以产生良好的结果（简化的 cfg），但我正在寻找一种更好/更快的方法。

我正在寻找一种工具来绘制C# 代码的控制流图..

类似于AVRORA但用于 C#

有任何想法吗？

我正在尝试构建通过调用 objdump -d 返回的装配结果的控制流图。目前我想出的最好的方法是将结果的每一行放入一个链表中，并将每一行的内存地址、操作码和操作数分开。我依靠 objdump 结果的常规性质将它们分开（内存地址是代表每一行的字符串中的字符 2 到字符 7）。

完成此操作后，我将启动实际的 CFG 指令。CFG 中的每个节点都拥有一个起始和结束内存地址、一个指向前一个基本块的指针以及指向任何子基本块的指针。然后，我将检查 objdump 结果并将操作码与 x86_64 中所有控制流操作码的数组进行比较。如果操作码是控制流，我将地址记录为基本块的结尾，并根据操作码添加两个子指针（条件操作码）或一个（调用或返回）。

我正在用 C 语言实现它，它似乎可以工作，但感觉非常脆弱。有没有人有任何建议，或者我没有考虑到的任何事情？

感谢您抽时间阅读！

编辑：

这个想法是使用它来比较 DynamoRIO 生成的系统调用的堆栈跟踪与目标二进制文件的预期 CFG，我希望像这样构建它会促进这一点。我没有重新使用可用的东西，因为 A) 我并没有真正考虑过它和 B) 我需要将图表转换为可用的数据结构，以便我可以进行路径比较。我将查看您所排的页面上的一些实用程序，感谢您为我指明了正确的方向。感谢您的评论，我真的很感激！

我已经开始使用 LLVM，我很想知道是否有一种编程方式可以从 LLVM/clang 中提取控制流图和/或基本块，以便对它们进行一些分析。有没有办法挂钩工具链并提取这些信息而不是直接编译？如果没有，有什么替代方案？

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

是否有任何工具、库或框架来获取 C 程序的控制流图，并找到程序可能采取的最坏路径？

当我阅读与控制流图相关的其他问题时，我遇到了一些可以生成控制流图的工具。有没有办法使用它们来找到最糟糕的路径？

我正在尝试从 gcc 生成的汇编代码中提取控制流图。我已经设法使用参数 -fdump-rtl-* 和 -dv 将几个 IR（rtl 阶段）的 CFG 转储到 .vcg 文件中。除了最终的汇编代码之外，有没有办法做同样的事情？我想要一个通用的、与目标无关且易于解析的表示（如 vcg 表示）。我的源代码是 C 语言（以防它扮演任何重要角色）。

最好的问候，米卡利斯。

我需要为项目中的 Java 代码操作控制流图。什么可能是一个很好的 Java 库，可以在 Java 中生成控制流图。到目前为止，我已经找到了几个 Eclipse 插件（严重依赖于 Eclipse API）和独立工具（不能嵌入到我的代码中）。

我想将 CFG 渲染为高级代码。通常这很容易；遍历树，依次渲染每个基本块，用 goto 将它们粘合在一起。

不幸的是，这些天 goto 已经过时了，大多数现代语言都不支持它们。所以我需要一些方法来将我的基本块粘合在一起，只使用语言中存在的那些控制流语句：for, while, do... while, if,break和continue. （我不愿意考虑使用变量构建状态机。）

看起来虽然有算法可以做到这一点，但它们并非在所有情况下都有效。也就是说，仅使用上述有限的一组控制流结构，就可以构建一个不能被扁平化为结构化代码的 CFG。

这对我来说似乎很直观，但我无法证明它（我发现的算法的文档没有更详细）。而且我还没有找到一个不能像这样展平的CFG的例子。

我想明确地知道这是否可能。

选项（a）：有没有人有一个如上所述不能展平的 CFG 示例？（这会告诉我这是不可能的。）

选项 (b)：是否有人证明 CFG可以如上所述被展平？（这会告诉我这是可能的。）做它的算法也是非常可取的，因为我必须让它工作......

我正在尝试分析 Java 代码结构。

所以，我使用 ANTLRv3 和 java 语法代码生成了一个 Java 解析器和词法分析器......

但我不知道如何使用生成的解析器和词法分析器生成上下文流图。

我试图通过教程页面学习如何做到这一点，但是教程页面已经消失了。

你能给我一个如何做到这一点的方法吗？或教程页面？

谢谢你。