Question

在语法分析已装入内存的程序时，前端为该程序构造一个调用图。每个子程序的中间代码和控制流向图隶属于调用图中的子程序结点；因此，语法分析、中间代码生成和流向图的构成是在扫描该程序映像同一趟中完成。数据信息被储存在全局的和局部的符号表中。如果使用者要求反汇编，则一个汇编器文件被输出写入一个带扩展名.a1 的文件；如果使用者要求交互式界面，则显示一个交互式窗口，而且使用者能够单步浏览指令、跟随程序。最后，进行语义分析，接着显示位映像图(bitmap)(如果使用者要求)。图 9-4 显示 FrontEnd() 子过程的代码。

9.3.1 语法分析器

语法分析器确定从装载器提供的入口点开始的代码是不是跟它储存的编译器签名之一等同，如果相同，就可以确定该程序的 main 并且把它作为这个分析的入口点。只要识别出一个编译器签名，就可以装入与之相关联的库签名文件。如果没有检测出编译器签名，语法分析过程也丝毫不受影响。此时，从装载器提供的入口点开始的所有代码都要被反编译，而且不做库例程识别。指出很重要一点是，有些编译器有 set-up 例程，由于它们使用间接跳转，所以很难对它们做语法分析；在这种情况下，无法对完整的代码进行语法分析，反编译将陷入困境。

void FrontEnd (char *filename, CALL_GRAPH *callGraph) { /* Parse image while building call graph and generating Icode */ parse (callGraph); /* Transform basic block list into a graph */ constructGraph (callGraph); /* Check for bytes used as both data and code */ checkDataCode (callGraph); if (option.asm1) /* disassembly of the program */ { printf ("dcc: writing assembler file %s.a1\n", filename); disassemble (1, callGraph, filename); } if (option.Interact) /* interactive option, display window */ interactWin (callGraph); /* Idiom analysis */ semAnalyzer (callGraph); /* Remove redundancies from the graph */ compressCFG (callGraph); if (option.stats) /* statistics on the basic blocks */ displayStats (callGraph); if (option.asm2) /* disassembly after graph compression */ disassemble (2, callGraph, filename); if (option.map) /* display memory bitmap */ displayMemMap(); }

图 9-4: 前端子过程

根据一个子程序的入口点，语法分析器实现把数据/指令分离的算法，见第 4 章图 4-7 的描述。这个算法递归地跟随从入口点开始的所有路径，而且模拟写入寄存器 (只要有可能)。当遇到一个子程序调用的时候，子程序的入口地址变成一个新的入口点，通过递归的方式对它进行分析，把子程序信息放在调用图里。寄存器内容被模拟以便检测某些情况，比如程序利用中断结束——这将依赖一个或多个寄存器的内容。对于编译器签名已经被识别的程序，已知它是通过在主程序结束之后执行的一个例程来终止的，因此，在这个例子中模拟寄存器的内容不是必需的。这个语法分析器不尝试识别外层寻址(up-level addressing)。

图 9-5 显示 PROC 记录的定义，它储存一个子程序的有关信息。注意，在语法分析期间并非所有的字段都被填充信息；有些是稍后由通用的反编译机器进行填充。

typedef struct _proc { Int procEntry; /* label number */ char name[SYMLEN]; /* Meaningful name for this proc */ STATE state; /* Entry state */ flags32 flg; /* Combination of Icode & Procedure flags */ int16 cbParam; /* Probable no. of bytes of parameters */ STKFRAME args; /* Array of formal arguments */ LOCAL_ID localId; /* Local symbol table */ ID retVal; /* Return value type (for functions) */ /* Icodes and control flow graph */ ICODE_REC Icode; /* Record of ICODE records */ PBB cfg; /* Pointer to control flow graph (cfg) */ PBB *dfsLast; /* Array of pointers to BBs in revPostorder */ Int numBBs; /* Number of basic blocks in the graph cfg */ boolT hasCase; /* Boolean: subroutine has an n-way node */ /* For interprocedural live analysis */ dword liveIn; /* Registers used before defined */ dword liveOut; /* Registers that may be used in successors */ boolT liveAnal; /* Procedure has been analysed already */ } PROC;

图 9-5: 子过程记录

