C++编译器能优化“for”循环内部的“if”语句吗？

Question

考虑如下示例：

if (flag)
  for (condition)
    do_something();
else
  for (condition)
    do_something_else();

如果在 for 循环内部 flag 没有发生改变，那么这应该与以下语句在语义上等价:

for (condition)
  if (flag)
    do_something();
  else
    do_something_else();

只有在第一种情况下，代码可能会更长（例如，如果使用了多个for循环或者do_something()是一个与do_something_else()基本相同的代码块），而在第二种情况下，标志被检查多次。

我很好奇当前的C++编译器（尤其是g++）是否能够优化第二个示例以消除for循环内部重复的测试。如果可以的话，在什么情况下可能实现此优化？

- generic-identity

Answer 1

如果确定变量flag不会在循环中改变，也不能被do_something或do_something_else更改，那么可以将其提取到循环外。我听说过这个叫做循环提升，但维基百科有一个称为“循环不变码移动”的词条。

如果flags是局部变量，编译器应该能够进行此优化，因为它保证不会影响生成的代码的行为。

如果flags是全局变量，并且您在循环内调用函数，则可能无法执行优化-它可能无法确定这些函数是否修改了全局变量。

这也可能受到你所做的优化类型的影响-优化大小会偏向非提升版本，而优化速度则可能会偏向提升版本。

一般来说，您不必担心这种事情，除非分析表明该函数是热点，并且通过查看编译器输出的汇编代码发现生成的代码效率低下。像这样的微小优化您应该总是交给编译器，除非您确实必须自己处理。

- Michael

---

谢谢您的回答。通过您提供的维基百科链接，我找到了“循环展开”的页面，这似乎是更精确的术语来描述这种类型的优化。 - generic-identity

虽然术语并不是非常明确，但是loop-hoisting和loop-invariant-code-motion并没有被真正用来描述这种优化。它们更多的是用于单个指令。 - Paul Biggar

OP提到的“循环展开”链接：https://en.wikipedia.org/wiki/Loop_unswitching - BrodieG

Answer 2

使用GCC和-O3尝试：

void foo();
void bar();

int main()
{
    bool doesnt_change = true;
    for (int i = 0; i != 3; ++i) {
        if (doesnt_change) {
            foo();
        }
        else {
            bar();
        }
    }
}

主函数的结果：

_main:
pushl   %ebp
movl    %esp, %ebp
andl    $-16, %esp
call    ___main
call    __Z3foov
call    __Z3foov
call    __Z3foov
xorl    %eax, %eax
leave
ret

所以它确实优化了选择（并展开了较小的循环）。

如果doesnt_change是全局变量，则不会进行此优化。

- UncleBens

---

你可以尝试一下我下面使用的代码片段吗？在你的代码片段中，编译器仅仅是移除了第二个分支，因为它永远不会被执行。（这个技巧是通过从一个 extern volatile 变量初始化 doesnt_change 来实现的，这样编译器就无法确定它将具有哪个值）。 - peterchen

Answer 3

我相信如果编译器能确定标志将保持不变，它可以进行一些重排：

const bool flag = /* ... */;
for (..;..;..;)
{
    if (flag)
    {
        // ...
    }
    else
    {
        // ...
    }
}

如果flag不是const，编译器不能保证优化循环，因为它无法确定flag是否会改变。如果进行静态分析，它可以，但并非所有编译器都这样做，我认为。 const是告诉编译器标志不会改变的可靠方法，之后就由编译器处理。

像往常一样，进行性能分析并找出是否真的存在问题。

- GManNickG

---

“const”是一个编译器检查的条件，但对优化没有影响。 - peterchen

彼得，const 与优化有很大关系。 - GManNickG

@peter，这并不完全正确。符合标准的 C++ 实现可以自由地假设一个本质上为 const 的对象永远不会改变，因为标准将任何试图这样做（比如通过 const_cast）定义为未定义行为。因此，在确定是否进行优化时，它肯定可以考虑 const。 - Pavel Minaev

