循环无关代码外提

外提无关代码

  1. 循环无关代码：循环中值不变的表达式
  2. 在不改变程序语义的情况下，将循环无关代码提出循环外
    • 那么程序将避免重复执行这些表达式，从而达到性能提升的效果
1
2
3
4
5
6
7
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 对应的字节码
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
  1. 循环体中的表达式x*y和循环判断条件中的a.length均属于循环不变代码
  2. x*y是整数乘法运算，a.length是内存访问操作，读取数组对象a的长度
    • 数组的长度存放在数组对象的对象头中，通过arraylength指令来访问

理想情况下，经过循环无关代码外提后，等同于下面的手工优化版本

1
2
3
4
5
6
7
8
9
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外提，还提供int数组加载指令iaload所暗含的null check和range check，伪代码如下

1
2
3
4
5
6
7
8
9
int iaload(int[] arrayRef, int index) {
    if (arrayRef == null) { // null check
        throw new NullPointerException();
    }
    if (index < 0 || index >= arrayRef.length) { // range check
        throw new ArrayIndexOutOfBoundsException();
    }
    return arrayRef[index];
}

外提null check

foo方法中的null check属于循环无关代码，即与第几次循环无关，将iaload伪代码展开，得到

1
2
3
4
5
6
7
8
9
10
11
12
13
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 ArrayIndexOutOfBoundsException();
        }
        sum += a[i];
    }
    return sum;
}

在C2中，null check的外提是通过额外的编译优化（_即循环预测_，-XX:+UseLoopPredicate）来实现的
该优化的实际做法就是在循环之前插入同样的检测代码，并在命中的时候进行去优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}

外提range check

由于如果外提range check之后，将无法再引用到循环变量，因此即时编译器需要转换检测条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = INIT; i < LIMIT; i += STRIDE) {
    if (i < 0 || i >= a.length) { // range check
        throw new ArrayIndexOutOfBoundsException();
    }
    sum += a[i];
}
----------
// 经过range check外提之后
if (INIT < 0 || IMAX >= a.length) {
    // IMAX是i所能达到的最大值，不一定是LIMIT-1
    detopimize(); // never returns
}
for (int i = INIT; i < LIMIT; i += STRIDE) {
    sum += a[i]; // 不再包含range check
}

循环展开

循环展开：在循环体中重复多次循环迭代，并减少循环次数的编译优化，是一种以空间换时间的优化方式

1
2
3
4
5
6
7
int foo(int[] a) {
    int sum = 0;
    for (int i = 0; i < 64; i++) {
        sum += (i % 2 == 0) ? a[i] : -a[i];
    }
    return sum;
}

经过一次循环展开后

1
2
3
4
5
6
7
8
int foo(int[] a) {
    int sum = 0;
    for (int i = 0; i < 64; i += 2) { // 步长为2
        sum += (i % 2 == 0) ? a[i] : -a[i];
        sum += ((i + 1) % 2 == 0) ? a[i + 1] : -a[i + 1];
    }
    return sum;
}

计数循环

在C2中，只有计数循环才能被展开，计数循环需要满足以下条件

  1. 维护一个循环计数器，并且基于计数器的循环出口只有一个
    • 但可以有基于其他判断条件的出口
  2. 循环计数器的类型只能为int/short/char
  3. 每个迭代循环计数器的增量为常数
  4. 循环计数器的上限和下限是与循环无关的数值
1
2
3
4
5
6
7
8
9
for (int i = START; i < LIMIT; i += STRIDE) { .. }
// 等价于
int i = START;
while (i < LIMIT) {
    ..
    i += STRIDE;
}
// 只要LIMIT是与循环无关的数值，STRIDE是常数，而且循环中除了i < LIMIT之外没有其他基于循环变量i的循环出口
// 那么C2便会将该循环标识为计数循环

优缺点

循环展开的缺点：增加了代码的冗余度，导致所生成机器码的长度大幅上涨
但随着循环体的增大，优化机会也会不断地增加，一旦循环展开能触发进一步的优化，总体的代码复杂度也将降低

1
2
3
4
5
6
7
8
int foo(int[] a) {
    int sum = 0;
    for (int i = 0; i < 64; i += 2) {
        sum += a[i];
        sum += -a[i + 1];
    }
    return sum;
}

完全展开

完全展开：当循环的数量是固定值而且非常小，即时编译器将循环完全展开
原本循环中的循环判断语句将不复存在，变成了若干顺序执行的循环体

1
2
3
4
5
6
7
int foo(int[] a) {
    int sum = 0;
    for (int i = 0; i < 4; i++) {
    sum += a[i];
    }
    return sum;
}

完全展开

1
2
3
4
5
6
7
8
int foo(int[] a) {
    int sum = 0;
    sum += a[0];
    sum += a[1];
    sum += a[2];
    sum += a[3];
    return sum;
}

即时编译器会在循环体的大小与循环展开次数之间作出权衡

循环判断外提

循环判断外提：将循环中的if语句外提到循环之前，并且在该if语句的两个分支中分别放置一份循环代码

1
2
3
4
5
6
7
8
9
int foo(int[] a) {
    int sum = 0;
    for (int i = 0; i < a.length; i++) {
        if (a.length > 4) {
            sum += a[i];
        }
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 循环判断外提
int foo(int[] a) {
    int sum = 0;
    if (a.length > 4) {
        for (int i = 0; i < a.length; i++) {
            sum += a[i];
        }
    } else {
        for (int i = 0; i < a.length; i++) {
        }
    }
    return sum;
}
// 进一步优化
int foo(int[] a) {
    int sum = 0;
    if (a.length > 4) {
        for (int i = 0; i < a.length; i++) {
            sum += a[i];
        }
    }
    return sum;
}

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

循环剥离

循环剥离：将循环的前几个迭代或者后几个迭代剥离出循环的优化方式
通过将这几个特殊的迭代剥离出去，使得原本的循环体的规律性更加明显，从而触发进一步优化

1
2
3
4
5
6
7
8
9
int foo(int[] a) {
    int j = 0;
    int sum = 0;
    for (int i = 0; i < a.length; i++) {
        sum += a[j];
        j = i;
    }
    return sum;
}

剥离第一个迭代

1
2
3
4
5
6
7
8
9
10
int foo(int[] a) {
    int sum = 0;
    if (0 < a.length) {
        sum += a[0];
        for (int i = 1; i < a.length; i++) {
            sum += a[i - 1];
        }
    }
    return sum;
}

参考资料

深入拆解Java虚拟机