我的辅助项目之一是反编译器,它将本地代码转换为LLVM IR,对其进行简化并输出伪C。程序过程的基本阶段是与模式无关的控制流结构化,该结构在程序中找到区域并将其转换为结构化的控制流语句(即,不是gotos)。
我必须推出自己的代码来查找区域,因为LLVM的区域看起来与论文期望的并不完全相同。但是,要找到区域,您需要有一棵后支配树,并且事实证明,LLVM的后支配树构建算法无法为没有端块的函数(例如以无限循环“结束”的函数)创建树。
这似乎是因为树构建算法需要一个起点。通常,起点是函数的返回块,因为它在其他每个块中都占主导地位。但是没有函数会陷入无限循环,因为它们没有任何return
或unreachable
终止符。(在这一点上,值得注意的是,LLVM的区域代码也依赖于后支配树,并且对于无法为其构建的功能也没有用。)
在我看来,即使该算法失败,函数不返回的事实也不意味着您无法为其创建后支配树。1实际上,如果该无限循环具有单个后边缘(我可以确保这一点),则具有后边缘的节点必然在图形中的每个其他节点上占主导地位,因此应该有可能进行后期处理-主导树。
如果可以找到该节点,则可以将其提供给LLVM的后域基础架构,并从中获得合理的后主导树。不幸的是,我不是很有想象力的,而且我想到该关键节点的唯一直截了当的方法是“这是后支配一切的那个”,这当然不会帮助我引导后支配树。
查找后边缘并不特别困难。正如Doug Currie所说的,您可以使用简单的DFS来实现,实际上,我项目的另一部分正是这样做的。但是,对于具有无限循环和嵌套终止循环的函数,我不知道如何在没有控制信息的情况下从外部后边缘分辨出内部后边缘。(如果有帮助,在此过程的此阶段,可以确保每个循环都具有一个入口节点,最多有一个出口节点。)
那么,如何构建没有返回基本块的函数的后支配树?
1.我的编译器和图论背景完全是自学成才的。这可能不正确。
严格来说,当存在一个无限循环(不仅仅是一个无穷循环-一个没有出口的严格无限循环)时,就没有后支配器,因为循环中的每个节点都将在循环之后执行下一个节点,因此循环没有“最后”节点。
处理它的一种方法是进行常规的后支配地位查找,除了从出口进行初始的深度优先遍历之后,您要检查未访问的节点。如果存在,则出口无法到达它们(从节点到出口没有路径),因此您随机选择一个,并将其作为伪出口添加(就像节点包含到出口的条件分支一样,只是条件始终为假),然后重新启动。这为您提供了后支配树,但不一定是唯一的树(因为您可能会随机选择不同的节点来添加出口分支),但是通常并不重要。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句