循环无关代码外提

外提无关代码

  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*ya.length外提,还提供int数组加载指令iaload所暗含的null checkrange 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虚拟机