循环优化 | Notes

JVM中即时编译器面向循环的编译优化。

循环无关代码外提

所谓的循环无关代码(Loop-invariant Code)，指的是循环中值不变的表达式。如果能够在不改变程序语义的情况下，将这些循环无关代码提出循环之外，那么程序便可以便便重复执行这些表达式，从而达到性能提升的效果。

int foo(int x, int y, int[] a) {
    int sum = 0;
    for(int i = 0; i < a.length; i++) {
        sum += x * y + a[i];
    }
    return sum;
}

//对应的字节码
int foo(int, int, int[]);
    code:
        0: iconst_0
        1: istore 4
        3: iconst_0
        4: istore 5
        6: goto 25
//循环体开始
        9: iload 4          //load sum
        11:iload_1          //load x
        12:iload_2          //load y
        13:imul             //x*y
        14:aload_3          //load a
        15:iload 5          //load i
        17:iaload           //a[i]
        18:iadd             //x*y + a[i]
        19:iadd             //sum+(x*y+a[i])
        20:istore 4         //sum=sum+(x*y+a[i])
        22:iinc 5,1         //i++
        25:iload 5          //load i
        27:aload_3          //load a
        28:arraylength      //a.length
        29:if_icmplt 9      //i<a.length
//循环体结束
        32:iload 4
        34:ireturn

上述代码中，循环体中的表达式x*y，以及循环判断条件中的a.length均属于循环不变代码。前者是一个整数乘法运算，而后者则是内存访问操作，读取数组对象a的长度。(数组的长度存放于数组对象的对象头中，可通过arraylength指令来访问。)

理想情况下，上述代码经过循环无关代码外提之后，等同于下面这一手工优化版本。

int fooManualOpt(int x, int y, int[] a) {
    int sum = 0;
    int t0 = x * y;
    int t1 = a.length;
    for(int i = 0; i < t1; i++) {
        sum += t0 + a[i];
    }
    return sum;
}

无论是乘法运算x*y，还是内存访问a.length，现在都在循环之前完成。原本循环中需要执行这两个表达式的地方，现在直接使用循环之前这两个表达式的执行结果。(借助Sea-of-Nodes IR实现循环无关代码外提比较简便)

0x02f0: mov edi,ebx         //ebx存放着x*y的结果
0x02f2: add edi,DWORD PTR [r8+r9*4+0x10]
                            //[r8+r9*4+0x10]即a[i]
                            //r8指向a,r9d存放着i
0x02f7: add eax,edi         //eax存放着sum
0x02f9: inc r9d             //i++
0x02fc: cmp r9d,r10d        //i<a.length//r10d存放着a.length
0x02ff: jl 0x02f0

上述机器码是foo方法的编译结果中的循环。这里面么有整数乘法指令，也没有读取数组长度的内存访问指令。它们的值已在循环之前计算好了，并且分别保存在寄存器ebx以及r10d之中。在循环之中，代码直接使用寄存器ebx以及r10d所保存的值，而不用在循环中反复计算。

从省城的机器码中可以看出，除了x*y和a.length的外提之外，即时编译器还外提了int数组加载指令iaload所暗含的null检测(null check)以及下标范围检测(range check)。

如果将iaload指令想象成一个接收数组对象以及下标作为参数，并且返回对应数组元素的方法，那么它的伪代码如下所示：

int iaload(int[] arrayRef, int index) {
    if(arrayRef == null) {//null检测
        throw new NullPointerException();
    }
    if(index < 0 || index >= arrayRef.length) {//下标范围检测
        throw new ArrayIndexOutOfBoundsException();
    }
    return arrayRef[index];
}

foo方法中的null检测属于循环无关代码。这是因为它始终检测作为输入参数的int数组是否为null，而这与第几次循环无关。

int foo(int[] a) {
    int sum = 0;
    for(int i = 0; i < a.length; i++) {
        if(a == null) {//null check
            throw new NullPointerException();
        }
        if(i < 0 || i >= a.length) {//range check
            throw new ArrayIndexOutOfBoundException();
        }
        sum += a[i];
    }
    return sum;
}

上述代码中，null检测涉及了控制流依赖，因而无法通过Sea-of-Nodes IR转换以及节点调度来完成外提。

在C2中，null检测的外提是通过额外的编译优化，也就是循环预测(Loop Prediction,对应虚拟机参数-XX:+UseLoopPredicate)来实现的。该优化的实际做法是在循环之前插入同样的检测代码，并在命中的时候进行去优化。这样一来，循环中的检测代码便会被归纳并消除掉。

