6.控制流还原（1）

控制流还原是反编译器中端优化流程的最后几步了，其目标是将原有的CFG图，还原成 while/if/switch 组成的高层次结构。

人类很难阅读并理解完全由jmp/goto跳转组合成的CFG结构图，因此还原出高层的控制流结构，能够极大的提升反编译结果的可读性。

以前的，还原后的结构标准：goto语句越少越好；

但是随着goto-less的算法研究（参考补充章节中的no-more-goto论文），以及对于编译器，尽可能的还原出接近源码的反编译结果，因为源码的可读性是最佳的。

可以移步到补充章节，在那里我讨论了和控制流还原相关的两篇很有意思的论文：

• “Dream: no-more-goto”：这篇论文提出了一种no-more-goto算法，从理论上证明了任何的CFG都能还原出不带goto的高层次控制流结构。

• “Sailr：no-need no-more-goto”：这个更有牛逼，驳斥了上面的no-more-goto算法，认为判断控制流还原算法应该和编译前的源码对比，并给出了更为先进的控制流还原理论。

好吧，先找我们从传统的控制流还原开始讲起吧。

介绍：传统控制流还原的实现

IDA和Ghidra的控制流还原技术均使用了“区间分析/结构分析”的经典编译器技术。这一理论来源与编译原理中的控制流分析技术。需要先介绍一个CFG流图关键的特性：可规约性（reducible）

可规约性（reducible）：

可规约性（reducible），这个词用来描述不够清楚，它的本质含义是“结构良好的流图”（well-structured），但是既然业界都这样说，那么后面还是用”可规约”这样来描述。

可归于的定义本身很复杂

一种定义方法是：如果图中的循环没有多个出口/多个入口，那么这个图一般而言就是可规约的。如果一个图不可规约，那么基于结构分析的技术，还原后一定会有goto语句（无法正确还原）。

上面这个定义太难懂了。

所以，在本单元的反编译器理论中，使用另一种简略的定义；对一个流图进行预定义的各种变幻，如果流图塌缩成单个结点，则称这个流图是可归约的，否则就是不可规约的。

如果一个图可规约，那么图中的循环就能被正确的还原出控制流（控制流还原的主要复杂读就是在于循环）

至于“塌缩”的意思，往下看。

区间分析与结构分析在反编译器中的运用

其基本原理即是：通过某一些列的规则将原有的流图不断的“塌缩”，最后成为一个点。

塌缩规则

• 基础规则 - 连续两个基础块可以直接压缩成一个

• 循环规则-自循环

• 循环规则-while循环

• 循环规则-do+while循环

• 条件分支- if+then

• 条件分支- if+else+then

• 条件分支-switch+case

示例：

参考：《高级编译器设计与实现》第七章

todo

难题：对于不可规约图的处理

于源码来说，不可规约的情况很少很少；

例如，js这种不支持goto语句的语言，源码中基本上不会产生不可规约的情况。常见的流程控制指令 (例如IF、FOR、WHILE、BREAK、CONTINUE）都会产生可规约控制流图。

在支持goto语句，比如C语言中，源码中不可规约流图常常出现在goto跳出多重循环等场景。

但是事情总会出岔子，编译器的总能给你找事情做。