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

Question

我正在阅读一份关于Java 即时编译器(JIT) 优化技术的文档。其中之一是“循环反转”。文件说：

while您用循环替换常规do-while循环。并且 do-while循环设置在一个if子句中。这种替换导致少了两次跳跃。

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

注意： 如果有人可以用 Java 代码示例解释 JIT 如何将其优化为本机代码以及为什么它在现代处理器中是最佳的，那就太好了。

Answer 1

while (condition) { 
  ... 
}

工作流程：

1. 检查条件；
2. 如果为假，则跳到循环外；
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); 
}

Answer 3

让我们来看看它们：

while版本：

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}

1. 首先，我们测试n并跳转到done();条件不成立。
2. 然后我们使用和递增n。
3. 现在我们跳回到条件。
4. 冲洗，重复。
5. 当条件不再为真时，我们跳转到done()。

do-while版本：

（请记住，我们实际上并没有在源代码中执行此操作[这会引入维护问题]，编译器/JIT 会为我们执行此操作。）

void foo(int n) {
    if (n < 10) {
        do {
            use(n);
            ++n;
        }
        while (n < 10);
    }
    done();
}

1. 首先，我们测试n并跳转到done();条件不成立。
2. 然后我们使用和递增n。
3. 现在我们测试条件，如果它是真的就跳回去。
4. 冲洗，重复。
5. 当条件不再为真时，我们流（而不是跳转）到done().

例如，如果n开始是9，我们根本不会在do-while版本中跳转，而在while版本中，我们必须跳回到开头，进行测试，然后当我们看到它不是真的时跳回到结尾.

Answer 4

Loop inversion is a performance optimization technique which improves performance as the processor can accomplish the same result with fewer instructions. This should mostly improve the performance in boundary conditions.

This link provides another example for loop inversion. In few architectures where decrement and compare is implemented as a single instruction set, It makes sense to convert a for loop to a while with decrement and compare operation.

Wikipedia has a very good example and I am explaining it here again.

 int i, a[100];
  i = 0;
  while (i < 100) {
    a[i] = 0;
    i++;
  }

will be converted by the compiler to

  int i, a[100];
  i = 0;
  if (i < 100) {
    do {
      a[i] = 0;
      i++;
    } while (i < 100);
  }

How this translates to performance? When the value of i is 99, the processor need not perform a GOTO (which is required in the first case). This improves performance.