C++：编译器能优化这段代码吗？

Question

void foo(const int constant)
{
    for(int i = 0; i < 1000000; i++) {
        // do stuff
        if(constant < 10) {              // Condition is tested million times :(
            // inner loop stuff
        }
    }
}

每次执行外部循环时都会检查“constant”的值。然而，"constant"从未改变过，因此反复测试条件 "constant < 10?"浪费了大量CPU时间。人类在几次通过后就会意识到"constant"永远不会改变，并且聪明地避免反复检查它。编译器是否能够注意到这一点并进行智能优化，或者重复的if循环是不可避免的？

个人认为问题是不可避免的。即使编译器将比较放在外部循环之前，并设置某种布尔变量"skip_inner_stuff"，该变量仍然必须在每次外部for循环中进行检查。

你对此有何想法？是否有更有效的方法来编写上面的代码段以避免这个问题？

- user1299784

---

我认为一个好的优化器可以做到这一点。你检查了生成的汇编代码吗？ - user529758

编译器很可能会优化掉这个测试。最好的方法是生成汇编代码并自行查看。 - Jonathan Potter

如果你的编译器在发布模式下（并且没有#pragma或指令不优化）不能对此进行优化，那么我建议你寻找一个新的编译器... - Mitch Wheat

@MitchWheat：嗯，根据do stuff的大小，您可能会发现编译器选择不优化它。这是有道理的，因为除非在将constant作为i.c.e内联到调用foo的位置，否则必须复制do stuff。此外，如果do stuff是大量代码，则分支的成本可能相对较低。因此，我认为标准应该是编译器能够执行优化，而不一定是它实际上在这个提问者的真实代码中执行了优化 :-) - Steve Jessop

请参见Oak下面的答案。 - Mitch Wheat

即使编译器不对其进行优化，常量也可能被保留在寄存器中，不会再次加载。CPU将识别分支谓词模式，因此与分支假谓词相比，if检查的成本将是可以忽略的。 - ZijingWu

Answer 1

您所描述的优化也被称为循环展开。它已经成为许多年来优化编译器的标准部分 - 但如果您想确保编译器执行它，请使用一些优化级别（例如，在gcc中使用-O2）编译示例代码并检查生成的代码。

然而，在编译器无法证明代码在整个循环期间不变的情况下 - 例如，调用在编译时不可用的外部函数 - 那么手动将代码提升到循环外部确实可以获得非常大的性能提升。

- Oak

---

我认为更为常见的名称是“循环不变式代码移动”。 - user541686

不，这不是循环不变代码移动，这是循环展开。 - chill

@chill 我不同意。这主要是将(constant < 10)常量折叠为true或false，然后根据情况进行（a）删除多余的测试，如果它折叠为true，或者（b）消除死代码，如果它折叠为false。只有当测试包含变量时，才会进行循环展开。 - user207421

我认为这个问题的核心是关于在循环内不会改变的东西，不一定是编译时常量。所以if语句必须在运行时执行，但可以提升到循环外部。 - Oak

这个问题明确说明了常量<10，毫无疑问。 - user207421

@EJP: constant不是一个编译时常量，除非对foo的调用已内联到将编译时常量作为参数表达式传递的位置。不要被const所迷惑 - 除非指向constant的指针或引用逃逸出此函数，否则声明constant为const既不会帮助也不会妨碍优化器。 - Steve Jessop

Answer 2

编译器可以优化代码，但是你不能期望它在你的代码上施展魔法。

优化强烈依赖于你的代码和你的代码的使用方式。例如，如果你像这样使用foo：

foo(12345);

编译器可以大大优化代码。甚至可以在编译时计算结果。

但是，如果您像这样使用它：

int k;
cin >> k;
foo(k);

在这种情况下，它无法摆脱内部的if（值是在运行时提供的）。

我使用MinGW/GCC-4.8.0编写了一个示例代码：

void foo(const int constant)
{
    int x = 0;
    for (int i = 0; i < 1000000; i++)
    {
        x++;
        if (constant < 10)
        {
            x--;
        }
    }
    cout << x << endl;
}

int main()
{
    int k;
    cin >> k;
    foo(k);
}

让我们看一下生成的汇编代码：

