JVM循环优化技术深度解析：让你的循环飞起来

本文导读

循环是程序中最常见的结构之一，也是性能优化的重点区域。在许多应用程序中，循环都扮演着非常重要的角色。为了提升循环的运行效率，编译器工程师们提出了不少面向循环的编译优化方式。

本文将带你深入理解JVM即时编译器中的循环优化技术，你将学到：

• 循环无关代码外提的原理与实现
• 循环预测如何外提null检测和范围检测
• 循环展开的效果与代价权衡
• 完全展开的适用场景
• 循环判断外提与循环剥离的优化思路

---

一、循环无关代码外提：把计算移到循环外面

所谓的循环无关代码（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指令来访问）。

1.1 优化效果

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

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，现在都在循环之前完成。原本循环中需要执行这两个表达式的地方，现在直接使用循环之前这两个表达式的执行结果。

1.2 实现机制：Sea-of-Nodes IR的魔力

在Sea-of-Nodes IR的帮助下，循环无关代码外提的实现并不复杂。

上图截取了Graal为前面例子中的foo方法所生成的IR图（局部）。其中B2基本块位于循环之前，B3基本块为循环头。

x*y所对应的21号乘法节点，以及a.length所对应的47号读取节点，均不依赖于循环体中生成的数据，而且都为浮动节点。节点调度算法会将它们放置于循环之前的B2基本块中，从而实现这些循环无关代码的外提。

我们来看一下生成的机器码中的循环部分：

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];
}

2.1 null检测的外提

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

为了更好地阐述具体的优化，我们精简了原来的例子，并将iaload展开，最终形成如下所示的代码：

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;
}

在这段代码中，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 evaluate to false
            throw new NullPointerException();
        }
        if (i < 0 || i >= a.length) { // range check
            throw new ArrayIndexOutOfBoundsException();
        }
        sum += a[i];
    }
    return sum;
}

由于循环之前已经做过了null检测，如果a为null的话直接去优化了，根本不会进入循环。因此，循环里面的null检测永远不会命中，可以直接消除。

2.2 范围检测的外提

除了null检测之外，其他循环无关检测都能够按照这种方式外提至循环之前。甚至是循环有关的下标范围检测，都能够借助循环预测来外提，只不过具体的转换要复杂一些。

之所以说下标范围检测是循环有关的，是因为在我们的例子中，该检测的主体是循环控制变量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
    deoptimize(); // never returns
}
for (int i = INIT; i < LIMIT; i += STRIDE) {
    sum += a[i]; // 不包含下标范围检测
}

可以看到，原本需要在每次循环中都进行的范围检测，现在只需要在循环开始前做一次检测即可。如果初始值和最大值都在合法范围内，那么循环过程中的所有迭代都必然是合法的。

---

三、循环展开：以空间换时间的艺术

另外一项非常重要的循环优化是循环展开（Loop Unrolling）。它指的是在循环体中重复多次循环迭代，并减少循环次数的编译优化。

我们来看一个例子：

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

上面的代码经过一次循环展开之后将形成下面的代码：

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;
}

3.1 计数循环的判定

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

1. 维护一个循环计数器，并且基于计数器的循环出口只有一个（但可以有基于其他判断条件的出口）
2. 循环计数器的类型为int、short或者char（即不能是byte、long，更不能是float或者double）
3. 每个迭代循环计数器的增量为常数
4. 循环计数器的上限（增量为正数）或下限（增量为负数）是循环无关的数值

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

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

3.2 循环展开的权衡

循环展开的缺点显而易见：它可能会增加代码的冗余度，导致所生成机器码的长度大幅上涨。

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

比如前面的例子经过循环展开之后便可以进一步优化为如下所示的代码：

int foo(int[] a) {
    int sum = 0;
    for (int i = 0; i < 64; i += 2) {
        sum += a[i];
        sum += -a[i + 1];
    }
    return sum;
}

可以看到，i % 2 == 0这个判断被消除了，因为展开之后我们可以直接知道i是偶数，i+1是奇数。

3.3 完全展开

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

int foo(int[] a) {
    int sum = 0;
    for (int i = 0; i < 4; i++) {
        sum += a[i];
    }
    return sum;
}

举个例子，上述代码将被完全展开为下述代码：

int foo(int[] a) {
    int sum = 0;
    sum += a[0];
    sum += a[1];
    sum += a[2];
    sum += a[3];
    return sum;
}

完全展开消除了循环变量和循环判断，使得代码变成了纯顺序执行，这为后续的更多优化打开了大门。

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

---

四、其他循环优化技术

除了循环无关代码外提以及循环展开之外，即时编译器还有两个比较重要的循环优化技术：循环判断外提以及循环剥离。

4.1 循环判断外提（Loop Unswitching）

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

int foo(int[] a) {
    int sum = 0;
    for (int i = 0; i < a.length; i++) {
        if (a.length > 4) {
            sum += a[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];
        }
    } 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语句的不同分支执行不同的代码逻辑。

4.2 循环剥离（Loop Peeling）

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

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;
}

举个例子，上面这段代码剥离了第一个迭代后，将变成下面这段代码：

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;
}

可以看到，剥离第一个迭代之后，剩下的循环体变得非常规律——每次都访问a[i-1]，这为向量化等优化创造了条件。

---

总结与思考

本文深入讲解了JVM即时编译器中的循环优化技术，让我们来总结一下核心要点：

1. 循环无关代码外提 将循环中值不变的表达式外提至循环之前，避免在循环中重复计算。

• 对于普通的计算（如乘法、字段读取），通过Sea-of-Nodes IR和节点调度自动完成
• 对于涉及控制流的检测（如null检测、范围检测），通过循环预测实现外提

2. 循环预测 在循环之前插入检测代码，命中则去优化，从而消除循环中的检测代码。

• 可以外提循环无关的null检测
• 也可以外提循环有关的下标范围检测，只需验证初始值和最大值是否在范围内

3. 循环展开 在循环体中重复多次循环迭代，减少循环次数，以空间换时间。

• 只有计数循环才能被展开
• 缺点是可能增加代码量，但能带来更多优化机会
• 完全展开是特殊情况，将整个循环转换为顺序执行的代码

4. 其他循环优化

• 循环判断外提：将循环中的if语句外提，两个分支各放一份循环
• 循环剥离：剥离前几个或后几个特殊迭代，使循环体更规律

实践建议：

• 编写循环时，尽量将循环无关的计算移到循环外面，虽然JIT可能会帮你做，但手动优化更可靠
• 保持循环体简洁，这有助于JIT进行各种循环优化
• 不要手动进行循环展开，让JIT来决定是否展开以及展开几次
• 使用标准的for循环模式（int i = 0; i < n; i++），这样更容易被识别为计数循环

最后，留给大家一个思考题：

void foo(byte[] dst, byte[] src) {
    for (int i = 0; i < dst.length; i++) {
        dst[i] = src[i];
    }
}

上面这段代码经过循环展开变成下面这段代码。你能想到进一步优化的机会吗？ （提示：数组元素在内存中的分布是连续的。假设dst[0]位于0x1000，那么dst[1]位于0x1001。）

void foo(byte[] dst, byte[] src) {
    for (int i = 0; i < dst.length - 4; i += 4) {
        dst[i] = src[i];
        dst[i + 1] = src[i + 1];
        dst[i + 2] = src[i + 2];
        dst[i + 3] = src[i + 3];
    }
    ... // post-loop
}

答案将在下一篇文章——向量化优化中揭晓。