Jimple to grimple to byte code

表达式聚合算法

表达式聚合背后的思想相对简单，但是在实践中我们发现很难正确地实现它。
概述:该算法包括考虑单个use-def对，并尝试将def插入到use中，确保此操作不会违反任何数据依赖关系。算法为不动点迭代;它迭代，直到不能执行任何聚合为止。

1. 为了使迭代次数最小化，需要以反伪拓扑顺序考虑语句。例如，在下面的代码中:由于潜在的副作用违反，第一个语句不能聚合到第二个语句之后。因此，应该首先汇总第二种方法

2. 只考虑单个use-def对进行聚合。这些是x =…的形式;x…;只有一个x的定义，只有一个x的用法。

3. 下一步是考虑s和use之间的路径，并确定将s移动到use中是否合法。注意，我们只考虑位于相同扩展基本块中的语句对。这确保连接路径是惟一的。

4. 路径中发生局部in s的重新定义，以防止聚合。

5. 此代码块防止方法调用移动到过去的字段写入，或字段读取过去的字段写入(同名)，或方法调用或数组读取过去的数组写入。

它还防止将方法调用传播到过去的EnterMonitorStmt或ExitMonitorStmt。

8. 此代码块防止使用数组引用、字段引用或其他方法调用对方法调用重新排序。
   在检查语句use(在本例中是use(x,m()， z))时，将f()移动到其他方法调用之前的验证在第一次使用x时停止，因为参数是从左到右求值的。

此时，聚合s并一起使用是安全的

虚拟调用

特殊的调用

效率低下的

从GRIMP生成BAF代码非常简单，因为GRIMP由类似树的语句组成，而BAF是基于堆栈的表示。这里使用的是堆栈机器的标准代码生成技术[2]，即预排序树遍历。

在某些情况下，与原始Java字节码相比，这种树遍历生成的代码可能效率较低。当原始Java源代码包含紧凑的类c结构时，就会发生这种情况，例如a[j++] = 5。注意，从GRIMP代码生成的字节码有两个额外的字节码。如果这样的语句出现在循环中，那么这种低效率可能会对程序执行时间产生重大影响(通常情况下确实如此)。

为了消除这种效率低下的根源，我们对GRIMP生成的代码执行窥视优化。为了优化增量情况，我们搜索表单的Grimp模式:

我们确保s1中定义的局部函数有两种用途，s2中的用途;s3只有一个定义。在这种情况下，我们只发出s3的代码。然而，在为s3生成代码的过程中，当要发出local时，我们还发出代码来复制堆栈上的local，并递增。

这种方法生成相当有效的字节码。在某些情况下，窥视孔模式失效，无法恢复完整的原始结构。在这些情况下，通过BAF生成字节码的第二个选项执行得更好。更多细节见第4章

在执行树遍历之前，我们还执行一个寄存器分配阶段，该阶段将GRIMP局部变量映射到字节码局部变量槽。此映射执行两次;一次用于32位数量，另一次用于64位数量。寄存器分配方案是一种基于启发式着色的简单方案，它使用干涉图来防止冲突。
从JIMPLE生成字节码的第一步是将JIMPLE作为树表示，并使用标准的树遍历技术将其直接转换为BAF代码，如第3.2.2节所述。

以这种方式生成代码会产生低效的BAF代码，因为局部变量用于存储中间结果，而不是使用堆栈。例如，图3.15中给出了运行示例的摘录，显式地显示了转换。

我们可以在图3.15中看到商店。我,负载。变量的i对stack0#12可以被删除，因为它们的值只是暂时留在堆栈上。消除冗余负载/存储的下一步是优化这种情况和其他情况。完整的翻译可以在图3.16中找到。

生成简单的BAF代码之后，还需要对其进行优化。特别是，我们必须删除前面步骤引入的所有冗余存储/加载指令，尽管理论上有许多不同的冗余存储/加载指令模式，但实际上只有少数几种冗余存储/加载指令占大多数

store/load:一个store指令后面跟着一个load指令，该指令引用同一个局部变量，没有其他用途。存储和加载指令都可以被删除，而值只保留在堆栈上。