@Michael，这要看情况 - 如果循环体中有一个类似于 foo(&flag) 的调用，并且编译器对 foo 一无所知，则 flag 的声明中是否有 const 关键字可能是决定性的（尽管我不知道是否有任何现实世界的实现会做这种事情）。 - Pavel Minaev

如果我们要站队，我会站在GMan和Pavel这边。:) 看看这个：{const int k=5; for(int i=0; i<k; ++i) g(&i);} 因为 k 是 const 的，并且在 g() 中修改 k 将导致未定义行为，所以编译器可以应用某些优化，如果必须假定 k 可能改变则无法应用这些优化。 - sbi

Answer 4

通常是这样的。但并不保证，编译器会执行它的地方可能很少。

大多数编译器可以轻松将不可变的计算提升出循环，例如如果您的条件是

if (a<b) ....

当a和b不受循环影响时，在循环之前将进行一次比较。

这意味着如果编译器可以确定条件不会改变，那么测试是廉价的，并且跳转预测良好。这反过来意味着测试本身成本为一个周期或根本没有周期（真的）。

在哪些情况下拆分循环会有益？

a）非常紧密的循环，其中1个周期是显著的成本
b）整个循环的两个部分都不适合代码缓存

现在，编译器只能对代码缓存做出假设，并且通常可以按照一种方式对代码进行排序，使得一个分支适合缓存。

没有任何测试，我希望仅在a）是应用此优化的唯一情况下，因为它并不总是更好的选择：

在哪些情况下拆分循环会很糟糕？

当拆分循环使代码大小超出代码缓存时，您将遭受重大打击。现在，这仅会影响到您，如果循环本身在另一个循环中被调用，但这是编译器通常无法确定的事情。

[编辑]
我无法让VC9拆分以下循环（这是少数几种情况之一，实际上可能有益）

extern volatile int vflag = 0;

int foo(int count)
{
   int sum = 0;
   int flag = vflag;
   for(int i=0; i<count; ++i)
   {
      if (flag)
         sum += i;
      else
         sum -= i;
   }

   return sum;
}

[编辑2]
请注意，使用int flag = true;会使第二个分支被优化掉。（不，这里const没有影响;）

这是什么意思？要么它不支持，要么无关紧要，或者我的分析是错误的 ;-)

通常，我认为这只是在极少数情况下有价值的一种优化，在大多数情况下可以轻松手动完成。

- peterchen

---

没有调试信息，总是内联 (/Ob2)，/Ox 与 /Os、/Ot 中的任意一个配合，或者不使用后两者中的任何一个。（我只查看编译器的输出，但 /GL 不应影响此事） - peterchen

Answer 5

正如许多人所说：这取决于情况。

如果你想确保，你应该尝试强制进行编译时决策。模板经常很有用：

for (condition)
  do_it<flag>();

- sbi

Answer 6

我会谨慎地说它是否会。它能保证这个值不会被此线程或其他线程修改吗？

话虽如此，代码的第二个版本通常更易读，而且它可能是代码块中最后需要优化的部分。

- patros

---

@patros - 如果它是一个局部变量，多线程就不需要发挥作用。即使变量对其他线程可见，编译器仍然可以执行优化 - 除非您将其标记为volatile，否则编译器不需要在每次访问时重新获取并且代码生成是有效的。 - Michael

@Michael - 我同意，但是在这个片段中我们没有看到flag的定义，所以它可能不是局部的。我也同意编译器可以合法地优化这个代码，只是不能保证它总是会这样做。如果它会这样做，那可能取决于变量作用域和编译器标志。 - patros

Answer 7

这被称为循环不变式，优化被称为循环不变式代码移动，也叫代码提升。它在条件语句中的事实肯定会使代码分析更加复杂，编译器可能会根据优化器的智能程度来反转循环和条件语句。

对于这种问题的任何具体情况都有一个通用的答案，那就是编译程序并查看生成的代码。

- DigitalRoss