java - 什么是循环反转技术？

Question

我正在浏览一份关于 just-in-time compiler 的文档。 (JIT) Java 优化技术。其中之一是“循环反转”。文件说:

You replace a regular while loop with a do-while loop. And the do-while loop is set within an if clause. This replacement leads to two fewer jumps.

循环反转如何工作以及它如何优化我们的代码路径？

注: 如果有人能用 Java 代码的例子解释一下 JIT 如何将其优化为 native 代码以及为什么它在现代处理器中是最佳的，那就太好了。

Answer 1

while (condition) { 
  ... 
}

工作流程:

1. 检查条件；
2. 如果为假，则跳到循环外；
3. 运行一次迭代；
4. 跳到顶部。

---

if (condition) do {
  ...
} while (condition);

工作流程:

1. 检查条件；
2. 如果为 false，则跳到循环之外；
3. 运行一次迭代；
4. 检查条件；
5. 如果为真，请跳至第 3 步。

---

比较这两个你可以很容易地看到，后者可能根本不做任何跳转，前提是循环恰好有一步，并且通常跳转的次数会比迭代次数少一。前者要跳回去检查条件，只有在条件为假时才跳出循环。

现代流水线 CPU 架构上的跳转可能会非常昂贵:由于 CPU 在跳转之前完成了检查的执行，因此跳转之后的指令已经在流水线的中间。如果分支预测失败，则必须丢弃所有这些处理。重新启动管道时会延迟进一步执行。

解释上述分支预测:对于每种条件跳转，CPU 都有两条指令，每条指令都包含一个关于结果的赌注。例如，您可以在循环结束时放置一条指令“jump if not zero, betting on not zero”，因为除了最后一次之外的所有迭代都必须进行跳转。这样，CPU 开始使用跳转目标之后的指令而不是跳转指令本身之后的指令来泵送其流水线。

重要提示

请不要以此为例说明如何在源代码级别进行优化。这将完全被误导，因为正如您的问题已经清楚的那样，从第一种形式到第二种形式的转换是 JIT 编译器作为例行程序所做的事情，完全独立。