GCC如何展开循环，如果它的迭代次数在编译时是未知的？

Question

我正在阅读GCC的优化选项时，发现了选项-funroll-all-loops。

它的描述如下：

展开所有循环，即使它们进入循环时迭代次数不确定。这通常会使程序运行更慢。 '-funroll-all-loops'意味着与'-funroll-loops'相同的选项

如果编译器无法在编译时知道循环迭代次数，那么它如何展开循环呢？编译器不需要这些信息来展开吗？它生成什么相应的C代码？在什么情况下这可能有用，如果通常会使程序运行更慢？

- PC Luddite

---

@Olaf，这不是一个具体的问题吗？OP明显在问gcc（一种特定的C编译器）如何能够知道如何展开循环，如果其边界未知。 - Ricky Mutschlechner

如果我想知道一个特定的编译器选项是什么意思，为什么会被认为是过于宽泛的问题？ - PC Luddite

@paulsm4 我不这么认为。如果编译器已经知道边界，那么决定就在于实际展开多少。但这个问题并不是在问那个。 - Ricky Mutschlechner

您可能会发现我在Switch case weird scoping的我的回答中讨论的Duff's Device有所帮助。(其他帖子中也提到了Duff's Device.) - Joshua Taylor

Answer 1

这里有一些C语言代码展示如何实现它：

int iterations = 100;
int unrollValue = 8;

while (iterations%unrollvalue)
{
   // insert loop code here
   iterations--;
}

while (iterations)
{
   // insert unrollValue copies of loop code here
   iterations-= unrollValue;
}

编译器将用相对跳转替换第一个循环，但这在C中不容易表示。请注意，将展开成2的幂次方可以使编译器使用掩码来代替（昂贵的）除法运算。

- Steve Kolokowsky

Answer 2

如果这个选项通常会使程序运行更慢，那么它在什么情况下会有用呢？

嗯，他们假设如果你选择了这个选项，你知道你在做什么，如果你不知道，就不应该使用这个选项。

gcc将会做什么呢？我用了这个样例程序：

#include <stdio.h>

void f(int j )
{
  for( int k = 0; k < j; ++k )
  {
    printf( "%d\n", k ) ;
  }
}

我已经使用godbolt进行测试，它根据剩余迭代次数生成跳转表（在此处查看实例）:

cmpl    $1, %ebp
movl    $1, %ebx
je  .L1
testl   %r12d, %r12d
je  .L27
cmpl    $1, %r12d
je  .L28
cmpl    $2, %r12d
je  .L29
cmpl    $3, %r12d
je  .L30
cmpl    $4, %r12d
je  .L31
cmpl    $5, %r12d
je  .L32
cmpl    $6, %r12d
je  .L33

- Shafik Yaghmour

---

当然，如果在其中加入一个 printf，那么好处基本上为零;-) - Mike Dunlavey

Answer 3

它可以做一些像这样的事情：

while(n >= 8){
  foo(); foo(); foo(); foo(); foo(); foo(); foo(); foo(); 
  n -= 8;
}
while(n > 0){
  foo();
  n--;
}

当然，使用 Duff's Device可以避免编写第二个循环。

为什么这样做呢？这取决于用户。如果 foo（）花费的时间多于几个周期，或者原始循环所占用的总体墙钟时间少于5％，或者 n 通常很小，则可能不值得麻烦。

- Mike Dunlavey

Answer 4

你不能假设编译器的中间表示形式有所谓的相应的 C 代码。但在这种情况下，我期望最接近的等效物是类似于Duff's Device的东西，它是一个序列（通常在循环中），可以在计算位置进入。

- Toby Speight