store/load/load:一个store指令后面跟着两条load指令，它们都引用同一个局部变量，没有其他用途。这3条指令可以消除，并引入dup指令。dup指令通过复制删除存储和第一次加载后堆栈上剩余的值来替换第二次加载

当所有相关的指令相互遵循时，消除冗余模式是很简单的。如果有交错指令(与load一样)。r l3 # 3,商店。在图3.17中运行的例子中，rl3 #3)然后必须小心地消除这一对。特别地，我们计算了这些交织指令的最小堆栈高度变化和净堆栈高度变化，只有当它们都等于零时，我们才能消除对(或三重)。如果它们不为零，则尝试对BAF指令进行一些重新排序。这些消除在基本块上执行，并执行迭代，直到没有更多更改为止。在我们的综述论文[28]中对这种优化进行了详细的讨论

在图3.17中运行的例子中，load/store消除的例子很明显，本地变量stack0#11和stack0#5和$stack0#9上有两个store/load/load三元组

首先：将Jimple码通过表达式聚合算法转换为grimple码：

test r0                                                                                                                      test r0
r0:=@this:test                                                                                                         r0:=@this:test
specialinvoke  r0.<java.lang.Object: void <init>()>()                                        r0.<java.lang.Object: void <init>()>()
return
java.lang.String[] r0;                                                                                              java.lang.String[] r0;
java.io.PrintStream $r1                                                                                        
byte l1;                                                                                                                   byte l1,l2;
l1 = 1;                                                                                                                      l1=1;
byte l2;                            
l2 = 2                                                                                                                       l2=2;                                                                         
r0:=@parameter0: java.lang.String[];                                                                 r0:=@parameter0: java.lang.String[];
int l3;                                                                                                                        int l3;
l3 = l1 + l2;                                                                                                              l3 = l1 + l2;
$r1 = <java.lang.System: java.io.printStream Out>          <java.lang.System: java.io.printStream Out>.<java.io.printStream: void println(int)>(i2);
virtualinvoke $r1.<java.io.printStream: void println(int)>(i2);
return

test r0                                                                                                                      word r0;
r0:=@this:test                                                                                                        r0:=@this:test;
                                                                                                                                load.r r0;
r0.<java.lang.Object: void <init>()>()                                                                 specialinvoke <java.lang.Object: void <init>()>;
return
java.lang.String[] r0;                                                                                            word r0;
r0:=@parameter0: java.lang.String[];                                                                r0:=@parameter0: java.lang.String[];                                        
l1=1;l2=2;                                                                                                              push 1;
byte l1,l2;                                                                                                               push 2;
int l3;                                                                                                                       add.b;
                                                                                                                               staticinvoke <java.lang.System: java.io.Stream Out>
l3 = l1 + l2;                                                                                                            virtualinvoke <java.io.printStream: void println(int)>;
<java.lang.System: java.io.printStream Out>.<java.io.printStream: void println(int)>(i2);

word r0;                                                                                                                  aload_0
r0:=@this:test;                                                                                                       invokespecial
load.r r0;                                                                                                                 return
specialinvoke <java.lang.Object: void <init>()>;
word r0; 
r0:=@parameter0: java.lang.String[]                                                                 
push 1;                                                                                                                  iconst_1                  istore_1
push 2;                                                                                                                  iconst_2                  istore_2
add.b;                                                                                                                    iload_1                    iload_2
virtualinvoke <java.io.printStream: void println(int)>;                                    iadd                          istore_3             
                                                                                                                               getstatic    
                                                                                                                               iload_3
                                                                                                                               invokevirtual
                                                                                                                               return

最终得到的编码是这样的

 public test();
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0       
         1: invokespecial #1                  // Method java/lang/Object."<init>":()Vint
         4: return        

  public static void main(java.lang.String[]);
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=4, args_size=1
         0: iconst_1      
         1: istore_1      
         2: iconst_2      
         3: istore_2      
         4: iload_1       
         5: iload_2       
         6: iadd          
         7: istore_3      
         8: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
        11: iload_3       
        12: invokevirtual #3                  // Method java/io/PrintStream.println:(I)V
        15: return