1

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

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

Push 1
Push 1
Pop
Pop

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

Push 1
Push true
If   .success
Pop
Jump .continue
.success:
Push 1
Push 1
Pop
Pop
Pop
.continue:

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

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

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

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

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

4

2 回答 2

2

鉴于您的语言似乎没有任何用户输入，所有程序将始终以相同的方式简单地计算。因此，您可以执行程序并在执行期间跟踪最大堆栈大小。可能不是你想要的。

至于您的路径论证：请注意，跳转允许循环，因此，如果没有进一步分析，循环可能意味着非终止和堆栈溢出（即，每次循环执行后堆栈大小都会增加）。[如果有循环，n个节点仍然意味着无限多的路径]

您可以进行某种形式的抽象解释，而不是实际执行代码。

关于 IVlad 的评论：由于可能存在循环，简单地计算推送是错误的。

我不确定你的 if 语句的语义是什么，所以这也很有用：假设 if 语句的标签只能是前向标签（即，你永远不能跳回你的代码）。在这种情况下，您的路径计数论点又恢复了活力。实际上，生成的 CFG 将是一棵树（如果您不复制代码，则为 DAG）。在这种情况下，您可以通过自下而上计算推送次数来进行近似计数，然后在 if 语句的情况下获取两个分支的最大推送次数。它仍然不是最佳的正确结果，但比简单的推送语句计数产生更好的近似值。

于 2010-05-03T10:15:01.530 回答
1

您通常希望堆栈深度在跳转和循环上保持不变。

这意味着对于每个节点，每个传入边都应该具有相同的堆栈深度。这显着简化了 CFG 的遍历，因为后边不能再改变已计算指令的堆栈深度。

这也是有限堆栈深度的要求。如果不强制执行，您的代码中将有越来越多的循环。

您应该考虑的另一件事是使所有操作码的堆栈效应具有确定性。非确定性操作码的一个示例是：POP IF TopOfStack == 0。

编辑：

如果您确实有一组确定的操作码和堆栈深度不变，则无需访问程序的每个可能路径。通过 CFG 做一个 DFS/BFS 来确定最大堆栈深度就足够了。这可以在线性时间内完成（取决于指令的数量），但不会更快。

评估是否仍需要评估当前基本块点的出边的基本块与性能无关。即使在最坏的情况下，每条指令都是一个IF，也只有 2*N 个边需要评估。

于 2010-05-03T10:19:02.603 回答