什么是环路反演技术？

Question

我正在阅读一篇文档,其中讨论了Java的即时编译器(JIT)优化技术.其中一个是"循环反转".文件说:

用while循环替换常规do-while循环.而 do-while循环的中设置if条款.这种替换可以减少两次跳跃.

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

注意: 如果有人可以用Java代码的例子解释JIT如何将其优化为本机代码以及为什么它在现代处理器中是最佳的,那将是很好的.

Answer 1

while (condition) { 
  ... 
}

工作流程:

1. 检查条件;
2. 如果为false,跳转到循环外;
3. 运行一次迭代;
4. 跳到顶部.

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

工作流程:

1. 检查条件;
2. 如果错误,跳到循环之外;
3. 运行一次迭代;
4. 检查条件;
5. 如果是,请跳到第3步.

比较这两个,您可以很容易地看到后者可能根本不会进行任何跳转,前提是循环只有一步,通常跳转次数比迭代次数少一次.前者必须跳回来检查条件,只有当条件为假时跳出循环.

现代流水线CPU体系结构的跳跃可能非常昂贵:由于CPU在跳转之前完成了检查的执行,超出该跳转的指令已经处于管道中间.如果分支预测失败,则必须丢弃所有这些处理.在管道被重新训练时,进一步的执行被延迟.

解释所提到的分支预测:对于每种条件跳转,CPU有两条指令,每条指令包括对结果的下注.例如,你会在循环结束时发出一条说明" 如果不为零则跳转,在不归零时投注 "的指令,因为必须在除最后一次之外的所有迭代上进行跳转.这样,CPU开始使用跳转目标之后的指令而不是跳转指令本身之后的指令来泵送其管道.

重要的提示

请不要不以此为如何在源代码级优化的例子.这完全是错误的,因为从你的问题中已经清楚地看到,从第一种形式到第二种形式的转换是JIT编译器根据例行情况完成的事情.

Answer 2

这可以优化始终至少执行一次的循环.

然后,常规while循环将始终至少跳回到开始一次并在结束时跳到结尾.运行一次的简单循环的示例:

int i = 0;
while (i++ < 1) {
    //do something
}  

一个do-while在另一方面循环将跳过第一个和最后一个跳跃.这是一个与上面相同的循环,它将在没有跳转的情况下运行:

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}