语法分析器后面跟随一个 checkDataCode() 子过程，它检查在位映像图里的每个字节，看有没有两个标志：数据，和代码；当字节位置被标志为是数据和代码，那么相应的子程序被标志为潜在地使用自修改代码。

9.3.2 中间代码

在 dcc 中使用的中间代码叫做 Icode，它有两种类型：低级的和高级的。低级 Icode 是 i80286 机器指令到汇编助记符的一个映射，确保每个 Icode 指令只执行一个逻辑指令。例如，指令：

DIV bx

把 dx:ax 除以 bx 所得的商赋值给 ax，而且把前面这个商的余数赋值给 dx；因此，DIV 机器指令是执行了两个逻辑指令。在 Icode 指令中，DIV 被分割成两个不同的指令：iDIV 和 iMOD。前者执行操作数的除法，而后者执行操作数的求余。因为这两个指令都使用被指令结果重写的寄存器 (即，这个例子中的 dx 和 ax)，所以在指令被执行之前这些寄存器需要被放在一个临时寄存器中。dcc 把寄存器 tmp 做为临时寄存器使用。这个寄存器被向前代入到另一个指令而且在数据流分析期间被清除掉。上述机器指令被翻译成三个 Icode 指令，如下：

iMOV tmp, dx:ax ; tmp = dx:ax iDIV bx ; ax = tmp / bx iMOD bx ; dx = tmp % bx

其中 iDIV 和 iMOD 的被除数都被设置为 tmp 寄存器而非 dx:ax。图 9-6 显示不同的机器指令，它们用多于一个 Icode 指令表示。每个指令给出一个例子。

机器指令	Icode 指令	含义
DIV cl	iMOV tmp, ax	tmp = ax
	iDIV cl	al = tmp / cl
	iMOD cl	ah = tmp % cl
LOOP L	iSUB cx, 1	cx = cx - 1
	iJNCXZ L	cx<>0 goto L
LOOPE L	iSUB cx, 1	cx = cx - 1
	iCMP cx, 0	cx == 0?
	iJZ L	zeroFlag == 1 goto L
	iJNCXZ L	if cx<>0 goto L
LOOPNE L	iSUB cx, 1	cx = cx = 1
	iCMP cx, 0	cx == 0?
	iJNE L	zeroFlag == 0 goto L
	iJNCXZ L	if cx<>0 goto L
XCHG cx, bx	iMOV tmp, cx	tmp = cx
	iMOV cx, bx	cx = bx
	iMOV bx, tmp	bx = tmp

图 9-6: 用多于一个 Icode 指令表示的机器指令

复合的指令，比如 rep movsb 被表现为两个不同的机器指令，但它只是执行一个逻辑的字符串功能；在这个例子中就是当字符串未结束时重复。这些指令就用一个 Icode 指令表示；在这个例子中是 iREP_MOVS。

执行低级任务的机器指令，比如从一个端口输入和输出，最有可能是由编译器在编译高级语言代码的时候产生的 (即，嵌入的汇编代码能够使用这些指令但是高级代码不生成这些指令)。这些指令在 Icode 中被标志为非高级的，而且使用这些指令的子程序也被这样做了标记，以便只为该子程序生成汇编程序。下列指令被认为不是由编译器生成的；被标记一个星号的指令有时是非高级的，取决于所使用的寄存器操作数：

AAA, AAD, AAM, AAS, CLI, DAA, DAS, *DEC, HLT, IN, *INC, INS, INT, INTO, IRET, JO, JNO, JP, JNP, LAHF, LOCK, *MOV, OUT, OUTS, *POP, POPA, POPF, *PUSH, PUSHA, PUSHF, SAHF, STI, *XCHG, XLAT

Icode 指令有一组与之关联的 Icode 标志用来确认在指令的语法分析期间发现的特性。下列标志被使用：

l B：字节操作数 (缺省是字操作数)。

l I：立即的（常数) 源操作数。

l No_Src：没有源操作数。

l No_Ops：没有操作数。

l Src_B：源操作数是字节，目的操作数是字。

l Im_Ops：隐含的操作数。

l Im_Src：隐含的源操作数。

l Im_Dst：隐含的目的操作数。

l Seg_Immed：指令有一个重定位的段数值。

