代码之家 › 专栏 › 技术社区 › Joa Ebert Emran

确定最大堆叠深度

control-flow-graph control-flow compiler-theory stack algorithm

Joa Ebert Emran · 技术社区 · 14 年前

想象一下,我有一个基于堆栈的玩具语言,它伴随着操作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),但是我正在寻找更好/更快的方法。

2 回复 | 直到 11 年前

ebo 14 年前

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

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

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

您应该考虑的另一件事是使所有操作码的堆栈效果具有确定性。非确定性操作码的一个例子是:如果topofstack==0,则弹出。

编辑:

如果您确实有一组确定的操作码和堆栈深度不变,那么就不需要访问程序的每个可能路径。通过cfg进行一次fs/bfs就足以确定最大的堆栈深度。这可以在线性时间内完成(取决于指令的数量),但不能更快。

评估当前基本块点的传出边缘是否仍需要评估的基本块不应与性能相关。即使在最坏的情况下,每个指令都是 IF 只有2*n条边可供评估。

Frank 14 年前

考虑到您的语言似乎没有任何用户输入,所有程序都将以相同的方式一直计算。因此,可以在执行期间执行程序并跟踪最大堆栈大小。可能不是你想要的。

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

您可能能够执行某种形式的 abstract interpretation 。

关于来自ivlad的评论:简单地计算push是错误的,因为存在可能的循环。

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