Question

通用的反编译机器(udm) 由两个阶段组成；数据流分析阶段把低级 Icode 转换成一个最理想的高级 Icode 表示法，和控制流分析阶段遍历每个子程序的图以确定条件结构和循环的范围；这些边界稍后被代码生成器使用。图 9-11 显示 udm() 子过程的代码。

9.5.1 数据流分析

数据流分析的第一部分是条件码的去除。条件码被分成两组：可能由编译器产生的条件码 (HLCC 组)，和可能手工汇编制作的的条件码 (NHLCC 组)。在 Intel i80286 [Int86](溢出、方向、中断准许、陷阱、符号、零、辅助进位、对等和进位) 的 9 个条件码中，只有 4 个标志可能是高级的；它们是进位、方向、零和符号。这些标志被用指令修改，这些指令可能是高级指令 (即，没有被打上非高级语言的标志)，因此对这一组做条件码去除的分析。在可能的高级指令中，30 个指令定义 HLCC 组的标志；一个指令定义 1 个标志到 3 个标志不等，而且 25 个指令使用标志；通常，每个指令使用一个或两个标志。dcc 实现了死条件码清除和条件码传播，详见第 5 章第 5.4.2 节和第 5.4.3 节的描述。这些最优化去掉所有对条件码的引用并且创建有一布尔条件表达式与之关联的 jcond 指令。这个分析与所有其它低级 Icodes 到高级 Icodes 的、用寄存器表达的最初映射互相重叠。最初的 Icodes 映射见附录 D 说明。

void udm (CALL_GRAPH *callGraph) { derSeq *derivedG; /* Data flow analysis - optimizations on Icode */ dataFlow (callGraph); /* Control flow analysis -- structure the graphs */ /* Build derived sequences for each subroutine */ buildDerivedSeq (callGraph, &derivedG); if (option.VeryVerbose) /* display derived sequence for each subroutine */ displayDerivedSeq (derivedG); /* Graph structuring */ structure (callGraph, derivedG); }

图 9-11: 通用的反编译机器子过程

这个分析的第二部分是关于该图中的基本块和 Icode 指令操作数的统计信息生成。为每个子程序进行一个定义-使用和使用-定义分析(definition-use and use-definition analysis)；为每个指令建立与之关联的链(chain)。在建立这些链的过程当中，进行死寄存器清除，详见第 5 章第 5.4.1 节的描述。下一步，为每个子程序做一个子过程内的活寄存器分析，以确定被该子程序使用的任何寄存器参数。这个分析在第 5 章第 5.4.4 节中描述。最后，接着做一个子过程间的活寄存器分析，以确定被函数返回的寄存器；分析在第 5 章第 5.4.5 节中描述。

死寄存器清除确定 DIV 机器指令的目的——即，这个指令是用来求操作数的商和余数这两个东西。下面的中间代码

1	asgn tmp, dx:ax	; ud(tmp) = {2,3}
2	asgn ax, tmp / bx	; ud(ax) = {}
3	asgn dx, tmp % bx	; ud(dx) = {4}
4	asgn [bp-2], dx	/* no further use of ax before redefinition */

确定寄存器 ax 在重新定义之前不被使用，因为在指令 2 中它的使用-定义链是空的。因为这个定义是死的，所以把该指令去掉——两个操作数的除法运算，并得到以下代码：

1	asgn tmp, dx:ax	; ud(tmp) = {2,3}
3	asgn dx, tmp % bx	; ud(dx) = {4}
4	asgn [bp-2], dx

所有那些在其使用-定义链中有指令 2 的指令需要被更新，以反映该寄存器不再被使用的这个事实，因为指令 2 是被用来定义一个死的寄存器；因此，在这个例子中，指令 1 的 ud() 链被更新，得到最后的代码：

1	asgn tmp, dx:ax	; ud(tmp) = {3}
3	asgn dx, tmp % bx	; ud(dx) = {4}
4	asgn [bp-2], dx

该分析的第三部分和最后部分是通过应用寄存器的使用-定义链来进行扩展的寄存器拷贝传播，详见第 5 章第 5.4.10 节的描述。这个分析去掉多余的寄存器引用，确定高级表达式，把实际参数放在子程序的列表上，而且跨子程序调用传播参数类型。在该分析中始终使用一个临时的表达式栈来清除中间伪高级指令 push 和 pop。

在前面的例子中，通过向前代入，确定了最初的 DIV 指令只是用来计算在两个操作数之间的模 (在这个例子中，这两个操作数被放在寄存器 dx:ax 和 bx)：

4	asgn [bp-2], dx:ax % bx

9.5.2 控制流分析

控制流分析程序有两个部分：第一部分为调用图中的每个子程序构造一个派生图序列而且计算区间。这个序列被结构化算法用来确定循环的边界和这些循环的嵌套层次。一旦为这个子程序建立派生图序列以后，就测试该图的可归约性；如果极限第 n 个顺序图不是一个平凡图，那么该子程序就是不可归约的。

该分析第二部分是程序的控制流向图的结构化。结构化算法确定循环和条件结构 (二路和 n 路结构) 的边界；这些边界稍后在代码生成期间被使用。循环被使用区间来结构化，而且它们的嵌套层次是根据它们在派生图序列中的建立顺序来确定，详见第 6 章第 6.6.1 节的描述。通过这个算法确定先测试循环、后测试循环和无穷循环。条件结构的结构化是依靠深度优先搜索树的一个反向遍历；这样，被嵌套的条件结构首先被发现。结构化二路条件和 n 路条件的方法在第 6 章第 6.6.2 节和第 6.6.3 节描述。这个方法考虑到组合的布尔条件，而且通过把两个或多个结点的布尔条件信息储存在这一个结点而从该图中移除一些结点。