反编译原理系列:基本块 | 表达式 | 控制流 | 优化与输出
本文的主要参考文献为Decompiler Design。
本系列是对Furikiri反编译器项目的一些总结。原本有打算汉化Decompiler Design(以下简称DD),但是一直没有时间(已经拖了五个月了),所以这里先把比较关键的部分记录下来。因此,本文中的举例将采用TJS2语言及其汇编指令(DD中是C语言/X86汇编)。TJS2的字节码采用的是基于寄存器的指令集,类似于X86汇编,但TJS2语言中没有指针和goto,因此相对简单。该教程对于任何寄存器指令集的语言(如C语言)都有直接参考价值。除此之外,高级语言的虚拟机如JVM(Java)、CLR(C#)等通常采用基于栈的指令集,在基本块分析和表达式生成上可能会有少许不同,但大部分还是可以参考的。
基本块
基本块(Basic Block,简称“块”)是(反)编译原理中的概念,是(汇编)指令的集合。
【定义】基本块是一串连续的指令,它的首条指令是进入并执行这一串指令的唯一入口,它的最后一条指令是退出这一串指令的唯一出口。(换言之,在执行时,一个基本块中的指令要么全部被执行,要么全部不执行。)
每条跳转语句(如无条件跳转JMP、满足条件则跳转JF、不满足条件则跳转JNF等)的目的地址会是一个基本块的开始,每条跳转语句本身会是一个基本块的结束。
从一大段汇编中划分出所有的基本块,并确定它们之间的跳转关系,也就生成了这段汇编代码的控制流图(Control Flow Graph, CFG)。这对于后续识别代码的逻辑结构(分支、循环)是非常有必要的。
有了上面的定义,识别基本块的算法就非常好理解了。我们只需要对每条跳转指令(JMP、JF、JNF、函数返回RET)进行重点分析。除了RET之外,每条跳转语句之后通常会分为两个基本块,一个紧挨着跳转语句所在的基本块(不跳转),另一个是跳转语句的目的地址开始的基本块(跳转)。在扫描基本块的过程中,还要同时记录基本块之间的跳转关系,即一个基本块可以由哪些基本块跳转过来(这个基本块的前驱predecessor/From),以及它可以跳转到哪些基本块(这个基本块的后继successor/To)。
具体的算法伪代码(摘自DD,如有不理解之处也可参见Furikiri实际代码中的ScanBlocks方法):
Block *get_block_at(Address start_address)
{
Block *block = find in BlockList a block for start_address
if block == not found
block = new Block at start_address
blockList += block
return block
}
CreateBasicBlocks(current_procedure)
{
current_address = current_procedure->entry_address
block = get_block_at(current_address)
current_procedure->entry_block = block
workList.push = current_address
while workList not empty
current_address = workList.pop
block = get_block_at(current_address)
next:
label = find label at address higher than current_address
branch = find branch at address higher than current_address
if label->address < branch->address_after_branch
block->length = label->address - block->address
current_address = label->address
next_block = get_block_at(current_address)
next_block->preds += block
block->succs += next_block
block = next_block
goto next
end if
block->length = branch->address_after_branch - block->address
if branch is return // returns have no known destination
continue
end if
next_block = get_block_at(branch->destination)
next_block->preds += block
block->succs += next_block
workList.push = branch->destination
if branch is not conditional
continue // will resume from branch destination
end if
next_block = get_block_at(branch->address_after_branch)
next_block->preds += block
block->succs += next_block
block = next_block
current_address = block->address
goto next
end while
sort blockList by block's start address
}
在识别基本块、完成控制流图的构建之后,我们基本上就达到了类似于IDA中的Flow Chart的效果:

图1:IDA中的控制流图
支配树
上文中我们已经建立了CFG,从CFG中我们可以看到,除了正常向下(继续执行后面代码)的边之外,还有很多向上(返回之前代码)的跳转边,即回边(back edge)。后者经常出现在循环结构(如for、while、do while)中。(除了循环结构之外,还有可能是goto语句手动跳转。但是在TJS2中不存在goto,所以我们不需要考虑这种情况。即使需要考虑goto,在此步骤中我们也可以将其视为循环,在后续恢复循环结构时如遇失败再转换为goto语句即可。)
我们可以把条件跳转指令如JF、JNF都反编译为if(...) goto (地址),但这样无法表现出原代码中的循环逻辑。因此我们首先要从CFG中识别出循环,进而将循环转化为具体的循环结构。
为了识别出循环,我们需要计算每个基本块的(前序)支配树(Dominator Tree)和后序支配树(Post Dominator Tree)。(本文中“支配”默认是指前序支配。)
【定义】在计算机科学中,若控制流图的开始节点(可以理解为源)到 节点n 的每一条路径均要经过 节点d,则称 节点d (前序)支配 节点n。
若控制流图的 节点n 到终结节点的每一条路径均要经过 节点d,则称 节点d 后序支配 节点n。
易得,每个节点(前序&后序)支配它自己。
在反编译过程中,节点就是基本块。如何通过支配树识别循环呢?
下图是一个do-while结构的控制流图。通过上文中的定义我们可知,1支配234,2支配34,3支配4。通常顺序执行情况下,一个节点的后继节点不会支配它,比如2不支配1(抵达1不需要经过2),3不支配2(抵达2不需要经过3,因为可以只经过1),4不支配3。但作为3的后继节点(之一)的2却能支配3(抵达3必须经过2)。注意从3出发的深色的回边使得2成为了3的后继节点。

图2:do-while的控制流图
当发现了这条回边,也就是符合“节点A的一个后继节点B支配A”这个条件,我们就认为这里存在一个循环(Loop),其中B是这个循环的头节点(Header),A是这个循环的尾结点。在上图中,2是循环的头节点。找到头节点后,我们从尾节点开始遍历前驱节点,直到抵达头节点,这些节点就构成了一个循环。(根据支配的定义,在头节点之后的 尾结点的前驱节点 一定被头节点支配。)
识别并记录循环,后续就可以将循环进一步转换为具体的while、for等结构。这将在“控制流”一章中讲解。
这就是支配树在识别循环上的作用。下面的算法可以计算支配树(摘自DD,如有不理解之处也可参见Furikiri实际代码中的ComputeDominators方法):
ComputeDominators()
{
int nBlocks = block_list.size();
int i = 0;
for each block in block_list {
block->id = i++;
block->dominators = new BitVector(nBlocks)
block->dominators->SetAllBitsTo(1)
}
block = block_list[0]
block->dominators->SetAllBitsTo(0)
block->dominators->SetBit(block->id)
BitVector T(nBlocks)
do {
changed = false
for each block in block_list {
if (block == entry_block)
continue
for each pred in block->predecessors {
T.SetAllBitsTo(0)
T.Or(block->dominators)
block->dominators->And(pred->dominators)
block->dominators->SetBit(block->id)
if (block->dominators != T)
changed = true
}
}
} while (changed);
}
下面的算法可以根据支配树识别循环(摘自DD,如有不理解之处也可参见Furikiri实际代码中的ComputeNaturalLoops方法):
NaturalLoopForEdge(Block header, Block tail)
{
Stack workList;
Loop loop;
loop = new Loop();
loop->header = header
loop->blocks += header
if header != tail {
loop->blocks += tail
workList += tail
}
while workList not empty {
block = workList.pop
for each pred in block->predecessors {
if not loop->find(pred) {
loop->blocks += pred
workList += pred
}
}
}
return loop
}
ComputeNaturalLoops()
{
LoopSet loopSet;
for each block in block_list {
if (block == entry_block)
continue
for each succ in block->successors {
// Every successor that dominates its predecessor
// must be the header of a loop.
// That is, block -> succ is a back edge.
if block->dominators->find(succ)
loopSet += NaturalLoopForEdge(succ, block);
}
}
}
尽管此处没有用到,但后序支配树在反编译中也是有用的(如识别循环中的break以及if条件合并,这些内容可能会在后续文章中讲解),因此在计算(前序)支配树时应当一并计算(如有不解之处可参见Furikiri源码)。