algorithm - 确定最大堆栈深度

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 可以助您一臂之力，您可以构建图表并遍历您拥有的基本 block 的每条可能路径。然而，由于 n 个顶点的路径数量可以快速增长，因此您得到 (n-1)!可能的路径。

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

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

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

Answer 1

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

关于您的路径论证:请注意，跳跃允许循环，因此，如果不进行进一步分析，循环可能意味着未终止和堆栈溢出(即堆栈大小在每次循环执行后增加)。 [如果有环，n个节点仍然意味着无限多条路径]

您可以执行某种形式的 abstract interpretation 而不是实际执行代码.

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

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