如何构建一个带有无限循环的函数的后支配树？

Question

如何构建一个带有无限循环的函数的后支配树？

algorithmgraphcompiler-constructionllvmdecompiler

18

我的一个副业项目是一个反编译器，它将原生代码转换为LLVM IR，简化并输出伪C代码。该程序过程的一个关键阶段是无模式控制流结构化, 它可以找到程序中的区域，并将它们转换为结构化的控制流语句（即没有goto语句）。

我不得不自己编写代码来查找区域，因为LLVM的区域不完全符合论文的期望。然而，查找区域需要你拥有后支配树，而LLVM的后支配树构建算法不能为没有结束块的函数（如以无限循环“结束”的函数）创建一个后支配树。

这似乎是因为树构建算法需要一个起点。通常，起点是函数的返回块，因为它支配着每个其他块；但在进入无限循环的函数中没有任何return或unreachable终止器，所以它们没有起点。(值得注意的是，LLVM的区域代码也依赖于后支配树，对于无法构建的函数也是无用的。)

我认为，即使此算法失败，函数不返回并不意味着您不能为其创建后支配树。¹实际上，如果该无限循环具有单个反向边缘(这是我可以确保的)，则具有该反向边缘的节点必然支配图中的每个其他节点，因此应该可以创建后支配树。

如果我能找到那个节点，我可能会将其提供给LLVM的后置基础设施，并从中获得合理的后支配树。不幸的是，我不太有想象力，我能想到的唯一直接的方法是识别那个关键节点的方式是“它支配着一切”，这肯定不会帮助我引导后支配树。

找回边并不是特别困难。正如Doug Currie所说，您可以使用简单的DFS来完成，事实上，我的项目正是这样做的。然而，在具有无限循环和嵌套终止循环的函数中，如果没有支配信息，我不知道如何区分内部反向边和外部反向边。（如果有帮助的话，在此过程的这个阶段，保证每个循环都有一个入口节点和至多一个出口节点。）

那么，如果一个函数没有任何返回基本块，我该如何构建后支配树呢？

注：我的编译器和图论背景完全是自学的。这可能不准确。

- zneak

作为一种hack，为了使您的分析成功，您可以在循环中插入一个假的结束条件，它实际上永远不会成为真，例如在伪代码中：if (5 == 7) break;？ - 500 - Internal Server Error

@500-InternalServerError，我还需要找到确切放置它的位置，而那将是在具有反向边的节点上，而我不知道如何找到这个节点。 - zneak

你可以使用深度优先搜索算法找到反向边；例如，参见http://www.cs.yale.edu/homes/aspnes/pinewiki/DepthFirstSearch.html。 - Doug Currie

@DougCurrie，一个包含无限循环的函数不一定只有一个循环。如果这个无限循环中有一个内部（终止）循环，我不知道如何确定哪个回边属于无限循环。我应该在问题中加入这一点。 - zneak

@zneak，请查看G RAMALINGAM的“几乎线性时间识别循环”文章，链接为http://pages.cs.wisc.edu/~ramali/Papers/toplas99.ps，该文章描述了用于查找循环和循环嵌套的近线性时间算法。 - Doug Currie

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris Dodd · Accepted Answer

严格来说，当存在无限循环（不仅是无界循环——严格的无限循环没有出口）时，就不存在后支配者，因为对于循环中的每个节点，下一个节点将在其之后执行，所以没有“最后”一个节点与该循环相关联。

一种处理方法是进行正常的后支配者查找，除了从退出点进行初始深度优先遍历后，检查未访问的节点。如果有任何未访问的节点，则从它们到退出点没有路径可达，因此您可以随机选择一个并将其添加为伪退出点（就像节点包含条件分支到退出点一样，只是条件始终为假），然后重新开始。这会给您提供一个后支配者树，但不一定是唯一的（因为您可能随机选择不同的节点添加退出分支），但通常这并不重要。