004015E1  MOV EAX,0F4240                 // i = 1000000
004015E6  MOV EBP,ESP
004015E8  XOR EDX,EDX
004015EA  PUSH ESI
004015EB  PUSH EBX
004015EC  SUB ESP,10
004015EF  MOV EBX,DWORD PTR SS:[EBP+8]
004015F2  XOR ECX,ECX                    // set ECX to 0
004015F4  CMP EBX,0A                     // if constant < 10
          ^^^^^^^^^^
004015F7  SETGE CL                       // then set ECX to 1
004015FA  ADD EDX,ECX                    // add ECX to i
004015FC  SUB EAX,1                      // i--
004015FF  JNE SHORT 004015F2             // loop if i is not zero

如你所见，代码中存在内部的 if。参见 CMP EBX,0A。

我再次强调，这严重依赖于循环中的行。

- masoud

Answer 3

其他人已经讲述了相关的编译器优化：循环展开将测试条件移动到循环外并提供两个单独的循环体；代码内联有时会向编译器提供constant实际值，以便编译器去除测试条件并无条件执行"内部循环操作"或完全删除它。

此外，请注意，除了编译器所做的任何事情之外，现代CPU设计实际上也会类似于"人们在几次通过后就会意识到常量从不会改变"。这被称为动态分支预测。

关键点在于，检查整数非常便宜，即使进行分支判断也可能非常便宜。潜在的昂贵在于错误预测分支。现代CPU使用各种策略来猜测分支走向，但所有这些策略都将快速开始正确地预测连续一百万次走同一个方向的分支。

我不知道的是，现代CPU是否足够聪明，可以发现constant是循环不变式，并在微码中进行完整的循环展开。但是假设分支预测正确，循环展开可能只是一个次要的优化。编译器针对的处理器族系越特定，它就知道其分支预测质量，并且编译器可以确定循环展开的附加好处是否值得代码膨胀。

当然还有一些最小化CPU，编译器必须提供所有智能。你PC上的CPU不是其中之一。

- Steve Jessop

Answer 4

你可以手动优化它：

void foo(const int constant)
{
    if (constant < 10) {
        for(int i = 0; i < 1000000; i++) {
            // do stuff

           // inner loop stuff here
        }
    } else {
        for(int i = 0; i < 1000000; i++) {
            // do stuff

            // NO inner loop stuff here
        }
    }
}

我不知道大多数编译器是否会做这样的事情，但这似乎并不是太过牵强。

- patmanpato

---

哦，为什么我没想到呢！谢谢回复 :) - user1299784

这基本上是编译器将要做的事情，如果有人乐意依赖编译器进行优化，你可以通过将条件留在循环内部来避免代码重复。 - goji

这被称为“循环展开”，通常在编译器中实现。 - chill

Answer 5

一个好的编译器可能会进行优化。

编译器基于成本分析进行优化。因此，一个好的编译器应该估算每个替代方案（带有和不带有提升）的成本，并选择成本更低的那个。

这意味着如果内部部分的代码很大，优化可能不值得，因为这可能导致指令缓存崩溃。另一方面，如果它很便宜，那么它可以被提升。

如果它出现在分析器中，因为它没有被优化，那么编译器出了问题。

- Matthieu M.

Answer 6

一个好的编译器将会优化它（当启用优化时）。

如果使用GCC，你可以

• 使用以下命令进行编译、优化和生成汇编代码：

   gcc -Wall -O2 -fverbose-asm -S source.c
  

  然后使用一些编辑器或者类似于 less 的分页器查看生成的汇编代码 source.s。

• 要求 GCC 转储大量（数百个！）中间文件并查看其中的中间 gimple 表示：

   gcc -Wall -O2 -fdump-tree-all -c source.c
  

• 使用 MELT 及其 probe 交互式地查看 gimple 中的内部信息。

^{养成使用-Wall参数来编译C++代码时，总是询问所有警告的习惯。}

顺便说一句，在实践中，这种优化（正如其他答案所解释的“循环不变代码外提”）是必不可少的，因为这种类型的中间代码经常出现，例如在函数内联之后....（想象一下多次调用foo被内联...）

- Basile Starynkevitch

---

一个好的编译器会计算出一个估计成本，无论是将检查提升出循环还是不提升，然后选择最便宜的替代方案。 - Matthieu M.

但这个成本估算是优化过程的组成部分，因此编译器正在对其进行优化（如果不值得移动代码，则可以选择不移动）。 - Basile Starynkevitch

Answer 7

实际上，所有现代编译器都进行优化，如果您认为编译器不应进行此优化，则应将变量设置为“volatile”以遵守此优化。

- Santosh Sahu