l Not_Hll：非高级的指令。

l Data_Code：指令修改数据。

l Word_Off：指令有一个字偏移量 (即，可能是一个地址)。

l Terminates：指令终止该程序。

l Target：指令是一个跳转指令的目标。

l Switch：当前的间接跳转决定一个 n 路语句的开始。

l Synthetic：指令是人工合成的 (即，在二进制文件中不存在的)。

l Float_Op：下一个指令是一个浮点指令。

dcc 使用一个由机器指令索引的静态表，实现 i80286 机器指令到低级 Icodes 的映射，该表包括的信息有相关联的 Icode，被使用的和被定义的条件码、标志，以及确定源操作数和目的操作数的子过程 (不同的子过程被用于不同的操作数类型，因此，相同的子过程被几个不同的指令使用)。机器指令到 Icode 指令的映射把 250 个指令转换成 108 个 Icode 指令。这个映射见图 9-7 所示。

低级指令	机器指令（组)
iAAA	37
iAAD	D5
iAAM	D4
iAAS	3F
iADC	10..15, (80..83)(50..57,90..97,D0..D7)
iADD	00..05, (80..83)(40..47,80..87,C0..C7)
iAND	20..25, (80..83)(60..67,A0..A7,E0..E7)
iBOUND	62
iCALL	E8, FE50..FE57, FE90..FE9F, FED0..FED7, FF50..FF57, FF90..FF9F, FFD0..FFD7
iCALLF	9A, FE58..FE5F, FE98..FE9F, FED8..FEDF, FF58..FF5F, FF98..FF9F, FFD8..FFDF
iCLC	F8
iCLD	FC
iCLI	FA
iCMC	F5
iCMP	38..3D, (80..83)(78..7F,B8..BF,F8..FF)
iCMPS	A6, A7
iREPNE_CMPS	F2A6, F2A7
iREPE_CMPS	F3A6, F3A7
iDAA	27
iDAS	2F
iDEC	48..4F, FE48..FE4F, FE88..FE8F, FEC8..FECF, FF48..FF4F, FF88..FF8F, FFC8..FFCF
iDIV	F670..F677, F6A0..F6A7, F6F0..F6F7, F770..F777, F7A0..F7A7, F7F0..F7F7
iMOD	F670..F677, F6A0..F6A7, F6F0..F6F7, F770..F777, F7A0..F7A7, F7F0..F7F7, F678..F67F, F6A8..F6AF, F6F8..F6FF, F778..F77F, F7A8..F7AF, F7F8..F7FF
iENTER	C8
iESC	D8..DF
iHLT	F4
iIDIV	F678..F67F, F6A8..F6AF, F6F8..F6FF, F778..F77F, F7A8..F7AF, F7F8..F7FF
iIMUL	69, 6B, F668..F66F, F6A8..F6AF, F6E8..F6EF, F768..F76F, F7A8..F7AF, F7E8..F7EF
iIN	E4, E5, EC, ED
iINC	40..47, FE40..FE47, FE80..FE87, FEC0..FEC7, FF40..FF47, FF80..FF87, FFC0..FFC7
iINS	6C, 6D
iREP_INS	F36C, F36D
iINT	CC, CD
iINTO	CE
iIRET	CF
iJB	72
iJBE	76
iJAE	73
iJA	77
iJE	74
iJNE	75
iJL	7C
iJGE	7D
iJLE	7E
iJG	7F
iJS	78
iJNS	79
iJO	70
iJNO	71
iJP	7A
iJNP	7B
iJCXZ	E3
iJNCXZ	E0..E2
iJMP	E9, EB, FE60..FE67, FEA0..FEA7, FEE0..FEE7, FF60..FF67, FFA0..FF A7, FFE0..FFE7
iJMPF	EA, FE68..FE6F, FEA8..FEAF, FEE8..FEEF, FF68..FF6F, FFA8..FF AF, FFE8..FFEF
iLAHF	9F
iLDS	C5
iLEA	8D
iLEAVE	C9
iLES	C4
iLOCK	F0
iLODS	AC, AD
iREP_LODS	F3AC, F3AD
iMOV	88..8C, 8E, A0..A3, B0..BF, C6, C7
iMOVS	A4, A5
iREP_MOVS	F3A4, F3A5
iMUL	F660..F667, F6A0..F6A7, F6E0..F6E7, F760..F767, F7A0..F7A7, F7E0..F7E7
iNEG	F658..F65F, F698..F69F, F6D8..F6DF, F758..F75F, F798..F79F, F7D8..F7DF
iNOT	F650..F657, F690..F697, F6D0..F6D7, F750..F757, F790..F797, F7D0..F7D7
iNOP	90
iOR	08..0D, (80..83)(48..4F,88..8F,C8..CF)
iOUT	E6, E7, EE, EF
iOUTS	6E, 6F
iREP_OUTS	F36E, F36F
iPOP	07, 17, 1F, 58..5F, 8F
iPOPA	61
iPOPF	9D
iPUSH	06, 0E, 16, 1E, 50..57, 68, 6A, FE70..FE77, FEB0..FEB7, FEF0..FEF7, FF70..FF77, FFB0..FFB7, FFF0..FFF7
iPUSHA	60
iPUSHF	9C
iRCL	(C0,C1,D0..D3)(50..57,90..97,D0..D7)
iRCR	(C0,C1,D0..D3)(58..5F,98..9F,D8..DF)
iREPE	F3
iREPNE	F2
iRET	C2, C3
iRETF	CA, CB
iROL	(C0,C1,DO..D3)(40..47,80..87,C0..C7)
iROR	(C0,C1,D0..D3)(48..4F,88..8F,C8..CF)
iSAHF	9E
iSAR	(C0,C1,D0..D3)(78..7F,B8..BF,F8..FF)
iSHL	(C0,C1,D0..D3)(60..67,A0..A7,E0..E7)
iSHR	(C0,C1,D0..D3)(68..6F,A8..AF,E8..EF)
iSBB	18..1D, (80..83)(58..5F,98..9F,D8..DF)
iSCAS	AE, AF
iREPE_SCAS	F3AE, F3AF
iREPNE_SCAS	F2AE, F2AF
iSIGNEX	98, 99
iSTC	F9
iSTD	FD
iSTI	FB
iSTOS	AA, AB
iREP_STOS	F3AA, F3AB
iSUB	28..2D, (80..83)(68..6F,A8..AF,E8..EF)
iTEST	84, 85, A8, A9, F640..F647, F680..F687, F6C0..F6C7, F740..F747, F780..F787, F7C0..F7C7
iWAIT	9B
iXCHG	86, 87, 91..97
iXLAT	D7
iXOR	30..35, (80..83)(70..77,B0..B7,F0..F7)

