超级牛的 Java 反编译大法（三）：循环结构

前文指路：

YAK，公众号：Yak Project超级牛的Java反编译大法（二）：If 语句解析

在高级编程语言 Java 中，我们拥有多种循环语法，如 for、foreach、while 以及 do-while。这些语法糖为开发者提供了便利，但在 JVM 眼中，它们最终都会被转换为一系列更基础的条件跳转和无条件跳转指令，如上一篇中提到的 ifeq,  ifne, if_icmp<cond> 等字节码指令。

循环结构则是巧妙地利用这些条件跳转指令与无条件跳转指令（如 goto ）组合，构建出一个可重复执行的代码路径。

通过分析不同循环语句生成的 CFG，我们可以发现一个共同的拓扑特征：图中存在一个有向环（ Cycle ）。这个环代表了代码的重复执行部分，而环的退出机制则由环内的一个或多个条件分支节点提供。

让我们分别审视几种典型循环的 CFG 结构：

while 循环是一种“前测试”循环，其 CFG 结构通常如下：

1. 循环头（ Loop Header ）: 一个条件判断节点，它既是循环的入口，也是循环体执行完毕后返回再次判断的地方。

2. 循环体（ Loop Body ）: 从条件判断为真（ True ）的分支引出的节点序列。

3. 回边（ Back Edge ）: 循环体末端会有一条边指回到循环头，形成闭环。

4. 循环出口（ Loop Exit ）: 条件判断为假（ False ）的分支指向循环外的后继节点。

for 循环（如 for(int i=0; i<10; i++)）和 foreach 循环本质上是 while 循环的语法糖。其初始化语句在循环前执行，而迭代语句（如 i++）则被置于循环体的末尾，紧邻着跳回循环头的回边。因此，它们的 CFG 结构与 while 循环高度同构。

下图展示了一个典型的 while 或 for 循环的 CFG 结构：

do-while 循环是一种“后测试”循环，其 CFG 结构与 while 略有不同：

1、入口: 直接进入循环体，而不是先进行条件判断。

2、循环体: 至少执行一次的代码块。

3、循环条件判断: 循环体执行完毕后，才会遇到条件判断节点。

4、回边: 条件为真（ True ）的分支指回循环体的入口，形成环。

5、循环出口: 条件为假（ False ）的分支指向循环外的后继节点。

综上所述，所有循环结构在 CFG 中都可以被抽象为：一个包含条件分支的有向环，其中一条分支导向环内（继续循环），另一条分支导向环外（跳出循环）。

这个统一的模型是后续自动化识别算法的基础。

为了使循环识别过程严谨且可自动化，我们需要引入图论中的一些关键概念。

在 CFG 中，如果从图的入口节点（ Entry ）到节点 N 的每一条路径都必须经过节点 D，那么我们称节点 D 支配（ Dominates ）节点 N，记作 D dom N。支配关系是识别循环结构的核心。

一条有向边 T -> H（从节点T指向节点 H）被称为回边，当且仅当它的头节点H支配其尾节点 T（H dom T）。

回边的存在是循环的充要条件。回边的头节点 H，即被支配者指向支配者的那个节点，就是我们直观感受上的循环头（ Loop Header ）。循环头是进入循环的唯一入口（在“结构化”程序中），并且它支配着循环体内的所有节点。

一个由回边  T -> H 定义的自然循环，其节点集合包括：

1. 循环头 H。

2. 所有能够到达 T 且不经过 H 的节点集合。

这个定义精确地圈定了循环体内的所有基本块。一个循环由其唯一的回边和循环头唯一确定。

基于以上理论，我们可以设计一套精确的循环识别算法：

前提：已经构建完成程序的控制流图（ CFG ）。

算法步骤：

• 计算支配关系：

  遍历整个 CFG，计算出每个节点的全集支配节点。这通常通过求解数据流方程的迭代算法来实现，最终可以构建一棵支配树（ Dominator Tree ），其中每个节点的父节点是其直接支配节点（ Immediate Dominator ）。

• 识别回边：

  (1) 遍历CFG中的每一条边 u -> v。

  (2) 利用上一步计算出的支配关系，检查头节点 v 是否支配尾节点 u（即 v dom u）。

  (3) 如果 v dom u 成立，则 u -> v 是一条回边。记录下所有找到的回边。

• 构造自然循环（识别循环体）：

  1、对于每一条已识别的回边 T -> H：

  (1) 初始化一个空的循环节点集合 LoopNodes，并将H加入其中。

  (2) 创建一个工作列表 Worklist，并将T加入其中。

  (3) 当 Worklist 不为空时：a. 从Worklist中取出一个节点 M。 b. 如果 M 不在 LoopNodes 中： i. 将 M 添加到 LoopNodes。 ii. 遍历 M 的所有前驱节点 P，将 P 添加到 Worklist 中。

  2、遍历结束后，LoopNodes 集合就包含了由回边 T -> H 定义的这个自然循环的所有节点。

通过这个算法，我们可以识别出程序中所有的（可能是嵌套的）循环，并精确地确定每个循环的头部和体部节点集合。

在识别出循环体 LoopNodes 之后，我们可以进一步分析循环的控制流。

• 循环出口节点（ Loop Exit Node ）： 

  一个节点 N 属于循环体 LoopNodes，但它的一条出边指向一个不属于 LoopNodes 的节点 E，那么 N 就是一个循环出口节点，而 E 则是循环的终止节点（ Termination Node ）之一。循环的终止条件，就是 N 中导向 E 的条件分支。

• 解析 break 语句： 

  在 CFG 中，break 语句表现为一条从循环体内部节点出发的、无条件的跳转（ goto ），其目标是该循环的一个终止节点。因此，任何从循环体内节点到其终止节点的直接边，都可以被解析为 break。

• 解析 continue 语句：

  continue 语句则表现为一条从循环体内部节点出发的、无条件的跳转，其目标是该循环的循环头（ Loop Header ），这会使程序跳过本次循环的剩余部分直接开始下一次迭代的判断。

• 带标签的跳转（ Labeled Jumps ）： 

  Java 等语言支持 break label；和 continue label；，这使得跳转可以跨越多层嵌套的循环。在 CFG 层面，这依然是一个 goto 指令，但其跳转目标是：

• break label;：跳转到被 label 所标记的、外层循环的终止节点。

• continue label;：跳转到被label所标记的、外层循环的循环头。

• 在分析时，需要根据支配关系和循环嵌套关系，正确匹配跳转指令与其对应的目标循环。

本文介绍了从高级语言的循环语法到其底层控制流图表示的转换，并在此基础上提供了形式化的循环识别方法。我们通过引入支配关系、回边和自然循环等图论概念，将直观的循环认知转化为严谨的算法步骤。

这套方法不仅能够精确地识别出各类循环的边界，还能清晰地解析 break、continue 等复杂的控制流转移，以便将字节码清晰准确的转为 Java 源码。

END

YAK官方资源 

Yak 语言官方教程：https://yaklang.com/docs/intro/Yakit 视频教程：https://space.bilibili.com/437503777Github下载地址：https://github.com/yaklang/yakitYakit官网下载地址：https://yaklang.com/Yakit安装文档：https://yaklang.com/products/download_and_installYakit使用文档：https://yaklang.com/products/intro/常见问题速查：https://yaklang.com/products/FAQ

原文始发于微信公众号（Yak Project）：超级牛的 Java 反编译大法（三）：循环结构