确定最大堆叠深度

Question

想象我有一个基于堆栈的玩具语言，带有 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。是否有可用的贪心算法可以在这里产生好的结果？

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

这也是有界堆栈深度的要求。如果不强制执行，代码中的循环将会增加。

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

编辑：

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

评估当前基本块点的传出边缘是否仍需要评估的基本块不应该与性能相关。即使在最坏的情况下，每条指令都是

IF

，也只有 2*N 条边需要评估。