int foo(int[] a) {
    int sum = 0;
    if(a == null) {
        deoptimize();//never returns
    }
    for(int i = 0; i < a.length; i++) {
        if(a == null) {//now evluate to false
            throw new NullPointerException();
        }
        if(i < 0 || i >= a.length) {//range check
            throw new ArrayIndexOutOfBoundsException();
        }
        sum += a[i];
    }
    return sum;
}

除了null检测之外，其他循环无关检测都能够按照这种方式外提至循环之前。甚至是循环有关的下标范围检测，都能够借助循环预测来外提，只不过具体的转换要复杂一些。(检测的主题是循环控制变量i，[0,a.length]，它的值将随着循环次数的增加而改变。)

下标范围检测是循环有关的，检测的主体是循环控制变量i(取值范围[0，a.length])，它的值将随着循环次数的增加而改变。外提下标范围检测之后，无法再引用到循环变量i，因此，即时编译器需要转换检测条件。

for(int i = INIT; i < LIMIT; i += STRIDE) {
    if(i < 0 || i >= a.length) {//range check
        throw new ArrayIndexOutOfBoundsException();
    }
    sum += a[i];
}
---
//经过下标范围检测外提之后：
if(INIT < 0 || IMAX >= a.length) {
    //IMAX是i所能达到的最大值，它不一定是LIMIT-1
    detopimize();//never returns
}
for(int i = INIT; i < LIMIT; i += STRIDE) {
    sum += a[i];//不包含下标范围检测
}

循环展开

循环展开(Loop Unrolling)。指的是在循环体中重复多次循环迭代，并减少循环次数的编译优化。(在默认情况下，即时编译器仅能将循环展开60次-XX:LoopUnrollLimit)

在C2中，只有计数循环(Counted Loop)才能被展开。所谓计数循环需要满足四个条件：

维护一个循环计数器，并且基于计数器的循环出口只有一个(但可以有基于其他判断条件的出口)。
循环计数器的类型为int、short或者char(即不能是byte、long，更不能是float或者double)。(循环变量改为long类型，可以“避免”这个优化)
每个迭代循环计数器的增量为常数。
循环计数器的上限(增量为正数)或下限(增量为负数)是循环无关的数值。

for(int i = START; i < LIMIT; i += STRIDE) {...}
//等价于
int i = START;
while(i < LIMIT) {
    ..
    i += STRIDE;
}

上面两种循环中，只要LIMIT是循环无关的数值，STRIDE是常数，而且循环中除了i<LIMIT之外没有其他基于循环变量i的循环出口，那么C2便会将该循环识别为计数循环。

缺点：它可能会增减代码的冗余度，导致所生成机器码的长度大幅上涨。

优点：随着循环体的增大，优化机会也会不断增加。一旦循环展开能够触发进一步的优化，总体的代码复杂度也将降低。

循环展开有一种特殊情况，完全展开(Full Unroll)。当循环的数目是固定值而且非常小时，即时编译器会将循环全部展开。此时，原本循环中的循环判断语句将不复存在，取而代之的是若干个顺序执行的循环体。

即时编译器会在循环体的大小与循环展开次数之间做出权衡。对于仅迭代三次(或以下)的循环，即时编译器将进行完全展开；对于循环体IR节点数据超过阈值的循环，即时编译器则不会进行任何循环展开。

其他循环优化

循环判断外提

循环判断外提(loop unswitching)指的是将循环中的if语句外提至循环之前，并且在该if语句的两个分支中分别放置一份循环代码。

循环判断外提与循环无关检测外提所针对的代码模式比较类似，都是循环中的if语句。不同的是，后者在检查失败时会抛出异常，中止当前的正常执行路径；而前者所针对的是更加常见的情况，即通过if语句的不同分支执行不同的代码逻辑。

循环剥离

循环剥离(loop peeling)指的是将循环的前几个迭代或者后几个迭代剥离出循环的优化方式。一般来说，循环的前几个迭代或者后几个迭代都包含特殊处理。通过将这几个特殊的迭代剥离出去，可以使原本的循环体的规律性更加明显，从而触发进一步的优化。

总结

循环无关代码外提将循环中值不变的表达式，或者循环无关检测外提至循环之前，以避免在循环中重复进行冗余计算。前者是通过Sea-of-Nodes IR以及节点调度来共同完成的，而后者则是通过一个独立优化–循环预测来完成的，循环预测还可以外提循环有关的数组下标范围检测。

循环展开是一种在循环中重复多次迭代，并且相应的减少循环次数的优化方式。它是一种以空间换时间的优化方式，通过增大循环体来获取更多的优化机会。循环展开的特殊形式是完全展开，将原本的循环转换成若干个循环体的顺序执行。

其他：循环判断外提、循环剥离