反编译原理系列：基本块 | 表达式 | 控制流 | 优化与输出

本文的主要参考文献为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源码）。