8. 案例分析：JAXD-1
示例Java代码
import java.util.Scanner;
public class test {
public static void main(String[] args) {
Scanner myInput = new Scanner( System.in );
int a = myInput.nextInt();;
int y = 1;
while (y > 0) {
while (a > 50) {
a = a + 1;
y = y + 1;
if (a > 10) {
if (a > 100) {
a = a * 5;
break;
} else {
y = y / a;
}
}
}
}
System.out.println(y);
}
}编译成Smali后
虽然相比于汇编，字节码还是很人性化的，为了观感，将这个代码进行优化
1、暂时不考虑try-exception-catch的情况
2、优化跳转指令展示，if + goto-label形式
3、将函数调用转换为便于阅读的形式，优化寄存器类型信息
4、删除冗余代码，将字节码指令优化，改为适合人类阅读的形态
现在，这个代码变成了这个样子
为了更好的理解，我简单的画了一下对应，当然稍微偷懒了省略了一写
跳过了类型的判断
跳过了代码的生成
好了已经很有伪代码的样子了，是啊，字节码就是这么轻松，不用解决各种麻烦的汇编转换的麻烦，再画一下CFG图
下一步，通过SSA+PHI还原变量，没有定义一个IR而是直接操作了原有的smali代码
1、生成CFG图
2、构建支配树、支配边界、：计算支配边界用于构造SSA, 循环不变量提取
算法来源：<http://www.hipersoft.rice.edu/grads/publications/dom14.pdf*>
3.1、循环识别
3.2、构造SSA
在basic-block上构建寄存器的def-use结构，这里我给出上面代码的def-use结构
R0
1,4,7
1,2,4,7,8
R1
3,4,5
3,4,5
R2
1,4,6,8
1,4,5,6,8
register define-use-pair
R0:(1,1) (1,2) (1,4) (1,8) (4,4) (4,2) (4,7) (4,8) (7,2) (7,4) (7,8)
R1: (3,3) (4,4) (5,5)
R2: (1,1) (1,4) (4,4) (4,5) (4,6) (6,4) (8,8)
基于def-use-pair，进行活跃变量分析（Live Variable Analysis）删除冗余的寄存器分配
也即是说存在两种情况，第一种，变量被定义了却没有被使用过（这里不存在），第二种，变量的定义与使用都在同一个基本块内，很明显，R1寄存器就是这种情况，这种寄存器将被活跃变量分析处理后inline掉
活跃变量分析后的register define-use-pair
R0: (1,2) (1,4) (1,8) (4,2) (4,7) (4,8) (7,2) (7,4) (7,8)
R2: (1,4) (4,5) (4,6) (6,4)
基于支配边界分配寄存器的PHI，即在变量定义的基本块的支配边界添加PHI，直到不动点（TODO,这个描述过于抽象，是否有办法更加简略一点），这里只要处理R1和R2:
关于支配边界+phi的构造关系，北大的熊英飞老师的课程有提供，虽然讲的不算详细，但是够用了
R0
1,4,7
2,3
R2
1,4,6
2,3
R0支配边界计算过程：
DF{1,4,7} ⇒ {3} : DF{1} = {}; DF{4} = {3}; DF{7} = {3};
DF1{1,3,4,7} ⇒ {2,3} : DF{3} = {2}
DF2{1,2,3,4,7} ⇒ {2,3} : DF{2} = {}
R2计算过程：
DF{1,4,6} ⇒ {2,3} : DF{1} = {}; DF{4} = {3}; DF{6} = {2};
DF1{1,2,3,4,6} ⇒ {2,3}: DF{3} = {2}; DF{2} = {}
按照支配边界转换顺序，构建SSA并在BasicBlock 2与3中插入phi节点，插入并清理R1的残留后，带有SSA的结构如下
生成代码
最终翻译为伪代码
Last updated