图 9-7: 适用于 i80286 的低级中间代码

9.3.3 控制流向图生成器

dcc 通过把基本块放在一个列表上然后把那个表转换成一个适当的图，为每个子程序实现控制流向图的构造。在语法分析的时候，只要遇到一个基本块的结束指令，该基本块就构造完成了，而且在该子程序的开始指令和结束指令在 Icode 数组里的索引号被记录储存。如果遇到无法确定它把控制转移到哪里的指令 (即，变址跳转假如未被识别为一个已知的 n 路结构头结点的，间接调用，等等) 那么应该让这个基本块结束了，因为沿着含有该指令的路径上已经没有更多指令需要解析了。这些结点在 dcc 中被叫做迷途结点(no-where)。其他类型的基本块有标准单路的、二路的、n 路的、直通的、调用的、和返回结点。基本块的定义记录见图 9-8 所示。这个信息的大部分稍后由通用的反编译机器填写。

typedef struct _BB { byte nodeType; /* Type of node */ Int start; /* First instruction offset */ Int finish; /* Last instruction in this BB */ flags32 flg; /* BB flags */ Int numHlIcodes; /* # of high-level Icodes */ /* In edges and out edges */ Int numInEdges; /* Number of in edges */ struct _BB **inEdges; /* Array of pointers to in-edges */ Int numOutEdges; /* Number of out edges */ union typeAdr { dword ip; /* Out edge Icode address */ struct _BB *BBptr; /* Out edge pointer to successor BB */ interval *intPtr; /* Out edge pointer to next interval */ } *outEdges; /* Array of pointers to out-edges */ /* For interval and derived sequence construction */ Int beenOnH; /* #times been on header list H */ Int inEdgeCount; /* #inEdges (to find intervals) */ struct _BB *reachingInt; /* Reaching interval header */ interval *inInterval; /* Node's interval */ interval *correspInt; /* Corresponding interval in Gi-1 */ /* For live register analysis */ dword liveUse; /* LiveUse(b) */ dword def; /* Def(b) */ dword liveIn; /* LiveIn(b) */ dword liveOut; /* LiveOut(b) */ /* For structuring analysis */ Int preorder; /* DFS #: first visit of the node */ Int revPostorder; /* DFS #: last visit of the node */ Int immedDom; /* Immediate dominator (revPostorder) */ Int ifFollow; /* follow node (if node is 2-way) */ Int loopType; /* Type of loop (if any) */ Int latchNode; /* latching node of the loop */ Int numBackEdges; /* # of back edges */ Int loopFollow; /* node that follows the loop */ Int caseFollow; /* follow node for n-way node */ /* Other fields */ Int traversed; /* Boolean: traversed yet? */ struct _BB *next; /* Next (initial list link) */ } BB;

