如何构建具有无限循环的函数的后支配树?

ne

我的辅助项目之一是反编译器,它将本地代码转换为LLVM IR,对其进行简化并输出伪C。程序过程的基本阶段是与模式无关的控制流结构化,该结构在程序中找到区域并将其转换为结构化的控制流语句(即,不是gotos)。

我必须推出自己的代码来查找区域,因为LLVM的区域看起来与论文期望的并不完全相同。但是,要找到区域,您需要有一棵后支配树,并且事实证明,LLVM的后支配树构建算法无法为没有端块的函数(例如以无限循环“结束”的函数)创建树。

这似乎是因为树构建算法需要一个起点。通常,起点是函数的返回块,因为它在其他每个块中都占主导地位。但是没有函数会陷入无限循环,因为它们没有任何returnunreachable终止符。(在这一点上,值得注意的是,LLVM的区域代码也依赖于后支配树,并且对于无法为其构建的功能也没有用。)

在我看来,即使该算法失败,函数不返回的事实也不意味着您无法为其创建后支配树。1实际上,如果该无限循环具有单个后边缘(我可以确保这一点),则具有后边缘的节点必然在图形中的每个其他节点上占主导地位,因此应该有可能进行后期处理-主导树。

如果可以找到该节点,则可以将其提供给LLVM的后域基础架构,并从中获得合理的后主导树。不幸的是,我不是很有想象力的,而且我想到该关键节点的唯一直截了当的方法是“这是后支配一切的那个”,这当然不会帮助我引导后支配树。

查找后边缘并不特别困难。正如Doug Currie所说的,您可以使用简单的DFS来实现,实际上,我项目的另一部分正是这样做的但是,对于具有无限循环和嵌套终止循环的函数,我不知道如何在没有控制信息的情况下从外部后边缘分辨出内部后边缘。(如果有帮助,在此过程的此阶段,可以确保每个循环都具有一个入口节点,最多有一个出口节点。)

那么,如何构建没有返回基本块的函数的后支配树?

1.我的编译器和图论背景完全是自学成才的。这可能不正确。

克里斯·多德

严格来说,当存在一个无限循环(不仅仅是一个无穷循环-一个没有出口的严格无限循环)时,就没有后支配器,因为循环中的每个节点都将在循环之后执行下一个节点,因此循环没有“最后”节点。

处理它的一种方法是进行常规的后支配地位查找,除了从出口进行初始的深度优先遍历之后,您要检查未访问的节点。如果存在,则出口无法到达它们(从节点到出口没有路径),因此您随机选择一个,并将其作为伪出口添加(就像节点包含到出口的条件分支一样,只是条件始终为假),然后重新启动。这为您提供后支配树,但不一定是唯一的树(因为您可能会随机选择不同的节点来添加出口分支),但是通常并不重要。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

如何在finally块中停止具有无限循环的线程

JavaScript - 具有无限循环的动态启动/停止功能

具有无限循环的守护程序线程不终止

WP Query Foreach具有无限循环

具有无限 While 循环的 Python 多处理池

具有无限多个(未命名)参数的函数 - 如何正确访问这些参数?

如果我使用“ while”,则具有无限循环的PHP函数,或者如果使用“ IF”而不是“ while”,则任务无法完全实现

如何启动具有无限内存的JVM?

HashTable具有无限深度。为什么?如何避免?

具有无限参数的Java方法

具有无限参数的 UDF

具有无限/动态成员的枚举

具有无限参数的类 scala

具有无限循环的线程会导致CPU过多吗

突破具有无限循环的第三方goroutine

具有无限while循环的异步任务之间的C#同步?

具有无限可选参数和输入变量选择的C ++函数

是否可以创建具有无限无限滚动的网页?

如何检查没有无限循环的JSON数据是否为null?

如何在一个元素具有无限宽度的行中排列元素?

如何通过Javascript中的任意属性制作具有无限深度的对象?

考虑到其父级具有无限的高度,如何获取视图高度?

如何在Ruby on Rails中使用回形针制作具有无限图像的模型?

具有无限滚动的ListView:如何防止刷新可见行?

如何使用猫鼬填充具有无限嵌套级别的文档

如何在 express.js 中处理具有无限可能性的路由?

如何使用 sympy 找到具有无限解的方程组的特定解?

如何在函数中设置参数,使其成为可选参数并拥有无限数量的参数

如何在函数中转换树后返回具有更新值的原始根节点