如何构建具有无限循环的函数的 post-支配树？
How can I build the post-dominator tree of a function with an endless loop?
我的一个业余项目是 decompiler that turns native code into LLVM IR, simplifies it and outputs pseudo-C. An essential phase of the program's process is pattern-independent control flow structuring，它在程序中找到区域并将它们变成结构化的控制流语句（即不是 gotos）。
我不得不推出自己的代码来查找区域，因为 LLVM 的区域看起来并不完全符合论文的预期。然而，寻找区域需要你有一个 post-dominator 树，事实证明 LLVM 的 post-dominator 树构建算法不能为没有结束块的函数，例如 "end" 无限循环的函数。
这似乎是因为树构建算法需要一个起点。通常，起点是函数的 returning 块，因为它 post-dominates 每隔一个块；但是没有任何 in 函数会陷入无限循环，因为它们没有任何 return 或 unreachable 终止符。 （在这一点上，可能值得注意的是，LLVM 的区域代码也依赖于 post-dominator 树，并且对于无法为其构建的函数也是无用的。）
在我看来，即使这个算法失败了，一个函数不 return 的事实并不意味着你不能做出 post-dominator tree for it.1 事实上，如果那个无限循环有一个单一的后缘（这是我可以确保的），具有那个后缘的节点必然 post-dominates图中的每个其他节点，所以应该可以制作一个post-dominator树。
如果我能找到那个节点，我可能可以将它提供给 LLVM 的 post-dom 基础设施，并从中获得合理的 post-dominator 树它。不幸的是，我不是很有想象力，我能想到的识别关键节点的唯一直接方法是 "it's the one that post-dominates everything"，这肯定不会帮助我 bootstrap a post- dominator 树。
找到后边并不是特别难。正如 Doug Currie 所说，您可以使用简单的 DFS 来完成，事实上，我项目的另一部分 does exactly that。但是，对于具有无限循环和嵌套终止循环的函数，我不知道在没有 domination 信息的情况下如何区分内部后边缘和外部后边缘。 （如果有帮助，在流程的这个阶段，保证每个循环只有一个入口节点，最多有一个出口节点。）
那么如何构建一个没有任何 returning 基本块的函数的 post-dom 构造树？
1.我的编译器和图论背景完全是自学的。这可能不准确。
严格来说，当存在无限循环（不仅仅是无界循环——严格的无限循环，没有出口）时，不存在post支配者，对于循环中的每个节点，循环中的下一个节点将在它之后执行，因此循环中没有 "last" 个节点。
处理它的一种方法是进行正常的 post-dominator 查找，除了在从出口进行初始深度优先遍历之后，检查未访问的节点。如果有的话，出口无法从它们到达（没有从节点到出口的路径），因此您随机选择一个并将其添加为伪出口（就好像该节点包含到出口的条件分支，只是条件始终为假）并重新启动。这为您提供了 a post-支配树，但不一定是唯一的（因为您可能会随机选择不同的节点来添加出口分支），但通常不会没关系。
我的一个业余项目是 decompiler that turns native code into LLVM IR, simplifies it and outputs pseudo-C. An essential phase of the program's process is pattern-independent control flow structuring，它在程序中找到区域并将它们变成结构化的控制流语句（即不是 gotos）。
我不得不推出自己的代码来查找区域，因为 LLVM 的区域看起来并不完全符合论文的预期。然而，寻找区域需要你有一个 post-dominator 树，事实证明 LLVM 的 post-dominator 树构建算法不能为没有结束块的函数，例如 "end" 无限循环的函数。
这似乎是因为树构建算法需要一个起点。通常，起点是函数的 returning 块，因为它 post-dominates 每隔一个块；但是没有任何 in 函数会陷入无限循环，因为它们没有任何 return 或 unreachable 终止符。 （在这一点上，可能值得注意的是，LLVM 的区域代码也依赖于 post-dominator 树，并且对于无法为其构建的函数也是无用的。）
在我看来，即使这个算法失败了，一个函数不 return 的事实并不意味着你不能做出 post-dominator tree for it.1 事实上，如果那个无限循环有一个单一的后缘（这是我可以确保的），具有那个后缘的节点必然 post-dominates图中的每个其他节点，所以应该可以制作一个post-dominator树。
如果我能找到那个节点，我可能可以将它提供给 LLVM 的 post-dom 基础设施，并从中获得合理的 post-dominator 树它。不幸的是，我不是很有想象力，我能想到的识别关键节点的唯一直接方法是 "it's the one that post-dominates everything"，这肯定不会帮助我 bootstrap a post- dominator 树。
找到后边并不是特别难。正如 Doug Currie 所说，您可以使用简单的 DFS 来完成，事实上，我项目的另一部分 does exactly that。但是，对于具有无限循环和嵌套终止循环的函数，我不知道在没有 domination 信息的情况下如何区分内部后边缘和外部后边缘。 （如果有帮助，在流程的这个阶段，保证每个循环只有一个入口节点，最多有一个出口节点。）
那么如何构建一个没有任何 returning 基本块的函数的 post-dom 构造树？
1.我的编译器和图论背景完全是自学的。这可能不准确。
严格来说，当存在无限循环（不仅仅是无界循环——严格的无限循环，没有出口）时，不存在post支配者，对于循环中的每个节点，循环中的下一个节点将在它之后执行，因此循环中没有 "last" 个节点。
处理它的一种方法是进行正常的 post-dominator 查找，除了在从出口进行初始深度优先遍历之后，检查未访问的节点。如果有的话，出口无法从它们到达（没有从节点到出口的路径），因此您随机选择一个并将其添加为伪出口（就好像该节点包含到出口的条件分支，只是条件始终为假）并重新启动。这为您提供了 a post-支配树，但不一定是唯一的（因为您可能会随机选择不同的节点来添加出口分支），但通常不会没关系。