10. 案例分析-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后

import java.util.Scanner;

.method public static main([Ljava/lang/String;)V
.registers 3
.line 5
    p0 = new-instance java/util/Scanner;
    sget-object v0, Ljava/lang/System;->in:Ljava/io/InputStream;
    invoke-direct {p0, v0}, Ljava/util/Scanner;-><init>(Ljava/io/InputStream;)V
.line 6
    invoke-virtual {p0}, Ljava/util/Scanner;->nextInt()I
    move-result p0
.line 7
    const/4 v0, 0x1
.line 8
    :cond_c
    :goto_c
    if-lez v0, :cond_23
.line 9
    :cond_e
    :goto_e
    const/16 v1, 0x32
    if-le p0, v1, :cond_c
.line 10
    add-int/lit8 p0, p0, 0x1
.line 11
    add-int/lit8 v0, v0, 0x1
.line 12
    const/16 v1, 0xa
    if-le p0, v1, :cond_e
.line 13
    const/16 v1, 0x64
    if-le p0, v1, :cond_21
.line 14
    mul-int/lit8 p0, p0, 0x5
.line 15
    goto :goto_c
.line 17
    :cond_21
    div-int/2addr v0, p0
    goto :goto_e
.line 23
    :cond_23
    sget-object p0, Ljava/lang/System;->out:Ljava/io/PrintStream;
    invoke-virtual {p0, v0}, Ljava/io/PrintStream;->println(I)V
.line 24
    return-void
.end method

虽然相比于汇编，字节码还是很人性化的，为了观感，将这个代码进行优化

1、暂时不考虑try-exception-catch的情况

2、优化跳转指令展示，if + goto-label形式

3、将函数调用转换为便于阅读的形式，优化寄存器类型信息

4、删除冗余代码，将字节码指令优化，改为适合人类阅读的形态

现在，这个代码变成了这个样子

public static void main(java.lang.String[] r2) {
        java.util.Scanner r2 = new java.util.Scanner
        java.io.InputStream r0 = java.lang.System.in
        r2.<init>(r0)
        int r2 = r2.nextInt()
        r0 = 1
    Lc:
        if (r0 <= 0) goto L23
    Le:
        r1 = 50
        if (r2 <= r1) goto Lc
        int r2 = r2 + 1
        int r0 = r0 + 1
        r1 = 10
        if (r2 <= r1) goto Le
        r1 = 100
        if (r2 <= r1) goto L21
        int r2 = r2 * 5
        goto Lc
    L21:
        int r0 = r0 / r2
        goto Le
    L23:
        java.io.PrintStream r2 = java.lang.System.out
        r2.println(r0)
        return
}

为了更好的理解，我简单的画了一下对应，当然稍微偷懒了省略了一写

• 跳过了类型的判断

• 跳过了代码的生成

好了已经很有伪代码的样子了，是啊，字节码就是这么轻松，不用解决各种麻烦的汇编转换的麻烦，再画一下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结构

	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的构造关系，北大的熊英飞老师的课程有提供，虽然讲的不算详细，但是够用了

	定义BasicBlock	支配边界
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的结构如下

生成代码

public static void main(String[] strArr) {
    int nextInt = new Scanner(System.in).nextInt();
    int i = 1;
L2:
    if (i <= 0) goto L20;
L4:
    if (nextInt <= 50) goto L2;
    nextInt = nextInt + 1;
    i = i + 1;
    if (nextInt <= 10) goto L4;
    if (nextInt > 100) goto L14;
    i = i / nextInt;
    goto L4
L14:
    nextInt = nextInt * 5;
    goto L2
L20:
    System.out.println(i);
}

最终翻译为伪代码

public static void main(String[] strArr) {
    int nextInt = new Scanner(System.in).nextInt();
    int i = 1;
    while (i > 0) {
        while (true) {
            if (nextInt > 50) {
                nextInt++;
                i++;
                if (nextInt > 10) {
                    if (nextInt > 100) {
                        nextInt *= 5;
                        break;
                    }
                    i /= nextInt;
                }
            }
        }
    }
    System.out.println(i);
}