zne*_*eak 14 compiler-construction algorithm graph llvm decompiler
我的一个项目是反编译器,它将本机代码转换为LLVM IR,简化它并输出伪C.程序过程的一个重要阶段是与模式无关的控制流结构,它在程序中查找区域并将其转换为结构化控制流语句(即不是结果).
我不得不推出自己的代码来寻找区域,因为LLVM的区域并不完全符合论文的预期.但是,找到区域需要你有一个后支配树,并且事实证明LLVM的后支配树构建算法不能为没有结束块的函数创建一个,就像用无限循环"结束"的函数一样.
这似乎是因为树构建算法需要一个起点.通常,起点是函数的返回块,因为它后控制每隔一个块; 但是没有任何函数可以旋转到无限循环中,因为它们没有任何return或unreachable终结符.(此时,值得注意的是LLVM的区域代码也依赖于后支配树,对于无法构建的函数也没用.)
在我看来,即使这个算法失败,函数不返回的事实并不意味着你不能为它做一个后支配树.1实际上,如果无限循环具有单个后沿(这是我可以确保的),那么具有该后沿的节点必然会支配图中的每个其他节点,因此应该可以发布帖子 - 主动树.
如果我能找到那个节点,我可以将它提供给LLVM的后dom基础设施,并从中获得一个合理的后支配树.不幸的是,我不是很富有想象力,而且我能想到的唯一直截了当的方法就是确定那个关键节点是"它是支配所有东西的那个",这当然不会帮助我引导后支配树.
寻找后缘并不是特别困难.正如Doug Currie所说,你可以用一个简单的DFS来实现,事实上,我的项目的另一部分就是这样做的.但是,在具有无限循环和嵌套终止循环的函数的情况下,我不知道如何在没有支配信息的情况下从外后边缘告诉内后边缘.(如果它可以提供帮助,在此过程的这个阶段,每个循环都保证有一个入口节点和最多一个出口节点.)
那么如何构建一个没有任何返回基本块的函数的后支配树？
我的编译器和图论背景完全是自学成才.这可能不准确.
严格来说,当存在无限循环(不仅仅是无界循环 - 严格无限循环而没有退出)时,没有后置控制器,对于循环中的每个节点,循环中的下一个节点将在其后执行,所以循环没有"最后"节点.
处理它的一种方法是执行正常的后支配者查找,除非在从出口执行初始深度优先遍历之后,检查未访问的节点.如果有,则从它们无法访问出口(没有从节点到出口的路径),因此您随机选择一个并将其添加为psuedo-exit(就好像该节点包含一个条件分支到出口,只是条件总是假的)并重新启动.这为您提供了一个后统治者树,但不一定是唯一的(因为您可以随机选择不同的节点来添加退出分支),但通常这并不重要.