图 9-8: 基本块记录

每个子程序的控制流向图由控制流优化(flow-of-control optimizations) 进行最优化——去掉多余的到跳转的跳转、和到跳转的条件跳转。这些最优化有可能从该图中移除一些基本块，因此直到所有可能的结点从图中移除以后才对该图进行编号。同时，每个基本块的前导结点被确定而且被放在*inEdges[]数组内。

9.3.4 语义分析程序

dcc 的语义分析程序确定成语而且用其它的 Icode 指令（组) 代替它们。在 dcc 中所检查的成语都在第 4 章第 4.2.1 节中有描述，被分成下列类别：子程序成语、调用约定、长整型变量运算、以及其它各种成语。

有一些的成语只在 C 语言中可用。在 C 语言中，一个变量可以被先加和后加，以及先减和后减。表现这些指令的机器代码使用一个额外的寄存器保存那个被先加/先减或后加/后减的变量的值，用于对比某数值/变量的检查。这个额外的寄存器可以通过利用某个成语把该指令组转换成一个使用‘先/后 加/减’操作数的指令而被清除掉。

对于在一个条件跳转中的一个后加/后减变量，该变量的值先被复制到一个寄存器，然后该变量被增量或减量，最后，保存最初的变量副本（即，在加或减之前) 的寄存器跟其它标识符相比较。额外寄存器的使用可以利用 C 语言中的后加/后减操作符而清除掉。因此，仅当生成 C 语言代码时才能检查这些成语。图 9-9 显示这个情况。

mov reg, var		mov reg, var
inc var	或者	dec var
cmp var, Y		cmp var, Y
jX label		jX label
	↓
jcond (var++ X Y)		jcond (var-- X Y)

图 9-9: 在一个条件跳转中的后加或后减

类似地，先加/先减利用一个中间的寄存器。该变量先被增量/减量，然后它被移入一个寄存器，跟另一个标识符相比较，然后条件跳转发生。在这个情况中，中间寄存器的使用是因为在比较指令中不能使用除了寄存器之外的标识符。这个中间寄存器能够通过使用一个先加/先减操作符而去掉，如图 9-10 所示。

inc var		dec var
mov reg, var	或者	mov reg, var
cmp reg, Y		cmp reg, Y
jX lab		jX lab
	↓
jcond (++var X Y)		jcond (--var X Y)

图 9-10: 在条件跳转中的先加/先减

在 dcc 中实现了 C 语言依赖的成语。从这些成语的一般格式可知，几个低级 Icode 指令被一个高级的 jcond 指令代替。这个指令被标志为一个高级指令，如此它不再被数据流分析程序处理。而且，所有参与这些成语的其它指令被标志为不表现高级指令。

在成语识别之后，对有符号整型、有符号字节、和长整型变量做简单类型传播。在跨条件结构传播长整型变量的时候，传播通过从图中移除一个结点而修改控制流向图，正如第 4 章第 4.2.2 节所描述。因为高级条件是从图的类型来确定的，所以写入对应的高级 jcond 指令而且那个指令被标志为是一个高级指令。